Reimplement dynamic cast and catch matching.

	* cp-tree.h (get_dynamic_cast_base_type): Prototype new function
	* search.c (dynamic_cast_base_recurse): New function.
	(get_dynamic_cast_base_type): New function for dynamic cast.
	* rtti.c (build_dynamic_cast_1): Determine source and target
	class relationship. Call __dynamic_cast_2.
	* tinfo.h (__user_type_info::upcast): New catch dispatcher.
	(__user_type_info::dyncast): New dynamic cast dispatcher.
	(__user_type_info::sub_kind): New nested enumeration.
	(__user_type_info::contained_p): sub_kind predicate.
	(__user_type_info::contained_public_p): Likewise.
	(__user_type_info::contained_nonpublic_p): Likewise.
	(__user_type_info::contained_nonvirtual_p: Likewise.
	(__user_type_info::upcast_result): New nested struct.
	(__user_type_info::dyncast_result): New nested struct.
	(*::do_upcast): New catch function.
	(*::do_dyncast): New dynamic cast function.
	(__user_type_info::find_public_subobj): New dynamic cast
	helper dispatcher.
	(*::do_find_public_subobj): New dynamic cast helper function.
	* tinfo.cc (__user_type_info::upcast): Define catch dispatcher.
	(__user_type_info::dyncast): Define dynamic cast dispatcher.
	(*::do_upcast): Define catch function.
	(*::do_dyncast): Define dynamic cast function.
	(*::do_find_public_subobj): Define dynamic cast helper function.
	* tinfo2.cc (__throw_type_match_rtti_2): Use upcast.
	(__dynamic_cast): Backwards compatibility wrapper. Use dyncast.
	(__dynamic_cast_2): New dynamic cast runtime.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@29544 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 430 insertions, 77 deletions

diff --git a/gcc/cp/tinfo.cc b/gcc/cp/tinfo.cc
index fe22e8de074..1d4885c9264 100644
--- a/gcc/cp/tinfo.cc
+++ b/gcc/cp/tinfo.cc
@@ -62,100 +62,453 @@ extern "C" void
 __rtti_user (void *addr, const char *name)
 { new (addr) __user_type_info (name); }
 
-// dynamic_cast helper methods.
-// Returns 1 if the cast succeeds, 0 otherwise.  Stores the adjusted value
-// in VALP.
-
+// Upcast for catch checking. OBJPTR points to the thrown object and might be
+// NULL. Return 0 on failure, non-zero on success. Set *ADJPTR to adjusted
+// object pointer.
 int __user_type_info::
-dcast (const type_info& to, int, void *addr, void **valp,
-       const type_info *, void *) const
+upcast (const type_info &target, void *objptr,
+        void **adjptr) const
+{
+  upcast_result result;
+  
+  if (do_upcast (contained_public, target, objptr, result))
+    return 0;
+  *adjptr = result.target_obj;
+  return contained_public_p (result.whole2target);
+}
+
+// Down or cross cast for dynamic_cast. OBJPTR points to the most derrived
+// object, SUBPTR points to the static base object. Both must not be NULL.
+// TARGET specifies the desired target type, SUBTYPE specifies the static
+// type. Both must be defined. Returns adjusted object pointer on success,
+// NULL on failure. [expr.dynamic.cast]/8 says 'unambiguous public base'. This
+// itself is an ambiguous statement. We choose it to mean the base must be
+// separately unambiguous and public, rather than unambiguous considering only
+// public bases.
+void *__user_type_info::
+dyncast (int boff,
+         const type_info &target, void *objptr,
+         const type_info &subtype, void *subptr) const
 {
-  *valp = addr;
-  return (*this == to);
+  dyncast_result result;
+  
+  do_dyncast (boff, contained_public,
+              target, objptr, subtype, subptr, result);
+  if (!result.target_obj)
+    return NULL;
+  if (contained_public_p (result.target2sub))
+    return result.target_obj;
+  if (contained_public_p (sub_kind (result.whole2sub & result.whole2target)))
+    // Found a valid cross cast
+    return result.target_obj;
+  if (contained_nonvirtual_p (result.whole2sub))
+    // Found an invalid cross cast, which cannot also be a down cast
+    return NULL;
+  if (result.target2sub == unknown)
+    result.target2sub = static_cast <const __user_type_info &> (target)
+                        .find_public_subobj (boff, subtype,
+                                             result.target_obj, subptr);
+  if (contained_public_p (result.target2sub))
+    // Found a valid down cast
+    return result.target_obj;
+  // Must be an invalid down cast, or the cross cast wasn't bettered
+  return NULL;
 }
 
-int __si_type_info::
-dcast (const type_info& to, int require_public, void *addr, void **valp,
-       const type_info *sub, void *subptr) const
+// Catch cast helper. ACCESS_PATH is the access from the complete thrown
+// object to this base. TARGET is the desired type we want to catch. OBJPTR
+// points to this base within the throw object, it might be NULL. Fill in
+// RESULT with what we find. Return true, should we determine catch must fail.
+bool __user_type_info::
+do_upcast (sub_kind access_path,
+           const type_info &target, void *objptr,
+           upcast_result &__restrict result) const
 {
-  if (*this == to)
+  if (*this == target)
     {
-      *valp = addr;
-      return 1;
+      result.target_obj = objptr;
+      result.base_type = nonvirtual_base_type;
+      result.whole2target = access_path;
+      return contained_nonpublic_p (access_path);
     }
-  return base.dcast (to, require_public, addr, valp, sub, subptr);
+  return false;
 }
 
-int __class_type_info::
-dcast (const type_info& desired, int is_public, void *objptr, void **valp,
-       const type_info *sub, void *subptr) const
+// dynamic cast helper. ACCESS_PATH gives the access from the most derived
+// object to this base. TARGET indicates the desired type we want. OBJPTR
+// points to this base within the object. SUBTYPE indicates the static type
+// started from and SUBPTR points to that base within the most derived object.
+// Fill in RESULT with what we find. Return true if we have located an
+// ambiguous match.
+bool __user_type_info::
+do_dyncast (int, sub_kind access_path,
+            const type_info &target, void *objptr,
+            const type_info &subtype, void *subptr,
+            dyncast_result &__restrict result) const
 {
-  *valp = objptr;
+  if (objptr == subptr && *this == subtype)
+    {
+      // The subobject we started from. Indicate how we are accessible from
+      // the most derived object.
+      result.whole2sub = access_path;
+      return false;
+    }
+  if (*this == target)
+    {
+      result.target_obj = objptr;
+      result.whole2target = access_path;
+      result.target2sub = not_contained;
+      return false;
+    }
+  return false;
+}
 
-  if (*this == desired)
-    return 1;
+// find_public_subobj helper. Return contained_public if we are the desired
+// subtype. OBJPTR points to this base type, SUBPTR points to the desired base
+// object.
+__user_type_info::sub_kind __user_type_info::
+do_find_public_subobj (int, const type_info &, void *objptr, void *subptr) const
+{
+  if (subptr == objptr)
+    // Must be our type, as the pointers match.
+    return contained_public;
+  return not_contained;
+}
 
-  int match_found = 0;
-  void *match = 0;
+// catch helper for single public inheritance types. See
+// __user_type_info::do_upcast for semantics.
+bool __si_type_info::
+do_upcast (sub_kind access_path,
+           const type_info &target, void *objptr,
+           upcast_result &__restrict result) const
+{
+  if (*this == target)
+    {
+      result.target_obj = objptr;
+      result.base_type = nonvirtual_base_type;
+      result.whole2target = access_path;
+      return contained_nonpublic_p (access_path);
+    }
+  return base.do_upcast (access_path, target, objptr, result);
+}
 
-  for (size_t i = 0; i < n_bases; i++)
+// dynamic cast helper for single public inheritance types. See
+// __user_type_info::do_dyncast for semantics. BOFF indicates how SUBTYPE
+// types are inherited by TARGET types.
+bool __si_type_info::
+do_dyncast (int boff, sub_kind access_path,
+            const type_info &target, void *objptr,
+            const type_info &subtype, void *subptr,
+            dyncast_result &__restrict result) const
+{
+  if (objptr == subptr && *this == subtype)
     {
-      if (is_public && base_list[i].access != PUBLIC)
-	continue;
+      // The subobject we started from. Indicate how we are accessible from
+      // the most derived object.
+      result.whole2sub = access_path;
+      return false;
+    }
+  if (*this == target)
+    {
+      result.target_obj = objptr;
+      result.whole2target = access_path;
+      if (boff >= 0)
+        result.target2sub = ((char *)subptr - (char *)objptr) == boff
+              ? contained_public : not_contained;
+      else if (boff == -3)
+        result.target2sub = not_contained;
+      return false;
+    }
+  return base.do_dyncast (boff, access_path,
+                          target, objptr, subtype, subptr, result);
+}
+
+// find_public_subobj helper. See __user_type_info::do_find_public_subobj or
+// semantics. BOFF indicates how SUBTYPE types are inherited by the original
+// target object.
+__user_type_info::sub_kind __si_type_info::
+do_find_public_subobj (int boff, const type_info &subtype, void *objptr, void *subptr) const
+{
+  if (subptr == objptr && subtype == *this)
+    return contained_public;
+  return base.do_find_public_subobj (boff, subtype, objptr, subptr);
+}
 
-      void *p;
+// catch helper for multiple or non-public inheritance types. See
+// __user_type_info::do_upcast for semantics.
+bool __class_type_info::
+do_upcast (sub_kind access_path,
+           const type_info &target, void *objptr,
+           upcast_result &__restrict result) const
+{
+  if (*this == target)
+    {
+      result.target_obj = objptr;
+      result.base_type = nonvirtual_base_type;
+      result.whole2target = access_path;
+      return contained_nonpublic_p (access_path);
+    }
+  
+  for (size_t i = n_bases; i--;)
+    {
+      upcast_result result2;
+      void *p = objptr;
+      sub_kind sub_access = access_path;
+      if (p)
+        p = (char *)p + base_list[i].offset;
+      if (base_list[i].is_virtual)
+        {
+          if (p)
+            p = *(void **)p;
+	  sub_access = sub_kind (sub_access | contained_virtual_mask);
+        }
+      if (base_list[i].access != PUBLIC)
+        sub_access = sub_kind (sub_access & ~contained_public_mask);
+      if (base_list[i].base->do_upcast (sub_access, target, p, result2))
+        return true; // must fail
+      if (result2.base_type)
+        {
+          if (result2.base_type == nonvirtual_base_type
+              && base_list[i].is_virtual)
+            result2.base_type = base_list[i].base;
+          if (!result.base_type)
+            result = result2;
+          else if (result.target_obj != result2.target_obj)
+            {
+              // Found an ambiguity.
+	      result.target_obj = NULL;
+	      result.whole2target = contained_ambig;
+	      return true;
+            }
+          else if (result.target_obj)
+            {
+              // Ok, found real object via a virtual path.
+              result.whole2target
+                  = sub_kind (result.whole2target | result2.whole2target);
+            }
+          else
+            {
+              // Dealing with a null pointer, need to check vbase
+              // containing each of the two choices.
+              if (result2.base_type == nonvirtual_base_type
+                  || result.base_type == nonvirtual_base_type
+                  || !(*result2.base_type == *result.base_type))
+                {
+                  // Already ambiguous, not virtual or via different virtuals.
+                  // Cannot match.
+                  result.whole2target = contained_ambig;
+                  return true;
+                }
+            }
+        }
+    }
+  return false;
+}
 
-      if (objptr)
-	{
-	  p = (char *)objptr + base_list[i].offset;
-	  if (base_list[i].is_virtual)
-	    p = *(void **)p;
-	}
-      else
-	/* Preserve null pointer.  */
-	p = objptr;
-
-      if (base_list[i].base->dcast (desired, is_public, p, &p, sub, subptr))
-	{
-	  if (! match_found)
-	    {
-	      match_found = 1;
-	      match = p;
-	    }
-	  else if (match != p)
-	    {
-	      if (sub)
-		{
-		  // Perhaps we're downcasting from *sub to desired; see if
-		  // subptr is a subobject of exactly one of {match_found,p}.
-
-		  const __user_type_info &d =
-		    static_cast <const __user_type_info &> (desired);
-
-		  void *os;
-		  d.dcast (*sub, 1, match, &os);
-		  void *ns;
-		  d.dcast (*sub, 1, p, &ns);
-
-		  if (os == ns)
-		    // Both have the same subobject, so we can't disambiguate;
-		    // i.e. subptr is a virtual base.
-		    return 0;
-		  else if (os == subptr)
-		    continue;
-		  else if (ns == subptr)
-		    {
-		      match = p;
-		      continue;
-		    }
-		}
-	      else
-		// We're not downcasting, so we can't disambiguate.
-		return 0;
-	    }
+// dynamic cast helper for non-public or multiple inheritance types. See
+// __user_type_info::do_dyncast for overall semantics.
+// This is a big hairy function. Although the run-time behaviour of
+// dynamic_cast is simple to describe, it gives rise to some non-obvious
+// behaviour. We also desire to determine as early as possible any definite
+// answer we can get. Because it is unknown what the run-time ratio of
+// succeeding to failing dynamic casts is, we do not know in which direction
+// to bias any optimizations. To that end we make no particular effort towards
+// early fail answers or early success answers. Instead we try to minimize
+// work by filling in things lazily (when we know we need the information),
+// and opportunisticly take early success or failure results.
+bool __class_type_info::
+do_dyncast (int boff, sub_kind access_path,
+            const type_info &target, void *objptr,
+            const type_info &subtype, void *subptr,
+            dyncast_result &__restrict result) const
+{
+  if (objptr == subptr && *this == subtype)
+    {
+      // The subobject we started from. Indicate how we are accessible from
+      // the most derived object.
+      result.whole2sub = access_path;
+      return false;
+    }
+  if (*this == target)
+    {
+      result.target_obj = objptr;
+      result.whole2target = access_path;
+      if (boff >= 0)
+        result.target2sub = ((char *)subptr - (char *)objptr) == boff
+              ? contained_public : not_contained;
+      else if (boff == -3)
+        result.target2sub = not_contained;
+      return false;
+    }
+  bool result_ambig = false;
+  for (size_t i = n_bases; i--;)
+    {
+      dyncast_result result2;
+      void *p = (char *)objptr + base_list[i].offset;
+      sub_kind sub_access = access_path;
+      if (base_list[i].is_virtual)
+        {
+	  p = *(void **)p;
+	  sub_access = sub_kind (sub_access | contained_virtual_mask);
 	}
+      if (base_list[i].access != PUBLIC)
+        sub_access = sub_kind (sub_access & ~contained_public_mask);
+      
+      bool result2_ambig
+          = base_list[i].base->do_dyncast (boff, sub_access,
+                                           target, p, subtype, subptr, result2);
+      result.whole2sub = sub_kind (result.whole2sub | result2.whole2sub);
+      if (result2.target2sub == contained_public
+          || result2.target2sub == contained_ambig)
+        {
+          result.target_obj = result2.target_obj;
+          result.whole2target = result2.whole2target;
+          result.target2sub = result2.target2sub;
+          // Found a downcast which can't be bettered or an ambiguous downcast
+          // which can't be disambiguated
+          return result2_ambig;
+        }
+      
+      if (!result_ambig && !result.target_obj)
+        {
+          // Not found anything yet.
+          result.target_obj = result2.target_obj;
+          result.whole2target = result2.whole2target;
+          result_ambig = result2_ambig;
+        }
+      else if (result.target_obj && result.target_obj == result2.target_obj)
+        {
+          // Found at same address, must be via virtual.  Pick the most
+          // accessible path.
+          result.whole2target =
+              sub_kind (result.whole2target | result2.whole2target);
+        }
+      else if ((result.target_obj && result2.target_obj)
+               || (result_ambig && result2.target_obj)
+               || (result2_ambig && result.target_obj))
+        {
+          // Found two different TARGET bases, or a valid one and a set of
+          // ambiguous ones, must disambiguate. See whether SUBOBJ is
+          // contained publicly within one of the non-ambiguous choices.
+          // If it is in only one, then that's the choice. If it is in
+          // both, then we're ambiguous and fail. If it is in neither,
+          // we're ambiguous, but don't yet fail as we might later find a
+          // third base which does contain SUBPTR.
+        
+          sub_kind new_sub_kind = result2.target2sub;
+          sub_kind old_sub_kind = result.target2sub;
+          
+          if (contained_nonvirtual_p (result.whole2sub))
+            {
+              // We already found SUBOBJ as a non-virtual base of most
+              // derived. Therefore if it is in either choice, it can only be
+              // in one of them, and we will already know.
+              if (old_sub_kind == unknown)
+                old_sub_kind = not_contained;
+              if (new_sub_kind == unknown)
+                new_sub_kind = not_contained;
+            }
+          else
+            {
+              const __user_type_info &t =
+                  static_cast <const __user_type_info &> (target);
+              
+              if (old_sub_kind >= not_contained)
+                ;// already calculated
+              else if (contained_nonvirtual_p (new_sub_kind))
+                // Already found non-virtually inside the other choice,
+                // cannot be in this.
+                old_sub_kind = not_contained;
+              else
+                old_sub_kind = t.find_public_subobj (boff, subtype,
+                                                     result.target_obj, subptr);
+          
+              if (new_sub_kind >= not_contained)
+                ;// already calculated
+              else if (contained_nonvirtual_p (old_sub_kind))
+                // Already found non-virtually inside the other choice,
+                // cannot be in this.
+                new_sub_kind = not_contained;
+              else
+                new_sub_kind = t.find_public_subobj (boff, subtype,
+                                                     result2.target_obj, subptr);
+            }
+          
+          // Neither sub_kind can be contained_ambig -- we bail out early
+          // when we find those.
+          if (contained_p (sub_kind (new_sub_kind ^ old_sub_kind)))
+            {
+              // Only on one choice, not ambiguous.
+              if (contained_p (new_sub_kind))
+                {
+                  // Only in new.
+                  result.target_obj = result2.target_obj;
+                  result.whole2target = result2.whole2target;
+                  result_ambig = false;
+                  old_sub_kind = new_sub_kind;
+                }
+              result.target2sub = old_sub_kind;
+              if (result.target2sub == contained_public)
+                return false; // Can't be an ambiguating downcast for later discovery.
+            }
+          else if (contained_p (sub_kind (new_sub_kind & old_sub_kind)))
+            {
+              // In both.
+              result.target_obj = NULL;
+              result.target2sub = contained_ambig;
+              return true;  // Fail.
+            }
+          else
+            {
+              // In neither publicly, ambiguous for the moment, but keep
+              // looking. It is possible that it was private in one or
+              // both and therefore we should fail, but that's just tough.
+              result.target_obj = NULL;
+              result.target2sub = not_contained;
+              result_ambig = true;
+            }
+        }
+      
+      if (result.whole2sub == contained_private)
+        // We found SUBOBJ as a private non-virtual base, therefore all
+        // cross casts will fail. We have already found a down cast, if
+        // there is one.
+        return result_ambig;
     }
 
-  *valp = match;
-  return match_found;
+  return result_ambig;
+}
+
+// find_public_subobj helper for non-public or multiple inheritance types. See
+// __user_type_info::do_find_public_subobj for semantics. We make use of BOFF
+// to prune the base class walk.
+__user_type_info::sub_kind __class_type_info::
+do_find_public_subobj (int boff, const type_info &subtype, void *objptr, void *subptr) const
+{
+  if (objptr == subptr && subtype == *this)
+    return contained_public;
+  
+  for (size_t i = n_bases; i--;)
+    {
+      if (base_list[i].access != PUBLIC)
+        continue; // Not public, can't be here.
+      void *p = (char *)objptr + base_list[i].offset;
+      if (base_list[i].is_virtual)
+        {
+          if (boff == -1)
+            continue; // Not a virtual base, so can't be here.
+          p = *(void **)p;
+        }
+
+      sub_kind base_kind = base_list[i].base->do_find_public_subobj
+                              (boff, subtype, p, subptr);
+      if (contained_p (base_kind))
+        {
+          if (base_list[i].is_virtual)
+            base_kind = sub_kind (base_kind | contained_virtual_mask);
+          return base_kind;
+        }
+    }
+  
+  return not_contained;
 }