2017-09-12  Nathan Sidwell  <nathan@acm.org>

	Kill CLASSTYPE_SORTED_FIELDS.
	* cp-tree.h (struct lang_type): Lose sorted_fields member.
	(CLASSTYPE_SORTED_FIELDS): Delete.
	* name-lookup.h (set_class_bindings): Add EXTRA arg.
	* name-lookup.c (fields_linear_search): New, broken out of ...
	(lookup_field_1): ... here.  Delete remainder of function.
	(get_class_binding_direct): Reimplement without sorted_fields.
	(get_class_binding): Rename TYPE arg to KLASS, for consistency.
	(get_method_slot): Call set_class_binding when creating method_vec
	on complete type.
	(method_name_cmp): Order identically named slots.
	(sorted_fields_type_new): Delete.
	(field_vc_append_class_fields): Rename to ...
	(method_vec_append_class_fields): ... here.  Adjust.
	(field_vec_append_enum_values): Renme to ...
	(method_vec_append_enum_values): ... here. Adjust.
	(method_vec_dedup): New.
	(set_class_bindings): Reimplement.
	(insert_late_enum_def_bindings): Reimplement.

Index: cp-tree.h
===================================================================
--- cp-tree.h	(revision 252002)
+++ cp-tree.h	(working copy)
@@ -2008,10 +2008,6 @@ struct GTY(()) lang_type {
      as a list of adopted protocols or a pointer to a corresponding
      @interface.  See objc/objc-act.h for details.  */
   tree objc_info;
-  /* sorted_fields is sorted based on a pointer, so we need to be able
-     to resort it if pointers get rearranged.  */
-  struct sorted_fields_type * GTY ((reorder ("resort_sorted_fields")))
-    sorted_fields;
   /* FIXME reuse another field?  */
   tree lambda_expr;
 };
@@ -3229,11 +3225,6 @@ extern void decl_shadowed_for_var_insert
    && TREE_CODE (TYPE_NAME (NODE)) == TYPE_DECL	\
    && TYPE_DECL_ALIAS_P (TYPE_NAME (NODE)))
 
-/* For a class type: if this structure has many fields, we'll sort them
-   and put them into a TREE_VEC.  */
-#define CLASSTYPE_SORTED_FIELDS(NODE) \
-  (LANG_TYPE_CLASS_CHECK (NODE)->sorted_fields)
-
 /* If non-NULL for a VAR_DECL, FUNCTION_DECL, TYPE_DECL or
    TEMPLATE_DECL, the entity is either a template specialization (if
    DECL_USE_TEMPLATE is nonzero) or the abstract instance of the
Index: name-lookup.c
===================================================================
--- name-lookup.c	(revision 252004)
+++ name-lookup.c	(working copy)
@@ -1156,103 +1156,54 @@ method_vec_linear_search (vec<tree, va_g
   return NULL_TREE;
 }
 
-/* Do a 1-level search for NAME as a member of TYPE.  The caller must
-   figure out whether it can access this field.  (Since it is only one
-   level, this is reasonable.)  */
+/* Linear search of (partially ordered) fields of KLASS for NAME.  */
 
 static tree
-lookup_field_1 (tree type, tree name, bool want_type)
+fields_linear_search (tree klass, tree name, bool want_type)
 {
-  tree field;
-
-  gcc_assert (identifier_p (name) && RECORD_OR_UNION_TYPE_P (type));
-
-  if (CLASSTYPE_SORTED_FIELDS (type))
+  for (tree fields = TYPE_FIELDS (klass); fields; fields = DECL_CHAIN (fields))
     {
-      tree *fields = &CLASSTYPE_SORTED_FIELDS (type)->elts[0];
-      int lo = 0, hi = CLASSTYPE_SORTED_FIELDS (type)->len;
-      int i;
+      tree decl = fields;
 
-      while (lo < hi)
+      if (!want_type
+	  && TREE_CODE (decl) == FIELD_DECL
+	  && ANON_AGGR_TYPE_P (TREE_TYPE (decl)))
 	{
-	  i = (lo + hi) / 2;
-
-	  if (DECL_NAME (fields[i]) > name)
-	    hi = i;
-	  else if (DECL_NAME (fields[i]) < name)
-	    lo = i + 1;
+	  tree anon = TREE_TYPE (decl);
+	  gcc_assert (COMPLETE_TYPE_P (anon));
+	  tree temp;
+	  
+	  if (vec<tree, va_gc> *method_vec = CLASSTYPE_METHOD_VEC (anon))
+	    temp = method_vec_linear_search (method_vec, name);
 	  else
-	    {
-	      field = NULL_TREE;
-
-	      /* We might have a nested class and a field with the
-		 same name; we sorted them appropriately via
-		 field_decl_cmp, so just look for the first or last
-		 field with this name.  */
-	      if (want_type)
-		{
-		  do
-		    field = fields[i--];
-		  while (i >= lo && DECL_NAME (fields[i]) == name);
-		  if (!DECL_DECLARES_TYPE_P (field))
-		    field = NULL_TREE;
-		}
-	      else
-		{
-		  do
-		    field = fields[i++];
-		  while (i < hi && DECL_NAME (fields[i]) == name);
-		}
-
-	      if (field)
-	      	{
-	      	  field = strip_using_decl (field);
-	      	  if (is_overloaded_fn (field))
-	      	    field = NULL_TREE;
-	      	}
+	    temp = fields_linear_search (anon, name, want_type);
 
-	      return field;
+	  if (temp)
+	    {
+	      /* Anon members can only contain fields.  */
+	      gcc_assert (!STAT_HACK_P (temp) && !DECL_DECLARES_TYPE_P (temp));
+	      return temp;
 	    }
 	}
-      return NULL_TREE;
-    }
 
-  field = TYPE_FIELDS (type);
-
-  for (field = TYPE_FIELDS (type); field; field = DECL_CHAIN (field))
-    {
-      tree decl = field;
-
-      if (DECL_DECLARES_FUNCTION_P (decl))
-	/* Functions are kep separately, at the moment.  */
+      if (DECL_NAME (decl) != name)
 	continue;
-
-      gcc_assert (DECL_P (field));
-      if (DECL_NAME (field) == NULL_TREE
-	  && ANON_AGGR_TYPE_P (TREE_TYPE (field)))
-	{
-	  tree temp = lookup_field_1 (TREE_TYPE (field), name, want_type);
-	  if (temp)
-	    return temp;
-	}
-
-      if (TREE_CODE (decl) == USING_DECL
-	  && DECL_NAME (decl) == name)
+      
+      if (TREE_CODE (decl) == USING_DECL)
 	{
 	  decl = strip_using_decl (decl);
 	  if (is_overloaded_fn (decl))
 	    continue;
 	}
 
-      if (DECL_NAME (decl) == name
-	  && (!want_type || DECL_DECLARES_TYPE_P (decl)))
+      if (DECL_DECLARES_FUNCTION_P (decl))
+	/* Functions are found separately.  */
+	continue;
+
+      if (!want_type || DECL_DECLARES_TYPE_P (decl))
 	return decl;
     }
 
-  /* We used to special-case vptr_identifier.  Make sure it's not
-     special any more.  */
-  gcc_assert (name != vptr_identifier || !TYPE_VFIELD (type));
-
   return NULL_TREE;
 }
 
@@ -1273,25 +1224,49 @@ get_class_binding_direct (tree klass, tr
   bool conv_op = IDENTIFIER_CONV_OP_P (name);
   tree lookup = conv_op ? conv_op_identifier : name;
   tree val = NULL_TREE;
+  vec<tree, va_gc> *method_vec = CLASSTYPE_METHOD_VEC (klass);
 
-  if (type_or_fns > 0)
-    /* User wants type.  Don't look in method_vec.  */;
-  else if (vec<tree, va_gc> *method_vec = CLASSTYPE_METHOD_VEC (klass))
+  if (COMPLETE_TYPE_P (klass) && method_vec)
     {
-      if (COMPLETE_TYPE_P (klass))
-	val = method_vec_binary_search (method_vec, lookup);
-      else
-	val = method_vec_linear_search (method_vec, lookup);
+      val = method_vec_binary_search (method_vec, lookup);
+      if (!val)
+	;
+      else if (type_or_fns > 0)
+	{
+	  if (STAT_HACK_P (val))
+	    val = STAT_TYPE (val);
+	  else if (!DECL_DECLARES_TYPE_P (val))
+	    val = NULL_TREE;
+	}
+      else if (STAT_HACK_P (val))
+	val = STAT_DECL (val);
+
+      if (val && TREE_CODE (val) == OVERLOAD
+	  && TREE_CODE (OVL_FUNCTION (val)) == USING_DECL)
+	{
+	  /* An overload with a dependent USING_DECL.  Does the caller
+	     want the USING_DECL or the functions?  */
+	  if (type_or_fns < 0)
+	    val = OVL_CHAIN (val);
+	  else
+	    val = OVL_FUNCTION (val);  
+	}
     }
+  else
+    {
+      if (method_vec && type_or_fns <= 0)
+	val = method_vec_linear_search (method_vec, lookup);
 
-  if (type_or_fns < 0)
-    /* User wants functions.  Don't look for a field. */;
-  else if (!val || (TREE_CODE (val) == OVERLOAD && OVL_USING_P (val)))
-    /* Dependent using declarations are a 'field', make sure we
-       return that even if we saw an overload already.  */
-    if (tree field_val = lookup_field_1 (klass, lookup, type_or_fns > 0))
-      if (!val || TREE_CODE (field_val) == USING_DECL)
-	val = field_val;
+      if (type_or_fns < 0)
+	/* Don't bother looking for field.  We don't want it.  */;
+      else if (!val || (TREE_CODE (val) == OVERLOAD && OVL_USING_P (val)))
+	/* Dependent using declarations are a 'field', make sure we
+	   return that even if we saw an overload already.  */
+	if (tree field_val = fields_linear_search (klass, lookup,
+						   type_or_fns > 0))
+	  if (!val || TREE_CODE (field_val) == USING_DECL)
+	    val = field_val;
+    }
 
   /* Extract the conversion operators asked for, unless the general
      conversion operator was requested.   */
@@ -1359,6 +1334,15 @@ get_method_slot (tree klass, tree name)
     {
       vec_alloc (method_vec, 8);
       CLASSTYPE_METHOD_VEC (klass) = method_vec;
+      if (complete_p)
+	{
+	  /* If the class is complete but had no method_vec, we need
+	     to add the TYPE_FIELDS into it.  We're also most likely
+	     to be adding ctors & dtors, so ask for 6 spare slots (the
+	     abstract cdtors and their clones).  */
+	  set_class_bindings (klass, 6);
+	  method_vec = CLASSTYPE_METHOD_VEC (klass);
+	}
     }
 
   if (IDENTIFIER_CONV_OP_P (name))
@@ -1372,6 +1356,12 @@ get_method_slot (tree klass, tree name)
 
       if (fn_name == name)
 	{
+	  /* If we found an existing slot, it must be a function set.
+	     Even with insertion after completion, because those only
+	     happen with artificial fns that have unspellable names.
+	     This means we do not have to deal with the stat hack
+	     either.  */
+	  gcc_checking_assert (OVL_P (*slot));
 	  if (name == conv_op_identifier)
 	    {
 	      gcc_checking_assert (OVL_FUNCTION (*slot) == conv_op_marker);
@@ -1413,7 +1403,9 @@ get_method_slot (tree klass, tree name)
 }
 
 /* Comparison function to compare two TYPE_METHOD_VEC entries by
-   name.  */
+   name.  Because we can have duplicates during insertion of
+   TYPE_FIELDS, we do extra checking so deduping doesn't have to deal
+   with so many cases.  */
 
 static int
 method_name_cmp (const void *a_p, const void *b_p)
@@ -1423,8 +1415,48 @@ method_name_cmp (const void *a_p, const
   tree name_a = DECL_NAME (TREE_CODE (a) == OVERLOAD ? OVL_FUNCTION (a) : a);
   tree name_b = DECL_NAME (TREE_CODE (b) == OVERLOAD ? OVL_FUNCTION (b) : b);
 
-  gcc_checking_assert (name_a && name_b && name_a != name_b);
-  return name_a < name_b ? -1 : +1;
+  gcc_checking_assert (name_a && name_b);
+  if (name_a != name_b)
+    return name_a < name_b ? -1 : +1;
+
+  if (name_a == conv_op_identifier)
+    {
+      /* Strip the conv-op markers. */
+      gcc_checking_assert (OVL_FUNCTION (a) == conv_op_marker
+			   && OVL_FUNCTION (b) == conv_op_marker);
+      a = OVL_CHAIN (a);
+      b = OVL_CHAIN (b);
+    }
+
+  if (TREE_CODE (a) == OVERLOAD)
+    a = OVL_FUNCTION (a);
+  if (TREE_CODE (b) == OVERLOAD)
+    b = OVL_FUNCTION (b);
+
+  /* We're in STAT_HACK or USING_DECL territory (or possibly error-land). */
+  if (TREE_CODE (a) == TREE_CODE (b))
+    /* We can get two TYPE_DECLs or two USING_DECLs.  Place in source
+       order.  */
+    return DECL_SOURCE_LOCATION (a) < DECL_SOURCE_LOCATION (b) ? -1 : +1;
+
+  /* If one of them is a TYPE_DECL, it loses.  */
+  if (TREE_CODE (a) == TYPE_DECL)
+    return +1;
+  else if (TREE_CODE (b) == TYPE_DECL)
+    return -1;
+
+  /* If one of them is a USING_DECL, it loses.  */
+  if (TREE_CODE (a) == USING_DECL)
+    return +1;
+  else if (TREE_CODE (b) == USING_DECL)
+    return -1;
+
+  /* There are no other cases, as duplicate detection should have
+     kicked in earlier.  However, some erroneous cases get though.
+     Order by source location.  We should really prevent this
+     happening.  */
+  gcc_assert (errorcount);
+  return DECL_SOURCE_LOCATION (a) < DECL_SOURCE_LOCATION (b) ? -1 : +1;
 }
 
 static struct {
@@ -1467,20 +1499,6 @@ resort_type_method_vec (void *obj, void
     }
 }
 
-/* Allocate and return an instance of struct sorted_fields_type with
-   N fields.  */
-
-static struct sorted_fields_type *
-sorted_fields_type_new (int n)
-{
-  struct sorted_fields_type *sft;
-  sft = (sorted_fields_type *) ggc_internal_alloc (sizeof (sorted_fields_type)
-				      + n * sizeof (tree));
-  sft->len = n;
-
-  return sft;
-}
-
 /* Recursively count the number of fields in KLASS, including anonymous
    union members.  */
 
@@ -1501,58 +1519,176 @@ count_class_fields (tree klass)
   return n_fields;
 }
 
-/* Append all the nonfunction members fields of KLASS to FIELD_VEC
-   starting at IDX. Recurse for anonymous members.  The array must
-   have space.  Returns the next available index.  */
+/* Append all the nonfunction members fields of KLASS to METHOD_VEC.
+   Recurse for anonymous members.  METHOD_VEC must have space.  */
 
-static unsigned
-field_vec_append_class_fields (struct sorted_fields_type *field_vec,
-			       tree klass, unsigned idx)
+static void
+method_vec_append_class_fields (vec<tree, va_gc> *method_vec, tree klass)
 {
   for (tree fields = TYPE_FIELDS (klass); fields; fields = DECL_CHAIN (fields))
     if (DECL_DECLARES_FUNCTION_P (fields))
       /* Functions are handled separately.  */;
     else if (TREE_CODE (fields) == FIELD_DECL
 	     && ANON_AGGR_TYPE_P (TREE_TYPE (fields)))
-      idx = field_vec_append_class_fields (field_vec, TREE_TYPE (fields), idx);
+      method_vec_append_class_fields (method_vec, TREE_TYPE (fields));
     else if (DECL_NAME (fields))
-      field_vec->elts[idx++] = fields;
-
-  return idx;
+      {
+	tree field = fields;
+	/* Mark a conv-op USING_DECL with the conv-op-marker.  */
+	if (TREE_CODE (field) == USING_DECL
+	    && IDENTIFIER_CONV_OP_P (DECL_NAME (field)))
+	  field = ovl_make (conv_op_marker, field);
+	method_vec->quick_push (field);
+      }
 }
 
-/* Append all of the enum values of ENUMTYPE to FIELD_VEC starting at IDX.
-   FIELD_VEC must have space.  */
+/* Append all of the enum values of ENUMTYPE to METHOD_VEC.
+   METHOD_VEC must have space.  */
 
-static unsigned
-field_vec_append_enum_values (struct sorted_fields_type *field_vec,
-			      tree enumtype, unsigned idx)
+static void
+method_vec_append_enum_values (vec<tree, va_gc> *method_vec, tree enumtype)
 {
   for (tree values = TYPE_VALUES (enumtype);
        values; values = TREE_CHAIN (values))
-    field_vec->elts[idx++] = TREE_VALUE (values);
+    method_vec->quick_push (TREE_VALUE (values));
+}
 
-  return idx;
+/* METHOD_VEC has just had new DECLs added to it, but is sorted.
+   DeDup adjacent DECLS of the same name.  We already dealt with
+   conflict resolution when adding the fields or methods themselves.
+   There are three cases (which could all be combined):
+   1) a TYPE_DECL and non TYPE_DECL.  Deploy STAT_HACK as appropriate.
+   2) a USING_DECL and an overload.  If the USING_DECL is dependent,
+   it wins.  Otherwise the OVERLOAD does.
+   3) two USING_DECLS. ...
+
+   method_name_cmp will have ordered duplicates as
+   <fns><using><type>  */
+
+static void
+method_vec_dedup (vec<tree, va_gc> *method_vec)
+{
+  unsigned len = method_vec->length ();
+  unsigned store = 0;
+
+  tree current = (*method_vec)[0], name = OVL_NAME (current);
+  tree next = NULL_TREE, next_name = NULL_TREE;
+  for (unsigned jx, ix = 0; ix < len;
+       ix = jx, current = next, name = next_name)
+    {
+      tree to_type = NULL_TREE;
+      tree to_using = NULL_TREE;
+      tree marker = NULL_TREE;
+      if (IDENTIFIER_CONV_OP_P (name))
+	{
+	  marker = current;
+	  current = OVL_CHAIN (current);
+	  name = DECL_NAME (OVL_FUNCTION (marker));
+	  gcc_checking_assert (name == conv_op_identifier);
+	}
+
+      if (TREE_CODE (current) == USING_DECL)
+	{
+	  current = strip_using_decl (current);
+	  if (is_overloaded_fn (current))
+	    current = NULL_TREE;
+	  else if (TREE_CODE (current) == USING_DECL)
+	    {
+	      to_using = current;
+	      current = NULL_TREE;
+	    }
+	}
+
+      if (current && DECL_DECLARES_TYPE_P (current))
+	{
+	  to_type = current;
+	  current = NULL_TREE;
+	}
+
+      for (jx = ix + 1; jx < len; jx++)
+	{
+	  next = (*method_vec)[jx];
+	  next_name = OVL_NAME (next);
+	  if (next_name != name)
+	    break;
+
+	  if (marker)
+	    {
+	      gcc_checking_assert (OVL_FUNCTION (marker)
+				   == OVL_FUNCTION (next));
+	      next = OVL_CHAIN (next);
+	    }
+
+	  if (TREE_CODE (next) == USING_DECL)
+	    {
+	      next = strip_using_decl (next);
+	      if (is_overloaded_fn (next))
+		next = NULL_TREE;
+	      else if (TREE_CODE (next) == USING_DECL)
+		{
+		  to_using = next;
+		  next = NULL_TREE;
+		}
+	    }
+
+	  if (next && DECL_DECLARES_TYPE_P (next))
+	    to_type = next;
+	}
+
+      if (to_using)
+	{
+	  if (!current)
+	    current = to_using;
+	  else
+	    current = ovl_make (to_using, current);
+	}
+
+      if (to_type)
+	{
+	  if (!current)
+	    current = to_type;
+	  else
+	    current = stat_hack (current, to_type);
+	}
+
+      gcc_assert (current);
+      if (marker)
+	{
+	  OVL_CHAIN (marker) = current;
+	  current = marker;
+	}
+      (*method_vec)[store++] = current;
+    }
+
+  while (store++ < len)
+    method_vec->pop ();
 }
 
-/* Insert FIELDS into KLASS for the sorted case if the FIELDS count is
-   big enough.  Sort the METHOD_VEC too.  */
+/* Add the non-function members to CLASSTYPE_METHOD_VEC.  If there is
+   no existing METHOD_VEC and fewer than 8 fields, do nothing.  We
+   know there must be at least 1 field -- the self-reference
+   TYPE_DECL, except for anon aggregates, which will have at least
+   one field.  */
 
 void 
-set_class_bindings (tree klass)
+set_class_bindings (tree klass, unsigned extra)
 {
-  if (vec<tree, va_gc> *method_vec = CLASSTYPE_METHOD_VEC (klass))
-    qsort (method_vec->address (), method_vec->length (),
-	   sizeof (tree), method_name_cmp);
-
-  int n_fields = count_class_fields (klass);
-  if (n_fields >= 8)
-    {
-      struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);
-      unsigned idx = field_vec_append_class_fields (field_vec, klass, 0);
-      gcc_assert (idx == unsigned (field_vec->len));
-      qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);
-      CLASSTYPE_SORTED_FIELDS (klass) = field_vec;
+  unsigned n_fields = count_class_fields (klass);
+  vec<tree, va_gc> *method_vec = CLASSTYPE_METHOD_VEC (klass);
+
+  if (method_vec || n_fields >= 8)
+    {
+      /* Append the new fields.  */
+      vec_safe_reserve_exact (method_vec, extra + n_fields);
+      method_vec_append_class_fields (method_vec, klass);
+    }
+
+  if (method_vec)
+    {
+      CLASSTYPE_METHOD_VEC (klass) = method_vec;
+      qsort (method_vec->address (), method_vec->length (),
+	     sizeof (tree), method_name_cmp);
+      method_vec_dedup (method_vec);
     }
 }
 
@@ -1561,33 +1697,27 @@ set_class_bindings (tree klass)
 void
 insert_late_enum_def_bindings (tree klass, tree enumtype)
 {
-  unsigned n_fields;
-  struct sorted_fields_type *sorted_fields = CLASSTYPE_SORTED_FIELDS (klass);
+  int n_fields;
+  vec<tree, va_gc> *method_vec = CLASSTYPE_METHOD_VEC (klass);
 
-  /* The enum values will already be on the TYPE_FIELDS, so don't
+  /* The enum bindings will already be on the TYPE_FIELDS, so don't
      count them twice.  */
-  if (sorted_fields)
-    n_fields = list_length (TYPE_VALUES (enumtype)) + sorted_fields->len;
-  else
+  if (!method_vec)
     n_fields = count_class_fields (klass);
+  else
+    n_fields = list_length (TYPE_VALUES (enumtype));
 
-  if (n_fields >= 8)
+  if (method_vec || n_fields >= 8)
     {
-      struct sorted_fields_type *field_vec = sorted_fields_type_new (n_fields);
-      unsigned idx;
-
-      if (sorted_fields)
-	{
-	  for (idx = 0; idx < unsigned (sorted_fields->len); ++idx)
-	    field_vec->elts[idx] = sorted_fields->elts[idx];
-
-	  idx = field_vec_append_enum_values (field_vec, enumtype, idx);
-	}
+      vec_safe_reserve_exact (method_vec, n_fields);
+      if (CLASSTYPE_METHOD_VEC (klass))
+	method_vec_append_enum_values (method_vec, enumtype);
       else
-	idx = field_vec_append_class_fields (field_vec, klass, 0);
-      gcc_assert (idx == unsigned (field_vec->len));
-      qsort (field_vec->elts, n_fields, sizeof (tree), field_decl_cmp);
-      CLASSTYPE_SORTED_FIELDS (klass) = field_vec;
+	method_vec_append_class_fields (method_vec, klass);
+      CLASSTYPE_METHOD_VEC (klass) = method_vec;
+      qsort (method_vec->address (), method_vec->length (),
+	     sizeof (tree), method_name_cmp);
+      method_vec_dedup (method_vec);
     }
 }
 
Index: name-lookup.h
===================================================================
--- name-lookup.h	(revision 252002)
+++ name-lookup.h	(working copy)
@@ -324,7 +324,7 @@ extern tree get_class_binding (tree, tre
 extern tree *get_method_slot (tree klass, tree name);
 extern void resort_type_method_vec (void *, void *,
 				    gt_pointer_operator, void *);
-extern void set_class_bindings (tree);
+extern void set_class_bindings (tree, unsigned extra = 0);
 extern void insert_late_enum_def_bindings (tree, tree);
 extern tree innermost_non_namespace_value (tree);
 extern cxx_binding *outer_binding (tree, cxx_binding *, bool);
