Add better ODR checking for modules.

When objects are imported for modules, there is a chance that a name collision
will cause an ODR violation.  Previously, only a small number of such
violations were detected.  This patch provides a stronger check based on
AST nodes.

The information needed to uniquely identify an object is taked from the AST and
put into a one-dimensional byte stream.  This stream is then hashed to give
a value to represent the object, which is stored with the other object data
in the module.

When modules are loaded, and Decl's are merged, the hash values of the two
Decl's are compared.  Only Decl's with matched hash values will be merged.
Mismatch hashes will generate a module error, and if possible, point to the
first difference between the two objects.

The transform from AST to byte stream is a modified depth first algorithm.
Due to references between some AST nodes, a pure depth first algorithm could
generate loops.  For Stmt nodes, a straight depth first processing occurs.
For Type and Decl nodes, they are replaced with an index number and only on
first visit will these nodes be processed.  As an optimization, boolean
values are saved and stored together in reverse order at the end of the
byte stream to lower the ammount of data that needs to be hashed.

Compile time impact was measured at 1.5-2.0% during module building, and
negligible during builds without module building.

Differential Revision: https://reviews.llvm.org/D21675


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@293585 91177308-0d34-0410-b5e6-96231b3b80d8

4 files changed, 153 insertions, 0 deletions

diff --git a/include/clang/AST/DeclCXX.h b/include/clang/AST/DeclCXX.h
index 0ca08db162..4e73613d34 100644
--- a/include/clang/AST/DeclCXX.h
+++ b/include/clang/AST/DeclCXX.h
@@ -458,6 +458,9 @@ class CXXRecordDecl : public RecordDecl {
     /// \brief Whether we are currently parsing base specifiers.
     unsigned IsParsingBaseSpecifiers : 1;
 
+    /// \brief A hash of parts of the class to help in ODR checking.
+    unsigned ODRHash;
+
     /// \brief The number of base class specifiers in Bases.
     unsigned NumBases;
 
@@ -703,6 +706,9 @@ public:
     return data().IsParsingBaseSpecifiers;
   }
 
+  void computeODRHash();
+  unsigned getODRHash() const { return data().ODRHash; }
+
   /// \brief Sets the base classes of this struct or class.
   void setBases(CXXBaseSpecifier const * const *Bases, unsigned NumBases);
 
diff --git a/include/clang/AST/ODRHash.h b/include/clang/AST/ODRHash.h
new file mode 100644
index 0000000000..0bf4d83807
--- /dev/null
+++ b/include/clang/AST/ODRHash.h
@@ -0,0 +1,80 @@
+//===-- ODRHash.h - Hashing to diagnose ODR failures ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file contains the declaration of the ODRHash class, which calculates
+/// a hash based on AST nodes, which is stable across different runs.
+///
+//===----------------------------------------------------------------------===//
+
+#include "clang/AST/DeclarationName.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TemplateBase.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/SmallVector.h"
+
+namespace clang {
+
+class Decl;
+class IdentifierInfo;
+class NestedNameSpecifer;
+class Stmt;
+class TemplateParameterList;
+
+// ODRHash is used to calculate a hash based on AST node contents that
+// does not rely on pointer addresses.  This allows the hash to not vary
+// between runs and is usable to detect ODR problems in modules.  To use,
+// construct an ODRHash object, then call Add* methods over the nodes that
+// need to be hashed.  Then call CalculateHash to get the hash value.
+// Typically, only one Add* call is needed.  clear can be called to reuse the
+// object.
+class ODRHash {
+  // Use DenseMaps to convert between Decl and Type pointers and an index value.
+  llvm::DenseMap<const Decl*, unsigned> DeclMap;
+  llvm::DenseMap<const Type*, unsigned> TypeMap;
+
+  // Save space by processing bools at the end.
+  llvm::SmallVector<bool, 128> Bools;
+
+  llvm::FoldingSetNodeID ID;
+
+public:
+  ODRHash() {}
+
+  // Use this for ODR checking classes between modules.  This method compares
+  // more information than the AddDecl class.
+  void AddCXXRecordDecl(const CXXRecordDecl *Record);
+
+  // Add AST nodes that need to be processes.  Some nodes are processed
+  // immediately while others are queued and processed later.
+  void AddDecl(const Decl *D);
+  void AddType(const Type *T);
+  void AddQualType(QualType T);
+  void AddStmt(const Stmt *S);
+  void AddIdentifierInfo(const IdentifierInfo *II);
+  void AddNestedNameSpecifier(const NestedNameSpecifier *NNS);
+  void AddTemplateName(TemplateName Name);
+  void AddDeclarationName(DeclarationName Name);
+  void AddTemplateArgument(TemplateArgument TA);
+  void AddTemplateParameterList(const TemplateParameterList *TPL);
+
+  // Reset the object for reuse.
+  void clear();
+
+  // Processes any unvisited nodes in Pointers and computes the final hash
+  // value.
+  unsigned CalculateHash();
+
+  // Save booleans until the end to lower the size of data to process.
+  void AddBoolean(bool value);
+};
+
+}  // end namespace clang
diff --git a/include/clang/AST/Stmt.h b/include/clang/AST/Stmt.h
index e28675d6a8..defe6c2ac2 100644
--- a/include/clang/AST/Stmt.h
+++ b/include/clang/AST/Stmt.h
@@ -39,6 +39,7 @@ namespace clang {
   class Expr;
   class IdentifierInfo;
   class LabelDecl;
+  class ODRHash;
   class ParmVarDecl;
   class PrinterHelper;
   struct PrintingPolicy;
@@ -436,6 +437,8 @@ public:
   /// written in the source.
   void Profile(llvm::FoldingSetNodeID &ID, const ASTContext &Context,
                bool Canonical) const;
+
+  void ProcessODRHash(llvm::FoldingSetNodeID &ID, ODRHash& Hash) const;
 };
 
 /// DeclStmt - Adaptor class for mixing declarations with statements and
diff --git a/include/clang/Basic/DiagnosticSerializationKinds.td b/include/clang/Basic/DiagnosticSerializationKinds.td
index 066a1f5fa6..9371b05c73 100644
--- a/include/clang/Basic/DiagnosticSerializationKinds.td
+++ b/include/clang/Basic/DiagnosticSerializationKinds.td
@@ -117,6 +117,70 @@ def note_module_odr_violation_different_definitions : Note<
 def err_module_odr_violation_different_instantiations : Error<
   "instantiation of %q0 is different in different modules">;
 
+def err_module_odr_violation_mismatch_decl : Error<
+  "%q0 has different definitions in different modules; first difference is "
+  "%select{definition in module '%2'|defined here}1 found "
+  "%select{end of class|public access specifier|private access specifier|"
+  "protected access specifier|friend declaration|enum|"
+  "static assert|typedef|type alias|method|constructor|destructor|"
+  "conversion operator|field|other}3">;
+def note_module_odr_violation_mismatch_decl : Note<"but in '%0' found "
+  "%select{end of class|public access specifier|private access specifier|"
+  "protected access specifier|friend declaration|enum|"
+  "static assert|typedef|type alias|method|constructor|destructor|"
+  "conversion operator|field|other}1">;
+
+def err_module_odr_violation_mismatch_decl_diff : Error<
+  "%q0 has different definitions in different modules; first difference is "
+  "%select{definition in module '%2'|defined here}1 found "
+  "%select{friend %4|enum %4|element %4 in enum %5|"
+  "element %4 in enum %5 with initializer|"
+  "element %4 in enum %5 with no initializer|"
+  "element %4 in enum %5 with initializer|"
+  "enum %4 has %5 element%s5|"
+  "static assert with condition|"
+  "static assert with message|"
+  "static assert with %select{|no}4 message|"
+  "%select{typedef|type alias}4 name %5|"
+  "method named %4|"
+  "method %4 is %select{non-|}5static|"
+  "method %4 is %select{not |}5inline|"
+  "method %4 is %select{not |}5const|"
+  "method %4 has %5 parameter%s5|"
+  "method %4 has %ordinal5 parameter %select{named %7|with no name}6|"
+  "method %4 has %ordinal5 parameter with type %6|"
+  "method %4 has %ordinal5 parameter with default argument|"
+  "method %4 has %ordinal5 parameter with %select{no |}6 default argument|"
+  "method %4 has %select{|no }5body|"
+  "method %4 has different body|"
+  "field %4|"
+  "%select{field|bitfield}5 %4|"
+  "%select{non-mutable|mutable}5 %4}3">;
+def note_module_odr_violation_mismatch_decl_diff : Note<"but in '%0' found "
+  "%select{other friend %2|other enum %2|different element %2 in enum %3|"
+  "element %2 in enum %3 with initializer|"
+  "element %2 in enum %3 with no initializer|"
+  "element %2 in enum %3 with different initializer|"
+  "enum %2 has %3 element%s3|"
+  "static assert with different condition|"
+  "static assert with different message|"
+  "static assert with %select{|no}2 message|"
+  "different %select{typedef|type alias}2 name %3|"
+  "method named %2|"
+  "method %2 is %select{non-|}3static|"
+  "method %2 is %select{not |}3inline|"
+  "method %2 is %select{not |}3const|"
+  "method %2 has %3 parameter%s3|"
+  "method %2 has %ordinal3 parameter %select{named %5|with no name}4|"
+  "method %2 has %ordinal3 parameter with type %4|"
+  "method %2 has %ordinal3 parameter with different default argument|"
+  "method %2 has %ordinal3 parameter with %select{no |}4default argument|"
+  "method %2 has %select{|no }3body|"
+  "method %2 has different body|"
+  "field %2|"
+  "%select{field|bitfield}3 %2|"
+  "%select{non-mutable|mutable}3 %2}1">;
+
 def warn_module_uses_date_time : Warning<
   "%select{precompiled header|module}0 uses __DATE__ or __TIME__">,
   InGroup<DiagGroup<"pch-date-time">>;