(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-core-subjects map) (topic-maps.tmdm:core-subject-error (c) (fail (topic-maps.tmdm:core-subject-error-code c) (princ-to-string c)))) (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 "~%" 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)