| 1 |
;; XML processing in Scheme |
| 2 |
; SXPath -- SXML Query Language |
| 3 |
; |
| 4 |
; $Id: sxpathlib.scm,v 1.1 2003-07-22 11:22:11 shirok Exp $ |
| 5 |
; |
| 6 |
; This code is in Public Domain |
| 7 |
; It's based on SXPath by Oleg Kiselyov, and multiple improvements |
| 8 |
; implemented by Dmitry Lizorkin. |
| 9 |
; |
| 10 |
; The list of differences from original SXPath.scm my be found in changelog.txt |
| 11 |
; |
| 12 |
; Kirill Lisovsky [email protected] |
| 13 |
; |
| 14 |
; * * * |
| 15 |
; |
| 16 |
; SXPath is a query language for SXML, an instance of XML Information |
| 17 |
; set (Infoset) in the form of s-expressions. See SSAX.scm for the |
| 18 |
; definition of SXML and more details. SXPath is also a translation into |
| 19 |
; Scheme of an XML Path Language, XPath: |
| 20 |
; http://www.w3.org/TR/xpath |
| 21 |
; XPath and SXPath describe means of selecting a set of Infoset's items |
| 22 |
; or their properties. |
| 23 |
; |
| 24 |
; To facilitate queries, XPath maps the XML Infoset into an explicit |
| 25 |
; tree, and introduces important notions of a location path and a |
| 26 |
; current, context node. A location path denotes a selection of a set of |
| 27 |
; nodes relative to a context node. Any XPath tree has a distinguished, |
| 28 |
; root node -- which serves as the context node for absolute location |
| 29 |
; paths. Location path is recursively defined as a location step joined |
| 30 |
; with a location path. A location step is a simple query of the |
| 31 |
; database relative to a context node. A step may include expressions |
| 32 |
; that further filter the selected set. Each node in the resulting set |
| 33 |
; is used as a context node for the adjoining location path. The result |
| 34 |
; of the step is a union of the sets returned by the latter location |
| 35 |
; paths. |
| 36 |
; |
| 37 |
; The SXML representation of the XML Infoset (see SSAX.scm) is rather |
| 38 |
; suitable for querying as it is. Bowing to the XPath specification, |
| 39 |
; we will refer to SXML information items as 'Nodes': |
| 40 |
; <Node> ::= <Element> | <attributes-coll> | <attrib> |
| 41 |
; | "text string" | <PI> |
| 42 |
; This production can also be described as |
| 43 |
; <Node> ::= (name . <Nodeset>) | "text string" |
| 44 |
; An (ordered) set of nodes is just a list of the constituent nodes: |
| 45 |
; <Nodeset> ::= (<Node> ...) |
| 46 |
; Nodesets, and Nodes other than text strings are both lists. A |
| 47 |
; <Nodeset> however is either an empty list, or a list whose head is not |
| 48 |
; a symbol. A symbol at the head of a node is either an XML name (in |
| 49 |
; which case it's a tag of an XML element), or an administrative name |
| 50 |
; such as '@'. This uniform list representation makes processing rather |
| 51 |
; simple and elegant, while avoiding confusion. The multi-branch tree |
| 52 |
; structure formed by the mutually-recursive datatypes <Node> and |
| 53 |
; <Nodeset> lends itself well to processing by functional languages. |
| 54 |
; |
| 55 |
; A location path is in fact a composite query over an XPath tree or |
| 56 |
; its branch. A singe step is a combination of a projection, selection |
| 57 |
; or a transitive closure. Multiple steps are combined via join and |
| 58 |
; union operations. This insight allows us to _elegantly_ implement |
| 59 |
; XPath as a sequence of projection and filtering primitives -- |
| 60 |
; converters -- joined by _combinators_. Each converter takes a node |
| 61 |
; and returns a nodeset which is the result of the corresponding query |
| 62 |
; relative to that node. A converter can also be called on a set of |
| 63 |
; nodes. In that case it returns a union of the corresponding queries over |
| 64 |
; each node in the set. The union is easily implemented as a list |
| 65 |
; append operation as all nodes in a SXML tree are considered |
| 66 |
; distinct, by XPath conventions. We also preserve the order of the |
| 67 |
; members in the union. Query combinators are high-order functions: |
| 68 |
; they take converter(s) (which is a Node|Nodeset -> Nodeset function) |
| 69 |
; and compose or otherwise combine them. We will be concerned with |
| 70 |
; only relative location paths [XPath]: an absolute location path is a |
| 71 |
; relative path applied to the root node. |
| 72 |
; |
| 73 |
; Similarly to XPath, SXPath defines full and abbreviated notations |
| 74 |
; for location paths. In both cases, the abbreviated notation can be |
| 75 |
; mechanically expanded into the full form by simple rewriting |
| 76 |
; rules. In case of SXPath the corresponding rules are given as |
| 77 |
; comments to a sxpath function, below. The regression test suite at |
| 78 |
; the end of this file shows a representative sample of SXPaths in |
| 79 |
; both notations, juxtaposed with the corresponding XPath |
| 80 |
; expressions. Most of the samples are borrowed literally from the |
| 81 |
; XPath specification, while the others are adjusted for our running |
| 82 |
; example, tree1. |
| 83 |
; |
| 84 |
|
| 85 |
|
| 86 |
;============================================================================= |
| 87 |
; Basic converters and applicators |
| 88 |
; A converter is a function |
| 89 |
; type Converter = Node|Nodeset -> Nodeset |
| 90 |
; A converter can also play a role of a predicate: in that case, if a |
| 91 |
; converter, applied to a node or a nodeset, yields a non-empty |
| 92 |
; nodeset, the converter-predicate is deemed satisfied. Throughout |
| 93 |
; this file a nil nodeset is equivalent to #f in denoting a failure. |
| 94 |
|
| 95 |
; Returns #t if given object is a nodeset |
| 96 |
(define (nodeset? x) |
| 97 |
(or (and (pair? x) (not (symbol? (car x)))) (null? x))) |
| 98 |
|
| 99 |
; If x is a nodeset - returns it as is, otherwise wrap it in a list. |
| 100 |
(define (as-nodeset x) |
| 101 |
(if (nodeset? x) x (list x))) |
| 102 |
|
| 103 |
;----------------------------------------------------------------------------- |
| 104 |
; Node test |
| 105 |
; The following functions implement 'Node test's as defined in |
| 106 |
; Sec. 2.3 of XPath document. A node test is one of the components of a |
| 107 |
; location step. It is also a converter-predicate in SXPath. |
| 108 |
|
| 109 |
; Predicate which returns #t if <obj> is SXML element, otherwise returns #f. |
| 110 |
(define (sxml:element? obj) |
| 111 |
(and (pair? obj) |
| 112 |
(symbol? (car obj)) |
| 113 |
(not (memq (car obj) |
| 114 |
; '(@ @@ *PI* *COMMENT* *ENTITY* *NAMESPACES*) |
| 115 |
; the line above is a workaround for old SXML |
| 116 |
'(@ @@ *PI* *COMMENT* *ENTITY*))))) |
| 117 |
|
| 118 |
; The function ntype-names?? takes a list of acceptable node names as a |
| 119 |
; criterion and returns a function, which, when applied to a node, |
| 120 |
; will return #t if the node name is present in criterion list and #f |
| 121 |
; othervise. |
| 122 |
; ntype-names?? :: ListOfNames -> Node -> Boolean |
| 123 |
(define (ntype-names?? crit) |
| 124 |
(lambda(node) |
| 125 |
(and (pair? node) |
| 126 |
(memq (car node) crit)))) |
| 127 |
|
| 128 |
; The function ntype?? takes a type criterion and returns |
| 129 |
; a function, which, when applied to a node, will tell if the node satisfies |
| 130 |
; the test. |
| 131 |
; ntype?? :: Crit -> Node -> Boolean |
| 132 |
; |
| 133 |
; The criterion 'crit' is |
| 134 |
; one of the following symbols: |
| 135 |
; id - tests if the Node has the right name (id) |
| 136 |
; @ - tests if the Node is an <attributes-list> |
| 137 |
; * - tests if the Node is an <Element> |
| 138 |
; *text* - tests if the Node is a text node |
| 139 |
; *data* - tests if the Node is a data node |
| 140 |
; (text, number, boolean, etc., but not pair) |
| 141 |
; *PI* - tests if the Node is a PI node |
| 142 |
; *COMMENT* - tests if the Node is a COMMENT node |
| 143 |
; *ENTITY* - tests if the Node is a ENTITY node |
| 144 |
; *any* - #t for any type of Node |
| 145 |
(define (ntype?? crit) |
| 146 |
(case crit |
| 147 |
((*) sxml:element?) |
| 148 |
((*any*) (lambda (node) #t)) |
| 149 |
((*text*) (lambda (node) (string? node))) |
| 150 |
((*data*) (lambda (node) (not (pair? node)))) |
| 151 |
(else (lambda (node) (and (pair? node) (eq? crit (car node))))) |
| 152 |
)) |
| 153 |
|
| 154 |
; This function takes a namespace-id, and returns a predicate |
| 155 |
; Node -> Boolean, which is #t for nodes with this very namespace-id. |
| 156 |
; ns-id is a string |
| 157 |
; (ntype-namespace-id?? #f) will be #t for nodes with non-qualified names. |
| 158 |
(define (ntype-namespace-id?? ns-id) |
| 159 |
(lambda (node) |
| 160 |
(and (pair? node) |
| 161 |
(not (memq (car node) |
| 162 |
'(@ @@ *PI* *COMMENT* *ENTITY*))) |
| 163 |
(let ((nm (symbol->string (car node)))) |
| 164 |
(cond |
| 165 |
((string-rindex nm #\:) |
| 166 |
=> (lambda (pos) |
| 167 |
(and |
| 168 |
(= pos (string-length ns-id)) |
| 169 |
(string-prefix? ns-id nm)))) |
| 170 |
(else (not ns-id))))))) |
| 171 |
;^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ |
| 172 |
|
| 173 |
; This function takes a predicate and returns it inverted |
| 174 |
; That is if the given predicate yelds #f or '() the inverted one |
| 175 |
; yields the given node (#t) and vice versa. |
| 176 |
(define (sxml:invert pred) |
| 177 |
(lambda(node) |
| 178 |
(case (pred node) |
| 179 |
((#f '()) node) |
| 180 |
(else #f)))) |
| 181 |
|
| 182 |
; Curried equivalence converter-predicates |
| 183 |
(define (node-eq? other) |
| 184 |
(lambda (node) |
| 185 |
(eq? other node))) |
| 186 |
|
| 187 |
(define (node-equal? other) |
| 188 |
(lambda (node) |
| 189 |
(equal? other node))) |
| 190 |
|
| 191 |
; node-pos:: N -> Nodeset -> Nodeset, or |
| 192 |
; node-pos:: N -> Converter |
| 193 |
; Select the N'th element of a Nodeset and return as a singular Nodeset; |
| 194 |
; Return an empty nodeset if the Nth element does not exist. |
| 195 |
; ((node-pos 1) Nodeset) selects the node at the head of the Nodeset, |
| 196 |
; if exists; ((node-pos 2) Nodeset) selects the Node after that, if |
| 197 |
; exists. |
| 198 |
; N can also be a negative number: in that case the node is picked from |
| 199 |
; the tail of the list. |
| 200 |
; ((node-pos -1) Nodeset) selects the last node of a non-empty nodeset; |
| 201 |
; ((node-pos -2) Nodeset) selects the last but one node, if exists. |
| 202 |
(define (node-pos n) |
| 203 |
(lambda (nodeset) |
| 204 |
(cond |
| 205 |
((not (nodeset? nodeset)) '()) |
| 206 |
((null? nodeset) nodeset) |
| 207 |
((eqv? n 1) (list (car nodeset))) |
| 208 |
((negative? n) ((node-pos (+ n 1 (length nodeset))) nodeset)) |
| 209 |
(else |
| 210 |
(assert (positive? n)) |
| 211 |
((node-pos (-- n)) (cdr nodeset)))))) |
| 212 |
|
| 213 |
; filter:: Converter -> Converter |
| 214 |
; A filter applicator, which introduces a filtering context. The argument |
| 215 |
; converter is considered a predicate, with either #f or nil result meaning |
| 216 |
; failure. |
| 217 |
(define (sxml:filter pred?) |
| 218 |
(lambda (lst) ; a nodeset or a node (will be converted to a singleton nset) |
| 219 |
(let loop ((lst (as-nodeset lst)) |
| 220 |
(res '())) |
| 221 |
(if (null? lst) |
| 222 |
(reverse res) |
| 223 |
(let ((pred-result (pred? (car lst)))) |
| 224 |
(loop (cdr lst) |
| 225 |
(if (and pred-result (not (null? pred-result))) |
| 226 |
(cons (car lst) res) |
| 227 |
res))))))) |
| 228 |
|
| 229 |
; take-until:: Converter -> Converter, or |
| 230 |
; take-until:: Pred -> Node|Nodeset -> Nodeset |
| 231 |
; Given a converter-predicate and a nodeset, apply the predicate to |
| 232 |
; each element of the nodeset, until the predicate yields anything but #f or |
| 233 |
; nil. Return the elements of the input nodeset that have been processed |
| 234 |
; till that moment (that is, which fail the predicate). |
| 235 |
; take-until is a variation of the filter above: take-until passes |
| 236 |
; elements of an ordered input set till (but not including) the first |
| 237 |
; element that satisfies the predicate. |
| 238 |
; The nodeset returned by ((take-until (not pred)) nset) is a subset -- |
| 239 |
; to be more precise, a prefix -- of the nodeset returned by |
| 240 |
; ((filter pred) nset) |
| 241 |
(define (take-until pred?) |
| 242 |
(lambda (lst) ; a nodeset or a node (will be converted to a singleton nset) |
| 243 |
(let loop ((lst (as-nodeset lst))) |
| 244 |
(if (null? lst) lst |
| 245 |
(let ((pred-result (pred? (car lst)))) |
| 246 |
(if (and pred-result (not (null? pred-result))) |
| 247 |
'() |
| 248 |
(cons (car lst) (loop (cdr lst))))) |
| 249 |
)))) |
| 250 |
|
| 251 |
; take-after:: Converter -> Converter, or |
| 252 |
; take-after:: Pred -> Node|Nodeset -> Nodeset |
| 253 |
; Given a converter-predicate and a nodeset, apply the predicate to |
| 254 |
; each element of the nodeset, until the predicate yields anything but #f or |
| 255 |
; nil. Return the elements of the input nodeset that have not been processed: |
| 256 |
; that is, return the elements of the input nodeset that follow the first |
| 257 |
; element that satisfied the predicate. |
| 258 |
; take-after along with take-until partition an input nodeset into three |
| 259 |
; parts: the first element that satisfies a predicate, all preceding |
| 260 |
; elements and all following elements. |
| 261 |
(define (take-after pred?) |
| 262 |
(lambda (lst) ; a nodeset or a node (will be converted to a singleton nset) |
| 263 |
(let loop ((lst (as-nodeset lst))) |
| 264 |
(if (null? lst) lst |
| 265 |
(let ((pred-result (pred? (car lst)))) |
| 266 |
(if (and pred-result (not (null? pred-result))) |
| 267 |
(cdr lst) |
| 268 |
(loop (cdr lst)))) |
| 269 |
)))) |
| 270 |
|
| 271 |
; Apply proc to each element of lst and return the list of results. |
| 272 |
; if proc returns a nodeset, splice it into the result |
| 273 |
; |
| 274 |
; From another point of view, map-union is a function Converter->Converter, |
| 275 |
; which places an argument-converter in a joining context. |
| 276 |
(define (map-union proc lst) |
| 277 |
(if (null? lst) lst |
| 278 |
(let ((proc-res (proc (car lst)))) |
| 279 |
((if (nodeset? proc-res) append cons) |
| 280 |
proc-res (map-union proc (cdr lst)))))) |
| 281 |
|
| 282 |
; node-reverse :: Converter, or |
| 283 |
; node-reverse:: Node|Nodeset -> Nodeset |
| 284 |
; Reverses the order of nodes in the nodeset |
| 285 |
; This basic converter is needed to implement a reverse document order |
| 286 |
; (see the XPath Recommendation). |
| 287 |
(define node-reverse |
| 288 |
(lambda (node-or-nodeset) |
| 289 |
(if (not (nodeset? node-or-nodeset)) (list node-or-nodeset) |
| 290 |
(reverse node-or-nodeset)))) |
| 291 |
|
| 292 |
; node-trace:: String -> Converter |
| 293 |
; (node-trace title) is an identity converter. In addition it prints out |
| 294 |
; a node or nodeset it is applied to, prefixed with the 'title'. |
| 295 |
; This converter is very useful for debugging. |
| 296 |
(define (node-trace title) |
| 297 |
(lambda (node-or-nodeset) |
| 298 |
(cout nl "-->" title " :") |
| 299 |
(pp node-or-nodeset) |
| 300 |
node-or-nodeset)) |
| 301 |
|
| 302 |
|
| 303 |
;------------------------------------------------------------------------------ |
| 304 |
; Converter combinators |
| 305 |
; |
| 306 |
; Combinators are higher-order functions that transmogrify a converter |
| 307 |
; or glue a sequence of converters into a single, non-trivial |
| 308 |
; converter. The goal is to arrive at converters that correspond to |
| 309 |
; XPath location paths. |
| 310 |
; |
| 311 |
; From a different point of view, a combinator is a fixed, named |
| 312 |
; _pattern_ of applying converters. Given below is a complete set of |
| 313 |
; such patterns that together implement XPath location path |
| 314 |
; specification. As it turns out, all these combinators can be built |
| 315 |
; from a small number of basic blocks: regular functional composition, |
| 316 |
; map-union and filter applicators, and the nodeset union. |
| 317 |
|
| 318 |
|
| 319 |
|
| 320 |
; select-kids:: Pred -> Node -> Nodeset |
| 321 |
; Given a Node, return an (ordered) subset its children that satisfy |
| 322 |
; the Pred (a converter, actually) |
| 323 |
; select-kids:: Pred -> Nodeset -> Nodeset |
| 324 |
; The same as above, but select among children of all the nodes in |
| 325 |
; the Nodeset |
| 326 |
; |
| 327 |
; More succinctly, the signature of this function is |
| 328 |
; select-kids:: Converter -> Converter |
| 329 |
(define (select-kids test-pred?) |
| 330 |
(lambda (node) ; node or node-set |
| 331 |
(cond |
| 332 |
((null? node) node) |
| 333 |
((not (pair? node)) '()) ; No children |
| 334 |
((symbol? (car node)) |
| 335 |
((sxml:filter test-pred?) (cdr node))) ; it's a single node |
| 336 |
(else (map-union (select-kids test-pred?) node))))) |
| 337 |
|
| 338 |
|
| 339 |
; node-self:: Pred -> Node -> Nodeset, or |
| 340 |
; node-self:: Converter -> Converter |
| 341 |
; Similar to select-kids but apply to the Node itself rather |
| 342 |
; than to its children. The resulting Nodeset will contain either one |
| 343 |
; component, or will be empty (if the Node failed the Pred). |
| 344 |
(define node-self sxml:filter) |
| 345 |
|
| 346 |
|
| 347 |
; node-join:: [LocPath] -> Node|Nodeset -> Nodeset, or |
| 348 |
; node-join:: [Converter] -> Converter |
| 349 |
; join the sequence of location steps or paths as described |
| 350 |
; in the title comments above. |
| 351 |
(define (node-join . selectors) |
| 352 |
(lambda (nodeset) ; Nodeset or node |
| 353 |
(let loop ((nodeset nodeset) (selectors selectors)) |
| 354 |
(if (null? selectors) nodeset |
| 355 |
(loop |
| 356 |
(if (nodeset? nodeset) |
| 357 |
(map-union (car selectors) nodeset) |
| 358 |
((car selectors) nodeset)) |
| 359 |
(cdr selectors)))))) |
| 360 |
|
| 361 |
|
| 362 |
; node-reduce:: [LocPath] -> Node|Nodeset -> Nodeset, or |
| 363 |
; node-reduce:: [Converter] -> Converter |
| 364 |
; A regular functional composition of converters. |
| 365 |
; From a different point of view, |
| 366 |
; ((apply node-reduce converters) nodeset) |
| 367 |
; is equivalent to |
| 368 |
; (foldl apply nodeset converters) |
| 369 |
; i.e., folding, or reducing, a list of converters with the nodeset |
| 370 |
; as a seed. |
| 371 |
(define (node-reduce . converters) |
| 372 |
(lambda (nodeset) ; Nodeset or node |
| 373 |
(let loop ((nodeset nodeset) (converters converters)) |
| 374 |
(if (null? converters) nodeset |
| 375 |
(loop ((car converters) nodeset) (cdr converters)))))) |
| 376 |
|
| 377 |
|
| 378 |
; node-or:: [Converter] -> Converter |
| 379 |
; This combinator applies all converters to a given node and |
| 380 |
; produces the union of their results. |
| 381 |
; This combinator corresponds to a union, '|' operation for XPath |
| 382 |
; location paths. |
| 383 |
; (define (node-or . converters) |
| 384 |
; (lambda (node-or-nodeset) |
| 385 |
; (if (null? converters) node-or-nodeset |
| 386 |
; (append |
| 387 |
; ((car converters) node-or-nodeset) |
| 388 |
; ((apply node-or (cdr converters)) node-or-nodeset))))) |
| 389 |
; More optimal implementation follows |
| 390 |
(define (node-or . converters) |
| 391 |
(lambda (node-or-nodeset) |
| 392 |
(let loop ((result '()) (converters converters)) |
| 393 |
(if (null? converters) result |
| 394 |
(loop (append result (or ((car converters) node-or-nodeset) '())) |
| 395 |
(cdr converters)))))) |
| 396 |
|
| 397 |
|
| 398 |
; node-closure:: Converter -> Converter |
| 399 |
; Select all _descendants_ of a node that satisfy a converter-predicate. |
| 400 |
; This combinator is similar to select-kids but applies to |
| 401 |
; grand... children as well. |
| 402 |
; This combinator implements the "descendant::" XPath axis |
| 403 |
; Conceptually, this combinator can be expressed as |
| 404 |
; (define (node-closure f) |
| 405 |
; (node-or |
| 406 |
; (select-kids f) |
| 407 |
; (node-reduce (select-kids (ntype?? '*)) (node-closure f)))) |
| 408 |
; This definition, as written, looks somewhat like a fixpoint, and it |
| 409 |
; will run forever. It is obvious however that sooner or later |
| 410 |
; (select-kids (ntype?? '*)) will return an empty nodeset. At |
| 411 |
; this point further iterations will no longer affect the result and |
| 412 |
; can be stopped. |
| 413 |
(define (node-closure test-pred?) |
| 414 |
(lambda (node) ; Nodeset or node |
| 415 |
(let loop ((parent node) (result '())) |
| 416 |
(if (null? parent) result |
| 417 |
(loop (sxml:child-elements parent) |
| 418 |
(append result |
| 419 |
((select-kids test-pred?) parent))) |
| 420 |
)))) |
| 421 |
|
| 422 |
;============================================================================= |
| 423 |
; Unified with sxpath-ext and sxml-tools |
| 424 |
|
| 425 |
; According to XPath specification 2.3, this test is true for any |
| 426 |
; XPath node. |
| 427 |
; For SXML auxiliary lists and lists of attributes has to be excluded. |
| 428 |
(define (sxml:node? node) |
| 429 |
(not (and |
| 430 |
(pair? node) |
| 431 |
(memq (car node) '(@ @@))))) |
| 432 |
|
| 433 |
; Returns the list of attributes for a given SXML node |
| 434 |
; Empty list is returned if the given node os not an element, |
| 435 |
; or if it has no list of attributes |
| 436 |
(define (sxml:attr-list obj) |
| 437 |
(if (and (sxml:element? obj) |
| 438 |
(not (null? (cdr obj))) |
| 439 |
(pair? (cadr obj)) |
| 440 |
(eq? '@ (caadr obj))) |
| 441 |
(cdadr obj) |
| 442 |
'())) |
| 443 |
|
| 444 |
; Attribute axis |
| 445 |
(define (sxml:attribute test-pred?) |
| 446 |
(let ((fltr (sxml:filter test-pred?))) |
| 447 |
(lambda (node) |
| 448 |
(fltr |
| 449 |
(apply append |
| 450 |
(map |
| 451 |
sxml:attr-list |
| 452 |
(as-nodeset node))))))) |
| 453 |
|
| 454 |
; Child axis |
| 455 |
; This function is similar to 'select-kids', but it returns an empty |
| 456 |
; child-list for PI, Comment and Entity nodes |
| 457 |
(define (sxml:child test-pred?) |
| 458 |
(lambda (node) ; node or node-set |
| 459 |
(cond |
| 460 |
((null? node) node) |
| 461 |
((not (pair? node)) '()) ; No children |
| 462 |
((memq (car node) '(*PI* *COMMENT* *ENTITY*)) ; PI, Comment or Entity |
| 463 |
'()) ; No children |
| 464 |
((symbol? (car node)) ; it's a single node |
| 465 |
((sxml:filter test-pred?) (cdr node))) |
| 466 |
(else (map-union (sxml:child test-pred?) node))))) |
| 467 |
|
| 468 |
; Parent axis |
| 469 |
; Given a predicate, it returns a function |
| 470 |
; RootNode -> Converter |
| 471 |
; which which yields a |
| 472 |
; node -> parent |
| 473 |
; converter then applied to a rootnode. |
| 474 |
; Thus, such a converter may be constructed using |
| 475 |
; ((sxml:parent test-pred) rootnode) |
| 476 |
; and returns a parent of a node it is applied to. |
| 477 |
; If applied to a nodeset, it returns the |
| 478 |
; list of parents of nodes in the nodeset. The rootnode does not have |
| 479 |
; to be the root node of the whole SXML tree -- it may be a root node |
| 480 |
; of a branch of interest. |
| 481 |
; The parent:: axis can be used with any SXML node. |
| 482 |
(define (sxml:parent test-pred?) |
| 483 |
(lambda (root-node) ; node or nodeset |
| 484 |
(lambda (node) ; node or nodeset |
| 485 |
(if (nodeset? node) |
| 486 |
(map-union ((sxml:parent test-pred?) root-node) node) |
| 487 |
(let rpt ((pairs |
| 488 |
(apply append |
| 489 |
(map |
| 490 |
(lambda (root-n) |
| 491 |
(map |
| 492 |
(lambda (arg) (cons arg root-n)) |
| 493 |
(append |
| 494 |
(sxml:attr-list root-n) |
| 495 |
(sxml:child-nodes root-n)))) |
| 496 |
(as-nodeset root-node))) |
| 497 |
)) |
| 498 |
(if (null? pairs) |
| 499 |
'() |
| 500 |
(let ((pair (car pairs))) |
| 501 |
(if (eq? (car pair) node) |
| 502 |
((sxml:filter test-pred?) (list (cdr pair))) |
| 503 |
(rpt (append |
| 504 |
(map |
| 505 |
(lambda (arg) (cons arg (car pair))) |
| 506 |
(append |
| 507 |
(sxml:attr-list (car pair)) |
| 508 |
(sxml:child-nodes (car pair)))) |
| 509 |
(cdr pairs) |
| 510 |
)))))))))) |
| 511 |
|
| 512 |
|
| 513 |
;============================================================================= |
| 514 |
; Popular short cuts |
| 515 |
|
| 516 |
; node-parent:: RootNode -> Converter |
| 517 |
; (node-parent rootnode) yields a converter that returns a parent of a |
| 518 |
; node it is applied to. If applied to a nodeset, it returns the list |
| 519 |
; of parents of nodes in the nodeset. |
| 520 |
; Given the notation of Philip Wadler's paper on semantics of XSLT, |
| 521 |
; parent(x) = { y | y=subnode*(root), x=subnode(y) } |
| 522 |
; Therefore, node-parent is not the fundamental converter: it can be |
| 523 |
; expressed through the existing ones. Yet node-parent is a rather |
| 524 |
; convenient converter. It corresponds to a parent:: axis of SXPath. |
| 525 |
; |
| 526 |
; Please note: this function is provided for backward compatibility |
| 527 |
; with SXPath/SXPathlib ver. 3.5.x.x and earlier. |
| 528 |
; Now it's a particular case of 'sxml:parent' application: |
| 529 |
(define node-parent (sxml:parent (ntype?? '*any*))) |
| 530 |
|
| 531 |
(define sxml:child-nodes (sxml:child sxml:node?)) |
| 532 |
|
| 533 |
(define sxml:child-elements (select-kids sxml:element?)) |
| 534 |
|