[clang-diff] Use data collectors for node comparison

[arphaman]

Can you remove getNodeValue now or do you still need it?

[johannes]

In D37001#852442, @arphaman wrote:

Can you remove getNodeValue now or do you still need it?

It is only used in the client, I think it makes sense to move it there, or to remove it altogether.
I think I'd keep it in the client for now, to disambiguate things with different names in the tests.

[arphaman]

lib/Tooling/ASTDiff/ASTDiff.cpp

499

I didn't realize that you're including files from within lib. That's not ideal. You should add a pre-commit that moves the *.inc files over to include/AST (and marks them as textual in Clang's module.modulemap). Then you should include them using the clang/AST path.

[johannes]

lib/Tooling/ASTDiff/ASTDiff.cpp

499

I tried moving StmtDataCollectors.inc to and adding
+ textual header "AST/StmtDataCollectors.inc"
in the modulemap, then I get some CMake errors, not sure why.

It might make sense to tablegen it like the other .inc files.

[johannes]

use raw source code of owned tokens instead

include/clang/Tooling/ASTDiff/ASTDiff.h

struct Node {
   /// The range for implicit ThisExpression nodes is empty.
   ///
   /// If it is a CXXConstructExpr that is not a temporary, then we exclude
   /// the class name from the range by returning
   /// CXXConstructExpr::getParentOrBraceRange(). So the class name will belong
   /// to the parent.
   CharSourceRange getSourceRange() const;
 
+  /// Returns the sub-ranges of getSourceRange() that are exclusively owned by
+  /// this node, that is, none of its descendants includes them.
+  SmallVector<CharSourceRange, 4> getOwnedSourceRanges() const;
+
   /// Returns the offsets for the range returned by getSourceRange().
   std::pair<unsigned, unsigned> getSourceRangeOffsets() const;
+
+  /// Returns the starting locations of all tokens in getOwnedSourceRanges().
+  SmallVector<SourceLocation, 4> getOwnedTokens() const;
 };
 
+void forEachTokenInRange(CharSourceRange Range, SyntaxTree &Tree,
+                         std::function<void(Token &)> Body);
+
+inline bool isListSeparator(Token &Tok) { return Tok.is(tok::comma); }
+
 struct NodeRefIterator {
   SyntaxTree::Impl *Tree;
   const NodeId *IdPointer;
   NodeRefIterator(SyntaxTree::Impl *Tree, const NodeId *IdPointer)
       : Tree(Tree), IdPointer(IdPointer) {}
   NodeRef operator*() const;
   NodeRefIterator &operator++();
   NodeRefIterator &operator+(int Offset);
   bool operator!=(const NodeRefIterator &Other) const;
 };
 
 } // end namespace diff
 } // end namespace clang
 
 #endif

lib/Tooling/ASTDiff/ASTDiff.cpp

 //
 //===----------------------------------------------------------------------===//
 
 #include "clang/Tooling/ASTDiff/ASTDiff.h"
 
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/PriorityQueue.h"
+#include "llvm/Support/MD5.h"
 
 #include <limits>
 #include <memory>
 #include <unordered_set>
 
 using namespace llvm;
 using namespace clang;
 
struct NodeList {
   NodeRefIterator begin() const { return {&Tree, &*Ids.begin()}; }
   NodeRefIterator end() const { return {&Tree, &*Ids.end()}; }
   NodeRef operator[](size_t Index) { return *(begin() + Index); }
   size_t size() { return Ids.size(); }
   void sort() { std::sort(Ids.begin(), Ids.end()); }
 };
 } // end anonymous namespace
 
+using HashType = std::array<uint8_t, 16>;
+
 /// Represents the AST of a TranslationUnit.
 class SyntaxTree::Impl {
 public:
   Impl(SyntaxTree *Parent, ASTUnit &AST);
   /// Constructs a tree from an AST node.
   Impl(SyntaxTree *Parent, Decl *N, ASTUnit &AST);
   Impl(SyntaxTree *Parent, Stmt *N, ASTUnit &AST);
   template <class T>
if (auto *D = dyn_cast<DeclRefExpr>(S))
     return getRelativeName(D->getDecl(), getEnclosingDeclContext(AST, S));
   if (auto *String = dyn_cast<StringLiteral>(S))
     return String->getString();
   if (auto *B = dyn_cast<CXXBoolLiteralExpr>(S))
     return B->getValue() ? "true" : "false";
   return "";
 }
 
+static HashType hashNode(NodeRef N) {
+  llvm::MD5 Hash;
+  SourceManager &SM = N.getTree().getSourceManager();
+  const LangOptions &LangOpts = N.getTree().getLangOpts();
+  Token Tok;
+  for (auto TokenLocation : N.getOwnedTokens()) {
+    bool Failure = Lexer::getRawToken(TokenLocation, Tok, SM, LangOpts,
+                                      /*IgnoreWhiteSpace=*/true);
+    assert(!Failure);
+    auto Range = CharSourceRange::getCharRange(TokenLocation, Tok.getEndLoc());
+    // This is here to make CompoundStmt nodes compare equal, to make the tests
+    // pass. It should be changed to include changes to comments.
+    if (!Tok.isOneOf(tok::comment, tok::semi))
+      Hash.update(Lexer::getSourceText(Range, SM, LangOpts));
+  }
+  llvm::MD5::MD5Result HashResult;
+  Hash.final(HashResult);
+  return HashResult;
+}
+
+static bool areNodesDifferent(NodeRef N1, NodeRef N2) {
+  return hashNode(N1) != hashNode(N2);
+}
+
 /// Identifies a node in a subtree by its postorder offset, starting at 1.
 struct SNodeId {
   int Id = 0;
 
   explicit SNodeId(int Id) : Id(Id) {}
   explicit SNodeId() = default;
 
   operator int() const { return Id; }
   SNodeId &operator++() { return ++Id, *this; }
   SNodeId &operator--() { return --Id, *this; }
   SNodeId operator+(int Other) const { return SNodeId(Id + Other); }
 };
 
 class Subtree {
 private:
private:
   /// always be avoided.
   static constexpr double DeletionCost = 1;
   static constexpr double InsertionCost = 1;
 
   double getUpdateCost(SNodeId Id1, SNodeId Id2) {
     NodeRef N1 = S1.getNode(Id1), N2 = S2.getNode(Id2);
     if (!DiffImpl.isMatchingPossible(N1, N2))
       return std::numeric_limits<double>::max();
-    return S1.getNodeValue(Id1) != S2.getNodeValue(Id2);
+    return areNodesDifferent(S1.getNode(Id1), S2.getNode(Id2));
   }
 
   void computeTreeDist() {
     for (SNodeId Id1 : S1.KeyRoots)
       for (SNodeId Id2 : S2.KeyRoots)
         computeForestDist(Id1, Id2);
   }
 

 std::pair<unsigned, unsigned> Node::getSourceRangeOffsets() const {
   const SourceManager &SM = Tree.AST.getSourceManager();
   CharSourceRange Range = getSourceRange();
   unsigned Begin = SM.getFileOffset(Range.getBegin());
   unsigned End = SM.getFileOffset(Range.getEnd());
   return {Begin, End};
 }
 
+static bool onlyWhitespace(StringRef Str) {
+  return std::all_of(Str.begin(), Str.end(),
+                     [](char C) { return std::isspace(C); });
+}
+
+SmallVector<CharSourceRange, 4> Node::getOwnedSourceRanges() const {
+  SmallVector<CharSourceRange, 4> SourceRanges;
+  SourceManager &SM = getTree().getSourceManager();
+  const LangOptions &LangOpts = getTree().getLangOpts();
+  CharSourceRange Range = getSourceRange();
+  SourceLocation Offset = Range.getBegin();
+  BeforeThanCompare<SourceLocation> Less(SM);
+  auto AddSegment = [&](SourceLocation Until) {
+    if (Offset.isValid() && Until.isValid() && Less(Offset, Until)) {
+      CharSourceRange R = CharSourceRange::getCharRange({Offset, Until});
+      StringRef Text = Lexer::getSourceText(R, SM, LangOpts);
+      if (onlyWhitespace(Text))
+        return;
+      SourceRanges.emplace_back(CharSourceRange::getCharRange({Offset, Until}));
+    }
+  };
+  int ChildIndex = 0;
+  for (NodeRef Descendant : *this) {
+    CharSourceRange DescendantRange = Descendant.getSourceRange();
+    CharSourceRange LMDRange =
+        getTree().getNode(Descendant.LeftMostDescendant).getSourceRange();
+    CharSourceRange RMDRange =
+        getTree().getNode(Descendant.RightMostDescendant).getSourceRange();
+    auto MinValidBegin = [&Less](CharSourceRange &Range1,
+                                 CharSourceRange &Range2) {
+      SourceLocation Begin1 = Range1.getBegin(), Begin2 = Range2.getBegin();
+      if (Begin1.isInvalid())
+        return Begin2;
+      if (Begin2.isInvalid())
+        return Begin1;
+      return std::min(Begin1, Begin2, Less);
+    };
+    auto MaxValidEnd = [&Less](CharSourceRange &Range1,
+                               CharSourceRange &Range2) {
+      SourceLocation End1 = Range1.getEnd(), End2 = Range2.getEnd();
+      if (End1.isInvalid())
+        return End2;
+      if (End2.isInvalid())
+        return End1;
+      return std::max(End1, End2, Less);
+    };
+    auto Min = MinValidBegin(DescendantRange, LMDRange);
+    auto Max = MaxValidEnd(DescendantRange, RMDRange);
+    AddSegment(Min);
+    if (Max.isValid())
+      Offset = Max;
+    ++ChildIndex;
+  }
+  AddSegment(Range.getEnd());
+  return SourceRanges;
+}
+
+void forEachTokenInRange(CharSourceRange Range, SyntaxTree &Tree,
+                         std::function<void(Token &)> Body) {
+  SourceLocation Begin = Range.getBegin(), End = Range.getEnd();
+  SourceManager &SM = Tree.getSourceManager();
+  BeforeThanCompare<SourceLocation> Less(SM);
+  Token Tok;
+  while (Begin.isValid() && Less(Begin, End) &&
+         !Lexer::getRawToken(Begin, Tok, SM, Tree.getLangOpts(),
+                             /*IgnoreWhiteSpace=*/true) &&
+         Less(Tok.getLocation(), End)) {
+    Body(Tok);
+    Begin = Tok.getEndLoc();
+  }
+}
+
+SmallVector<SourceLocation, 4> Node::getOwnedTokens() const {
+  SmallVector<SourceLocation, 4> TokenLocations;
+  BeforeThanCompare<SourceLocation> Less(getTree().getSourceManager());
+  const auto &SourceRanges = getOwnedSourceRanges();
+  for (auto &Range : SourceRanges) {
+    forEachTokenInRange(Range, getTree(), [&TokenLocations](Token &Tok) {
+      if (!isListSeparator(Tok))
+        TokenLocations.push_back(Tok.getLocation());
+    });
+  }
+  return TokenLocations;
+}
+
 namespace {
 // Compares nodes by their depth.
 struct HeightLess {
   SyntaxTree::Impl &Tree;
   HeightLess(SyntaxTree::Impl &Tree) : Tree(Tree) {}
   bool operator()(NodeId Id1, NodeId Id2) const {
     return Tree.getNode(Id1).Height < Tree.getNode(Id2).Height;
   }
void open(NodeRef N) {
     for (NodeRef Child : N)
       push(Child.getId());
   }
 };
 } // end anonymous namespace
 
 bool ASTDiff::Impl::identical(NodeRef N1, NodeRef N2) const {
   if (N1.getNumChildren() != N2.getNumChildren() ||
-      !isMatchingPossible(N1, N2) || T1.getNodeValue(N1) != T2.getNodeValue(N2))
+      !isMatchingPossible(N1, N2) || areNodesDifferent(N1, N2))
     return false;
   for (size_t Id = 0, E = N1.getNumChildren(); Id < E; ++Id)
     if (!identical(N1.getChild(Id), N2.getChild(Id)))
       return false;
   return true;
 }
 
 bool ASTDiff::Impl::isMatchingPossible(NodeRef N1, NodeRef N2) const {
double ASTDiff::Impl::getJaccardSimilarity(NodeRef N1, NodeRef N2) const {
   if (Denominator == 0)
     return 0;
   return CommonDescendants / Denominator;
 }
 
 double ASTDiff::Impl::getNodeSimilarity(NodeRef N1, NodeRef N2) const {
   auto Ident1 = N1.getIdentifier(), Ident2 = N2.getIdentifier();
 
-  bool SameValue = T1.getNodeValue(N1) == T2.getNodeValue(N2);
+  bool SameValue = !areNodesDifferent(N1, N2);
   auto SameIdent = Ident1 && Ident2 && *Ident1 == *Ident2;
 
   double NodeSimilarity = 0;
   NodeSimilarity += SameValue;
   NodeSimilarity += SameIdent;
 
   assert(haveSameParents(N1, N2));
   return NodeSimilarity * Options.MinSimilarity;
if (!getSrc(N2))
       continue;
     NodeRef N1 = *getSrc(N2);
     Node &MutableN1 = T1.getMutableNode(N1);
     Node &MutableN2 = T2.getMutableNode(N2);
     if (!haveSameParents(N1, N2) ||
         findNewPosition(N1) != findNewPosition(N2)) {
       MutableN1.Change = MutableN2.Change = Move;
     }
-    if (T1.getNodeValue(N1) != T2.getNodeValue(N2)) {
+    if (areNodesDifferent(N1, N2)) {
       MutableN1.Change = MutableN2.Change =
           (N1.Change == Move ? UpdateMove : Update);
     }
   }
 }
 
 const Node *ASTDiff::Impl::getMapped(NodeRef N) const {
   if (&N.Tree == &T1)

test/Tooling/clang-diff-basic.cpp

 // CHECK: Update VarDecl: :p(int){{.*}} to :prod(double)
 // CHECK: Match BinaryOperator: *{{.*}} to BinaryOperator: *
 double prod = 1 * 2 * 10;
 // CHECK: Update DeclRefExpr
 int squared = prod * prod;
 
 class X {
   const char *foo(int i) {
+    // CHECK: Insert IfStmt(29) into CompoundStmt(28)
     if (i == 0)
       return "Bar";
-    // CHECK: Insert IfStmt{{.*}} into IfStmt
-    // CHECK: Insert BinaryOperator: =={{.*}} into IfStmt
+    // CHECK: Move IfStmt(35) into IfStmt
     else if (i == -1)
       return "foo";
     return 0;
   }
   X(){}
 };
 }
 

 #define M2 return 2 * 2
 #define F(a, b) return a + b;
 
 int f2() {
   // CHECK: Match Macro: M1{{.*}} to Macro: M1
   M1;
   // CHECK: Update Macro: M1{{.*}} to M2
   M2;
-  // CHECK: Update Macro: F(1, 1){{.*}} to F(1, /*b=*/1)
+  // CHECK: Match Macro: F(1, 1)(74)
   F(1, /*b=*/1);
 }
 
 // CHECK: Delete AccessSpecDecl: public
 // CHECK: Delete CXXMethodDecl

test/Tooling/clang-diff-html.test

 RUN: clang-diff -html %S/Inputs/clang-diff-basic-src.cpp %S/clang-diff-basic.cpp -- | FileCheck %s
 
 CHECK: <pre><div id='L' class='code'><span id='L0' tid='R0' title='TranslationUnitDecl
-CHECK-NEXT: 0 -> 0'>
+CHECK-NEXT: 0 -> 0' class='u'>
 
 match, update
 CHECK: <span id='L[[L:[0-9]+]]' tid='R[[R:[0-9]+]]' title='NamespaceDecl
 CHECK-NEXT: [[L]] -> [[R]]
 CHECK-NEXT: src;' class='u'>namespace src {
 
 match, move
 CHECK: <span id='L[[L:[0-9]+]]' tid='R[[R:[0-9]+]]' title='FunctionDecl

 CHECK: 2' class='u m'>2</span>
 
 insertion
 CHECK: <span id='R[[R:[0-9]+]]' tid='L-1' title='StringLiteral
 CHECK-NEXT: -1 -> [[R]]
 CHECK-NEXT: Bar' class='i'>&quot;Bar&quot;</span>
 
 comments
-CHECK: // CHECK: Insert IfStmt{{.*}} into IfStmt
 CHECK: // CHECK: Delete AccessSpecDecl: public

test/Tooling/clang-diff-topdown.cpp

 int x;
 
 namespace src {
   int x;
   int x1 = x + 1;
   int x2 = ::x + 1;
 }
 
-class A { int x = 1 + 1; void f() { int x1 = x; } };
-
 #else
 
 
 void f1() {
 
   {{;}}
 
   {;}

 namespace dst {
   int x;
   // CHECK: Match DeclRefExpr: :x(17) to DeclRefExpr: :x(22)
   int x1 = x + 1;
   // CHECK: Match DeclRefExpr: x(21) to DeclRefExpr: x(26)
   int x2 = ::x + 1;
 }
 
-class B {
-  // Only the class name changed; it is not included in the field value,
-  // therefore there is no update.
-  // CHECK: Match FieldDecl: :x(int)(24) to FieldDecl: :x(int)(29)
-  // CHECK-NOT: Update FieldDecl: :x(int)(24)
-  int x = 1+1;
-  void f() {
-    // CHECK: Match MemberExpr: :x(32) to MemberExpr: :x(37)
-    // CHECK-NOT: Update MemberExpr: :x(32)
-    int x1 = B::x;
-  }
-
-};
-
 #endif