[PATCH 3/3] Add some type equality paranoia.

[Giuliano Procida <gprocida@google.com>]

This commit is an attempt to answer the question "how do canonical
types relate to type equality?" and in particular "are they just an
optimisation?". It adds some instrumentation to the equality_helper
methods.

- they take an extra line (__LINE__) argument
- both canonical type pointer and plain comparisons are done
- comparisons are skipped if the pointers are identical
- in-progress comparisons are recorded to avoid infinite recursion
- discrepancies are logged

The commit also adds some comments to reflect behaviour seen in
practice with libabigail's test suite.

Note that this is not quite cross-checking canonical pointer
comparison with deep equality as the (recursive) equality tests are
themselves influenced by canonical pointer comparisons in the
direction of considering more things to be equal.

Note that thread-local storage is used to avoid corruption of the
comparison stack. This is not portable to older compilers in its
current form.

While the behaviour should be the same, the code runs much more slowly
and there can be considerable logging to stderr depending on what you
choose to log.

Signed-off-by: Giuliano Procida <gprocida@google.com>
---
 src/abg-ir.cc | 111 ++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 94 insertions(+), 17 deletions(-)

diff --git a/src/abg-ir.cc b/src/abg-ir.cc
index 4b7e180d..e797a341 100644
--- a/src/abg-ir.cc
+++ b/src/abg-ir.cc
@@ -651,18 +651,81 @@ struct type_name_comp
   {return operator()(type_base_sptr(l), type_base_sptr(r));}
 }; // end struct type_name_comp
 
+class hold
+{
+ public:
+  hold(const void* l, const void* r)
+    : p_(std::make_pair(l, r))
+  {
+    st_.push_back(p_);
+  }
+  ~hold()
+  {
+    ABG_ASSERT(st_.size());
+    ABG_ASSERT(st_.back() == p_);
+    st_.pop_back();
+  }
+  static bool has(const void* l, const void* r)
+  {
+    return find(st_.begin(), st_.end(), std::make_pair(l, r)) != st_.end();
+  }
+ private:
+  const std::pair<const void *, const void *> p_;
+  thread_local static std::vector<std::pair<const void*, const void*>> st_;
+};
+
+thread_local std::vector<std::pair<const void*, const void*>> hold::st_;
+
+const bool debug_equality = true;
+
 template<typename T>
-bool equality_helper(const T* lptr, const T* rptr,
+bool equality_helper(size_t line, const T* lptr, const T* rptr,
 		     const type_base* lcanon,
 		     const type_base* rcanon)
 {
-  return lcanon && rcanon ? lcanon == rcanon : equals(*lptr, *rptr, 0);
+  if (debug_equality)
+    {
+      // Short cut equality with identical pointers to avoid wasteful deep
+      // comparisons.
+      if (lptr == rptr)
+	return true;
+      // Record outcome of canonical type pointer comparison.
+      char c = lcanon ? rcanon ? lcanon == rcanon ? '1' : '0' : 'L' : rcanon ? 'R' : 'X';
+      // If we are already holding this pair of type_base pointers we should
+      // assume they are equal in recursive calls.
+      bool held = hold::has(lptr, rptr);
+      bool eq;
+      if (held)
+	eq = true;
+      else
+	{
+	  hold it(static_cast<const void *>(lptr),
+		  static_cast<const void *>(rptr));
+	  eq = equals(*lptr, *rptr, 0);
+	}
+      // Record outcome of plain comparison.
+      char p = held ? 'H' : eq ? '1' : '0';
+      if (c + p == '0' + '1')
+	{
+	  // Avoid tearing the output.
+	  std::ostringstream os;
+	  os << line << " canon=" << c << " plain=" << p
+	     << " '" << lptr->get_cached_pretty_representation(true)
+	     << "' '" << rptr->get_cached_pretty_representation(true) << "'\n";
+	  std::cerr << os.str();
+	}
+      return lcanon && rcanon ? lcanon == rcanon : eq;
+    }
+  else
+    {
+      return lcanon && rcanon ? lcanon == rcanon : equals(*lptr, *rptr, 0);
+    }
 }
 
 template<typename T>
-bool equality_helper(const T* lptr, const T* rptr)
+bool equality_helper(size_t line, const T* lptr, const T* rptr)
 {
-  return equality_helper(lptr, rptr,
+  return equality_helper(line, lptr, rptr,
 			 lptr->get_naked_canonical_type(),
 			 rptr->get_naked_canonical_type());
 }
@@ -12706,7 +12769,7 @@ type_decl::operator==(const decl_base& o) const
   const type_decl* other = dynamic_cast<const type_decl*>(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  return equality_helper(__LINE__, this, other);
 }
 
 /// Return true if both types equals.
@@ -12883,7 +12946,7 @@ scope_type_decl::operator==(const decl_base& o) const
   const scope_type_decl* other = dynamic_cast<const scope_type_decl*>(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  return equality_helper(__LINE__, this, other);
 }
 
 /// Equality operator between two scope_type_decl.
@@ -13247,7 +13310,7 @@ qualified_type_def::operator==(const decl_base& o) const
     dynamic_cast<const qualified_type_def*>(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  return equality_helper(__LINE__, this, other);
 }
 
 /// Equality operator for qualified types.
@@ -13614,7 +13677,8 @@ pointer_type_def::operator==(const decl_base& o) const
   const pointer_type_def* other = is_pointer_type(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  // Sometimes canonically distinct but compare as equal.
+  return equality_helper(__LINE__, this, other);
 }
 
 /// Return true iff both instances of pointer_type_def are equal.
@@ -13918,7 +13982,7 @@ reference_type_def::operator==(const decl_base& o) const
     dynamic_cast<const reference_type_def*>(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  return equality_helper(__LINE__, this, other);
 }
 
 /// Equality operator of the @ref reference_type_def type.
@@ -14460,7 +14524,7 @@ array_type_def::subrange_type::operator==(const decl_base& o) const
     dynamic_cast<const subrange_type*>(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  return equality_helper(__LINE__, this, other);
 }
 
 /// Equality operator.
@@ -14778,7 +14842,8 @@ array_type_def::operator==(const decl_base& o) const
     dynamic_cast<const array_type_def*>(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  // Sometimes canonically distinct but compare as equal.
+  return equality_helper(__LINE__, this, other);
 }
 
 bool
@@ -15254,7 +15319,8 @@ enum_type_decl::operator==(const decl_base& o) const
   const enum_type_decl* op = dynamic_cast<const enum_type_decl*>(&o);
   if (!op)
     return false;
-  return equality_helper(this, op);
+  // Sometimes canonically distinct but compare as equal.
+  return equality_helper(__LINE__, this, op);
 }
 
 /// Equality operator.
@@ -15604,7 +15670,9 @@ typedef_decl::operator==(const decl_base& o) const
   const typedef_decl* other = dynamic_cast<const typedef_decl*>(&o);
   if (!other)
     return false;
-  return equality_helper(this, other);
+  // Sometimes canonically distinct but compare as equal.
+  // Sometimes canonically equal but compare as distinct.
+  return equality_helper(__LINE__, this, other);
 }
 
 /// Equality operator
@@ -16699,7 +16767,9 @@ function_type::operator==(const type_base& other) const
   const function_type* o = dynamic_cast<const function_type*>(&other);
   if (!o)
     return false;
-  return equality_helper(this, o);
+  // Sometimes canonically distinct but compare as equal.
+  // Sometimes canonically equal but compare as distinct.
+  return equality_helper(__LINE__, this, o);
 }
 
 /// Return a copy of the pretty representation of the current @ref
@@ -19074,7 +19144,9 @@ class_or_union::operator==(const decl_base& other) const
     other_canonical_type =
       op->get_naked_definition_of_declaration()->get_naked_canonical_type();
 
-  return equality_helper(this, op, canonical_type, other_canonical_type);
+  // Or should this just be definition_of_declaration equality?
+  // Sometimes canonically equal but compare as distinct.
+  return equality_helper(__LINE__, this, op, canonical_type, other_canonical_type);
 }
 
 /// Equality operator.
@@ -20925,7 +20997,10 @@ class_decl::operator==(const decl_base& other) const
     other_canonical_type =
       op->get_naked_definition_of_declaration()->get_naked_canonical_type();
 
-  return equality_helper(this, op, canonical_type, other_canonical_type);
+  // Or should this just be definition_of_declaration equality?
+  // Sometimes canonically distinct but compare as equal.
+  // Sometimes canonically equal but compare as distinct.
+  return equality_helper(__LINE__, this, op, canonical_type, other_canonical_type);
 }
 
 /// Equality operator for class_decl.
@@ -21706,7 +21781,9 @@ union_decl::operator==(const decl_base& other) const
   const union_decl* op = dynamic_cast<const union_decl*>(&other);
   if (!op)
     return false;
-  return equality_helper(this, op);
+  // Sometimes canonically distinct but compare as equal.
+  // Sometimes canonically equal but compare as distinct.
+  return equality_helper(__LINE__, this, op);
 }
 
 /// Equality operator for union_decl.
-- 
2.27.0.383.g050319c2ae-goog