Integrate CHash into CLang

[stettberger]

Summary

The CHashVisitor can be used to determine a unique hash for a translation unit. The hash is stable across compiler invocations and if two translation units have the same hash, the resulting object file is semantically equal (code, data, etc. are equal; debug information may be different).

[Eugene.Zelenko]

Please run Clang-format and Clang-tidy modernize over newly added code.

include/clang/AST/CHashVisitor.h

2

Please loon onto other headers for inclusion guards style.

10

No empty lines between header groups.

15

Unnecessary empty line.

19

Please add empty line below.

154

} // namespace CHashConstants

Please add empty line above.

160

Please use using instead of typedef same in other places.

161

Please add empty line above.

447

Unnecessary lines.

451

} // namespace clang

452

#endif // <inclusion guard>

[rsmith]

We already have mechanisms to hash the AST. I'm strongly opposed to adding another one (and requiring AST modifications to update yet more such mechanisms).

Please look at the work that Richard Trieu has been doing recently to create stable-across-TUs hashes of statements and declarations, start a conversation on cfe-dev about integrating your approach and the existing Profile approach, and try to reach consensus on a way forward that doesn't leave us with multiple different hashing mechanisms. Replacing the Profile mechanism with a tablegen-driven one such as the one in this patch (and then generating the various hashing functions with their distinct requirements from that shared description) does seem like it could be a reasonable approach to me, but it needs to be a replacement rather than keeping both mechanisms around.

[stettberger]

@Eugene.Zelenko Thank you for pointing me out on these issues. I ran clang-tidy and clang-format on CHashVisitor.h

@rsmith You're right, there is already more than one implemenation of {partial,unstable} AST hashes within LLVM, as we already discussed on cfe-dev in August[1]. Therefore, I rewrote our original CHash implementation to extend the already existing StmtDataCollectors approach. However, you are right, efforts should be coordinated to get a AST hashing implementation that can be adapted to various use-case scenarios.

[1] http://lists.llvm.org/pipermail/cfe-dev/2017-August/054911.html

[johannes]

I think it would be quite nice if we manage to consolidate the implementation of hashing mechanisms.

Modifications to StmtDataCollectors.td will alter the behaviour of clone detection. Currently, this file assumes that we want to find type 2 clones. So we should maintain that, and add things only where needed.
I submitted this patch so we can have different categories of data collection
https://reviews.llvm.org/D40781

[johannes]

So you can define a category for cHash and add let cHash = [{ .. }] or let cHash = TypeIIClone; if you just want to reuse it.
With this patch you can also use !codeconcat to append some code: https://reviews.llvm.org/D40782

[stettberger]

For my changes to StmtDataCollectors: I tried to leave the already existing entries in StmtDataCollector.td untouched and the test-cases still work OK. If there is something somebody could break by changing these files it would be good to have a test case for it.

However, some of the collectors are not node local, which seems a little bit inconsequent to me. For example, DeclStmt includes information about the its Decl Children. In my opinion every entry in the *DataCollector.td should include only information that can be directly retrieved from this particular AST node. Cross-referencing between nodes should be done on the user side of the collectors (as it is done in CHashVisitor.h, which follows pointers in a cross-tree manner). With this separation of concerns it was quite easy for me to base CHash of the TableGen'ed headers. Furthermore, a purely syntactical hash (only the children, no cross-tree dependencies) could be derived easily.

@johannes For the different types of information that should be included for one AST node (e.g., Type II clones): We could use a hierachy of "What should be considered here". But we should clearly define what is the definition of equivalency for that level. For example, if you wake me up at night I could not define you the difference between a type I and a type II clone.

[johannes]

In D40731#943564, @stettberger wrote:

For my changes to StmtDataCollectors: I tried to leave the already existing entries in StmtDataCollector.td untouched and the test-cases still work OK. If there is something somebody could break by changing these files it would be good to have a test case for it.

Yeah, the tests are not comprehensive unfortunately

However, some of the collectors are not node local, which seems a little bit inconsequent to me. For example, DeclStmt includes information about the its Decl Children. In my opinion every entry in the *DataCollector.td should include only information that can be directly retrieved from this particular AST node. Cross-referencing between nodes should be done on the user side of the collectors (as it is done in CHashVisitor.h, which follows pointers in a cross-tree manner). With this separation of concerns it was quite easy for me to base CHash of the TableGen'ed headers. Furthermore, a purely syntactical hash (only the children, no cross-tree dependencies) could be derived easily.

Good point, I think we can move the code for DeclStmt to CloneDetection.cpp

@johannes For the different types of information that should be included for one AST node (e.g., Type II clones): We could use a hierachy of "What should be considered here". But we should clearly define what is the definition of equivalency for that level. For example, if you wake me up at night I could not define you the difference between a type I and a type II clone.

Yeah, it's difficult to clearly define that though. The thing I noticed is that the function name is included for PredefinedExpr, but Type II clones do not care about values, but only structure. I think most of your additions should be fine , @teemperor could confirm them.

[stettberger]

I removed the magic constants and added the number of children for various AST nodes. This should avoid hash collisions.

[stettberger]

@rtrieu: Fixed the checking of Decl::hasAttrs() before using Decl::attrs()

[stettberger]

Rebased to HEAD, Run (external) clang-hash testsuite and ASTTest

[stettberger]

[CHash] Stable TU-level AST Hashing for local and global hashes

This patch does integrate the AST hashing parts of the CHash project[1][2] into
CLang. The extension provided by this patch accomplishes 2 things:

• local hashes: It extends StmtDataCollector infrastructure by hash rules for declarations, types, and attributes. These rules are expressed in terms of TableGen files and capture what parts of a AST node are important to its semantic. Thereby, the rules only include information that is local to the respecting node (no pointers to other AST nodes should be followed).
  
  Since these DataCollectors do not impose rules how the AST nodes relate to each other, they provide a mechanism for "local" hashes.

• global hashes: The CHashVisitor combines the local hashes via the RecursiveAST Visitor into a global semantic hash that includes (for a given AST node) all local hashes of all AST nodes that can influence the compilation of this AST node.
  
  With these global hashes, we can deduce (early) in the compilation process wether the result of this compiler run will produce the same object file. This mechanism is *NOT* part of this commit.

[1] https://www.sra.uni-hannover.de/Research/cHash/
[2] "cHash: Detection of Redunandt Recompilations via AST hashing", USENIX 2017

[rtrieu]

include/clang/AST/CHashVisitor.h

73–80

Should these also be storing the hashes of the elements in addition to storing the size?

212

I thought the idea was to have all the code in the *Collectors.td but here you have a bunch of Visit* functions for AST nodes. This seems counter to your point of having them generated.

213–214

I don't see this example in the test.

227

Can't you query the hash for the Decl instead of doing work here?

254

Is this possible recursion included in your test?

256

Shouldn't this be handled in the VisitFieldDecl function?

include/clang/AST/DeclDataCollectors.td

6–8

Why is this randomness needed?

10

What do you mean by "CrossRef"?

61–62

Does that mean you consider:

enum E { E1, E2, E3 };

to be equivalent to:

enum E { E1 = 0, E2 = 1, E3 = 2 };

?

[v.g.vassilev]

I am not sure if this is the right time but maybe testing and comparing the behavior of this patch against something such as the ODRHash will help you, me (and probably others) to understand the current patch better.

In D41416, I started working on lazy deserialization of template specializations. When you produce a PCM or PCH and a template instantiation is required it'd currently deserialize eagerly all possible template specializations (and standard libraries have a lot of them). I am computing the hashes of the template arguments and comparing against the usual Profile-ed hashes. In the assert, essentially I am comparing the behavior of the ODRHash and the Stmt::Profile logic for some cases.

Perhaps you can plugin your algorithm to it, create a pch and start comparing your logic with the when it comes to template arguments hashing and alike.

Of course this is not something that will give you perfect coverage and so on but it can stress test the implementation and compare it to the 2 major existing ones in clang.

include/clang/AST/CHashVisitor.h

11

I suspect this is a copy-paste from the APValue class. Could you update the documentation what the file contains?

292

Clang uses /// for doxygen style documentation.

[stettberger]

Addressed comments, for more details, please see the mail on cfe-devel

[stettberger]

include/clang/AST/CHashVisitor.h

73–80

Ok. So this is called from

• FunctionProtoTypes { addData(S->exceptions()); }
• DecompositionDecl { addData(S->bindings()); }
• ObjCObjectType { addData(S->getTypeArgsAsWritten()); }

All of these occurrences are vistied by the RecursiveASTVisitor. However, we have no Idea how many children are visited by these for loops. Therefore, we additionally call addData(ArrayRef<...> x) to indicate give the actual user of StmtCollector* the possibility to add these lengths to the hash. This is also the reason, why we add only the std::distance to the length. I will add a comment to this.

212

See Mail.

213–214

It is now reflected in the tests.

227

How would I do it. As the example shows, there is no hash for a, when we try to calculate the hash for a. However, I included a unittest to cover this.

254

It now is.

256

I must avoid to call addData(D->getType()) in VisitValueDecl for FieldDeclarations. So there would also be a conditional.

include/clang/AST/DeclDataCollectors.td

6–8

It is there for my personal feeling of less hash collisions. In former versions of this patch there was a large random constant for every type of AST node to decrease the likelyness of collisions when we left out some information. Small numbers (like enum values) often occur in source code. A 32 Bit Pseudo-Random value is unlikely to be seen in real source code. However, if you dislike its, I can remove the llvm::hash_value here.

10

CrossRef indicates that the following fields are not local to the node. However, we give them to the user of the DataCollector to give it a chance to include the number of children into its hash. This directly relates to the addData(ArrayRef<...>) question above.

include/clang/AST/AttrDataCollectors.td

+//--- Attributes ---------------------------------------------------------//
+class Attr {
+  code Code = [{
+    std::string AttrString;      
+    llvm::raw_string_ostream OS(AttrString);
+    S->printPretty(OS, Context.getLangOpts());
+    OS.flush();
+    addData(AttrString);
+  }];
+}

include/clang/AST/CHashVisitor.h

+//===--- CHashVisitor.h - Stable AST Hashing -----*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the APValue class.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CLANG_AST_CHASHVISITOR_H
+#define LLVM_CLANG_AST_CHASHVISITOR_H
+
+#include "clang/AST/AST.h"
+#include "clang/AST/ASTConsumer.h"
+#include "clang/AST/DataCollection.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "llvm/Support/MD5.h"
+#include <map>
+#include <string>
+
+namespace clang {
+
+
+template <typename H = llvm::MD5, typename HR = llvm::MD5::MD5Result>
+class CHashVisitor : public clang::RecursiveASTVisitor<CHashVisitor<H, HR>> {
+
+  using Inherited = clang::RecursiveASTVisitor<CHashVisitor<H, HR>>;
+
+public:
+  using Hash = H;
+  using HashResult = HR;
+
+  /// Configure the RecursiveASTVisitor
+  bool shouldWalkTypesOfTypeLocs() const { return false; }
+
+protected:
+  ASTContext &Context;
+
+  // For the DataCollector, we implement a few addData() functions
+  void addData(uint64_t data) { topHash().update(data); }
+  void addData(const StringRef &str) { topHash().update(str); }
+  // On our way down, we meet a lot of qualified types.
+  void addData(const QualType &T) {
+    // 1. Hash referenced type
+    const Type *const ActualType = T.getTypePtr();
+    assert(ActualType != nullptr);
+
+    // FIXME: Structural hash
+    // 1.1 Was it already hashed?
+    const HashResult *const SavedDigest = getHash(ActualType);
+    if (SavedDigest) {
+      // 1.1.1 Use cached value
+      topHash().update(SavedDigest->Bytes);
+    } else {
+      // 1.1.2 Calculate hash for type
+      const Hash *const CurrentHash = pushHash();
+      Inherited::TraverseType(T); // Uses getTypePtr() internally
+      const HashResult TypeDigest = popHash(CurrentHash);
+      topHash().update(TypeDigest.Bytes);
+
+      // Store hash for underlying type
+      storeHash(ActualType, TypeDigest);
+    }
+
+    // Add the qulaifiers at this specific usage of the type
+    addData(T.getCVRQualifiers());
+  }
+  template<typename T>
+  void addData(const llvm::iterator_range<T> &x) {
+    addData(std::distance(x.begin(), x.end()));
+  }
+  template<typename T>
+  void addData(const llvm::ArrayRef<T> &x) {
+    addData(x.size());
+  }
+
+public:
+#define DEF_ADD_DATA_STORED(CLASS, CODE)                                       \
+  template <class = void> bool Visit##CLASS(const CLASS *S) {                  \
+    CODE;                                                                      \
+    return true;                                                               \
+  }
+#define DEF_ADD_DATA(CLASS, CODE) DEF_ADD_DATA_STORED(CLASS, CODE)
+#include "clang/AST/StmtDataCollectors.inc"
+#define DEF_ADD_DATA(CLASS, CODE) DEF_ADD_DATA_STORED(CLASS, CODE)
+#include "clang/AST/AttrDataCollectors.inc"
+#define DEF_ADD_DATA(CLASS, CODE) DEF_ADD_DATA_STORED(CLASS, CODE)
+#include "clang/AST/DeclDataCollectors.inc"
+#define DEF_ADD_DATA(CLASS, CODE) DEF_ADD_DATA_STORED(CLASS, CODE)
+#include "clang/AST/TypeDataCollectors.inc"
+
+  CHashVisitor(ASTContext &Context) : Context(Context) {}
+
+  /* For some special nodes, override the traverse function, since we
+     need both pre- and post order traversal */
+  bool TraverseTranslationUnitDecl(TranslationUnitDecl *TU) {
+    if (!TU)
+      return true;
+    // First, we push a new hash onto the hashing stack. This hash
+    // will capture everythin within the TU*/
+    Hash *CurrentHash = pushHash();
+
+    Inherited::WalkUpFromTranslationUnitDecl(TU);
+
+    // Do recursion on our own, since we want to exclude some children
+    const auto DC = cast<DeclContext>(TU);
+    for (auto *Child : DC->noload_decls()) {
+      if (isa<TypedefDecl>(Child) || isa<RecordDecl>(Child) ||
+          isa<EnumDecl>(Child))
+        continue;
+
+      // Extern variable definitions at the top-level
+      if (const auto VD = dyn_cast<VarDecl>(Child)) {
+        if (VD->hasExternalStorage()) {
+          continue;
+        }
+      }
+
+      if (const auto FD = dyn_cast<FunctionDecl>(Child)) {
+        // We try to avoid hashing of declarations that have no definition
+        if (!FD->isThisDeclarationADefinition()) {
+          bool doHashing = false;
+          // HOWEVER! If this declaration is an alias Declaration, we
+          // hash it no matter what
+          if (FD->hasAttrs()) {
+            for (const Attr *const A : FD->getAttrs()) {
+              if (A->getKind() == attr::Kind::Alias) {
+                doHashing = true;
+                break;
+              }
+            }
+          }
+          if (!doHashing)
+            continue;
+        }
+      }
+
+      TraverseDecl(Child);
+    }
+
+    storeHash(TU, popHash(CurrentHash));
+
+    return true;
+  }
+
+  /* For some special nodes, override the traverse function, since
+     we need both pre- and post order traversal. Storing of type
+     hashes is done in addData() */
+  bool TraverseDecl(Decl *D) {
+    if (!D)
+      return true;
+    /* For some declarations, we store the calculated hash value. */
+    bool CacheHash = false;
+    if (isa<FunctionDecl>(D) && cast<FunctionDecl>(D)->isDefined())
+      CacheHash = true;
+    if (isa<VarDecl>(D) && cast<VarDecl>(D)->hasGlobalStorage())
+      CacheHash = true;
+    if (isa<RecordDecl>(D) && dyn_cast<RecordDecl>(D)->isCompleteDefinition())
+      CacheHash = true;
+
+    if (!CacheHash) {
+      return Inherited::TraverseDecl(D);
+    }
+
+    const HashResult *const SavedDigest = getHash(D);
+    if (SavedDigest) {
+      topHash().update(SavedDigest->Bytes);
+      return true;
+    }
+    Hash *CurrentHash = pushHash();
+    bool Ret = Inherited::TraverseDecl(D);
+    HashResult CurrentHashResult = popHash(CurrentHash);
+    storeHash(D, CurrentHashResult);
+    if (!isa<TranslationUnitDecl>(D)) {
+      topHash().update(CurrentHashResult.Bytes);
+    }
+
+    return Ret;
+  }
+
+  /*****************************************************************
+   * When doing a semantic hash, we have to use cross-tree links to
+   * other parts of the AST, here we establish these links
+   */
+
+#define DEF_TYPE_GOTO_DECL(CLASS, EXPR)                                        \
+  bool Visit##CLASS(CLASS *T) {                                                \
+    Inherited::Visit##CLASS(T);                                                \
+    return TraverseDecl(EXPR);                                                 \
+  }
+
+  DEF_TYPE_GOTO_DECL(TypedefType, T->getDecl());
+  DEF_TYPE_GOTO_DECL(RecordType, T->getDecl());
+  // The EnumType forwards to the declaration. The declaration does
+  // not hand back to the type.
+  DEF_TYPE_GOTO_DECL(EnumType, T->getDecl());
+  bool TraverseEnumDecl(EnumDecl *E) {
+    /* In the original RecursiveASTVisitor
+       > if (D->getTypeForDecl()) {
+       >    TRY_TO(TraverseType(QualType(D->getTypeForDecl(), 0)));
+       > }
+       => NO, NO, NO, to avoid endless recursion
+    */
+    return Inherited::WalkUpFromEnumDecl(E);
+  }
+
+  bool VisitTypeDecl(TypeDecl *D) {
+    // If we would hash the resulting type for a typedef, we
+    // would get into an endless recursion.
+    if (!isa<TypedefNameDecl>(D) && !isa<RecordDecl>(D) && !isa<EnumDecl>(D)) {
+      addData(QualType(D->getTypeForDecl(), 0));
+    }
+    return true;
+  }
+
+  bool VisitDeclRefExpr(DeclRefExpr *E) {
+    ValueDecl *ValDecl = E->getDecl();
+    // Function Declarations are handled in VisitCallExpr
+    if (!ValDecl) {
+      return true;
+    }
+    if (isa<VarDecl>(ValDecl)) {
+      /* We emulate TraverseDecl here for VarDecl, because we
+       * are not allowed to call TraverseDecl here, since the
+       * initial expression of a DeclRefExpr might reference a
+       * sourronding Declaration itself. For example:
+       *
+       * struct foo {int N;}
+       * struct foo a = { sizeof(a) };
+       */
+      VarDecl *VD = static_cast<VarDecl *>(ValDecl);
+      VisitNamedDecl(VD);
+      Inherited::TraverseType(VD->getType());
+      VisitVarDecl(VD);
+    } else if (isa<FunctionDecl>(ValDecl)) {
+      /* Hash Functions without their body */
+      FunctionDecl *FD = static_cast<FunctionDecl *>(ValDecl);
+      Stmt *Body = FD->getBody();
+      FD->setBody(nullptr);
+      TraverseDecl(FD);
+      FD->setBody(Body);
+    } else {
+      TraverseDecl(ValDecl);
+    }
+    return true;
+  }
+
+  bool VisitValueDecl(ValueDecl *D) {
+    /* Field Declarations can induce recursions */
+    if (isa<FieldDecl>(D)) {
+      addData(std::string(D->getType().getAsString()));
+    } else {
+      addData(D->getType());
+    }
+    addData(D->isWeak());
+    return true;
+  }
+
+  /*****************************************************************
+   * For performance reasons, we cache some of the hashes for types
+   * and declarations.
+   */
+
+public:
+  // We store hashes for declarations and types in separate maps.
+  std::map<const Type *, HashResult> TypeSilo;
+  std::map<const Decl *, HashResult> DeclSilo;
+
+  void storeHash(const Type *Obj, HashResult Dig) { TypeSilo[Obj] = Dig; }
+
+  void storeHash(const Decl *Obj, HashResult Dig) { DeclSilo[Obj] = Dig; }
+
+  const HashResult *getHash(const Type *Obj) {
+    if (TypeSilo.find(Obj) != TypeSilo.end()) {
+      return &TypeSilo[Obj];
+    }
+    return nullptr;
+  }
+
+  const HashResult *getHash(const Decl *Obj) {
+    if (DeclSilo.find(Obj) != DeclSilo.end()) {
+      return &DeclSilo[Obj];
+    }
+    return nullptr;
+  }
+
+  /*****************************************************************
+   * In order to produce hashes for subtrees on the way, a hash
+   * stack is used. When a new subhash is meant to be calculated, we
+   * push a new stack on the hash. All hashing functions use always
+   * the top of the hashing stack.
+   */
+protected:
+  llvm::SmallVector<Hash, 32> HashStack;
+
+public:
+  Hash *pushHash() {
+    HashStack.push_back(Hash());
+    return &HashStack.back();
+  }
+
+  HashResult popHash(const Hash *ShouldBe = nullptr) {
+    assert(!ShouldBe || ShouldBe == &HashStack.back());
+
+    // Finalize the Hash and return the digest.
+    HashResult CurrentDigest;
+    topHash().final(CurrentDigest);
+    HashStack.pop_back();
+    return CurrentDigest;
+  }
+
+  Hash &topHash() { return HashStack.back(); }
+};
+
+} // namespace clang
+#endif // LLVM_CLANG_AST_CHASHVISITOR_H

include/clang/AST/CMakeLists.txt

 
 clang_tablegen(CommentCommandList.inc -gen-clang-comment-command-list
   SOURCE CommentCommands.td
   TARGET ClangCommentCommandList)
 
 clang_tablegen(StmtDataCollectors.inc -gen-clang-data-collectors
   SOURCE StmtDataCollectors.td
   TARGET StmtDataCollectors)
+
+clang_tablegen(DeclDataCollectors.inc -gen-clang-data-collectors
+  SOURCE DeclDataCollectors.td
+  TARGET DeclDataCollectors)
+
+clang_tablegen(AttrDataCollectors.inc -gen-clang-data-collectors
+  SOURCE AttrDataCollectors.td
+  TARGET AttrDataCollectors)
+
+clang_tablegen(TypeDataCollectors.inc -gen-clang-data-collectors
+  SOURCE TypeDataCollectors.td
+  TARGET TypeDataCollectors)

include/clang/AST/DataCollection.h

 typename std::enable_if<
     std::is_integral<Type>::value || std::is_enum<Type>::value ||
     std::is_convertible<Type, size_t>::value // for llvm::hash_code
     >::type
 addDataToConsumer(T &DataConsumer, Type Data) {
   DataConsumer.update(StringRef(reinterpret_cast<char *>(&Data), sizeof(Data)));
 }
 
+template <class T, class Type>
+void addDataToConsumer(T &DataConsumer, const llvm::iterator_range<Type> &R) {
+  addDataToConsumer(DataConsumer, std::distance(R.begin(), R.end()));
+}
+
+template <class T, class Type>
+void addDataToConsumer(T &DataConsumer, const llvm::ArrayRef<Type> &R) {
+  addDataToConsumer(DataConsumer, R.size());
+}
+
 } // end namespace data_collection
 } // end namespace clang
 
 #endif // LLVM_CLANG_AST_DATACOLLECTION_H

include/clang/AST/DeclDataCollectors.td

+//--- Declarations -------------------------------------------------------//
+
+class Decl {
+  code Code = [{
+      // Every Declaration gets a tag field in the hash stream. It is
+      // hashed to add additional randomness to the hash
+      addData(llvm::hash_value(S->getKind()));
+
+      // CrossRef
+      addData(S->attrs());
+  }];
+}
+
+class DeclContext  {
+   code Code = [{
+      // CrossRef
+      addData(S->decls());
+   }];
+}
+
+class BlockDecl  {
+   code Code = [{
+      // CrossRef
+      auto it = llvm::make_range(S->capture_begin(), S->capture_end());
+      addData(it);
+   }];
+}
+
+
+class ValueDecl  {
+  code Code = [{
+      addData(S->getType());
+      addData(S->isWeak());
+  }];
+}
+
+class NamedDecl {
+  code Code = [{
+      addData(S->getName());
+  }];
+}
+
+class TypeDecl {
+  code Code = [{
+      addData(QualType(S->getTypeForDecl(),0));
+  }];
+}
+
+class EnumDecl {
+  code Code = [{
+      addData(S->getNumPositiveBits());
+      addData(S->getNumNegativeBits());
+  }];
+}
+
+class EnumConstantDecl {
+  code Code = [{
+       /* Not every enum has a init expression. Therefore, 
+          we extract the actual enum value from it. */
+       addData(S->getInitVal().getExtValue());
+  }];
+}
+
+class TagDecl {
+  code Code = [{
+     addData(S->getTagKind());
+  }];
+}
+
+
+class TypedefNameDecl {
+  code Code = [{
+     addData(S->getUnderlyingType());
+  }];
+}
+
+class VarDecl {
+  code Code = [{
+      addData(S->getStorageClass());
+      addData(S->getTLSKind());
+      addData(S->isModulePrivate());
+      addData(S->isNRVOVariable());
+  }];
+}
+
+class ParmVarDecl {
+  code Code = [{
+       addData(S->isParameterPack());
+       addData(S->getOriginalType());
+  }];
+}
+
+class ImplicitParamDecl {
+  code Code = [{
+       addData(S->getParameterKind());
+  }];
+}
+
+class FunctionDecl {
+  code Code = [{
+       addData(S->isExternC());
+       addData(S->isGlobal());
+       addData(S->isNoReturn());
+       addData(S->getStorageClass());
+       addData(S->isInlineSpecified());
+       addData(S->isInlined());
+
+       // CrossRef
+       auto range = llvm::make_range(S->param_begin(), S->param_end());
+       addData(range);
+  }];
+}
+
+class LabelDecl {
+  code Code = [{
+       addData(S->isGnuLocal());
+       addData(S->isMSAsmLabel());
+       if (S->isMSAsmLabel()) {
+          addData(S->getMSAsmLabel());
+       }
+  }];
+}
+
+class CXXRecordDecl {
+  code Code = [{
+       // CrossRef
+       if (S->isCompleteDefinition()) {
+           addData(S->bases());
+       }
+  }];
+}
+
+class CXXConstructorDecl {
+  code Code = [{
+       // CrossRef
+       addData(S->inits());
+  }];
+}
+
+class FieldDecl {
+  code Code = [{
+      addData(S->isBitField());
+  }];
+}
+
+class CapturedDecl {
+  code Code = [{
+      addData(S->isNothrow());
+  }];
+}
+
+class DecompositionDecl {
+  code Code = [{
+      // CrossRef
+      addData(S->bindings());
+  }];
+}
+
+
+//--- Obj-C ---------------------------------------------------------//
+
+class ObjCCategoryDecl {
+  code Code = [{
+     // CrossRef
+     if (auto *it = S->getTypeParamList()) {
+       auto range = llvm::make_range(it->begin(), it->end());
+       addData(range);
+     }
+  }];
+}
+
+class ObjCInterfaceDecl {
+  code Code = [{
+     // CrossRef
+     if (auto *it = S->getTypeParamListAsWritten()) {
+       auto range = llvm::make_range(it->begin(), it->end());
+       addData(range);
+     }
+  }];
+}
+
+class ObjCMethodDecl {
+  code Code = [{
+     // CrossRef
+     auto range = llvm::make_range(S->param_begin(), S->param_end());
+     addData(range);
+  }];
+}
+
+//--- Templates -----------------------------------------------------//
+
+class FriendTemplateDecl {
+  code Code = [{
+      // CrossRef
+      addData(S->getNumTemplateParameters());
+      for (unsigned I = 0, E = S->getNumTemplateParameters(); I < E; ++I) {
+          auto TPL = S->getTemplateParameterList(I);
+          auto it  = llvm::make_range(TPL->begin(), TPL->end());
+          addData(it);
+      }
+  }];
+}
+

include/clang/AST/StmtDataCollectors.td

 class Stmt {
   code Code = [{
     addData(S->getStmtClass());
     // This ensures that non-macro-generated code isn't identical to
     // macro-generated code.
     addData(data_collection::getMacroStack(S->getLocStart(), Context));
     addData(data_collection::getMacroStack(S->getLocEnd(), Context));
+
+    // CrossRef
+    addData(S->children());
   }];
 }
 
 class Expr {
   code Code = [{
     addData(S->getType());
   }];
 }
 
 //--- Builtin functionality ----------------------------------------------//
 class ArrayTypeTraitExpr {
   code Code = [{
     addData(S->getTrait());
   }];
 }
 class ExpressionTraitExpr {
   code Code = [{
     addData(S->getTrait());
   }];
 }
 class PredefinedExpr {
   code Code = [{
     addData(S->getIdentType());
+    addData(S->getFunctionName()->getString());
   }];
 }
 class TypeTraitExpr {
   code Code = [{
     addData(S->getTrait());
+    // CrossRef
+    addData(S->getNumArgs());
     for (unsigned i = 0; i < S->getNumArgs(); ++i)
       addData(S->getArg(i)->getType());
   }];
 }
 
+class UnaryExprOrTypeTraitExpr {
+  code Code = [{
+    addData(S->getKind());
+    if (S->isArgumentType()) {
+       addData(S->getArgumentType());
+    }
+  }];
+}
+
+
 //--- Calls --------------------------------------------------------------//
 class CallExpr {
   code Code = [{
     // Function pointers don't have a callee and we just skip hashing it.
     if (const FunctionDecl *D = S->getDirectCallee()) {
       // If the function is a template specialization, we also need to handle
       // the template arguments as they are not included in the qualified name.
       if (auto Args = D->getTemplateSpecializationArgs()) {

 //--- Value references ---------------------------------------------------//
 class DeclRefExpr {
   code Code = [{
     addData(S->getDecl()->getQualifiedNameAsString());
   }];
 }
 class MemberExpr {
   code Code = [{
+    // I suspect this should be included: addData(S->isArrow());
     addData(S->getMemberDecl()->getName());
   }];
 }
 
 //--- Literals -----------------------------------------------------------//
 class IntegerLiteral {
   code Code = [{
     addData(llvm::hash_value(S->getValue()));

 
 //--- Casts --------------------------------------------------------------//
 class ObjCBridgedCastExpr {
   code Code = [{
     addData(S->getBridgeKind());
   }];
 }
 
+class CastExpr {
+  code Code = [{
+    addData(S->getCastKind());
+  }];
+}
+
 //--- Miscellaneous Exprs ------------------------------------------------//
 class BinaryOperator {
   code Code = [{
     addData(S->getOpcode());
   }];
 }
 class UnaryOperator {
   code Code = [{
     addData(S->getOpcode());
   }];
 }
 
+class VAArgExpr {
+  code Code = [{
+       addData(S->isMicrosoftABI());
+  }];
+}
+
 //--- Control flow -------------------------------------------------------//
 class GotoStmt {
   code Code = [{
     addData(S->getLabel()->getName());
   }];
 }
 class IndirectGotoStmt {
   code Code = [{

 //--- Miscellaneous Stmts ------------------------------------------------//
 class CXXFoldExpr {
   code Code = [{
     addData(S->isRightFold()); addData(S->getOperator());
   }];
 }
 class GenericSelectionExpr {
   code Code = [{
+    // CrossRef
+    addData(S->getNumAssocs());
     for (unsigned i = 0; i < S->getNumAssocs(); ++i) {
       addData(S->getAssocType(i));
     }
   }];
 }
+
+class PseudoObjectExpr {
+  code Code = [{
+    // CrossRef
+    addData(S->semantics());
+  }];
+}
+
 class LambdaExpr {
   code Code = [{
+    addData(S->isGenericLambda());
+    addData(S->isMutable());
+    addData(S->hasExplicitParameters());
+    addData(S->hasExplicitResultType());
+
+
+    // CrossRef
+    addData(S->captures());
+    addData(S->explicit_captures());
     for (const LambdaCapture &C : S->captures()) {
       addData(C.isPackExpansion());
       addData(C.getCaptureKind());
       if (C.capturesVariable())
         addData(C.getCapturedVar()->getType());
     }
-    addData(S->isGenericLambda());
-    addData(S->isMutable());
+    
+
   }];
 }
 class DeclStmt {
   code Code = [{
-    auto numDecls = std::distance(S->decl_begin(), S->decl_end());
-    addData(static_cast<unsigned>(numDecls));
+    // CrossRef
+    addData(S->decls());
+
+    // FIXME? As this should be done by a using visitor
     for (const Decl *D : S->decls()) {
       if (const VarDecl *VD = dyn_cast<VarDecl>(D)) {
         addData(VD->getType());
       }
     }
   }];
 }
 class AsmStmt {
   code Code = [{
     addData(S->isSimple());
     addData(S->isVolatile());
     addData(S->generateAsmString(Context));
+
+    // CrossRef + FIXME
+    addData(S->getNumInputs());
+    addData(S->getNumOutputs());
+    addData(S->getNumClobbers());
+
     for (unsigned i = 0; i < S->getNumInputs(); ++i) {
       addData(S->getInputConstraint(i));
     }
     for (unsigned i = 0; i < S->getNumOutputs(); ++i) {
       addData(S->getOutputConstraint(i));
     }
     for (unsigned i = 0; i < S->getNumClobbers(); ++i) {
       addData(S->getClobber(i));
     }
   }];
 }
 class AttributedStmt {
   code Code = [{
     for (const Attr *A : S->getAttrs()) {
+       // We duplicate class Attr here to not rely on being integrated
+       // into a RecursiveASTVisitor.
+       std::string AttrString;      
+       llvm::raw_string_ostream OS(AttrString);
+       A->printPretty(OS, Context.getLangOpts());
+       OS.flush();
       addData(std::string(A->getSpelling()));
     }
   }];
 }
+
+class CompoundStmt {
+  code Code = [{
+    // CrossRef
+    addData(S->size());
+  }];
+}
+

include/clang/AST/TypeDataCollectors.td

+//--- Types ---------------------------------------------------------------//
+
+class Type {
+  code Code = [{
+     addData(llvm::hash_value(S->getTypeClass()));
+  }];
+}
+
+class BuiltinType {
+   code Code = [{
+      addData(S->getKind());
+   }];
+}
+
+class ArrayType  {
+   code Code = [{
+      addData(S->getSizeModifier());
+      addData(S->getIndexTypeCVRQualifiers());
+   }];
+}
+
+class ConstantArrayType {
+   code Code = [{
+      addData(S->getSize().getZExtValue());
+   }];
+}
+
+class VectorType {
+   code Code = [{
+      addData(S->getNumElements());
+      addData(S->getVectorKind());
+   }];
+}
+
+class FunctionType {
+   code Code = [{
+      addData(S->getRegParmType());
+      addData(S->getCallConv());
+   }];
+}
+
+class FunctionProtoType {
+   code Code = [{
+      addData(S->getExceptionSpecType());
+      addData(S->isVariadic());
+      addData(S->getRefQualifier());
+      addData(S->hasTrailingReturn());
+
+      addData(S->param_types());
+      addData(S->exceptions());
+   }];
+}
+
+class UnaryTransformType {
+   code Code = [{
+        addData(S->getUTTKind());
+   }];
+}
+
+class AttributedType {
+   code Code = [{
+        addData(S->getAttrKind());
+   }];
+}
+
+class ElaboratedType {
+   code Code = [{
+        addData(S->getKeyword());
+   }];
+}
+
+class ObjCObjectType {
+   code Code = [{
+        addData(S->getTypeArgsAsWritten());
+   }];
+}
+
+

unittests/AST/CHashTest.cpp

+//===- unittests/AST/DataCollectionTest.cpp -------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains tests for the DataCollection module.
+//
+// They work by hashing the collected data of two nodes and asserting that the
+// hash values are equal iff the nodes are considered equal.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/CHashVisitor.h"
+#include "clang/Tooling/Tooling.h"
+#include "gtest/gtest.h"
+#include <memory>
+
+using namespace clang;
+using namespace tooling;
+
+
+class CHashConsumer : public ASTConsumer {
+    CompilerInstance &CI;
+    llvm::MD5::MD5Result *ASTHash;
+
+public:
+
+    CHashConsumer(CompilerInstance &CI, llvm::MD5::MD5Result *ASTHash)
+        : CI(CI), ASTHash(ASTHash){}
+
+    virtual void HandleTranslationUnit(clang::ASTContext &Context) override {
+        TranslationUnitDecl *TU = Context.getTranslationUnitDecl();
+
+        // Traversing the translation unit decl via a RecursiveASTVisitor
+        // will visit all nodes in the AST.
+        CHashVisitor<> Visitor(Context);
+        Visitor.TraverseDecl(TU);
+        // Copy Away the resulting hash
+        *ASTHash = *Visitor.getHash(TU);
+
+    }
+
+    ~CHashConsumer() override {}
+};
+
+struct CHashAction : public ASTFrontendAction {
+    llvm::MD5::MD5Result *Hash;
+
+    CHashAction(llvm::MD5::MD5Result *Hash) : Hash(Hash) {}
+
+    std::unique_ptr<ASTConsumer> CreateASTConsumer(CompilerInstance &CI,
+                                                   StringRef) override {
+        return std::unique_ptr<ASTConsumer>(new CHashConsumer(CI, Hash));
+    }
+};
+
+static testing::AssertionResult
+isASTHashEqual(StringRef Code1, StringRef Code2) {
+    llvm::MD5::MD5Result Hash1, Hash2;
+    if (!runToolOnCode(new CHashAction(&Hash1), Code1)) {
+        return testing::AssertionFailure()
+            << "Parsing error in (A)\"" << Code1.str() << "\"";
+    }
+    if (!runToolOnCode(new CHashAction(&Hash2), Code2)) {
+        return testing::AssertionFailure()
+            << "Parsing error in (B) \"" << Code2.str() << "\"";
+    }
+    return testing::AssertionResult(Hash1 == Hash2);
+}
+
+TEST(CHashVisitor, TestRecordTypes) {
+    ASSERT_TRUE(isASTHashEqual( // Unused struct
+                     "struct foobar { int a0; char a1; unsigned long a2; };",
+                     "struct foobar { int a0; char a1;};"
+                     ));
+
+}
+
+TEST(CHashVisitor, TestSourceStructure) {
+    ASSERT_FALSE(isASTHashEqual(
+                     "void foo() { int c; if (0) { c = 1; } }",
+                     "void foo() { int c; if (0) { } c = 1; }"));
+
+    ASSERT_FALSE(isASTHashEqual(
+                     "void f1() {} void f2() {       }",
+                     "void f1() {} void f2() { f1(); }"));
+}

unittests/AST/CMakeLists.txt

add_clang_unittest(ASTTests
   DeclPrinterTest.cpp
   DeclTest.cpp
   EvaluateAsRValueTest.cpp
   ExternalASTSourceTest.cpp
   NamedDeclPrinterTest.cpp
   PostOrderASTVisitor.cpp
   SourceLocationTest.cpp
   StmtPrinterTest.cpp
+  CHashTest.cpp
   )
 
 target_link_libraries(ASTTests
   clangAST
   clangASTMatchers
   clangBasic
   clangFrontend
   clangTooling
   )