From: rgb Date: Wed, 28 Oct 2026 15:42:36 +0000 (+0100) Subject: perf(tmdm): index association normalization merge candidates X-Git-Url: https://dreyeck.freedombox.rocks/gitweb/topic-maps.git/commitdiff_plain/88994c1b9e1edbf13e665e984a5c9c3b2cdf7575?ds=sidebyside perf(tmdm): index association normalization merge candidates Replace the quadratic cross-Association scan in normalize-associations with an indexed search for the next merge candidate. Pair selection order and merge semantics are unchanged relative to 6162ed68. Adds tests/association-index.lisp with 29 fixtures. Independently reviewed. Not verified: Linux execution, the Stage 2 CTM, peak RSS and suitability for the constrained NixOS host, high-arity performance, and the historical Python Unicode/NFC checker mismatch (pre-existing, Python 3.14 / Unicode 16). Co-Authored-By: Claude Sonnet 5.5 --- diff --git a/scripts/fresh-sbcl.lisp b/scripts/fresh-sbcl.lisp index 3342b08..f0bfdee 100644 --- a/scripts/fresh-sbcl.lisp +++ b/scripts/fresh-sbcl.lisp @@ -152,6 +152,7 @@ ;; Which Topics merge next: outcomes recorded at b2eecffa, invalidation and scale. (asdf:test-system "topic-maps/tmdm/normalization-index-tests") +(asdf:test-system "topic-maps/tmdm/association-index-tests") ;; Optional executable learning example, after all historical stage snapshots. (asdf:test-system "topic-maps/project-work-tests") diff --git a/src/tmdm/associations.lisp b/src/tmdm/associations.lisp index 48d8856..11905a2 100644 --- a/src/tmdm/associations.lisp +++ b/src/tmdm/associations.lisp @@ -41,9 +41,49 @@ (normalize-roles c) (merge-item-reifiers c a b))) +(defun scan-next-association-merge (map) + "The pair of Associations to merge next, found by comparing Associations pairwise: the first Association with a +later equal one, and the first such later one, in map order; NIL if none. This is the search that defines the +choice; NEXT-ASSOCIATION-MERGE returns the same pair." + (equal-pair (%topic-map-associations map) #'equal-associations-p)) + +(defun next-association-merge (map) + "The pair SCAN-NEXT-ASSOCIATION-MERGE returns, found through an index built for this one search and dropped with it. +When no Association holds two Roles of one signature and no Scope repeats a theme, EQUAL-ASSOCIATIONS-P holds exactly +when the two Associations have the EQ type, the same Scope set and the same set of Role signatures: equal Role counts +and inclusion of duplicate-free sets make the sets equal. Those three are the key, built from the stored references +as EQUAL-ASSOCIATIONS-P compares them (EQ, never resolved to a representative). The relation is then an equivalence and +has no side effect, so the first Association with a later key-sharer, and its first such sharer, are what the pairwise +search finds. With a repeated Role signature the relation is not symmetric; then, and with a repeated theme, the +pairwise search itself runs. The index is never kept: a merge, a Role merge or a Reifier cascade can change any +type, player, theme and the list itself before the next search." + (let ((associations (%topic-map-associations map))) + (unless (every (lambda (a) + (and (null (equal-pair (%association-roles a) #'same-role-signature-p)) + (let ((scope (%association-scope a))) + (= (length scope) (length (remove-duplicates scope :test #'eq)))))) + associations) + (return-from next-association-merge (scan-next-association-merge map))) + (let ((ids (make-hash-table :test #'eq)) (next 0) (sharers (make-hash-table :test #'equal))) + (flet ((id (object) (or (gethash object ids) (setf (gethash object ids) (incf next)))) + (signature< (x y) (or (< (car x) (car y)) (and (= (car x) (car y)) (< (cdr x) (cdr y)))))) + (let ((keys (mapcar (lambda (a) + (list (id (%association-type a)) + (sort (mapcar #'id (%association-scope a)) #'<) + (sort (mapcar (lambda (role) (cons (id (%association-role-type role)) + (id (%association-role-player role)))) + (%association-roles a)) + #'signature<))) + associations))) + ;; Each key lists its Associations in map order. + (loop for a in (reverse associations) for key in (reverse keys) do (push a (gethash key sharers))) + (loop for a in associations for key in keys + for later = (second (member a (gethash key sharers) :test #'eq)) + when later return (list a later))))))) + (defun normalize-associations (map) (dolist (association (%topic-map-associations map)) (normalize-roles association)) - (loop for pair = (equal-pair (%topic-map-associations map) #'equal-associations-p) + (loop for pair = (next-association-merge map) while pair do (merge-two-associations map (first pair) (second pair))) map) diff --git a/tests/association-index.lisp b/tests/association-index.lisp new file mode 100644 index 0000000..2bca5a0 --- /dev/null +++ b/tests/association-index.lisp @@ -0,0 +1,487 @@ +(defpackage #:topic-maps.association-index.tests + (:use #:cl #:topic-maps.tmdm) + (:import-from #:topic-maps.ctm.tests #:check #:cxtm) + (:import-from #:topic-maps.identifier.tests #:si) + (:export #:run-tests #:association-index-checks #:record-expected #:with-shadow-search #:shadow-report)) +(in-package #:topic-maps.association-index.tests) + +;;; Which Associations merge next, and the results that must not change while the search for them changes. +;;; The expected CXTM of every case, the facts of every API scenario and the class and code of every rejection +;;; were recorded from the unchanged implementation at 6162ed68 (RECORD-EXPECTED) before NEXT-ASSOCIATION-MERGE +;;; existed; they are not derived from the implementation under test. SCAN-NEXT-ASSOCIATION-MERGE is the 6162ed68 +;;; search, kept as the fallback and used here as the oracle. + +(defvar *last-checks* nil) +(defun association-index-checks () *last-checks*) +(defparameter +document+ "https://example.invalid/a/doc.ctm") +(defvar *fixture-directory* nil) +(defun fixture-directory () + (or *fixture-directory* (asdf:system-relative-pathname "topic-maps" "tests/fixtures/association-index/"))) +(defun read-case (text) (topic-maps.ctm:deserialize-string text :document-iri +document+ :source-name "association-index")) +(defun pick (random sequence) (elt sequence (random (length sequence) random))) +(defun ii (name) (format nil "~A#~A" +document+ name)) + +;;; Documents whose result must not change + +(defun same-type-document (associations duplicate-every) + "ASSOCIATIONS Associations of one type with distinct players; every DUPLICATE-EVERYth is stated twice." + (with-output-to-string (s) + (dotimes (i associations) + (format s "t(r: p~D, q: o~D)~%" i (mod i 7)) + (when (and (plusp duplicate-every) (zerop (mod i duplicate-every))) (format s "t(q: o~D, r: p~D)~%" (mod i 7) i))))) + +(defparameter *documents* + `(("plain-duplicates" ,(format nil "t(r: a, q: b)~%t(r: a, q: b)")) + ("role-order-permutation" ,(format nil "t(r: a, q: b)~%t(q: b, r: a)")) + ("n-ary-permutation" ,(format nil "t(r1: a, r2: b, r3: c)~%t(r3: c, r2: b, r1: a)~%t(r1: a, r2: b)")) + ("scoped-duplicates" ,(format nil "t(r: a)@s~%t(r: a)@s~%t(r: a)@u~%t(r: a)~%t(r: a)@s,u~%t(r: a)@u,s")) + ("repeated-role-signature" ,(format nil "t(r: a, r: a, q: b)~%t(r: a, q: b)~%t(r: a, r: a)~%t(r: a)")) + ("type-differs" ,(format nil "t(r: a)~%u(r: a)")) + ("role-type-differs" ,(format nil "t(r: a)~%t(q: a)")) + ("player-differs" ,(format nil "t(r: a)~%t(r: b)")) + ("role-count-differs" ,(format nil "t(r: a)~%t(r: a, q: b)")) + ("equal-after-player-merge" ,(format nil "t(r: a, q: c)~%t(r: b, q: c)~%b ^ ~A ." (ii "a"))) + ("equal-after-type-merge" ,(format nil "t(r: a)~%u(r: a)~%u ^ ~A ." (ii "t"))) + ("equal-after-role-type-merge" ,(format nil "t(r: a)~%t(q: a)~%q ^ ~A ." (ii "r"))) + ("equal-after-theme-merge" ,(format nil "t(r: a)@s~%t(r: a)@u~%u ^ ~A ." (ii "s"))) + ("scope-collapses-after-theme-merge" ,(format nil "t(r: a)@s,u~%t(r: a)@s~%u ^ ~A ." (ii "s"))) + ("duplicate-chain" ,(format nil "t(r: a)~%t(r: b)~%t(r: c)~%b ^ ~A .~%c ^ ~A ." (ii "a") (ii "a"))) + ("first-pair-is-not-the-first-association" ,(format nil "u(r: x)~%t(r: a)~%t(r: b)~%u(r: y)~%t(r: a)~%u(r: x)")) + ("reified-duplicates-reifiers-merge" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%x - \"X\" .~%y - \"Y\" .")) + ("reified-one-side" ,(format nil "t(r: p) ~~ x~%t(r: p)~%x - \"X\" .")) + ("reifier-cascade" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%u(r: x) ~~ z~%u(r: y) ~~ w~%z - \"Z\" .~%w - \"W\" .")) + ("reifiers-become-equal-associations" ,(format nil "t(r: a) ~~ x~%t(r: b) ~~ y~%v(r: x)~%v(r: y)~%b ^ ~A ." (ii "a"))) + ("isa-duplicates-merge" ,(format nil "a isa k .~%b isa k .~%a isa k .~%k2 http://example.org/k .~%k http://example.org/k .~%b isa k2 .")) + ("same-type-80" ,(same-type-document 80 9))) + "CTM documents whose CXTM is recorded.") + +(defparameter *rejections* + `(("reifier-reifies-association-and-name" ,(format nil "t(r: p) ~~ x~%m - \"M\" ~~ x .")) + ("equal-associations-with-core-subject-reifiers" + ,(format nil "t(r: a) ~~ x~%t(r: b) ~~ y~%x http://psi.topicmaps.org/iso13250/model/type .~%y http://psi.topicmaps.org/iso13250/model/instance .~%b ^ ~A ." (ii "a"))) + ("reifier-merge-conflict" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ y~%x ^ ~A ." (ii "y")))) + "CTM documents whose rejection is recorded as condition class and code.") + +;;; API scenarios: what no CTM text shows (retained Association and Role handles, identifier order, reifiers) + +(defun label (topic) + "A Topic named by its sorted subject identifiers, after resolving the handle." + (let ((topic (canonical-topic topic))) (format nil "~{~A~^|~}" (sort (topic-subject-identifiers topic) #'string<)))) +(defun role-facts (role association) + (let ((current (canonical-association-role role))) + (list (label (association-role-type current)) (label (association-role-player current)) + (association-role-item-identifiers current) + (and (member current (association-roles association) :test #'eq) t) + (let ((r (item-reifier current))) (and r (label r)))))) +(defun association-facts (map handles roles) + (let ((current (canonical-association (first handles)))) + (list :associations (length (topic-map-associations map)) + :one-association (every (lambda (h) (eq current (canonical-association h))) handles) + :position (position current (topic-map-associations map) :test #'eq) + :item-identifiers (association-item-identifiers current) + :reifier (let ((r (item-reifier current))) (and r (label r))) + :roles (length (association-roles current)) + :role-handles (mapcar (lambda (r) (role-facts r current)) roles) + :topics (length (topic-map-topics map))))) + +(defun api-identifiers-and-handles () + (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (q (si map "q")) (o (si map "other")) + (a (si map "a")) (b (si map "b")) (p (si map "p"))) + (make-association map o (list (list r a))) + (let* ((a1 (make-association map ty (list (list r a) (list q p)))) + (a2 (make-association map ty (list (list q p) (list r b)))) + (roles (append (association-roles a1) (association-roles a2)))) + (add-item-identifier a1 "urn:assoc-1") (add-item-identifier a2 "urn:assoc-2") + (add-item-identifier (first (association-roles a1)) "urn:role-1a") + (add-item-identifier (second (association-roles a2)) "urn:role-2b") + (add-item-identifier (first (association-roles a2)) "urn:role-2p") + (add-topic-identifier b :subject-identifier "urn:a") + (values map (association-facts map (list a1 a2) roles))))) + +(defun api-reified-associations () + (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) + (x (si map "x")) (y (si map "y")) + (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b))))) + (set-item-reifier a1 x) (set-item-reifier a2 y) + (add-name y "Y") + (add-topic-identifier b :subject-identifier "urn:a") + (values map (append (association-facts map (list a1 a2) (append (association-roles a1) (association-roles a2))) + (list :reifiers-one (eq (canonical-topic x) (canonical-topic y)) + :inverse (eq (canonical-association a1) (topic-reified x))))))) + +(defun api-reified-roles () + (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) + (x (si map "x")) (y (si map "y")) + (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b)))) + (r1 (first (association-roles a1))) (r2 (first (association-roles a2)))) + (set-item-reifier r1 x) (set-item-reifier r2 y) + (merge-topics a b) + (values map (append (association-facts map (list a1 a2) (list r1 r2)) + (list :role-reifiers-one (eq (canonical-topic x) (canonical-topic y)) + :one-role (eq (canonical-association-role r1) (canonical-association-role r2))))))) + +(defun api-three-way () + ;; Three equal Associations after one merge of players: the representative is the first, then the third joins it. + (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) (c (si map "c")) + (a1 (make-association map ty (list (list r a)))) (mid (make-association map (si map "mid") (list (list r a)))) + (a2 (make-association map ty (list (list r b)))) (a3 (make-association map ty (list (list r c))))) + (add-item-identifier a1 "urn:1") (add-item-identifier a2 "urn:2") (add-item-identifier a3 "urn:3") + (add-topic-identifier b :subject-identifier "urn:a") + (add-topic-identifier c :subject-identifier "urn:a") + (values map (append (association-facts map (list a1 a2 a3) nil) + (list :order (mapcar (lambda (h) (position (canonical-association h) (topic-map-associations map) :test #'eq)) + (list a1 mid a2 a3))))))) + +(defun api-core-subject-rejection () + ;; Equal Associations whose Reifiers cannot merge: the conflict is signalled and the map is not changed. + (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) + (x (intern-topic map :subject-identifier "http://psi.topicmaps.org/iso13250/model/type")) + (y (intern-topic map :subject-identifier "http://psi.topicmaps.org/iso13250/model/instance")) + (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b))))) + (set-item-reifier a1 x) (set-item-reifier a2 y) + (let* ((before (topic-maps.ctm.tests::map-state map)) + (condition (handler-case (progn (add-topic-identifier b :subject-identifier "urn:a") nil) (error (c) c)))) + (values map (list :condition (and condition (type-of condition)) :code (and condition (condition-code condition)) + :unchanged (equal before (topic-maps.ctm.tests::map-state map)) + :associations (length (topic-map-associations map))))))) + +(defparameter *api-scenarios* + '(("api-identifiers-and-handles" api-identifiers-and-handles) ("api-reified-associations" api-reified-associations) + ("api-reified-roles" api-reified-roles) ("api-three-way" api-three-way) + ("api-core-subject-rejection" api-core-subject-rejection)) + "API scenarios whose CXTM and facts are recorded.") + +(defun condition-code (c) + (cond ((typep c 'topic-maps.ctm:ctm-error) (topic-maps.ctm:error-code c)) + ((typep c 'reification-error) (reification-error-code c)) + ((typep c 'core-subject-error) (core-subject-error-code c)) + (t nil))) +(defun outcome (thunk) + (handler-case (list :read (funcall thunk)) + (error (c) (list :refused (type-of c) (condition-code c))))) +(defun document-outcome (text) (outcome (lambda () (cxtm (read-case text) +document+)))) +(defun as-recorded (value) + "VALUE as it reads back from a fixture file: printed and read in the keyword package." + (let ((*package* (find-package "KEYWORD"))) (read-from-string (prin1-to-string value)))) +(defun api-outcome (function) + (multiple-value-bind (map facts) (funcall function) (list (cxtm map +document+) facts))) + +(defun record-expected () + "Write the expected outcomes with the implementation now loaded. Run once, at unchanged 6162ed68." + (ensure-directories-exist (fixture-directory)) + (flet ((record (name value) + (with-open-file (out (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory)) + :direction :output :if-exists :supersede :external-format :utf-8) + (write-string value out)))) + (dolist (case *documents*) + (destructuring-bind (kind value &rest rest) (document-outcome (second case)) + (declare (ignore rest)) + (unless (eq kind :read) (error "Case ~A was refused: ~S" (first case) value)) + (record (first case) value))) + (with-open-file (facts (merge-pathnames "api-facts.sexp" (fixture-directory)) :direction :output :if-exists :supersede) + (let ((*package* (find-package "KEYWORD"))) + (dolist (case *api-scenarios*) + (destructuring-bind (text value) (api-outcome (symbol-function (second case))) + (record (first case) text) + (prin1 (cons (first case) value) facts) (terpri facts)))))) + (with-open-file (out (merge-pathnames "rejections.sexp" (fixture-directory)) :direction :output :if-exists :supersede) + (let ((*package* (find-package "KEYWORD"))) + (dolist (case *rejections*) + (prin1 (cons (first case) (rest (document-outcome (second case)))) out) (terpri out))))) + +(defun expected-cxtm (name) + (uiop:read-file-string (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory)) :external-format :utf-8)) +(defun read-forms (name) + (with-open-file (in (merge-pathnames name (fixture-directory))) + (let ((*read-eval* nil) (*package* (find-package "KEYWORD"))) (loop for form = (read in nil) while form collect form)))) + +(defun recorded-outcome-tests () + (dolist (case *documents*) + (let ((o (document-outcome (second case)))) + (check (format nil "document:~A:read" (first case)) (eq :read (first o))) + (check (format nil "document:~A:cxtm-equals-6162ed68" (first case)) (string= (second o) (expected-cxtm (first case)))))) + (let ((facts (read-forms "api-facts.sexp"))) + (dolist (case *api-scenarios*) + (destructuring-bind (text value) (api-outcome (symbol-function (second case))) + (check (format nil "api:~A:cxtm-equals-6162ed68" (first case)) (string= text (expected-cxtm (first case)))) + (check (format nil "api:~A:facts-equal-6162ed68" (first case)) + (equal (as-recorded value) (rest (assoc (first case) facts :test #'string=))))))) + (let ((expected (read-forms "rejections.sexp"))) + (dolist (case *rejections*) + (let ((recorded (rest (assoc (first case) expected :test #'string=))) (o (document-outcome (second case)))) + (check (format nil "rejection:~A:recorded" (first case)) recorded) + (check (format nil "rejection:~A:class-and-code-equal-6162ed68" (first case)) + (equal (as-recorded (rest o)) recorded)))))) + +;;; The search itself, against the 6162ed68 search on unnormalized maps + +(defun precondition-holds-p (associations) + "The index's precondition: no Association with two Roles of one signature, no Scope with a repeated theme." + (every (lambda (a) + (and (null (topic-maps.tmdm::equal-pair (topic-maps.tmdm::%association-roles a) #'topic-maps.tmdm::same-role-signature-p)) + (= (length (topic-maps.tmdm::%association-scope a)) + (length (remove-duplicates (topic-maps.tmdm::%association-scope a) :test #'eq))))) + associations)) + +(defun random-association-map (random &key (stale t) (repeated-listing t) (reifiers nil) (size 8) (max-roles 4) (max-themes 3)) + "An unnormalized Map: a few raw Topics, raw Associations whose types, Role types, players and themes come from +small pools (so equal Associations are frequent), sometimes a repeated Role signature or theme (the fallback), +sometimes a reference to a replaced Topic (a raw stale reference), sometimes an Association listed twice, and, +with REIFIERS, distinct reifier Topics. Nothing is merged." + (let* ((map (make-topic-map)) (live (loop repeat (+ 3 (random 5 random)) collect (topic-maps.tmdm::%make-topic map))) + (old (and stale (zerop (random 3 random)) + (let ((s (topic-maps.tmdm::%make-topic map))) (setf (topic-maps.tmdm::%topic-forward s) (pick random live)) s))) + (associations nil)) + (setf (topic-maps.tmdm::%topic-map-topics map) live) + (flet ((ref (pool) (if (and old (zerop (random 7 random))) old (pick random (subseq live 0 (min pool (length live))))))) + (dotimes (k (+ 1 (random size random))) + (let ((a (topic-maps.tmdm::%make-association map (ref 2)))) + (setf (topic-maps.tmdm::%association-roles a) + (loop repeat (random max-roles random) collect (topic-maps.tmdm::%make-association-role a (ref 2) (ref 3)))) + (when (and (topic-maps.tmdm::%association-roles a) (zerop (random 6 random))) + (let ((r (first (topic-maps.tmdm::%association-roles a)))) + (push (topic-maps.tmdm::%make-association-role a (topic-maps.tmdm::%association-role-type r) + (topic-maps.tmdm::%association-role-player r)) + (topic-maps.tmdm::%association-roles a)))) + (let ((themes (loop repeat (random max-themes random) collect (ref 3)))) + (setf (topic-maps.tmdm::%association-scope a) + (if (zerop (random 6 random)) themes (remove-duplicates themes :test #'eq :from-end t)))) + (push a associations) + (when (and repeated-listing (zerop (random 12 random))) (push a associations))))) + (setf associations (nreverse associations) (topic-maps.tmdm::%topic-map-associations map) associations) + (when reifiers + (let ((free nil)) + (dolist (a (remove-duplicates associations)) + (when (zerop (random 3 random)) + (let ((r (topic-maps.tmdm::%make-topic map))) (push r free) + (setf (topic-maps.tmdm::%topic-map-topics map) (append (topic-maps.tmdm::%topic-map-topics map) (list r)) + (topic-maps.tmdm::%association-reifier a) r)))))) + map)) + +(defun asymmetric-pair-p (associations) + (loop for (a . rest) on associations + thereis (some (lambda (b) (not (eq (topic-maps.tmdm::equal-associations-p a b) (topic-maps.tmdm::equal-associations-p b a)))) rest))) + +(defun selection-equivalence-tests (&key (maps 6000) (seed 20261028)) + (let ((random (sb-ext:seed-random-state seed)) (pairs 0) (none 0) (index-path 0) (fallback 0) (asymmetric 0) + (stale 0) (listed-twice 0) (differences 0)) + (dotimes (n maps) + (let* ((map (random-association-map random)) (associations (topic-maps.tmdm::%topic-map-associations map)) + (indexed (topic-maps.tmdm::next-association-merge map)) + (oracle (topic-maps.tmdm::scan-next-association-merge map))) + (cond ((not (equal indexed oracle)) (incf differences)) + (oracle (incf pairs)) + (t (incf none))) + (if (precondition-holds-p associations) (incf index-path) (incf fallback)) + (when (asymmetric-pair-p associations) (incf asymmetric)) + (when (some (lambda (a) (some (lambda (x) (topic-maps.tmdm::%topic-forward x)) + (list* (topic-maps.tmdm::%association-type a) + (append (topic-maps.tmdm::%association-scope a) + (loop for r in (topic-maps.tmdm::%association-roles a) + collect (topic-maps.tmdm::%association-role-player r)))))) + associations) + (incf stale)) + (when (/= (length associations) (length (remove-duplicates associations))) (incf listed-twice)))) + (check "selection:indexed-equals-oracle-on-every-map" (zerop differences)) + (check "selection:maps-with-a-pair-exercised" (> pairs (floor maps 4))) + (check "selection:maps-without-a-pair-exercised" (> none (floor maps 20))) + (check "selection:index-path-exercised" (> index-path (floor maps 4))) + (check "selection:fallback-exercised" (> fallback (floor maps 20))) + (check "selection:asymmetric-equality-exercised" (> asymmetric (floor maps 100))) + (check "selection:raw-stale-references-exercised" (> stale (floor maps 20))) + (check "selection:association-listed-twice-exercised" (> listed-twice (floor maps 50))) + (list :maps maps :pair pairs :none none :index-path index-path :fallback fallback :asymmetric asymmetric + :stale stale :listed-twice listed-twice :differences differences))) + +(defun asymmetry-tests () + ;; With a repeated Role signature equality is not symmetric; only the pairwise search may decide then. + (let* ((map (make-topic-map)) (ty (topic-maps.tmdm::%make-topic map)) (r (topic-maps.tmdm::%make-topic map)) + (p (topic-maps.tmdm::%make-topic map)) (q (topic-maps.tmdm::%make-topic map)) + (a (topic-maps.tmdm::%make-association map ty)) (b (topic-maps.tmdm::%make-association map ty))) + (setf (topic-maps.tmdm::%topic-map-topics map) (list ty r p q) + (topic-maps.tmdm::%association-roles a) (list (topic-maps.tmdm::%make-association-role a r p) (topic-maps.tmdm::%make-association-role a r p)) + (topic-maps.tmdm::%association-roles b) (list (topic-maps.tmdm::%make-association-role b r p) (topic-maps.tmdm::%make-association-role b r q))) + (check "asymmetry:a-equals-b" (topic-maps.tmdm::equal-associations-p a b)) + (check "asymmetry:b-does-not-equal-a" (not (topic-maps.tmdm::equal-associations-p b a))) + (setf (topic-maps.tmdm::%topic-map-associations map) (list a b)) + (check "asymmetry:a-first-is-a-pair" (equal (list a b) (topic-maps.tmdm::scan-next-association-merge map))) + (check "asymmetry:a-first-indexed-agrees" (equal (list a b) (topic-maps.tmdm::next-association-merge map))) + (setf (topic-maps.tmdm::%topic-map-associations map) (list b a)) + (check "asymmetry:b-first-is-no-pair" (null (topic-maps.tmdm::scan-next-association-merge map))) + (check "asymmetry:b-first-indexed-agrees" (null (topic-maps.tmdm::next-association-merge map))))) + +;;; Every search during a run compared with the oracle, nested searches of cascades included + +(defvar *shadow* nil) +(defun shadow-report () *shadow*) +(defmacro with-shadow-search (&body body) + "Run BODY with every NEXT-ASSOCIATION-MERGE call compared with SCAN-NEXT-ASSOCIATION-MERGE on the same map state." + `(let ((*shadow* (list :calls 0 :pairs 0 :inside-normalization 0 :nested 0 :mismatches 0)) (depth 0)) + (sb-int:encapsulate 'topic-maps.tmdm::next-association-merge :shadow + (lambda (original map) + (let ((oracle (topic-maps.tmdm::scan-next-association-merge map)) + (indexed (funcall original map))) + (incf (getf *shadow* :calls)) + (when (> depth 0) (incf (getf *shadow* :inside-normalization))) + (when (> depth 1) (incf (getf *shadow* :nested))) + (when indexed (incf (getf *shadow* :pairs))) + (unless (equal indexed oracle) (incf (getf *shadow* :mismatches))) + indexed))) + (sb-int:encapsulate 'topic-maps.tmdm::normalize-associations :depth + (lambda (original map) (incf depth) (unwind-protect (funcall original map) (decf depth)))) + (unwind-protect (progn ,@body) + (sb-int:unencapsulate 'topic-maps.tmdm::normalize-associations :depth) + (sb-int:unencapsulate 'topic-maps.tmdm::next-association-merge :shadow)))) + +(defmacro counting (functions &body body) + "BODY's value and a plist of how often each of FUNCTIONS was called." + `(let ((counts (list ,@(loop for f in functions append (list (intern (symbol-name f) "KEYWORD") 0))))) + ,@(loop for f in functions + collect `(sb-int:encapsulate ',f :count (lambda (original &rest arguments) + (incf (getf counts ,(intern (symbol-name f) "KEYWORD"))) + (apply original arguments)))) + (unwind-protect (values (progn ,@body) counts) + ,@(loop for f in functions collect `(sb-int:unencapsulate ',f :count))))) + +;;; Invalidation: the index lives for one search. After every mutation the search starts again from the map. + +(defun merge-walk (random) + "Follow normalization on a random unnormalized Map with reifiers: at every step the indexed and the oracle search +must agree (the shadow also compares every nested search of the reifier cascades), then the pair is merged +exactly as NORMALIZE-ASSOCIATIONS does. Returns the number of steps and how the walk ended." + (let ((map (random-association-map random :stale nil :repeated-listing nil :reifiers t :size 14 :max-roles 3 :max-themes 2)) (steps 0)) + (dolist (a (topic-maps.tmdm::%topic-map-associations map)) (topic-maps.tmdm::normalize-roles a)) + (loop + (let ((indexed (topic-maps.tmdm::next-association-merge map)) (oracle (topic-maps.tmdm::scan-next-association-merge map))) + (unless (equal indexed oracle) (return (values steps :differs))) + (unless oracle (return (values steps :done))) + (handler-case (topic-maps.tmdm::merge-two-associations map (first oracle) (second oracle)) + (error () (return (values steps :merge-refused)))) + (incf steps))))) + +(defun invalidation-tests (&key (walks 1500) (seed 20261029)) + (let ((random (sb-ext:seed-random-state seed)) (steps 0) (differs 0) (done 0) (multi-step 0) (refused 0) result counts) + (multiple-value-setq (result counts) + (counting (topic-maps.tmdm::merge-two-topics topic-maps.tmdm::merge-two-associations topic-maps.tmdm::copy-map-graph) + (with-shadow-search + (dotimes (n walks) + (multiple-value-bind (count how) (merge-walk random) + (incf steps count) + (when (> count 1) (incf multi-step)) + (case how (:differs (incf differs)) (:done (incf done)) (:merge-refused (incf refused))))) + (copy-list (shadow-report))))) + (check "invalidation:agrees-after-every-merge-step" (zerop differs)) + (check "invalidation:every-nested-search-agrees" (zerop (getf result :mismatches))) + (check "invalidation:walks-with-several-merges-exercised" (> multi-step (floor walks 10))) + (check "invalidation:walks-reaching-a-fixed-point-exercised" (> done (floor walks 2))) + (check "invalidation:reifier-cascades-merged-topics" (> (getf counts :merge-two-topics) (floor walks 20))) + (check "invalidation:searches-inside-merge-cascades-exercised" (> (getf result :inside-normalization) 0)) + (check "invalidation:preflight-copies-exercised" (> (getf counts :copy-map-graph) 0)) + (list :walks walks :merge-steps steps :several-merges multi-step :fixed-point done :merge-refused refused + :differences differs :shadow result :counts counts))) + +(defun stale-index-tests () + ;; A pair found before a merge names Associations that are no longer live; the search after the merge never returns them. + (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) (c (si map "c")) + (x (topic-maps.tmdm::%make-association map ty)) (y (topic-maps.tmdm::%make-association map ty)) + (z (topic-maps.tmdm::%make-association map ty)) (w (topic-maps.tmdm::%make-association map (si map "other")))) + (setf (topic-maps.tmdm::%association-roles x) (list (topic-maps.tmdm::%make-association-role x r a)) + (topic-maps.tmdm::%association-roles y) (list (topic-maps.tmdm::%make-association-role y r a)) + (topic-maps.tmdm::%association-roles z) (list (topic-maps.tmdm::%make-association-role z r a)) + (topic-maps.tmdm::%association-roles w) (list (topic-maps.tmdm::%make-association-role w r b) + (topic-maps.tmdm::%make-association-role w r c)) + (topic-maps.tmdm::%topic-map-associations map) (list w x y z)) + (let ((before (topic-maps.tmdm::next-association-merge map))) + (check "stale:pair-found-before-the-merge" (equal (list x y) before)) + (topic-maps.tmdm::merge-two-associations map x y) + (let ((after (topic-maps.tmdm::next-association-merge map)) (merged (canonical-association x))) + (check "stale:positive-control-old-handles-are-no-longer-listed" + (notany (lambda (h) (member h (topic-maps.tmdm::%topic-map-associations map))) before)) + (check "stale:old-handles-forward-to-the-representative" (and (eq merged (canonical-association x)) (eq merged (canonical-association y)))) + (check "stale:representative-takes-the-first-position" (equal (list w merged z) (topic-maps.tmdm::%topic-map-associations map))) + (check "stale:search-after-the-merge-names-listed-associations-only" + (every (lambda (h) (member h (topic-maps.tmdm::%topic-map-associations map))) after)) + (check "stale:search-after-the-merge-finds-the-next-pair" (equal (list merged z) after)) + (check "stale:search-agrees-with-the-oracle" (equal after (topic-maps.tmdm::scan-next-association-merge map))) + (check "stale:the-earlier-pair-differs" (not (equal before after))))))) + +;;; Whole reads: indexed and oracle searches run the same normalization to the same result + +(defun random-document (random) + "A CTM document of Associations from small pools, scopes, repeated Roles, reifiers and identifier statements +that merge players, types, Role types, themes and reifiers." + (let ((tops (+ 2 (random 3 random)))) + (with-output-to-string (s) + (flet ((topic () (format nil "t~D" (random tops random))) + (role () (format nil "r~D" (random 2 random))) + (reifier () (format nil "z~D" (random 8 random)))) + (dotimes (i (+ 6 (random 14 random))) + (ecase (random 9 random) + ((0 1) (format s "a~D(~A: ~A, ~A: ~A)~%" (random 2 random) (role) (topic) (role) (topic))) + (2 (format s "a~D(~A: ~A)@~A~%" (random 2 random) (role) (topic) (topic))) + (3 (format s "a~D(~A: ~A, ~A: ~A)@~A,~A~%" (random 2 random) (role) (topic) (role) (topic) (topic) (topic))) + (4 (format s "a~D(~A: ~A) ~~ ~A~%" (random 2 random) (role) (topic) (reifier))) + (5 (format s "a~D(~A: ~A, ~A: ~A) ~~ ~A~%" (random 2 random) (role) (topic) (role) (topic) (reifier))) + (6 (format s "~A ^ ~A .~%" (topic) (ii (topic)))) + (7 (format s "~A ^ ~A .~%" (pick random '("a0" "a1" "r0" "r1" "z0" "z1")) (ii (pick random '("a0" "a1" "r0" "r1" "t0" "z2"))))) + (8 (format s "~A - \"n~D\" .~%" (topic) (random 2 random))))))))) + +(defmacro with-oracle-search (&body body) + `(progn + (sb-int:encapsulate 'topic-maps.tmdm::next-association-merge :oracle + (lambda (original map) (declare (ignore original)) (topic-maps.tmdm::scan-next-association-merge map))) + (unwind-protect (progn ,@body) (sb-int:unencapsulate 'topic-maps.tmdm::next-association-merge :oracle)))) + +(defun reads-equal-tests (&key (documents 600) (seed 20261030)) + (let ((random (sb-ext:seed-random-state seed)) (read 0) (refused 0) (differences 0) (merging 0) (association-merges 0) + (topic-merges 0) (reified 0) (shadow-mismatches 0)) + (dotimes (n documents) + (let ((text (random-document random))) + (multiple-value-bind (indexed indexed-counts) + (counting (topic-maps.tmdm::merge-two-associations topic-maps.tmdm::merge-two-topics) + (with-shadow-search (prog1 (document-outcome text) (incf shadow-mismatches (getf (shadow-report) :mismatches))))) + (multiple-value-bind (oracle oracle-counts) + (with-oracle-search + (counting (topic-maps.tmdm::merge-two-associations topic-maps.tmdm::merge-two-topics) (document-outcome text))) + (cond ((or (not (equal indexed oracle)) (not (equal indexed-counts oracle-counts))) (incf differences)) + (t (incf association-merges (getf indexed-counts :merge-two-associations)) + (incf topic-merges (getf indexed-counts :merge-two-topics)) + (when (plusp (getf indexed-counts :merge-two-associations)) (incf merging)) + (cond ((eq :read (first oracle)) + (incf read) + (when (search "reifier=" (second oracle)) (incf reified))) + (t (incf refused))))))))) + (check "reads:indexed-equals-oracle-on-every-document" (zerop differences)) + (check "reads:every-search-of-every-read-agrees" (zerop shadow-mismatches)) + (check "reads:documents-read-exercised" (> read (floor documents 2))) + (check "reads:association-merging-documents-exercised" (> merging (floor documents 4))) + (check "reads:topic-merges-exercised" (> topic-merges documents)) + (check "reads:reified-documents-exercised" (> reified (floor documents 10))) + (list :documents documents :read read :refused refused :merging merging :association-merges association-merges + :topic-merges topic-merges :reified reified :differences differences :shadow-mismatches shadow-mismatches))) + +;;; Scale: many Associations of one type, the shape of the project CTM's search + +(defun seconds-to (thunk) + (let ((start (get-internal-real-time))) + (values (funcall thunk) (float (/ (- (get-internal-real-time) start) internal-time-units-per-second) 1d0)))) + +(defun scale-tests (&key (associations 600) (budget 60)) + (multiple-value-bind (map seconds) (seconds-to (lambda () (read-case (same-type-document associations 9)))) + (check "scale:duplicates-merged" (= associations (length (topic-map-associations map)))) + (check (format nil "scale:read-within-~Ds" budget) (< seconds budget)) + (list :associations associations :seconds seconds))) + +(defun run-tests () + (let ((topic-maps.ctm.tests::*checks* nil) (search nil) (walks nil) (reads nil) (seconds nil)) + (recorded-outcome-tests) + (asymmetry-tests) + (stale-index-tests) + (setf search (selection-equivalence-tests) walks (invalidation-tests) reads (reads-equal-tests)) + (setf seconds (scale-tests)) + (format t "~&ASSOCIATION-INDEX-SELECTION: ~S~%ASSOCIATION-INDEX-WALKS: ~S~%ASSOCIATION-INDEX-READS: ~S~%ASSOCIATION-INDEX-SCALE: ~S~%" + search walks reads seconds) + (setf *last-checks* (reverse topic-maps.ctm.tests::*checks*)) + (format t "~&ASSOCIATION-INDEX-PASS: ~D checks; ~D documents, ~D API scenarios and ~D rejections equal to the outcomes recorded at 6162ed68.~%" + (length *last-checks*) (length *documents*) (length *api-scenarios*) (length *rejections*)) + *last-checks*)) diff --git a/tests/fixtures/association-index/api-core-subject-rejection.cxtm b/tests/fixtures/association-index/api-core-subject-rejection.cxtm new file mode 100644 index 0000000..120eafb --- /dev/null +++ b/tests/fixtures/association-index/api-core-subject-rejection.cxtm @@ -0,0 +1,48 @@ + + + +http://psi.topicmaps.org/iso13250/model/instance + + + + +http://psi.topicmaps.org/iso13250/model/type + + + + +urn:a + + + + + +urn:b + + + + + +urn:r + + + + +urn:type + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/api-facts.sexp b/tests/fixtures/association-index/api-facts.sexp new file mode 100644 index 0000000..5ade55f --- /dev/null +++ b/tests/fixtures/association-index/api-facts.sexp @@ -0,0 +1,27 @@ +("api-identifiers-and-handles" :ASSOCIATIONS 2 :ONE-ASSOCIATION COMMON-LISP:T + :POSITION 1 :ITEM-IDENTIFIERS ("urn:assoc-1" "urn:assoc-2") :REIFIER + COMMON-LISP:NIL :ROLES 2 :ROLE-HANDLES + (("urn:r" "urn:a|urn:b" ("urn:role-1a" "urn:role-2b") COMMON-LISP:T + COMMON-LISP:NIL) + ("urn:q" "urn:p" ("urn:role-2p") COMMON-LISP:T COMMON-LISP:NIL) + ("urn:q" "urn:p" ("urn:role-2p") COMMON-LISP:T COMMON-LISP:NIL) + ("urn:r" "urn:a|urn:b" ("urn:role-1a" "urn:role-2b") COMMON-LISP:T + COMMON-LISP:NIL)) + :TOPICS 6) +("api-reified-associations" :ASSOCIATIONS 1 :ONE-ASSOCIATION COMMON-LISP:T + :POSITION 0 :ITEM-IDENTIFIERS COMMON-LISP:NIL :REIFIER "urn:x|urn:y" :ROLES 1 + :ROLE-HANDLES + (("urn:r" "urn:a|urn:b" COMMON-LISP:NIL COMMON-LISP:T COMMON-LISP:NIL) + ("urn:r" "urn:a|urn:b" COMMON-LISP:NIL COMMON-LISP:T COMMON-LISP:NIL)) + :TOPICS 5 :REIFIERS-ONE COMMON-LISP:T :INVERSE COMMON-LISP:T) +("api-reified-roles" :ASSOCIATIONS 1 :ONE-ASSOCIATION COMMON-LISP:T :POSITION 0 + :ITEM-IDENTIFIERS COMMON-LISP:NIL :REIFIER COMMON-LISP:NIL :ROLES 1 + :ROLE-HANDLES + (("urn:r" "urn:a|urn:b" COMMON-LISP:NIL COMMON-LISP:T "urn:x|urn:y") + ("urn:r" "urn:a|urn:b" COMMON-LISP:NIL COMMON-LISP:T "urn:x|urn:y")) + :TOPICS 4 :ROLE-REIFIERS-ONE COMMON-LISP:T :ONE-ROLE COMMON-LISP:T) +("api-three-way" :ASSOCIATIONS 2 :ONE-ASSOCIATION COMMON-LISP:T :POSITION 0 + :ITEM-IDENTIFIERS ("urn:1" "urn:2" "urn:3") :REIFIER COMMON-LISP:NIL :ROLES 1 + :ROLE-HANDLES COMMON-LISP:NIL :TOPICS 4 :ORDER (0 1 0 0)) +("api-core-subject-rejection" :CONDITION TOPIC-MAPS.TMDM:CORE-SUBJECT-ERROR + :CODE :CORE-SUBJECT-CONFLICT :UNCHANGED COMMON-LISP:T :ASSOCIATIONS 2) diff --git a/tests/fixtures/association-index/api-identifiers-and-handles.cxtm b/tests/fixtures/association-index/api-identifiers-and-handles.cxtm new file mode 100644 index 0000000..895dd04 --- /dev/null +++ b/tests/fixtures/association-index/api-identifiers-and-handles.cxtm @@ -0,0 +1,65 @@ + + + +urn:other + + + + +urn:p + + + + + +urn:q + + + + +urn:r + + + + +urn:type + + + + +urn:a +urn:b + + + + + + + + + + + + + + + + + +urn:role-2p + + + + + + +urn:role-1a +urn:role-2b + + + +urn:assoc-1 +urn:assoc-2 + + + diff --git a/tests/fixtures/association-index/api-reified-associations.cxtm b/tests/fixtures/association-index/api-reified-associations.cxtm new file mode 100644 index 0000000..87d8858 --- /dev/null +++ b/tests/fixtures/association-index/api-reified-associations.cxtm @@ -0,0 +1,41 @@ + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + +urn:r + + + + +urn:type + + + + +urn:a +urn:b + + + + + +urn:x +urn:y + + +Y + + + + + + + + + + + diff --git a/tests/fixtures/association-index/api-reified-roles.cxtm b/tests/fixtures/association-index/api-reified-roles.cxtm new file mode 100644 index 0000000..18b2689 --- /dev/null +++ b/tests/fixtures/association-index/api-reified-roles.cxtm @@ -0,0 +1,32 @@ + + + +urn:r + + + + +urn:type + + + + +urn:a +urn:b + + + + + +urn:x +urn:y + + + + + + + + + + diff --git a/tests/fixtures/association-index/api-three-way.cxtm b/tests/fixtures/association-index/api-three-way.cxtm new file mode 100644 index 0000000..cb393f9 --- /dev/null +++ b/tests/fixtures/association-index/api-three-way.cxtm @@ -0,0 +1,45 @@ + + + +urn:mid + + + + +urn:r + + + + +urn:type + + + + +urn:a +urn:b +urn:c + + + + + + + + + + + + + + + + + + +urn:1 +urn:2 +urn:3 + + + diff --git a/tests/fixtures/association-index/duplicate-chain.cxtm b/tests/fixtures/association-index/duplicate-chain.cxtm new file mode 100644 index 0000000..e326dbf --- /dev/null +++ b/tests/fixtures/association-index/duplicate-chain.cxtm @@ -0,0 +1,27 @@ + + + +#r + + + + +#t + + + + +#a +#b +#c + + + + + + + + + + + diff --git a/tests/fixtures/association-index/equal-after-player-merge.cxtm b/tests/fixtures/association-index/equal-after-player-merge.cxtm new file mode 100644 index 0000000..aad14f0 --- /dev/null +++ b/tests/fixtures/association-index/equal-after-player-merge.cxtm @@ -0,0 +1,41 @@ + + + +#c + + + + + +#q + + + + +#r + + + + +#t + + + + +#a +#b + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/equal-after-role-type-merge.cxtm b/tests/fixtures/association-index/equal-after-role-type-merge.cxtm new file mode 100644 index 0000000..eea033c --- /dev/null +++ b/tests/fixtures/association-index/equal-after-role-type-merge.cxtm @@ -0,0 +1,26 @@ + + + +#a + + + + + +#t + + + + +#q +#r + + + + + + + + + + diff --git a/tests/fixtures/association-index/equal-after-theme-merge.cxtm b/tests/fixtures/association-index/equal-after-theme-merge.cxtm new file mode 100644 index 0000000..55f889c --- /dev/null +++ b/tests/fixtures/association-index/equal-after-theme-merge.cxtm @@ -0,0 +1,34 @@ + + + +#a + + + + + +#r + + + + +#t + + + + +#s +#u + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/equal-after-type-merge.cxtm b/tests/fixtures/association-index/equal-after-type-merge.cxtm new file mode 100644 index 0000000..d890ba8 --- /dev/null +++ b/tests/fixtures/association-index/equal-after-type-merge.cxtm @@ -0,0 +1,26 @@ + + + +#a + + + + + +#r + + + + +#t +#u + + + + + + + + + + diff --git a/tests/fixtures/association-index/first-pair-is-not-the-first-association.cxtm b/tests/fixtures/association-index/first-pair-is-not-the-first-association.cxtm new file mode 100644 index 0000000..070e54b --- /dev/null +++ b/tests/fixtures/association-index/first-pair-is-not-the-first-association.cxtm @@ -0,0 +1,69 @@ + + + +#a + + + + + +#b + + + + + +#r + + + + +#t + + + + +#u + + + + +#x + + + + + +#y + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/isa-duplicates-merge.cxtm b/tests/fixtures/association-index/isa-duplicates-merge.cxtm new file mode 100644 index 0000000..fcdaf9a --- /dev/null +++ b/tests/fixtures/association-index/isa-duplicates-merge.cxtm @@ -0,0 +1,62 @@ + + + +#a + + + + + +#b + + + + + +http://example.org/k + + +#k +#k2 + + + + + + +http://psi.topicmaps.org/iso13250/model/instance + + + + +http://psi.topicmaps.org/iso13250/model/type + + + + +http://psi.topicmaps.org/iso13250/model/type-instance + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/n-ary-permutation.cxtm b/tests/fixtures/association-index/n-ary-permutation.cxtm new file mode 100644 index 0000000..c430be0 --- /dev/null +++ b/tests/fixtures/association-index/n-ary-permutation.cxtm @@ -0,0 +1,68 @@ + + + +#a + + + + + + +#b + + + + + + +#c + + + + + +#r1 + + + + +#r2 + + + + +#r3 + + + + +#t + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/plain-duplicates.cxtm b/tests/fixtures/association-index/plain-duplicates.cxtm new file mode 100644 index 0000000..017667a --- /dev/null +++ b/tests/fixtures/association-index/plain-duplicates.cxtm @@ -0,0 +1,40 @@ + + + +#a + + + + + +#b + + + + + +#q + + + + +#r + + + + +#t + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/player-differs.cxtm b/tests/fixtures/association-index/player-differs.cxtm new file mode 100644 index 0000000..fee2f3a --- /dev/null +++ b/tests/fixtures/association-index/player-differs.cxtm @@ -0,0 +1,38 @@ + + + +#a + + + + + +#b + + + + + +#r + + + + +#t + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/reified-duplicates-reifiers-merge.cxtm b/tests/fixtures/association-index/reified-duplicates-reifiers-merge.cxtm new file mode 100644 index 0000000..62483b5 --- /dev/null +++ b/tests/fixtures/association-index/reified-duplicates-reifiers-merge.cxtm @@ -0,0 +1,44 @@ + + + +#p + + + + + +#r + + + + +#t + + + + +#x +#y + + +X + + + +Y + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + + + + + + + diff --git a/tests/fixtures/association-index/reified-one-side.cxtm b/tests/fixtures/association-index/reified-one-side.cxtm new file mode 100644 index 0000000..5433996 --- /dev/null +++ b/tests/fixtures/association-index/reified-one-side.cxtm @@ -0,0 +1,39 @@ + + + +#p + + + + + +#r + + + + +#t + + + + +#x + + +X + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + + + + + + + diff --git a/tests/fixtures/association-index/reifier-cascade.cxtm b/tests/fixtures/association-index/reifier-cascade.cxtm new file mode 100644 index 0000000..04b41c9 --- /dev/null +++ b/tests/fixtures/association-index/reifier-cascade.cxtm @@ -0,0 +1,63 @@ + + + +#p + + + + + +#r + + + + +#t + + + + +#u + + + + +#w +#z + + +W + + + +Z + + + + + +#x +#y + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/reifiers-become-equal-associations.cxtm b/tests/fixtures/association-index/reifiers-become-equal-associations.cxtm new file mode 100644 index 0000000..17ac572 --- /dev/null +++ b/tests/fixtures/association-index/reifiers-become-equal-associations.cxtm @@ -0,0 +1,45 @@ + + + +#r + + + + +#t + + + + +#v + + + + +#a +#b + + + + + +#x +#y + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/rejections.sexp b/tests/fixtures/association-index/rejections.sexp new file mode 100644 index 0000000..2286838 --- /dev/null +++ b/tests/fixtures/association-index/rejections.sexp @@ -0,0 +1,5 @@ +("reifier-reifies-association-and-name" TOPIC-MAPS.CTM:CTM-REJECTION + :REIFIER-CONFLICT) +("equal-associations-with-core-subject-reifiers" TOPIC-MAPS.CTM:CTM-REJECTION + :CORE-SUBJECT-CONFLICT) +("reifier-merge-conflict" TOPIC-MAPS.CTM:CTM-REJECTION :REIFIER-CONFLICT) diff --git a/tests/fixtures/association-index/repeated-role-signature.cxtm b/tests/fixtures/association-index/repeated-role-signature.cxtm new file mode 100644 index 0000000..840f959 --- /dev/null +++ b/tests/fixtures/association-index/repeated-role-signature.cxtm @@ -0,0 +1,48 @@ + + + +#a + + + + + + +#b + + + + + +#q + + + + +#r + + + + +#t + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/role-count-differs.cxtm b/tests/fixtures/association-index/role-count-differs.cxtm new file mode 100644 index 0000000..840f959 --- /dev/null +++ b/tests/fixtures/association-index/role-count-differs.cxtm @@ -0,0 +1,48 @@ + + + +#a + + + + + + +#b + + + + + +#q + + + + +#r + + + + +#t + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/role-order-permutation.cxtm b/tests/fixtures/association-index/role-order-permutation.cxtm new file mode 100644 index 0000000..017667a --- /dev/null +++ b/tests/fixtures/association-index/role-order-permutation.cxtm @@ -0,0 +1,40 @@ + + + +#a + + + + + +#b + + + + + +#q + + + + +#r + + + + +#t + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/role-type-differs.cxtm b/tests/fixtures/association-index/role-type-differs.cxtm new file mode 100644 index 0000000..795092e --- /dev/null +++ b/tests/fixtures/association-index/role-type-differs.cxtm @@ -0,0 +1,38 @@ + + + +#a + + + + + + +#q + + + + +#r + + + + +#t + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/same-type-80.cxtm b/tests/fixtures/association-index/same-type-80.cxtm new file mode 100644 index 0000000..5a02606 --- /dev/null +++ b/tests/fixtures/association-index/same-type-80.cxtm @@ -0,0 +1,1492 @@ + + + +#o0 + + + + + + + + + + + + + + + + +#o1 + + + + + + + + + + + + + + + + +#o2 + + + + + + + + + + + + + + + + +#o3 + + + + + + + + + + + + + + + +#o4 + + + + + + + + + + + + + + + +#o5 + + + + + + + + + + + + + + + +#o6 + + + + + + + + + + + + + + + +#p0 + + + + + +#p1 + + + + + +#p10 + + + + + +#p11 + + + + + +#p12 + + + + + +#p13 + + + + + +#p14 + + + + + +#p15 + + + + + +#p16 + + + + + +#p17 + + + + + +#p18 + + + + + +#p19 + + + + + +#p2 + + + + + +#p20 + + + + + +#p21 + + + + + +#p22 + + + + + +#p23 + + + + + +#p24 + + + + + +#p25 + + + + + +#p26 + + + + + +#p27 + + + + + +#p28 + + + + + +#p29 + + + + + +#p3 + + + + + +#p30 + + + + + +#p31 + + + + + +#p32 + + + + + +#p33 + + + + + +#p34 + + + + + +#p35 + + + + + +#p36 + + + + + +#p37 + + + + + +#p38 + + + + + +#p39 + + + + + +#p4 + + + + + +#p40 + + + + + +#p41 + + + + + +#p42 + + + + + +#p43 + + + + + +#p44 + + + + + +#p45 + + + + + +#p46 + + + + + +#p47 + + + + + +#p48 + + + + + +#p49 + + + + + +#p5 + + + + + +#p50 + + + + + +#p51 + + + + + +#p52 + + + + + +#p53 + + + + + +#p54 + + + + + +#p55 + + + + + +#p56 + + + + + +#p57 + + + + + +#p58 + + + + + +#p59 + + + + + +#p6 + + + + + +#p60 + + + + + +#p61 + + + + + +#p62 + + + + + +#p63 + + + + + +#p64 + + + + + +#p65 + + + + + +#p66 + + + + + +#p67 + + + + + +#p68 + + + + + +#p69 + + + + + +#p7 + + + + + +#p70 + + + + + +#p71 + + + + + +#p72 + + + + + +#p73 + + + + + +#p74 + + + + + +#p75 + + + + + +#p76 + + + + + +#p77 + + + + + +#p78 + + + + + +#p79 + + + + + +#p8 + + + + + +#p9 + + + + + +#q + + + + +#r + + + + +#t + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/scope-collapses-after-theme-merge.cxtm b/tests/fixtures/association-index/scope-collapses-after-theme-merge.cxtm new file mode 100644 index 0000000..55f889c --- /dev/null +++ b/tests/fixtures/association-index/scope-collapses-after-theme-merge.cxtm @@ -0,0 +1,34 @@ + + + +#a + + + + + +#r + + + + +#t + + + + +#s +#u + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/scoped-duplicates.cxtm b/tests/fixtures/association-index/scoped-duplicates.cxtm new file mode 100644 index 0000000..03b30e5 --- /dev/null +++ b/tests/fixtures/association-index/scoped-duplicates.cxtm @@ -0,0 +1,69 @@ + + + +#a + + + + + + + + +#r + + + + +#s + + + + +#t + + + + +#u + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/association-index/type-differs.cxtm b/tests/fixtures/association-index/type-differs.cxtm new file mode 100644 index 0000000..64eed7f --- /dev/null +++ b/tests/fixtures/association-index/type-differs.cxtm @@ -0,0 +1,38 @@ + + + +#a + + + + + + +#r + + + + +#t + + + + +#u + + + + + + + + + + + + + + + + + diff --git a/topic-maps.asd b/topic-maps.asd index 9d29fca..625c8f4 100644 --- a/topic-maps.asd +++ b/topic-maps.asd @@ -339,3 +339,11 @@ :perform (asdf:test-op (operation component) (declare (ignore operation component)) (uiop:symbol-call :topic-maps.normalization-index.tests :run-tests))) + +(asdf:defsystem "topic-maps/tmdm/association-index-tests" + :description "Which Associations merge next: outcomes recorded at 6162ed68, retained Association and Role handles, asymmetric equality, invalidation and reader scale" + :depends-on ("topic-maps/tmdm/import-tests") :serial t + :components ((:file "tests/association-index")) + :perform (asdf:test-op (operation component) + (declare (ignore operation component)) + (uiop:symbol-call :topic-maps.association-index.tests :run-tests)))