]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - tests/normalization-index.lisp
docs: design draft for a read-only SHOP3 adapter over TMDM objects
[topic-maps.git] / tests / normalization-index.lisp
1 (defpackage #:topic-maps.normalization-index.tests
2 (:use #:cl #:topic-maps.tmdm)
3 (:import-from #:topic-maps.ctm.tests #:check #:cxtm)
4 (:import-from #:topic-maps.variant.tests #:condition-from)
5 (:import-from #:topic-maps.identifier.tests #:si #:current)
6 (:export #:run-tests #:normalization-index-checks #:record-expected))
7 (in-package #:topic-maps.normalization-index.tests)
8
9 ;;; Which Topics merge next, and the results that must not change while the search for them changes.
10 ;;; The expected CXTM of every case and the class and code of every rejection were recorded from the
11 ;;; unchanged implementation at b2eecffa (RECORD-EXPECTED) before NEXT-TOPIC-MERGE existed; they are not
12 ;;; derived from the implementation under test. SCAN-NEXT-TOPIC-MERGE is the b2eecffa search, kept as the
13 ;;; fallback and used here as the oracle.
14
15 (defvar *last-checks* nil)
16 (defun normalization-index-checks () *last-checks*)
17 (defparameter +document+ "https://example.invalid/n/doc.ctm")
18 (defvar *fixture-directory* nil)
19 (defun fixture-directory ()
20 (or *fixture-directory* (asdf:system-relative-pathname "topic-maps" "tests/fixtures/normalization-index/")))
21 (defun read-case (text) (topic-maps.ctm:deserialize-string text :document-iri +document+ :source-name "normalization-index"))
22 (defun pick (random sequence) (elt sequence (random (length sequence) random)))
23
24 (defun chain-document (topics links)
25 "TOPICS Topics with one subject identifier each and a Name, LINKS later statements that give Topic 2I the
26 item identifier equal to the subject identifier of Topic 2I+1, and one Association per Topic."
27 (with-output-to-string (s)
28 (dotimes (i topics) (format s "t~D http://example.org/s/~D ; - \"Topic ~D\" .~%" i i i))
29 (dotimes (i topics) (format s "rel~D(from: t~D, to: t~D)~%" (mod i 5) i (mod (* 7 (1+ i)) topics)))
30 (dotimes (i links) (format s "t~D ^ http://example.org/s/~D .~%" (* 2 i) (1+ (* 2 i))))))
31
32 ;;; Reifiers: the corpus has 57 reified Associations, each reifier Topic named in its own statement.
33
34 (defun reified-document (associations &key (duplicate-every 0))
35 "ASSOCIATIONS reified Associations, each reifier Topic with a subject identifier and a Name. Every
36 DUPLICATE-EVERYth Association is stated a second time with a second reifier Topic: the two Associations are
37 equal, so their reifier Topics merge although nothing else identifies them."
38 (with-output-to-string (s)
39 (dotimes (i associations)
40 (format s "p~D http://example.org/p/~D ; - \"P ~D\" .~%" i i i)
41 (format s "r~D http://example.org/r/~D ; - \"R ~D\" .~%" i i i)
42 (format s "rel~D(from: p~D, to: p~D) ~~ r~D~%" (mod i 4) i (mod (* 5 (1+ i)) associations) i))
43 (when (plusp duplicate-every)
44 (loop for i from 0 below associations by duplicate-every
45 do (format s "q~D http://example.org/q/~D ; - \"Q ~D\" .~%" i i i)
46 (format s "rel~D(from: p~D, to: p~D) ~~ q~D~%" (mod i 4) i (mod (* 5 (1+ i)) associations) i)))))
47
48 ;;; Documents whose result must not change, and the nonconflicting-reifier merges among them
49
50 (defparameter *documents*
51 `(("identifier-acquisition" ,(format nil "a - \"A\" .~%b - \"B\" .~%a ^ https://example.invalid/n/doc.ctm#b ."))
52 ("ii-si-cross-identity" ,(format nil "x http://example.org/s .~%y ^ http://example.org/s ."))
53 ("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 ."))
54 ("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 ."))
55 ("subject-locator-merge" ,(format nil "s1 = http://example.org/doc .~%s2 = http://example.org/doc ."))
56 ("si-and-sl-stay-apart" ,(format nil "t1 http://example.org/z .~%t2 = http://example.org/z ."))
57 ("reified-duplicate-associations" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%x - \"X\" .~%y - \"Y\" ."))
58 ("reified-duplicate-names" ,(format nil "n - \"N\" ~~ nr .~%n - \"N\" ~~ nr2 ."))
59 ("topic-map-reifier" ,(format nil "~~ mapr~%mapr - \"M\" ."))
60 ("reifier-merges-by-identifier" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ y~%y ^ https://example.invalid/n/doc.ctm#z .~%z - \"Z\" ."))
61 ("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"))
62 ("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 ."))
63 ("equal-reifiers-of-equal-items" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%x ^ https://example.invalid/n/doc.ctm#y ."))
64 ("isa-ako" ,(format nil "a isa b .~%b ako c .~%d isa b .~%e isa c ."))
65 ("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 ."))
66 ("n-ary-duplicate-roles" "t(r1: a, r2: b, r3: c, r1: a)")
67 ("wildcard-merge" "?foo . ?foo .")
68 ("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 ."))
69 ("chain-40-topics" ,(chain-document 40 12))
70 ("reified-30-associations" ,(reified-document 30))
71 ("reified-30-associations-merging-reifiers" ,(reified-document 30 :duplicate-every 3)))
72 "CTM documents whose CXTM is recorded.")
73
74 ;;; The staged-import scenarios behind the nonconflicting-reifier preference: the Reifier Topics precede
75 ;;; the owners and Types in both maps, and the reified Names become equal only after those Topics merge.
76
77 (defun import-outcome (build)
78 (multiple-value-bind (target source) (funcall build)
79 (import-map-content target source)
80 (cxtm target +document+)))
81
82 (defun scenario-reifier-first ()
83 (let* ((target (make-topic-map)) (source (make-topic-map))
84 (r (si target "r")) (s (si source "r")) (a (si target "owner")) (b (si source "owner"))
85 (ty (si target "type")) (sy (si source "type")) (n (add-name a "N" :type ty)) (m (add-name b "N" :type sy)))
86 (set-item-reifier n r) (set-item-reifier m s)
87 (values target source)))
88
89 (defun scenario-cascade ()
90 ;; Equal Names merge their Reifiers, which are themselves types, players and themes of further items.
91 (let* ((target (make-topic-map)) (source (make-topic-map)) (a (si target "owner")) (b (si source "owner"))
92 (ty (si target "name-type")) (sy (si source "name-type")) (r (si target "r")) (s (si source "s"))
93 (n (add-name a "N" :type ty)) (m (add-name b "N" :type sy)))
94 (add-occurrence r r "O" :scope (list r)) (add-occurrence s s "O" :scope (list s))
95 (make-association target r (list (list r r)) :scope (list r)) (make-association source s (list (list s s)) :scope (list s))
96 (set-item-reifier n r) (set-item-reifier m s)
97 (values target source)))
98
99 (defun scenario-reifier-chain ()
100 ;; Three levels: the Reifiers of equal Names are the owners of further equal Names with their own Reifiers.
101 (let* ((target (make-topic-map)) (source (make-topic-map)) (a (si target "owner")) (b (si source "owner"))
102 (ty (si target "type")) (sy (si source "type")) (r (si target "r")) (s (si source "s"))
103 (r2 (si target "r2")) (s2 (si source "s2"))
104 (n (add-name a "N" :type ty)) (m (add-name b "N" :type sy))
105 (k (add-name r "K" :type ty)) (l (add-name s "K" :type sy)))
106 (set-item-reifier n r) (set-item-reifier m s) (set-item-reifier k r2) (set-item-reifier l s2)
107 (values target source)))
108
109 (defparameter *scenarios*
110 '(("import-reifier-first" scenario-reifier-first) ("import-cascade" scenario-cascade)
111 ("import-reifier-chain" scenario-reifier-chain))
112 "Staged imports whose resulting CXTM is recorded.")
113
114 ;;; Rejections: conflict signalling and preflight rejection must stay as recorded
115
116 (defparameter *rejections*
117 `(("reifier-reifies-two-items" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ x"))
118 ("reifier-merge-conflict" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ y~%x ^ https://example.invalid/n/doc.ctm#y ."))
119 ("core-subject-conflict" ,(format nil "a http://psi.topicmaps.org/iso13250/model/type .~%a http://psi.topicmaps.org/iso13250/model/instance ."))
120 ("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 ."))
121 ("unclosed-association" "a(r: b"))
122 "CTM documents whose rejection is recorded as condition class and code.")
123
124 (defun rejecting-scenario-reifier-conflict ()
125 (let* ((target (make-topic-map)) (source (make-topic-map)) (a (si target "owner")) (b (si source "owner"))
126 (ty (si target "type")) (sy (si source "type")) (r (si target "r")) (s (si source "r")))
127 (set-item-reifier (add-name a "Different" :type ty) r) (set-item-reifier (add-name b "Name" :type sy) s)
128 (values target source)))
129
130 (defun rejecting-scenario-retained-root-reifier ()
131 (let* ((target (make-topic-map)) (source (make-topic-map)) (r (si target "r")) (s (si source "r")) (owner (si source "owner")))
132 (set-item-reifier target r) (set-item-reifier (add-default-name owner "N") s)
133 (values target source)))
134
135 (defparameter *rejecting-scenarios*
136 '(("import-reifier-conflict" rejecting-scenario-reifier-conflict)
137 ("import-retained-root-reifier" rejecting-scenario-retained-root-reifier)))
138
139 (defun condition-code (c)
140 (cond ((typep c 'topic-maps.ctm:ctm-error) (topic-maps.ctm:error-code c))
141 ((typep c 'reification-error) (reification-error-code c))
142 ((typep c 'core-subject-error) (core-subject-error-code c))
143 ((typep c 'map-import-error) (map-import-error-code c))
144 (t nil)))
145
146 (defun outcome (thunk)
147 (handler-case (list :read (funcall thunk))
148 (error (c) (list :refused (type-of c) (condition-code c)))))
149
150 (defun document-outcome (text) (outcome (lambda () (cxtm (read-case text) +document+))))
151
152 (defun record-expected ()
153 "Write the expected outcomes with the implementation now loaded. Run once, at b2eecffa."
154 (ensure-directories-exist (fixture-directory))
155 (flet ((record (name value)
156 (with-open-file (out (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory))
157 :direction :output :if-exists :supersede :external-format :utf-8)
158 (write-string value out))))
159 (dolist (case *documents*)
160 (destructuring-bind (kind value &rest rest) (document-outcome (second case))
161 (declare (ignore rest))
162 (unless (eq kind :read) (error "Case ~A was refused: ~S" (first case) value))
163 (record (first case) value)))
164 (dolist (case *scenarios*)
165 (destructuring-bind (kind value &rest rest) (outcome (lambda () (import-outcome (symbol-function (second case)))))
166 (declare (ignore rest))
167 (unless (eq kind :read) (error "Scenario ~A was refused: ~S" (first case) value))
168 (record (first case) value))))
169 (with-open-file (out (merge-pathnames "rejections.sexp" (fixture-directory)) :direction :output :if-exists :supersede)
170 (let ((*package* (find-package "KEYWORD")))
171 (dolist (case *rejections*)
172 (prin1 (cons (first case) (rest (document-outcome (second case)))) out) (terpri out))
173 (dolist (case *rejecting-scenarios*)
174 (prin1 (cons (first case) (rest (outcome (lambda () (import-outcome (symbol-function (second case))))))) out) (terpri out)))))
175
176 (defun expected-cxtm (name)
177 (uiop:read-file-string (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory)) :external-format :utf-8))
178 (defun expected-rejections ()
179 (with-open-file (in (merge-pathnames "rejections.sexp" (fixture-directory)))
180 (let ((*read-eval* nil)) (loop for form = (read in nil) while form collect form))))
181
182 (defun recorded-outcome-tests ()
183 (dolist (case *documents*)
184 (let ((o (document-outcome (second case))))
185 (check (format nil "document:~A:read" (first case)) (eq :read (first o)))
186 (check (format nil "document:~A:cxtm-equals-b2eecffa" (first case)) (string= (second o) (expected-cxtm (first case))))))
187 (dolist (case *scenarios*)
188 (let ((o (outcome (lambda () (import-outcome (symbol-function (second case)))))))
189 (check (format nil "scenario:~A:cxtm-equals-b2eecffa" (first case))
190 (and (eq :read (first o)) (string= (second o) (expected-cxtm (first case)))))))
191 (let ((expected (expected-rejections)))
192 (flet ((same (name o)
193 (let ((recorded (rest (assoc name expected :test #'string=))))
194 (check (format nil "rejection:~A:recorded" name) recorded)
195 (check (format nil "rejection:~A:class-and-code-equal-b2eecffa" name) (equal (rest o) recorded)))))
196 (dolist (case *rejections*) (same (first case) (document-outcome (second case))))
197 (dolist (case *rejecting-scenarios*)
198 (same (first case) (outcome (lambda () (import-outcome (symbol-function (second case))))))))))
199
200 ;;; Semantics that no recorded text shows: canonical representatives, retained handles, reifier preference
201
202 (defun live-p (topic map) (member topic (topic-map-topics map) :test #'eq))
203
204 (defun handle-tests (with-reifier)
205 (let* ((map (make-topic-map)) (label (if with-reifier "with-reifier" "plain"))
206 (a (si map "a")) (b (si map "b")) (c (intern-topic map :item-identifier "urn:c")) (other (si map "other")))
207 (when with-reifier
208 (set-item-reifier (make-association map other (list (list other a))) (si map "reifier")))
209 (add-topic-identifier c :item-identifier "urn:a")
210 (check (format nil "handles:~A:c-merged-with-a" label) (eq (canonical-topic a) (canonical-topic c)))
211 (check (format nil "handles:~A:b-still-apart" label) (not (eq (canonical-topic a) (canonical-topic b))))
212 (add-topic-identifier c :subject-identifier "urn:b")
213 (let ((merged (canonical-topic a)))
214 (check (format nil "handles:~A:transitive-one-topic" label)
215 (and (eq merged (canonical-topic b)) (eq merged (canonical-topic c))))
216 (check (format nil "handles:~A:representative-is-live" label) (live-p merged map))
217 (check (format nil "handles:~A:obsolete-handles-are-not-live-and-forward" label)
218 (every (lambda (h) (or (eq h merged) (and (not (live-p h map)) (eq merged (canonical-topic h))))) (list a b c)))
219 (check (format nil "handles:~A:other-untouched" label) (eq other (canonical-topic other)))
220 (check (format nil "handles:~A:model-valid" label)
221 (and (topic-maps.tmdm::validate-map-item-identifiers map) (topic-maps.tmdm::validate-map-reification map))))))
222
223 (defun representative-tests ()
224 ;; Three Topics become one; the representative takes the place of the first of them, whatever the order of merging.
225 (let* ((map (make-topic-map)) (x (si map "x")) (a (si map "a")) (b (si map "b")) (y (si map "y"))
226 (c (intern-topic map :item-identifier "urn:c")))
227 (add-topic-identifier c :subject-identifier "urn:a") (add-topic-identifier c :subject-identifier "urn:b")
228 (let ((merged (canonical-topic a)))
229 (check "representative:one-topic-for-three-handles" (and (eq merged (canonical-topic b)) (eq merged (canonical-topic c))))
230 (check "representative:replaces-the-first-merged-topic-in-place"
231 (equal (list x merged y) (topic-map-topics map))))))
232
233 (defun reifier-preference-tests ()
234 ;; Staged: the reifier Topics are equal (same subject identifier) but reify items that become equal only after
235 ;; their owners and types merge. The owners and types merge first; the reifiers then merge without conflict.
236 (multiple-value-bind (target source) (scenario-reifier-first)
237 (let ((r (si target "r")) (n (first (topic-names (si target "owner")))))
238 (multiple-value-bind (map resolve) (import-map-content target source)
239 (let ((s (si source "r")))
240 (check "preference:reifier-topics-merge-after-their-owners" (eq (canonical-topic r) (funcall resolve s)))
241 (check "preference:one-name-one-reifier"
242 (let ((names (topic-names (current (si map "owner")))))
243 (and (= 1 (length names)) (eq (canonical-topic r) (item-reifier (first names)))
244 (eq (canonical-topic-name n) (first names)))))
245 (check "preference:inverse-is-consistent" (eq (canonical-topic-name n) (topic-reified (canonical-topic r))))
246 (check "preference:model-valid" (topic-maps.tmdm::validate-map-reification map))))))
247 ;; The conflict itself is still signalled when no nonconflicting merge is available, before any mutation.
248 (multiple-value-bind (target source) (rejecting-scenario-reifier-conflict)
249 (let* ((before (topic-maps.ctm.tests::map-state target)) (c (condition-from (lambda () (import-map-content target source)))))
250 (check "preference:conflict-still-signalled" (and (typep c 'reification-error) (eq :reifier-conflict (reification-error-code c))))
251 (check "preference:conflict-leaves-the-target-unchanged" (equal before (topic-maps.ctm.tests::map-state target))))))
252
253 ;;; The search itself, against the b2eecffa search on unnormalized maps
254
255 (defun random-map (random topics)
256 "An unnormalized Map: TOPICS raw Topics with identifiers from small pools (so equal Topics are frequent), raw
257 Associations and Names, and Reifiers set directly. Reifier Topics are often equal to each other while the items
258 they reify differ, which is the case the nonconflicting preference exists for. Sometimes one Topic reifies two
259 items (the fallback). Nothing is merged."
260 (let* ((map (make-topic-map)) (single (not (zerop (random 4 random))))
261 (made (loop repeat topics collect (topic-maps.tmdm::%make-topic map))))
262 (flet ((pool (prefix n) (format nil "http://example.org/~A/~D" prefix (random n random))))
263 (setf (topic-maps.tmdm::%topic-map-topics map) made)
264 (dolist (topic made)
265 (dotimes (k (random 3 random)) (push (pool "id" (* 2 topics)) (topic-maps.tmdm::%topic-item-identifiers topic)))
266 (dotimes (k (random 2 random)) (push (pool "id" (* 2 topics)) (topic-maps.tmdm::%topic-subject-identifiers topic)))
267 (when (zerop (random 4 random)) (push (pool "id" (* 2 topics)) (topic-maps.tmdm::%topic-subject-locators topic))))
268 (let ((items nil))
269 (dotimes (k (random 5 random))
270 (let* ((type (pick random made)) (association (topic-maps.tmdm::%make-association map type)))
271 (setf (topic-maps.tmdm::%association-roles association)
272 (list (topic-maps.tmdm::%make-association-role association type (pick random made))))
273 (push association (topic-maps.tmdm::%topic-map-associations map))
274 (push association items)))
275 (dotimes (k (random 4 random))
276 (let* ((owner (pick random made)) (name (topic-maps.tmdm::%make-topic-name (format nil "n~D" k) owner owner)))
277 (push name (topic-maps.tmdm::%topic-names owner))
278 (push name items)))
279 (when (zerop (random 5 random)) (push map items))
280 (let ((unused (copy-list made)))
281 (dolist (item items)
282 (when (zerop (random 3 random))
283 ;; single reifiers: each Topic reifies at most one item; otherwise any Topic may be taken again
284 (let ((reifier (if single
285 (and unused (let ((r (pick random unused))) (setf unused (remove r unused)) r))
286 (pick random made))))
287 (when reifier (setf (topic-maps.tmdm::%item-reifier item) reifier))))))
288 ;; two Topics that reify items now share an identifier: equal Reifiers of (usually) different items
289 (let ((reifiers (remove-duplicates (loop for item in items for r = (topic-maps.tmdm::%item-reifier item) when r collect r))))
290 (when (and (rest reifiers) (zerop (random 2 random)))
291 (let ((iri (pool "reifier" topics)))
292 (push iri (topic-maps.tmdm::%topic-subject-identifiers (first reifiers)))
293 (push iri (topic-maps.tmdm::%topic-subject-identifiers (pick random (rest reifiers)))))))))
294 map))
295
296 (defun selection (thunk)
297 (handler-case (list :pair (let ((pair (funcall thunk))) (and pair (mapcar #'position-of-topic pair))))
298 (reification-error (c) (list :refused (reification-error-code c)))))
299 (defvar *topics-in-order* nil)
300 (defun position-of-topic (topic) (position topic *topics-in-order* :test #'eq))
301
302 (defun differs-from-first-pair-p (map)
303 "True when the oracle's choice is not simply the first equal pair: a nonconflicting pair was preferred."
304 (let ((first-pair (ignore-errors (topic-maps.tmdm::equal-pair (topic-maps.tmdm::%topic-map-topics map)
305 #'topic-maps.tmdm::equal-topics-p)))
306 (chosen (ignore-errors (topic-maps.tmdm::scan-next-topic-merge map))))
307 (and first-pair chosen (not (equal first-pair chosen)))))
308
309 (defun selection-equivalence-tests (&key (maps 4000) (seed 20261027))
310 (let ((random (sb-ext:seed-random-state seed)) (pairs 0) (none 0) (refused 0) (preferred 0) (differences 0))
311 (dotimes (n maps)
312 (let* ((map (random-map random (+ 2 (random 14 random))))
313 (*topics-in-order* (topic-maps.tmdm::%topic-map-topics map))
314 (indexed (selection (lambda () (topic-maps.tmdm::next-topic-merge map))))
315 (oracle (selection (lambda () (topic-maps.tmdm::scan-next-topic-merge map)))))
316 (cond ((not (equal indexed oracle)) (incf differences))
317 ((eq :refused (first oracle)) (incf refused))
318 ((second oracle) (incf pairs) (when (differs-from-first-pair-p map) (incf preferred)))
319 (t (incf none)))))
320 (check "selection:indexed-equals-oracle-on-every-map" (zerop differences))
321 (check "selection:maps-with-a-pair-exercised" (> pairs (floor maps 4)))
322 (check "selection:maps-without-a-pair-exercised" (> none 0))
323 (check "selection:nonconflicting-preference-exercised" (> preferred (floor maps 50)))
324 (check "selection:fallback-exercised" (> refused (floor maps 100)))
325 (list :maps maps :pair pairs :none none :preferred preferred :refused refused :differences differences)))
326
327 ;;; Invalidation: the index lives for one search. After every mutation the search starts again from the map.
328
329 (defun merge-walk (random topics)
330 "Follow normalization on a random unnormalized Map: at every step the indexed and the oracle search must agree,
331 then the oracle's pair is merged exactly as NORMALIZE-TOPIC-MAP does. Returns the number of steps and how the walk ended."
332 (let ((map (random-map random topics)) (steps 0))
333 (loop
334 (let* ((*topics-in-order* (topic-maps.tmdm::%topic-map-topics map))
335 (indexed (selection (lambda () (topic-maps.tmdm::next-topic-merge map))))
336 (oracle (selection (lambda () (topic-maps.tmdm::scan-next-topic-merge map)))))
337 (unless (equal indexed oracle) (return (values steps :differs)))
338 (unless (and (eq :pair (first oracle)) (second oracle)) (return (values steps (if (eq :refused (first oracle)) :refused :done))))
339 (let ((pair (topic-maps.tmdm::scan-next-topic-merge map)))
340 (handler-case (topic-maps.tmdm::merge-two-topics map (first pair) (second pair))
341 (error () (return (values steps :merge-refused))))
342 (incf steps))))))
343
344 (defun invalidation-tests (&key (walks 800) (seed 20261028))
345 (let ((random (sb-ext:seed-random-state seed)) (steps 0) (differs 0) (done 0) (multi-step 0))
346 (dotimes (n walks)
347 (multiple-value-bind (count how) (merge-walk random (+ 3 (random 12 random)))
348 (incf steps count)
349 (when (> count 1) (incf multi-step))
350 (case how (:differs (incf differs)) (:done (incf done)))))
351 (check "invalidation:agrees-after-every-merge-step" (zerop differs))
352 (check "invalidation:walks-with-several-merges-exercised" (> multi-step (floor walks 10)))
353 (check "invalidation:walks-reaching-a-fixed-point-exercised" (> done (floor walks 4)))
354 (list :walks walks :merge-steps steps :several-merges multi-step :fixed-point done :differences differs)))
355
356 (defun stale-reference-tests ()
357 ;; A pair found before a merge names Topics that are no longer live; the search after the merge never returns them.
358 (let* ((map (make-topic-map)) (a (si map "a")) (b (si map "b")) (c (si map "c")))
359 ;; make a~b and b~c equal without normalizing: raw identifiers, as an unnormalized staged map has them
360 (push "urn:ab" (topic-maps.tmdm::%topic-subject-identifiers a)) (push "urn:ab" (topic-maps.tmdm::%topic-item-identifiers b))
361 (push "urn:bc" (topic-maps.tmdm::%topic-subject-identifiers b)) (push "urn:bc" (topic-maps.tmdm::%topic-subject-identifiers c))
362 (let ((before (topic-maps.tmdm::next-topic-merge map)))
363 (check "stale:pair-found-before-the-merge" (equal (list a b) before))
364 (topic-maps.tmdm::merge-two-topics map a b)
365 (let ((after (topic-maps.tmdm::next-topic-merge map)) (merged (canonical-topic a)))
366 (check "stale:positive-control-old-handles-are-no-longer-live" (and (not (live-p a map)) (not (live-p b map))))
367 (check "stale:old-handles-forward-to-the-representative" (and (eq merged (canonical-topic a)) (eq merged (canonical-topic b))))
368 (check "stale:search-after-the-merge-names-live-topics-only" (every (lambda (tpc) (live-p tpc map)) after))
369 (check "stale:search-after-the-merge-finds-the-next-pair" (equal (list merged c) after))
370 (check "stale:search-agrees-with-the-oracle" (equal after (topic-maps.tmdm::scan-next-topic-merge map)))))))
371
372 (defun reifier-mutation-tests ()
373 ;; The reification inverse changes between searches (set, replace, clear); no search may use an earlier state.
374 ;; The reifier Topics r, s precede the owners a, b, so the first equal pair is the reifiers' as soon as they are equal.
375 (let* ((map (make-topic-map)) (r (si map "r")) (s (si map "s")) (a (si map "a")) (b (si map "b"))
376 (x (add-name a "X" :type r)) (y (add-name b "Y" :type r)))
377 (flet ((result (function)
378 (handler-case (funcall function map) (reification-error (c) (list :refused (reification-error-code c)))))
379 (sid (topic iri) (push iri (topic-maps.tmdm::%topic-subject-identifiers topic))))
380 (flet ((agree (label)
381 (check (concatenate 'string "reifier-mutation:" label)
382 (equal (result #'topic-maps.tmdm::next-topic-merge) (result #'topic-maps.tmdm::scan-next-topic-merge)))))
383 (sid a "urn:ab") (sid b "urn:ab")
384 (agree "equal-owners-no-reifier")
385 (setf (topic-maps.tmdm::%item-reifier x) r (topic-maps.tmdm::%item-reifier y) s)
386 (agree "reifiers-of-different-items-not-equal")
387 (sid r "urn:rs") (sid s "urn:rs")
388 (check "reifier-mutation:preferred-pair-skips-the-conflicting-reifiers"
389 (equal (list a b) (topic-maps.tmdm::next-topic-merge map)))
390 (check "reifier-mutation:the-first-equal-pair-is-the-conflicting-one"
391 (equal (list r s) (topic-maps.tmdm::equal-pair (topic-map-topics map) #'topic-maps.tmdm::equal-topics-p)))
392 (agree "equal-reifiers-of-different-items")
393 (setf (topic-maps.tmdm::%item-reifier y) nil)
394 (check "reifier-mutation:one-side-cleared-makes-the-reifiers-mergeable"
395 (equal (list r s) (topic-maps.tmdm::next-topic-merge map)))
396 (agree "one-reifier-cleared")
397 (setf (topic-maps.tmdm::%item-reifier y) r)
398 (check "reifier-mutation:one-topic-reifying-two-items-is-the-recorded-conflict"
399 (equal '(:refused :reifier-conflict) (result #'topic-maps.tmdm::next-topic-merge)))
400 (agree "one-topic-reifying-two-items-falls-back")))))
401
402 (defun stale-listed-topic-tests ()
403 ;; Not reachable through the public API: a Topic that was replaced but is still listed. TOPIC-REIFIED resolves
404 ;; it to its representative, so the pairwise search finds the pair although no identifier is shared; the index,
405 ;; which would not, must not be trusted here.
406 (let* ((map (make-topic-map)) (a (si map "a")) (b (si map "b")) (owner (si map "owner"))
407 (name (add-name owner "N" :type a)))
408 (setf (topic-maps.tmdm::%item-reifier name) a (topic-maps.tmdm::%topic-forward b) a)
409 (check "stale-listed:pairwise-search-finds-the-replaced-topic-equal-to-its-representative"
410 (equal (list a b) (topic-maps.tmdm::scan-next-topic-merge map)))
411 (check "stale-listed:indexed-search-defers-to-it" (equal (list a b) (topic-maps.tmdm::next-topic-merge map)))))
412
413 ;;; Whole reads: indexed and oracle searches run the same normalization to the same result
414
415 (defun random-document (random)
416 "A CTM document with identifier statements from small pools, reified Names and Associations."
417 (let ((tops (+ 3 (random 7 random))))
418 (with-output-to-string (s)
419 (flet ((topic () (format nil "t~D" (random tops random))) (iri (kind) (format nil "http://example.org/~A/~D" kind (random (* 2 tops) random))))
420 (dotimes (i (+ 4 (random 14 random)))
421 (ecase (random 8 random)
422 (0 (format s "~A ~A .~%" (topic) (iri "i")))
423 (1 (format s "~A ^ ~A .~%" (topic) (iri "i")))
424 (2 (format s "~A = ~A .~%" (topic) (iri "l")))
425 (3 (format s "~A - \"n~D\" .~%" (topic) (random 2 random)))
426 (4 (format s "~A - \"n~D\" ~~ ~A .~%" (topic) (random 2 random) (topic)))
427 (5 (format s "rel~D(r: ~A, q: ~A)~%" (random 2 random) (topic) (topic)))
428 (6 (format s "rel~D(r: ~A, q: ~A) ~~ ~A~%" (random 2 random) (topic) (topic) (topic)))
429 (7 (format s "~A ^ https://example.invalid/n/doc.ctm#~A .~%" (topic) (topic)))))))))
430
431 (defmacro with-oracle-search (&body body)
432 `(progn
433 (sb-int:encapsulate 'topic-maps.tmdm::next-topic-merge :oracle
434 (lambda (original map) (declare (ignore original)) (topic-maps.tmdm::scan-next-topic-merge map)))
435 (unwind-protect (progn ,@body) (sb-int:unencapsulate 'topic-maps.tmdm::next-topic-merge :oracle))))
436
437 (defun counting-merges (thunk)
438 "The outcome of THUNK and how many Topic merges it performed."
439 (let ((merges 0))
440 (sb-int:encapsulate 'topic-maps.tmdm::merge-two-topics :count
441 (lambda (original &rest arguments) (incf merges) (apply original arguments)))
442 (unwind-protect (values (funcall thunk) (progn merges))
443 (sb-int:unencapsulate 'topic-maps.tmdm::merge-two-topics :count))))
444
445 (defun reads-equal-tests (&key (documents 400) (seed 20261029))
446 (let ((random (sb-ext:seed-random-state seed)) (read 0) (refused 0) (differences 0) (merging 0) (merges 0) (reified 0))
447 (dotimes (n documents)
448 (let ((text (random-document random)))
449 (multiple-value-bind (indexed indexed-merges) (counting-merges (lambda () (document-outcome text)))
450 (multiple-value-bind (oracle oracle-merges)
451 (with-oracle-search (counting-merges (lambda () (document-outcome text))))
452 (cond ((or (not (equal indexed oracle)) (/= indexed-merges oracle-merges)) (incf differences))
453 (t (incf merges indexed-merges)
454 (when (plusp indexed-merges) (incf merging))
455 (cond ((eq :read (first oracle))
456 (incf read)
457 (when (search "reifier=" (second oracle)) (incf reified)))
458 (t (incf refused)))))))))
459 (check "reads:indexed-equals-oracle-on-every-document" (zerop differences))
460 (check "reads:documents-read-exercised" (> read (floor documents 2)))
461 (check "reads:refusals-exercised" (> refused 0))
462 (check "reads:merging-documents-exercised" (> merging (floor documents 4)))
463 (check "reads:reified-documents-exercised" (> reified (floor documents 20)))
464 (list :documents documents :read read :refused refused :merging merging :merges merges :reified reified :differences differences)))
465
466 (defun positive-control-for-preference ()
467 ;; The comparisons above can tell a search without the preference from the real one: always taking the first
468 ;; equal pair refuses the staged import that the preference reads.
469 (let ((first-pair-only (lambda (original map) (declare (ignore original))
470 (topic-maps.tmdm::equal-pair (topic-maps.tmdm::%topic-map-topics map) #'topic-maps.tmdm::equal-topics-p)))
471 (staged (lambda () (import-outcome #'scenario-reifier-first))))
472 (check "control:preferring-search-imports-the-staged-maps" (eq :read (first (outcome staged))))
473 (sb-int:encapsulate 'topic-maps.tmdm::next-topic-merge :control first-pair-only)
474 (unwind-protect (check "control:first-pair-search-refuses-them-with-a-reifier-conflict"
475 (equal '(:refused reification-error :reifier-conflict) (outcome staged)))
476 (sb-int:unencapsulate 'topic-maps.tmdm::next-topic-merge :control))))
477
478 ;;; Scale: documents of the size the reader was too slow for, read within a stated budget
479
480 (defun seconds-to (thunk)
481 (let ((start (get-internal-real-time)))
482 (values (funcall thunk) (float (/ (- (get-internal-real-time) start) internal-time-units-per-second) 1d0))))
483
484 (defun scale-tests (&key (topics 300) (associations 120) (budget 60))
485 (multiple-value-bind (map seconds) (seconds-to (lambda () (read-case (chain-document topics (floor topics 4)))))
486 (check "scale:chain-read" (= (+ topics 5 2 1 (- (floor topics 4))) (length (topic-map-topics map))))
487 (check "scale:chain-associations" (= topics (length (topic-map-associations map))))
488 (check (format nil "scale:chain-within-~Ds" budget) (< seconds budget))
489 (let ((plain (read-case (reified-document associations))))
490 (multiple-value-bind (map reified-seconds) (seconds-to (lambda () (read-case (reified-document associations :duplicate-every 3))))
491 (check "scale:reified-associations" (and (= associations (length (topic-map-associations map)))
492 (= associations (length (topic-map-associations plain)))))
493 (check "scale:duplicate-reifier-topics-merged-into-the-first" (= (length (topic-map-topics plain)) (length (topic-map-topics map))))
494 (check "scale:every-association-keeps-its-reifier" (every #'item-reifier (topic-map-associations map)))
495 (check (format nil "scale:reified-within-~Ds" budget) (< reified-seconds budget))
496 (list :chain seconds :reified reified-seconds)))))
497
498 (defun run-tests ()
499 (let ((topic-maps.ctm.tests::*checks* nil) (search nil) (walks nil) (reads nil) (seconds nil))
500 (recorded-outcome-tests)
501 (handle-tests nil)
502 (handle-tests t)
503 (representative-tests)
504 (reifier-preference-tests)
505 (stale-reference-tests)
506 (stale-listed-topic-tests)
507 (reifier-mutation-tests)
508 (setf search (selection-equivalence-tests) walks (invalidation-tests) reads (reads-equal-tests))
509 (positive-control-for-preference)
510 (setf seconds (scale-tests))
511 (format t "~&NORMALIZATION-INDEX-SELECTION: ~S~%NORMALIZATION-INDEX-WALKS: ~S~%NORMALIZATION-INDEX-READS: ~S~%NORMALIZATION-INDEX-SCALE: ~S~%"
512 search walks reads seconds)
513 (setf *last-checks* (reverse topic-maps.ctm.tests::*checks*))
514 (format t "~&NORMALIZATION-INDEX-PASS: ~D checks; ~D documents, ~D staged imports and ~D rejections equal to the outcomes recorded at b2eecffa.~%"
515 (length *last-checks*) (length *documents*) (length *scenarios*) (+ (length *rejections*) (length *rejecting-scenarios*)))
516 *last-checks*))