Debian Codegraph @

ext/sxml/src/sxpathlib.scm

raw
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