]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - tests/association-index.lisp
feat(tmdm): readers for the TMDM 7.2/7.3 relationships; tests for both default name...
[topic-maps.git] / tests / association-index.lisp
1 (defpackage #:topic-maps.association-index.tests
2 (:use #:cl #:topic-maps.tmdm)
3 (:import-from #:topic-maps.ctm.tests #:check #:cxtm)
4 (:import-from #:topic-maps.identifier.tests #:si)
5 (:export #:run-tests #:association-index-checks #:record-expected #:with-shadow-search #:shadow-report))
6 (in-package #:topic-maps.association-index.tests)
7
8 ;;; Which Associations merge next, and the results that must not change while the search for them changes.
9 ;;; The expected CXTM of every case, the facts of every API scenario and the class and code of every rejection
10 ;;; were recorded from the unchanged implementation at 6162ed68 (RECORD-EXPECTED) before NEXT-ASSOCIATION-MERGE
11 ;;; existed; they are not derived from the implementation under test. SCAN-NEXT-ASSOCIATION-MERGE is the 6162ed68
12 ;;; search, kept as the fallback and used here as the oracle.
13
14 (defvar *last-checks* nil)
15 (defun association-index-checks () *last-checks*)
16 (defparameter +document+ "https://example.invalid/a/doc.ctm")
17 (defvar *fixture-directory* nil)
18 (defun fixture-directory ()
19 (or *fixture-directory* (asdf:system-relative-pathname "topic-maps" "tests/fixtures/association-index/")))
20 (defun read-case (text) (topic-maps.ctm:deserialize-string text :document-iri +document+ :source-name "association-index"))
21 (defun pick (random sequence) (elt sequence (random (length sequence) random)))
22 (defun ii (name) (format nil "~A#~A" +document+ name))
23
24 ;;; Documents whose result must not change
25
26 (defun same-type-document (associations duplicate-every)
27 "ASSOCIATIONS Associations of one type with distinct players; every DUPLICATE-EVERYth is stated twice."
28 (with-output-to-string (s)
29 (dotimes (i associations)
30 (format s "t(r: p~D, q: o~D)~%" i (mod i 7))
31 (when (and (plusp duplicate-every) (zerop (mod i duplicate-every))) (format s "t(q: o~D, r: p~D)~%" (mod i 7) i)))))
32
33 (defparameter *documents*
34 `(("plain-duplicates" ,(format nil "t(r: a, q: b)~%t(r: a, q: b)"))
35 ("role-order-permutation" ,(format nil "t(r: a, q: b)~%t(q: b, r: a)"))
36 ("n-ary-permutation" ,(format nil "t(r1: a, r2: b, r3: c)~%t(r3: c, r2: b, r1: a)~%t(r1: a, r2: b)"))
37 ("scoped-duplicates" ,(format nil "t(r: a)@s~%t(r: a)@s~%t(r: a)@u~%t(r: a)~%t(r: a)@s,u~%t(r: a)@u,s"))
38 ("repeated-role-signature" ,(format nil "t(r: a, r: a, q: b)~%t(r: a, q: b)~%t(r: a, r: a)~%t(r: a)"))
39 ("type-differs" ,(format nil "t(r: a)~%u(r: a)"))
40 ("role-type-differs" ,(format nil "t(r: a)~%t(q: a)"))
41 ("player-differs" ,(format nil "t(r: a)~%t(r: b)"))
42 ("role-count-differs" ,(format nil "t(r: a)~%t(r: a, q: b)"))
43 ("equal-after-player-merge" ,(format nil "t(r: a, q: c)~%t(r: b, q: c)~%b ^ ~A ." (ii "a")))
44 ("equal-after-type-merge" ,(format nil "t(r: a)~%u(r: a)~%u ^ ~A ." (ii "t")))
45 ("equal-after-role-type-merge" ,(format nil "t(r: a)~%t(q: a)~%q ^ ~A ." (ii "r")))
46 ("equal-after-theme-merge" ,(format nil "t(r: a)@s~%t(r: a)@u~%u ^ ~A ." (ii "s")))
47 ("scope-collapses-after-theme-merge" ,(format nil "t(r: a)@s,u~%t(r: a)@s~%u ^ ~A ." (ii "s")))
48 ("duplicate-chain" ,(format nil "t(r: a)~%t(r: b)~%t(r: c)~%b ^ ~A .~%c ^ ~A ." (ii "a") (ii "a")))
49 ("first-pair-is-not-the-first-association" ,(format nil "u(r: x)~%t(r: a)~%t(r: b)~%u(r: y)~%t(r: a)~%u(r: x)"))
50 ("reified-duplicates-reifiers-merge" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%x - \"X\" .~%y - \"Y\" ."))
51 ("reified-one-side" ,(format nil "t(r: p) ~~ x~%t(r: p)~%x - \"X\" ."))
52 ("reifier-cascade" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%u(r: x) ~~ z~%u(r: y) ~~ w~%z - \"Z\" .~%w - \"W\" ."))
53 ("reifiers-become-equal-associations" ,(format nil "t(r: a) ~~ x~%t(r: b) ~~ y~%v(r: x)~%v(r: y)~%b ^ ~A ." (ii "a")))
54 ("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 ."))
55 ("same-type-80" ,(same-type-document 80 9)))
56 "CTM documents whose CXTM is recorded.")
57
58 (defparameter *rejections*
59 `(("reifier-reifies-association-and-name" ,(format nil "t(r: p) ~~ x~%m - \"M\" ~~ x ."))
60 ("equal-associations-with-core-subject-reifiers"
61 ,(format nil "t(r: a) ~~ x~%t(r: b) ~~ y~%x http://psi.topicmaps.org/iso13250/model/type .~%y http://psi.topicmaps.org/iso13250/model/instance .~%b ^ ~A ." (ii "a")))
62 ("reifier-merge-conflict" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ y~%x ^ ~A ." (ii "y"))))
63 "CTM documents whose rejection is recorded as condition class and code.")
64
65 ;;; API scenarios: what no CTM text shows (retained Association and Role handles, identifier order, reifiers)
66
67 (defun label (topic)
68 "A Topic named by its sorted subject identifiers, after resolving the handle."
69 (let ((topic (canonical-topic topic))) (format nil "~{~A~^|~}" (sort (topic-subject-identifiers topic) #'string<))))
70 (defun role-facts (role association)
71 (let ((current (canonical-association-role role)))
72 (list (label (association-role-type current)) (label (association-role-player current))
73 (association-role-item-identifiers current)
74 (and (member current (association-roles association) :test #'eq) t)
75 (let ((r (item-reifier current))) (and r (label r))))))
76 (defun association-facts (map handles roles)
77 (let ((current (canonical-association (first handles))))
78 (list :associations (length (topic-map-associations map))
79 :one-association (every (lambda (h) (eq current (canonical-association h))) handles)
80 :position (position current (topic-map-associations map) :test #'eq)
81 :item-identifiers (association-item-identifiers current)
82 :reifier (let ((r (item-reifier current))) (and r (label r)))
83 :roles (length (association-roles current))
84 :role-handles (mapcar (lambda (r) (role-facts r current)) roles)
85 :topics (length (topic-map-topics map)))))
86
87 (defun api-identifiers-and-handles ()
88 (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (q (si map "q")) (o (si map "other"))
89 (a (si map "a")) (b (si map "b")) (p (si map "p")))
90 (make-association map o (list (list r a)))
91 (let* ((a1 (make-association map ty (list (list r a) (list q p))))
92 (a2 (make-association map ty (list (list q p) (list r b))))
93 (roles (append (association-roles a1) (association-roles a2))))
94 (add-item-identifier a1 "urn:assoc-1") (add-item-identifier a2 "urn:assoc-2")
95 (add-item-identifier (first (association-roles a1)) "urn:role-1a")
96 (add-item-identifier (second (association-roles a2)) "urn:role-2b")
97 (add-item-identifier (first (association-roles a2)) "urn:role-2p")
98 (add-topic-identifier b :subject-identifier "urn:a")
99 (values map (association-facts map (list a1 a2) roles)))))
100
101 (defun api-reified-associations ()
102 (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b"))
103 (x (si map "x")) (y (si map "y"))
104 (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b)))))
105 (set-item-reifier a1 x) (set-item-reifier a2 y)
106 (add-name y "Y")
107 (add-topic-identifier b :subject-identifier "urn:a")
108 (values map (append (association-facts map (list a1 a2) (append (association-roles a1) (association-roles a2)))
109 (list :reifiers-one (eq (canonical-topic x) (canonical-topic y))
110 :inverse (eq (canonical-association a1) (topic-reified x)))))))
111
112 (defun api-reified-roles ()
113 (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b"))
114 (x (si map "x")) (y (si map "y"))
115 (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b))))
116 (r1 (first (association-roles a1))) (r2 (first (association-roles a2))))
117 (set-item-reifier r1 x) (set-item-reifier r2 y)
118 (merge-topics a b)
119 (values map (append (association-facts map (list a1 a2) (list r1 r2))
120 (list :role-reifiers-one (eq (canonical-topic x) (canonical-topic y))
121 :one-role (eq (canonical-association-role r1) (canonical-association-role r2)))))))
122
123 (defun api-three-way ()
124 ;; Three equal Associations after one merge of players: the representative is the first, then the third joins it.
125 (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) (c (si map "c"))
126 (a1 (make-association map ty (list (list r a)))) (mid (make-association map (si map "mid") (list (list r a))))
127 (a2 (make-association map ty (list (list r b)))) (a3 (make-association map ty (list (list r c)))))
128 (add-item-identifier a1 "urn:1") (add-item-identifier a2 "urn:2") (add-item-identifier a3 "urn:3")
129 (add-topic-identifier b :subject-identifier "urn:a")
130 (add-topic-identifier c :subject-identifier "urn:a")
131 (values map (append (association-facts map (list a1 a2 a3) nil)
132 (list :order (mapcar (lambda (h) (position (canonical-association h) (topic-map-associations map) :test #'eq))
133 (list a1 mid a2 a3)))))))
134
135 (defun api-core-subject-rejection ()
136 ;; Equal Associations whose Reifiers cannot merge: the conflict is signalled and the map is not changed.
137 (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b"))
138 (x (intern-topic map :subject-identifier "http://psi.topicmaps.org/iso13250/model/type"))
139 (y (intern-topic map :subject-identifier "http://psi.topicmaps.org/iso13250/model/instance"))
140 (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b)))))
141 (set-item-reifier a1 x) (set-item-reifier a2 y)
142 (let* ((before (topic-maps.ctm.tests::map-state map))
143 (condition (handler-case (progn (add-topic-identifier b :subject-identifier "urn:a") nil) (error (c) c))))
144 (values map (list :condition (and condition (type-of condition)) :code (and condition (condition-code condition))
145 :unchanged (equal before (topic-maps.ctm.tests::map-state map))
146 :associations (length (topic-map-associations map)))))))
147
148 (defparameter *api-scenarios*
149 '(("api-identifiers-and-handles" api-identifiers-and-handles) ("api-reified-associations" api-reified-associations)
150 ("api-reified-roles" api-reified-roles) ("api-three-way" api-three-way)
151 ("api-core-subject-rejection" api-core-subject-rejection))
152 "API scenarios whose CXTM and facts are recorded.")
153
154 (defun condition-code (c)
155 (cond ((typep c 'topic-maps.ctm:ctm-error) (topic-maps.ctm:error-code c))
156 ((typep c 'reification-error) (reification-error-code c))
157 ((typep c 'core-subject-error) (core-subject-error-code c))
158 (t nil)))
159 (defun outcome (thunk)
160 (handler-case (list :read (funcall thunk))
161 (error (c) (list :refused (type-of c) (condition-code c)))))
162 (defun document-outcome (text) (outcome (lambda () (cxtm (read-case text) +document+))))
163 (defun as-recorded (value)
164 "VALUE as it reads back from a fixture file: printed and read in the keyword package."
165 (let ((*package* (find-package "KEYWORD"))) (read-from-string (prin1-to-string value))))
166 (defun api-outcome (function)
167 (multiple-value-bind (map facts) (funcall function) (list (cxtm map +document+) facts)))
168
169 (defun record-expected ()
170 "Write the expected outcomes with the implementation now loaded. Run once, at unchanged 6162ed68."
171 (ensure-directories-exist (fixture-directory))
172 (flet ((record (name value)
173 (with-open-file (out (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory))
174 :direction :output :if-exists :supersede :external-format :utf-8)
175 (write-string value out))))
176 (dolist (case *documents*)
177 (destructuring-bind (kind value &rest rest) (document-outcome (second case))
178 (declare (ignore rest))
179 (unless (eq kind :read) (error "Case ~A was refused: ~S" (first case) value))
180 (record (first case) value)))
181 (with-open-file (facts (merge-pathnames "api-facts.sexp" (fixture-directory)) :direction :output :if-exists :supersede)
182 (let ((*package* (find-package "KEYWORD")))
183 (dolist (case *api-scenarios*)
184 (destructuring-bind (text value) (api-outcome (symbol-function (second case)))
185 (record (first case) text)
186 (prin1 (cons (first case) value) facts) (terpri facts))))))
187 (with-open-file (out (merge-pathnames "rejections.sexp" (fixture-directory)) :direction :output :if-exists :supersede)
188 (let ((*package* (find-package "KEYWORD")))
189 (dolist (case *rejections*)
190 (prin1 (cons (first case) (rest (document-outcome (second case)))) out) (terpri out)))))
191
192 (defun expected-cxtm (name)
193 (uiop:read-file-string (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory)) :external-format :utf-8))
194 (defun read-forms (name)
195 (with-open-file (in (merge-pathnames name (fixture-directory)))
196 (let ((*read-eval* nil) (*package* (find-package "KEYWORD"))) (loop for form = (read in nil) while form collect form))))
197
198 (defun recorded-outcome-tests ()
199 (dolist (case *documents*)
200 (let ((o (document-outcome (second case))))
201 (check (format nil "document:~A:read" (first case)) (eq :read (first o)))
202 (check (format nil "document:~A:cxtm-equals-6162ed68" (first case)) (string= (second o) (expected-cxtm (first case))))))
203 (let ((facts (read-forms "api-facts.sexp")))
204 (dolist (case *api-scenarios*)
205 (destructuring-bind (text value) (api-outcome (symbol-function (second case)))
206 (check (format nil "api:~A:cxtm-equals-6162ed68" (first case)) (string= text (expected-cxtm (first case))))
207 (check (format nil "api:~A:facts-equal-6162ed68" (first case))
208 (equal (as-recorded value) (rest (assoc (first case) facts :test #'string=)))))))
209 (let ((expected (read-forms "rejections.sexp")))
210 (dolist (case *rejections*)
211 (let ((recorded (rest (assoc (first case) expected :test #'string=))) (o (document-outcome (second case))))
212 (check (format nil "rejection:~A:recorded" (first case)) recorded)
213 (check (format nil "rejection:~A:class-and-code-equal-6162ed68" (first case))
214 (equal (as-recorded (rest o)) recorded))))))
215
216 ;;; The search itself, against the 6162ed68 search on unnormalized maps
217
218 (defun precondition-holds-p (associations)
219 "The index's precondition: no Association with two Roles of one signature, no Scope with a repeated theme."
220 (every (lambda (a)
221 (and (null (topic-maps.tmdm::equal-pair (topic-maps.tmdm::%association-roles a) #'topic-maps.tmdm::same-role-signature-p))
222 (= (length (topic-maps.tmdm::%association-scope a))
223 (length (remove-duplicates (topic-maps.tmdm::%association-scope a) :test #'eq)))))
224 associations))
225
226 (defun random-association-map (random &key (stale t) (repeated-listing t) (reifiers nil) (size 8) (max-roles 4) (max-themes 3))
227 "An unnormalized Map: a few raw Topics, raw Associations whose types, Role types, players and themes come from
228 small pools (so equal Associations are frequent), sometimes a repeated Role signature or theme (the fallback),
229 sometimes a reference to a replaced Topic (a raw stale reference), sometimes an Association listed twice, and,
230 with REIFIERS, distinct reifier Topics. Nothing is merged."
231 (let* ((map (make-topic-map)) (live (loop repeat (+ 3 (random 5 random)) collect (topic-maps.tmdm::%make-topic map)))
232 (old (and stale (zerop (random 3 random))
233 (let ((s (topic-maps.tmdm::%make-topic map))) (setf (topic-maps.tmdm::%topic-forward s) (pick random live)) s)))
234 (associations nil))
235 (setf (topic-maps.tmdm::%topic-map-topics map) live)
236 (flet ((ref (pool) (if (and old (zerop (random 7 random))) old (pick random (subseq live 0 (min pool (length live)))))))
237 (dotimes (k (+ 1 (random size random)))
238 (let ((a (topic-maps.tmdm::%make-association map (ref 2))))
239 (setf (topic-maps.tmdm::%association-roles a)
240 (loop repeat (random max-roles random) collect (topic-maps.tmdm::%make-association-role a (ref 2) (ref 3))))
241 (when (and (topic-maps.tmdm::%association-roles a) (zerop (random 6 random)))
242 (let ((r (first (topic-maps.tmdm::%association-roles a))))
243 (push (topic-maps.tmdm::%make-association-role a (topic-maps.tmdm::%association-role-type r)
244 (topic-maps.tmdm::%association-role-player r))
245 (topic-maps.tmdm::%association-roles a))))
246 (let ((themes (loop repeat (random max-themes random) collect (ref 3))))
247 (setf (topic-maps.tmdm::%association-scope a)
248 (if (zerop (random 6 random)) themes (remove-duplicates themes :test #'eq :from-end t))))
249 (push a associations)
250 (when (and repeated-listing (zerop (random 12 random))) (push a associations)))))
251 (setf associations (nreverse associations) (topic-maps.tmdm::%topic-map-associations map) associations)
252 (when reifiers
253 (let ((free nil))
254 (dolist (a (remove-duplicates associations))
255 (when (zerop (random 3 random))
256 (let ((r (topic-maps.tmdm::%make-topic map))) (push r free)
257 (setf (topic-maps.tmdm::%topic-map-topics map) (append (topic-maps.tmdm::%topic-map-topics map) (list r))
258 (topic-maps.tmdm::%association-reifier a) r))))))
259 map))
260
261 (defun asymmetric-pair-p (associations)
262 (loop for (a . rest) on associations
263 thereis (some (lambda (b) (not (eq (topic-maps.tmdm::equal-associations-p a b) (topic-maps.tmdm::equal-associations-p b a)))) rest)))
264
265 (defun selection-equivalence-tests (&key (maps 6000) (seed 20261028))
266 (let ((random (sb-ext:seed-random-state seed)) (pairs 0) (none 0) (index-path 0) (fallback 0) (asymmetric 0)
267 (stale 0) (listed-twice 0) (differences 0))
268 (dotimes (n maps)
269 (let* ((map (random-association-map random)) (associations (topic-maps.tmdm::%topic-map-associations map))
270 (indexed (topic-maps.tmdm::next-association-merge map))
271 (oracle (topic-maps.tmdm::scan-next-association-merge map)))
272 (cond ((not (equal indexed oracle)) (incf differences))
273 (oracle (incf pairs))
274 (t (incf none)))
275 (if (precondition-holds-p associations) (incf index-path) (incf fallback))
276 (when (asymmetric-pair-p associations) (incf asymmetric))
277 (when (some (lambda (a) (some (lambda (x) (topic-maps.tmdm::%topic-forward x))
278 (list* (topic-maps.tmdm::%association-type a)
279 (append (topic-maps.tmdm::%association-scope a)
280 (loop for r in (topic-maps.tmdm::%association-roles a)
281 collect (topic-maps.tmdm::%association-role-player r))))))
282 associations)
283 (incf stale))
284 (when (/= (length associations) (length (remove-duplicates associations))) (incf listed-twice))))
285 (check "selection:indexed-equals-oracle-on-every-map" (zerop differences))
286 (check "selection:maps-with-a-pair-exercised" (> pairs (floor maps 4)))
287 (check "selection:maps-without-a-pair-exercised" (> none (floor maps 20)))
288 (check "selection:index-path-exercised" (> index-path (floor maps 4)))
289 (check "selection:fallback-exercised" (> fallback (floor maps 20)))
290 (check "selection:asymmetric-equality-exercised" (> asymmetric (floor maps 100)))
291 (check "selection:raw-stale-references-exercised" (> stale (floor maps 20)))
292 (check "selection:association-listed-twice-exercised" (> listed-twice (floor maps 50)))
293 (list :maps maps :pair pairs :none none :index-path index-path :fallback fallback :asymmetric asymmetric
294 :stale stale :listed-twice listed-twice :differences differences)))
295
296 (defun asymmetry-tests ()
297 ;; With a repeated Role signature equality is not symmetric; only the pairwise search may decide then.
298 (let* ((map (make-topic-map)) (ty (topic-maps.tmdm::%make-topic map)) (r (topic-maps.tmdm::%make-topic map))
299 (p (topic-maps.tmdm::%make-topic map)) (q (topic-maps.tmdm::%make-topic map))
300 (a (topic-maps.tmdm::%make-association map ty)) (b (topic-maps.tmdm::%make-association map ty)))
301 (setf (topic-maps.tmdm::%topic-map-topics map) (list ty r p q)
302 (topic-maps.tmdm::%association-roles a) (list (topic-maps.tmdm::%make-association-role a r p) (topic-maps.tmdm::%make-association-role a r p))
303 (topic-maps.tmdm::%association-roles b) (list (topic-maps.tmdm::%make-association-role b r p) (topic-maps.tmdm::%make-association-role b r q)))
304 (check "asymmetry:a-equals-b" (topic-maps.tmdm::equal-associations-p a b))
305 (check "asymmetry:b-does-not-equal-a" (not (topic-maps.tmdm::equal-associations-p b a)))
306 (setf (topic-maps.tmdm::%topic-map-associations map) (list a b))
307 (check "asymmetry:a-first-is-a-pair" (equal (list a b) (topic-maps.tmdm::scan-next-association-merge map)))
308 (check "asymmetry:a-first-indexed-agrees" (equal (list a b) (topic-maps.tmdm::next-association-merge map)))
309 (setf (topic-maps.tmdm::%topic-map-associations map) (list b a))
310 (check "asymmetry:b-first-is-no-pair" (null (topic-maps.tmdm::scan-next-association-merge map)))
311 (check "asymmetry:b-first-indexed-agrees" (null (topic-maps.tmdm::next-association-merge map)))))
312
313 ;;; Every search during a run compared with the oracle, nested searches of cascades included
314
315 (defvar *shadow* nil)
316 (defun shadow-report () *shadow*)
317 (defmacro with-shadow-search (&body body)
318 "Run BODY with every NEXT-ASSOCIATION-MERGE call compared with SCAN-NEXT-ASSOCIATION-MERGE on the same map state."
319 `(let ((*shadow* (list :calls 0 :pairs 0 :inside-normalization 0 :nested 0 :mismatches 0)) (depth 0))
320 (sb-int:encapsulate 'topic-maps.tmdm::next-association-merge :shadow
321 (lambda (original map)
322 (let ((oracle (topic-maps.tmdm::scan-next-association-merge map))
323 (indexed (funcall original map)))
324 (incf (getf *shadow* :calls))
325 (when (> depth 0) (incf (getf *shadow* :inside-normalization)))
326 (when (> depth 1) (incf (getf *shadow* :nested)))
327 (when indexed (incf (getf *shadow* :pairs)))
328 (unless (equal indexed oracle) (incf (getf *shadow* :mismatches)))
329 indexed)))
330 (sb-int:encapsulate 'topic-maps.tmdm::normalize-associations :depth
331 (lambda (original map) (incf depth) (unwind-protect (funcall original map) (decf depth))))
332 (unwind-protect (progn ,@body)
333 (sb-int:unencapsulate 'topic-maps.tmdm::normalize-associations :depth)
334 (sb-int:unencapsulate 'topic-maps.tmdm::next-association-merge :shadow))))
335
336 (defmacro counting (functions &body body)
337 "BODY's value and a plist of how often each of FUNCTIONS was called."
338 `(let ((counts (list ,@(loop for f in functions append (list (intern (symbol-name f) "KEYWORD") 0)))))
339 ,@(loop for f in functions
340 collect `(sb-int:encapsulate ',f :count (lambda (original &rest arguments)
341 (incf (getf counts ,(intern (symbol-name f) "KEYWORD")))
342 (apply original arguments))))
343 (unwind-protect (values (progn ,@body) counts)
344 ,@(loop for f in functions collect `(sb-int:unencapsulate ',f :count)))))
345
346 ;;; Invalidation: the index lives for one search. After every mutation the search starts again from the map.
347
348 (defun merge-walk (random)
349 "Follow normalization on a random unnormalized Map with reifiers: at every step the indexed and the oracle search
350 must agree (the shadow also compares every nested search of the reifier cascades), then the pair is merged
351 exactly as NORMALIZE-ASSOCIATIONS does. Returns the number of steps and how the walk ended."
352 (let ((map (random-association-map random :stale nil :repeated-listing nil :reifiers t :size 14 :max-roles 3 :max-themes 2)) (steps 0))
353 (dolist (a (topic-maps.tmdm::%topic-map-associations map)) (topic-maps.tmdm::normalize-roles a))
354 (loop
355 (let ((indexed (topic-maps.tmdm::next-association-merge map)) (oracle (topic-maps.tmdm::scan-next-association-merge map)))
356 (unless (equal indexed oracle) (return (values steps :differs)))
357 (unless oracle (return (values steps :done)))
358 (handler-case (topic-maps.tmdm::merge-two-associations map (first oracle) (second oracle))
359 (error () (return (values steps :merge-refused))))
360 (incf steps)))))
361
362 (defun invalidation-tests (&key (walks 1500) (seed 20261029))
363 (let ((random (sb-ext:seed-random-state seed)) (steps 0) (differs 0) (done 0) (multi-step 0) (refused 0) result counts)
364 (multiple-value-setq (result counts)
365 (counting (topic-maps.tmdm::merge-two-topics topic-maps.tmdm::merge-two-associations topic-maps.tmdm::copy-map-graph)
366 (with-shadow-search
367 (dotimes (n walks)
368 (multiple-value-bind (count how) (merge-walk random)
369 (incf steps count)
370 (when (> count 1) (incf multi-step))
371 (case how (:differs (incf differs)) (:done (incf done)) (:merge-refused (incf refused)))))
372 (copy-list (shadow-report)))))
373 (check "invalidation:agrees-after-every-merge-step" (zerop differs))
374 (check "invalidation:every-nested-search-agrees" (zerop (getf result :mismatches)))
375 (check "invalidation:walks-with-several-merges-exercised" (> multi-step (floor walks 10)))
376 (check "invalidation:walks-reaching-a-fixed-point-exercised" (> done (floor walks 2)))
377 (check "invalidation:reifier-cascades-merged-topics" (> (getf counts :merge-two-topics) (floor walks 20)))
378 (check "invalidation:searches-inside-merge-cascades-exercised" (> (getf result :inside-normalization) 0))
379 (check "invalidation:preflight-copies-exercised" (> (getf counts :copy-map-graph) 0))
380 (list :walks walks :merge-steps steps :several-merges multi-step :fixed-point done :merge-refused refused
381 :differences differs :shadow result :counts counts)))
382
383 (defun stale-index-tests ()
384 ;; A pair found before a merge names Associations that are no longer live; the search after the merge never returns them.
385 (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) (c (si map "c"))
386 (x (topic-maps.tmdm::%make-association map ty)) (y (topic-maps.tmdm::%make-association map ty))
387 (z (topic-maps.tmdm::%make-association map ty)) (w (topic-maps.tmdm::%make-association map (si map "other"))))
388 (setf (topic-maps.tmdm::%association-roles x) (list (topic-maps.tmdm::%make-association-role x r a))
389 (topic-maps.tmdm::%association-roles y) (list (topic-maps.tmdm::%make-association-role y r a))
390 (topic-maps.tmdm::%association-roles z) (list (topic-maps.tmdm::%make-association-role z r a))
391 (topic-maps.tmdm::%association-roles w) (list (topic-maps.tmdm::%make-association-role w r b)
392 (topic-maps.tmdm::%make-association-role w r c))
393 (topic-maps.tmdm::%topic-map-associations map) (list w x y z))
394 (let ((before (topic-maps.tmdm::next-association-merge map)))
395 (check "stale:pair-found-before-the-merge" (equal (list x y) before))
396 (topic-maps.tmdm::merge-two-associations map x y)
397 (let ((after (topic-maps.tmdm::next-association-merge map)) (merged (canonical-association x)))
398 (check "stale:positive-control-old-handles-are-no-longer-listed"
399 (notany (lambda (h) (member h (topic-maps.tmdm::%topic-map-associations map))) before))
400 (check "stale:old-handles-forward-to-the-representative" (and (eq merged (canonical-association x)) (eq merged (canonical-association y))))
401 (check "stale:representative-takes-the-first-position" (equal (list w merged z) (topic-maps.tmdm::%topic-map-associations map)))
402 (check "stale:search-after-the-merge-names-listed-associations-only"
403 (every (lambda (h) (member h (topic-maps.tmdm::%topic-map-associations map))) after))
404 (check "stale:search-after-the-merge-finds-the-next-pair" (equal (list merged z) after))
405 (check "stale:search-agrees-with-the-oracle" (equal after (topic-maps.tmdm::scan-next-association-merge map)))
406 (check "stale:the-earlier-pair-differs" (not (equal before after)))))))
407
408 ;;; Whole reads: indexed and oracle searches run the same normalization to the same result
409
410 (defun random-document (random)
411 "A CTM document of Associations from small pools, scopes, repeated Roles, reifiers and identifier statements
412 that merge players, types, Role types, themes and reifiers."
413 (let ((tops (+ 2 (random 3 random))))
414 (with-output-to-string (s)
415 (flet ((topic () (format nil "t~D" (random tops random)))
416 (role () (format nil "r~D" (random 2 random)))
417 (reifier () (format nil "z~D" (random 8 random))))
418 (dotimes (i (+ 6 (random 14 random)))
419 (ecase (random 9 random)
420 ((0 1) (format s "a~D(~A: ~A, ~A: ~A)~%" (random 2 random) (role) (topic) (role) (topic)))
421 (2 (format s "a~D(~A: ~A)@~A~%" (random 2 random) (role) (topic) (topic)))
422 (3 (format s "a~D(~A: ~A, ~A: ~A)@~A,~A~%" (random 2 random) (role) (topic) (role) (topic) (topic) (topic)))
423 (4 (format s "a~D(~A: ~A) ~~ ~A~%" (random 2 random) (role) (topic) (reifier)))
424 (5 (format s "a~D(~A: ~A, ~A: ~A) ~~ ~A~%" (random 2 random) (role) (topic) (role) (topic) (reifier)))
425 (6 (format s "~A ^ ~A .~%" (topic) (ii (topic))))
426 (7 (format s "~A ^ ~A .~%" (pick random '("a0" "a1" "r0" "r1" "z0" "z1")) (ii (pick random '("a0" "a1" "r0" "r1" "t0" "z2")))))
427 (8 (format s "~A - \"n~D\" .~%" (topic) (random 2 random)))))))))
428
429 (defmacro with-oracle-search (&body body)
430 `(progn
431 (sb-int:encapsulate 'topic-maps.tmdm::next-association-merge :oracle
432 (lambda (original map) (declare (ignore original)) (topic-maps.tmdm::scan-next-association-merge map)))
433 (unwind-protect (progn ,@body) (sb-int:unencapsulate 'topic-maps.tmdm::next-association-merge :oracle))))
434
435 (defun reads-equal-tests (&key (documents 600) (seed 20261030))
436 (let ((random (sb-ext:seed-random-state seed)) (read 0) (refused 0) (differences 0) (merging 0) (association-merges 0)
437 (topic-merges 0) (reified 0) (shadow-mismatches 0))
438 (dotimes (n documents)
439 (let ((text (random-document random)))
440 (multiple-value-bind (indexed indexed-counts)
441 (counting (topic-maps.tmdm::merge-two-associations topic-maps.tmdm::merge-two-topics)
442 (with-shadow-search (prog1 (document-outcome text) (incf shadow-mismatches (getf (shadow-report) :mismatches)))))
443 (multiple-value-bind (oracle oracle-counts)
444 (with-oracle-search
445 (counting (topic-maps.tmdm::merge-two-associations topic-maps.tmdm::merge-two-topics) (document-outcome text)))
446 (cond ((or (not (equal indexed oracle)) (not (equal indexed-counts oracle-counts))) (incf differences))
447 (t (incf association-merges (getf indexed-counts :merge-two-associations))
448 (incf topic-merges (getf indexed-counts :merge-two-topics))
449 (when (plusp (getf indexed-counts :merge-two-associations)) (incf merging))
450 (cond ((eq :read (first oracle))
451 (incf read)
452 (when (search "reifier=" (second oracle)) (incf reified)))
453 (t (incf refused)))))))))
454 (check "reads:indexed-equals-oracle-on-every-document" (zerop differences))
455 (check "reads:every-search-of-every-read-agrees" (zerop shadow-mismatches))
456 (check "reads:documents-read-exercised" (> read (floor documents 2)))
457 (check "reads:association-merging-documents-exercised" (> merging (floor documents 4)))
458 (check "reads:topic-merges-exercised" (> topic-merges documents))
459 (check "reads:reified-documents-exercised" (> reified (floor documents 10)))
460 (list :documents documents :read read :refused refused :merging merging :association-merges association-merges
461 :topic-merges topic-merges :reified reified :differences differences :shadow-mismatches shadow-mismatches)))
462
463 ;;; Scale: many Associations of one type, the shape of the project CTM's search
464
465 (defun seconds-to (thunk)
466 (let ((start (get-internal-real-time)))
467 (values (funcall thunk) (float (/ (- (get-internal-real-time) start) internal-time-units-per-second) 1d0))))
468
469 (defun scale-tests (&key (associations 600) (budget 60))
470 (multiple-value-bind (map seconds) (seconds-to (lambda () (read-case (same-type-document associations 9))))
471 (check "scale:duplicates-merged" (= associations (length (topic-map-associations map))))
472 (check (format nil "scale:read-within-~Ds" budget) (< seconds budget))
473 (list :associations associations :seconds seconds)))
474
475 (defun run-tests ()
476 (let ((topic-maps.ctm.tests::*checks* nil) (search nil) (walks nil) (reads nil) (seconds nil))
477 (recorded-outcome-tests)
478 (asymmetry-tests)
479 (stale-index-tests)
480 (setf search (selection-equivalence-tests) walks (invalidation-tests) reads (reads-equal-tests))
481 (setf seconds (scale-tests))
482 (format t "~&ASSOCIATION-INDEX-SELECTION: ~S~%ASSOCIATION-INDEX-WALKS: ~S~%ASSOCIATION-INDEX-READS: ~S~%ASSOCIATION-INDEX-SCALE: ~S~%"
483 search walks reads seconds)
484 (setf *last-checks* (reverse topic-maps.ctm.tests::*checks*))
485 (format t "~&ASSOCIATION-INDEX-PASS: ~D checks; ~D documents, ~D API scenarios and ~D rejections equal to the outcomes recorded at 6162ed68.~%"
486 (length *last-checks*) (length *documents*) (length *api-scenarios*) (length *rejections*))
487 *last-checks*))