| 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 |
|