[analyzer] Added custom hashing to the CloneDetector.

[teemperor]

Summary

The CloneDetector consumes in it's current state to much memory to analyze big code bases such as SQLite.

This patch reintroduces the custom hashing functionality which replaces CloneSignature's large data vectors with fixed size hash codes. This includes an additional check for each clone that prevents that the CloneDetector produces false-positives because of collisions in the hash function.

[v.g.vassilev]

Could you add some tests?

[NoQ]

Hmm. Since you're working with FoldingSetNodeIDs, maybe you could avoid numeric hashes completely in your code, and use FoldingSetNodeIDs themselves as your keys? Just organize the whole clone list as a map from FoldingSetNodeIDs to lists of particular code samples. There would be no collisions at all from the beginning (even if internally the map would hash the FoldingSetNodeIDs to a number and there will be collisions in this hashing, but you wouldn't need to know about them - and there's no performance loss at the same time).

[v.g.vassilev]

@teemperor: could you summarize what we discussed at the phone meeting today wrt to this patch.

[teemperor]

This patch is no longer needed because the CloneDetector from patch https://reviews.llvm.org/D20795 no longer uses custom hashing.

[teemperor]

• Rebased the patch to the newest code base.

This patch is live again as it turned out that the CloneDetector can't handle large code bases without it. The simpler approach that we implemented instead consumed too much memory (e.g. at least 15 GB for analyzing SQLite) because the large data vectors and the quadratic space complexity of the sub-sequence search didn't play together very well.

[teemperor]

• Fixed some formatting problems.
• Updated Title/Summary

[NoQ]

Considering the refactoring planned in D23418, i've no more comments on the part of the code that isn't rewritten in the subsequent review. I like how the new hashing system is put to work here.

lib/Analysis/CloneDetection.cpp

548

Hmm. FoldingSetNodeIDWrapper? Because in fact we're wrapping neither a set, nor a node, but only an ID.

559

// end anonymous namespace?

[teemperor]

• Renamed FoldingSetWrapper to FoldingSetNodeIDWrapper
• Added missing // end anonymous namespace

[teemperor]

• As the hash_stream patch will take a while to land upstream, we will change this to use FoldingSetNodeID and change it to hash_stream once that landed.

[v.g.vassilev]

LGTM.

[teemperor]

• Moved from hash_stream to LLVM's MD5 implementation.

[NoQ]

lib/Analysis/CloneDetection.cpp

313

Hmm, this still uses hash_stream.

[teemperor]

• Replaced hash_stream with MD5 in the sub-sequence code.

lib/Analysis/CloneDetection.cpp

void removeChildren(Stmt const *Parent, ASTContext &Context) {
     for (Stmt const *Child : Parent->children()) {
       if (!Child)
         continue;
       StmtSequence ChildSequence(Child, Context);
       remove(ChildSequence);
     }
   }
 
   /// \brief Retrieves the CloneSignature that describes the given Sequence.
   CloneDetector::CloneSignature get(StmtSequence const &S) const {
     // This cache promises good lookup time for recently added CloneSignatures
     // even if not properly cleaned. As the most recently added CloneSignature
     // is at the end, we start searching from back of the cache to the front to
     // keep that promise.
     for (auto I = Cache.rbegin(); I != Cache.rend(); ++I) {
       if (I->Sequence == S) {
         return *I;
bool GroupContains(CloneDetector::CloneGroup &Group,
   for (StmtSequence &Stmt : Group) {
     if (!StmtContainsAnyInGroup(Stmt, OtherGroup))
       return false;
   }
   return true;
 }
 } // end anonymous namespace
 
+namespace {
+/// \brief Collects the data from all statements and their children.
+///
+/// The data is collected by StmtDataCollector, which means that the collected
+/// data is equal for StmtSequences that are considered equal by the
+/// StmtDataCollector class.
+class SequenceDataCollector
+    : public RecursiveASTVisitor<SequenceDataCollector> {
+
+  ASTContext &Context;
+  llvm::FoldingSetNodeID &D;
+
+public:
+  SequenceDataCollector(const StmtSequence& Sequence, ASTContext &Context,
+                        llvm::FoldingSetNodeID &D)
+    : Context(Context), D(D) {
+    // We want that sub-sequences inside CompoundStmts have the same data
+    // as a normal CompoundStmt containing the same children. For this we have
+    // to manually add the data of the surrounding CompoundStmt to the result.
+    if (Sequence.holdsSequence())
+      D.AddInteger(CompoundStmt::StmtClass::CompoundStmtClass);
+
+    for (Stmt const * S : Sequence) {
+      // We cast away the const because RecursiveASTVisitor doesn't support
+      // traversing non-const statements. As we don't modify the statement,
+      // we shouldn't run in any trouble with this.
+      TraverseStmt(const_cast<Stmt *>(S));
+    }
+  }
+
+  bool VisitStmt(const Stmt *S) {
+    // Append all the data in S to our data set.
+    StmtDataCollector(S, Context, D);
+    return true;
+  }
+};
+}
+
+/// \brief Returns true if both sequences are clones of each other.
+static bool areSequencesEqual(const StmtSequence &LHS,
+                              const StmtSequence &RHS) {
+  // We collect the data from all statements in the sequence as we did before
+  // when generating a hash value for each sequence. But this time we don't
+  // hash the collected data and compare the whole data set instead. This
+  // prevents any false-positives due to hash code collisions.
+  llvm::FoldingSetNodeID DataLHS, DataRHS;
+
+  SequenceDataCollector(LHS, LHS.getASTContext(), DataLHS);
+  SequenceDataCollector(RHS, RHS.getASTContext(), DataRHS);
+
+  return DataLHS == DataRHS;
+}
+
+/// \brief Finds all actual CloneGroups in a given CloneGroup.
+/// \param Result Output parameter to which found CloneGroups are added.
+/// \param HashGroup A CloneGroup that should be searched. It is recommended to
+///                  keep this group as small as possible.
+///
+/// This function is intended to be a false-positive filter behind a fast
+/// heuristic for finding CloneGroups.
+static void findCloneGroups(std::vector<CloneDetector::CloneGroup> &Result,
+                              const CloneDetector::CloneGroup &HashGroup) {
+  // Contains all indexes in HashGroup that were already added to a CloneGroup.
+  std::vector<unsigned> Indexes;
+  Indexes.reserve(HashGroup.size());
+
+  for (unsigned i = 0; i < HashGroup.size(); ++i) {
+    // Skip indexes that are already part of a CloneGroup.
+    if (std::find(Indexes.begin(), Indexes.end(), i) != Indexes.end())
+      continue;
+
+    // Pick the first unhandled StmtSequence and consider it as the beginning
+    // of a new CloneGroup for now.
+    // We don't add i to Indexes because we never iterate back.
+    StmtSequence PrototypeStmt = HashGroup[i];
+    CloneDetector::CloneGroup PotentialGroup = {PrototypeStmt};
+
+    // Check all following StmtSequences for clones.
+    for (unsigned j = i + 1; j < HashGroup.size(); ++j) {
+      // Skip indexes that are already part of a CloneGroup.
+      if (std::find(Indexes.begin(), Indexes.end(), j)
+          != Indexes.end())
+          continue;
+
+      // If a following StmtSequence belongs to our CloneGroup, we add it to it.
+      const StmtSequence &Candidate = HashGroup[j];
+      if (!areSequencesEqual(Candidate, PrototypeStmt))
+        continue;
+      PotentialGroup.push_back(Candidate);
+      // Make sure we never visit this StmtSequence again.
+      Indexes.push_back(j);
+    }
+
+    // CloneGroups with only one member don't make any sense, so we don't at
+    // them to the result.
+    if (PotentialGroup.size() == 1)
+      continue;
+    // Otherwise, add it to the result and continue searching for more groups.
+    Result.push_back(PotentialGroup);
+  }
+}
+
 void CloneDetector::findClones(std::vector<CloneGroup> &Result,
                                unsigned MinGroupComplexity) {
   // For creating hash groups, we need to find CloneSignatures with the same
   // hash value, so we first sort all CloneSignatures by their hash value. Then
   // we search for sequences of CloneSignatures with the same hash value.
   std::sort(Signatures.begin(), Signatures.end(),
             [](const CloneSignature &A, const CloneSignature &B) {
               return A.Hash < B.Hash;
for (unsigned i = 0; i < Signatures.size() - 1; ++i) {
 
     // There is a chance that we haven't found more than two fitting
     // CloneSignature because not enough CloneSignatures passed the complexity
     // requirement. As a CloneGroup with less than two members makes no sense,
     // we ignore this CloneGroup and won't add it to the result.
     if (Group.size() <= 1)
       continue;
 
-    Result.push_back(Group);
+    findCloneGroups(Result, Group);
   }
 
   std::vector<unsigned> IndexesToRemove;
 
   // Compare every group in the result with the rest. If one groups contains
   // another group, we only need to return the bigger group.
   // Note: This doesn't scale well, so if possible avoid calling any heavy
   // function from this loop to reduce the negative performance impact.