]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - src/tmdm/merging.lisp
Implement general TMDM item identifiers and canonical output
[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 (some (lambda (kind)
18 (some (lambda (iri) (identifier-matches-p a kind iri)) (identifiers b kind)))
19 '(:item-identifier :subject-identifier :subject-locator)))
20
21 (defun set-union (a b test)
22 (remove-duplicates (append a b) :test test :from-end t))
23
24 (defun replace-pair (items a b replacement)
25 ;; Set ordering is not normative; retain the first replaced position.
26 (loop with inserted = nil for item in items
27 append (if (or (eq item a) (eq item b))
28 (unless inserted (setf inserted t) (list replacement))
29 (list item))))
30
31 (defun equal-pair (items predicate)
32 (loop for tail on items do
33 (let ((other (find-if (lambda (item) (funcall predicate (first tail) item)) (rest tail))))
34 (when other (return (list (first tail) other))))))
35
36 (define-condition scope-error (error)
37 ((code :initarg :code :reader scope-error-code)
38 (detail :initarg :detail :reader scope-error-detail))
39 (:report (lambda (c stream) (format stream "Scope ~A: ~A" (scope-error-code c) (scope-error-detail c)))))
40 (defun scope-problem (code detail) (error 'scope-error :code code :detail detail))
41 (defun proper-list-p (value)
42 ;; LIST-LENGTH detects cycles; dotted tails signal TYPE-ERROR. ANSI CL only.
43 (and (listp value) (handler-case (integerp (list-length value)) (type-error () nil))))
44 (defun canonical-scope (map themes)
45 "Validate before mutation and copy a set of current same-map Topic references."
46 (unless (proper-list-p themes)
47 (scope-problem :invalid-scope "Supply a proper finite list of Topics."))
48 (remove-duplicates
49 (mapcar (lambda (theme)
50 (unless (typep theme 'topic) (scope-problem :invalid-theme "A theme must be a Topic object."))
51 (let ((current (live-topic theme)))
52 (unless (eq map (%topic-parent current))
53 (scope-problem :foreign-theme "Every theme must belong to the item's Topic Map."))
54 current)) themes)
55 :test #'eq :from-end t))
56 (defun same-scope-p (a b)
57 ;; Storage is canonical and duplicate-free; equality has no sequence ordering.
58 (and (= (length a) (length b)) (every (lambda (theme) (member theme b :test #'eq)) a)))
59
60 (defun normalize-names (map)
61 ;; TMDM 5.4 and 6.3: union Variants and replace their computed Parent.
62 ;; Identifier metadata is not an equality key; reifier remains null.
63 (dolist (topic (%topic-map-topics map))
64 (loop for pair = (equal-pair (%topic-names topic)
65 (lambda (a b)
66 (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 while pair do
70 (let* ((a (first pair)) (b (second pair))
71 (c (%make-topic-name (%topic-name-value a) (%topic-name-type a) topic)))
72 (setf (%topic-name-scope c) (copy-list (%topic-name-scope a))
73 (%topic-name-item-identifiers c) (set-union (%topic-name-item-identifiers a) (%topic-name-item-identifiers b) #'string=)
74 (%topic-name-variants c) (set-union (%topic-name-variants a) (%topic-name-variants b) #'eq)
75 (%topic-names topic) (replace-pair (%topic-names topic) a b c)
76 (%topic-name-forward a) c (%topic-name-forward b) c)
77 (dolist (item (%topic-name-variants c)) (setf (%variant-parent item) c)))))
78 (normalize-variants map))
79
80 (defun merge-two-topics (map a b)
81 ;; TMDM 6.2: create C, union supported properties, replace model references.
82 ;; Replace Scope sets too; Reification remains outside the supported model.
83 (check-variant-merge-constraints map :pair (list a b))
84 (let ((c (%make-topic map)))
85 (setf (%topic-item-identifiers c) (set-union (%topic-item-identifiers a) (%topic-item-identifiers b) #'string=)
86 (%topic-subject-identifiers c) (set-union (%topic-subject-identifiers a) (%topic-subject-identifiers b) #'string=)
87 (%topic-subject-locators c) (set-union (%topic-subject-locators a) (%topic-subject-locators b) #'string=)
88 (%topic-names c) (set-union (%topic-names a) (%topic-names b) #'eq)
89 (%topic-occurrences c) (set-union (%topic-occurrences a) (%topic-occurrences b) #'eq)
90 (%topic-map-topics map) (replace-pair (%topic-map-topics map) a b c)
91 (%topic-forward a) c (%topic-forward b) c)
92 (dolist (topic (%topic-map-topics map))
93 (dolist (name (%topic-names topic))
94 ;; Parent is the computed containing topic (TMDM 5.4).
95 (setf (%topic-name-parent name) topic
96 (%topic-name-type name) (canonical-topic (%topic-name-type name))
97 (%topic-name-scope name) (canonical-scope map (%topic-name-scope name)))
98 (dolist (item (%topic-name-variants name))
99 (setf (%variant-scope item) (canonical-scope map (%variant-scope item))))))
100 (dolist (topic (%topic-map-topics map))
101 (dolist (occurrence (%topic-occurrences topic))
102 (setf (%occurrence-parent occurrence) topic
103 (%occurrence-type occurrence) (canonical-topic (%occurrence-type occurrence))
104 (%occurrence-scope occurrence) (canonical-scope map (%occurrence-scope occurrence)))))
105 (dolist (association (%topic-map-associations map))
106 (setf (%association-type association) (canonical-topic (%association-type association))
107 (%association-scope association) (canonical-scope map (%association-scope association)))
108 (dolist (role (%association-roles association))
109 (setf (%association-role-type role) (canonical-topic (%association-role-type role))
110 (%association-role-player role) (canonical-topic (%association-role-player role)))))
111 (normalize-names map)
112 (normalize-occurrences map)
113 (normalize-associations map)
114 c))
115
116 (defun normalize-topic-map (map)
117 "Apply same-map identity merging, then remove equal Names, Occurrences, Roles and Associations.
118 Only implemented properties participate; no cross-map merging."
119 (check-type map topic-map)
120 (check-variant-merge-constraints map)
121 (loop for pair = (equal-pair (%topic-map-topics map) #'equal-topics-p)
122 while pair do (merge-two-topics map (first pair) (second pair)))
123 (normalize-names map)
124 (normalize-occurrences map)
125 (normalize-associations map)
126 map)
127
128 (defun live-topic (topic)
129 (let ((current (canonical-topic topic)))
130 (unless (member current (%topic-map-topics (%topic-parent current)) :test #'eq)
131 (error "Topic is not a live member of its map."))
132 current))
133
134 (defun merge-topics (a b)
135 "Merge two Topics in the same map, returning their current representative.
136 Explicit merging may assert shared subject identity beyond locator equality.
137 Cross-map merging is rejected before mutation. Obsolete handles remain resolvable."
138 (let* ((a (live-topic a)) (b (live-topic b)) (map (%topic-parent a)))
139 (unless (eq map (%topic-parent b)) (error "Cross-map Topic merging is outside this API."))
140 (unless (eq a b) (setf a (merge-two-topics map a b)))
141 (normalize-topic-map map)
142 (canonical-topic a)))
143
144 (defun add-topic-identifier (topic kind iri)
145 "Add a locator to its distinct identity property and perform required merging.
146 KIND is :ITEM-IDENTIFIER, :SUBJECT-IDENTIFIER or :SUBJECT-LOCATOR.
147 IRI is an already resolved, nonempty absolute locator string; CTM validates it."
148 (unless (and (stringp iri) (plusp (length iri))) (error "A nonempty locator string is required."))
149 (let ((topic (live-topic topic)))
150 (check-topic-occurrence-identifiers (%topic-parent topic) kind iri)
151 ;; Check the entire prospective identity closure before adding the locator.
152 (check-variant-merge-constraints (%topic-parent topic) :identifier (list topic kind iri))
153 (ecase kind
154 (:item-identifier (pushnew (copy-seq iri) (%topic-item-identifiers topic) :test #'string=))
155 (:subject-identifier (pushnew iri (%topic-subject-identifiers topic) :test #'string=))
156 (:subject-locator (pushnew iri (%topic-subject-locators topic) :test #'string=)))
157 (normalize-topic-map (%topic-parent topic))
158 (canonical-topic topic)))
159
160 (defun intern-topic (map kind iri)
161 "Lookup/create a Topic using the same identity rule as same-map merging."
162 (check-type map topic-map)
163 (unless (and (stringp iri) (plusp (length iri))) (error "A nonempty locator string is required."))
164 ;; Validate the category even for an empty map, before adding a Topic.
165 (ecase kind ((:item-identifier :subject-identifier :subject-locator)))
166 (check-topic-occurrence-identifiers map kind iri)
167 (let ((topic (or (find-if (lambda (topic) (identifier-matches-p topic kind iri))
168 (%topic-map-topics map))
169 (let ((new (%make-topic map)))
170 (setf (%topic-map-topics map) (append (%topic-map-topics map) (list new)))
171 new))))
172 (add-topic-identifier topic kind iri)))
173
174 (defun add-name (topic value &key (type nil type-supplied-p) scope)
175 "Add a Name with VALUE, optional TYPE Topic and SCOPE Topic set (TMDM 5.4).
176 Validate all arguments before interning the default type. Retained Topic handles
177 are canonicalized, including after default-type identity merging."
178 (check-type value string)
179 (let* ((topic (live-topic topic)) (map (%topic-parent topic))
180 (scope (canonical-scope map scope))
181 (type (when type-supplied-p (live-topic type))))
182 (when (and type-supplied-p (not (eq map (%topic-parent type))))
183 (error "Name type belongs to another map."))
184 (unless type-supplied-p
185 (setf type (intern-topic map :subject-identifier (default-name-type-identifier))))
186 (let* ((topic (canonical-topic topic)) (type (canonical-topic type))
187 (scope (canonical-scope map scope))
188 (existing (find-if (lambda (name)
189 (and (string= value (%topic-name-value name))
190 (eq type (%topic-name-type name))
191 (same-scope-p scope (%topic-name-scope name))))
192 (%topic-names topic))))
193 (or existing
194 (let ((name (%make-topic-name value type topic)))
195 (setf (%topic-name-scope name) scope
196 (%topic-names topic) (append (%topic-names topic) (list name)))
197 name)))))
198
199 (defun add-default-name (topic value &key scope)
200 "Compatibility entry point for ADD-NAME with the CTM 3.11 default type."
201 (add-name topic value :scope scope))