]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - src/cxtm/canonicalizer.lisp
Implement Topic-set Scope across TMDM, CTM and CXTM
[topic-maps.git] / src / cxtm / canonicalizer.lisp
1 (in-package #:topic-maps.cxtm)
2
3 (defvar *base-locator*)
4 (defvar *locator-cache*)
5
6 (defun path-start (iri)
7 (let* ((colon (position #\: iri)) (start (if colon (1+ colon) 0)))
8 (if (and (<= (+ start 2) (length iri))
9 (string= "//" iri :start2 start :end2 (+ start 2)))
10 (or (position #\/ iri :start (+ start 2)) (length iri)) start)))
11 (defun normalized-locator (locator)
12 "CXTM 3.18, literal prefix removal, NOT RFC relative-IRI resolution."
13 (or (gethash locator *locator-cache*)
14 (setf (gethash locator *locator-cache*)
15 (nfc
16 (let ((prefix (string-right-trim "/" (subseq *base-locator* 0
17 (position-if (lambda (c) (find c "?#")) *base-locator*)))))
18 (loop
19 (when (and (<= (length prefix) (length locator))
20 (string= prefix locator :end2 (length prefix)))
21 (return (string-left-trim "/" (subseq locator (length prefix)))))
22 (let ((start (path-start prefix)))
23 (when (>= start (length prefix)) (return locator))
24 (setf prefix (string-right-trim "/"
25 (subseq prefix 0 (or (position #\/ prefix :start start :from-end t) start)))))))))))
26
27 (defun string-order (a b)
28 ;; Character CODE order, independent of a Lisp implementation's collation.
29 (loop for x across a for y across b
30 when (< (char-code x) (char-code y)) do (return-from string-order -1)
31 when (> (char-code x) (char-code y)) do (return-from string-order 1))
32 (signum (- (length a) (length b))))
33 (defun sorted (items comparison)
34 (stable-sort (copy-list items) (lambda (a b) (minusp (funcall comparison a b)))))
35 (defun set-order (a b comparison)
36 (let ((size (signum (- (length a) (length b)))))
37 (if (not (zerop size)) size
38 (loop for x in (sorted a comparison) for y in (sorted b comparison)
39 for c = (funcall comparison x y) when (not (zerop c)) return c
40 finally (return 0)))))
41 (defun locator-order (a b) (string-order (normalized-locator a) (normalized-locator b)))
42 (defun topic-order (a b)
43 (loop for getter in '(topic-subject-identifiers topic-subject-locators topic-item-identifiers)
44 for c = (set-order (funcall getter a) (funcall getter b) #'locator-order)
45 when (not (zerop c)) return c finally (return 0)))
46 (defun name-order (a b)
47 (let ((c (string-order (nfc (topic-name-value a)) (nfc (topic-name-value b)))))
48 (if (not (zerop c)) c
49 (let ((type (topic-order (topic-name-type a) (topic-name-type b))))
50 (if (not (zerop type)) type
51 (let ((scope (set-order (topic-name-scope a) (topic-name-scope b) #'topic-order)))
52 (if (not (zerop scope)) scope (topic-order (topic-name-parent a) (topic-name-parent b)))))))))
53 (defun occurrence-value-order (a b)
54 ;; TMDM 4.3/5.6: anyURI values are locators; other supported values are strings.
55 ;; CXTM 4.2 orders strings before locators, independent of their spelling.
56 (let ((iri-a (string= (occurrence-datatype a) (iri-datatype)))
57 (iri-b (string= (occurrence-datatype b) (iri-datatype))))
58 (cond ((and iri-a iri-b) (locator-order (occurrence-value a) (occurrence-value b)))
59 (iri-a 1) (iri-b -1)
60 (t (string-order (nfc (occurrence-value a)) (nfc (occurrence-value b)))))))
61 (defun occurrence-order (a b)
62 (loop for comparison in
63 (list (occurrence-value-order a b)
64 (locator-order (occurrence-datatype a) (occurrence-datatype b))
65 (topic-order (occurrence-type a) (occurrence-type b))
66 (set-order (occurrence-scope a) (occurrence-scope b) #'topic-order)
67 (topic-order (occurrence-parent a) (occurrence-parent b)))
68 when (not (zerop comparison)) return comparison finally (return 0)))
69
70 (defun role-signature-order (a b)
71 ;; In a single parent's roles set, [parent] is equal. During association
72 ;; comparison equal player/type pairs also have equal parent-comparison
73 ;; context. Comparing this prefix avoids recursive parent/roles traversal.
74 (let ((c (topic-order (association-role-player a) (association-role-player b))))
75 (if (not (zerop c)) c (topic-order (association-role-type a) (association-role-type b)))))
76 (defun association-order (a b)
77 (let ((c (topic-order (association-type a) (association-type b))))
78 (if (not (zerop c)) c
79 (let ((roles (set-order (association-roles a) (association-roles b) #'role-signature-order)))
80 ;; Parent Map is equal for all associations compared by this serializer.
81 (if (not (zerop roles)) roles
82 (set-order (association-scope a) (association-scope b) #'topic-order))))))
83 (defun role-order (a b)
84 (let ((c (role-signature-order a b)))
85 (if (not (zerop c)) c
86 (association-order (association-role-parent a) (association-role-parent b)))))
87
88 (defun require-exact-item (item type)
89 ;; A future/subclass model carrying extra properties is explicitly unsupported.
90 (unless (eq (type-of item) type)
91 (fail :unsupported-information-item (format nil "Expected exact ~S, received ~S." type (type-of item)) t)))
92 (defun require-set (items)
93 (unless (and (topic-maps.tmdm::proper-list-p items) (= (length items) (length (remove-duplicates items :test #'eq))))
94 (fail :invalid-set "An information-item collection must be a proper set.")))
95 (defun validate-map (map)
96 "Validate current model schema and referential integrity; never normalize/mutate."
97 (require-exact-item map 'topic-map)
98 (let ((topics (topic-map-topics map)) (associations (topic-map-associations map)))
99 (require-set topics) (require-set associations)
100 (labels ((reference (topic)
101 (require-exact-item topic 'topic)
102 (unless (and (eq topic (canonical-topic topic)) (member topic topics :test #'eq))
103 (fail :invalid-topic-reference "Reference must designate a current Topic in this map."))))
104 (dolist (topic topics)
105 (reference topic)
106 (unless (eq (topic-parent topic) map) (fail :invalid-parent "Topic parent mismatch."))
107 (unless (or (topic-item-identifiers topic) (topic-subject-identifiers topic) (topic-subject-locators topic))
108 (fail :unidentified-topic "CXTM 4.6 requires an identity-bearing Topic." t))
109 (dolist (getter '(topic-item-identifiers topic-subject-identifiers topic-subject-locators))
110 (let ((ids (funcall getter topic)))
111 (unless (and (every (lambda (s) (and (stringp s) (plusp (length s)))) ids)
112 (= (length ids) (length (remove-duplicates ids :test #'string=))))
113 (fail :invalid-locators "Locator properties must be sets of nonempty strings."))))
114 (require-set (topic-names topic))
115 (dolist (name (topic-names topic))
116 (require-exact-item name 'topic-name)
117 (unless (and (eq name (canonical-topic-name name)) (eq (topic-name-parent name) topic))
118 (fail :invalid-parent "Name must be current and owned by its containing Topic."))
119 (reference (topic-name-type name))
120 (require-set (topic-name-scope name)) (mapc #'reference (topic-name-scope name)))
121 (require-set (topic-occurrences topic))
122 (dolist (item (topic-occurrences topic))
123 (require-exact-item item 'occurrence)
124 (unless (and (eq item (canonical-occurrence item)) (eq (occurrence-parent item) topic))
125 (fail :invalid-parent "Occurrence must be current and owned by its containing Topic."))
126 (reference (occurrence-type item))
127 (require-set (occurrence-scope item)) (mapc #'reference (occurrence-scope item))
128 (unless (topic-maps.tmdm::absolute-locator-p (occurrence-datatype item))
129 (fail :invalid-occurrence-datatype "Datatype must be an absolute locator."))
130 (when (and (string= (occurrence-datatype item) (integer-datatype))
131 (not (integer-lexical-p (occurrence-value item))))
132 (fail :invalid-integer-value "Occurrence value is not an xsd:integer lexical form."))
133 (when (and (string= (occurrence-datatype item) (decimal-datatype))
134 (not (decimal-lexical-p (occurrence-value item))))
135 (fail :invalid-decimal-value "Occurrence value is not an xsd:decimal lexical form."))
136 (when (string= (occurrence-datatype item) (date-datatype))
137 (unless (date-lexical-p (occurrence-value item))
138 (fail :invalid-date-value "Occurrence value is not a valid XSD 1.0 date."))
139 (unless (canonical-date-lexical-form (occurrence-value item))
140 (fail :date-timezone-canonicalization "XSD date recoverable-timezone canonicalization is outside this slice." t)))
141 (when (string= (occurrence-datatype item) (datetime-datatype))
142 (unless (datetime-lexical-p (occurrence-value item))
143 (fail :invalid-datetime-value "Occurrence value is not a valid XSD 1.0 dateTime."))
144 (multiple-value-bind (value reason) (canonical-datetime-lexical-form (occurrence-value item))
145 (unless value (fail (if (eq reason :unsupported-bce-timezone-rollover)
146 :datetime-bce-timezone-rollover :datetime-leap-second-context)
147 "DateTime BCE rollover/leap-second context is outside this canonical subset." t))))
148 (when (and (string= (occurrence-datatype item) (iri-datatype))
149 (not (topic-maps.tmdm::absolute-locator-p (occurrence-value item))))
150 (fail :invalid-occurrence-value "IRI-valued Occurrences must store an absolute locator."))
151 (let ((ids (occurrence-item-identifiers item)))
152 (unless (and (every #'topic-maps.tmdm::absolute-locator-p ids)
153 (= (length ids) (length (remove-duplicates ids :test #'string=))))
154 (fail :invalid-locators "Occurrence identifiers must be an absolute locator set.")))))
155 (dolist (a associations)
156 (require-exact-item a 'association)
157 (unless (and (eq a (canonical-association a)) (eq (association-parent a) map))
158 (fail :invalid-parent "Association must be current and owned by this map."))
159 (reference (association-type a))
160 (require-set (association-scope a)) (mapc #'reference (association-scope a))
161 (require-set (association-roles a))
162 (unless (association-roles a) (fail :empty-association "Association requires Roles."))
163 (dolist (r (association-roles a))
164 (require-exact-item r 'association-role)
165 (unless (and (eq r (canonical-association-role r)) (eq (association-role-parent r) a))
166 (fail :invalid-parent "Role must be current and owned by its Association."))
167 (reference (association-role-type r)) (reference (association-role-player r)))))))
168
169 (defun xml-text (text out)
170 (loop for c across (nfc text) for n = (char-code c) do
171 (unless (or (member n '(9 10 13)) (<= 32 n #xd7ff) (<= #xe000 n #xfffd) (<= #x10000 n #x10ffff))
172 (fail :xml-character (format nil "U+~4,'0X cannot be represented in XML 1.0." n)))
173 (case c
174 (#\& (write-string "&amp;" out)) (#\< (write-string "&lt;" out))
175 (#\> (write-string "&gt;" out)) (#\Return (write-string "&#xD;" out))
176 (otherwise (write-char c out)))))
177 (defun emit-locators (tag locators out)
178 (when locators
179 (format out "<~A>~%" tag)
180 (dolist (locator (sorted locators #'locator-order))
181 (write-string "<locator>" out) (xml-text (normalized-locator locator) out)
182 (format out "</locator>~%"))
183 (format out "</~A>~%" tag)))
184
185 (defun emit-scope (themes topic-numbers out)
186 ;; CXTM 3.12/4.4/4.6. Empty Scope has no XML representation.
187 (when themes
188 (format out "<scope>~%")
189 (dolist (theme (sorted themes #'topic-order))
190 (format out "<scopingTopic topicref=\"~D\"></scopingTopic>~%" (gethash theme topic-numbers)))
191 (format out "</scope>~%")))
192
193 (defun canonicalize (map &key base-locator)
194 "Return CXTM as a string. BASE-LOCATOR is an explicit absolute IRI (CXTM 3.1).
195 Only the existing TMDM schema is supported: Topic-set Scope, null Reifier, no
196 Variants or non-Topic identifiers other than Occurrence identifiers. Does not mutate MAP or handles."
197 (unless (and (stringp base-locator) (position #\: base-locator)
198 (let ((scheme (subseq base-locator 0 (position #\: base-locator))))
199 (and (plusp (length scheme))
200 (or (char<= #\a (char scheme 0) #\z) (char<= #\A (char scheme 0) #\Z))
201 (every (lambda (c) (or (char<= #\a c #\z) (char<= #\A c #\Z)
202 (char<= #\0 c #\9) (find c "+-."))) scheme))))
203 (fail :invalid-base-locator "Supply an absolute base locator."))
204 (validate-map map)
205 (let* ((*base-locator* base-locator) (*locator-cache* (make-hash-table :test #'equal))
206 (topics (sorted (topic-map-topics map) #'topic-order))
207 (associations (sorted (topic-map-associations map) #'association-order))
208 (topic-numbers (make-hash-table :test #'eq))
209 (association-numbers (make-hash-table :test #'eq))
210 (role-numbers (make-hash-table :test #'eq)))
211 ;; NFC/base normalization can expose distinct, comparator-equal Topics.
212 ;; No address/construction-order tie breaker or implicit merge is permitted.
213 (loop for (a b) on topics while b do
214 (when (zerop (topic-order a b))
215 (fail :ambiguous-topic-order "Distinct Topics have identical normalized identity keys; resolve model identity first." t)))
216 (loop for topic in topics for number from 1 do (setf (gethash topic topic-numbers) number))
217 (loop for a in associations for number from 1 do
218 (setf (gethash a association-numbers) number)
219 (loop for r in (sorted (association-roles a) #'role-order) for index from 1 do
220 (setf (gethash r role-numbers) index)))
221 (with-output-to-string (out)
222 (labels ((type-ref (topic)
223 (format out "<type topicref=\"~D\"></type>~%" (gethash topic topic-numbers)))
224 (role-ref (r)
225 (format out "<rolePlayed ref=\"association.~D.role.~D\"></rolePlayed>~%"
226 (gethash (association-role-parent r) association-numbers)
227 (gethash r role-numbers))))
228 (format out "<topicMap>~%")
229 (loop for topic in topics for number from 1 do
230 (format out "<topic number=\"~D\">~%" number)
231 (emit-locators "subjectIdentifiers" (topic-subject-identifiers topic) out)
232 (emit-locators "subjectLocators" (topic-subject-locators topic) out)
233 (emit-locators "itemIdentifiers" (topic-item-identifiers topic) out)
234 (loop for name in (sorted (topic-names topic) #'name-order) for index from 1 do
235 (format out "<name number=\"~D\">~%<value>" index)
236 (xml-text (topic-name-value name) out) (format out "</value>~%")
237 (type-ref (topic-name-type name))
238 (emit-scope (topic-name-scope name) topic-numbers out) (format out "</name>~%"))
239 (loop for item in (sorted (topic-occurrences topic) #'occurrence-order) for index from 1 do
240 (format out "<occurrence number=\"~D\">~%<value>" index)
241 (xml-text (cond ((string= (occurrence-datatype item) (iri-datatype))
242 (normalized-locator (occurrence-value item)))
243 ((string= (occurrence-datatype item) (integer-datatype))
244 (canonical-integer-lexical-form (occurrence-value item)))
245 ((string= (occurrence-datatype item) (decimal-datatype))
246 (canonical-decimal-lexical-form (occurrence-value item)))
247 ((string= (occurrence-datatype item) (date-datatype))
248 (canonical-date-lexical-form (occurrence-value item)))
249 ((string= (occurrence-datatype item) (datetime-datatype))
250 (canonical-datetime-lexical-form (occurrence-value item)))
251 (t (occurrence-value item))) out)
252 (format out "</value>~%<datatype>")
253 ;; CXTM 3.14: datatype locator is NOT base-normalized.
254 (xml-text (occurrence-datatype item) out) (format out "</datatype>~%")
255 (type-ref (occurrence-type item))
256 (emit-scope (occurrence-scope item) topic-numbers out)
257 (emit-locators "itemIdentifiers" (occurrence-item-identifiers item) out)
258 (format out "</occurrence>~%"))
259 (dolist (r (sorted (topic-roles-played topic) #'role-order)) (role-ref r))
260 (format out "</topic>~%"))
261 (loop for a in associations for number from 1 do
262 (format out "<association number=\"~D\">~%" number)
263 (type-ref (association-type a))
264 (loop for r in (sorted (association-roles a) #'role-order) for index from 1 do
265 (format out "<role number=\"~D\">~%<player topicref=\"~D\"></player>~%"
266 index (gethash (association-role-player r) topic-numbers))
267 (type-ref (association-role-type r)) (format out "</role>~%"))
268 (emit-scope (association-scope a) topic-numbers out)
269 (format out "</association>~%"))
270 ;; CXTM 3.1 step 2 appends LF after EVERY element, including the root.
271 (format out "</topicMap>~%")))))
272
273 (defun canonicalize-octets (map &key base-locator)
274 "Return canonical UTF-8 octets, with no BOM and the CXTM-mandated final LF."
275 (let ((out (make-array 0 :element-type '(unsigned-byte 8) :adjustable t :fill-pointer 0)))
276 (loop for c across (canonicalize map :base-locator base-locator) for n = (char-code c) do
277 (flet ((octet (b) (vector-push-extend b out)))
278 (cond ((< n #x80) (octet n))
279 ((< n #x800) (octet (logior #xc0 (ash n -6))) (octet (logior #x80 (logand n 63))))
280 ((< n #x10000) (octet (logior #xe0 (ash n -12)))
281 (octet (logior #x80 (logand (ash n -6) 63))) (octet (logior #x80 (logand n 63))))
282 (t (octet (logior #xf0 (ash n -18))) (octet (logior #x80 (logand (ash n -12) 63)))
283 (octet (logior #x80 (logand (ash n -6) 63))) (octet (logior #x80 (logand n 63))))))) out))
284 (defun write-cxtm (map pathname &key base-locator)
285 "Write canonical UTF-8 bytes to PATHNAME; MAP is not modified."
286 (let ((bytes (canonicalize-octets map :base-locator base-locator)))
287 (with-open-file (out pathname :direction :output :element-type '(unsigned-byte 8)
288 :if-exists :supersede :if-does-not-exist :create)
289 (write-sequence bytes out))) pathname)