Intrinsics for N2965: Type traits and base classes

[Mike Spertus <mike_spertus at symantec dot com>]

This patch consists intrinsics to properly create the bases and 
direct_bases of a class in the correct order (including multiple nested 
ambiguous virtual and non-virtual classes) for N2965 
(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2009/n2965.html). 
This allows you to create type traits for giving the base classes of the 
class:

template<typename _Tp>
struct bases
{
  typedef tuple<__bases(_Tp)...> type;
};

I didn't modify the standard library to include the above type trait in 
the patch because it is not yet clear what type it should return (e.g., 
a tuple, a "typelist," something satisfying the requirements of a 
boost::mpl sequence, or a generalization of parameter packs). I have 
(cursorily) tested it with the above type trait and the corresponding 
direct_bases trait.

Thanks to Jason Merrill and Benjamin Kosnik for all their help,

Mike

Index: gcc/c-family/c-common.c
===================================================================
--- gcc/c-family/c-common.c    (revision 178892)
+++ gcc/c-family/c-common.c    (working copy)
@@ -423,6 +423,7 @@
   { "__asm__",        RID_ASM,    0 },
   { "__attribute",    RID_ATTRIBUTE,    0 },
   { "__attribute__",    RID_ATTRIBUTE,    0 },
+  { "__bases",          RID_BASES, D_CXXONLY },
   { "__builtin_choose_expr", RID_CHOOSE_EXPR, D_CONLY },
   { "__builtin_complex", RID_BUILTIN_COMPLEX, D_CONLY },
   { "__builtin_offsetof", RID_OFFSETOF, 0 },
@@ -433,6 +434,7 @@
   { "__const",        RID_CONST,    0 },
   { "__const__",    RID_CONST,    0 },
   { "__decltype",       RID_DECLTYPE,   D_CXXONLY },
+  { "__direct_bases",   RID_DIRECT_BASES, D_CXXONLY },
   { "__extension__",    RID_EXTENSION,    0 },
   { "__func__",        RID_C99_FUNCTION_NAME, 0 },
   { "__has_nothrow_assign", RID_HAS_NOTHROW_ASSIGN, D_CXXONLY },
Index: gcc/c-family/c-common.h
===================================================================
--- gcc/c-family/c-common.h    (revision 178892)
+++ gcc/c-family/c-common.h    (working copy)
@@ -139,7 +139,8 @@
   RID_IS_LITERAL_TYPE,         RID_IS_POD,
   RID_IS_POLYMORPHIC,          RID_IS_STD_LAYOUT,
   RID_IS_TRIVIAL,              RID_IS_UNION,
-  RID_UNDERLYING_TYPE,
+  RID_UNDERLYING_TYPE,         RID_BASES,
+  RID_DIRECT_BASES,

   /* C++0x */
   RID_CONSTEXPR, RID_DECLTYPE, RID_NOEXCEPT, RID_NULLPTR, 
RID_STATIC_ASSERT,
Index: gcc/tree.h
===================================================================
--- gcc/tree.h    (revision 178892)
+++ gcc/tree.h    (working copy)
@@ -21,7 +21,6 @@

 #ifndef GCC_TREE_H
 #define GCC_TREE_H
-
 #include "hashtab.h"
 #include "machmode.h"
 #include "input.h"
Index: gcc/cp/pt.c
===================================================================
--- gcc/cp/pt.c    (revision 178892)
+++ gcc/cp/pt.c    (working copy)
@@ -2976,6 +2976,10 @@
         }
       break;

+    case BASES:
+    case DIRECT_BASES:
+      parameter_pack_p = true;
+      break;
     default:
       /* Not a parameter pack.  */
       break;
@@ -9123,6 +9127,16 @@
       tree arg_pack = NULL_TREE;
       tree orig_arg = NULL_TREE;

+      if (TREE_CODE (parm_pack) == BASES)
+        {
+          return calculate_bases(tsubst_expr(BASES_TYPE(parm_pack),
+                                 args, complain, in_decl, false));
+        }
+      if (TREE_CODE (parm_pack) == DIRECT_BASES)
+        {
+          return 
calculate_direct_bases(tsubst_expr(DIRECT_BASES_TYPE(parm_pack),
+                                        args, complain, in_decl, false));
+        }
       if (TREE_CODE (parm_pack) == PARM_DECL)
     {
       if (!cp_unevaluated_operand)
Index: gcc/cp/semantics.c
===================================================================
--- gcc/cp/semantics.c    (revision 178892)
+++ gcc/cp/semantics.c    (working copy)
@@ -3407,6 +3407,155 @@
   return underlying_type;
 }

+/* Implement the __direct_bases keyword: Return the direct base classes
+   of type */
+tree
+calculate_direct_bases (tree type)
+{
+  VEC(tree, gc) *vector;
+  tree bases_vec = NULL_TREE;
+  VEC(tree, none) *base_binfos;
+  tree binfo;
+  unsigned i;
+
+  complete_type (type);
+
+  if (!NON_UNION_CLASS_TYPE_P (type))
+    {
+      return bases_vec;
+    }
+  /* Virtual bases are initialized first */
+  vector = VEC_copy (tree, gc, CLASSTYPE_VBASECLASSES (type));
+
+  base_binfos = BINFO_BASE_BINFOS(TYPE_BINFO (complete_type 
(TYPE_MAIN_VARIANT (type))));
+  for (i = 0; VEC_iterate (tree, base_binfos, i, binfo); i++)
+    {
+      /* Now the non-virtual bases */
+      if (!BINFO_VIRTUAL_P (binfo))
+    {
+      VEC_safe_push (tree, gc, vector, binfo);
+    }
+    }
+
+  bases_vec = make_tree_vec (VEC_length (tree, vector));
+
+  for (i = 0; i < VEC_length (tree, vector); ++i)
+    {
+      TREE_VEC_ELT (bases_vec, i) = BINFO_TYPE (VEC_index (tree, 
vector, i));
+    }
+  return bases_vec;
+}
+
+tree
+finish_direct_bases (tree type)
+{
+  tree direct_bases = NULL_TREE;
+
+  if (!processing_template_decl)
+    {
+      /* Parameter packs can only be used in templates */
+      error ("__direct_bases only valid in template declaration");
+      return error_mark_node;
+    }
+
+  direct_bases = cxx_make_type (DIRECT_BASES);
+  DIRECT_BASES_TYPE (direct_bases) = type;
+  SET_TYPE_STRUCTURAL_EQUALITY (direct_bases);
+
+  return direct_bases;
+
+}
+
+/* Implement the __bases keyword: Return the base classes
+   of type */
+
+/* Find morally non-virtual base classes by walking binfo hierarchy */
+/* Virtual base classes are handled separately in finish_bases */
+
+static tree
+dfs_calculate_bases_pre (tree binfo, void *data_)
+{
+  (void)data_;
+  /* Don't walk bases of virtual bases */
+  return BINFO_VIRTUAL_P (binfo) ? dfs_skip_bases : NULL_TREE;
+}
+
+static tree
+dfs_calculate_bases_post (tree binfo, void *data_)
+{
+  VEC(tree, gc) **data = (VEC(tree, gc) **) data_;
+  if (!BINFO_VIRTUAL_P (binfo))
+    {
+      VEC_safe_push (tree, gc, *data, BINFO_TYPE (binfo));
+    }
+  return NULL_TREE;
+}
+
+static VEC(tree, gc) *
+calculate_bases_helper (tree type)
+{
+  VEC(tree, gc) *vector = make_tree_vector();
+  unsigned i;
+  VEC(tree,gc) *vbases;
+  tree binfo;
+
+  /* First go through virtual base classes */
+  for (vbases = CLASSTYPE_VBASECLASSES (type), i = 0;
+       VEC_iterate (tree, vbases, i, binfo); i++)
+    {
+      VEC_safe_splice (tree, gc, vector, calculate_bases_helper 
(BINFO_TYPE (binfo)));
+    }
+
+  /* Now add non-virtual base classes in order of construction */
+  dfs_walk_all (TYPE_BINFO (complete_type (TYPE_MAIN_VARIANT (type))),
+                dfs_calculate_bases_pre, dfs_calculate_bases_post, 
&vector);
+  return vector;
+}
+
+tree
+calculate_bases (tree type)
+{
+  VEC(tree, gc) *vector;
+  tree bases_vec = NULL_TREE;
+  unsigned i;
+
+  complete_type (type);
+
+  if (!NON_UNION_CLASS_TYPE_P (type))
+    {
+      return bases_vec;
+    }
+
+  vector = calculate_bases_helper (type);
+  /* Last element is entire class, so don't copy */
+  bases_vec = make_tree_vec (VEC_length (tree, vector) - 1);
+
+  for (i = 0; i < VEC_length (tree, vector) - 1; ++i)
+    {
+      TREE_VEC_ELT (bases_vec, i) = VEC_index (tree, vector, i);
+    }
+  return bases_vec;
+}
+
+tree
+finish_bases (tree type)
+{
+  tree bases = NULL_TREE;
+
+  if (!processing_template_decl)
+    {
+      /* Parameter packs can only be used in templates */
+      error ("Parameter pack __bases only valid in template declaration");
+      return error_mark_node;
+    }
+
+  bases = cxx_make_type (BASES);
+  BASES_TYPE (bases) = type;
+  SET_TYPE_STRUCTURAL_EQUALITY (bases);
+
+  return bases;
+}
+
 /* Perform C++-specific checks for __builtin_offsetof before calling
    fold_offsetof.  */

Index: gcc/cp/parser.c
===================================================================
--- gcc/cp/parser.c    (revision 178892)
+++ gcc/cp/parser.c    (working copy)
@@ -7295,6 +7295,12 @@
     case RID_UNDERLYING_TYPE:
       kind = CPTK_UNDERLYING_TYPE;
       break;
+    case RID_BASES:
+      kind = CPTK_BASES;
+      break;
+    case RID_DIRECT_BASES:
+      kind = CPTK_DIRECT_BASES;
+      break;
     default:
       gcc_unreachable ();
     }
@@ -7339,9 +7345,17 @@

   /* Complete the trait expression, which may mean either processing
      the trait expr now or saving it for template instantiation.  */
-  return kind != CPTK_UNDERLYING_TYPE
-    ? finish_trait_expr (kind, type1, type2)
-    : finish_underlying_type (type1);
+  switch(kind)
+    {
+    case CPTK_UNDERLYING_TYPE:
+      return finish_underlying_type (type1);
+    case CPTK_BASES:
+      return finish_bases (type1);
+    case CPTK_DIRECT_BASES:
+      return finish_direct_bases (type1);
+    default:
+      return finish_trait_expr (kind, type1, type2);
+    }
 }

 /* Lambdas that appear in variable initializer or default argument scope
@@ -12010,6 +12024,7 @@
   parser->integral_constant_expression_p = false;
   saved_non_ice_p = parser->non_integral_constant_expression_p;
   parser->non_integral_constant_expression_p = false;
+
   /* Parse the arguments.  */
   do
     {
@@ -12826,7 +12841,9 @@
       return type;

     case RID_UNDERLYING_TYPE:
-      type = cp_parser_trait_expr (parser, RID_UNDERLYING_TYPE);
+    case RID_BASES:
+    case RID_DIRECT_BASES:
+      type = cp_parser_trait_expr (parser, token->keyword);

       if (decl_specs)
     cp_parser_set_decl_spec_type (decl_specs, type,
@@ -20534,7 +20551,7 @@
 }

 /* Parse a template-argument-list, as well as the trailing ">" (but
-   not the opening ">").  See cp_parser_template_argument_list for the
+   not the opening "<").  See cp_parser_template_argument_list for the
    return value.  */

 static tree
Index: gcc/cp/cp-tree.def
===================================================================
--- gcc/cp/cp-tree.def    (revision 178892)
+++ gcc/cp/cp-tree.def    (working copy)
@@ -461,6 +461,14 @@
    UNDERLYING_TYPE_TYPE is the type in question.  */
 DEFTREECODE (UNDERLYING_TYPE, "underlying_type", tcc_type, 0)

+/* A type designated by `__bases (type)'.
+   BASES_TYPE is the type in question.  */
+DEFTREECODE (BASES, "bases", tcc_type, 0)
+
+/* A type designated by `__direct_bases (type)'.
+   DIRECT_BASES_TYPE is the type in question.  */
+DEFTREECODE (DIRECT_BASES, "direct_bases", tcc_type, 0)
+
 /* Used to represent the template information stored by template
    specializations.
    The accessors are:
Index: gcc/cp/cp-tree.h
===================================================================
--- gcc/cp/cp-tree.h    (revision 178892)
+++ gcc/cp/cp-tree.h    (working copy)
@@ -578,7 +578,9 @@
   CPTK_IS_STD_LAYOUT,
   CPTK_IS_TRIVIAL,
   CPTK_IS_UNION,
-  CPTK_UNDERLYING_TYPE
+  CPTK_UNDERLYING_TYPE,
+  CPTK_BASES,
+  CPTK_DIRECT_BASES
 } cp_trait_kind;

 /* The types that we are processing.  */
@@ -3416,6 +3418,14 @@
 #define UNDERLYING_TYPE_TYPE(NODE) \
   (TYPE_VALUES_RAW (UNDERLYING_TYPE_CHECK (NODE)))

+/* The type in question for BASES.  */
+#define BASES_TYPE(NODE) \
+  (TYPE_VALUES_RAW (BASES_CHECK (NODE)))
+
+/* The type in question for DIRECT_BASES.  */
+#define DIRECT_BASES_TYPE(NODE) \
+  (TYPE_VALUES_RAW (DIRECT_BASES_CHECK (NODE)))
+
 /* The expression in question for a DECLTYPE_TYPE.  */
 #define DECLTYPE_TYPE_EXPR(NODE) (TYPE_VALUES_RAW (DECLTYPE_TYPE_CHECK 
(NODE)))

@@ -5430,6 +5440,10 @@
                                                  location_t);
 extern tree finish_typeof            (tree);
 extern tree finish_underlying_type            (tree);
+extern tree calculate_bases                (tree);
+extern tree finish_bases                (tree);
+extern tree calculate_direct_bases            (tree);
+extern tree finish_direct_bases                (tree);
 extern tree finish_offsetof            (tree);
 extern void finish_decl_cleanup            (tree, tree);
 extern void finish_eh_cleanup            (tree);