source: project/release/3/c3/c3.scm @ 8765

Last change on this file since 8765 was 8765, checked in by felix winkelmann, 12 years ago

trivial test change

File size: 3.9 KB
Line 
1;;;; c3.scm - By Alex Shinn
2;
3; Copyright (c) 2000-2004, Alex Shinn
4; All rights reserved.
5;
6; Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
7; conditions are met:
8;
9;   Redistributions of source code must retain the above copyright notice, this list of conditions and the following
10;     disclaimer.
11;   Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following
12;     disclaimer in the documentation and/or other materials provided with the distribution.
13;   Neither the name of the author nor the names of its contributors may be used to endorse or promote
14;     products derived from this software without specific prior written permission.
15;
16; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS
17; OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
18; AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR
19; CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
20; CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
21; SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
23; OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24; POSSIBILITY OF SUCH DAMAGE.
25;
26; Send bugs, suggestions and ideas to:
27;
28; felix@call-with-current-continuation.org
29;
30; Felix L. Winkelmann
31; Steinweg 1A
32; 37130 Gleichen, OT Weissenborn
33; Germany
34
35
36(use tinyclos srfi-1) 
37
38(private tinyclos
39  fast-getl getl not-found-object filter-in ensure-generic add-global-method compute-std-cpl
40  %allocate-instance %allocate-entity get-field set-field! lookup-slot-info the-slots-of-a-class
41  getters-n-setters-for-class generic-invocation-generics applicable? more-specific?
42  entity-tag make-instance-from-pointer
43  method-cache-tag method-cache-lookup make-method-cache method-caching-enabled
44  make-primitive-class make-structure-class make-port-class
45  make-extended-procedure-class make-tagged-pointer-class
46  new-primitive-class delete-primitive-class
47  new-structure-class delete-structure-class
48  new-tagged-pointer-class delete-tagged-pointer-class
49  new-extended-procedure-class delete-extended-procedure-class)
50
51(declare
52 (fixnum)
53 (disable-interrupts)
54 (hide c3-linearization) )
55
56(cond-expand
57 [paranoia]
58 [else
59  (declare
60    (no-bound-checks)
61    (bound-to-procedure c3-linearization) ) ] )
62
63
64;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
65;; C3 linearization from
66;;
67;;   http://www.webcom.com/~haahr/dylan/linearization-oopsla96.html
68
69; 25.03.2004 (flw): removed the `eq' parameter for better performance.
70
71(define (c3-linearization klass all-supers direct-supers)
72  (let ((klass-direct-supers (direct-supers klass)))
73    (define (merge-lists res lol)
74      (define (candidate? c)
75        (define (tail? l) (memq c (cdr l)))
76        (and (not (any tail? lol))
77             c))
78      (define (candidate-at-head l)
79        (and (pair? l)
80             (candidate? (car l))))
81      (if (every null? lol)
82        (reverse! res)
83        (let ((next (any candidate-at-head lol)))
84          (define (remove-next l) (if (eq? next (car l)) (cdr l) l))
85          (if next
86            (merge-lists (cons next res) (filter pair? (map remove-next lol)))
87            (##sys#error 'c3-linearization "inconsistent precedence graph: ")))))
88    (merge-lists (list klass)
89                 (filter pair?
90                         (append (map all-supers klass-direct-supers)
91                                 (list klass-direct-supers))))))
92
93(define compute-std-cpl
94  (lambda (c get-direct-supers)
95    (c3-linearization c class-cpl get-direct-supers)))
Note: See TracBrowser for help on using the repository browser.