From 5f574bf631e973546f6f2c4484cb8ca6480b91d5 Mon Sep 17 00:00:00 2001 From: Manuel Klimek Date: Tue, 16 Jul 2013 13:20:30 +0000 Subject: [PATCH] Fixes another hard to test problem with iterator invalidation. As every match call can recursively call back into the memoized match via a nested traversal matcher (for example: stmt(hasAncestor(stmt(hasDescendant(stmt(hasDescendant(stmt()))))))), and every memoization step might clear the cache, we must not store iterators into the result cache when calling match on a submatcher. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@186411 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/ASTMatchers/ASTMatchFinder.cpp | 129 +++++++++++++++-------------- 1 file changed, 69 insertions(+), 60 deletions(-) diff --git a/lib/ASTMatchers/ASTMatchFinder.cpp b/lib/ASTMatchers/ASTMatchFinder.cpp index e1e5f44c07..9971d589b2 100644 --- a/lib/ASTMatchers/ASTMatchFinder.cpp +++ b/lib/ASTMatchers/ASTMatchFinder.cpp @@ -373,27 +373,31 @@ public: const DynTypedMatcher &Matcher, BoundNodesTreeBuilder *Builder, int MaxDepth, TraversalKind Traversal, BindKind Bind) { + // For AST-nodes that don't have an identity, we can't memoize. + if (!Node.getMemoizationData()) + return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal, + Bind); + MatchKey Key; Key.MatcherID = Matcher.getID(); Key.Node = Node; // Note that we key on the bindings *before* the match. Key.BoundNodes = *Builder; - // For AST-nodes that don't have an identity, we can't memoize. - if (!Node.getMemoizationData()) - return matchesRecursively(Node, Matcher, Builder, MaxDepth, Traversal, - Bind); - - std::pair InsertResult = - ResultCache.insert(std::make_pair(Key, MemoizedMatchResult())); - if (InsertResult.second) { - InsertResult.first->second.Nodes = *Builder; - InsertResult.first->second.ResultOfMatch = - matchesRecursively(Node, Matcher, &InsertResult.first->second.Nodes, - MaxDepth, Traversal, Bind); + MemoizationMap::iterator I = ResultCache.find(Key); + if (I != ResultCache.end()) { + *Builder = I->second.Nodes; + return I->second.ResultOfMatch; } - *Builder = InsertResult.first->second.Nodes; - return InsertResult.first->second.ResultOfMatch; + + MemoizedMatchResult Result; + Result.ResultOfMatch = false; + Result.Nodes = *Builder; + Result.ResultOfMatch = matchesRecursively(Node, Matcher, &Result.Nodes, + MaxDepth, Traversal, Bind); + ResultCache[Key] = Result; + *Builder = Result.Nodes; + return Result.ResultOfMatch; } // Matches children or descendants of 'Node' with 'BaseMatcher'. @@ -502,57 +506,62 @@ private: Key.MatcherID = Matcher.getID(); Key.Node = Node; Key.BoundNodes = *Builder; - std::pair InsertResult = - ResultCache.insert(std::make_pair(Key, MemoizedMatchResult())); - if (InsertResult.second) { - bool Matches = false; - if (Parents.size() == 1) { - // Only one parent - do recursive memoization. - const ast_type_traits::DynTypedNode Parent = Parents[0]; - BoundNodesTreeBuilder Result(*Builder); - if (Matcher.matches(Parent, this, &Result)) { - InsertResult.first->second.Nodes = Result; - Matches = true; - } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { - Matches = memoizedMatchesAncestorOfRecursively(Parent, Matcher, - Builder, MatchMode); - // Once we get back from the recursive call, the result will be the - // same as the parent's result. - InsertResult.first->second.Nodes = *Builder; + + // Note that we cannot use insert and reuse the iterator, as recursive + // calls to match might invalidate the result cache iterators. + MemoizationMap::iterator I = ResultCache.find(Key); + if (I != ResultCache.end()) { + *Builder = I->second.Nodes; + return I->second.ResultOfMatch; + } + MemoizedMatchResult Result; + Result.ResultOfMatch = false; + Result.Nodes = *Builder; + if (Parents.size() == 1) { + // Only one parent - do recursive memoization. + const ast_type_traits::DynTypedNode Parent = Parents[0]; + if (Matcher.matches(Parent, this, &Result.Nodes)) { + Result.ResultOfMatch = true; + } else if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { + // Reset the results to not include the bound nodes from the failed + // match above. + Result.Nodes = *Builder; + Result.ResultOfMatch = memoizedMatchesAncestorOfRecursively( + Parent, Matcher, &Result.Nodes, MatchMode); + // Once we get back from the recursive call, the result will be the + // same as the parent's result. + } + } else { + // Multiple parents - BFS over the rest of the nodes. + llvm::DenseSet Visited; + std::deque Queue(Parents.begin(), + Parents.end()); + while (!Queue.empty()) { + Result.Nodes = *Builder; + if (Matcher.matches(Queue.front(), this, &Result.Nodes)) { + Result.ResultOfMatch = true; + break; } - } else { - // Multiple parents - BFS over the rest of the nodes. - llvm::DenseSet Visited; - std::deque Queue(Parents.begin(), - Parents.end()); - while (!Queue.empty()) { - BoundNodesTreeBuilder Result(*Builder); - if (Matcher.matches(Queue.front(), this, &Result)) { - InsertResult.first->second.Nodes = Result; - Matches = true; - break; - } - if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { - ASTContext::ParentVector Ancestors = - ActiveASTContext->getParents(Queue.front()); - for (ASTContext::ParentVector::const_iterator I = Ancestors.begin(), - E = Ancestors.end(); - I != E; ++I) { - // Make sure we do not visit the same node twice. - // Otherwise, we'll visit the common ancestors as often as there - // are splits on the way down. - if (Visited.insert(I->getMemoizationData()).second) - Queue.push_back(*I); - } + if (MatchMode != ASTMatchFinder::AMM_ParentOnly) { + ASTContext::ParentVector Ancestors = + ActiveASTContext->getParents(Queue.front()); + for (ASTContext::ParentVector::const_iterator I = Ancestors.begin(), + E = Ancestors.end(); + I != E; ++I) { + // Make sure we do not visit the same node twice. + // Otherwise, we'll visit the common ancestors as often as there + // are splits on the way down. + if (Visited.insert(I->getMemoizationData()).second) + Queue.push_back(*I); } - Queue.pop_front(); } + Queue.pop_front(); } - - InsertResult.first->second.ResultOfMatch = Matches; } - *Builder = InsertResult.first->second.Nodes; - return InsertResult.first->second.ResultOfMatch; + ResultCache[Key] = Result; + + *Builder = Result.Nodes; + return Result.ResultOfMatch; } // Implements a BoundNodesTree::Visitor that calls a MatchCallback with -- 2.50.1