Index: clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h =================================================================== --- clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h +++ clang/include/clang/StaticAnalyzer/Core/PathSensitive/SVals.h @@ -133,6 +133,10 @@ return !(*this == R); } + bool operator<(const SVal &R) const { + return getRawKind() < R.getRawKind() && Data < R.Data; + } + bool isUnknown() const { return getRawKind() == UnknownValKind; } @@ -207,6 +211,8 @@ SymExpr::symbol_iterator symbol_end() const { return SymExpr::symbol_end(); } + + const void *getRawData() const { return Data; } }; inline raw_ostream &operator<<(raw_ostream &os, clang::ento::SVal V) { Index: clang/include/clang/StaticAnalyzer/SADMatchers/RecursiveSADVisitor.h =================================================================== --- /dev/null +++ clang/include/clang/StaticAnalyzer/SADMatchers/RecursiveSADVisitor.h @@ -0,0 +1,447 @@ +//===--- RecursiveSADVisitor.h - Recursive SAD Visitor ----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file is a copy-paste of the original RecursiveASTVisitor.h. +// The terminology "SAD" stands for the Static Analyzer Data. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_SADMATCHERS_RECURSIVESADVISITOR_H +#define LLVM_CLANG_STATICANALYZER_SADMATCHERS_RECURSIVESADVISITOR_H + +#include "clang/Basic/LLVM.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" + +namespace clang { +namespace ento { + +// A helper macro to implement short-circuiting when recursing. It +// invokes CALL_EXPR, which must be a method call, on the derived +// object (s.t. a user of RecursiveASTVisitor can override the method +// in CALL_EXPR). +#define TRY_TO(CALL_EXPR) \ + do { \ + if (!getDerived().CALL_EXPR) \ + return false; \ + } while (false); + +template class RecursiveSADVisitor { +public: + /// Return a reference to the derived class. + Derived &getDerived() { return *static_cast(this); } + + /// Recursively visit a symbolic value. + bool TraverseSVal(SVal V); + + /// Recursively visit a memory region. + bool TraverseMemRegion(const MemRegion *MR); + + /// Recursively visit a symbolic expression. + bool TraverseSymExpr(const SymExpr *SE); + + // SVal. + // Declare Traverse*() for all concerete SVal classes. +#define ABSTRACT_SVAL(Id, Parent) +#define BASIC_SVAL(Id, Parent) bool Traverse##Id(Id V); +#define LOC_SVAL(Id, Parent) bool TraverseLoc##Id(loc ::Id V); +#define NONLOC_SVAL(Id, Parent) bool TraverseNonLoc##Id(nonloc ::Id V); +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" + + // Define empty Visit*() for all SVal classes. + bool VisitSVal(SVal V) { return true; } +#define BASIC_SVAL(Id, Parent) \ + bool Visit##Id(Id V) { return true; } +#define LOC_SVAL(Id, Parent) \ + bool VisitLoc##Id(loc ::Id V) { return true; } +#define NONLOC_SVAL(Id, Parent) \ + bool VisitNonLoc##Id(nonloc ::Id V) { return true; } +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" + + // MemRegion. + // Declare Traverse*() for all concerete MemRegion classes. +#define ABSTRACT_REGION(Id, Parent) +#define REGION(Id, Parent) bool Traverse##Id(const Id *MR); +#include "clang/StaticAnalyzer/Core/PathSensitive/Regions.def" + + // Define empty Visit*() for all MemRegion classes. + bool VisitMemRegion(const MemRegion *MR) { return true; } +#define REGION(Id, Parent) \ + bool Visit##Id(const Id *MR) { return true; } +#define ABSTRACT_REGION(Id, Parent) REGION(Id, Parent) +#include "clang/StaticAnalyzer/Core/PathSensitive/Regions.def" + + // SymExpr. + // Declare Traverse*() for all concerete SymExpr classes. +#define ABSTRACT_SYMBOL(Id, Parent) +#define SYMBOL(Id, Parent) bool Traverse##Id(const Id *SE); +#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def" + + // Define empty Visit*() for all SymExpr classes. + bool VisitSymExpr(const SymExpr *SE) { return true; } +#define SYMBOL(Id, Parent) \ + bool Visit##Id(const Id *SE) { return true; } +#define ABSTRACT_SYMBOL(Id, Parent) SYMBOL(Id, Parent) +#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def" +}; + +//===----------------------------------------------------------------------===// +// SVal. +//===----------------------------------------------------------------------===// + +#define DISPATCH(NAME, CLASS) \ + return getDerived().Traverse##NAME(V.castAs()) + +template +bool RecursiveSADVisitor::TraverseSVal(SVal V) { + // Use namespace loc and nonloc. + switch (V.getBaseKind()) { +#define BASIC_SVAL(Id, Parent) \ + case SVal::Id##Kind: \ + DISPATCH(Id, Id); +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" + case SVal::LocKind: + switch (V.getSubKind()) { +#define LOC_SVAL(Id, Parent) \ + case loc::Id##Kind: \ + DISPATCH(Loc##Id, loc ::Id); +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" + } + case SVal::NonLocKind: + switch (V.getSubKind()) { +#define NONLOC_SVAL(Id, Parent) \ + case nonloc::Id##Kind: \ + DISPATCH(NonLoc##Id, nonloc ::Id); +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.def" + } + } + llvm_unreachable("Unhandled SVal"); +} + +#undef DISPATCH + +template +bool RecursiveSADVisitor::TraverseUnknownVal(UnknownVal V) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseUndefinedVal(UndefinedVal V) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseLocConcreteInt(loc::ConcreteInt V) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseLocGotoLabel(loc::GotoLabel V) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseLocMemRegionVal( + loc::MemRegionVal V) { + TRY_TO(TraverseMemRegion(V.getRegion())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseNonLocConcreteInt( + nonloc::ConcreteInt V) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseNonLocCompoundVal( + nonloc::CompoundVal V) { + for (const SVal V : llvm::make_range(V.begin(), V.end())) + TRY_TO(TraverseSVal(V)) + return true; +} + +template +bool RecursiveSADVisitor::TraverseNonLocLazyCompoundVal( + nonloc::LazyCompoundVal V) { + TRY_TO(TraverseMemRegion(V.getRegion())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseNonLocLocAsInteger( + nonloc::LocAsInteger V) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseNonLocPointerToMember( + nonloc::PointerToMember V) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseNonLocSymbolVal( + nonloc::SymbolVal V) { + TRY_TO(TraverseSymExpr(V.getSymbol())) + return true; +} + +//===----------------------------------------------------------------------===// +// MemRegion. +//===----------------------------------------------------------------------===// + +#define DISPATCH(CLASS) return getDerived().Traverse##CLASS(cast(MR)) + +template +bool RecursiveSADVisitor::TraverseMemRegion(const MemRegion *MR) { + switch (MR->getKind()) { +#define REGION(Id, Parent) \ + case MemRegion::Id##Kind: \ + DISPATCH(Id); +#include "clang/StaticAnalyzer/Core/PathSensitive/Regions.def" + } + llvm_unreachable("Unhandled MemRegion"); +} + +#undef DISPATCH + +template +bool RecursiveSADVisitor::TraverseAllocaRegion( + const AllocaRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseElementRegion( + const ElementRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseFieldRegion(const FieldRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseStringRegion( + const StringRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymbolicRegion( + const SymbolicRegion *MR) { + TRY_TO(TraverseSymExpr(MR->getSymbol())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseVarRegion(const VarRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseBlockCodeRegion( + const BlockCodeRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseBlockDataRegion( + const BlockDataRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseCXXThisRegion( + const CXXThisRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseCodeSpaceRegion( + const CodeSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseCompoundLiteralRegion( + const CompoundLiteralRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseFunctionCodeRegion( + const FunctionCodeRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseHeapSpaceRegion( + const HeapSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseUnknownSpaceRegion( + const UnknownSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseCXXBaseObjectRegion( + const CXXBaseObjectRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseCXXDerivedObjectRegion( + const CXXDerivedObjectRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseCXXTempObjectRegion( + const CXXTempObjectRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseGlobalImmutableSpaceRegion( + const GlobalImmutableSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseGlobalInternalSpaceRegion( + const GlobalInternalSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseGlobalSystemSpaceRegion( + const GlobalSystemSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseObjCIvarRegion( + const ObjCIvarRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseObjCStringRegion( + const ObjCStringRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseStackArgumentsSpaceRegion( + const StackArgumentsSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseStackLocalsSpaceRegion( + const StackLocalsSpaceRegion *MR) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseStaticGlobalSpaceRegion( + const StaticGlobalSpaceRegion *MR) { + return true; +} + +//===----------------------------------------------------------------------===// +// SymExpr. +//===----------------------------------------------------------------------===// + +#define DISPATCH(CLASS) return getDerived().Traverse##CLASS(cast(SE)) + +template +bool RecursiveSADVisitor::TraverseSymExpr(const SymExpr *SE) { + switch (SE->getKind()) { +#define SYMBOL(Id, Parent) \ + case SymExpr::Id##Kind: \ + DISPATCH(Id); +#include "clang/StaticAnalyzer/Core/PathSensitive/Symbols.def" + } + llvm_unreachable("Unhandled SymExpr"); +} + +#undef DISPATCH + +template +bool RecursiveSADVisitor::TraverseIntSymExpr(const IntSymExpr *SE) { + TRY_TO(TraverseSVal(nonloc::ConcreteInt(SE->getLHS()))) + TRY_TO(TraverseSymExpr(SE->getRHS())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymIntExpr(const SymIntExpr *SE) { + TRY_TO(TraverseSymExpr(SE->getLHS())) + TRY_TO(TraverseSVal(nonloc::ConcreteInt(SE->getRHS()))) + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymSymExpr(const SymSymExpr *SE) { + TRY_TO(TraverseSymExpr(SE->getLHS())) + TRY_TO(TraverseSymExpr(SE->getRHS())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymbolCast(const SymbolCast *SE) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymbolConjured( + const SymbolConjured *SE) { + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymbolDerived( + const SymbolDerived *SE) { + // FIXME: Match on parent? + TRY_TO(TraverseMemRegion(SE->getRegion())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymbolExtent( + const SymbolExtent *SE) { + TRY_TO(TraverseMemRegion(SE->getRegion())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymbolMetadata( + const SymbolMetadata *SE) { + TRY_TO(TraverseMemRegion(SE->getRegion())) + return true; +} + +template +bool RecursiveSADVisitor::TraverseSymbolRegionValue( + const SymbolRegionValue *SE) { + TRY_TO(TraverseMemRegion(SE->getRegion())) + return true; +} + +} // namespace ento +} // namespace clang + +#endif // LLVM_CLANG_STATICANALYZER_SADMATCHERS_RECURSIVESADVISITOR_H Index: clang/include/clang/StaticAnalyzer/SADMatchers/SADMatchFinder.h =================================================================== --- /dev/null +++ clang/include/clang/StaticAnalyzer/SADMatchers/SADMatchFinder.h @@ -0,0 +1,101 @@ +//===--- SADMatchFinder.h - Structural query framework ----------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file is a copy-paste of the original ASTMatchFinder.h +// The terminology "SAD" stands for the Static Analyzer Data. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHFINDER_H +#define LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHFINDER_H + +#include "clang/StaticAnalyzer/SADMatchers/SADMatchers.h" +#include "clang/StaticAnalyzer/SADMatchers/SADTypeTraits.h" +#include "llvm/ADT/SmallPtrSet.h" +#include "llvm/ADT/StringMap.h" + +namespace clang { +namespace ento { +namespace sad_matchers { + +/// A class to allow finding matches over the Static Analyzer Data. +class MatchFinder { +public: + /// Contains all information for a given match. + struct MatchResult { + MatchResult(const BoundNodes &Nodes); + + /// Contains the nodes bound on the current match. + const BoundNodes Nodes; + }; + + /// Called when the Match registered for it was successfully found in the SAD. + class MatchCallback { + public: + virtual ~MatchCallback(); + + /// Called on every match by the \c MatchFinder. + virtual void run(const MatchResult &Result) = 0; + + /// An id used to group the matchers. + virtual StringRef getID() const; + }; + + MatchFinder(); + ~MatchFinder(); + + /// Adds a matcher to execute when running over an SVal. + void addMatcher(const SValMatcher &NodeMatch, MatchCallback *Action); + + /// Calls the registered callbacks on all matches on the given \p Node. + template void match(const T &Node) { + match(DynTypedNode::create(Node)); + } + void match(const DynTypedNode &Node); + + /// For each \c Matcher<> a \c MatchCallback that will be called + /// when it matches. + struct MatchersByType { + std::vector> Data; + /// All the callbacks in one container to simplify iteration. + llvm::SmallPtrSet AllCallbacks; + }; + +private: + MatchersByType Matchers; +}; + +namespace internal { +class CollectMatchesCallback : public MatchFinder::MatchCallback { +public: + void run(const MatchFinder::MatchResult &Result) override { + Nodes.push_back(Result.Nodes); + } + SmallVector Nodes; +}; +} // namespace internal + +template +SmallVector match(MatcherT Matcher, const DynTypedNode &Node) { + internal::CollectMatchesCallback Callback; + MatchFinder Finder; + Finder.addMatcher(Matcher, &Callback); + Finder.match(Node); + return std::move(Callback.Nodes); +} + +template +SmallVector match(MatcherT Matcher, const NodeT &Node) { + return match(Matcher, DynTypedNode::create(Node)); +} + +} // namespace sad_matchers +} // namespace ento +} // namespace clang + +#endif // LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHFINDER_H Index: clang/include/clang/StaticAnalyzer/SADMatchers/SADMatchers.h =================================================================== --- /dev/null +++ clang/include/clang/StaticAnalyzer/SADMatchers/SADMatchers.h @@ -0,0 +1,306 @@ +//===- SADMatchers.h - Structural query framework ---------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file is a copy-paste of the original ASTMatchers.h. +// The terminology "SAD" stands for the Static Analyzer Data. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHERS_H +#define LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHERS_H + +#include "clang/ASTMatchers/ASTMatchers.h" +#include "clang/StaticAnalyzer/SADMatchers/SADMatchersInternal.h" +#include "clang/StaticAnalyzer/SADMatchers/SADMatchersMacros.h" +#include "clang/StaticAnalyzer/SADMatchers/SADTypeTraits.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/Compiler.h" +#include "llvm/Support/ErrorHandling.h" +#include "llvm/Support/Regex.h" +#include +#include +#include +#include +#include +#include +#include + +namespace clang { +namespace ento { +namespace sad_matchers { + +/// Maps string IDs to SAD nodes matched by parts of a matcher. +class BoundNodes { +public: + /// Returns the SAD node bound to \c ID. + template const T *getNodeAs(StringRef ID) const { + return MyBoundNodes.getNodeAs(ID); + } + + /// Type of mapping from binding identifiers to bound nodes. This type + /// is an associative container with a key type of \c std::string and a value + /// type of \c clang::DynTypedNode + using IDToNodeMap = internal::BoundNodesMap::IDToNodeMap; + + /// Retrieve mapping from binding identifiers to bound nodes. + const IDToNodeMap &getMap() const { return MyBoundNodes.getMap(); } + +private: + friend class internal::BoundNodesTreeBuilder; + + /// Create BoundNodes from a pre-filled map of bindings. + BoundNodes(internal::BoundNodesMap &MyBoundNodes) + : MyBoundNodes(MyBoundNodes) {} + + internal::BoundNodesMap MyBoundNodes; +}; + +/// SVal is the entry point of matching SAD nodes. +using SValMatcher = internal::Matcher; + +/// Matches any node. +inline internal::TrueMatcher anything() { return internal::TrueMatcher(); } + +/// Matches if each of the given matchers matches. +extern const internal::VariadicOperatorMatcherFunc< + 2, std::numeric_limits::max()> + eachOf; + +/// Matches if any of the given matchers matches. +extern const internal::VariadicOperatorMatcherFunc< + 2, std::numeric_limits::max()> + anyOf; + +/// Matches if all given matchers match. +extern const internal::VariadicOperatorMatcherFunc< + 2, std::numeric_limits::max()> + allOf; + +/// Matches SAD nodes that have child SAD nodes that match the +/// provided matcher. +extern const internal::ArgumentAdaptingMatcherFunc has; + +/// Matches SAD nodes that have descendant SAD nodes that match the +/// provided matcher. +extern const internal::ArgumentAdaptingMatcherFunc< + internal::HasDescendantMatcher> + hasDescendant; + +/// Matches SAD nodes that have child SAD nodes that match the +/// provided matcher. +extern const internal::ArgumentAdaptingMatcherFunc + forEach; + +/// Matches SAD nodes that have descendant SAD nodes that match the +/// provided matcher. +extern const internal::ArgumentAdaptingMatcherFunc< + internal::ForEachDescendantMatcher> + forEachDescendant; + +/// Matches if the node or any descendant matches. +template +internal::Matcher findAll(const internal::Matcher &Matcher) { + return eachOf(Matcher, forEachDescendant(Matcher)); +} + +/// Matches if the provided matcher does not match. +extern const internal::VariadicOperatorMatcherFunc<1, 1> unless; + +SAD_POLYMORPHIC_MATCHER_P(equals, + SAD_POLYMORPHIC_SUPPORTED_TYPES(nonloc::ConcreteInt, + loc::ConcreteInt), + unsigned, Value) { + return internal::ValueEqualsMatcher(Value).matchesNode( + Node); +} + +SAD_MATCHER_P(BinarySymExpr, hasOperatorName, std::string, Name) { + return Name == BinaryOperator::getOpcodeStr(Node.getOpcode()); +} + +/// Matches operator expressions that have any of the specified names. +extern const internal::VariadicFunction< + internal::PolymorphicMatcherWithParam1< + internal::HasAnyOperatorNameMatcher, std::vector, + SAD_POLYMORPHIC_SUPPORTED_TYPES(BinarySymExpr)>, + StringRef, internal::hasAnyOperatorNameFunc> + hasAnyOperatorName; + +/// Matches if a node equals a previously bound node. +SAD_POLYMORPHIC_MATCHER_P(equalsBoundNode, + SAD_POLYMORPHIC_SUPPORTED_TYPES(SVal, MemRegion, + SymExpr), + std::string, ID) { + internal::NotEqualsBoundNodePredicate Predicate; + Predicate.ID = ID; + Predicate.Node = DynTypedNode::create(Node); + return Builder->removeBindings(Predicate); +} + +SAD_MATCHER_P_OVERLOAD(SVal, equalsNode, SVal, Other, 0) { + return &Node == &Other; +} + +SAD_MATCHER_P_OVERLOAD(MemRegion, equalsNode, const MemRegion *, Other, 1) { + return &Node == Other; +} + +SAD_MATCHER_P_OVERLOAD(SymExpr, equalsNode, const SymExpr *, Other, 2) { + return &Node == Other; +} + +//===----------------------------------------------------------------------===// +// SymExpr. +//===----------------------------------------------------------------------===// + +SAD_POLYMORPHIC_MATCHER_P_OVERLOAD( + hasLHS, SAD_POLYMORPHIC_SUPPORTED_TYPES(SymIntExpr, SymSymExpr), + internal::Matcher, InnerMatcher, 0) { + const SymExpr *LHS = Node.getLHS(); + return InnerMatcher.matches(*LHS, Finder, Builder); +} + +SAD_MATCHER_P_OVERLOAD(IntSymExpr, hasLHS, + internal::Matcher, InnerMatcher, + 1) { + nonloc::ConcreteInt LHS(Node.getLHS()); + return InnerMatcher.matches(LHS, Finder, Builder); +} + +SAD_POLYMORPHIC_MATCHER_P_OVERLOAD( + hasRHS, SAD_POLYMORPHIC_SUPPORTED_TYPES(IntSymExpr, SymSymExpr), + internal::Matcher, InnerMatcher, 0) { + const SymExpr *RHS = Node.getLHS(); + return InnerMatcher.matches(*RHS, Finder, Builder); +} + +SAD_MATCHER_P_OVERLOAD(SymIntExpr, hasRHS, + internal::Matcher, InnerMatcher, + 1) { + nonloc::ConcreteInt RHS(Node.getRHS()); + return InnerMatcher.matches(RHS, Finder, Builder); +} + +//===----------------------------------------------------------------------===// +// MemRegion. +//===----------------------------------------------------------------------===// + +SAD_MATCHER_P(MemRegion, hasBaseRegion, internal::Matcher, + InnerMatcher) { + return InnerMatcher.matches(*Node.getBaseRegion(), Finder, Builder); +} + +SAD_MATCHER_P(MemRegion, hasSymbolicBase, internal::Matcher, + InnerMatcher) { + const SymbolicRegion *SR = Node.getSymbolicBase(); + return SR && InnerMatcher.matches(*SR, Finder, Builder); +} + +SAD_MATCHER_P(MemRegion, hasSuperRegion, internal::Matcher, + InnerMatcher) { + const auto *SR = Node.getAs(); + return SR && InnerMatcher.matches(*SR->getSuperRegion(), Finder, Builder); +} + +SAD_MATCHER_P(MemRegion, hasMostDerivedObjectRegion, + internal::Matcher, InnerMatcher) { + return InnerMatcher.matches(*Node.getMostDerivedObjectRegion(), Finder, + Builder); +} + +SAD_MATCHER_P(MemRegion, hasMemorySpace, internal::Matcher, + InnerMatcher) { + return InnerMatcher.matches(*Node.getMemorySpace(), Finder, Builder); +} + +SAD_MATCHER_P(MemRegion, isSubRegionOf, const MemRegion *, MR) { + return Node.isSubRegionOf(MR); +} + +SAD_MATCHER_P(VarRegion, hasName, std::string, Name) { + return Node.getDecl()->getNameAsString() == Name; +} + +//===----------------------------------------------------------------------===// +// Basic definitions. +//===----------------------------------------------------------------------===// + +extern const internal::VariadicAllOfMatcher sVal; +template +using SValMatch = const internal::VariadicDynCastAllOfMatcher; +extern SValMatch definedSVal; +extern SValMatch definedOrUnknownSVal; +extern SValMatch undefinedVal; +extern SValMatch unknownVal; +extern SValMatch locConcreteInt; +extern SValMatch locGotoLabel; +extern SValMatch locMemRegionVal; +extern SValMatch compoundVal; +extern SValMatch nonLocConcreteInt; +extern SValMatch lazyCompoundVal; +extern SValMatch locAsInteger; +extern SValMatch pointerToMember; +extern SValMatch symbolVal; + +extern const internal::VariadicAllOfMatcher memRegion; +template +using MemRegionMatch = + const internal::VariadicDynCastAllOfMatcher; +extern MemRegionMatch allocaRegion; +extern MemRegionMatch blockCodeRegion; +extern MemRegionMatch blockDataRegion; +extern MemRegionMatch codeTextRegion; +extern MemRegionMatch compoundLiteralRegion; +extern MemRegionMatch cxxThisRegion; +extern MemRegionMatch declRegion; +extern MemRegionMatch elementRegion; +extern MemRegionMatch fieldRegion; +extern MemRegionMatch functionCodeRegion; +extern MemRegionMatch stringRegion; +extern MemRegionMatch subRegion; +extern MemRegionMatch symbolicRegion; +extern MemRegionMatch typedRegion; +extern MemRegionMatch typedValueRegion; +extern MemRegionMatch varRegion; +extern MemRegionMatch codeSpaceRegion; +extern MemRegionMatch globalImmutableSpaceRegion; +extern MemRegionMatch globalInternalSpaceRegion; +extern MemRegionMatch globalSystemSpaceRegion; +extern MemRegionMatch globalsSpaceRegion; +extern MemRegionMatch heapSpaceRegion; +extern MemRegionMatch memSpaceRegion; +extern MemRegionMatch nonStaticGlobalSpaceRegion; +extern MemRegionMatch stackSpaceRegion; +extern MemRegionMatch stackArgumentsSpaceRegion; +extern MemRegionMatch stackLocalsSpaceRegion; +extern MemRegionMatch staticGlobalSpaceRegion; +extern MemRegionMatch unknownSpaceRegion; + +extern const internal::VariadicAllOfMatcher symExpr; +template +using SymExprMatch = const internal::VariadicDynCastAllOfMatcher; +extern SymExprMatch binarySymExpr; +extern SymExprMatch intSymExpr; +extern SymExprMatch symIntExpr; +extern SymExprMatch symSymExpr; +extern SymExprMatch symbolCast; +extern SymExprMatch symbolConjured; +extern SymExprMatch symbolData; +extern SymExprMatch symbolDerived; +extern SymExprMatch symbolExtent; +extern SymExprMatch symbolRegionValue; +extern SymExprMatch symbolMetadata; + +} // namespace sad_matchers +} // namespace ento +} // namespace clang + +#endif // LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHERS_H Index: clang/include/clang/StaticAnalyzer/SADMatchers/SADMatchersInternal.h =================================================================== --- /dev/null +++ clang/include/clang/StaticAnalyzer/SADMatchers/SADMatchersInternal.h @@ -0,0 +1,1087 @@ +//===- SADMatchersInternal.h - Structural query framework -------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// This file is a copy-paste of the original ASTMatchersInternal.h +// The terminology "SAD" stands for the Static Analyzer Data. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHERSINTERNAL_H +#define LLVM_CLANG_STATICANALYZER_SADMATCHERS_SADMATCHERSINTERNAL_H + +#include "clang/ASTMatchers/ASTMatchersInternal.h" +#include "clang/Basic/LLVM.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/MemRegion.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SVals.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SymExpr.h" +#include "clang/StaticAnalyzer/Core/PathSensitive/SymbolManager.h" +#include "clang/StaticAnalyzer/SADMatchers/SADTypeTraits.h" +#include "llvm/ADT/APFloat.h" +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/ArrayRef.h" +#include "llvm/ADT/IntrusiveRefCntPtr.h" +#include "llvm/ADT/None.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/StringRef.h" +#include "llvm/ADT/iterator.h" +#include "llvm/Support/Casting.h" +#include "llvm/Support/ManagedStatic.h" +#include +#include +#include +#include +#include +#include +#include +#include +#include +#include + +namespace clang { +namespace ento { +namespace sad_matchers { + +class BoundNodes; + +namespace internal { + +/// Internal version of BoundNodes. Holds all the bound nodes. +class BoundNodesMap { +public: + /// Adds \c Node to the map with key \c ID. + /// + /// The node's base type should be in NodeBaseType or it will be unaccessible. + void addNode(StringRef ID, const DynTypedNode &DynNode) { + NodeMap[std::string(ID)] = DynNode; + } + + /// Returns the SAD node bound to \c ID. + /// + /// Returns NULL if there was no node bound to \c ID or if there is a node but + /// it cannot be converted to the specified type. + template const T *getNodeAs(StringRef ID) const { + IDToNodeMap::const_iterator It = NodeMap.find(ID); + if (It == NodeMap.end()) { + return nullptr; + } + return It->second.get(); + } + + DynTypedNode getNode(StringRef ID) const { + IDToNodeMap::const_iterator It = NodeMap.find(ID); + if (It == NodeMap.end()) { + return DynTypedNode(); + } + return It->second; + } + + /// Imposes an order on BoundNodesMaps. + bool operator<(const BoundNodesMap &Other) const { + return NodeMap < Other.NodeMap; + } + + /// A map from IDs to the bound nodes. + /// + /// Note that we're using std::map here, as for memoization: + /// - we need a comparison operator + /// - we need an assignment operator + using IDToNodeMap = std::map>; + + const IDToNodeMap &getMap() const { return NodeMap; } + + /// Returns \c true if this \c BoundNodesMap can be compared, i.e. all + /// stored nodes have memoization data. + bool isComparable() const { + for (const auto &IDAndNode : NodeMap) { + if (!IDAndNode.second.getMemoizationData()) + return false; + } + return true; + } + +private: + IDToNodeMap NodeMap; +}; + +/// Creates BoundNodesTree objects. +/// +/// The tree builder is used during the matching process to insert the bound +/// nodes from the Id matcher. +class BoundNodesTreeBuilder { +public: + /// A visitor interface to visit all BoundNodes results for a + /// BoundNodesTree. + class Visitor { + public: + virtual ~Visitor() = default; + + /// Called multiple times during a single call to VisitMatches(...). + /// + /// 'BoundNodesView' contains the bound nodes for a single match. + virtual void visitMatch(const BoundNodes &BoundNodesView) = 0; + }; + + /// Add a binding from an id to a node. + void setBinding(StringRef Id, const DynTypedNode &DynNode) { + if (Bindings.empty()) + Bindings.emplace_back(); + for (BoundNodesMap &Binding : Bindings) + Binding.addNode(Id, DynNode); + } + + /// Adds a branch in the tree. + void addMatch(const BoundNodesTreeBuilder &Bindings); + + /// Visits all matches that this BoundNodesTree represents. + /// + /// The ownership of 'ResultVisitor' remains at the caller. + void visitMatches(Visitor *ResultVisitor); + + template + bool removeBindings(const ExcludePredicate &Predicate) { + Bindings.erase(std::remove_if(Bindings.begin(), Bindings.end(), Predicate), + Bindings.end()); + return !Bindings.empty(); + } + + /// Imposes an order on BoundNodesTreeBuilders. + bool operator<(const BoundNodesTreeBuilder &Other) const { + return Bindings < Other.Bindings; + } + + /// Returns \c true if this \c BoundNodesTreeBuilder can be compared, + /// i.e. all stored node maps have memoization data. + bool isComparable() const { + for (const BoundNodesMap &NodesMap : Bindings) { + if (!NodesMap.isComparable()) + return false; + } + return true; + } + +private: + SmallVector Bindings; +}; + +class SADMatchFinder; + +/// Generic interface for all matchers. +/// +/// Used by the implementation of Matcher and DynTypedMatcher. +/// In general, implement MatcherInterface or SingleNodeMatcherInterface +/// instead. +class DynMatcherInterface + : public llvm::ThreadSafeRefCountedBase { +public: + virtual ~DynMatcherInterface() = default; + + /// Returns true if \p DynNode can be matched. + /// + /// May bind \p DynNode to an ID via \p Builder, or recurse into + /// the SAD via \p Finder. + virtual bool dynMatches(const DynTypedNode &DynNode, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const = 0; +}; + +/// Generic interface for matchers on an SAD node of type T. +/// +/// Implement this if your matcher may need to inspect the children or +/// descendants of the node or bind matched nodes to names. If you are +/// writing a simple matcher that only inspects properties of the +/// current node and doesn't care about its children or descendants, +/// implement SingleNodeMatcherInterface instead. +template class MatcherInterface : public DynMatcherInterface { +public: + /// Returns true if 'Node' can be matched. + /// + /// May bind 'Node' to an ID via 'Builder', or recurse into + /// the SAD via 'Finder'. + virtual bool matches(const T &Node, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const = 0; + + bool dynMatches(const DynTypedNode &DynNode, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const override { + return matches(DynNode.getUnchecked(), Finder, Builder); + } +}; + +/// Interface for matchers that only evaluate properties on a single +/// node. +template +class SingleNodeMatcherInterface : public MatcherInterface { +public: + /// Returns true if the matcher matches the provided node. + /// + /// A subclass must implement this instead of Matches(). + virtual bool matchesNode(const T &Node) const = 0; + +private: + /// Implements MatcherInterface::Matches. + bool matches(const T &Node, SADMatchFinder * /* Finder */, + BoundNodesTreeBuilder * /* Builder */) const override { + return matchesNode(Node); + } +}; + +template class Matcher; + +/// Matcher that works on a \c DynTypedNode. +/// +/// It is constructed from a \c Matcher object and redirects most calls to +/// underlying matcher. +/// It checks whether the \c DynTypedNode is convertible into the type of the +/// underlying matcher and then do the actual match on the actual node, or +/// return false if it is not convertible. +class DynTypedMatcher { +public: + /// Takes ownership of the provided implementation pointer. + template + DynTypedMatcher(MatcherInterface *Implementation) + : SupportedKind(SADNodeKind::getFromNodeKind()), + RestrictKind(SupportedKind), Implementation(Implementation) {} + + /// Construct from a variadic function. + enum VariadicOperator { + /// Matches nodes for which all provided matchers match. + VO_AllOf, + + /// Matches nodes for which at least one of the provided matchers + /// matches. + VO_AnyOf, + + /// Matches nodes for which at least one of the provided matchers + /// matches, but doesn't stop at the first match. + VO_EachOf, + + /// Matches any node but executes all inner matchers to find result + /// bindings. + VO_Optionally, + + /// Matches nodes that do not match the provided matcher. + /// + /// Uses the variadic matcher interface, but fails if + /// InnerMatchers.size() != 1. + VO_UnaryNot + }; + + static DynTypedMatcher + constructVariadic(VariadicOperator Op, SADNodeKind SupportedKind, + std::vector InnerMatchers); + + static DynTypedMatcher + constructRestrictedWrapper(const DynTypedMatcher &InnerMatcher, + SADNodeKind RestrictKind); + + /// Get a "true" matcher for \p NodeKind. + /// + /// It only checks that the node is of the right kind. + static DynTypedMatcher trueMatcher(SADNodeKind NodeKind); + + void setAllowBind(bool AB) { AllowBind = AB; } + + /// Check whether this matcher could ever match a node of kind \p Kind. + /// \return \c false if this matcher will never match such a node. Otherwise, + /// return \c true. + bool canMatchNodesOfKind(SADNodeKind Kind) const; + + /// Return a matcher that points to the same implementation, but + /// restricts the node types for \p Kind. + DynTypedMatcher dynCastTo(const SADNodeKind Kind) const { + auto Copy = *this; + Copy.SupportedKind = Kind; + Copy.RestrictKind = SADNodeKind::getMostDerivedType(Kind, RestrictKind); + return Copy; + } + + /// Returns true if the matcher matches the given \c DynNode. + bool matches(const DynTypedNode &DynNode, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const; + + /// Same as matches(), but skips the kind check. + /// + /// It is faster, but the caller must ensure the node is valid for the + /// kind of this matcher. + bool matchesNoKindCheck(const DynTypedNode &DynNode, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const; + + class IdDynMatcher : public DynMatcherInterface { + public: + IdDynMatcher(StringRef ID, + IntrusiveRefCntPtr InnerMatcher) + : ID(ID), InnerMatcher(std::move(InnerMatcher)) {} + + bool dynMatches(const DynTypedNode &DynNode, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const override { + bool Result = InnerMatcher->dynMatches(DynNode, Finder, Builder); + if (Result) + Builder->setBinding(ID, DynNode); + return Result; + } + + private: + const std::string ID; + const IntrusiveRefCntPtr InnerMatcher; + }; + + /// Bind the specified \p ID to the matcher. + /// \return A new matcher with the \p ID bound to it if this matcher supports + /// binding. Otherwise, returns an empty \c Optional<>. + llvm::Optional tryBind(StringRef ID) const { + if (!AllowBind) + return llvm::None; + auto Result = *this; + Result.Implementation = + new IdDynMatcher(ID, std::move(Result.Implementation)); + return std::move(Result); + } + + /// Returns a unique \p ID for the matcher. + /// + /// Casting a Matcher to Matcher creates a matcher that has the + /// same \c Implementation pointer, but different \c RestrictKind. We need to + /// include both in the ID to make it unique. + /// + /// \c MatcherIDType supports operator< and provides strict weak ordering. + using MatcherIDType = std::pair; + MatcherIDType getID() const { + /// FIXME: Document the requirements this imposes on matcher + /// implementations (no new() implementation_ during a Matches()). + return std::make_pair(RestrictKind, + reinterpret_cast(Implementation.get())); + } + + /// Returns the type this matcher works on. + /// + /// \c matches() will always return false unless the node passed is of this + /// or a derived type. + SADNodeKind getSupportedKind() const { return SupportedKind; } + + /// Returns \c true if the passed \c DynTypedMatcher can be converted + /// to a \c Matcher. + /// + /// This method verifies that the underlying matcher in \c Other can process + /// nodes of types T. + template bool canConvertTo() const { + return canConvertTo(SADNodeKind::getFromNodeKind()); + } + bool canConvertTo(SADNodeKind To) const; + + /// Construct a \c Matcher interface around the dynamic matcher. + /// + /// This method asserts that \c canConvertTo() is \c true. Callers + /// should call \c canConvertTo() first to make sure that \c this is + /// compatible with T. + template Matcher convertTo() const { + assert(canConvertTo()); + return unconditionalConvertTo(); + } + + /// Same as \c convertTo(), but does not check that the underlying + /// matcher can handle a value of T. + /// + /// If it is not compatible, then this matcher will never match anything. + template Matcher unconditionalConvertTo() const; + +private: + DynTypedMatcher(SADNodeKind SupportedKind, SADNodeKind RestrictKind, + IntrusiveRefCntPtr Implementation) + : SupportedKind(SupportedKind), RestrictKind(RestrictKind), + Implementation(std::move(Implementation)) {} + + bool AllowBind = false; + SADNodeKind SupportedKind; + + /// A potentially stricter node kind. + /// + /// It allows to perform implicit and dynamic cast of matchers without + /// needing to change \c Implementation. + SADNodeKind RestrictKind; + IntrusiveRefCntPtr Implementation; +}; + +template struct SValContent; + +template <> struct SValContent { + static const SymExpr *get(SVal SV) { return SV.getAsSymbol(); } +}; + +template <> struct SValContent { + static const MemRegion *get(SVal SV) { return SV.getAsRegion(); } +}; + +/// Wrapper base class for a wrapping matcher. +/// +/// This is just a container for a DynTypedMatcher that can be used as a base +/// class for another matcher. +template +class WrapperMatcherInterface : public MatcherInterface { +protected: + explicit WrapperMatcherInterface(DynTypedMatcher &&InnerMatcher) + : InnerMatcher(std::move(InnerMatcher)) {} + + const DynTypedMatcher InnerMatcher; +}; + +/// Wrapper of a MatcherInterface *that allows copying. +/// +/// A Matcher can be used anywhere a Matcher is +/// required. This establishes an is-a relationship which is reverse +/// to the SAD hierarchy. In other words, Matcher is contravariant +/// with respect to T. The relationship is built via a type conversion +/// operator rather than a type hierarchy to be able to templatize the +/// type hierarchy instead of spelling it out. +template class Matcher { +public: + /// Takes ownership of the provided implementation pointer. + explicit Matcher(MatcherInterface *Implementation) + : Implementation(Implementation) {} + + /// Implicitly converts \c Other to a Matcher. + /// + /// Requires \c T to be derived from \c From. + template + Matcher(const Matcher &Other, + std::enable_if_t::value && + !std::is_same::value> * = nullptr) + : Implementation(restrictMatcher(Other.Implementation)) { + assert(Implementation.getSupportedKind().isSame( + SADNodeKind::getFromNodeKind())); + } + + /// Implicitly converts \c Matcher or \c Matcher + /// to \c Matcher (SValMatcher). + template + Matcher( + const Matcher &Other, + std::enable_if_t::value && + (std::is_same::value || + std::is_same::value)> * = + nullptr) + : Implementation(new SymbolOrRegionToSVal(Other)) {} + + /// Convert \c this into a \c Matcher by applying dyn_cast<> to the + /// argument. + /// \c To must be a base class of \c T. + template Matcher dynCastTo() const { + static_assert(std::is_base_of::value, "Invalid dynCast call."); + return Matcher(Implementation); + } + + /// Forwards the call to the underlying MatcherInterface pointer. + bool matches(const T &Node, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const { + return Implementation.matches(DynTypedNode::create(Node), Finder, Builder); + } + + /// Returns an ID that uniquely identifies the matcher. + DynTypedMatcher::MatcherIDType getID() const { + return Implementation.getID(); + } + + /// Extract the dynamic matcher. + /// + /// The returned matcher keeps the same restrictions as \c this and remembers + /// that it is meant to support nodes of type \c T. + operator DynTypedMatcher() const { return Implementation; } + + /// \brief Allows the conversion of a \c Matcher and + /// \c Matcher to a \c Matcher. + template + class SymbolOrRegionToSVal : public WrapperMatcherInterface { + public: + SymbolOrRegionToSVal(const Matcher &InnerMatcher) + : SymbolOrRegionToSVal::WrapperMatcherInterface(InnerMatcher) {} + + bool matches(const ento::SVal &Node, SADMatchFinder *Finder, + BoundNodesTreeBuilder *Builder) const override { + if (auto V = SValContent::get(Node)) + return InnerMatcher.matches(DynTypedNode::create(*V), Finder, Builder); + return false; + } + }; + +private: + // For Matcher <=> Matcher conversions. + template friend class Matcher; + + // For DynTypedMatcher::unconditionalConvertTo. + friend class DynTypedMatcher; + + static DynTypedMatcher restrictMatcher(const DynTypedMatcher &Other) { + return Other.dynCastTo(SADNodeKind::getFromNodeKind()); + } + + explicit Matcher(const DynTypedMatcher &Implementation) + : Implementation(restrictMatcher(Implementation)) { + assert(this->Implementation.getSupportedKind().isSame( + SADNodeKind::getFromNodeKind())); + } + + DynTypedMatcher Implementation; +}; // class Matcher + +/// A convenient helper for creating a Matcher without specifying +/// the template type argument. +template +inline Matcher makeMatcher(MatcherInterface *Implementation) { + return Matcher(Implementation); +} + +/// IsBaseType::value is true if T is a "base" type in the SAD +/// node class hierarchies. +template struct IsBaseType { + static const bool value = std::is_same::value || + std::is_same::value || + std::is_same::value; +}; +template const bool IsBaseType::value; + +/// Interface that allows matchers to traverse the SAD. +class SADMatchFinder { +public: + /// Defines how bindings are processed on recursive matches. + enum BindKind { + /// Stop at the first match and only bind the first match. + BK_First, + + /// Create results for all combinations of bindings that match. + BK_All + }; + + virtual ~SADMatchFinder() = default; + + template + bool matchesChildOf(const T &Node, const DynTypedMatcher &Matcher, + BoundNodesTreeBuilder *Builder, BindKind Bind) { + static_assert(std::is_base_of::value || + std::is_base_of::value || + std::is_base_of::value, + "unsupported type for recursive matching"); + return matchesChildOf(DynTypedNode::create(Node), Matcher, Builder, Bind); + } + + template + bool matchesDescendantOf(const T &Node, const DynTypedMatcher &Matcher, + BoundNodesTreeBuilder *Builder, BindKind Bind) { + static_assert(std::is_base_of::value || + std::is_base_of::value || + std::is_base_of::value, + "unsupported type for recursive matching"); + return matchesDescendantOf(DynTypedNode::create(Node), Matcher, Builder, + Bind); + } + +protected: + virtual bool matchesChildOf(const DynTypedNode &Node, + const DynTypedMatcher &Matcher, + BoundNodesTreeBuilder *Builder, + BindKind Bind) = 0; + + virtual bool matchesDescendantOf(const DynTypedNode &Node, + const DynTypedMatcher &Matcher, + BoundNodesTreeBuilder *Builder, + BindKind Bind) = 0; +}; + +/// A type-list implementation. +/// +/// A "linked list" of types, accessible by using the ::head and ::tail +/// typedefs. +template struct TypeList {}; // Empty sentinel type list. + +template struct TypeList { + /// The first type on the list. + using head = T1; + + /// A sublist with the tail. ie everything but the head. + /// + /// This type is used to do recursion. TypeList<>/EmptyTypeList indicates the + /// end of the list. + using tail = TypeList; +}; + +/// The empty type list. +using EmptyTypeList = TypeList<>; + +/// Helper meta-function to determine if some type \c T is present or +/// a parent type in the list. +template struct TypeListContainsSuperOf { + static const bool value = + std::is_base_of::value || + TypeListContainsSuperOf::value; +}; +template struct TypeListContainsSuperOf { + static const bool value = false; +}; + +/// A "type list" that contains all types. +/// +/// Useful for matchers like \c anything and \c unless. +using AllNodeBaseTypes = TypeList; + +/// Helper meta-function to extract the argument out of a function of +/// type void(Arg). +/// +/// See SAD_POLYMORPHIC_SUPPORTED_TYPES for details. +template struct ExtractFunctionArgMeta; + +template struct ExtractFunctionArgMeta { using type = T; }; + +/// Default type lists for ArgumentAdaptingMatcher matchers. +using AdaptativeDefaultFromTypes = AllNodeBaseTypes; +using AdaptativeDefaultToTypes = TypeList; + +template