;;;; c3.scm - By Alex Shinn
;
; Copyright (c) 2000-2004, Alex Shinn
; All rights reserved.
;
; Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
; conditions are met:
;
;   Redistributions of source code must retain the above copyright notice, this list of conditions and the following
;     disclaimer.
;   Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following
;     disclaimer in the documentation and/or other materials provided with the distribution.
;   Neither the name of the author nor the names of its contributors may be used to endorse or promote
;     products derived from this software without specific prior written permission.
;
; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
; OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
; AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
; CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
; CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
; SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
; OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
; POSSIBILITY OF SUCH DAMAGE.
;
; Send bugs, suggestions and ideas to:
;
; felix@call-with-current-continuation.org
;
; Felix L. Winkelmann
; Steinweg 1A
; 37130 Gleichen, OT Weissenborn
; Germany

(module c3

  (export compute-c3-cpl)

  (import scheme chicken)

  (use tinyclos srfi-1)

  ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
  ;; C3 linearization from
  ;;
  ;;   http://www.webcom.com/~haahr/dylan/linearization-oopsla96.html
  ;;
  ;; 25.03.2004 (flw): removed the `eq' parameter for better performance.

  (define (c3-linearization klass all-supers direct-supers)
    (let ((klass-direct-supers (direct-supers klass)))
      (define (merge-lists res lol)
	(define (candidate? c)
	  (define (tail? l) (memq c (cdr l)))
	  (and (not (any tail? lol))
	       c) )
	(define (candidate-at-head l)
	  (and (pair? l)
	       (candidate? (car l))) )
	(if (every null? lol)
	    (reverse! res)
	    (let ((next (any candidate-at-head lol)))
	      (define (remove-next l) (if (eq? next (car l)) (cdr l) l))
	      (if next
		  (merge-lists (cons next res) (filter pair? (map remove-next lol)))
		  (##sys#error 'c3-linearization "inconsistent precedence graph: ") ) ) ) )
      (merge-lists (list klass)
		   (filter pair?
			   (append (map all-supers klass-direct-supers)
				   (list klass-direct-supers)))) ) )

  (define (compute-c3-cpl c get-direct-supers)
    (c3-linearization c class-cpl get-direct-supers) )

  (add-method compute-cpl
    (make-method (list <class>)
      (lambda (call-next-method class)
        (compute-c3-cpl class class-direct-supers) ) ) )
)