Synopsis: Compute the L*LOOPS 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-l*loops-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 tail? (l :: <list>)
                              member?(c, tail(l))
                            end method tail?;

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

                    method candidate-at-head (l :: <list>)
                      ~empty?(l) & candidate(head(l))
                    end candidate-at-head;

              let next = any?(candidate-at-head, remaining-inputs);
              // 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;

    let c-direct-superclasses = direct-superclasses(c);
    local method cpl-list (c)
            as(<list>, l*loops-linearization(c))	// all-superclasses
          end method cpl-list;
    merge-lists(list(c),
                map(cpl-list, c-direct-superclasses));

  end method; // compute-l*loops-linearization