+(defpackage #:topic-maps.normalization-index.tests
+ (:use #:cl #:topic-maps.tmdm)
+ (:import-from #:topic-maps.ctm.tests #:check #:cxtm)
+ (:import-from #:topic-maps.variant.tests #:condition-from)
+ (:import-from #:topic-maps.identifier.tests #:si #:current)
+ (:export #:run-tests #:normalization-index-checks #:record-expected))
+(in-package #:topic-maps.normalization-index.tests)
+
+;;; Which Topics merge next, and the results that must not change while the search for them changes.
+;;; The expected CXTM of every case and the class and code of every rejection were recorded from the
+;;; unchanged implementation at b2eecffa (RECORD-EXPECTED) before NEXT-TOPIC-MERGE existed; they are not
+;;; derived from the implementation under test. SCAN-NEXT-TOPIC-MERGE is the b2eecffa search, kept as the
+;;; fallback and used here as the oracle.
+
+(defvar *last-checks* nil)
+(defun normalization-index-checks () *last-checks*)
+(defparameter +document+ "https://example.invalid/n/doc.ctm")
+(defvar *fixture-directory* nil)
+(defun fixture-directory ()
+ (or *fixture-directory* (asdf:system-relative-pathname "topic-maps" "tests/fixtures/normalization-index/")))
+(defun read-case (text) (topic-maps.ctm:deserialize-string text :document-iri +document+ :source-name "normalization-index"))
+(defun pick (random sequence) (elt sequence (random (length sequence) random)))
+
+(defun chain-document (topics links)
+ "TOPICS Topics with one subject identifier each and a Name, LINKS later statements that give Topic 2I the
+item identifier equal to the subject identifier of Topic 2I+1, and one Association per Topic."
+ (with-output-to-string (s)
+ (dotimes (i topics) (format s "t~D http://example.org/s/~D ; - \"Topic ~D\" .~%" i i i))
+ (dotimes (i topics) (format s "rel~D(from: t~D, to: t~D)~%" (mod i 5) i (mod (* 7 (1+ i)) topics)))
+ (dotimes (i links) (format s "t~D ^ http://example.org/s/~D .~%" (* 2 i) (1+ (* 2 i))))))
+
+;;; Reifiers: the corpus has 57 reified Associations, each reifier Topic named in its own statement.
+
+(defun reified-document (associations &key (duplicate-every 0))
+ "ASSOCIATIONS reified Associations, each reifier Topic with a subject identifier and a Name. Every
+DUPLICATE-EVERYth Association is stated a second time with a second reifier Topic: the two Associations are
+equal, so their reifier Topics merge although nothing else identifies them."
+ (with-output-to-string (s)
+ (dotimes (i associations)
+ (format s "p~D http://example.org/p/~D ; - \"P ~D\" .~%" i i i)
+ (format s "r~D http://example.org/r/~D ; - \"R ~D\" .~%" i i i)
+ (format s "rel~D(from: p~D, to: p~D) ~~ r~D~%" (mod i 4) i (mod (* 5 (1+ i)) associations) i))
+ (when (plusp duplicate-every)
+ (loop for i from 0 below associations by duplicate-every
+ do (format s "q~D http://example.org/q/~D ; - \"Q ~D\" .~%" i i i)
+ (format s "rel~D(from: p~D, to: p~D) ~~ q~D~%" (mod i 4) i (mod (* 5 (1+ i)) associations) i)))))
+
+;;; Documents whose result must not change, and the nonconflicting-reifier merges among them
+
+(defparameter *documents*
+ `(("identifier-acquisition" ,(format nil "a - \"A\" .~%b - \"B\" .~%a ^ https://example.invalid/n/doc.ctm#b ."))
+ ("ii-si-cross-identity" ,(format nil "x http://example.org/s .~%y ^ http://example.org/s ."))
+ ("transitive-through-third" ,(format nil "a http://example.org/1 .~%b http://example.org/2 .~%c - \"C\" .~%c ^ http://example.org/1 .~%c http://example.org/2 ."))
+ ("transitive-late-chain" ,(format nil "p http://example.org/p .~%q http://example.org/q .~%r http://example.org/r .~%q ^ http://example.org/r .~%p http://example.org/q ."))
+ ("subject-locator-merge" ,(format nil "s1 = http://example.org/doc .~%s2 = http://example.org/doc ."))
+ ("si-and-sl-stay-apart" ,(format nil "t1 http://example.org/z .~%t2 = http://example.org/z ."))
+ ("reified-duplicate-associations" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%x - \"X\" .~%y - \"Y\" ."))
+ ("reified-duplicate-names" ,(format nil "n - \"N\" ~~ nr .~%n - \"N\" ~~ nr2 ."))
+ ("topic-map-reifier" ,(format nil "~~ mapr~%mapr - \"M\" ."))
+ ("reifier-merges-by-identifier" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ y~%y ^ https://example.invalid/n/doc.ctm#z .~%z - \"Z\" ."))
+ ("reifier-acquires-another-topics-identifier" ,(format nil "t(r: p) ~~ x~%x ^ https://example.invalid/n/doc.ctm#w .~%w - \"W\" .~%u(r: q) ~~ v"))
+ ("equal-owners-make-the-reified-associations-equal" ,(format nil "a(r: p) ~~ x~%b(r: p) ~~ y~%a ^ https://example.invalid/n/doc.ctm#b ."))
+ ("equal-reifiers-of-equal-items" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%x ^ https://example.invalid/n/doc.ctm#y ."))
+ ("isa-ako" ,(format nil "a isa b .~%b ako c .~%d isa b .~%e isa c ."))
+ ("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 ."))
+ ("n-ary-duplicate-roles" "t(r1: a, r2: b, r3: c, r1: a)")
+ ("wildcard-merge" "?foo . ?foo .")
+ ("associations-equal-after-topic-merge" ,(format nil "t(r: a, q: c)~%t(r: b, q: c) ~~ x~%t(r: a, q: c) ~~ y~%b ^ https://example.invalid/n/doc.ctm#a ."))
+ ("chain-40-topics" ,(chain-document 40 12))
+ ("reified-30-associations" ,(reified-document 30))
+ ("reified-30-associations-merging-reifiers" ,(reified-document 30 :duplicate-every 3)))
+ "CTM documents whose CXTM is recorded.")
+
+;;; The staged-import scenarios behind the nonconflicting-reifier preference: the Reifier Topics precede
+;;; the owners and Types in both maps, and the reified Names become equal only after those Topics merge.
+
+(defun import-outcome (build)
+ (multiple-value-bind (target source) (funcall build)
+ (import-map-content target source)
+ (cxtm target +document+)))
+
+(defun scenario-reifier-first ()
+ (let* ((target (make-topic-map)) (source (make-topic-map))
+ (r (si target "r")) (s (si source "r")) (a (si target "owner")) (b (si source "owner"))
+ (ty (si target "type")) (sy (si source "type")) (n (add-name a "N" :type ty)) (m (add-name b "N" :type sy)))
+ (set-item-reifier n r) (set-item-reifier m s)
+ (values target source)))
+
+(defun scenario-cascade ()
+ ;; Equal Names merge their Reifiers, which are themselves types, players and themes of further items.
+ (let* ((target (make-topic-map)) (source (make-topic-map)) (a (si target "owner")) (b (si source "owner"))
+ (ty (si target "name-type")) (sy (si source "name-type")) (r (si target "r")) (s (si source "s"))
+ (n (add-name a "N" :type ty)) (m (add-name b "N" :type sy)))
+ (add-occurrence r r "O" :scope (list r)) (add-occurrence s s "O" :scope (list s))
+ (make-association target r (list (list r r)) :scope (list r)) (make-association source s (list (list s s)) :scope (list s))
+ (set-item-reifier n r) (set-item-reifier m s)
+ (values target source)))
+
+(defun scenario-reifier-chain ()
+ ;; Three levels: the Reifiers of equal Names are the owners of further equal Names with their own Reifiers.
+ (let* ((target (make-topic-map)) (source (make-topic-map)) (a (si target "owner")) (b (si source "owner"))
+ (ty (si target "type")) (sy (si source "type")) (r (si target "r")) (s (si source "s"))
+ (r2 (si target "r2")) (s2 (si source "s2"))
+ (n (add-name a "N" :type ty)) (m (add-name b "N" :type sy))
+ (k (add-name r "K" :type ty)) (l (add-name s "K" :type sy)))
+ (set-item-reifier n r) (set-item-reifier m s) (set-item-reifier k r2) (set-item-reifier l s2)
+ (values target source)))
+
+(defparameter *scenarios*
+ '(("import-reifier-first" scenario-reifier-first) ("import-cascade" scenario-cascade)
+ ("import-reifier-chain" scenario-reifier-chain))
+ "Staged imports whose resulting CXTM is recorded.")
+
+;;; Rejections: conflict signalling and preflight rejection must stay as recorded
+
+(defparameter *rejections*
+ `(("reifier-reifies-two-items" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ x"))
+ ("reifier-merge-conflict" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ y~%x ^ https://example.invalid/n/doc.ctm#y ."))
+ ("core-subject-conflict" ,(format nil "a http://psi.topicmaps.org/iso13250/model/type .~%a http://psi.topicmaps.org/iso13250/model/instance ."))
+ ("core-subject-merge-conflict" ,(format nil "a http://psi.topicmaps.org/iso13250/model/type .~%b http://psi.topicmaps.org/iso13250/model/instance .~%a ^ http://psi.topicmaps.org/iso13250/model/instance ."))
+ ("unclosed-association" "a(r: b"))
+ "CTM documents whose rejection is recorded as condition class and code.")
+
+(defun rejecting-scenario-reifier-conflict ()
+ (let* ((target (make-topic-map)) (source (make-topic-map)) (a (si target "owner")) (b (si source "owner"))
+ (ty (si target "type")) (sy (si source "type")) (r (si target "r")) (s (si source "r")))
+ (set-item-reifier (add-name a "Different" :type ty) r) (set-item-reifier (add-name b "Name" :type sy) s)
+ (values target source)))
+
+(defun rejecting-scenario-retained-root-reifier ()
+ (let* ((target (make-topic-map)) (source (make-topic-map)) (r (si target "r")) (s (si source "r")) (owner (si source "owner")))
+ (set-item-reifier target r) (set-item-reifier (add-default-name owner "N") s)
+ (values target source)))
+
+(defparameter *rejecting-scenarios*
+ '(("import-reifier-conflict" rejecting-scenario-reifier-conflict)
+ ("import-retained-root-reifier" rejecting-scenario-retained-root-reifier)))
+
+(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))
+ ((typep c 'map-import-error) (map-import-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 record-expected ()
+ "Write the expected outcomes with the implementation now loaded. Run once, at b2eecffa."
+ (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)))
+ (dolist (case *scenarios*)
+ (destructuring-bind (kind value &rest rest) (outcome (lambda () (import-outcome (symbol-function (second case)))))
+ (declare (ignore rest))
+ (unless (eq kind :read) (error "Scenario ~A was refused: ~S" (first case) value))
+ (record (first case) value))))
+ (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))
+ (dolist (case *rejecting-scenarios*)
+ (prin1 (cons (first case) (rest (outcome (lambda () (import-outcome (symbol-function (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 expected-rejections ()
+ (with-open-file (in (merge-pathnames "rejections.sexp" (fixture-directory)))
+ (let ((*read-eval* nil)) (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-b2eecffa" (first case)) (string= (second o) (expected-cxtm (first case))))))
+ (dolist (case *scenarios*)
+ (let ((o (outcome (lambda () (import-outcome (symbol-function (second case)))))))
+ (check (format nil "scenario:~A:cxtm-equals-b2eecffa" (first case))
+ (and (eq :read (first o)) (string= (second o) (expected-cxtm (first case)))))))
+ (let ((expected (expected-rejections)))
+ (flet ((same (name o)
+ (let ((recorded (rest (assoc name expected :test #'string=))))
+ (check (format nil "rejection:~A:recorded" name) recorded)
+ (check (format nil "rejection:~A:class-and-code-equal-b2eecffa" name) (equal (rest o) recorded)))))
+ (dolist (case *rejections*) (same (first case) (document-outcome (second case))))
+ (dolist (case *rejecting-scenarios*)
+ (same (first case) (outcome (lambda () (import-outcome (symbol-function (second case))))))))))
+
+;;; Semantics that no recorded text shows: canonical representatives, retained handles, reifier preference
+
+(defun live-p (topic map) (member topic (topic-map-topics map) :test #'eq))
+
+(defun handle-tests (with-reifier)
+ (let* ((map (make-topic-map)) (label (if with-reifier "with-reifier" "plain"))
+ (a (si map "a")) (b (si map "b")) (c (intern-topic map :item-identifier "urn:c")) (other (si map "other")))
+ (when with-reifier
+ (set-item-reifier (make-association map other (list (list other a))) (si map "reifier")))
+ (add-topic-identifier c :item-identifier "urn:a")
+ (check (format nil "handles:~A:c-merged-with-a" label) (eq (canonical-topic a) (canonical-topic c)))
+ (check (format nil "handles:~A:b-still-apart" label) (not (eq (canonical-topic a) (canonical-topic b))))
+ (add-topic-identifier c :subject-identifier "urn:b")
+ (let ((merged (canonical-topic a)))
+ (check (format nil "handles:~A:transitive-one-topic" label)
+ (and (eq merged (canonical-topic b)) (eq merged (canonical-topic c))))
+ (check (format nil "handles:~A:representative-is-live" label) (live-p merged map))
+ (check (format nil "handles:~A:obsolete-handles-are-not-live-and-forward" label)
+ (every (lambda (h) (or (eq h merged) (and (not (live-p h map)) (eq merged (canonical-topic h))))) (list a b c)))
+ (check (format nil "handles:~A:other-untouched" label) (eq other (canonical-topic other)))
+ (check (format nil "handles:~A:model-valid" label)
+ (and (topic-maps.tmdm::validate-map-item-identifiers map) (topic-maps.tmdm::validate-map-reification map))))))
+
+(defun representative-tests ()
+ ;; Three Topics become one; the representative takes the place of the first of them, whatever the order of merging.
+ (let* ((map (make-topic-map)) (x (si map "x")) (a (si map "a")) (b (si map "b")) (y (si map "y"))
+ (c (intern-topic map :item-identifier "urn:c")))
+ (add-topic-identifier c :subject-identifier "urn:a") (add-topic-identifier c :subject-identifier "urn:b")
+ (let ((merged (canonical-topic a)))
+ (check "representative:one-topic-for-three-handles" (and (eq merged (canonical-topic b)) (eq merged (canonical-topic c))))
+ (check "representative:replaces-the-first-merged-topic-in-place"
+ (equal (list x merged y) (topic-map-topics map))))))
+
+(defun reifier-preference-tests ()
+ ;; Staged: the reifier Topics are equal (same subject identifier) but reify items that become equal only after
+ ;; their owners and types merge. The owners and types merge first; the reifiers then merge without conflict.
+ (multiple-value-bind (target source) (scenario-reifier-first)
+ (let ((r (si target "r")) (n (first (topic-names (si target "owner")))))
+ (multiple-value-bind (map resolve) (import-map-content target source)
+ (let ((s (si source "r")))
+ (check "preference:reifier-topics-merge-after-their-owners" (eq (canonical-topic r) (funcall resolve s)))
+ (check "preference:one-name-one-reifier"
+ (let ((names (topic-names (current (si map "owner")))))
+ (and (= 1 (length names)) (eq (canonical-topic r) (item-reifier (first names)))
+ (eq (canonical-topic-name n) (first names)))))
+ (check "preference:inverse-is-consistent" (eq (canonical-topic-name n) (topic-reified (canonical-topic r))))
+ (check "preference:model-valid" (topic-maps.tmdm::validate-map-reification map))))))
+ ;; The conflict itself is still signalled when no nonconflicting merge is available, before any mutation.
+ (multiple-value-bind (target source) (rejecting-scenario-reifier-conflict)
+ (let* ((before (topic-maps.ctm.tests::map-state target)) (c (condition-from (lambda () (import-map-content target source)))))
+ (check "preference:conflict-still-signalled" (and (typep c 'reification-error) (eq :reifier-conflict (reification-error-code c))))
+ (check "preference:conflict-leaves-the-target-unchanged" (equal before (topic-maps.ctm.tests::map-state target))))))
+
+;;; The search itself, against the b2eecffa search on unnormalized maps
+
+(defun random-map (random topics)
+ "An unnormalized Map: TOPICS raw Topics with identifiers from small pools (so equal Topics are frequent), raw
+Associations and Names, and Reifiers set directly. Reifier Topics are often equal to each other while the items
+they reify differ, which is the case the nonconflicting preference exists for. Sometimes one Topic reifies two
+items (the fallback). Nothing is merged."
+ (let* ((map (make-topic-map)) (single (not (zerop (random 4 random))))
+ (made (loop repeat topics collect (topic-maps.tmdm::%make-topic map))))
+ (flet ((pool (prefix n) (format nil "http://example.org/~A/~D" prefix (random n random))))
+ (setf (topic-maps.tmdm::%topic-map-topics map) made)
+ (dolist (topic made)
+ (dotimes (k (random 3 random)) (push (pool "id" (* 2 topics)) (topic-maps.tmdm::%topic-item-identifiers topic)))
+ (dotimes (k (random 2 random)) (push (pool "id" (* 2 topics)) (topic-maps.tmdm::%topic-subject-identifiers topic)))
+ (when (zerop (random 4 random)) (push (pool "id" (* 2 topics)) (topic-maps.tmdm::%topic-subject-locators topic))))
+ (let ((items nil))
+ (dotimes (k (random 5 random))
+ (let* ((type (pick random made)) (association (topic-maps.tmdm::%make-association map type)))
+ (setf (topic-maps.tmdm::%association-roles association)
+ (list (topic-maps.tmdm::%make-association-role association type (pick random made))))
+ (push association (topic-maps.tmdm::%topic-map-associations map))
+ (push association items)))
+ (dotimes (k (random 4 random))
+ (let* ((owner (pick random made)) (name (topic-maps.tmdm::%make-topic-name (format nil "n~D" k) owner owner)))
+ (push name (topic-maps.tmdm::%topic-names owner))
+ (push name items)))
+ (when (zerop (random 5 random)) (push map items))
+ (let ((unused (copy-list made)))
+ (dolist (item items)
+ (when (zerop (random 3 random))
+ ;; single reifiers: each Topic reifies at most one item; otherwise any Topic may be taken again
+ (let ((reifier (if single
+ (and unused (let ((r (pick random unused))) (setf unused (remove r unused)) r))
+ (pick random made))))
+ (when reifier (setf (topic-maps.tmdm::%item-reifier item) reifier))))))
+ ;; two Topics that reify items now share an identifier: equal Reifiers of (usually) different items
+ (let ((reifiers (remove-duplicates (loop for item in items for r = (topic-maps.tmdm::%item-reifier item) when r collect r))))
+ (when (and (rest reifiers) (zerop (random 2 random)))
+ (let ((iri (pool "reifier" topics)))
+ (push iri (topic-maps.tmdm::%topic-subject-identifiers (first reifiers)))
+ (push iri (topic-maps.tmdm::%topic-subject-identifiers (pick random (rest reifiers)))))))))
+ map))
+
+(defun selection (thunk)
+ (handler-case (list :pair (let ((pair (funcall thunk))) (and pair (mapcar #'position-of-topic pair))))
+ (reification-error (c) (list :refused (reification-error-code c)))))
+(defvar *topics-in-order* nil)
+(defun position-of-topic (topic) (position topic *topics-in-order* :test #'eq))
+
+(defun differs-from-first-pair-p (map)
+ "True when the oracle's choice is not simply the first equal pair: a nonconflicting pair was preferred."
+ (let ((first-pair (ignore-errors (topic-maps.tmdm::equal-pair (topic-maps.tmdm::%topic-map-topics map)
+ #'topic-maps.tmdm::equal-topics-p)))
+ (chosen (ignore-errors (topic-maps.tmdm::scan-next-topic-merge map))))
+ (and first-pair chosen (not (equal first-pair chosen)))))
+
+(defun selection-equivalence-tests (&key (maps 4000) (seed 20261027))
+ (let ((random (sb-ext:seed-random-state seed)) (pairs 0) (none 0) (refused 0) (preferred 0) (differences 0))
+ (dotimes (n maps)
+ (let* ((map (random-map random (+ 2 (random 14 random))))
+ (*topics-in-order* (topic-maps.tmdm::%topic-map-topics map))
+ (indexed (selection (lambda () (topic-maps.tmdm::next-topic-merge map))))
+ (oracle (selection (lambda () (topic-maps.tmdm::scan-next-topic-merge map)))))
+ (cond ((not (equal indexed oracle)) (incf differences))
+ ((eq :refused (first oracle)) (incf refused))
+ ((second oracle) (incf pairs) (when (differs-from-first-pair-p map) (incf preferred)))
+ (t (incf none)))))
+ (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 0))
+ (check "selection:nonconflicting-preference-exercised" (> preferred (floor maps 50)))
+ (check "selection:fallback-exercised" (> refused (floor maps 100)))
+ (list :maps maps :pair pairs :none none :preferred preferred :refused refused :differences differences)))
+
+;;; Invalidation: the index lives for one search. After every mutation the search starts again from the map.
+
+(defun merge-walk (random topics)
+ "Follow normalization on a random unnormalized Map: at every step the indexed and the oracle search must agree,
+then the oracle's pair is merged exactly as NORMALIZE-TOPIC-MAP does. Returns the number of steps and how the walk ended."
+ (let ((map (random-map random topics)) (steps 0))
+ (loop
+ (let* ((*topics-in-order* (topic-maps.tmdm::%topic-map-topics map))
+ (indexed (selection (lambda () (topic-maps.tmdm::next-topic-merge map))))
+ (oracle (selection (lambda () (topic-maps.tmdm::scan-next-topic-merge map)))))
+ (unless (equal indexed oracle) (return (values steps :differs)))
+ (unless (and (eq :pair (first oracle)) (second oracle)) (return (values steps (if (eq :refused (first oracle)) :refused :done))))
+ (let ((pair (topic-maps.tmdm::scan-next-topic-merge map)))
+ (handler-case (topic-maps.tmdm::merge-two-topics map (first pair) (second pair))
+ (error () (return (values steps :merge-refused))))
+ (incf steps))))))
+
+(defun invalidation-tests (&key (walks 800) (seed 20261028))
+ (let ((random (sb-ext:seed-random-state seed)) (steps 0) (differs 0) (done 0) (multi-step 0))
+ (dotimes (n walks)
+ (multiple-value-bind (count how) (merge-walk random (+ 3 (random 12 random)))
+ (incf steps count)
+ (when (> count 1) (incf multi-step))
+ (case how (:differs (incf differs)) (:done (incf done)))))
+ (check "invalidation:agrees-after-every-merge-step" (zerop differs))
+ (check "invalidation:walks-with-several-merges-exercised" (> multi-step (floor walks 10)))
+ (check "invalidation:walks-reaching-a-fixed-point-exercised" (> done (floor walks 4)))
+ (list :walks walks :merge-steps steps :several-merges multi-step :fixed-point done :differences differs)))
+
+(defun stale-reference-tests ()
+ ;; A pair found before a merge names Topics that are no longer live; the search after the merge never returns them.
+ (let* ((map (make-topic-map)) (a (si map "a")) (b (si map "b")) (c (si map "c")))
+ ;; make a~b and b~c equal without normalizing: raw identifiers, as an unnormalized staged map has them
+ (push "urn:ab" (topic-maps.tmdm::%topic-subject-identifiers a)) (push "urn:ab" (topic-maps.tmdm::%topic-item-identifiers b))
+ (push "urn:bc" (topic-maps.tmdm::%topic-subject-identifiers b)) (push "urn:bc" (topic-maps.tmdm::%topic-subject-identifiers c))
+ (let ((before (topic-maps.tmdm::next-topic-merge map)))
+ (check "stale:pair-found-before-the-merge" (equal (list a b) before))
+ (topic-maps.tmdm::merge-two-topics map a b)
+ (let ((after (topic-maps.tmdm::next-topic-merge map)) (merged (canonical-topic a)))
+ (check "stale:positive-control-old-handles-are-no-longer-live" (and (not (live-p a map)) (not (live-p b map))))
+ (check "stale:old-handles-forward-to-the-representative" (and (eq merged (canonical-topic a)) (eq merged (canonical-topic b))))
+ (check "stale:search-after-the-merge-names-live-topics-only" (every (lambda (tpc) (live-p tpc map)) after))
+ (check "stale:search-after-the-merge-finds-the-next-pair" (equal (list merged c) after))
+ (check "stale:search-agrees-with-the-oracle" (equal after (topic-maps.tmdm::scan-next-topic-merge map)))))))
+
+(defun reifier-mutation-tests ()
+ ;; The reification inverse changes between searches (set, replace, clear); no search may use an earlier state.
+ ;; The reifier Topics r, s precede the owners a, b, so the first equal pair is the reifiers' as soon as they are equal.
+ (let* ((map (make-topic-map)) (r (si map "r")) (s (si map "s")) (a (si map "a")) (b (si map "b"))
+ (x (add-name a "X" :type r)) (y (add-name b "Y" :type r)))
+ (flet ((result (function)
+ (handler-case (funcall function map) (reification-error (c) (list :refused (reification-error-code c)))))
+ (sid (topic iri) (push iri (topic-maps.tmdm::%topic-subject-identifiers topic))))
+ (flet ((agree (label)
+ (check (concatenate 'string "reifier-mutation:" label)
+ (equal (result #'topic-maps.tmdm::next-topic-merge) (result #'topic-maps.tmdm::scan-next-topic-merge)))))
+ (sid a "urn:ab") (sid b "urn:ab")
+ (agree "equal-owners-no-reifier")
+ (setf (topic-maps.tmdm::%item-reifier x) r (topic-maps.tmdm::%item-reifier y) s)
+ (agree "reifiers-of-different-items-not-equal")
+ (sid r "urn:rs") (sid s "urn:rs")
+ (check "reifier-mutation:preferred-pair-skips-the-conflicting-reifiers"
+ (equal (list a b) (topic-maps.tmdm::next-topic-merge map)))
+ (check "reifier-mutation:the-first-equal-pair-is-the-conflicting-one"
+ (equal (list r s) (topic-maps.tmdm::equal-pair (topic-map-topics map) #'topic-maps.tmdm::equal-topics-p)))
+ (agree "equal-reifiers-of-different-items")
+ (setf (topic-maps.tmdm::%item-reifier y) nil)
+ (check "reifier-mutation:one-side-cleared-makes-the-reifiers-mergeable"
+ (equal (list r s) (topic-maps.tmdm::next-topic-merge map)))
+ (agree "one-reifier-cleared")
+ (setf (topic-maps.tmdm::%item-reifier y) r)
+ (check "reifier-mutation:one-topic-reifying-two-items-is-the-recorded-conflict"
+ (equal '(:refused :reifier-conflict) (result #'topic-maps.tmdm::next-topic-merge)))
+ (agree "one-topic-reifying-two-items-falls-back")))))
+
+(defun stale-listed-topic-tests ()
+ ;; Not reachable through the public API: a Topic that was replaced but is still listed. TOPIC-REIFIED resolves
+ ;; it to its representative, so the pairwise search finds the pair although no identifier is shared; the index,
+ ;; which would not, must not be trusted here.
+ (let* ((map (make-topic-map)) (a (si map "a")) (b (si map "b")) (owner (si map "owner"))
+ (name (add-name owner "N" :type a)))
+ (setf (topic-maps.tmdm::%item-reifier name) a (topic-maps.tmdm::%topic-forward b) a)
+ (check "stale-listed:pairwise-search-finds-the-replaced-topic-equal-to-its-representative"
+ (equal (list a b) (topic-maps.tmdm::scan-next-topic-merge map)))
+ (check "stale-listed:indexed-search-defers-to-it" (equal (list a b) (topic-maps.tmdm::next-topic-merge map)))))
+
+;;; Whole reads: indexed and oracle searches run the same normalization to the same result
+
+(defun random-document (random)
+ "A CTM document with identifier statements from small pools, reified Names and Associations."
+ (let ((tops (+ 3 (random 7 random))))
+ (with-output-to-string (s)
+ (flet ((topic () (format nil "t~D" (random tops random))) (iri (kind) (format nil "http://example.org/~A/~D" kind (random (* 2 tops) random))))
+ (dotimes (i (+ 4 (random 14 random)))
+ (ecase (random 8 random)
+ (0 (format s "~A ~A .~%" (topic) (iri "i")))
+ (1 (format s "~A ^ ~A .~%" (topic) (iri "i")))
+ (2 (format s "~A = ~A .~%" (topic) (iri "l")))
+ (3 (format s "~A - \"n~D\" .~%" (topic) (random 2 random)))
+ (4 (format s "~A - \"n~D\" ~~ ~A .~%" (topic) (random 2 random) (topic)))
+ (5 (format s "rel~D(r: ~A, q: ~A)~%" (random 2 random) (topic) (topic)))
+ (6 (format s "rel~D(r: ~A, q: ~A) ~~ ~A~%" (random 2 random) (topic) (topic) (topic)))
+ (7 (format s "~A ^ https://example.invalid/n/doc.ctm#~A .~%" (topic) (topic)))))))))
+
+(defmacro with-oracle-search (&body body)
+ `(progn
+ (sb-int:encapsulate 'topic-maps.tmdm::next-topic-merge :oracle
+ (lambda (original map) (declare (ignore original)) (topic-maps.tmdm::scan-next-topic-merge map)))
+ (unwind-protect (progn ,@body) (sb-int:unencapsulate 'topic-maps.tmdm::next-topic-merge :oracle))))
+
+(defun counting-merges (thunk)
+ "The outcome of THUNK and how many Topic merges it performed."
+ (let ((merges 0))
+ (sb-int:encapsulate 'topic-maps.tmdm::merge-two-topics :count
+ (lambda (original &rest arguments) (incf merges) (apply original arguments)))
+ (unwind-protect (values (funcall thunk) (progn merges))
+ (sb-int:unencapsulate 'topic-maps.tmdm::merge-two-topics :count))))
+
+(defun reads-equal-tests (&key (documents 400) (seed 20261029))
+ (let ((random (sb-ext:seed-random-state seed)) (read 0) (refused 0) (differences 0) (merging 0) (merges 0) (reified 0))
+ (dotimes (n documents)
+ (let ((text (random-document random)))
+ (multiple-value-bind (indexed indexed-merges) (counting-merges (lambda () (document-outcome text)))
+ (multiple-value-bind (oracle oracle-merges)
+ (with-oracle-search (counting-merges (lambda () (document-outcome text))))
+ (cond ((or (not (equal indexed oracle)) (/= indexed-merges oracle-merges)) (incf differences))
+ (t (incf merges indexed-merges)
+ (when (plusp indexed-merges) (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:documents-read-exercised" (> read (floor documents 2)))
+ (check "reads:refusals-exercised" (> refused 0))
+ (check "reads:merging-documents-exercised" (> merging (floor documents 4)))
+ (check "reads:reified-documents-exercised" (> reified (floor documents 20)))
+ (list :documents documents :read read :refused refused :merging merging :merges merges :reified reified :differences differences)))
+
+(defun positive-control-for-preference ()
+ ;; The comparisons above can tell a search without the preference from the real one: always taking the first
+ ;; equal pair refuses the staged import that the preference reads.
+ (let ((first-pair-only (lambda (original map) (declare (ignore original))
+ (topic-maps.tmdm::equal-pair (topic-maps.tmdm::%topic-map-topics map) #'topic-maps.tmdm::equal-topics-p)))
+ (staged (lambda () (import-outcome #'scenario-reifier-first))))
+ (check "control:preferring-search-imports-the-staged-maps" (eq :read (first (outcome staged))))
+ (sb-int:encapsulate 'topic-maps.tmdm::next-topic-merge :control first-pair-only)
+ (unwind-protect (check "control:first-pair-search-refuses-them-with-a-reifier-conflict"
+ (equal '(:refused reification-error :reifier-conflict) (outcome staged)))
+ (sb-int:unencapsulate 'topic-maps.tmdm::next-topic-merge :control))))
+
+;;; Scale: documents of the size the reader was too slow for, read within a stated budget
+
+(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 (topics 300) (associations 120) (budget 60))
+ (multiple-value-bind (map seconds) (seconds-to (lambda () (read-case (chain-document topics (floor topics 4)))))
+ (check "scale:chain-read" (= (+ topics 5 2 1 (- (floor topics 4))) (length (topic-map-topics map))))
+ (check "scale:chain-associations" (= topics (length (topic-map-associations map))))
+ (check (format nil "scale:chain-within-~Ds" budget) (< seconds budget))
+ (let ((plain (read-case (reified-document associations))))
+ (multiple-value-bind (map reified-seconds) (seconds-to (lambda () (read-case (reified-document associations :duplicate-every 3))))
+ (check "scale:reified-associations" (and (= associations (length (topic-map-associations map)))
+ (= associations (length (topic-map-associations plain)))))
+ (check "scale:duplicate-reifier-topics-merged-into-the-first" (= (length (topic-map-topics plain)) (length (topic-map-topics map))))
+ (check "scale:every-association-keeps-its-reifier" (every #'item-reifier (topic-map-associations map)))
+ (check (format nil "scale:reified-within-~Ds" budget) (< reified-seconds budget))
+ (list :chain seconds :reified reified-seconds)))))
+
+(defun run-tests ()
+ (let ((topic-maps.ctm.tests::*checks* nil) (search nil) (walks nil) (reads nil) (seconds nil))
+ (recorded-outcome-tests)
+ (handle-tests nil)
+ (handle-tests t)
+ (representative-tests)
+ (reifier-preference-tests)
+ (stale-reference-tests)
+ (stale-listed-topic-tests)
+ (reifier-mutation-tests)
+ (setf search (selection-equivalence-tests) walks (invalidation-tests) reads (reads-equal-tests))
+ (positive-control-for-preference)
+ (setf seconds (scale-tests))
+ (format t "~&NORMALIZATION-INDEX-SELECTION: ~S~%NORMALIZATION-INDEX-WALKS: ~S~%NORMALIZATION-INDEX-READS: ~S~%NORMALIZATION-INDEX-SCALE: ~S~%"
+ search walks reads seconds)
+ (setf *last-checks* (reverse topic-maps.ctm.tests::*checks*))
+ (format t "~&NORMALIZATION-INDEX-PASS: ~D checks; ~D documents, ~D staged imports and ~D rejections equal to the outcomes recorded at b2eecffa.~%"
+ (length *last-checks*) (length *documents*) (length *scenarios*) (+ (length *rejections*) (length *rejecting-scenarios*)))
+ *last-checks*))