#
#
# The Nim 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
ast, astalgo, types, semdata, sigmatch, msgs, idents, aliases, parampatterns,
trees
type
TPatternContext = object
owner: PSym
mapping: seq[PNode] # maps formal parameters to nodes
formals: int
c: PContext
subMatch: bool # subnode matches are special
PPatternContext = var TPatternContext
proc getLazy(c: PPatternContext, sym: PSym): PNode =
if not isNil(c.mapping):
result = c.mapping[sym.position]
proc putLazy(c: PPatternContext, sym: PSym, n: PNode) =
if isNil(c.mapping): newSeq(c.mapping, c.formals)
c.mapping[sym.position] = n
proc matches(c: PPatternContext, p, n: PNode): bool
proc canonKind(n: PNode): TNodeKind =
## nodekind canonilization for pattern matching
result = n.kind
case result
of nkCallKinds: result = nkCall
of nkStrLit..nkTripleStrLit: result = nkStrLit
of nkFastAsgn: result = nkAsgn
else: discard
proc sameKinds(a, b: PNode): bool {.inline.} =
result = a.kind == b.kind or a.canonKind == b.canonKind
proc sameTrees(a, b: PNode): bool =
if sameKinds(a, b):
case a.kind
of nkSym: result = a.sym == b.sym
of nkIdent: result = a.ident.id == b.ident.id
of nkCharLit..nkInt64Lit: result = a.intVal == b.intVal
of nkFloatLit..nkFloat64Lit: result = a.floatVal == b.floatVal
of nkStrLit..nkTripleStrLit: result = a.strVal == b.strVal
of nkEmpty, nkNilLit: result = true
of nkType: result = sameTypeOrNil(a.typ, b.typ)
else:
if sonsLen(a) == sonsLen(b):
for i in countup(0, sonsLen(a) - 1):
if not sameTrees(a.sons[i], b.sons[i]): return
result = true
proc inSymChoice(sc, x: PNode): bool =
if sc.kind == nkClosedSymChoice:
for i in 0.. <sc.len:
if sc.sons[i].sym == x.sym: return true
elif sc.kind == nkOpenSymChoice:
# same name suffices for open sym choices!
result = sc.sons[0].sym.name.id == x.sym.name.id
proc checkTypes(c: PPatternContext, p: PSym, n: PNode): bool =
# check param constraints first here as this is quite optimized:
if p.constraint != nil:
result = matchNodeKinds(p.constraint, n)
if not result: return
if isNil(n.typ):
result = p.typ.kind in {tyEmpty, tyStmt}
else:
result = sigmatch.argtypeMatches(c.c, p.typ, n.typ)
proc isPatternParam(c: PPatternContext, p: PNode): bool {.inline.} =
result = p.kind == nkSym and p.sym.kind == skParam and p.sym.owner == c.owner
proc matchChoice(c: PPatternContext, p, n: PNode): bool =
for i in 1 .. <p.len:
if matches(c, p.sons[i], n): return true
proc bindOrCheck(c: PPatternContext, param: PSym, n: PNode): bool =
var pp = getLazy(c, param)
if pp != nil:
# check if we got the same pattern (already unified):
result = sameTrees(pp, n) #matches(c, pp, n)
elif n.kind == nkArgList or checkTypes(c, param, n):
putLazy(c, param, n)
result = true
proc gather(c: PPatternContext, param: PSym, n: PNode) =
var pp = getLazy(c, param)
if pp != nil and pp.kind == nkArgList:
pp.add(n)
else:
pp = newNodeI(nkArgList, n.info, 1)
pp.sons[0] = n
putLazy(c, param, pp)
proc matchNested(c: PPatternContext, p, n: PNode, rpn: bool): bool =
# match ``op * param`` or ``op *| param``
proc matchStarAux(c: PPatternContext, op, n, arglist: PNode,
rpn: bool): bool =
result = true
if n.kind in nkCallKinds and matches(c, op.sons[1], n.sons[0]):
for i in 1..sonsLen(n)-1:
if not matchStarAux(c, op, n[i], arglist, rpn): return false
if rpn: arglist