1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
|
#
#
# The Nimrod Compiler
# (c) Copyright 2012 Andreas Rumpf
#
# See the file "copying.txt", included in this
# distribution, for details about the copyright.
#
## This module implements the pattern matching features for term rewriting
## macro support.
import strutils, ast, astalgo, types, msgs, idents, renderer, wordrecg
# we precompile the pattern here for efficiency into some internal
# stack based VM :-) Why? Because it's fun; I did no benchmarks to see if that
# actually improves performance.
type
TAliasRequest* = enum # first byte of the bytecode determines alias checking
aqNone = 1, # no alias analysis requested
aqShouldAlias, # with some other param
aqNoAlias # request noalias
TOpcode = enum
ppEof = 1, # end of compiled pattern
ppOr, # we could short-cut the evaluation for 'and' and 'or',
ppAnd, # but currently we don't
ppNot,
ppSym,
ppAtom,
ppLit,
ppIdent,
ppCall,
ppSymKind,
ppNodeKind,
ppLValue,
ppLocal,
ppSideEffect,
ppNoSideEffect
TPatternCode = string
const
MaxStackSize* = 64 ## max required stack size by the VM
proc patternError(n: PNode) =
LocalError(n.info, errIllFormedAstX, renderTree(n, {renderNoComments}))
proc add(code: var TPatternCode, op: TOpcode) {.inline.} =
add(code, chr(ord(op)))
proc whichAlias*(p: PSym): TAliasRequest =
if p.typ.constraint != nil:
result = TAliasRequest(p.typ.constraint.strVal[0].ord)
proc compileConstraints(p: PNode, result: var TPatternCode) =
case p.kind
of nkCallKinds:
if p.sons[0].kind != nkIdent:
patternError(p.sons[0])
return
let op = p.sons[0].ident
if p.len == 3:
if op.s == "|" or op.id == ord(wOr):
compileConstraints(p.sons[1], result)
compileConstraints(p.sons[2], result)
result.add(ppOr)
elif op.s == "&" or op.id == ord(wAnd):
compileConstraints(p.sons[1], result)
compileConstraints(p.sons[2], result)
result.add(ppAnd)
else:
patternError(p)
elif p.len == 2 and (op.s == "~" or op.id == ord(wNot)):
compileConstraints(p.sons[1], result)
result.add(ppNot)
else:
patternError(p)
of nkAccQuoted, nkPar:
if p.len == 1:
compileConstraints(p.sons[0], result)
else:
patternError(p)
of nkIdent:
let spec = p.ident.s.normalize
case spec
of "atom": result.add(ppAtom)
of "lit": result.add(ppLit)
of "sym": result.add(ppSym)
of "ident": result.add(ppIdent)
of "call": result.add(ppCall)
of "alias": result[0] = chr(aqShouldAlias.ord)
of "noalias": result[0] = chr(aqNoAlias.ord)
of "lvalue": result.add(ppLValue)
of "local": result.add(ppLocal)
of "sideeffect": result.add(ppSideEffect)
of "nosideeffect": result.add(ppNoSideEffect)
else:
# check all symkinds:
InternalAssert int(high(TSymKind)) < 255
for i in low(TSymKind)..high(TSymKind):
if cmpIgnoreStyle(($i).substr(2), spec) == 0:
result.add(ppSymKind)
result.add(chr(i.ord))
return
# check all nodekinds:
InternalAssert int(high(TNodeKind)) < 255
for i in low(TNodeKind)..high(TNodeKind):
if cmpIgnoreStyle($i, spec) == 0:
result.add(ppNodeKind)
result.add(chr(i.ord))
return
patternError(p)
else:
patternError(p)
proc semNodeKindConstraints*(p: PNode): PNode =
## does semantic checking for a node kind pattern and compiles it into an
## efficient internal format.
assert p.kind == nkCurlyExpr
result = newNodeI(nkStrLit, p.info)
result.strVal = newStringOfCap(10)
result.strVal.add(chr(aqNone.ord))
if p.len >= 2:
for i in 1.. <p.len:
compileConstraints(p.sons[i], result.strVal)
if result.strVal.len > maxStackSize-1:
InternalError(p.info, "parameter pattern too complex")
else:
patternError(p)
result.strVal.add(ppEof)
type
TSideEffectAnalysis = enum
seUnknown, seSideEffect, seNoSideEffect
proc checkForSideEffects(n: PNode): TSideEffectAnalysis =
# XXX is 'raise' a side effect?
case n.kind
of nkCallKinds:
# only calls can produce side effects:
let op = n.sons[0]
if op.kind == nkSym and isRoutine(op.sym):
let s = op.sym
if sfSideEffect in s.flags:
return seSideEffect
# assume no side effect:
result = seNoSideEffect
elif tfNoSideEffect in op.typ.flags:
# indirect call without side effects:
result = seNoSideEffect
else:
# indirect call: assume side effect:
return seSideEffect
# we need to check n[0] too: (FwithSideEffectButReturnsProcWithout)(args)
for i in 0 .. <n.len:
let ret = checkForSideEffects(n.sons[i])
if ret == seSideEffect: return ret
elif ret == seUnknown and result == seNoSideEffect:
result = seUnknown
of nkNone..nkNilLit:
# an atom cannot produce a side effect:
result = seNoSideEffect
else:
for i in 0 .. <n.len:
let ret = checkForSideEffects(n.sons[i])
if ret == seSideEffect: return ret
elif ret == seUnknown and result == seNoSideEffect:
result = seUnknown
type
TAssignableResult* = enum
arNone, # no l-value and no discriminant
arLValue, # is an l-value
arLocalLValue, # is an l-value, but local var; must not escape
# its stack frame!
arDiscriminant # is a discriminant
proc isAssignable*(owner: PSym, n: PNode): TAssignableResult =
## 'owner' can be nil!
result = arNone
case n.kind
of nkSym:
# don't list 'skLet' here:
if n.sym.kind in {skVar, skResult, skTemp}:
if owner != nil and owner.id == n.sym.owner.id and
sfGlobal notin n.sym.flags:
result = arLocalLValue
else:
result = arLValue
of nkDotExpr:
if skipTypes(n.sons[0].typ, abstractInst).kind in {tyVar, tyPtr, tyRef}:
result = arLValue
else:
result = isAssignable(owner, n.sons[0])
if result != arNone and sfDiscriminant in n.sons[1].sym.flags:
result = arDiscriminant
of nkBracketExpr:
if skipTypes(n.sons[0].typ, abstractInst).kind in {tyVar, tyPtr, tyRef}:
result = arLValue
else:
result = isAssignable(owner, n.sons[0])
of nkHiddenStdConv, nkHiddenSubConv, nkConv:
# Object and tuple conversions are still addressable, so we skip them
# XXX why is 'tyOpenArray' allowed here?
if skipTypes(n.typ, abstractPtrs).kind in {tyOpenArray, tyTuple, tyObject}:
result = isAssignable(owner, n.sons[1])
elif compareTypes(n.typ, n.sons[1].typ, dcEqIgnoreDistinct):
# types that are equal modulo distinction preserve l-value:
result = isAssignable(owner, n.sons[1])
of nkHiddenDeref, nkDerefExpr:
result = arLValue
of nkObjUpConv, nkObjDownConv, nkCheckedFieldExpr:
result = isAssignable(owner, n.sons[0])
else:
nil
proc matchNodeKinds*(p, n: PNode): bool =
# matches the parameter constraint 'p' against the concrete AST 'n'.
# Efficiency matters here.
var stack {.noinit.}: array[0..maxStackSize, bool]
# empty patterns are true:
stack[0] = true
var sp = 1
template push(x: bool) =
stack[sp] = x
inc sp
let code = p.strVal
var pc = 1
while true:
case TOpcode(code[pc])
of ppEof: break
of ppOr:
stack[sp-2] = stack[sp-1] or stack[sp-2]
dec sp
of ppAnd:
stack[sp-2] = stack[sp-1] and stack[sp-2]
dec sp
of ppNot: stack[sp-1] = not stack[sp-1]
of ppSym: push n.kind == nkSym
of ppAtom: push isAtom(n)
of ppLit: push n.kind in {nkCharLit..nkNilLit}
of ppIdent: push n.kind == nkIdent
of ppCall: push n.kind in nkCallKinds
of ppSymKind:
let kind = TSymKind(code[pc+1])
push n.kind == nkSym and n.sym.kind == kind
inc pc
of ppNodeKind:
let kind = TNodeKind(code[pc+1])
push n.kind == kind
inc pc
of ppLValue: push isAssignable(nil, n) in {arLValue, arLocalLValue}
of ppLocal: push isAssignable(nil, n) == arLocalLValue
of ppSideEffect: push checkForSideEffects(n) == seSideEffect
of ppNoSideEffect: push checkForSideEffects(n) != seSideEffect
inc pc
result = stack[sp-1]
|