src/utilities.lisp (merge-lists): Make default tie-break sane, and document.

  * Make sure the candidate list given to the tie-breaking `pick'
    function is sorted according to the /first/ list each candidate
    appears in, rather than the last one, because `remove-duplicates' by
    default keeps the last-appearing element of each equivalence class,
    unless I give `:from-end t'.  So do that.

  * Describe the tie-breaking behaviour now that it's sane.  This is
    sort of important because it's used by the output machinery.

diff --git a/src/utilities.lisp b/src/utilities.lisp
index 1767b9e..023fc60 100644 (file)
--- a/src/utilities.lisp
+++ b/src/utilities.lisp
@@ -437,7 +437,7 @@
 (defun merge-lists (lists &key pick (test #'eql))
   "Return a merge of the given LISTS.
 
-   The resulting LIST contains the items of the given lists, with duplicates
+   The resulting list contains the items of the given LISTS, with duplicates
    removed.  The order of the resulting list is consistent with the orders of
    the input LISTS in the sense that if A precedes B in some input list then
    A will also precede B in the output list.  If the lists aren't consistent
@@ -449,8 +449,19 @@
    If there is an ambiguity at any point -- i.e., a choice between two or
    more possible next items to emit -- then PICK is called to arbitrate.
    PICK is called with two arguments: the list of candidate next items, and
-   the current output list.  It should return one of the candidate items.  If
-   PICK is omitted then an arbitrary choice is made.
+   the current output list.  It should return one of the candidate items.
+   The order of the candidates in the list given to the PICK function
+   reflects their order in the input LISTS: item A will precede item B in the
+   candidates list if and only if an occurrence of A appears in an earlier
+   input list than any occurrence of item B.  (This completely determines the
+   order of the candidates: it is not possible that two candidates appear in
+   the same input list would resolve the ambiguity between them.)  If PICK is
+   omitted then the item chosen is the one appearing in the earliest of the
+   input lists: i.e., effectively, the default PICK function is
+
+       (lambda (candidates output-so-far)
+         (declare (ignore output-so-far))
+         (car candidates))
 
    The primary use of this function is in computing class precedence lists.
    By building the input lists and selecting the PICK function appropriately,
@@ -464,7 +475,8 @@
     ;; one of the other lists other than at the front then we reject it.  If
     ;; we've just rejected everything, then we can make no more progress and
     ;; the input lists were inconsistent.
-    (let* ((candidates (delete-duplicates (mapcar #'car lists) :test test))
+    (let* ((candidates (delete-duplicates (mapcar #'car lists)
+                                         :test test :from-end t))
           (leasts (remove-if (lambda (item)
                                (some (lambda (list)
                                        (member item (cdr list) :test test))