]> dreyeck.freedombox.rocks Git - topic-maps.git/blobdiff - src/tmdm/merging.lisp
perf(tmdm): index association normalization merge candidates
[topic-maps.git] / src / tmdm / merging.lisp
index d9dfd781c23313bcc21cde7efbd1363d23e20641..454fec130a66e6aa078df4d7d3dccb84b54814cb 100644 (file)
@@ -82,6 +82,7 @@
 (defun merge-two-topics (map a b)
   ;; TMDM 6.2: create C, union supported properties, replace model references.
   ;; TMDM 6.2 conflict is checked against current targets BEFORE replacement.
 (defun merge-two-topics (map a b)
   ;; TMDM 6.2: create C, union supported properties, replace model references.
   ;; TMDM 6.2 conflict is checked against current targets BEFORE replacement.
+  (check-core-subject-identifiers (append (%topic-subject-identifiers a) (%topic-subject-identifiers b)))
   (let ((left (topic-reified a)) (right (topic-reified b)))
     (when (and left right (not (eq left right)))
       (reification-problem :reifier-conflict "Topics reify different information items.")))
   (let ((left (topic-reified a)) (right (topic-reified b)))
     (when (and left right (not (eq left right)))
       (reification-problem :reifier-conflict "Topics reify different information items.")))
     (normalize-associations map)
     (canonical-topic c)))
 
     (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)
 (defun normalize-topic-map (map)
   "Reach a fixed point of same-map Topic and structural item merging."
   (check-type map topic-map)
-  (when (needs-reification-preflight-p map)
+  (when (needs-merge-preflight-p map)
     (return-from normalize-topic-map
     (return-from normalize-topic-map
-      (preflight-reification-mutation map (lambda (ref) (normalize-topic-map (funcall ref map))))))
+      (preflight-merge-mutation map (lambda (ref) (normalize-topic-map (funcall ref map))))))
+  (validate-map-core-subjects map)
   (check-variant-merge-constraints map)
   (loop for before = (length (map-information-items map)) do
   (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)
+    (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))
           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))
@@ -146,8 +214,8 @@ Explicit merging may assert shared subject identity beyond locator equality.
 Cross-map merging is rejected before mutation. Obsolete handles remain resolvable."
   (let* ((a (live-topic a)) (b (live-topic b)) (map (%topic-parent a)))
     (unless (eq map (%topic-parent b)) (error "Cross-map Topic merging is outside this API."))
 Cross-map merging is rejected before mutation. Obsolete handles remain resolvable."
   (let* ((a (live-topic a)) (b (live-topic b)) (map (%topic-parent a)))
     (unless (eq map (%topic-parent b)) (error "Cross-map Topic merging is outside this API."))
-    (when (needs-reification-preflight-p map)
-      (return-from merge-topics (preflight-reification-mutation map
+    (when (needs-merge-preflight-p map)
+      (return-from merge-topics (preflight-merge-mutation map
         (lambda (ref) (merge-topics (funcall ref a) (funcall ref b))))))
     (unless (eq a b) (setf a (merge-two-topics map a b)))
     (normalize-topic-map map)
         (lambda (ref) (merge-topics (funcall ref a) (funcall ref b))))))
     (unless (eq a b) (setf a (merge-two-topics map a b)))
     (normalize-topic-map map)
@@ -159,9 +227,11 @@ KIND is :ITEM-IDENTIFIER, :SUBJECT-IDENTIFIER or :SUBJECT-LOCATOR.
 IRI is an already resolved, nonempty absolute locator string; CTM validates it."
   (unless (and (stringp iri) (plusp (length iri))) (error "A nonempty locator string is required."))
   (let ((topic (live-topic topic)))
 IRI is an already resolved, nonempty absolute locator string; CTM validates it."
   (unless (and (stringp iri) (plusp (length iri))) (error "A nonempty locator string is required."))
   (let ((topic (live-topic topic)))
-    (when (needs-reification-preflight-p (%topic-parent topic))
-      (return-from add-topic-identifier (preflight-reification-mutation (%topic-parent topic)
+    (when (needs-merge-preflight-p (%topic-parent topic))
+      (return-from add-topic-identifier (preflight-merge-mutation (%topic-parent topic)
         (lambda (ref) (add-topic-identifier (funcall ref topic) kind iri)))))
         (lambda (ref) (add-topic-identifier (funcall ref topic) kind iri)))))
+    (when (eq kind :subject-identifier)
+      (check-core-subject-identifiers (cons iri (%topic-subject-identifiers topic))))
     (check-topic-occurrence-identifiers (%topic-parent topic) kind iri)
     ;; Check the entire prospective identity closure before adding the locator.
     (check-variant-merge-constraints (%topic-parent topic) :identifier (list topic kind iri))
     (check-topic-occurrence-identifiers (%topic-parent topic) kind iri)
     ;; Check the entire prospective identity closure before adding the locator.
     (check-variant-merge-constraints (%topic-parent topic) :identifier (list topic kind iri))
@@ -179,6 +249,11 @@ IRI is an already resolved, nonempty absolute locator string; CTM validates it."
   ;; Validate the category even for an empty map, before adding a Topic.
   (ecase kind ((:item-identifier :subject-identifier :subject-locator)))
   (check-topic-occurrence-identifiers map kind iri)
   ;; Validate the category even for an empty map, before adding a Topic.
   (ecase kind ((:item-identifier :subject-identifier :subject-locator)))
   (check-topic-occurrence-identifiers map kind iri)
+  ;; Preflight BEFORE creating a new Topic, so rejected cascades cannot leave
+  ;; even an empty newly interned item in the original Map.
+  (when (needs-merge-preflight-p map)
+    (return-from intern-topic (preflight-merge-mutation map
+      (lambda (ref) (intern-topic (funcall ref map) kind iri)))))
   (let ((topic (or (find-if (lambda (topic) (identifier-matches-p topic kind iri))
                            (%topic-map-topics map))
                    (let ((new (%make-topic map)))
   (let ((topic (or (find-if (lambda (topic) (identifier-matches-p topic kind iri))
                            (%topic-map-topics map))
                    (let ((new (%make-topic map)))