]> dreyeck.freedombox.rocks Git - topic-maps.git/commitdiff
perf(tmdm): index topic normalization merge candidates
authorrgb <ralf.barkow@me.com>
Wed, 28 Oct 2026 06:01:47 +0000 (07:01 +0100)
committerrgb <ralf.barkow@me.com>
Wed, 28 Oct 2026 06:01:47 +0000 (07:01 +0100)
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 <noreply@anthropic.com>
29 files changed:
scripts/fresh-sbcl.lisp
src/tmdm/merging.lisp
tests/fixtures/normalization-index/associations-equal-after-topic-merge.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/chain-40-topics.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/equal-owners-make-the-reified-associations-equal.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/equal-reifiers-of-equal-items.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/identifier-acquisition.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/ii-si-cross-identity.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/import-cascade.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/import-reifier-chain.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/import-reifier-first.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/isa-ako.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/isa-duplicates-merge.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/n-ary-duplicate-roles.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/reified-30-associations-merging-reifiers.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/reified-30-associations.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/reified-duplicate-associations.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/reified-duplicate-names.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/reifier-acquires-another-topics-identifier.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/reifier-merges-by-identifier.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/rejections.sexp [new file with mode: 0644]
tests/fixtures/normalization-index/si-and-sl-stay-apart.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/subject-locator-merge.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/topic-map-reifier.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/transitive-late-chain.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/transitive-through-third.cxtm [new file with mode: 0644]
tests/fixtures/normalization-index/wildcard-merge.cxtm [new file with mode: 0644]
tests/normalization-index.lisp [new file with mode: 0644]
topic-maps.asd

index d9cb14230901dd6d9c9abd8533f97059ad05ebc7..3342b082c1935d21a32262285f21523d5fab8dfa 100644 (file)
   (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")
index b34766d0fdaaca222277e7b5c1195370648bf149..454fec130a66e6aa078df4d7d3dccb84b54814cb 100644 (file)
     (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)
   (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 (file)
index 0000000..ee99872
--- /dev/null
@@ -0,0 +1,47 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#c</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#q</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#r</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#t</locator>
+</itemIdentifiers>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#a</locator>
+<locator>#b</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.2"></rolePlayed>
+</topic>
+<topic number="6">
+<itemIdentifiers>
+<locator>#x</locator>
+<locator>#y</locator>
+</itemIdentifiers>
+</topic>
+<association number="1" reifier="6">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="2"></type>
+</role>
+<role number="2">
+<player topicref="5"></player>
+<type topicref="3"></type>
+</role>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/chain-40-topics.cxtm b/tests/fixtures/normalization-index/chain-40-topics.cxtm
new file mode 100644 (file)
index 0000000..8b1eed7
--- /dev/null
@@ -0,0 +1,982 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#from</locator>
+</itemIdentifiers>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#rel0</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#rel1</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#rel2</locator>
+</itemIdentifiers>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#rel3</locator>
+</itemIdentifiers>
+</topic>
+<topic number="6">
+<itemIdentifiers>
+<locator>#rel4</locator>
+</itemIdentifiers>
+</topic>
+<topic number="7">
+<itemIdentifiers>
+<locator>#to</locator>
+</itemIdentifiers>
+</topic>
+<topic number="8">
+<subjectIdentifiers>
+<locator>http://example.org/s/24</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t24</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 24</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.33.role.1"></rolePlayed>
+<rolePlayed ref="association.9.role.1"></rolePlayed>
+</topic>
+<topic number="9">
+<subjectIdentifiers>
+<locator>http://example.org/s/25</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t25</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 25</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+<rolePlayed ref="association.34.role.1"></rolePlayed>
+</topic>
+<topic number="10">
+<subjectIdentifiers>
+<locator>http://example.org/s/26</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t26</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 26</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.10.role.1"></rolePlayed>
+<rolePlayed ref="association.17.role.1"></rolePlayed>
+</topic>
+<topic number="11">
+<subjectIdentifiers>
+<locator>http://example.org/s/27</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t27</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 27</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.18.role.1"></rolePlayed>
+<rolePlayed ref="association.2.role.1"></rolePlayed>
+</topic>
+<topic number="12">
+<subjectIdentifiers>
+<locator>http://example.org/s/28</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t28</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 28</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.25.role.1"></rolePlayed>
+<rolePlayed ref="association.26.role.1"></rolePlayed>
+</topic>
+<topic number="13">
+<subjectIdentifiers>
+<locator>http://example.org/s/29</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t29</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 29</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.35.role.1"></rolePlayed>
+<rolePlayed ref="association.10.role.2"></rolePlayed>
+</topic>
+<topic number="14">
+<subjectIdentifiers>
+<locator>http://example.org/s/30</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t30</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 30</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.3.role.1"></rolePlayed>
+<rolePlayed ref="association.36.role.1"></rolePlayed>
+</topic>
+<topic number="15">
+<subjectIdentifiers>
+<locator>http://example.org/s/31</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t31</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 31</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.9.role.2"></rolePlayed>
+<rolePlayed ref="association.19.role.1"></rolePlayed>
+</topic>
+<topic number="16">
+<subjectIdentifiers>
+<locator>http://example.org/s/32</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t32</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 32</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.19.role.2"></rolePlayed>
+<rolePlayed ref="association.4.role.1"></rolePlayed>
+</topic>
+<topic number="17">
+<subjectIdentifiers>
+<locator>http://example.org/s/33</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t33</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 33</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.27.role.1"></rolePlayed>
+<rolePlayed ref="association.28.role.1"></rolePlayed>
+</topic>
+<topic number="18">
+<subjectIdentifiers>
+<locator>http://example.org/s/34</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t34</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 34</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.37.role.1"></rolePlayed>
+<rolePlayed ref="association.11.role.1"></rolePlayed>
+</topic>
+<topic number="19">
+<subjectIdentifiers>
+<locator>http://example.org/s/35</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t35</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 35</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.5.role.1"></rolePlayed>
+<rolePlayed ref="association.38.role.1"></rolePlayed>
+</topic>
+<topic number="20">
+<subjectIdentifiers>
+<locator>http://example.org/s/36</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t36</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 36</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.12.role.1"></rolePlayed>
+<rolePlayed ref="association.18.role.2"></rolePlayed>
+</topic>
+<topic number="21">
+<subjectIdentifiers>
+<locator>http://example.org/s/37</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t37</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 37</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.17.role.2"></rolePlayed>
+<rolePlayed ref="association.6.role.1"></rolePlayed>
+</topic>
+<topic number="22">
+<subjectIdentifiers>
+<locator>http://example.org/s/38</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t38</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 38</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.28.role.2"></rolePlayed>
+<rolePlayed ref="association.27.role.2"></rolePlayed>
+</topic>
+<topic number="23">
+<subjectIdentifiers>
+<locator>http://example.org/s/39</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t39</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 39</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.39.role.1"></rolePlayed>
+<rolePlayed ref="association.13.role.1"></rolePlayed>
+</topic>
+<topic number="24">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="25">
+<subjectIdentifiers>
+<locator>http://example.org/s/0</locator>
+<locator>http://example.org/s/1</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t0</locator>
+<locator>#t1</locator>
+<locator>http://example.org/s/1</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 0</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 1</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.7.role.1"></rolePlayed>
+<rolePlayed ref="association.14.role.1"></rolePlayed>
+<rolePlayed ref="association.20.role.1"></rolePlayed>
+<rolePlayed ref="association.39.role.2"></rolePlayed>
+</topic>
+<topic number="26">
+<subjectIdentifiers>
+<locator>http://example.org/s/10</locator>
+<locator>http://example.org/s/11</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t10</locator>
+<locator>#t11</locator>
+<locator>http://example.org/s/11</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 10</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 11</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.6.role.2"></rolePlayed>
+<rolePlayed ref="association.15.role.1"></rolePlayed>
+<rolePlayed ref="association.21.role.1"></rolePlayed>
+<rolePlayed ref="association.35.role.2"></rolePlayed>
+</topic>
+<topic number="27">
+<subjectIdentifiers>
+<locator>http://example.org/s/12</locator>
+<locator>http://example.org/s/13</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t12</locator>
+<locator>#t13</locator>
+<locator>http://example.org/s/13</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 12</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 13</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.21.role.2"></rolePlayed>
+<rolePlayed ref="association.29.role.1"></rolePlayed>
+<rolePlayed ref="association.5.role.2"></rolePlayed>
+<rolePlayed ref="association.30.role.1"></rolePlayed>
+</topic>
+<topic number="28">
+<subjectIdentifiers>
+<locator>http://example.org/s/14</locator>
+<locator>http://example.org/s/15</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t14</locator>
+<locator>#t15</locator>
+<locator>http://example.org/s/15</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 14</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 15</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.4.role.2"></rolePlayed>
+<rolePlayed ref="association.34.role.2"></rolePlayed>
+<rolePlayed ref="association.14.role.2"></rolePlayed>
+<rolePlayed ref="association.33.role.2"></rolePlayed>
+</topic>
+<topic number="29">
+<subjectIdentifiers>
+<locator>http://example.org/s/16</locator>
+<locator>http://example.org/s/17</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t16</locator>
+<locator>#t17</locator>
+<locator>http://example.org/s/17</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 16</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 17</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.13.role.2"></rolePlayed>
+<rolePlayed ref="association.22.role.1"></rolePlayed>
+<rolePlayed ref="association.3.role.2"></rolePlayed>
+<rolePlayed ref="association.23.role.1"></rolePlayed>
+</topic>
+<topic number="30">
+<subjectIdentifiers>
+<locator>http://example.org/s/18</locator>
+<locator>http://example.org/s/19</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t18</locator>
+<locator>#t19</locator>
+<locator>http://example.org/s/19</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 18</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 19</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.30.role.2"></rolePlayed>
+<rolePlayed ref="association.40.role.1"></rolePlayed>
+<rolePlayed ref="association.12.role.2"></rolePlayed>
+<rolePlayed ref="association.29.role.2"></rolePlayed>
+</topic>
+<topic number="31">
+<subjectIdentifiers>
+<locator>http://example.org/s/2</locator>
+<locator>http://example.org/s/3</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t2</locator>
+<locator>#t3</locator>
+<locator>http://example.org/s/3</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 2</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 3</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.24.role.1"></rolePlayed>
+<rolePlayed ref="association.26.role.2"></rolePlayed>
+<rolePlayed ref="association.8.role.1"></rolePlayed>
+<rolePlayed ref="association.25.role.2"></rolePlayed>
+</topic>
+<topic number="32">
+<subjectIdentifiers>
+<locator>http://example.org/s/20</locator>
+<locator>http://example.org/s/21</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t20</locator>
+<locator>#t21</locator>
+<locator>http://example.org/s/21</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 20</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 21</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.2.role.2"></rolePlayed>
+<rolePlayed ref="association.11.role.2"></rolePlayed>
+<rolePlayed ref="association.24.role.2"></rolePlayed>
+<rolePlayed ref="association.40.role.2"></rolePlayed>
+</topic>
+<topic number="33">
+<subjectIdentifiers>
+<locator>http://example.org/s/22</locator>
+<locator>http://example.org/s/23</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t22</locator>
+<locator>#t23</locator>
+<locator>http://example.org/s/23</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 22</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 23</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.20.role.2"></rolePlayed>
+<rolePlayed ref="association.31.role.1"></rolePlayed>
+<rolePlayed ref="association.1.role.2"></rolePlayed>
+<rolePlayed ref="association.32.role.1"></rolePlayed>
+</topic>
+<topic number="34">
+<subjectIdentifiers>
+<locator>http://example.org/s/4</locator>
+<locator>http://example.org/s/5</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t4</locator>
+<locator>#t5</locator>
+<locator>http://example.org/s/5</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 4</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 5</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.8.role.2"></rolePlayed>
+<rolePlayed ref="association.38.role.2"></rolePlayed>
+<rolePlayed ref="association.15.role.2"></rolePlayed>
+<rolePlayed ref="association.37.role.2"></rolePlayed>
+</topic>
+<topic number="35">
+<subjectIdentifiers>
+<locator>http://example.org/s/6</locator>
+<locator>http://example.org/s/7</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t6</locator>
+<locator>#t7</locator>
+<locator>http://example.org/s/7</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 6</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 7</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.16.role.1"></rolePlayed>
+<rolePlayed ref="association.23.role.2"></rolePlayed>
+<rolePlayed ref="association.7.role.2"></rolePlayed>
+<rolePlayed ref="association.22.role.2"></rolePlayed>
+</topic>
+<topic number="36">
+<subjectIdentifiers>
+<locator>http://example.org/s/8</locator>
+<locator>http://example.org/s/9</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t8</locator>
+<locator>#t9</locator>
+<locator>http://example.org/s/9</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Topic 8</value>
+<type topicref="24"></type>
+</name>
+<name number="2">
+<value>Topic 9</value>
+<type topicref="24"></type>
+</name>
+<rolePlayed ref="association.32.role.2"></rolePlayed>
+<rolePlayed ref="association.36.role.2"></rolePlayed>
+<rolePlayed ref="association.16.role.2"></rolePlayed>
+<rolePlayed ref="association.31.role.2"></rolePlayed>
+</topic>
+<association number="1">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="33"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="2">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="11"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="3">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="29"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="4">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="16"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="28"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="5">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="19"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="27"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="6">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="21"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="26"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="7">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="25"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="35"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="8">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="31"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="34"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="9">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="8"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="15"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="10">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="10"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="13"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="11">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="18"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="12">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="30"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="13">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="23"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="29"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="14">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="25"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="28"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="15">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="26"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="34"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="16">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="35"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="36"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="17">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="10"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="21"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="18">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="11"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="20"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="19">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="15"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="16"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="20">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="25"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="33"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="21">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="26"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="27"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="22">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="29"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="35"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="23">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="29"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="35"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="24">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="31"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="25">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="12"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="31"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="26">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="12"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="31"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="27">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="17"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="22"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="28">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="17"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="22"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="29">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="27"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="30"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="30">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="27"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="30"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="31">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="33"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="36"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="32">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="33"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="36"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="33">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="8"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="28"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="34">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="28"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="35">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="13"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="26"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="36">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="36"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="37">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="18"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="34"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="38">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="19"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="34"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="39">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="23"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="7"></type>
+</role>
+</association>
+<association number="40">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="30"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="7"></type>
+</role>
+</association>
+</topicMap>
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 (file)
index 0000000..ff709f7
--- /dev/null
@@ -0,0 +1,32 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#p</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#r</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#a</locator>
+<locator>#b</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#x</locator>
+<locator>#y</locator>
+</itemIdentifiers>
+</topic>
+<association number="1" reifier="4">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="2"></type>
+</role>
+</association>
+</topicMap>
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 (file)
index 0000000..db53e62
--- /dev/null
@@ -0,0 +1,31 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#p</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#r</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#t</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#x</locator>
+<locator>#y</locator>
+</itemIdentifiers>
+</topic>
+<association number="1" reifier="4">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="2"></type>
+</role>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/identifier-acquisition.cxtm b/tests/fixtures/normalization-index/identifier-acquisition.cxtm
new file mode 100644 (file)
index 0000000..ebb7abf
--- /dev/null
@@ -0,0 +1,21 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#a</locator>
+<locator>#b</locator>
+</itemIdentifiers>
+<name number="1">
+<value>A</value>
+<type topicref="2"></type>
+</name>
+<name number="2">
+<value>B</value>
+<type topicref="2"></type>
+</name>
+</topic>
+<topic number="2">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+</topicMap>
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 (file)
index 0000000..1cc2522
--- /dev/null
@@ -0,0 +1,12 @@
+<topicMap>
+<topic number="1">
+<subjectIdentifiers>
+<locator>http://example.org/s</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#x</locator>
+<locator>#y</locator>
+<locator>http://example.org/s</locator>
+</itemIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/import-cascade.cxtm b/tests/fixtures/normalization-index/import-cascade.cxtm
new file mode 100644 (file)
index 0000000..07c1c49
--- /dev/null
@@ -0,0 +1,41 @@
+<topicMap>
+<topic number="1">
+<subjectIdentifiers>
+<locator>urn:name-type</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="2">
+<subjectIdentifiers>
+<locator>urn:owner</locator>
+</subjectIdentifiers>
+<name number="1" reifier="3">
+<value>N</value>
+<type topicref="1"></type>
+</name>
+</topic>
+<topic number="3">
+<subjectIdentifiers>
+<locator>urn:r</locator>
+<locator>urn:s</locator>
+</subjectIdentifiers>
+<occurrence number="1">
+<value>O</value>
+<datatype>http://www.w3.org/2001/XMLSchema#string</datatype>
+<type topicref="3"></type>
+<scope>
+<scopingTopic topicref="3"></scopingTopic>
+</scope>
+</occurrence>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<association number="1">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="3"></player>
+<type topicref="3"></type>
+</role>
+<scope>
+<scopingTopic topicref="3"></scopingTopic>
+</scope>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/import-reifier-chain.cxtm b/tests/fixtures/normalization-index/import-reifier-chain.cxtm
new file mode 100644 (file)
index 0000000..d4dd32b
--- /dev/null
@@ -0,0 +1,32 @@
+<topicMap>
+<topic number="1">
+<subjectIdentifiers>
+<locator>urn:owner</locator>
+</subjectIdentifiers>
+<name number="1" reifier="3">
+<value>N</value>
+<type topicref="2"></type>
+</name>
+</topic>
+<topic number="2">
+<subjectIdentifiers>
+<locator>urn:type</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="3">
+<subjectIdentifiers>
+<locator>urn:r</locator>
+<locator>urn:s</locator>
+</subjectIdentifiers>
+<name number="1" reifier="4">
+<value>K</value>
+<type topicref="2"></type>
+</name>
+</topic>
+<topic number="4">
+<subjectIdentifiers>
+<locator>urn:r2</locator>
+<locator>urn:s2</locator>
+</subjectIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/import-reifier-first.cxtm b/tests/fixtures/normalization-index/import-reifier-first.cxtm
new file mode 100644 (file)
index 0000000..0b6d411
--- /dev/null
@@ -0,0 +1,21 @@
+<topicMap>
+<topic number="1">
+<subjectIdentifiers>
+<locator>urn:owner</locator>
+</subjectIdentifiers>
+<name number="1" reifier="2">
+<value>N</value>
+<type topicref="3"></type>
+</name>
+</topic>
+<topic number="2">
+<subjectIdentifiers>
+<locator>urn:r</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="3">
+<subjectIdentifiers>
+<locator>urn:type</locator>
+</subjectIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/isa-ako.cxtm b/tests/fixtures/normalization-index/isa-ako.cxtm
new file mode 100644 (file)
index 0000000..73dce2f
--- /dev/null
@@ -0,0 +1,109 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#a</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.2.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#b</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+<rolePlayed ref="association.2.role.2"></rolePlayed>
+<rolePlayed ref="association.3.role.1"></rolePlayed>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#c</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.2"></rolePlayed>
+<rolePlayed ref="association.4.role.1"></rolePlayed>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#d</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.3.role.2"></rolePlayed>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#e</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.4.role.2"></rolePlayed>
+</topic>
+<topic number="6">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/instance</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="7">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/subtype</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="8">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/supertype</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="9">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/supertype-subtype</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="10">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/type</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="11">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/type-instance</locator>
+</subjectIdentifiers>
+</topic>
+<association number="1">
+<type topicref="9"></type>
+<role number="1">
+<player topicref="2"></player>
+<type topicref="7"></type>
+</role>
+<role number="2">
+<player topicref="3"></player>
+<type topicref="8"></type>
+</role>
+</association>
+<association number="2">
+<type topicref="11"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="2"></player>
+<type topicref="10"></type>
+</role>
+</association>
+<association number="3">
+<type topicref="11"></type>
+<role number="1">
+<player topicref="2"></player>
+<type topicref="10"></type>
+</role>
+<role number="2">
+<player topicref="4"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="4">
+<type topicref="11"></type>
+<role number="1">
+<player topicref="3"></player>
+<type topicref="10"></type>
+</role>
+<role number="2">
+<player topicref="5"></player>
+<type topicref="6"></type>
+</role>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/isa-duplicates-merge.cxtm b/tests/fixtures/normalization-index/isa-duplicates-merge.cxtm
new file mode 100644 (file)
index 0000000..fcdaf9a
--- /dev/null
@@ -0,0 +1,62 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#a</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#b</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.2.role.1"></rolePlayed>
+</topic>
+<topic number="3">
+<subjectIdentifiers>
+<locator>http://example.org/k</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#k</locator>
+<locator>#k2</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.2"></rolePlayed>
+<rolePlayed ref="association.2.role.2"></rolePlayed>
+</topic>
+<topic number="4">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/instance</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="5">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/type</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="6">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/type-instance</locator>
+</subjectIdentifiers>
+</topic>
+<association number="1">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="4"></type>
+</role>
+<role number="2">
+<player topicref="3"></player>
+<type topicref="5"></type>
+</role>
+</association>
+<association number="2">
+<type topicref="6"></type>
+<role number="1">
+<player topicref="2"></player>
+<type topicref="4"></type>
+</role>
+<role number="2">
+<player topicref="3"></player>
+<type topicref="5"></type>
+</role>
+</association>
+</topicMap>
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 (file)
index 0000000..2fd7c19
--- /dev/null
@@ -0,0 +1,55 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#a</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#b</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.2"></rolePlayed>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#c</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.3"></rolePlayed>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#r1</locator>
+</itemIdentifiers>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#r2</locator>
+</itemIdentifiers>
+</topic>
+<topic number="6">
+<itemIdentifiers>
+<locator>#r3</locator>
+</itemIdentifiers>
+</topic>
+<topic number="7">
+<itemIdentifiers>
+<locator>#t</locator>
+</itemIdentifiers>
+</topic>
+<association number="1">
+<type topicref="7"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="4"></type>
+</role>
+<role number="2">
+<player topicref="2"></player>
+<type topicref="5"></type>
+</role>
+<role number="3">
+<player topicref="3"></player>
+<type topicref="6"></type>
+</role>
+</association>
+</topicMap>
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 (file)
index 0000000..59da5ef
--- /dev/null
@@ -0,0 +1,1207 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#from</locator>
+</itemIdentifiers>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#rel0</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#rel1</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#rel2</locator>
+</itemIdentifiers>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#rel3</locator>
+</itemIdentifiers>
+</topic>
+<topic number="6">
+<itemIdentifiers>
+<locator>#to</locator>
+</itemIdentifiers>
+</topic>
+<topic number="7">
+<subjectIdentifiers>
+<locator>http://example.org/p/0</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p0</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 0</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+<rolePlayed ref="association.9.role.1"></rolePlayed>
+<rolePlayed ref="association.10.role.1"></rolePlayed>
+<rolePlayed ref="association.11.role.1"></rolePlayed>
+<rolePlayed ref="association.24.role.1"></rolePlayed>
+<rolePlayed ref="association.25.role.1"></rolePlayed>
+</topic>
+<topic number="8">
+<subjectIdentifiers>
+<locator>http://example.org/p/1</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p1</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 1</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.12.role.1"></rolePlayed>
+</topic>
+<topic number="9">
+<subjectIdentifiers>
+<locator>http://example.org/p/10</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p10</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 10</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.17.role.1"></rolePlayed>
+<rolePlayed ref="association.12.role.2"></rolePlayed>
+<rolePlayed ref="association.13.role.1"></rolePlayed>
+<rolePlayed ref="association.14.role.1"></rolePlayed>
+<rolePlayed ref="association.26.role.1"></rolePlayed>
+<rolePlayed ref="association.27.role.1"></rolePlayed>
+</topic>
+<topic number="10">
+<subjectIdentifiers>
+<locator>http://example.org/p/11</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p11</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 11</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.24.role.2"></rolePlayed>
+</topic>
+<topic number="11">
+<subjectIdentifiers>
+<locator>http://example.org/p/12</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p12</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 12</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.2.role.1"></rolePlayed>
+</topic>
+<topic number="12">
+<subjectIdentifiers>
+<locator>http://example.org/p/13</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p13</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 13</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.13.role.2"></rolePlayed>
+</topic>
+<topic number="13">
+<subjectIdentifiers>
+<locator>http://example.org/p/14</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p14</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 14</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.18.role.1"></rolePlayed>
+</topic>
+<topic number="14">
+<subjectIdentifiers>
+<locator>http://example.org/p/15</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p15</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 15</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.28.role.1"></rolePlayed>
+<rolePlayed ref="association.3.role.1"></rolePlayed>
+<rolePlayed ref="association.4.role.1"></rolePlayed>
+<rolePlayed ref="association.18.role.2"></rolePlayed>
+<rolePlayed ref="association.19.role.1"></rolePlayed>
+<rolePlayed ref="association.20.role.1"></rolePlayed>
+</topic>
+<topic number="15">
+<subjectIdentifiers>
+<locator>http://example.org/p/16</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p16</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 16</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.5.role.1"></rolePlayed>
+</topic>
+<topic number="16">
+<subjectIdentifiers>
+<locator>http://example.org/p/17</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p17</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 17</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.9.role.2"></rolePlayed>
+</topic>
+<topic number="17">
+<subjectIdentifiers>
+<locator>http://example.org/p/18</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p18</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 18</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.21.role.1"></rolePlayed>
+</topic>
+<topic number="18">
+<subjectIdentifiers>
+<locator>http://example.org/p/19</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p19</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 19</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.26.role.2"></rolePlayed>
+</topic>
+<topic number="19">
+<subjectIdentifiers>
+<locator>http://example.org/p/2</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p2</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 2</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.19.role.2"></rolePlayed>
+</topic>
+<topic number="20">
+<subjectIdentifiers>
+<locator>http://example.org/p/20</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p20</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 20</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.3.role.2"></rolePlayed>
+<rolePlayed ref="association.15.role.1"></rolePlayed>
+<rolePlayed ref="association.16.role.1"></rolePlayed>
+<rolePlayed ref="association.28.role.2"></rolePlayed>
+<rolePlayed ref="association.29.role.1"></rolePlayed>
+<rolePlayed ref="association.30.role.1"></rolePlayed>
+</topic>
+<topic number="21">
+<subjectIdentifiers>
+<locator>http://example.org/p/21</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p21</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 21</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.15.role.2"></rolePlayed>
+</topic>
+<topic number="22">
+<subjectIdentifiers>
+<locator>http://example.org/p/22</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p22</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 22</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.22.role.1"></rolePlayed>
+</topic>
+<topic number="23">
+<subjectIdentifiers>
+<locator>http://example.org/p/23</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p23</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 23</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.25.role.2"></rolePlayed>
+</topic>
+<topic number="24">
+<subjectIdentifiers>
+<locator>http://example.org/p/24</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p24</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 24</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.6.role.1"></rolePlayed>
+</topic>
+<topic number="25">
+<subjectIdentifiers>
+<locator>http://example.org/p/25</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p25</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 25</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.14.role.2"></rolePlayed>
+<rolePlayed ref="association.5.role.2"></rolePlayed>
+<rolePlayed ref="association.7.role.1"></rolePlayed>
+<rolePlayed ref="association.8.role.1"></rolePlayed>
+<rolePlayed ref="association.17.role.2"></rolePlayed>
+<rolePlayed ref="association.22.role.2"></rolePlayed>
+</topic>
+<topic number="26">
+<subjectIdentifiers>
+<locator>http://example.org/p/26</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p26</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 26</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.20.role.2"></rolePlayed>
+</topic>
+<topic number="27">
+<subjectIdentifiers>
+<locator>http://example.org/p/27</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p27</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 27</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.29.role.2"></rolePlayed>
+</topic>
+<topic number="28">
+<subjectIdentifiers>
+<locator>http://example.org/p/28</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p28</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 28</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.7.role.2"></rolePlayed>
+</topic>
+<topic number="29">
+<subjectIdentifiers>
+<locator>http://example.org/p/29</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p29</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 29</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.10.role.2"></rolePlayed>
+</topic>
+<topic number="30">
+<subjectIdentifiers>
+<locator>http://example.org/p/3</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p3</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 3</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.30.role.2"></rolePlayed>
+</topic>
+<topic number="31">
+<subjectIdentifiers>
+<locator>http://example.org/p/4</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p4</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 4</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.8.role.2"></rolePlayed>
+</topic>
+<topic number="32">
+<subjectIdentifiers>
+<locator>http://example.org/p/5</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p5</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 5</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.11.role.2"></rolePlayed>
+<rolePlayed ref="association.1.role.2"></rolePlayed>
+<rolePlayed ref="association.2.role.2"></rolePlayed>
+<rolePlayed ref="association.6.role.2"></rolePlayed>
+<rolePlayed ref="association.21.role.2"></rolePlayed>
+<rolePlayed ref="association.23.role.1"></rolePlayed>
+</topic>
+<topic number="33">
+<subjectIdentifiers>
+<locator>http://example.org/p/6</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p6</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 6</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.23.role.2"></rolePlayed>
+</topic>
+<topic number="34">
+<subjectIdentifiers>
+<locator>http://example.org/p/7</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p7</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 7</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.27.role.2"></rolePlayed>
+</topic>
+<topic number="35">
+<subjectIdentifiers>
+<locator>http://example.org/p/8</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p8</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 8</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.4.role.2"></rolePlayed>
+</topic>
+<topic number="36">
+<subjectIdentifiers>
+<locator>http://example.org/p/9</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p9</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 9</value>
+<type topicref="57"></type>
+</name>
+<rolePlayed ref="association.16.role.2"></rolePlayed>
+</topic>
+<topic number="37">
+<subjectIdentifiers>
+<locator>http://example.org/r/1</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r1</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 1</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="38">
+<subjectIdentifiers>
+<locator>http://example.org/r/10</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r10</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 10</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="39">
+<subjectIdentifiers>
+<locator>http://example.org/r/11</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r11</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 11</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="40">
+<subjectIdentifiers>
+<locator>http://example.org/r/13</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r13</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 13</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="41">
+<subjectIdentifiers>
+<locator>http://example.org/r/14</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r14</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 14</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="42">
+<subjectIdentifiers>
+<locator>http://example.org/r/16</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r16</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 16</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="43">
+<subjectIdentifiers>
+<locator>http://example.org/r/17</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r17</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 17</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="44">
+<subjectIdentifiers>
+<locator>http://example.org/r/19</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r19</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 19</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="45">
+<subjectIdentifiers>
+<locator>http://example.org/r/2</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r2</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 2</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="46">
+<subjectIdentifiers>
+<locator>http://example.org/r/20</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r20</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 20</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="47">
+<subjectIdentifiers>
+<locator>http://example.org/r/22</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r22</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 22</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="48">
+<subjectIdentifiers>
+<locator>http://example.org/r/23</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r23</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 23</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="49">
+<subjectIdentifiers>
+<locator>http://example.org/r/25</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r25</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 25</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="50">
+<subjectIdentifiers>
+<locator>http://example.org/r/26</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r26</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 26</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="51">
+<subjectIdentifiers>
+<locator>http://example.org/r/28</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r28</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 28</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="52">
+<subjectIdentifiers>
+<locator>http://example.org/r/29</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r29</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 29</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="53">
+<subjectIdentifiers>
+<locator>http://example.org/r/4</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r4</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 4</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="54">
+<subjectIdentifiers>
+<locator>http://example.org/r/5</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r5</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 5</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="55">
+<subjectIdentifiers>
+<locator>http://example.org/r/7</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r7</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 7</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="56">
+<subjectIdentifiers>
+<locator>http://example.org/r/8</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r8</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 8</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="57">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="58">
+<subjectIdentifiers>
+<locator>http://example.org/q/0</locator>
+<locator>http://example.org/r/0</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q0</locator>
+<locator>#r0</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 0</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 0</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="59">
+<subjectIdentifiers>
+<locator>http://example.org/q/12</locator>
+<locator>http://example.org/r/12</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q12</locator>
+<locator>#r12</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 12</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 12</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="60">
+<subjectIdentifiers>
+<locator>http://example.org/q/15</locator>
+<locator>http://example.org/r/15</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q15</locator>
+<locator>#r15</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 15</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 15</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="61">
+<subjectIdentifiers>
+<locator>http://example.org/q/18</locator>
+<locator>http://example.org/r/18</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q18</locator>
+<locator>#r18</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 18</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 18</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="62">
+<subjectIdentifiers>
+<locator>http://example.org/q/21</locator>
+<locator>http://example.org/r/21</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q21</locator>
+<locator>#r21</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 21</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 21</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="63">
+<subjectIdentifiers>
+<locator>http://example.org/q/24</locator>
+<locator>http://example.org/r/24</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q24</locator>
+<locator>#r24</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 24</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 24</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="64">
+<subjectIdentifiers>
+<locator>http://example.org/q/27</locator>
+<locator>http://example.org/r/27</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q27</locator>
+<locator>#r27</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 27</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 27</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="65">
+<subjectIdentifiers>
+<locator>http://example.org/q/3</locator>
+<locator>http://example.org/r/3</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q3</locator>
+<locator>#r3</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 3</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 3</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="66">
+<subjectIdentifiers>
+<locator>http://example.org/q/6</locator>
+<locator>http://example.org/r/6</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q6</locator>
+<locator>#r6</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 6</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 6</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<topic number="67">
+<subjectIdentifiers>
+<locator>http://example.org/q/9</locator>
+<locator>http://example.org/r/9</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#q9</locator>
+<locator>#r9</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Q 9</value>
+<type topicref="57"></type>
+</name>
+<name number="2">
+<value>R 9</value>
+<type topicref="57"></type>
+</name>
+</topic>
+<association number="1" reifier="58">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="2" reifier="59">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="11"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="3" reifier="46">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="20"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="4" reifier="56">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="35"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="5" reifier="42">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="15"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="6" reifier="63">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="24"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="7" reifier="51">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="28"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="8" reifier="53">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="31"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="9" reifier="43">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="16"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="10" reifier="52">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="29"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="11" reifier="54">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="12" reifier="37">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="8"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="13" reifier="40">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="12"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="14" reifier="49">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="15" reifier="62">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="21"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="16" reifier="67">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="36"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="17" reifier="38">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="18" reifier="41">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="13"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="19" reifier="45">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="19"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="20" reifier="50">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="26"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="21" reifier="61">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="17"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="22" reifier="47">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="22"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="23" reifier="66">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="33"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="24" reifier="39">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="10"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="25" reifier="48">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="23"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="26" reifier="44">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="18"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="27" reifier="55">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="34"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="28" reifier="60">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="29" reifier="64">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="27"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="30" reifier="65">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="30"></player>
+<type topicref="1"></type>
+</role>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/reified-30-associations.cxtm b/tests/fixtures/normalization-index/reified-30-associations.cxtm
new file mode 100644 (file)
index 0000000..87f4ca1
--- /dev/null
@@ -0,0 +1,1147 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#from</locator>
+</itemIdentifiers>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#rel0</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#rel1</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#rel2</locator>
+</itemIdentifiers>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#rel3</locator>
+</itemIdentifiers>
+</topic>
+<topic number="6">
+<itemIdentifiers>
+<locator>#to</locator>
+</itemIdentifiers>
+</topic>
+<topic number="7">
+<subjectIdentifiers>
+<locator>http://example.org/p/0</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p0</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 0</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+<rolePlayed ref="association.9.role.1"></rolePlayed>
+<rolePlayed ref="association.10.role.1"></rolePlayed>
+<rolePlayed ref="association.11.role.1"></rolePlayed>
+<rolePlayed ref="association.24.role.1"></rolePlayed>
+<rolePlayed ref="association.25.role.1"></rolePlayed>
+</topic>
+<topic number="8">
+<subjectIdentifiers>
+<locator>http://example.org/p/1</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p1</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 1</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.12.role.1"></rolePlayed>
+</topic>
+<topic number="9">
+<subjectIdentifiers>
+<locator>http://example.org/p/10</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p10</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 10</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.17.role.1"></rolePlayed>
+<rolePlayed ref="association.12.role.2"></rolePlayed>
+<rolePlayed ref="association.13.role.1"></rolePlayed>
+<rolePlayed ref="association.14.role.1"></rolePlayed>
+<rolePlayed ref="association.26.role.1"></rolePlayed>
+<rolePlayed ref="association.27.role.1"></rolePlayed>
+</topic>
+<topic number="10">
+<subjectIdentifiers>
+<locator>http://example.org/p/11</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p11</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 11</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.24.role.2"></rolePlayed>
+</topic>
+<topic number="11">
+<subjectIdentifiers>
+<locator>http://example.org/p/12</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p12</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 12</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.2.role.1"></rolePlayed>
+</topic>
+<topic number="12">
+<subjectIdentifiers>
+<locator>http://example.org/p/13</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p13</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 13</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.13.role.2"></rolePlayed>
+</topic>
+<topic number="13">
+<subjectIdentifiers>
+<locator>http://example.org/p/14</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p14</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 14</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.18.role.1"></rolePlayed>
+</topic>
+<topic number="14">
+<subjectIdentifiers>
+<locator>http://example.org/p/15</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p15</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 15</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.28.role.1"></rolePlayed>
+<rolePlayed ref="association.3.role.1"></rolePlayed>
+<rolePlayed ref="association.4.role.1"></rolePlayed>
+<rolePlayed ref="association.18.role.2"></rolePlayed>
+<rolePlayed ref="association.19.role.1"></rolePlayed>
+<rolePlayed ref="association.20.role.1"></rolePlayed>
+</topic>
+<topic number="15">
+<subjectIdentifiers>
+<locator>http://example.org/p/16</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p16</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 16</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.5.role.1"></rolePlayed>
+</topic>
+<topic number="16">
+<subjectIdentifiers>
+<locator>http://example.org/p/17</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p17</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 17</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.9.role.2"></rolePlayed>
+</topic>
+<topic number="17">
+<subjectIdentifiers>
+<locator>http://example.org/p/18</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p18</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 18</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.21.role.1"></rolePlayed>
+</topic>
+<topic number="18">
+<subjectIdentifiers>
+<locator>http://example.org/p/19</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p19</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 19</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.26.role.2"></rolePlayed>
+</topic>
+<topic number="19">
+<subjectIdentifiers>
+<locator>http://example.org/p/2</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p2</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 2</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.19.role.2"></rolePlayed>
+</topic>
+<topic number="20">
+<subjectIdentifiers>
+<locator>http://example.org/p/20</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p20</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 20</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.3.role.2"></rolePlayed>
+<rolePlayed ref="association.15.role.1"></rolePlayed>
+<rolePlayed ref="association.16.role.1"></rolePlayed>
+<rolePlayed ref="association.28.role.2"></rolePlayed>
+<rolePlayed ref="association.29.role.1"></rolePlayed>
+<rolePlayed ref="association.30.role.1"></rolePlayed>
+</topic>
+<topic number="21">
+<subjectIdentifiers>
+<locator>http://example.org/p/21</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p21</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 21</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.15.role.2"></rolePlayed>
+</topic>
+<topic number="22">
+<subjectIdentifiers>
+<locator>http://example.org/p/22</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p22</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 22</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.22.role.1"></rolePlayed>
+</topic>
+<topic number="23">
+<subjectIdentifiers>
+<locator>http://example.org/p/23</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p23</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 23</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.25.role.2"></rolePlayed>
+</topic>
+<topic number="24">
+<subjectIdentifiers>
+<locator>http://example.org/p/24</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p24</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 24</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.6.role.1"></rolePlayed>
+</topic>
+<topic number="25">
+<subjectIdentifiers>
+<locator>http://example.org/p/25</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p25</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 25</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.14.role.2"></rolePlayed>
+<rolePlayed ref="association.5.role.2"></rolePlayed>
+<rolePlayed ref="association.7.role.1"></rolePlayed>
+<rolePlayed ref="association.8.role.1"></rolePlayed>
+<rolePlayed ref="association.17.role.2"></rolePlayed>
+<rolePlayed ref="association.22.role.2"></rolePlayed>
+</topic>
+<topic number="26">
+<subjectIdentifiers>
+<locator>http://example.org/p/26</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p26</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 26</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.20.role.2"></rolePlayed>
+</topic>
+<topic number="27">
+<subjectIdentifiers>
+<locator>http://example.org/p/27</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p27</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 27</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.29.role.2"></rolePlayed>
+</topic>
+<topic number="28">
+<subjectIdentifiers>
+<locator>http://example.org/p/28</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p28</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 28</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.7.role.2"></rolePlayed>
+</topic>
+<topic number="29">
+<subjectIdentifiers>
+<locator>http://example.org/p/29</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p29</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 29</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.10.role.2"></rolePlayed>
+</topic>
+<topic number="30">
+<subjectIdentifiers>
+<locator>http://example.org/p/3</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p3</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 3</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.30.role.2"></rolePlayed>
+</topic>
+<topic number="31">
+<subjectIdentifiers>
+<locator>http://example.org/p/4</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p4</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 4</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.8.role.2"></rolePlayed>
+</topic>
+<topic number="32">
+<subjectIdentifiers>
+<locator>http://example.org/p/5</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p5</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 5</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.11.role.2"></rolePlayed>
+<rolePlayed ref="association.1.role.2"></rolePlayed>
+<rolePlayed ref="association.2.role.2"></rolePlayed>
+<rolePlayed ref="association.6.role.2"></rolePlayed>
+<rolePlayed ref="association.21.role.2"></rolePlayed>
+<rolePlayed ref="association.23.role.1"></rolePlayed>
+</topic>
+<topic number="33">
+<subjectIdentifiers>
+<locator>http://example.org/p/6</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p6</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 6</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.23.role.2"></rolePlayed>
+</topic>
+<topic number="34">
+<subjectIdentifiers>
+<locator>http://example.org/p/7</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p7</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 7</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.27.role.2"></rolePlayed>
+</topic>
+<topic number="35">
+<subjectIdentifiers>
+<locator>http://example.org/p/8</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p8</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 8</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.4.role.2"></rolePlayed>
+</topic>
+<topic number="36">
+<subjectIdentifiers>
+<locator>http://example.org/p/9</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p9</locator>
+</itemIdentifiers>
+<name number="1">
+<value>P 9</value>
+<type topicref="67"></type>
+</name>
+<rolePlayed ref="association.16.role.2"></rolePlayed>
+</topic>
+<topic number="37">
+<subjectIdentifiers>
+<locator>http://example.org/r/0</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r0</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 0</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="38">
+<subjectIdentifiers>
+<locator>http://example.org/r/1</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r1</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 1</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="39">
+<subjectIdentifiers>
+<locator>http://example.org/r/10</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r10</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 10</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="40">
+<subjectIdentifiers>
+<locator>http://example.org/r/11</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r11</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 11</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="41">
+<subjectIdentifiers>
+<locator>http://example.org/r/12</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r12</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 12</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="42">
+<subjectIdentifiers>
+<locator>http://example.org/r/13</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r13</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 13</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="43">
+<subjectIdentifiers>
+<locator>http://example.org/r/14</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r14</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 14</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="44">
+<subjectIdentifiers>
+<locator>http://example.org/r/15</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r15</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 15</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="45">
+<subjectIdentifiers>
+<locator>http://example.org/r/16</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r16</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 16</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="46">
+<subjectIdentifiers>
+<locator>http://example.org/r/17</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r17</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 17</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="47">
+<subjectIdentifiers>
+<locator>http://example.org/r/18</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r18</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 18</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="48">
+<subjectIdentifiers>
+<locator>http://example.org/r/19</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r19</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 19</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="49">
+<subjectIdentifiers>
+<locator>http://example.org/r/2</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r2</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 2</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="50">
+<subjectIdentifiers>
+<locator>http://example.org/r/20</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r20</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 20</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="51">
+<subjectIdentifiers>
+<locator>http://example.org/r/21</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r21</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 21</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="52">
+<subjectIdentifiers>
+<locator>http://example.org/r/22</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r22</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 22</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="53">
+<subjectIdentifiers>
+<locator>http://example.org/r/23</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r23</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 23</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="54">
+<subjectIdentifiers>
+<locator>http://example.org/r/24</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r24</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 24</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="55">
+<subjectIdentifiers>
+<locator>http://example.org/r/25</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r25</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 25</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="56">
+<subjectIdentifiers>
+<locator>http://example.org/r/26</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r26</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 26</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="57">
+<subjectIdentifiers>
+<locator>http://example.org/r/27</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r27</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 27</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="58">
+<subjectIdentifiers>
+<locator>http://example.org/r/28</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r28</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 28</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="59">
+<subjectIdentifiers>
+<locator>http://example.org/r/29</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r29</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 29</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="60">
+<subjectIdentifiers>
+<locator>http://example.org/r/3</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r3</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 3</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="61">
+<subjectIdentifiers>
+<locator>http://example.org/r/4</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r4</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 4</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="62">
+<subjectIdentifiers>
+<locator>http://example.org/r/5</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r5</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 5</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="63">
+<subjectIdentifiers>
+<locator>http://example.org/r/6</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r6</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 6</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="64">
+<subjectIdentifiers>
+<locator>http://example.org/r/7</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r7</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 7</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="65">
+<subjectIdentifiers>
+<locator>http://example.org/r/8</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r8</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 8</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="66">
+<subjectIdentifiers>
+<locator>http://example.org/r/9</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#r9</locator>
+</itemIdentifiers>
+<name number="1">
+<value>R 9</value>
+<type topicref="67"></type>
+</name>
+</topic>
+<topic number="67">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+<association number="1" reifier="37">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="2" reifier="41">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="11"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="3" reifier="50">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="20"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="4" reifier="65">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="35"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="5" reifier="45">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="15"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="6" reifier="54">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="24"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="7" reifier="58">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="28"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="8" reifier="61">
+<type topicref="2"></type>
+<role number="1">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="31"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="9" reifier="46">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="16"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="10" reifier="59">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="29"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="11" reifier="62">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="12" reifier="38">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="8"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="13" reifier="42">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="12"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="14" reifier="55">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="15" reifier="51">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="21"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="16" reifier="66">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="36"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="17" reifier="39">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="18" reifier="43">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="13"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="19" reifier="49">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="19"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="20" reifier="56">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="26"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="21" reifier="47">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="17"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="22" reifier="52">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="22"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="25"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="23" reifier="63">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="32"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="33"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="24" reifier="40">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="10"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="25" reifier="53">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="7"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="23"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="26" reifier="48">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="18"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="27" reifier="64">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="9"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="34"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="28" reifier="44">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="14"></player>
+<type topicref="1"></type>
+</role>
+<role number="2">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+</association>
+<association number="29" reifier="57">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="27"></player>
+<type topicref="1"></type>
+</role>
+</association>
+<association number="30" reifier="60">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="20"></player>
+<type topicref="6"></type>
+</role>
+<role number="2">
+<player topicref="30"></player>
+<type topicref="1"></type>
+</role>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/reified-duplicate-associations.cxtm b/tests/fixtures/normalization-index/reified-duplicate-associations.cxtm
new file mode 100644 (file)
index 0000000..62483b5
--- /dev/null
@@ -0,0 +1,44 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#p</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#r</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#t</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#x</locator>
+<locator>#y</locator>
+</itemIdentifiers>
+<name number="1">
+<value>X</value>
+<type topicref="5"></type>
+</name>
+<name number="2">
+<value>Y</value>
+<type topicref="5"></type>
+</name>
+</topic>
+<topic number="5">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+<association number="1" reifier="4">
+<type topicref="3"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="2"></type>
+</role>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/reified-duplicate-names.cxtm b/tests/fixtures/normalization-index/reified-duplicate-names.cxtm
new file mode 100644 (file)
index 0000000..7f2e455
--- /dev/null
@@ -0,0 +1,22 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#n</locator>
+</itemIdentifiers>
+<name number="1" reifier="2">
+<value>N</value>
+<type topicref="3"></type>
+</name>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#nr</locator>
+<locator>#nr2</locator>
+</itemIdentifiers>
+</topic>
+<topic number="3">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+</topicMap>
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 (file)
index 0000000..807d1cb
--- /dev/null
@@ -0,0 +1,63 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#p</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#q</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.2.role.1"></rolePlayed>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#r</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#t</locator>
+</itemIdentifiers>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#u</locator>
+</itemIdentifiers>
+</topic>
+<topic number="6">
+<itemIdentifiers>
+<locator>#v</locator>
+</itemIdentifiers>
+</topic>
+<topic number="7">
+<itemIdentifiers>
+<locator>#w</locator>
+<locator>#x</locator>
+</itemIdentifiers>
+<name number="1">
+<value>W</value>
+<type topicref="8"></type>
+</name>
+</topic>
+<topic number="8">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+<association number="1" reifier="7">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="3"></type>
+</role>
+</association>
+<association number="2" reifier="6">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="2"></player>
+<type topicref="3"></type>
+</role>
+</association>
+</topicMap>
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 (file)
index 0000000..c29f443
--- /dev/null
@@ -0,0 +1,63 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#p</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.1.role.1"></rolePlayed>
+</topic>
+<topic number="2">
+<itemIdentifiers>
+<locator>#q</locator>
+</itemIdentifiers>
+<rolePlayed ref="association.2.role.1"></rolePlayed>
+</topic>
+<topic number="3">
+<itemIdentifiers>
+<locator>#r</locator>
+</itemIdentifiers>
+</topic>
+<topic number="4">
+<itemIdentifiers>
+<locator>#t</locator>
+</itemIdentifiers>
+</topic>
+<topic number="5">
+<itemIdentifiers>
+<locator>#u</locator>
+</itemIdentifiers>
+</topic>
+<topic number="6">
+<itemIdentifiers>
+<locator>#x</locator>
+</itemIdentifiers>
+</topic>
+<topic number="7">
+<itemIdentifiers>
+<locator>#y</locator>
+<locator>#z</locator>
+</itemIdentifiers>
+<name number="1">
+<value>Z</value>
+<type topicref="8"></type>
+</name>
+</topic>
+<topic number="8">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+<association number="1" reifier="6">
+<type topicref="4"></type>
+<role number="1">
+<player topicref="1"></player>
+<type topicref="3"></type>
+</role>
+</association>
+<association number="2" reifier="7">
+<type topicref="5"></type>
+<role number="1">
+<player topicref="2"></player>
+<type topicref="3"></type>
+</role>
+</association>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/rejections.sexp b/tests/fixtures/normalization-index/rejections.sexp
new file mode 100644 (file)
index 0000000..a8e8b05
--- /dev/null
@@ -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 (file)
index 0000000..f901a65
--- /dev/null
@@ -0,0 +1,18 @@
+<topicMap>
+<topic number="1">
+<subjectLocators>
+<locator>http://example.org/z</locator>
+</subjectLocators>
+<itemIdentifiers>
+<locator>#t2</locator>
+</itemIdentifiers>
+</topic>
+<topic number="2">
+<subjectIdentifiers>
+<locator>http://example.org/z</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#t1</locator>
+</itemIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/subject-locator-merge.cxtm b/tests/fixtures/normalization-index/subject-locator-merge.cxtm
new file mode 100644 (file)
index 0000000..5f639f5
--- /dev/null
@@ -0,0 +1,11 @@
+<topicMap>
+<topic number="1">
+<subjectLocators>
+<locator>http://example.org/doc</locator>
+</subjectLocators>
+<itemIdentifiers>
+<locator>#s1</locator>
+<locator>#s2</locator>
+</itemIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/topic-map-reifier.cxtm b/tests/fixtures/normalization-index/topic-map-reifier.cxtm
new file mode 100644 (file)
index 0000000..6ef75bb
--- /dev/null
@@ -0,0 +1,16 @@
+<topicMap reifier="1">
+<topic number="1">
+<itemIdentifiers>
+<locator>#mapr</locator>
+</itemIdentifiers>
+<name number="1">
+<value>M</value>
+<type topicref="2"></type>
+</name>
+</topic>
+<topic number="2">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/transitive-late-chain.cxtm b/tests/fixtures/normalization-index/transitive-late-chain.cxtm
new file mode 100644 (file)
index 0000000..7adbcc8
--- /dev/null
@@ -0,0 +1,15 @@
+<topicMap>
+<topic number="1">
+<subjectIdentifiers>
+<locator>http://example.org/p</locator>
+<locator>http://example.org/q</locator>
+<locator>http://example.org/r</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#p</locator>
+<locator>#q</locator>
+<locator>#r</locator>
+<locator>http://example.org/r</locator>
+</itemIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/transitive-through-third.cxtm b/tests/fixtures/normalization-index/transitive-through-third.cxtm
new file mode 100644 (file)
index 0000000..89c23cf
--- /dev/null
@@ -0,0 +1,23 @@
+<topicMap>
+<topic number="1">
+<subjectIdentifiers>
+<locator>http://psi.topicmaps.org/iso13250/model/topic-name</locator>
+</subjectIdentifiers>
+</topic>
+<topic number="2">
+<subjectIdentifiers>
+<locator>http://example.org/1</locator>
+<locator>http://example.org/2</locator>
+</subjectIdentifiers>
+<itemIdentifiers>
+<locator>#a</locator>
+<locator>#b</locator>
+<locator>#c</locator>
+<locator>http://example.org/1</locator>
+</itemIdentifiers>
+<name number="1">
+<value>C</value>
+<type topicref="1"></type>
+</name>
+</topic>
+</topicMap>
diff --git a/tests/fixtures/normalization-index/wildcard-merge.cxtm b/tests/fixtures/normalization-index/wildcard-merge.cxtm
new file mode 100644 (file)
index 0000000..76268b1
--- /dev/null
@@ -0,0 +1,7 @@
+<topicMap>
+<topic number="1">
+<itemIdentifiers>
+<locator>#$__1.foo</locator>
+</itemIdentifiers>
+</topic>
+</topicMap>
diff --git a/tests/normalization-index.lisp b/tests/normalization-index.lisp
new file mode 100644 (file)
index 0000000..c6b7ff5
--- /dev/null
@@ -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*))
index eb6c4e0053237d1989df9ae73fdd68eab76c3512..9d29fca907fd7da1f4d74293d30d01673848c25e 100644 (file)
   :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)))