Only use wild_sort_fast

there's no reason why the tree-based variant can't always be used
when sorting is required, it merely needs to also support filename
sorting and have a fast path for insertion at end (aka rightmost tree
leaf).

The filename sorting isn't tested anywhere and the only scripttempl
that uses it is avr (for 'SORT(*)(.ctors)'), and I believe even there it
was a mistake.  Either way, this adds a testcase for filename sorting as
well.

Then the non-BST based sorting can be simplified to only support
the fast case of no sorting required at all (at the same time renaming
the two variants to _sort and _nosort).

6 files changed, 163 insertions, 178 deletions

diff --git a/ld/ldlang.c b/ld/ldlang.c
index 5fc55dc..336eea9 100644
--- a/ld/ldlang.c
+++ b/ld/ldlang.c
@@ -556,30 +556,92 @@ compare_section (sort_type sort, asection *asec, asection *bsec)
   return ret;
 }
 
-/* Build a Binary Search Tree to sort sections, unlike insertion sort
-   used in wild_sort(). BST is considerably faster if the number of
-   of sections are large.  */
+/* PE puts the sort key in the input statement.  */
+
+static const char *
+sort_filename (bfd *abfd)
+{
+  lang_input_statement_type *is = bfd_usrdata (abfd);
+  if (is->sort_key)
+    return is->sort_key;
+  return bfd_get_filename (abfd);
+}
+
+/* Handle wildcard sorting.  This returns the place in a binary search tree
+   where this FILE:SECTION should be inserted for wild statement WILD where
+   the spec SEC was the matching one.  The tree is later linearized.  */
 
 static lang_section_bst_type **
-wild_sort_fast (lang_wild_statement_type *wild,
-		struct wildcard_list *sec,
-		lang_input_statement_type *file ATTRIBUTE_UNUSED,
-		asection *section)
+wild_sort (lang_wild_statement_type *wild,
+	   struct wildcard_list *sec,
+	   lang_input_statement_type *file,
+	   asection *section)
 {
   lang_section_bst_type **tree;
 
-  tree = &wild->tree;
   if (!wild->filenames_sorted
-      && (sec == NULL || sec->spec.sorted == none))
+      && (sec == NULL || sec->spec.sorted == none
+	  || sec->spec.sorted == by_none))
     {
-      /* Append at the right end of tree.  */
-      while (*tree)
-	tree = &((*tree)->right);
-      return tree;
+      /* We might be called even if _this_ spec doesn't need sorting,
+         in which case we simply append at the right end of tree.  */
+      return wild->rightmost;
     }
 
+  tree = &wild->tree;
   while (*tree)
     {
+      /* Sorting by filename takes precedence over sorting by section
+	 name.  */
+
+      if (wild->filenames_sorted)
+	{
+	  const char *fn, *ln;
+	  bool fa, la;
+	  int i;
+	  asection *lsec = (*tree)->section;
+
+	  /* The PE support for the .idata section as generated by
+	     dlltool assumes that files will be sorted by the name of
+	     the archive and then the name of the file within the
+	     archive.  */
+
+	  fa = file->the_bfd->my_archive != NULL;
+	  if (fa)
+	    fn = sort_filename (file->the_bfd->my_archive);
+	  else
+	    fn = sort_filename (file->the_bfd);
+
+	  la = lsec->owner->my_archive != NULL;
+	  if (la)
+	    ln = sort_filename (lsec->owner->my_archive);
+	  else
+	    ln = sort_filename (lsec->owner);
+
+	  i = filename_cmp (fn, ln);
+	  if (i > 0)
+	    { tree = &((*tree)->right); continue; }
+	  else if (i < 0)
+	    { tree = &((*tree)->left); continue; }
+
+	  if (fa || la)
+	    {
+	      if (fa)
+		fn = sort_filename (file->the_bfd);
+	      if (la)
+		ln = sort_filename (lsec->owner);
+
+	      i = filename_cmp (fn, ln);
+	      if (i > 0)
+		{ tree = &((*tree)->right); continue; }
+	      else if (i < 0)
+		{ tree = &((*tree)->left); continue; }
+	    }
+	}
+
+      /* Here either the files are not sorted by name, or we are
+	 looking at the sections for this file.  */
+
       /* Find the correct node to append this section.  */
       if (compare_section (sec->spec.sorted, section, (*tree)->section) < 0)
 	tree = &((*tree)->left);
@@ -590,10 +652,10 @@ wild_sort_fast (lang_wild_statement_type *wild,
   return tree;
 }
 
-/* Use wild_sort_fast to build a BST to sort sections.  */
+/* Use wild_sort to build a BST to sort sections.  */
 
 static void
-output_section_callback_fast (lang_wild_statement_type *ptr,
+output_section_callback_sort (lang_wild_statement_type *ptr,
 			      struct wildcard_list *sec,
 			      asection *section,
 			      lang_input_statement_type *file,
@@ -614,9 +676,13 @@ output_section_callback_fast (lang_wild_statement_type *ptr,
   node->section = section;
   node->pattern = ptr->section_list;
 
-  tree = wild_sort_fast (ptr, sec, file, section);
+  tree = wild_sort (ptr, sec, file, section);
   if (tree != NULL)
-    *tree = node;
+    {
+      *tree = node;
+      if (tree == ptr->rightmost)
+	ptr->rightmost = &node->right;
+    }
 }
 
 /* Convert a sorted sections' BST back to list form.  */
@@ -629,7 +695,8 @@ output_section_callback_tree_to_list (lang_wild_statement_type *ptr,
   if (tree->left)
     output_section_callback_tree_to_list (ptr, tree->left, output);
 
-  lang_add_section (&ptr->children, tree->section, tree->pattern, NULL,
+  lang_add_section (&ptr->children, tree->section, tree->pattern,
+		    ptr->section_flag_list,
 		    (lang_output_section_statement_type *) output);
 
   if (tree->right)
@@ -887,6 +954,7 @@ analyze_walk_wild_section_handler (lang_wild_statement_type *ptr)
   ptr->handler_data[2] = NULL;
   ptr->handler_data[3] = NULL;
   ptr->tree = NULL;
+  ptr->rightmost = &ptr->tree;
 
   for (sec = ptr->section_list; sec != NULL; sec = sec->next)
     {
@@ -2777,113 +2845,17 @@ lang_add_section (lang_statement_list_type *ptr,
   new_section->pattern = pattern;
 }
 
-/* PE puts the sort key in the input statement.  */
-
-static const char *
-sort_filename (bfd *abfd)
-{
-  lang_input_statement_type *is = bfd_usrdata (abfd);
-  if (is->sort_key)
-    return is->sort_key;
-  return bfd_get_filename (abfd);
-}
-
-/* Handle wildcard sorting.  This returns the lang_input_section which
-   should follow the one we are going to create for SECTION and FILE,
-   based on the sorting requirements of WILD.  It returns NULL if the
-   new section should just go at the end of the current list.  */
-
-static lang_statement_union_type *
-wild_sort (lang_wild_statement_type *wild,
-	   struct wildcard_list *sec,
-	   lang_input_statement_type *file,
-	   asection *section)
-{
-  lang_statement_union_type *l;
-
-  if (!wild->filenames_sorted
-      && (sec == NULL || sec->spec.sorted == none))
-    return NULL;
-
-  for (l = wild->children.head; l != NULL; l = l->header.next)
-    {
-      lang_input_section_type *ls;
-
-      if (l->header.type != lang_input_section_enum)
-	continue;
-      ls = &l->input_section;
-
-      /* Sorting by filename takes precedence over sorting by section
-	 name.  */
-
-      if (wild->filenames_sorted)
-	{
-	  const char *fn, *ln;
-	  bool fa, la;
-	  int i;
-
-	  /* The PE support for the .idata section as generated by
-	     dlltool assumes that files will be sorted by the name of
-	     the archive and then the name of the file within the
-	     archive.  */
-
-	  fa = file->the_bfd->my_archive != NULL;
-	  if (fa)
-	    fn = sort_filename (file->the_bfd->my_archive);
-	  else
-	    fn = sort_filename (file->the_bfd);
-
-	  la = ls->section->owner->my_archive != NULL;
-	  if (la)
-	    ln = sort_filename (ls->section->owner->my_archive);
-	  else
-	    ln = sort_filename (ls->section->owner);
-
-	  i = filename_cmp (fn, ln);
-	  if (i > 0)
-	    continue;
-	  else if (i < 0)
-	    break;
-
-	  if (fa || la)
-	    {
-	      if (fa)
-		fn = sort_filename (file->the_bfd);
-	      if (la)
-		ln = sort_filename (ls->section->owner);
-
-	      i = filename_cmp (fn, ln);
-	      if (i > 0)
-		continue;
-	      else if (i < 0)
-		break;
-	    }
-	}
-
-      /* Here either the files are not sorted by name, or we are
-	 looking at the sections for this file.  */
-
-      if (sec != NULL
-	  && sec->spec.sorted != none
-	  && sec->spec.sorted != by_none)
-	if (compare_section (sec->spec.sorted, section, ls->section) < 0)
-	  break;
-    }
-
-  return l;
-}
-
 /* Expand a wild statement for a particular FILE.  SECTION may be
-   NULL, in which case it is a wild card.  */
+   NULL, in which case it is a wild card.  This assumes that the
+   wild statement doesn't need any sorting (of filenames or sections).  */
 
 static void
-output_section_callback (lang_wild_statement_type *ptr,
-			 struct wildcard_list *sec,
-			 asection *section,
-			 lang_input_statement_type *file,
-			 void *output)
+output_section_callback_nosort (lang_wild_statement_type *ptr,
+			struct wildcard_list *sec ATTRIBUTE_UNUSED,
+			asection *section,
+			lang_input_statement_type *file ATTRIBUTE_UNUSED,
+			void *output)
 {
-  lang_statement_union_type *before;
   lang_output_section_statement_type *os;
 
   os = (lang_output_section_statement_type *) output;
@@ -2892,40 +2864,8 @@ output_section_callback (lang_wild_statement_type *ptr,
   if (unique_section_p (section, os))
     return;
 
-  before = wild_sort (ptr, sec, file, section);
-
-  /* Here BEFORE points to the lang_input_section which
-     should follow the one we are about to add.  If BEFORE
-     is NULL, then the section should just go at the end
-     of the current list.  */
-
-  if (before == NULL)
-    lang_add_section (&ptr->children, section, ptr->section_list,
-		      ptr->section_flag_list, os);
-  else
-    {
-      lang_statement_list_type list;
-      lang_statement_union_type **pp;
-
-      lang_list_init (&list);
-      lang_add_section (&list, section, ptr->section_list,
-			ptr->section_flag_list, os);
-
-      /* If we are discarding the section, LIST.HEAD will
-	 be NULL.  */
-      if (list.head != NULL)
-	{
-	  ASSERT (list.head->header.next == NULL);
-
-	  for (pp = &ptr->children.head;
-	       *pp != before;
-	       pp = &(*pp)->header.next)
-	    ASSERT (*pp != NULL);
-
-	  list.head->header.next = *pp;
-	  *pp = list.head;
-	}
-    }
+  lang_add_section (&ptr->children, section, ptr->section_list,
+		    ptr->section_flag_list, os);
 }
 
 /* Check if all sections in a wild statement for a particular FILE
@@ -3236,23 +3176,22 @@ wild (lang_wild_statement_type *s,
 {
   struct wildcard_list *sec;
 
-  if (s->handler_data[0]
-      && s->handler_data[0]->spec.sorted == by_name
-      && !s->filenames_sorted)
+  if (s->filenames_sorted || s->any_specs_sorted)
     {
       lang_section_bst_type *tree;
 
-      walk_wild (s, output_section_callback_fast, output);
+      walk_wild (s, output_section_callback_sort, output);
 
       tree = s->tree;
       if (tree)
 	{
 	  output_section_callback_tree_to_list (s, tree, output);
 	  s->tree = NULL;
+	  s->rightmost = &s->tree;
 	}
     }
   else
-    walk_wild (s, output_section_callback, output);
+    walk_wild (s, output_section_callback_nosort, output);
 
   if (default_common_section == NULL)
     for (sec = s->section_list; sec != NULL; sec = sec->next)
@@ -4210,22 +4149,25 @@ update_wild_statements (lang_statement_union_type *s)
 		/* Don't sort .init/.fini sections.  */
 		if (strcmp (sec->spec.name, ".init") != 0
 		    && strcmp (sec->spec.name, ".fini") != 0)
-		  switch (sec->spec.sorted)
-		    {
-		    case none:
-		      sec->spec.sorted = sort_section;
-		      break;
-		    case by_name:
-		      if (sort_section == by_alignment)
-			sec->spec.sorted = by_name_alignment;
-		      break;
-		    case by_alignment:
-		      if (sort_section == by_name)
-			sec->spec.sorted = by_alignment_name;
-		      break;
-		    default:
-		      break;
-		    }
+		  {
+		    switch (sec->spec.sorted)
+		      {
+			case none:
+			    sec->spec.sorted = sort_section;
+			    break;
+			case by_name:
+			    if (sort_section == by_alignment)
+			      sec->spec.sorted = by_name_alignment;
+			    break;
+			case by_alignment:
+			    if (sort_section == by_name)
+			      sec->spec.sorted = by_alignment_name;
+			    break;
+			default:
+			    break;
+		      }
+		    s->wild_statement.any_specs_sorted = true;
+		  }
 	      break;
 
 	    case lang_constructors_statement_enum:
@@ -8253,7 +8195,9 @@ lang_process (void)
 
   ldemul_after_check_relocs ();
 
-  /* Update wild statements.  */
+  /* Update wild statements in case the user gave --sort-section.
+     Note how the option might have come after the linker script and
+     so couldn't have been set when the wild statements were created.  */
   update_wild_statements (statement_list.head);
 
   /* Run through the contours of the script and attach input sections
@@ -8367,12 +8311,15 @@ lang_add_wild (struct wildcard_spec *filespec,
 {
   struct wildcard_list *curr, *next;
   lang_wild_statement_type *new_stmt;
+  bool any_specs_sorted = false;
 
   /* Reverse the list as the parser puts it back to front.  */
   for (curr = section_list, section_list = NULL;
        curr != NULL;
        section_list = curr, curr = next)
     {
+      if (curr->spec.sorted != none && curr->spec.sorted != by_none)
+	any_specs_sorted = true;
       next = curr->next;
       curr->next = section_list;
     }
@@ -8388,6 +8335,7 @@ lang_add_wild (struct wildcard_spec *filespec,
   new_stmt = new_stat (lang_wild_statement, stat_ptr);
   new_stmt->filename = NULL;
   new_stmt->filenames_sorted = false;
+  new_stmt->any_specs_sorted = any_specs_sorted;
   new_stmt->section_flag_list = NULL;
   new_stmt->exclude_name_list = NULL;
   if (filespec != NULL)
diff --git a/ld/ldlang.h b/ld/ldlang.h
index b853cdb..713c528 100644
--- a/ld/ldlang.h
+++ b/ld/ldlang.h
@@ -384,6 +384,7 @@ struct lang_wild_statement_struct
   lang_statement_header_type header;
   const char *filename;
   bool filenames_sorted;
+  bool any_specs_sorted;
   struct wildcard_list *section_list;
   bool keep_sections;
   lang_statement_list_type children;
@@ -391,7 +392,7 @@ struct lang_wild_statement_struct
 
   walk_wild_section_handler_t walk_wild_section_handler;
   struct wildcard_list *handler_data[4];
-  lang_section_bst_type *tree;
+  lang_section_bst_type *tree, **rightmost;
   struct flag_info *section_flag_list;
 };
 
diff --git a/ld/testsuite/ld-scripts/sort-file.d b/ld/testsuite/ld-scripts/sort-file.d
new file mode 100644
index 0000000..01eb694
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file.d
@@ -0,0 +1,18 @@
+#source: sort-file2.s
+#source: sort-file1.s
+#ld: -T sort-file.t
+#nm: -n
+
+# Check that SORT_BY_NAME on filenames works
+# the text sections should come in sorted order, the data
+# sections in input order.  Note how we specifically pass
+# the object filenames in non-alphabetical order
+#...
+0[0-9a-f]* t infile1
+#...
+0[0-9a-f]* t infile2
+#...
+0[0-9a-f]* d data2
+#...
+0[0-9a-f]* d data1
+#pass
diff --git a/ld/testsuite/ld-scripts/sort-file.t b/ld/testsuite/ld-scripts/sort-file.t
new file mode 100644
index 0000000..559a000
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file.t
@@ -0,0 +1,6 @@
+SECTIONS
+{
+  .text : { SORT_BY_NAME(*)(.text*) }
+  .data : { *(.data*) }
+  /DISCARD/ : { *(.*) }
+}
diff --git a/ld/testsuite/ld-scripts/sort-file1.s b/ld/testsuite/ld-scripts/sort-file1.s
new file mode 100644
index 0000000..23777a8
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file1.s
@@ -0,0 +1,6 @@
+	.text
+infile1:
+	.long 0
+	.data
+data1:
+	.long 0
diff --git a/ld/testsuite/ld-scripts/sort-file2.s b/ld/testsuite/ld-scripts/sort-file2.s
new file mode 100644
index 0000000..cf4bb1f
--- /dev/null
+++ b/ld/testsuite/ld-scripts/sort-file2.s
@@ -0,0 +1,6 @@
+	.text
+infile2:
+	.long 0
+	.data
+data2:
+	.long 0