Synopsis: Compute the CLOS superclass linearization
Author: Kim Barrett <kab@camellia.org>,
        Bob Cassels <Cassels@harlequin.com>,
        Paul Haahr <haahr@netcom.com>,
        David A. Moon <Moon@mc.lcs.mit.edu>,
        Keith Playford <keith@harlequin.co.uk>,
        P. Tucker Withington <ptw@harlequin.com>
Module: dylan-user

define constant compute-clos-linearization =
  method (c :: <class>) => (cpl :: <list>)
    local method merge-lists (reversed-partial-result :: <list>,
                              remaining-inputs :: <sequence>)

            if (every?(empty?, remaining-inputs))
              reverse!(reversed-partial-result)
            else

              // start of selection rule
              local method candidate (c :: <class>)
                      // returns c if it can go in the result now, otherwise false

                      local method head? (l :: <list>)
                              c == head(l)
                            end method head?,

                            method tail? (l :: <list>)
                              member?(c, tail(l))
                            end method tail?;

                      any?(head?, remaining-inputs)
                        & ~any?(tail?, remaining-inputs)
                        & c
                    end method candidate,

                    method candidate-direct-superclass (c :: <class>)
                      any?(candidate, direct-superclasses(c))
                    end method candidate-direct-superclass;

              let next = any?(candidate-direct-superclass,
                              reversed-partial-result);
              // end of selection rule

              if (next)
                local method remove-next (l :: <list>)
                        if (head(l) == next) tail(l) else l end
                      end method remove-next;
                merge-lists(pair(next, reversed-partial-result),
                            map(remove-next, remaining-inputs))
              else
                error("Inconsistent precedence graph");
              end if
            end if
          end method merge-lists;

    local method direct-superclass-list (s :: <class>)
            let supers = as(<list>, clos-linearization(s));  // all-superclasses
            if (s == c) supers else pair(s, supers) end
          end method direct-superclass-list;
    merge-lists(list(c),
                map(direct-superclass-list, all-superclasses(c)));

  end method; // compute-clos-linearization