If you weren't aware of this (I wasn't until a couple days ago), there is actually a whole subfield of computer science dedicated to pattern matching. You may find some big inspiration by browsing the literature.
I mention this because I recently stumbled upon the existence of this subfield in the context of the Mathematica programming language, and this hasAncestor match is extremely similar to something that happens in the Mathematica programming language when an "upvalue" is matched, although upvalues are much more general. In Mathematica, for example, you can do: g /: g[x_] + g[y_] := gplus[x, y] which roughly means "whenever you see `g` as you traverse the expression tree, check if the expression tree structure surrounding it looks like g[<arbitrary expression to be bound to `x`>] + g[<arbitrary expression to be bound to `y`>], and if it does, then rewrite that subtree to be `gplus[x,y]`". The behavior needed to perform such matching efficiently seems to be highly relevant to hasAncestor. --Sean Silva On Wed, Sep 5, 2012 at 9:53 AM, Manuel Klimek <[email protected]> wrote: > Hi djasper, mdiamond, > > A first shot at implementing the hasAncestor matcher. This builds > on the previous patch that introduced DynTypedNode to build up > a parent map for an dditional degree of freedom in the AST traversal. > > The map is only built once we hit an hasAncestor matcher, in order > to not slow down matching for cases where this is not needed. > > We could implement some speed-ups for special cases, like building up > the parent map as we go and only building up the full map if we break > out of the already visited part of the tree, but that is probably > not going to be worth it, and would make the code significantly more > complex. > > http://llvm-reviews.chandlerc.com/D36 > > Files: > include/clang/ASTMatchers/ASTMatchers.h > include/clang/ASTMatchers/ASTMatchersInternal.h > include/clang/ASTMatchers/ASTTypeTraits.h > lib/ASTMatchers/ASTMatchFinder.cpp > unittests/ASTMatchers/ASTMatchersTest.cpp > > _______________________________________________ > cfe-commits mailing list > [email protected] > http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits > _______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
