]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - src/xml/resource-c14n.lisp
perf(tmdm): index association normalization merge candidates
[topic-maps.git] / src / xml / resource-c14n.lisp
1 (in-package #:topic-maps.xml)
2
3 ;;; W3C Canonical XML 1.0 (2001-03-15), restricted to the XTM 2.0
4 ;;; 4.16.3 node set. Not an arbitrary XPath, Exclusive C14N or C14N 1.1 API.
5 (defparameter +xml-namespace+ "http://www.w3.org/XML/1998/namespace")
6 (defparameter +xmlns-namespace+ "http://www.w3.org/2000/xmlns/")
7 (defparameter +xtm-namespace+ "http://www.topicmaps.org/xtm/")
8
9 (define-condition canonicalization-error (error)
10 ((code :initarg :code :reader canonicalization-error-code)
11 (detail :initarg :detail :reader canonicalization-error-detail))
12 (:report (lambda (c s) (format s "XML canonicalization ~S: ~A"
13 (canonicalization-error-code c) (canonicalization-error-detail c)))))
14
15 (defstruct (canonical-context (:constructor %make-canonical-context (document))
16 (:copier nil) (:conc-name %canonical-context-))
17 ;; Private DOM, built only from qualified raw bytes; never returned for mutation.
18 (document nil :read-only t))
19
20 (defun parse-canonical-context (bytes)
21 "Parse original XML octets into an opaque namespace/QName-preserving context.
22 This additional entry point does not change PARSE-OCTETS or global SAX settings.
23 The existing qualification markers, closed handler, DOCTYPE prohibition, fresh
24 DTD cache and non-returning external-resource denial remain mandatory."
25 (check-type bytes (vector (unsigned-byte 8)))
26 (unless (and (boundp 'cxml::*topic-maps-encoding-patch*)
27 (equal (symbol-value 'cxml::*topic-maps-encoding-patch*) "19d0b-1")
28 (boundp 'runes-encoding::*topic-maps-encoding-patch*)
29 (equal (symbol-value 'runes-encoding::*topic-maps-encoding-patch*) "19d0b-1"))
30 (error 'unqualified-parser))
31 (let ((sax:*namespace-processing* t) (sax:*include-xmlns-attributes* t)
32 (sax:*use-xmlns-namespace* t) (cxml:*catalog* nil)
33 (cxml:*cache-all-dtds* nil) (cxml:*dtd-cache* (cxml:make-dtd-cache)))
34 (%make-canonical-context
35 (cxml:parse-octets bytes
36 (make-instance 'closed-handler :chained-handler (cxml-dom:make-dom-builder))
37 :validate nil :disallow-internal-subset t :entity-resolver #'deny-external-resource))))
38
39 (defun %dom-list (nodes)
40 (loop for i below (dom:length nodes) collect (dom:item nodes i)))
41 (defun %element-p (node) (eq (dom:node-type node) :element))
42 (defun %namespace (node) (or (dom:namespace-uri node) ""))
43 (defun %prefix (node) (or (dom:prefix node) ""))
44 (defun %namespace-attribute-p (node) (string= (%namespace node) +xmlns-namespace+))
45 (defun %attributes (element)
46 (remove-if #'%namespace-attribute-p (%dom-list (dom:attributes element))))
47 (defun %children (node) (%dom-list (dom:child-nodes node)))
48 (defun %elements (nodes)
49 (loop for node in nodes when (%element-p node)
50 append (cons node (%elements (%children node)))))
51 (defun %resource-elements (context)
52 (remove-if-not (lambda (e) (and (string= (%namespace e) +xtm-namespace+)
53 (string= (dom:local-name e) "resourceData")))
54 (%elements (%children (%canonical-context-document context)))))
55
56 (defun resource-data-count (context)
57 "Number of XTM-namespace resourceData elements in document order. No XTM validation."
58 (check-type context canonical-context)
59 (length (%resource-elements context)))
60
61 (defun %absolute-namespace-p (uri)
62 ;; C14N 1.0 2.1 prohibits relative namespace URIs, even unused ones.
63 ;; XML namespace well-formedness and character validity belong to the parser.
64 (let ((colon (position #\: uri)))
65 (and colon (plusp colon) (find (char uri 0) "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")
66 (every (lambda (c) (find c "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+-."))
67 (subseq uri 1 colon)))))
68 (defun %check-namespace-uris (document)
69 (dolist (e (%elements (%children document)))
70 (dolist (a (%dom-list (dom:attributes e)))
71 (when (and (%namespace-attribute-p a) (plusp (length (dom:value a)))
72 (not (%absolute-namespace-p (dom:value a))))
73 (error 'canonicalization-error :code :relative-namespace-uri :detail (dom:value a))))))
74
75 (defun %in-scope-namespaces (element)
76 ;; DOM stores declarations, not the XPath namespace axis. Reconstruct that
77 ;; axis from nearest ancestors, preserving the original prefix and URI.
78 (let ((seen nil) (bindings nil))
79 (loop for e = element then (dom:parent-node e) while (and e (%element-p e)) do
80 (dolist (a (%dom-list (dom:attributes e)))
81 (when (%namespace-attribute-p a)
82 (let ((prefix (if (string= (dom:name a) "xmlns") "" (dom:local-name a))))
83 (unless (member prefix seen :test #'string=)
84 (push prefix seen)
85 (unless (zerop (length (dom:value a))) (push (cons prefix (dom:value a)) bindings)))))))
86 bindings))
87 (defun %used-namespace-pairs (elements)
88 ;; XTM's filter is over the ENTIRE selected node set, not just visibly used
89 ;; prefixes on the current element. QName-valued attribute values do not count.
90 (remove-duplicates
91 (loop for e in elements append
92 (loop for n in (cons e (%attributes e))
93 unless (zerop (length (%namespace n))) collect (cons (%prefix n) (%namespace n))))
94 :test #'equal))
95 (defun %selected-namespaces (element used)
96 (sort (remove-if-not (lambda (binding)
97 (and (not (equal binding (cons "xml" +xml-namespace+)))
98 (member binding used :test #'equal)))
99 (%in-scope-namespaces element))
100 #'string< :key #'car))
101 (defun %apex-attributes (element)
102 ;; C14N 1.0 2.4: inherit nearest xml:* attributes when the parent is omitted.
103 ;; This is not C14N 1.1: xml:id/base are NOT given 1.1 special treatment.
104 (let* ((attributes (%attributes element))
105 (seen (loop for a in attributes when (string= (%namespace a) +xml-namespace+)
106 collect (dom:local-name a))))
107 (loop for e = (dom:parent-node element) then (dom:parent-node e)
108 while (and e (%element-p e)) do
109 (dolist (a (%attributes e))
110 (when (and (string= (%namespace a) +xml-namespace+)
111 (not (member (dom:local-name a) seen :test #'string=)))
112 (push (dom:local-name a) seen) (push a attributes))))
113 attributes))
114 (defun %attribute-less-p (a b)
115 (or (string< (%namespace a) (%namespace b))
116 (and (string= (%namespace a) (%namespace b))
117 (string< (dom:local-name a) (dom:local-name b)))))
118 (defun %write-canonical-value (value stream attribute-p)
119 (loop for c across value do
120 (let ((escape (case c
121 (#\& "&amp;") (#\< "&lt;")
122 (#\> (unless attribute-p "&gt;"))
123 (#\" (when attribute-p "&quot;"))
124 (#\Return "&#xD;")
125 (#\Tab (when attribute-p "&#x9;"))
126 (#\Newline (when attribute-p "&#xA;")))))
127 (if escape (write-string escape stream) (write-char c stream)))))
128 (defun %write-canonical-attribute (name value stream)
129 (write-char #\Space stream) (write-string name stream) (write-string "=\"" stream)
130 (%write-canonical-value value stream t) (write-char #\" stream))
131
132 (defun %canonical-subtrees (nodes)
133 "Internal engine: all element/attribute/text descendants, XTM namespace filter.
134 NODES are the apex children of the omitted resourceData container."
135 (let ((used (%used-namespace-pairs (%elements nodes))))
136 (with-output-to-string (stream)
137 (labels ((emit (node parent-namespaces apex-p)
138 (case (dom:node-type node)
139 (:element
140 (let ((namespaces (%selected-namespaces node used)))
141 (write-char #\< stream) (write-string (dom:tag-name node) stream)
142 ;; Namespace absence refers to the nearest SELECTED parent,
143 ;; not a cumulative rendered-prefix table (C14N 2.3).
144 (when (and (not (assoc "" namespaces :test #'string=))
145 (assoc "" parent-namespaces :test #'string=))
146 (%write-canonical-attribute "xmlns" "" stream))
147 (dolist (binding namespaces)
148 (unless (equal binding (assoc (car binding) parent-namespaces :test #'string=))
149 (%write-canonical-attribute
150 (if (zerop (length (car binding))) "xmlns" (concatenate 'string "xmlns:" (car binding)))
151 (cdr binding) stream)))
152 (dolist (a (sort (if apex-p (%apex-attributes node) (%attributes node)) #'%attribute-less-p))
153 (%write-canonical-attribute (dom:name a) (dom:value a) stream))
154 (write-char #\> stream)
155 (dolist (child (%children node)) (emit child namespaces nil))
156 (write-string "</" stream) (write-string (dom:tag-name node) stream) (write-char #\> stream)))
157 ((:text :cdata-section) (%write-canonical-value (dom:data node) stream nil))
158 ;; PI and comments are NOT selected by XTM 4.16.3.
159 ((:processing-instruction :comment) nil)
160 (otherwise (error 'canonicalization-error :code :unexpected-node-type :detail (dom:node-type node))))))
161 (dolist (node nodes) (emit node nil t))))))
162
163 (defun canonicalize-resource-data (context &key (index 0))
164 "Return (values Unicode-string UTF-8-octets) for resourceData INDEX (zero based).
165 Selection is by expanded name and document order in the qualified opaque CONTEXT.
166 The container itself is omitted. This function does not validate XTM syntax or
167 choose a datatype, and never constructs or changes a Topic Maps model. The
168 result can be a text fragment, several apex elements, or the empty string."
169 (check-type context canonical-context)
170 (check-type index (integer 0 *))
171 (%check-namespace-uris (%canonical-context-document context))
172 (let ((element (nth index (%resource-elements context))))
173 (unless element
174 (error 'canonicalization-error :code :resource-data-index :detail index))
175 (let ((string (%canonical-subtrees (%children element))))
176 (values string (babel:string-to-octets string :encoding :utf-8 :use-bom nil)))))