Debian Codegraph @

ext/sxml/src/SXML-tree-trans.scm

raw
1 ; XML/HTML processing in Scheme
2 ; SXML expression tree transformers
3 ;
4 ; IMPORT
5 ; A prelude appropriate for your Scheme system
6 ; (myenv-bigloo.scm, myenv-mit.scm, etc.)
7 ;
8 ; EXPORT
9 ; (provide SRV:send-reply
10 ; post-order pre-post-order replace-range)
11 ;
12 ; See vSXML-tree-trans.scm for the validation code, which also
13 ; serves as usage examples.
14 ;
15 ; $Id: SXML-tree-trans.scm,v 1.2 2003-07-21 12:19:43 shirok Exp $
16
17
18 ; Output the 'fragments'
19 ; The fragments are a list of strings, characters,
20 ; numbers, thunks, #f, #t -- and other fragments.
21 ; The function traverses the tree depth-first, writes out
22 ; strings and characters, executes thunks, and ignores
23 ; #f and '().
24 ; The function returns #t if anything was written at all;
25 ; otherwise the result is #f
26 ; If #t occurs among the fragments, it is not written out
27 ; but causes the result of SRV:send-reply to be #t
28
29 (define (SRV:send-reply . fragments)
30 (let loop ((fragments fragments) (result #f))
31 (cond
32 ((null? fragments) result)
33 ((not (car fragments)) (loop (cdr fragments) result))
34 ((null? (car fragments)) (loop (cdr fragments) result))
35 ((eq? #t (car fragments)) (loop (cdr fragments) #t))
36 ((pair? (car fragments))
37 (loop (cdr fragments) (loop (car fragments) result)))
38 ((procedure? (car fragments))
39 ((car fragments))
40 (loop (cdr fragments) #t))
41 (else
42 (display (car fragments))
43 (loop (cdr fragments) #t)))))
44
45
46
47 ;------------------------------------------------------------------------
48 ; Traversal of an SXML tree or a grove:
49 ; a <Node> or a <Nodelist>
50 ;
51 ; A <Node> and a <Nodelist> are mutually-recursive datatypes that
52 ; underlie the SXML tree:
53 ; <Node> ::= (name . <Nodelist>) | "text string"
54 ; An (ordered) set of nodes is just a list of the constituent nodes:
55 ; <Nodelist> ::= (<Node> ...)
56 ; Nodelists, and Nodes other than text strings are both lists. A
57 ; <Nodelist> however is either an empty list, or a list whose head is
58 ; not a symbol (an atom in general). A symbol at the head of a node is
59 ; either an XML name (in which case it's a tag of an XML element), or
60 ; an administrative name such as '@'.
61 ; See SXPath.scm and SSAX.scm for more information on SXML.
62
63
64 ; Pre-Post-order traversal of a tree and creation of a new tree:
65 ; pre-post-order:: <tree> x <bindings> -> <new-tree>
66 ; where
67 ; <bindings> ::= (<binding> ...)
68 ; <binding> ::= (<trigger-symbol> *preorder* . <handler>) |
69 ; (<trigger-symbol> *macro* . <handler>) |
70 ; (<trigger-symbol> <new-bindings> . <handler>) |
71 ; (<trigger-symbol> . <handler>)
72 ; <trigger-symbol> ::= XMLname | *text* | *default*
73 ; <handler> :: <trigger-symbol> x [<tree>] -> <new-tree>
74 ;
75 ; The pre-post-order function visits the nodes and nodelists
76 ; pre-post-order (depth-first). For each <Node> of the form (name
77 ; <Node> ...) it looks up an association with the given 'name' among
78 ; its <bindings>. If failed, pre-post-order tries to locate a
79 ; *default* binding. It's an error if the latter attempt fails as
80 ; well. Having found a binding, the pre-post-order function first
81 ; checks to see if the binding is of the form
82 ; (<trigger-symbol> *preorder* . <handler>)
83 ; If it is, the handler is 'applied' to the current node. Otherwise,
84 ; the pre-post-order function first calls itself recursively for each
85 ; child of the current node, with <new-bindings> prepended to the
86 ; <bindings> in effect. The result of these calls is passed to the
87 ; <handler> (along with the head of the current <Node>). To be more
88 ; precise, the handler is _applied_ to the head of the current node
89 ; and its processed children. The result of the handler, which should
90 ; also be a <tree>, replaces the current <Node>. If the current <Node>
91 ; is a text string or other atom, a special binding with a symbol
92 ; *text* is looked up.
93 ;
94 ; A binding can also be of a form
95 ; (<trigger-symbol> *macro* . <handler>)
96 ; This is equivalent to *preorder* described above. However, the result
97 ; is re-processed again, with the current stylesheet.
98
99 (define (pre-post-order tree bindings)
100 (let* ((default-binding (assq '*default* bindings))
101 (text-binding (or (assq '*text* bindings) default-binding))
102 (text-handler ; Cache default and text bindings
103 (and text-binding
104 (if (procedure? (cdr text-binding))
105 (cdr text-binding) (cddr text-binding)))))
106 (let loop ((tree tree))
107 (cond
108 ((null? tree) '())
109 ((not (pair? tree))
110 (let ((trigger '*text*))
111 (if text-handler (text-handler trigger tree)
112 (error "Unknown binding for " trigger " and no default"))))
113 ((not (symbol? (car tree))) (map loop tree)) ; tree is a nodelist
114 (else ; tree is an SXML node
115 (let* ((trigger (car tree))
116 (binding (or (assq trigger bindings) default-binding)))
117 (cond
118 ((not binding)
119 (error "Unknown binding for " trigger " and no default"))
120 ((not (pair? (cdr binding))) ; must be a procedure: handler
121 (apply (cdr binding) trigger (map loop (cdr tree))))
122 ((eq? '*preorder* (cadr binding))
123 (apply (cddr binding) tree))
124 ((eq? '*macro* (cadr binding))
125 (loop (apply (cddr binding) tree)))
126 (else ; (cadr binding) is a local binding
127 (apply (cddr binding) trigger
128 (pre-post-order (cdr tree) (append (cadr binding) bindings)))
129 ))))))))
130
131 ; post-order is a strict subset of pre-post-order without *preorder*
132 ; (let alone *macro*) traversals.
133 ; Now pre-post-order is actually faster than the old post-order.
134 ; The function post-order is deprecated and is aliased below for
135 ; backward compatibility.
136 (define post-order pre-post-order)
137
138 ;------------------------------------------------------------------------
139 ; Extended tree fold
140 ; tree = atom | (node-name tree ...)
141 ;
142 ; foldts fdown fup fhere seed (Leaf str) = fhere seed str
143 ; foldts fdown fup fhere seed (Nd kids) =
144 ; fup seed $ foldl (foldts fdown fup fhere) (fdown seed) kids
145
146 ; procedure fhere: seed -> atom -> seed
147 ; procedure fdown: seed -> node -> seed
148 ; procedure fup: parent-seed -> last-kid-seed -> node -> seed
149 ; foldts returns the final seed
150
151 (define (foldts fdown fup fhere seed tree)
152 (cond
153 ((null? tree) seed)
154 ((not (pair? tree)) ; An atom
155 (fhere seed tree))
156 (else
157 (let loop ((kid-seed (fdown seed tree)) (kids (cdr tree)))
158 (if (null? kids)
159 (fup seed kid-seed tree)
160 (loop (foldts fdown fup fhere kid-seed (car kids))
161 (cdr kids)))))))
162
163 ;------------------------------------------------------------------------
164 ; Traverse a forest depth-first and cut/replace ranges of nodes.
165 ;
166 ; The nodes that define a range don't have to have the same immediate
167 ; parent, don't have to be on the same level, and the end node of a
168 ; range doesn't even have to exist. A replace-range procedure removes
169 ; nodes from the beginning node of the range up to (but not including)
170 ; the end node of the range. In addition, the beginning node of the
171 ; range can be replaced by a node or a list of nodes. The range of
172 ; nodes is cut while depth-first traversing the forest. If all
173 ; branches of the node are cut a node is cut as well. The procedure
174 ; can cut several non-overlapping ranges from a forest.
175
176 ; replace-range:: BEG-PRED x END-PRED x FOREST -> FOREST
177 ; where
178 ; type FOREST = (NODE ...)
179 ; type NODE = Atom | (Name . FOREST) | FOREST
180 ;
181 ; The range of nodes is specified by two predicates, beg-pred and end-pred.
182 ; beg-pred:: NODE -> #f | FOREST
183 ; end-pred:: NODE -> #f | FOREST
184 ; The beg-pred predicate decides on the beginning of the range. The node
185 ; for which the predicate yields non-#f marks the beginning of the range
186 ; The non-#f value of the predicate replaces the node. The value can be a
187 ; list of nodes. The replace-range procedure then traverses the tree and skips
188 ; all the nodes, until the end-pred yields non-#f. The value of the end-pred
189 ; replaces the end-range node. The new end node and its brothers will be
190 ; re-scanned.
191 ; The predicates are evaluated pre-order. We do not descend into a node that
192 ; is marked as the beginning of the range.
193
194 (define (replace-range beg-pred end-pred forest)
195
196 ; loop forest keep? new-forest
197 ; forest is the forest to traverse
198 ; new-forest accumulates the nodes we will keep, in the reverse
199 ; order
200 ; If keep? is #t, keep the curr node if atomic. If the node is not atomic,
201 ; traverse its children and keep those that are not in the skip range.
202 ; If keep? is #f, skip the current node if atomic. Otherwise,
203 ; traverse its children. If all children are skipped, skip the node
204 ; as well.
205
206 (define (loop forest keep? new-forest)
207 (if (null? forest) (values (reverse new-forest) keep?)
208 (let ((node (car forest)))
209 (if keep?
210 (cond ; accumulate mode
211 ((beg-pred node) => ; see if the node starts the skip range
212 (lambda (repl-branches) ; if so, skip/replace the node
213 (loop (cdr forest) #f
214 (append (reverse repl-branches) new-forest))))
215 ((not (pair? node)) ; it's an atom, keep it
216 (loop (cdr forest) keep? (cons node new-forest)))
217 (else
218 (let*-values
219 (((node?) (symbol? (car node))) ; or is it a nodelist?
220 ((new-kids keep?) ; traverse its children
221 (loop (if node? (cdr node) node) #t '())))
222 (loop (cdr forest) keep?
223 (cons
224 (if node? (cons (car node) new-kids) new-kids)
225 new-forest)))))
226 ; skip mode
227 (cond
228 ((end-pred node) => ; end the skip range
229 (lambda (repl-branches) ; repl-branches will be re-scanned
230 (loop (append repl-branches (cdr forest)) #t
231 new-forest)))
232 ((not (pair? node)) ; it's an atom, skip it
233 (loop (cdr forest) keep? new-forest))
234 (else
235 (let*-values
236 (((node?) (symbol? (car node))) ; or is it a nodelist?
237 ((new-kids keep?) ; traverse its children
238 (loop (if node? (cdr node) node) #f '())))
239 (loop (cdr forest) keep?
240 (if (or keep? (pair? new-kids))
241 (cons
242 (if node? (cons (car node) new-kids) new-kids)
243 new-forest)
244 new-forest) ; if all kids are skipped
245 )))))))) ; skip the node too
246
247 (let*-values (((new-forest keep?) (loop forest #t '())))
248 new-forest))
249