(in-package #:topic-maps.cxtm)
(defvar *base-locator*)
(defvar *locator-cache*)
(defun path-start (iri)
(let* ((colon (position #\: iri)) (start (if colon (1+ colon) 0)))
(if (and (<= (+ start 2) (length iri))
(string= "//" iri :start2 start :end2 (+ start 2)))
(or (position #\/ iri :start (+ start 2)) (length iri)) start)))
(defun normalized-locator (locator)
"CXTM 3.18, literal prefix removal, NOT RFC relative-IRI resolution."
(or (gethash locator *locator-cache*)
(setf (gethash locator *locator-cache*)
(nfc
(let ((prefix (string-right-trim "/" (subseq *base-locator* 0
(position-if (lambda (c) (find c "?#")) *base-locator*)))))
(loop
(when (and (<= (length prefix) (length locator))
(string= prefix locator :end2 (length prefix)))
(return (string-left-trim "/" (subseq locator (length prefix)))))
(let ((start (path-start prefix)))
(when (>= start (length prefix)) (return locator))
(setf prefix (string-right-trim "/"
(subseq prefix 0 (or (position #\/ prefix :start start :from-end t) start)))))))))))
(defun string-order (a b)
;; Character CODE order, independent of a Lisp implementation's collation.
(loop for x across a for y across b
when (< (char-code x) (char-code y)) do (return-from string-order -1)
when (> (char-code x) (char-code y)) do (return-from string-order 1))
(signum (- (length a) (length b))))
(defun sorted (items comparison)
(stable-sort (copy-list items) (lambda (a b) (minusp (funcall comparison a b)))))
(defun set-order (a b comparison)
(let ((size (signum (- (length a) (length b)))))
(if (not (zerop size)) size
(loop for x in (sorted a comparison) for y in (sorted b comparison)
for c = (funcall comparison x y) when (not (zerop c)) return c
finally (return 0)))))
(defun locator-order (a b) (string-order (normalized-locator a) (normalized-locator b)))
(defun topic-order (a b)
(loop for getter in '(topic-subject-identifiers topic-subject-locators topic-item-identifiers)
for c = (set-order (funcall getter a) (funcall getter b) #'locator-order)
when (not (zerop c)) return c finally (return 0)))
(defun name-order (a b)
(let ((c (string-order (nfc (topic-name-value a)) (nfc (topic-name-value b)))))
(if (not (zerop c)) c
(let ((type (topic-order (topic-name-type a) (topic-name-type b))))
(if (not (zerop type)) type
(let ((scope (set-order (topic-name-scope a) (topic-name-scope b) #'topic-order)))
(if (not (zerop scope)) scope (topic-order (topic-name-parent a) (topic-name-parent b)))))))))
(defun literal-value-order (value-a datatype-a value-b datatype-b)
;; TMDM 4.3/5.5/5.6: anyURI values are locators; other supported values are strings.
;; CXTM 4.2 orders strings before locators, independent of their spelling.
(let ((iri-a (string= datatype-a (iri-datatype)))
(iri-b (string= datatype-b (iri-datatype))))
(cond ((and iri-a iri-b) (locator-order value-a value-b))
(iri-a 1) (iri-b -1)
(t (string-order (nfc value-a) (nfc value-b))))))
(defun occurrence-value-order (a b)
(literal-value-order (occurrence-value a) (occurrence-datatype a)
(occurrence-value b) (occurrence-datatype b)))
(defun variant-order (a b)
(loop for comparison in
(list (literal-value-order (variant-value a) (variant-datatype a) (variant-value b) (variant-datatype b))
(locator-order (variant-datatype a) (variant-datatype b))
(set-order (variant-scope a) (variant-scope b) #'topic-order)
(name-order (variant-parent a) (variant-parent b)))
when (not (zerop comparison)) return comparison finally (return 0)))
(defun canonical-literal-value (value datatype)
"CXTM 3.16: shared Occurrence/Variant representation; never rewrite model data."
(cond ((string= datatype (iri-datatype)) (normalized-locator value))
((string= datatype (integer-datatype)) (canonical-integer-lexical-form value))
((string= datatype (decimal-datatype)) (canonical-decimal-lexical-form value))
((string= datatype (date-datatype)) (canonical-date-lexical-form value))
((string= datatype (datetime-datatype)) (canonical-datetime-lexical-form value))
(t value)))
(defun occurrence-order (a b)
(loop for comparison in
(list (occurrence-value-order a b)
(locator-order (occurrence-datatype a) (occurrence-datatype b))
(topic-order (occurrence-type a) (occurrence-type b))
(set-order (occurrence-scope a) (occurrence-scope b) #'topic-order)
(topic-order (occurrence-parent a) (occurrence-parent b)))
when (not (zerop comparison)) return comparison finally (return 0)))
(defun role-signature-order (a b)
;; In a single parent's roles set, [parent] is equal. During association
;; comparison equal player/type pairs also have equal parent-comparison
;; context. Comparing this prefix avoids recursive parent/roles traversal.
(let ((c (topic-order (association-role-player a) (association-role-player b))))
(if (not (zerop c)) c (topic-order (association-role-type a) (association-role-type b)))))
(defun association-order (a b)
(let ((c (topic-order (association-type a) (association-type b))))
(if (not (zerop c)) c
(let ((roles (set-order (association-roles a) (association-roles b) #'role-signature-order)))
;; Parent Map is equal for all associations compared by this serializer.
(if (not (zerop roles)) roles
(set-order (association-scope a) (association-scope b) #'topic-order))))))
(defun role-order (a b)
(let ((c (role-signature-order a b)))
(if (not (zerop c)) c
(association-order (association-role-parent a) (association-role-parent b)))))
(defun require-exact-item (item type)
;; A future/subclass model carrying extra properties is explicitly unsupported.
(unless (eq (type-of item) type)
(fail :unsupported-information-item (format nil "Expected exact ~S, received ~S." type (type-of item)) t)))
(defun require-set (items)
(unless (and (topic-maps.tmdm::proper-list-p items) (= (length items) (length (remove-duplicates items :test #'eq))))
(fail :invalid-set "An information-item collection must be a proper set.")))
(defun validate-literal-value (value datatype)
"Validate the shared Variant/Occurrence literal representation without mutation."
(unless (and (stringp value) (stringp datatype)) (fail :invalid-literal "Value and datatype must be strings."))
(unless (topic-maps.tmdm::absolute-locator-p datatype)
(fail :invalid-occurrence-datatype "Datatype must be an absolute locator."))
(when (and (string= datatype (integer-datatype))
(not (integer-lexical-p value)))
(fail :invalid-integer-value "Literal value is not an xsd:integer lexical form."))
(when (and (string= datatype (decimal-datatype))
(not (decimal-lexical-p value)))
(fail :invalid-decimal-value "Literal value is not an xsd:decimal lexical form."))
(when (string= datatype (date-datatype))
(unless (date-lexical-p value)
(fail :invalid-date-value "Literal value is not a valid XSD 1.0 date."))
(unless (canonical-date-lexical-form value)
(fail :date-timezone-canonicalization "XSD date recoverable-timezone canonicalization is outside this slice." t)))
(when (string= datatype (datetime-datatype))
(unless (datetime-lexical-p value)
(fail :invalid-datetime-value "Literal value is not a valid XSD 1.0 dateTime."))
(multiple-value-bind (value reason) (canonical-datetime-lexical-form value)
(unless value (fail (if (eq reason :unsupported-bce-timezone-rollover)
:datetime-bce-timezone-rollover :datetime-leap-second-context)
"DateTime BCE rollover/leap-second context is outside this canonical subset." t))))
(when (and (string= datatype (iri-datatype))
(not (topic-maps.tmdm::absolute-locator-p value)))
(fail :invalid-occurrence-value "IRI-valued literals must store an absolute locator."))
t)
(defun validate-map (map)
"Validate current model schema and referential integrity; never normalize/mutate."
(require-exact-item map 'topic-map)
(let ((topics (topic-map-topics map)) (associations (topic-map-associations map)))
(require-set topics) (require-set associations)
(labels ((reference (topic)
(require-exact-item topic 'topic)
(unless (and (eq topic (canonical-topic topic)) (member topic topics :test #'eq))
(fail :invalid-topic-reference "Reference must designate a current Topic in this map."))))
(dolist (topic topics)
(reference topic)
(unless (eq (topic-parent topic) map) (fail :invalid-parent "Topic parent mismatch."))
(unless (or (topic-item-identifiers topic) (topic-subject-identifiers topic) (topic-subject-locators topic))
(fail :unidentified-topic "CXTM 4.6 requires an identity-bearing Topic." t))
(dolist (getter '(topic-item-identifiers topic-subject-identifiers topic-subject-locators))
(let ((ids (funcall getter topic)))
(unless (and (every (lambda (s) (and (stringp s) (plusp (length s)))) ids)
(= (length ids) (length (remove-duplicates ids :test #'string=))))
(fail :invalid-locators "Locator properties must be sets of nonempty strings."))))
(require-set (topic-names topic))
(dolist (name (topic-names topic))
(require-exact-item name 'topic-name)
(unless (and (eq name (canonical-topic-name name)) (eq (topic-name-parent name) topic))
(fail :invalid-parent "Name must be current and owned by its containing Topic."))
(reference (topic-name-type name))
(require-set (topic-name-scope name)) (mapc #'reference (topic-name-scope name))
(require-set (topic-name-variants name))
(dolist (item (topic-name-variants name))
(require-exact-item item 'variant)
(unless (and (eq item (canonical-variant item)) (eq (variant-parent item) name))
(fail :invalid-parent "Variant must be current and owned by its containing Name."))
(require-set (variant-scope item)) (mapc #'reference (variant-scope item))
(unless (topic-maps.tmdm::variant-scope-valid-p (variant-scope item) (topic-name-scope name))
(fail :invalid-variant-scope "Variant scope must properly contain its Parent Name scope."))
(validate-literal-value (variant-value item) (variant-datatype item))))
(require-set (topic-occurrences topic))
(dolist (item (topic-occurrences topic))
(require-exact-item item 'occurrence)
(unless (and (eq item (canonical-occurrence item)) (eq (occurrence-parent item) topic))
(fail :invalid-parent "Occurrence must be current and owned by its containing Topic."))
(reference (occurrence-type item))
(require-set (occurrence-scope item)) (mapc #'reference (occurrence-scope item))
(validate-literal-value (occurrence-value item) (occurrence-datatype item))
(let ((ids (occurrence-item-identifiers item)))
(unless (and (every #'topic-maps.tmdm::absolute-locator-p ids)
(= (length ids) (length (remove-duplicates ids :test #'string=))))
(fail :invalid-locators "Occurrence identifiers must be an absolute locator set.")))))
(dolist (a associations)
(require-exact-item a 'association)
(unless (and (eq a (canonical-association a)) (eq (association-parent a) map))
(fail :invalid-parent "Association must be current and owned by this map."))
(reference (association-type a))
(require-set (association-scope a)) (mapc #'reference (association-scope a))
(require-set (association-roles a))
(unless (association-roles a) (fail :empty-association "Association requires Roles."))
(dolist (r (association-roles a))
(require-exact-item r 'association-role)
(unless (and (eq r (canonical-association-role r)) (eq (association-role-parent r) a))
(fail :invalid-parent "Role must be current and owned by its Association."))
(reference (association-role-type r)) (reference (association-role-player r))))))
(handler-case (topic-maps.tmdm::validate-map-item-identifiers map)
(topic-maps.tmdm:item-identifier-error (c)
(fail (topic-maps.tmdm:item-identifier-error-code c) (princ-to-string c))))
(handler-case (topic-maps.tmdm::validate-map-reification map)
(topic-maps.tmdm:reification-error (c)
(fail (topic-maps.tmdm:reification-error-code c) (princ-to-string c)))))
(defun xml-text (text out)
(loop for c across (nfc text) for n = (char-code c) do
(unless (or (member n '(9 10 13)) (<= 32 n #xd7ff) (<= #xe000 n #xfffd) (<= #x10000 n #x10ffff))
(fail :xml-character (format nil "U+~4,'0X cannot be represented in XML 1.0." n)))
(case c
(#\& (write-string "&" out)) (#\< (write-string "<" out))
(#\> (write-string ">" out)) (#\Return (write-string "
" out))
(otherwise (write-char c out)))))
(defun emit-locators (tag locators out)
(when locators
(format out "<~A>~%" tag)
(dolist (locator (sorted locators #'locator-order))
(write-string "" out) (xml-text (normalized-locator locator) out)
(format out "~%"))
(format out "~A>~%" tag)))
(defun emit-scope (themes topic-numbers out)
;; CXTM 3.12/4.4/4.6. Empty Scope has no XML representation.
(when themes
(format out "~%")
(dolist (theme (sorted themes #'topic-order))
(format out "~%" (gethash theme topic-numbers)))
(format out "~%")))
(defun canonicalize (map &key base-locator)
"Return CXTM as a string. BASE-LOCATOR is an explicit absolute IRI (CXTM 3.1).
Supports Scope, Variants, Item Identifiers and same-map Reification.
Does not mutate MAP or retained handles."
(unless (and (stringp base-locator) (position #\: base-locator)
(let ((scheme (subseq base-locator 0 (position #\: base-locator))))
(and (plusp (length scheme))
(or (char<= #\a (char scheme 0) #\z) (char<= #\A (char scheme 0) #\Z))
(every (lambda (c) (or (char<= #\a c #\z) (char<= #\A c #\Z)
(char<= #\0 c #\9) (find c "+-."))) scheme))))
(fail :invalid-base-locator "Supply an absolute base locator."))
(validate-map map)
(let* ((*base-locator* base-locator) (*locator-cache* (make-hash-table :test #'equal))
(topics (sorted (topic-map-topics map) #'topic-order))
(associations (sorted (topic-map-associations map) #'association-order))
(topic-numbers (make-hash-table :test #'eq))
(association-numbers (make-hash-table :test #'eq))
(role-numbers (make-hash-table :test #'eq)))
;; NFC/base normalization can expose distinct, comparator-equal Topics.
;; No address/construction-order tie breaker or implicit merge is permitted.
(loop for (a b) on topics while b do
(when (zerop (topic-order a b))
(fail :ambiguous-topic-order "Distinct Topics have identical normalized identity keys; resolve model identity first." t)))
(loop for topic in topics for number from 1 do (setf (gethash topic topic-numbers) number))
(loop for a in associations for number from 1 do
(setf (gethash a association-numbers) number)
(loop for r in (sorted (association-roles a) #'role-order) for index from 1 do
(setf (gethash r role-numbers) index)))
(with-output-to-string (out)
(labels ((start (tag item number)
;; CXTM 3.11, canonical XML attribute order: number, reifier.
(format out "<~A" tag)
(when number (format out " number=\"~D\"" number))
(when (item-reifier item)
(format out " reifier=\"~D\"" (gethash (item-reifier item) topic-numbers)))
(format out ">~%"))
(type-ref (topic)
(format out "~%" (gethash topic topic-numbers)))
(role-ref (r)
(format out "~%"
(gethash (association-role-parent r) association-numbers)
(gethash r role-numbers))))
(start "topicMap" map nil)
(emit-locators "itemIdentifiers" (item-identifiers map) out)
(loop for topic in topics for number from 1 do
(format out "~%" number)
(emit-locators "subjectIdentifiers" (topic-subject-identifiers topic) out)
(emit-locators "subjectLocators" (topic-subject-locators topic) out)
(emit-locators "itemIdentifiers" (topic-item-identifiers topic) out)
(loop for name in (sorted (topic-names topic) #'name-order) for index from 1 do
(start "name" name index) (write-string "" out)
(xml-text (topic-name-value name) out) (format out "~%")
(type-ref (topic-name-type name))
(emit-scope (topic-name-scope name) topic-numbers out)
(loop for item in (sorted (topic-name-variants name) #'variant-order) for number from 1 do
(start "variant" item number) (write-string "" out)
(xml-text (canonical-literal-value (variant-value item) (variant-datatype item)) out)
(format out "~%") (xml-text (variant-datatype item) out)
(format out "~%") (emit-scope (variant-scope item) topic-numbers out)
(emit-locators "itemIdentifiers" (item-identifiers item) out)
(format out "~%"))
(emit-locators "itemIdentifiers" (item-identifiers name) out)
(format out "~%"))
(loop for item in (sorted (topic-occurrences topic) #'occurrence-order) for index from 1 do
(start "occurrence" item index) (write-string "" out)
(xml-text (canonical-literal-value (occurrence-value item) (occurrence-datatype item)) out)
(format out "~%")
;; CXTM 3.14: datatype locator is NOT base-normalized.
(xml-text (occurrence-datatype item) out) (format out "~%")
(type-ref (occurrence-type item))
(emit-scope (occurrence-scope item) topic-numbers out)
(emit-locators "itemIdentifiers" (occurrence-item-identifiers item) out)
(format out "~%"))
(dolist (r (sorted (topic-roles-played topic) #'role-order)) (role-ref r))
(format out "~%"))
(loop for a in associations for number from 1 do
(start "association" a number)
(type-ref (association-type a))
(loop for r in (sorted (association-roles a) #'role-order) for index from 1 do
(start "role" r index)
(format out "~%" (gethash (association-role-player r) topic-numbers))
(type-ref (association-role-type r))
(emit-locators "itemIdentifiers" (item-identifiers r) out)
(format out "~%"))
(emit-scope (association-scope a) topic-numbers out)
(emit-locators "itemIdentifiers" (item-identifiers a) out)
(format out "~%"))
;; CXTM 3.1 step 2 appends LF after EVERY element, including the root.
(format out "~%")))))
(defun canonicalize-octets (map &key base-locator)
"Return canonical UTF-8 octets, with no BOM and the CXTM-mandated final LF."
(let ((out (make-array 0 :element-type '(unsigned-byte 8) :adjustable t :fill-pointer 0)))
(loop for c across (canonicalize map :base-locator base-locator) for n = (char-code c) do
(flet ((octet (b) (vector-push-extend b out)))
(cond ((< n #x80) (octet n))
((< n #x800) (octet (logior #xc0 (ash n -6))) (octet (logior #x80 (logand n 63))))
((< n #x10000) (octet (logior #xe0 (ash n -12)))
(octet (logior #x80 (logand (ash n -6) 63))) (octet (logior #x80 (logand n 63))))
(t (octet (logior #xf0 (ash n -18))) (octet (logior #x80 (logand (ash n -12) 63)))
(octet (logior #x80 (logand (ash n -6) 63))) (octet (logior #x80 (logand n 63))))))) out))
(defun write-cxtm (map pathname &key base-locator)
"Write canonical UTF-8 bytes to PATHNAME; MAP is not modified."
(let ((bytes (canonicalize-octets map :base-locator base-locator)))
(with-open-file (out pathname :direction :output :element-type '(unsigned-byte 8)
:if-exists :supersede :if-does-not-exist :create)
(write-sequence bytes out))) pathname)