From: rgb Date: Wed, 28 Oct 2026 06:01:47 +0000 (+0100) Subject: perf(tmdm): index topic normalization merge candidates X-Git-Url: https://dreyeck.freedombox.rocks/gitweb/topic-maps.git/commitdiff_plain/6162ed68c94ea4796b8cf2282edd347d9607b08c perf(tmdm): index topic normalization merge candidates normalize-topic-map chose the next pair of Topics to merge by comparing all Topic pairs; each pair without a shared identifier called topic-reified, which enumerates every information item. Reading the 1,855-line HyperDoc project CTM did not finish in 120 s. next-topic-merge returns the same pair through an index built for one search and dropped with it: identifier keys (item and subject identifiers in one namespace, subject locators apart) and a table of reified items for the nonconflicting-reifier preference. A Topic that reifies two items, or a listed Topic that is not its own representative, falls back to scan-next-topic-merge, the unchanged pairwise search, so the conditions and the moment they are signalled stay as they were. Nothing outlives a call, so no invalidation rule exists. The project CTM now reads in about 29-31 s (median of three fresh runs in two independent reproductions); its semantic signature and CXTM are byte-identical to the 5a4a668 reference. The Association pair search is the remaining cost and is left unchanged. tests/normalization-index.lisp (120 checks): CXTM and rejection outcomes recorded from unchanged b2eecffa, staged-import reifier preference, retained handles, index-versus-pairwise comparison on random maps, merge walks and CTM documents, stale references, a positive control and scale. Co-Authored-By: Claude Sonnet 5.5 --- diff --git a/scripts/fresh-sbcl.lisp b/scripts/fresh-sbcl.lisp index d9cb142..3342b08 100644 --- a/scripts/fresh-sbcl.lisp +++ b/scripts/fresh-sbcl.lisp @@ -150,5 +150,8 @@ (when prefix (uiop:symbol-call :topic-maps.encoding.tests :write-reports prefix))) +;; Which Topics merge next: outcomes recorded at b2eecffa, invalidation and scale. +(asdf:test-system "topic-maps/tmdm/normalization-index-tests") + ;; Optional executable learning example, after all historical stage snapshots. (asdf:test-system "topic-maps/project-work-tests") diff --git a/src/tmdm/merging.lisp b/src/tmdm/merging.lisp index b34766d..454fec1 100644 --- a/src/tmdm/merging.lisp +++ b/src/tmdm/merging.lisp @@ -122,6 +122,72 @@ (normalize-associations map) (canonical-topic c))) +(defun scan-next-topic-merge (map) + "The pair of Topics to merge next, found by comparing Topics pairwise: the first nonconflicting equal pair, else +the first equal pair, else NIL. This is the search that defines the choice; NEXT-TOPIC-MERGE returns the same pair. +A staged import may contain equal owners/types AND equal Reifier Topics whose Names/Occurrences/etc. have not +merged yet. First perform available nonconflicting Topic merges; their ordinary item merging can resolve those +Reified references. Do not let collection order invent a conflict. If none can proceed, MERGE-TWO-TOPICS still +signals TMDM 6.2's conflict; no equality or conflict rule is relaxed." + (let ((pair (equal-pair (%topic-map-topics map) #'equal-topics-p))) + (when pair + (or (equal-pair (%topic-map-topics map) + (lambda (a b) + (and (equal-topics-p a b) + (let ((left (topic-reified a)) (right (topic-reified b))) + (not (and left right (not (eq left right)))))))) + pair)))) + +(defun next-topic-merge (map) + "The pair SCAN-NEXT-TOPIC-MERGE returns, found through an index built for this one search and dropped with it. +Two live Topics are equal exactly when they share an identifier: an item or subject identifier string (one +namespace, as IDENTIFIER-MATCHES-P compares them) or a subject locator string. EQUAL-TOPICS-P's third condition, +that both reify the same item, cannot hold for two distinct Topics: an item has one Reifier slot. A pair conflicts +when each Topic reifies an item and the items differ, which a table of the reified items answers without +TOPIC-REIFIED's scan. EQUAL-TOPICS-P and the conflict test have no side effect, so the first Topic with a later +sharer, and its first such sharer, are what the pairwise search finds; likewise for nonconflicting sharers. +The index is never kept: nothing it holds can outlive a merge or a change of Reifier. +When a Topic reifies two items TOPIC-REIFIED would signal from inside the search, and when a listed Topic is not +its own representative the table's assumptions fail; then the pairwise search itself runs, so the condition and +the moment it is signalled are unchanged." + (let ((topics (%topic-map-topics map)) (reified (make-hash-table :test #'eq))) + (dolist (item (map-information-items map)) + (when (and (reifiable-p item) (%item-reifier item)) + (push item (gethash (%item-reifier item) reified)))) + (when (or (loop for items being the hash-values of reified thereis (rest items)) + (some (lambda (topic) (not (eq topic (canonical-topic topic)))) topics)) + (return-from next-topic-merge (scan-next-topic-merge map))) + (let ((position (make-hash-table :test #'eq)) (sharers (make-hash-table :test #'equal)) + (keys (mapcar (lambda (topic) + (remove-duplicates + (append (mapcar (lambda (iri) (cons :item-or-subject iri)) + (append (%topic-item-identifiers topic) (%topic-subject-identifiers topic))) + (mapcar (lambda (iri) (cons :subject-locator iri)) (%topic-subject-locators topic))) + :test #'equal)) + topics)) + (pair nil)) + (loop for topic in topics for i from 0 do (setf (gethash topic position) i)) + ;; Each key lists its Topics in map order. + (loop for topic in (reverse topics) for topic-keys in (reverse keys) + do (dolist (key topic-keys) (push topic (gethash key sharers)))) + (flet ((earlier (a b) (if (and a b) (if (< (gethash a position) (gethash b position)) a b) (or a b))) + (conflict-p (a b) + (let ((left (first (gethash a reified))) (right (first (gethash b reified)))) + (and left right (not (eq left right)))))) + (loop for topic in topics for topic-keys in keys + do (let ((i (gethash topic position)) (first-later nil) (first-ready nil)) + (dolist (key topic-keys) + (let ((seen nil)) + (dolist (other (gethash key sharers)) + (when (> (gethash other position) i) + (unless seen (setf seen t first-later (earlier first-later other))) + (unless (conflict-p topic other) + (setf first-ready (earlier first-ready other)) + (return)))))) + (when first-ready (return-from next-topic-merge (list topic first-ready))) + (when (and first-later (null pair)) (setf pair (list topic first-later)))))) + pair))) + (defun normalize-topic-map (map) "Reach a fixed point of same-map Topic and structural item merging." (check-type map topic-map) @@ -131,21 +197,8 @@ (validate-map-core-subjects map) (check-variant-merge-constraints map) (loop for before = (length (map-information-items map)) do - (loop for pair = (equal-pair (%topic-map-topics map) #'equal-topics-p) - while pair do - ;; A staged import may contain equal owners/types AND equal Reifier - ;; Topics whose Names/Occurrences/etc. have not merged yet. First perform - ;; available nonconflicting Topic merges; their ordinary item merging can - ;; resolve those Reified references. Do not let collection order invent a - ;; conflict. If none can proceed, MERGE-TWO-TOPICS still signals TMDM 6.2's - ;; conflict; no equality or conflict rule is relaxed. - (let ((ready (equal-pair (%topic-map-topics map) - (lambda (a b) - (and (equal-topics-p a b) - (let ((left (topic-reified a)) (right (topic-reified b))) - (not (and left right (not (eq left right)))))))))) - (let ((next (or ready pair))) - (merge-two-topics map (first next) (second next))))) + (loop for pair = (next-topic-merge map) + while pair do (merge-two-topics map (first pair) (second pair))) (normalize-names map) (normalize-occurrences map) (normalize-associations map) when (= before (length (map-information-items map))) return map)) diff --git a/tests/fixtures/normalization-index/associations-equal-after-topic-merge.cxtm b/tests/fixtures/normalization-index/associations-equal-after-topic-merge.cxtm new file mode 100644 index 0000000..ee99872 --- /dev/null +++ b/tests/fixtures/normalization-index/associations-equal-after-topic-merge.cxtm @@ -0,0 +1,47 @@ + + + +#c + + + + + +#q + + + + +#r + + + + +#t + + + + +#a +#b + + + + + +#x +#y + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/chain-40-topics.cxtm b/tests/fixtures/normalization-index/chain-40-topics.cxtm new file mode 100644 index 0000000..8b1eed7 --- /dev/null +++ b/tests/fixtures/normalization-index/chain-40-topics.cxtm @@ -0,0 +1,982 @@ + + + +#from + + + + +#rel0 + + + + +#rel1 + + + + +#rel2 + + + + +#rel3 + + + + +#rel4 + + + + +#to + + + + +http://example.org/s/24 + + +#t24 + + +Topic 24 + + + + + + + +http://example.org/s/25 + + +#t25 + + +Topic 25 + + + + + + + +http://example.org/s/26 + + +#t26 + + +Topic 26 + + + + + + + +http://example.org/s/27 + + +#t27 + + +Topic 27 + + + + + + + +http://example.org/s/28 + + +#t28 + + +Topic 28 + + + + + + + +http://example.org/s/29 + + +#t29 + + +Topic 29 + + + + + + + +http://example.org/s/30 + + +#t30 + + +Topic 30 + + + + + + + +http://example.org/s/31 + + +#t31 + + +Topic 31 + + + + + + + +http://example.org/s/32 + + +#t32 + + +Topic 32 + + + + + + + +http://example.org/s/33 + + +#t33 + + +Topic 33 + + + + + + + +http://example.org/s/34 + + +#t34 + + +Topic 34 + + + + + + + +http://example.org/s/35 + + +#t35 + + +Topic 35 + + + + + + + +http://example.org/s/36 + + +#t36 + + +Topic 36 + + + + + + + +http://example.org/s/37 + + +#t37 + + +Topic 37 + + + + + + + +http://example.org/s/38 + + +#t38 + + +Topic 38 + + + + + + + +http://example.org/s/39 + + +#t39 + + +Topic 39 + + + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + +http://example.org/s/0 +http://example.org/s/1 + + +#t0 +#t1 +http://example.org/s/1 + + +Topic 0 + + + +Topic 1 + + + + + + + + + +http://example.org/s/10 +http://example.org/s/11 + + +#t10 +#t11 +http://example.org/s/11 + + +Topic 10 + + + +Topic 11 + + + + + + + + + +http://example.org/s/12 +http://example.org/s/13 + + +#t12 +#t13 +http://example.org/s/13 + + +Topic 12 + + + +Topic 13 + + + + + + + + + +http://example.org/s/14 +http://example.org/s/15 + + +#t14 +#t15 +http://example.org/s/15 + + +Topic 14 + + + +Topic 15 + + + + + + + + + +http://example.org/s/16 +http://example.org/s/17 + + +#t16 +#t17 +http://example.org/s/17 + + +Topic 16 + + + +Topic 17 + + + + + + + + + +http://example.org/s/18 +http://example.org/s/19 + + +#t18 +#t19 +http://example.org/s/19 + + +Topic 18 + + + +Topic 19 + + + + + + + + + +http://example.org/s/2 +http://example.org/s/3 + + +#t2 +#t3 +http://example.org/s/3 + + +Topic 2 + + + +Topic 3 + + + + + + + + + +http://example.org/s/20 +http://example.org/s/21 + + +#t20 +#t21 +http://example.org/s/21 + + +Topic 20 + + + +Topic 21 + + + + + + + + + +http://example.org/s/22 +http://example.org/s/23 + + +#t22 +#t23 +http://example.org/s/23 + + +Topic 22 + + + +Topic 23 + + + + + + + + + +http://example.org/s/4 +http://example.org/s/5 + + +#t4 +#t5 +http://example.org/s/5 + + +Topic 4 + + + +Topic 5 + + + + + + + + + +http://example.org/s/6 +http://example.org/s/7 + + +#t6 +#t7 +http://example.org/s/7 + + +Topic 6 + + + +Topic 7 + + + + + + + + + +http://example.org/s/8 +http://example.org/s/9 + + +#t8 +#t9 +http://example.org/s/9 + + +Topic 8 + + + +Topic 9 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/equal-owners-make-the-reified-associations-equal.cxtm b/tests/fixtures/normalization-index/equal-owners-make-the-reified-associations-equal.cxtm new file mode 100644 index 0000000..ff709f7 --- /dev/null +++ b/tests/fixtures/normalization-index/equal-owners-make-the-reified-associations-equal.cxtm @@ -0,0 +1,32 @@ + + + +#p + + + + + +#r + + + + +#a +#b + + + + +#x +#y + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/equal-reifiers-of-equal-items.cxtm b/tests/fixtures/normalization-index/equal-reifiers-of-equal-items.cxtm new file mode 100644 index 0000000..db53e62 --- /dev/null +++ b/tests/fixtures/normalization-index/equal-reifiers-of-equal-items.cxtm @@ -0,0 +1,31 @@ + + + +#p + + + + + +#r + + + + +#t + + + + +#x +#y + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/identifier-acquisition.cxtm b/tests/fixtures/normalization-index/identifier-acquisition.cxtm new file mode 100644 index 0000000..ebb7abf --- /dev/null +++ b/tests/fixtures/normalization-index/identifier-acquisition.cxtm @@ -0,0 +1,21 @@ + + + +#a +#b + + +A + + + +B + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + diff --git a/tests/fixtures/normalization-index/ii-si-cross-identity.cxtm b/tests/fixtures/normalization-index/ii-si-cross-identity.cxtm new file mode 100644 index 0000000..1cc2522 --- /dev/null +++ b/tests/fixtures/normalization-index/ii-si-cross-identity.cxtm @@ -0,0 +1,12 @@ + + + +http://example.org/s + + +#x +#y +http://example.org/s + + + diff --git a/tests/fixtures/normalization-index/import-cascade.cxtm b/tests/fixtures/normalization-index/import-cascade.cxtm new file mode 100644 index 0000000..07c1c49 --- /dev/null +++ b/tests/fixtures/normalization-index/import-cascade.cxtm @@ -0,0 +1,41 @@ + + + +urn:name-type + + + + +urn:owner + + +N + + + + + +urn:r +urn:s + + +O +http://www.w3.org/2001/XMLSchema#string + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/import-reifier-chain.cxtm b/tests/fixtures/normalization-index/import-reifier-chain.cxtm new file mode 100644 index 0000000..d4dd32b --- /dev/null +++ b/tests/fixtures/normalization-index/import-reifier-chain.cxtm @@ -0,0 +1,32 @@ + + + +urn:owner + + +N + + + + + +urn:type + + + + +urn:r +urn:s + + +K + + + + + +urn:r2 +urn:s2 + + + diff --git a/tests/fixtures/normalization-index/import-reifier-first.cxtm b/tests/fixtures/normalization-index/import-reifier-first.cxtm new file mode 100644 index 0000000..0b6d411 --- /dev/null +++ b/tests/fixtures/normalization-index/import-reifier-first.cxtm @@ -0,0 +1,21 @@ + + + +urn:owner + + +N + + + + + +urn:r + + + + +urn:type + + + diff --git a/tests/fixtures/normalization-index/isa-ako.cxtm b/tests/fixtures/normalization-index/isa-ako.cxtm new file mode 100644 index 0000000..73dce2f --- /dev/null +++ b/tests/fixtures/normalization-index/isa-ako.cxtm @@ -0,0 +1,109 @@ + + + +#a + + + + + +#b + + + + + + + +#c + + + + + + +#d + + + + + +#e + + + + + +http://psi.topicmaps.org/iso13250/model/instance + + + + +http://psi.topicmaps.org/iso13250/model/subtype + + + + +http://psi.topicmaps.org/iso13250/model/supertype + + + + +http://psi.topicmaps.org/iso13250/model/supertype-subtype + + + + +http://psi.topicmaps.org/iso13250/model/type + + + + +http://psi.topicmaps.org/iso13250/model/type-instance + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/isa-duplicates-merge.cxtm b/tests/fixtures/normalization-index/isa-duplicates-merge.cxtm new file mode 100644 index 0000000..fcdaf9a --- /dev/null +++ b/tests/fixtures/normalization-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/normalization-index/n-ary-duplicate-roles.cxtm b/tests/fixtures/normalization-index/n-ary-duplicate-roles.cxtm new file mode 100644 index 0000000..2fd7c19 --- /dev/null +++ b/tests/fixtures/normalization-index/n-ary-duplicate-roles.cxtm @@ -0,0 +1,55 @@ + + + +#a + + + + + +#b + + + + + +#c + + + + + +#r1 + + + + +#r2 + + + + +#r3 + + + + +#t + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/reified-30-associations-merging-reifiers.cxtm b/tests/fixtures/normalization-index/reified-30-associations-merging-reifiers.cxtm new file mode 100644 index 0000000..59da5ef --- /dev/null +++ b/tests/fixtures/normalization-index/reified-30-associations-merging-reifiers.cxtm @@ -0,0 +1,1207 @@ + + + +#from + + + + +#rel0 + + + + +#rel1 + + + + +#rel2 + + + + +#rel3 + + + + +#to + + + + +http://example.org/p/0 + + +#p0 + + +P 0 + + + + + + + + + + + +http://example.org/p/1 + + +#p1 + + +P 1 + + + + + + +http://example.org/p/10 + + +#p10 + + +P 10 + + + + + + + + + + + +http://example.org/p/11 + + +#p11 + + +P 11 + + + + + + +http://example.org/p/12 + + +#p12 + + +P 12 + + + + + + +http://example.org/p/13 + + +#p13 + + +P 13 + + + + + + +http://example.org/p/14 + + +#p14 + + +P 14 + + + + + + +http://example.org/p/15 + + +#p15 + + +P 15 + + + + + + + + + + + +http://example.org/p/16 + + +#p16 + + +P 16 + + + + + + +http://example.org/p/17 + + +#p17 + + +P 17 + + + + + + +http://example.org/p/18 + + +#p18 + + +P 18 + + + + + + +http://example.org/p/19 + + +#p19 + + +P 19 + + + + + + +http://example.org/p/2 + + +#p2 + + +P 2 + + + + + + +http://example.org/p/20 + + +#p20 + + +P 20 + + + + + + + + + + + +http://example.org/p/21 + + +#p21 + + +P 21 + + + + + + +http://example.org/p/22 + + +#p22 + + +P 22 + + + + + + +http://example.org/p/23 + + +#p23 + + +P 23 + + + + + + +http://example.org/p/24 + + +#p24 + + +P 24 + + + + + + +http://example.org/p/25 + + +#p25 + + +P 25 + + + + + + + + + + + +http://example.org/p/26 + + +#p26 + + +P 26 + + + + + + +http://example.org/p/27 + + +#p27 + + +P 27 + + + + + + +http://example.org/p/28 + + +#p28 + + +P 28 + + + + + + +http://example.org/p/29 + + +#p29 + + +P 29 + + + + + + +http://example.org/p/3 + + +#p3 + + +P 3 + + + + + + +http://example.org/p/4 + + +#p4 + + +P 4 + + + + + + +http://example.org/p/5 + + +#p5 + + +P 5 + + + + + + + + + + + +http://example.org/p/6 + + +#p6 + + +P 6 + + + + + + +http://example.org/p/7 + + +#p7 + + +P 7 + + + + + + +http://example.org/p/8 + + +#p8 + + +P 8 + + + + + + +http://example.org/p/9 + + +#p9 + + +P 9 + + + + + + +http://example.org/r/1 + + +#r1 + + +R 1 + + + + + +http://example.org/r/10 + + +#r10 + + +R 10 + + + + + +http://example.org/r/11 + + +#r11 + + +R 11 + + + + + +http://example.org/r/13 + + +#r13 + + +R 13 + + + + + +http://example.org/r/14 + + +#r14 + + +R 14 + + + + + +http://example.org/r/16 + + +#r16 + + +R 16 + + + + + +http://example.org/r/17 + + +#r17 + + +R 17 + + + + + +http://example.org/r/19 + + +#r19 + + +R 19 + + + + + +http://example.org/r/2 + + +#r2 + + +R 2 + + + + + +http://example.org/r/20 + + +#r20 + + +R 20 + + + + + +http://example.org/r/22 + + +#r22 + + +R 22 + + + + + +http://example.org/r/23 + + +#r23 + + +R 23 + + + + + +http://example.org/r/25 + + +#r25 + + +R 25 + + + + + +http://example.org/r/26 + + +#r26 + + +R 26 + + + + + +http://example.org/r/28 + + +#r28 + + +R 28 + + + + + +http://example.org/r/29 + + +#r29 + + +R 29 + + + + + +http://example.org/r/4 + + +#r4 + + +R 4 + + + + + +http://example.org/r/5 + + +#r5 + + +R 5 + + + + + +http://example.org/r/7 + + +#r7 + + +R 7 + + + + + +http://example.org/r/8 + + +#r8 + + +R 8 + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + +http://example.org/q/0 +http://example.org/r/0 + + +#q0 +#r0 + + +Q 0 + + + +R 0 + + + + + +http://example.org/q/12 +http://example.org/r/12 + + +#q12 +#r12 + + +Q 12 + + + +R 12 + + + + + +http://example.org/q/15 +http://example.org/r/15 + + +#q15 +#r15 + + +Q 15 + + + +R 15 + + + + + +http://example.org/q/18 +http://example.org/r/18 + + +#q18 +#r18 + + +Q 18 + + + +R 18 + + + + + +http://example.org/q/21 +http://example.org/r/21 + + +#q21 +#r21 + + +Q 21 + + + +R 21 + + + + + +http://example.org/q/24 +http://example.org/r/24 + + +#q24 +#r24 + + +Q 24 + + + +R 24 + + + + + +http://example.org/q/27 +http://example.org/r/27 + + +#q27 +#r27 + + +Q 27 + + + +R 27 + + + + + +http://example.org/q/3 +http://example.org/r/3 + + +#q3 +#r3 + + +Q 3 + + + +R 3 + + + + + +http://example.org/q/6 +http://example.org/r/6 + + +#q6 +#r6 + + +Q 6 + + + +R 6 + + + + + +http://example.org/q/9 +http://example.org/r/9 + + +#q9 +#r9 + + +Q 9 + + + +R 9 + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/reified-30-associations.cxtm b/tests/fixtures/normalization-index/reified-30-associations.cxtm new file mode 100644 index 0000000..87f4ca1 --- /dev/null +++ b/tests/fixtures/normalization-index/reified-30-associations.cxtm @@ -0,0 +1,1147 @@ + + + +#from + + + + +#rel0 + + + + +#rel1 + + + + +#rel2 + + + + +#rel3 + + + + +#to + + + + +http://example.org/p/0 + + +#p0 + + +P 0 + + + + + + + + + + + +http://example.org/p/1 + + +#p1 + + +P 1 + + + + + + +http://example.org/p/10 + + +#p10 + + +P 10 + + + + + + + + + + + +http://example.org/p/11 + + +#p11 + + +P 11 + + + + + + +http://example.org/p/12 + + +#p12 + + +P 12 + + + + + + +http://example.org/p/13 + + +#p13 + + +P 13 + + + + + + +http://example.org/p/14 + + +#p14 + + +P 14 + + + + + + +http://example.org/p/15 + + +#p15 + + +P 15 + + + + + + + + + + + +http://example.org/p/16 + + +#p16 + + +P 16 + + + + + + +http://example.org/p/17 + + +#p17 + + +P 17 + + + + + + +http://example.org/p/18 + + +#p18 + + +P 18 + + + + + + +http://example.org/p/19 + + +#p19 + + +P 19 + + + + + + +http://example.org/p/2 + + +#p2 + + +P 2 + + + + + + +http://example.org/p/20 + + +#p20 + + +P 20 + + + + + + + + + + + +http://example.org/p/21 + + +#p21 + + +P 21 + + + + + + +http://example.org/p/22 + + +#p22 + + +P 22 + + + + + + +http://example.org/p/23 + + +#p23 + + +P 23 + + + + + + +http://example.org/p/24 + + +#p24 + + +P 24 + + + + + + +http://example.org/p/25 + + +#p25 + + +P 25 + + + + + + + + + + + +http://example.org/p/26 + + +#p26 + + +P 26 + + + + + + +http://example.org/p/27 + + +#p27 + + +P 27 + + + + + + +http://example.org/p/28 + + +#p28 + + +P 28 + + + + + + +http://example.org/p/29 + + +#p29 + + +P 29 + + + + + + +http://example.org/p/3 + + +#p3 + + +P 3 + + + + + + +http://example.org/p/4 + + +#p4 + + +P 4 + + + + + + +http://example.org/p/5 + + +#p5 + + +P 5 + + + + + + + + + + + +http://example.org/p/6 + + +#p6 + + +P 6 + + + + + + +http://example.org/p/7 + + +#p7 + + +P 7 + + + + + + +http://example.org/p/8 + + +#p8 + + +P 8 + + + + + + +http://example.org/p/9 + + +#p9 + + +P 9 + + + + + + +http://example.org/r/0 + + +#r0 + + +R 0 + + + + + +http://example.org/r/1 + + +#r1 + + +R 1 + + + + + +http://example.org/r/10 + + +#r10 + + +R 10 + + + + + +http://example.org/r/11 + + +#r11 + + +R 11 + + + + + +http://example.org/r/12 + + +#r12 + + +R 12 + + + + + +http://example.org/r/13 + + +#r13 + + +R 13 + + + + + +http://example.org/r/14 + + +#r14 + + +R 14 + + + + + +http://example.org/r/15 + + +#r15 + + +R 15 + + + + + +http://example.org/r/16 + + +#r16 + + +R 16 + + + + + +http://example.org/r/17 + + +#r17 + + +R 17 + + + + + +http://example.org/r/18 + + +#r18 + + +R 18 + + + + + +http://example.org/r/19 + + +#r19 + + +R 19 + + + + + +http://example.org/r/2 + + +#r2 + + +R 2 + + + + + +http://example.org/r/20 + + +#r20 + + +R 20 + + + + + +http://example.org/r/21 + + +#r21 + + +R 21 + + + + + +http://example.org/r/22 + + +#r22 + + +R 22 + + + + + +http://example.org/r/23 + + +#r23 + + +R 23 + + + + + +http://example.org/r/24 + + +#r24 + + +R 24 + + + + + +http://example.org/r/25 + + +#r25 + + +R 25 + + + + + +http://example.org/r/26 + + +#r26 + + +R 26 + + + + + +http://example.org/r/27 + + +#r27 + + +R 27 + + + + + +http://example.org/r/28 + + +#r28 + + +R 28 + + + + + +http://example.org/r/29 + + +#r29 + + +R 29 + + + + + +http://example.org/r/3 + + +#r3 + + +R 3 + + + + + +http://example.org/r/4 + + +#r4 + + +R 4 + + + + + +http://example.org/r/5 + + +#r5 + + +R 5 + + + + + +http://example.org/r/6 + + +#r6 + + +R 6 + + + + + +http://example.org/r/7 + + +#r7 + + +R 7 + + + + + +http://example.org/r/8 + + +#r8 + + +R 8 + + + + + +http://example.org/r/9 + + +#r9 + + +R 9 + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/reified-duplicate-associations.cxtm b/tests/fixtures/normalization-index/reified-duplicate-associations.cxtm new file mode 100644 index 0000000..62483b5 --- /dev/null +++ b/tests/fixtures/normalization-index/reified-duplicate-associations.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/normalization-index/reified-duplicate-names.cxtm b/tests/fixtures/normalization-index/reified-duplicate-names.cxtm new file mode 100644 index 0000000..7f2e455 --- /dev/null +++ b/tests/fixtures/normalization-index/reified-duplicate-names.cxtm @@ -0,0 +1,22 @@ + + + +#n + + +N + + + + + +#nr +#nr2 + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + diff --git a/tests/fixtures/normalization-index/reifier-acquires-another-topics-identifier.cxtm b/tests/fixtures/normalization-index/reifier-acquires-another-topics-identifier.cxtm new file mode 100644 index 0000000..807d1cb --- /dev/null +++ b/tests/fixtures/normalization-index/reifier-acquires-another-topics-identifier.cxtm @@ -0,0 +1,63 @@ + + + +#p + + + + + +#q + + + + + +#r + + + + +#t + + + + +#u + + + + +#v + + + + +#w +#x + + +W + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/reifier-merges-by-identifier.cxtm b/tests/fixtures/normalization-index/reifier-merges-by-identifier.cxtm new file mode 100644 index 0000000..c29f443 --- /dev/null +++ b/tests/fixtures/normalization-index/reifier-merges-by-identifier.cxtm @@ -0,0 +1,63 @@ + + + +#p + + + + + +#q + + + + + +#r + + + + +#t + + + + +#u + + + + +#x + + + + +#y +#z + + +Z + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + + + + + + + + + + + + + + diff --git a/tests/fixtures/normalization-index/rejections.sexp b/tests/fixtures/normalization-index/rejections.sexp new file mode 100644 index 0000000..a8e8b05 --- /dev/null +++ b/tests/fixtures/normalization-index/rejections.sexp @@ -0,0 +1,9 @@ +("reifier-reifies-two-items" TOPIC-MAPS.CTM:CTM-REJECTION :REIFIER-CONFLICT) +("reifier-merge-conflict" TOPIC-MAPS.CTM:CTM-REJECTION :REIFIER-CONFLICT) +("core-subject-conflict" TOPIC-MAPS.CTM:CTM-REJECTION :CORE-SUBJECT-CONFLICT) +("core-subject-merge-conflict" TOPIC-MAPS.CTM:CTM-REJECTION + :CORE-SUBJECT-CONFLICT) +("unclosed-association" TOPIC-MAPS.CTM:CTM-REJECTION :MISSING-ASSOCIATION-CLOSE) +("import-reifier-conflict" TOPIC-MAPS.TMDM:REIFICATION-ERROR :REIFIER-CONFLICT) +("import-retained-root-reifier" TOPIC-MAPS.TMDM:REIFICATION-ERROR + :REIFIER-CONFLICT) diff --git a/tests/fixtures/normalization-index/si-and-sl-stay-apart.cxtm b/tests/fixtures/normalization-index/si-and-sl-stay-apart.cxtm new file mode 100644 index 0000000..f901a65 --- /dev/null +++ b/tests/fixtures/normalization-index/si-and-sl-stay-apart.cxtm @@ -0,0 +1,18 @@ + + + +http://example.org/z + + +#t2 + + + + +http://example.org/z + + +#t1 + + + diff --git a/tests/fixtures/normalization-index/subject-locator-merge.cxtm b/tests/fixtures/normalization-index/subject-locator-merge.cxtm new file mode 100644 index 0000000..5f639f5 --- /dev/null +++ b/tests/fixtures/normalization-index/subject-locator-merge.cxtm @@ -0,0 +1,11 @@ + + + +http://example.org/doc + + +#s1 +#s2 + + + diff --git a/tests/fixtures/normalization-index/topic-map-reifier.cxtm b/tests/fixtures/normalization-index/topic-map-reifier.cxtm new file mode 100644 index 0000000..6ef75bb --- /dev/null +++ b/tests/fixtures/normalization-index/topic-map-reifier.cxtm @@ -0,0 +1,16 @@ + + + +#mapr + + +M + + + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + diff --git a/tests/fixtures/normalization-index/transitive-late-chain.cxtm b/tests/fixtures/normalization-index/transitive-late-chain.cxtm new file mode 100644 index 0000000..7adbcc8 --- /dev/null +++ b/tests/fixtures/normalization-index/transitive-late-chain.cxtm @@ -0,0 +1,15 @@ + + + +http://example.org/p +http://example.org/q +http://example.org/r + + +#p +#q +#r +http://example.org/r + + + diff --git a/tests/fixtures/normalization-index/transitive-through-third.cxtm b/tests/fixtures/normalization-index/transitive-through-third.cxtm new file mode 100644 index 0000000..89c23cf --- /dev/null +++ b/tests/fixtures/normalization-index/transitive-through-third.cxtm @@ -0,0 +1,23 @@ + + + +http://psi.topicmaps.org/iso13250/model/topic-name + + + + +http://example.org/1 +http://example.org/2 + + +#a +#b +#c +http://example.org/1 + + +C + + + + diff --git a/tests/fixtures/normalization-index/wildcard-merge.cxtm b/tests/fixtures/normalization-index/wildcard-merge.cxtm new file mode 100644 index 0000000..76268b1 --- /dev/null +++ b/tests/fixtures/normalization-index/wildcard-merge.cxtm @@ -0,0 +1,7 @@ + + + +#$__1.foo + + + diff --git a/tests/normalization-index.lisp b/tests/normalization-index.lisp new file mode 100644 index 0000000..c6b7ff5 --- /dev/null +++ b/tests/normalization-index.lisp @@ -0,0 +1,516 @@ +(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*)) diff --git a/topic-maps.asd b/topic-maps.asd index eb6c4e0..9d29fca 100644 --- a/topic-maps.asd +++ b/topic-maps.asd @@ -331,3 +331,11 @@ :perform (asdf:test-op (operation component) (declare (ignore operation component)) (uiop:symbol-call :topic-maps.project-work.tests :run-tests))) + +(asdf:defsystem "topic-maps/tmdm/normalization-index-tests" + :description "Which Topics merge next: outcomes recorded at b2eecffa, canonical representatives, retained handles, invalidation and reader scale" + :depends-on ("topic-maps/tmdm/import-tests") :serial t + :components ((:file "tests/normalization-index")) + :perform (asdf:test-op (operation component) + (declare (ignore operation component)) + (uiop:symbol-call :topic-maps.normalization-index.tests :run-tests)))