]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - src/tmdm/merging.lisp
perf(tmdm): index topic normalization merge candidates
[topic-maps.git] / src / tmdm / merging.lisp
1 (in-package #:topic-maps.tmdm)
2
3 (defun identifiers (topic kind)
4 (ecase kind
5 (:item-identifier (%topic-item-identifiers topic))
6 (:subject-identifier (%topic-subject-identifiers topic))
7 (:subject-locator (%topic-subject-locators topic))))
8
9 (defun identifier-matches-p (topic kind iri)
10 ;; One identity rule for lookup and merging: TMDM 5.3.5, excluding reification.
11 (some (lambda (property) (member iri (identifiers topic property) :test #'string=))
12 (ecase kind
13 ((:item-identifier :subject-identifier) '(:item-identifier :subject-identifier))
14 (:subject-locator '(:subject-locator)))))
15
16 (defun equal-topics-p (a b)
17 (or (some (lambda (kind)
18 (some (lambda (iri) (identifier-matches-p a kind iri)) (identifiers b kind)))
19 '(:item-identifier :subject-identifier :subject-locator))
20 (let ((target (topic-reified a))) (and target (eq target (topic-reified b))))))
21
22 (defun set-union (a b test)
23 (remove-duplicates (append a b) :test test :from-end t))
24
25 (defun replace-pair (items a b replacement)
26 ;; Set ordering is not normative; retain the first replaced position.
27 (loop with inserted = nil for item in items
28 append (if (or (eq item a) (eq item b))
29 (unless inserted (setf inserted t) (list replacement))
30 (list item))))
31
32 (defun equal-pair (items predicate)
33 (loop for tail on items do
34 (let ((other (find-if (lambda (item) (funcall predicate (first tail) item)) (rest tail))))
35 (when other (return (list (first tail) other))))))
36
37 (define-condition scope-error (error)
38 ((code :initarg :code :reader scope-error-code)
39 (detail :initarg :detail :reader scope-error-detail))
40 (:report (lambda (c stream) (format stream "Scope ~A: ~A" (scope-error-code c) (scope-error-detail c)))))
41 (defun scope-problem (code detail) (error 'scope-error :code code :detail detail))
42 (defun proper-list-p (value)
43 ;; LIST-LENGTH detects cycles; dotted tails signal TYPE-ERROR. ANSI CL only.
44 (and (listp value) (handler-case (integerp (list-length value)) (type-error () nil))))
45 (defun canonical-scope (map themes)
46 "Validate before mutation and copy a set of current same-map Topic references."
47 (unless (proper-list-p themes)
48 (scope-problem :invalid-scope "Supply a proper finite list of Topics."))
49 (remove-duplicates
50 (mapcar (lambda (theme)
51 (unless (typep theme 'topic) (scope-problem :invalid-theme "A theme must be a Topic object."))
52 (let ((current (live-topic theme)))
53 (unless (eq map (%topic-parent current))
54 (scope-problem :foreign-theme "Every theme must belong to the item's Topic Map."))
55 current)) themes)
56 :test #'eq :from-end t))
57 (defun same-scope-p (a b)
58 ;; Storage is canonical and duplicate-free; equality has no sequence ordering.
59 (and (= (length a) (length b)) (every (lambda (theme) (member theme b :test #'eq)) a)))
60
61 (defun normalize-names (map)
62 ;; Rescan live owners after each replacement: merging Reifiers can replace
63 ;; the owner/type/theme of the very Name currently being normalized.
64 (loop for entry = (loop for topic in (%topic-map-topics map)
65 for pair = (equal-pair (%topic-names topic)
66 (lambda (a b) (and (string= (%topic-name-value a) (%topic-name-value b))
67 (eq (%topic-name-type a) (%topic-name-type b))
68 (same-scope-p (%topic-name-scope a) (%topic-name-scope b)))))
69 when pair return (cons topic pair))
70 while entry do
71 (let* ((topic (first entry)) (a (second entry)) (b (third entry))
72 (c (%make-topic-name (%topic-name-value a) (%topic-name-type a) topic)))
73 (setf (%topic-name-scope c) (copy-list (%topic-name-scope a))
74 (%topic-name-item-identifiers c) (set-union (%topic-name-item-identifiers a) (%topic-name-item-identifiers b) #'string=)
75 (%topic-name-variants c) (set-union (%topic-name-variants a) (%topic-name-variants b) #'eq)
76 (%topic-names topic) (replace-pair (%topic-names topic) a b c)
77 (%topic-name-forward a) c (%topic-name-forward b) c)
78 (dolist (v (%topic-name-variants c)) (setf (%variant-parent v) c))
79 (merge-item-reifiers c a b)))
80 (normalize-variants map))
81
82 (defun merge-two-topics (map a b)
83 ;; TMDM 6.2: create C, union supported properties, replace model references.
84 ;; TMDM 6.2 conflict is checked against current targets BEFORE replacement.
85 (check-core-subject-identifiers (append (%topic-subject-identifiers a) (%topic-subject-identifiers b)))
86 (let ((left (topic-reified a)) (right (topic-reified b)))
87 (when (and left right (not (eq left right)))
88 (reification-problem :reifier-conflict "Topics reify different information items.")))
89 (check-variant-merge-constraints map :pair (list a b))
90 (let ((c (%make-topic map)))
91 (setf (%topic-item-identifiers c) (set-union (%topic-item-identifiers a) (%topic-item-identifiers b) #'string=)
92 (%topic-subject-identifiers c) (set-union (%topic-subject-identifiers a) (%topic-subject-identifiers b) #'string=)
93 (%topic-subject-locators c) (set-union (%topic-subject-locators a) (%topic-subject-locators b) #'string=)
94 (%topic-names c) (set-union (%topic-names a) (%topic-names b) #'eq)
95 (%topic-occurrences c) (set-union (%topic-occurrences a) (%topic-occurrences b) #'eq)
96 (%topic-map-topics map) (replace-pair (%topic-map-topics map) a b c)
97 (%topic-forward a) c (%topic-forward b) c)
98 (dolist (topic (%topic-map-topics map))
99 (dolist (name (%topic-names topic))
100 ;; Parent is the computed containing topic (TMDM 5.4).
101 (setf (%topic-name-parent name) topic
102 (%topic-name-type name) (canonical-topic (%topic-name-type name))
103 (%topic-name-scope name) (canonical-scope map (%topic-name-scope name)))
104 (dolist (item (%topic-name-variants name))
105 (setf (%variant-scope item) (canonical-scope map (%variant-scope item))))))
106 (dolist (topic (%topic-map-topics map))
107 (dolist (occurrence (%topic-occurrences topic))
108 (setf (%occurrence-parent occurrence) topic
109 (%occurrence-type occurrence) (canonical-topic (%occurrence-type occurrence))
110 (%occurrence-scope occurrence) (canonical-scope map (%occurrence-scope occurrence)))))
111 (dolist (association (%topic-map-associations map))
112 (setf (%association-type association) (canonical-topic (%association-type association))
113 (%association-scope association) (canonical-scope map (%association-scope association)))
114 (dolist (role (%association-roles association))
115 (setf (%association-role-type role) (canonical-topic (%association-role-type role))
116 (%association-role-player role) (canonical-topic (%association-role-player role)))))
117 (dolist (item (map-information-items map))
118 (when (and (reifiable-p item) (%item-reifier item))
119 (setf (%item-reifier item) (canonical-topic (%item-reifier item)))))
120 (normalize-names map)
121 (normalize-occurrences map)
122 (normalize-associations map)
123 (canonical-topic c)))
124
125 (defun scan-next-topic-merge (map)
126 "The pair of Topics to merge next, found by comparing Topics pairwise: the first nonconflicting equal pair, else
127 the first equal pair, else NIL. This is the search that defines the choice; NEXT-TOPIC-MERGE returns the same pair.
128 A staged import may contain equal owners/types AND equal Reifier Topics whose Names/Occurrences/etc. have not
129 merged yet. First perform available nonconflicting Topic merges; their ordinary item merging can resolve those
130 Reified references. Do not let collection order invent a conflict. If none can proceed, MERGE-TWO-TOPICS still
131 signals TMDM 6.2's conflict; no equality or conflict rule is relaxed."
132 (let ((pair (equal-pair (%topic-map-topics map) #'equal-topics-p)))
133 (when pair
134 (or (equal-pair (%topic-map-topics map)
135 (lambda (a b)
136 (and (equal-topics-p a b)
137 (let ((left (topic-reified a)) (right (topic-reified b)))
138 (not (and left right (not (eq left right))))))))
139 pair))))
140
141 (defun next-topic-merge (map)
142 "The pair SCAN-NEXT-TOPIC-MERGE returns, found through an index built for this one search and dropped with it.
143 Two live Topics are equal exactly when they share an identifier: an item or subject identifier string (one
144 namespace, as IDENTIFIER-MATCHES-P compares them) or a subject locator string. EQUAL-TOPICS-P's third condition,
145 that both reify the same item, cannot hold for two distinct Topics: an item has one Reifier slot. A pair conflicts
146 when each Topic reifies an item and the items differ, which a table of the reified items answers without
147 TOPIC-REIFIED's scan. EQUAL-TOPICS-P and the conflict test have no side effect, so the first Topic with a later
148 sharer, and its first such sharer, are what the pairwise search finds; likewise for nonconflicting sharers.
149 The index is never kept: nothing it holds can outlive a merge or a change of Reifier.
150 When a Topic reifies two items TOPIC-REIFIED would signal from inside the search, and when a listed Topic is not
151 its own representative the table's assumptions fail; then the pairwise search itself runs, so the condition and
152 the moment it is signalled are unchanged."
153 (let ((topics (%topic-map-topics map)) (reified (make-hash-table :test #'eq)))
154 (dolist (item (map-information-items map))
155 (when (and (reifiable-p item) (%item-reifier item))
156 (push item (gethash (%item-reifier item) reified))))
157 (when (or (loop for items being the hash-values of reified thereis (rest items))
158 (some (lambda (topic) (not (eq topic (canonical-topic topic)))) topics))
159 (return-from next-topic-merge (scan-next-topic-merge map)))
160 (let ((position (make-hash-table :test #'eq)) (sharers (make-hash-table :test #'equal))
161 (keys (mapcar (lambda (topic)
162 (remove-duplicates
163 (append (mapcar (lambda (iri) (cons :item-or-subject iri))
164 (append (%topic-item-identifiers topic) (%topic-subject-identifiers topic)))
165 (mapcar (lambda (iri) (cons :subject-locator iri)) (%topic-subject-locators topic)))
166 :test #'equal))
167 topics))
168 (pair nil))
169 (loop for topic in topics for i from 0 do (setf (gethash topic position) i))
170 ;; Each key lists its Topics in map order.
171 (loop for topic in (reverse topics) for topic-keys in (reverse keys)
172 do (dolist (key topic-keys) (push topic (gethash key sharers))))
173 (flet ((earlier (a b) (if (and a b) (if (< (gethash a position) (gethash b position)) a b) (or a b)))
174 (conflict-p (a b)
175 (let ((left (first (gethash a reified))) (right (first (gethash b reified))))
176 (and left right (not (eq left right))))))
177 (loop for topic in topics for topic-keys in keys
178 do (let ((i (gethash topic position)) (first-later nil) (first-ready nil))
179 (dolist (key topic-keys)
180 (let ((seen nil))
181 (dolist (other (gethash key sharers))
182 (when (> (gethash other position) i)
183 (unless seen (setf seen t first-later (earlier first-later other)))
184 (unless (conflict-p topic other)
185 (setf first-ready (earlier first-ready other))
186 (return))))))
187 (when first-ready (return-from next-topic-merge (list topic first-ready)))
188 (when (and first-later (null pair)) (setf pair (list topic first-later))))))
189 pair)))
190
191 (defun normalize-topic-map (map)
192 "Reach a fixed point of same-map Topic and structural item merging."
193 (check-type map topic-map)
194 (when (needs-merge-preflight-p map)
195 (return-from normalize-topic-map
196 (preflight-merge-mutation map (lambda (ref) (normalize-topic-map (funcall ref map))))))
197 (validate-map-core-subjects map)
198 (check-variant-merge-constraints map)
199 (loop for before = (length (map-information-items map)) do
200 (loop for pair = (next-topic-merge map)
201 while pair do (merge-two-topics map (first pair) (second pair)))
202 (normalize-names map) (normalize-occurrences map) (normalize-associations map)
203 when (= before (length (map-information-items map))) return map))
204
205 (defun live-topic (topic)
206 (let ((current (canonical-topic topic)))
207 (unless (member current (%topic-map-topics (%topic-parent current)) :test #'eq)
208 (error "Topic is not a live member of its map."))
209 current))
210
211 (defun merge-topics (a b)
212 "Merge two Topics in the same map, returning their current representative.
213 Explicit merging may assert shared subject identity beyond locator equality.
214 Cross-map merging is rejected before mutation. Obsolete handles remain resolvable."
215 (let* ((a (live-topic a)) (b (live-topic b)) (map (%topic-parent a)))
216 (unless (eq map (%topic-parent b)) (error "Cross-map Topic merging is outside this API."))
217 (when (needs-merge-preflight-p map)
218 (return-from merge-topics (preflight-merge-mutation map
219 (lambda (ref) (merge-topics (funcall ref a) (funcall ref b))))))
220 (unless (eq a b) (setf a (merge-two-topics map a b)))
221 (normalize-topic-map map)
222 (canonical-topic a)))
223
224 (defun add-topic-identifier (topic kind iri)
225 "Add a locator to its distinct identity property and perform required merging.
226 KIND is :ITEM-IDENTIFIER, :SUBJECT-IDENTIFIER or :SUBJECT-LOCATOR.
227 IRI is an already resolved, nonempty absolute locator string; CTM validates it."
228 (unless (and (stringp iri) (plusp (length iri))) (error "A nonempty locator string is required."))
229 (let ((topic (live-topic topic)))
230 (when (needs-merge-preflight-p (%topic-parent topic))
231 (return-from add-topic-identifier (preflight-merge-mutation (%topic-parent topic)
232 (lambda (ref) (add-topic-identifier (funcall ref topic) kind iri)))))
233 (when (eq kind :subject-identifier)
234 (check-core-subject-identifiers (cons iri (%topic-subject-identifiers topic))))
235 (check-topic-occurrence-identifiers (%topic-parent topic) kind iri)
236 ;; Check the entire prospective identity closure before adding the locator.
237 (check-variant-merge-constraints (%topic-parent topic) :identifier (list topic kind iri))
238 (ecase kind
239 (:item-identifier (pushnew (copy-seq iri) (%topic-item-identifiers topic) :test #'string=))
240 (:subject-identifier (pushnew iri (%topic-subject-identifiers topic) :test #'string=))
241 (:subject-locator (pushnew iri (%topic-subject-locators topic) :test #'string=)))
242 (normalize-topic-map (%topic-parent topic))
243 (canonical-topic topic)))
244
245 (defun intern-topic (map kind iri)
246 "Lookup/create a Topic using the same identity rule as same-map merging."
247 (check-type map topic-map)
248 (unless (and (stringp iri) (plusp (length iri))) (error "A nonempty locator string is required."))
249 ;; Validate the category even for an empty map, before adding a Topic.
250 (ecase kind ((:item-identifier :subject-identifier :subject-locator)))
251 (check-topic-occurrence-identifiers map kind iri)
252 ;; Preflight BEFORE creating a new Topic, so rejected cascades cannot leave
253 ;; even an empty newly interned item in the original Map.
254 (when (needs-merge-preflight-p map)
255 (return-from intern-topic (preflight-merge-mutation map
256 (lambda (ref) (intern-topic (funcall ref map) kind iri)))))
257 (let ((topic (or (find-if (lambda (topic) (identifier-matches-p topic kind iri))
258 (%topic-map-topics map))
259 (let ((new (%make-topic map)))
260 (setf (%topic-map-topics map) (append (%topic-map-topics map) (list new)))
261 new))))
262 (add-topic-identifier topic kind iri)))
263
264 (defun add-name (topic value &key (type nil type-supplied-p) scope)
265 "Add a Name with VALUE, optional TYPE Topic and SCOPE Topic set (TMDM 5.4).
266 Validate all arguments before interning the default type. Retained Topic handles
267 are canonicalized, including after default-type identity merging."
268 (check-type value string)
269 (let* ((topic (live-topic topic)) (map (%topic-parent topic))
270 (scope (canonical-scope map scope))
271 (type (when type-supplied-p (live-topic type))))
272 (when (and type-supplied-p (not (eq map (%topic-parent type))))
273 (error "Name type belongs to another map."))
274 (unless type-supplied-p
275 (setf type (intern-topic map :subject-identifier (default-name-type-identifier))))
276 (let* ((topic (canonical-topic topic)) (type (canonical-topic type))
277 (scope (canonical-scope map scope))
278 (existing (find-if (lambda (name)
279 (and (string= value (%topic-name-value name))
280 (eq type (%topic-name-type name))
281 (same-scope-p scope (%topic-name-scope name))))
282 (%topic-names topic))))
283 (or existing
284 (let ((name (%make-topic-name value type topic)))
285 (setf (%topic-name-scope name) scope
286 (%topic-names topic) (append (%topic-names topic) (list name)))
287 name)))))
288
289 (defun add-default-name (topic value &key scope)
290 "Compatibility entry point for ADD-NAME with the CTM 3.11 default type."
291 (add-name topic value :scope scope))