(defpackage #:topic-maps.association-index.tests (:use #:cl #:topic-maps.tmdm) (:import-from #:topic-maps.ctm.tests #:check #:cxtm) (:import-from #:topic-maps.identifier.tests #:si) (:export #:run-tests #:association-index-checks #:record-expected #:with-shadow-search #:shadow-report)) (in-package #:topic-maps.association-index.tests) ;;; Which Associations merge next, and the results that must not change while the search for them changes. ;;; The expected CXTM of every case, the facts of every API scenario and the class and code of every rejection ;;; were recorded from the unchanged implementation at 6162ed68 (RECORD-EXPECTED) before NEXT-ASSOCIATION-MERGE ;;; existed; they are not derived from the implementation under test. SCAN-NEXT-ASSOCIATION-MERGE is the 6162ed68 ;;; search, kept as the fallback and used here as the oracle. (defvar *last-checks* nil) (defun association-index-checks () *last-checks*) (defparameter +document+ "https://example.invalid/a/doc.ctm") (defvar *fixture-directory* nil) (defun fixture-directory () (or *fixture-directory* (asdf:system-relative-pathname "topic-maps" "tests/fixtures/association-index/"))) (defun read-case (text) (topic-maps.ctm:deserialize-string text :document-iri +document+ :source-name "association-index")) (defun pick (random sequence) (elt sequence (random (length sequence) random))) (defun ii (name) (format nil "~A#~A" +document+ name)) ;;; Documents whose result must not change (defun same-type-document (associations duplicate-every) "ASSOCIATIONS Associations of one type with distinct players; every DUPLICATE-EVERYth is stated twice." (with-output-to-string (s) (dotimes (i associations) (format s "t(r: p~D, q: o~D)~%" i (mod i 7)) (when (and (plusp duplicate-every) (zerop (mod i duplicate-every))) (format s "t(q: o~D, r: p~D)~%" (mod i 7) i))))) (defparameter *documents* `(("plain-duplicates" ,(format nil "t(r: a, q: b)~%t(r: a, q: b)")) ("role-order-permutation" ,(format nil "t(r: a, q: b)~%t(q: b, r: a)")) ("n-ary-permutation" ,(format nil "t(r1: a, r2: b, r3: c)~%t(r3: c, r2: b, r1: a)~%t(r1: a, r2: b)")) ("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")) ("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)")) ("type-differs" ,(format nil "t(r: a)~%u(r: a)")) ("role-type-differs" ,(format nil "t(r: a)~%t(q: a)")) ("player-differs" ,(format nil "t(r: a)~%t(r: b)")) ("role-count-differs" ,(format nil "t(r: a)~%t(r: a, q: b)")) ("equal-after-player-merge" ,(format nil "t(r: a, q: c)~%t(r: b, q: c)~%b ^ ~A ." (ii "a"))) ("equal-after-type-merge" ,(format nil "t(r: a)~%u(r: a)~%u ^ ~A ." (ii "t"))) ("equal-after-role-type-merge" ,(format nil "t(r: a)~%t(q: a)~%q ^ ~A ." (ii "r"))) ("equal-after-theme-merge" ,(format nil "t(r: a)@s~%t(r: a)@u~%u ^ ~A ." (ii "s"))) ("scope-collapses-after-theme-merge" ,(format nil "t(r: a)@s,u~%t(r: a)@s~%u ^ ~A ." (ii "s"))) ("duplicate-chain" ,(format nil "t(r: a)~%t(r: b)~%t(r: c)~%b ^ ~A .~%c ^ ~A ." (ii "a") (ii "a"))) ("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)")) ("reified-duplicates-reifiers-merge" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%x - \"X\" .~%y - \"Y\" .")) ("reified-one-side" ,(format nil "t(r: p) ~~ x~%t(r: p)~%x - \"X\" .")) ("reifier-cascade" ,(format nil "t(r: p) ~~ x~%t(r: p) ~~ y~%u(r: x) ~~ z~%u(r: y) ~~ w~%z - \"Z\" .~%w - \"W\" .")) ("reifiers-become-equal-associations" ,(format nil "t(r: a) ~~ x~%t(r: b) ~~ y~%v(r: x)~%v(r: y)~%b ^ ~A ." (ii "a"))) ("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 .")) ("same-type-80" ,(same-type-document 80 9))) "CTM documents whose CXTM is recorded.") (defparameter *rejections* `(("reifier-reifies-association-and-name" ,(format nil "t(r: p) ~~ x~%m - \"M\" ~~ x .")) ("equal-associations-with-core-subject-reifiers" ,(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"))) ("reifier-merge-conflict" ,(format nil "t(r: p) ~~ x~%u(r: q) ~~ y~%x ^ ~A ." (ii "y")))) "CTM documents whose rejection is recorded as condition class and code.") ;;; API scenarios: what no CTM text shows (retained Association and Role handles, identifier order, reifiers) (defun label (topic) "A Topic named by its sorted subject identifiers, after resolving the handle." (let ((topic (canonical-topic topic))) (format nil "~{~A~^|~}" (sort (topic-subject-identifiers topic) #'string<)))) (defun role-facts (role association) (let ((current (canonical-association-role role))) (list (label (association-role-type current)) (label (association-role-player current)) (association-role-item-identifiers current) (and (member current (association-roles association) :test #'eq) t) (let ((r (item-reifier current))) (and r (label r)))))) (defun association-facts (map handles roles) (let ((current (canonical-association (first handles)))) (list :associations (length (topic-map-associations map)) :one-association (every (lambda (h) (eq current (canonical-association h))) handles) :position (position current (topic-map-associations map) :test #'eq) :item-identifiers (association-item-identifiers current) :reifier (let ((r (item-reifier current))) (and r (label r))) :roles (length (association-roles current)) :role-handles (mapcar (lambda (r) (role-facts r current)) roles) :topics (length (topic-map-topics map))))) (defun api-identifiers-and-handles () (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (q (si map "q")) (o (si map "other")) (a (si map "a")) (b (si map "b")) (p (si map "p"))) (make-association map o (list (list r a))) (let* ((a1 (make-association map ty (list (list r a) (list q p)))) (a2 (make-association map ty (list (list q p) (list r b)))) (roles (append (association-roles a1) (association-roles a2)))) (add-item-identifier a1 "urn:assoc-1") (add-item-identifier a2 "urn:assoc-2") (add-item-identifier (first (association-roles a1)) "urn:role-1a") (add-item-identifier (second (association-roles a2)) "urn:role-2b") (add-item-identifier (first (association-roles a2)) "urn:role-2p") (add-topic-identifier b :subject-identifier "urn:a") (values map (association-facts map (list a1 a2) roles))))) (defun api-reified-associations () (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) (x (si map "x")) (y (si map "y")) (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b))))) (set-item-reifier a1 x) (set-item-reifier a2 y) (add-name y "Y") (add-topic-identifier b :subject-identifier "urn:a") (values map (append (association-facts map (list a1 a2) (append (association-roles a1) (association-roles a2))) (list :reifiers-one (eq (canonical-topic x) (canonical-topic y)) :inverse (eq (canonical-association a1) (topic-reified x))))))) (defun api-reified-roles () (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) (x (si map "x")) (y (si map "y")) (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b)))) (r1 (first (association-roles a1))) (r2 (first (association-roles a2)))) (set-item-reifier r1 x) (set-item-reifier r2 y) (merge-topics a b) (values map (append (association-facts map (list a1 a2) (list r1 r2)) (list :role-reifiers-one (eq (canonical-topic x) (canonical-topic y)) :one-role (eq (canonical-association-role r1) (canonical-association-role r2))))))) (defun api-three-way () ;; Three equal Associations after one merge of players: the representative is the first, then the third joins it. (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")) (a1 (make-association map ty (list (list r a)))) (mid (make-association map (si map "mid") (list (list r a)))) (a2 (make-association map ty (list (list r b)))) (a3 (make-association map ty (list (list r c))))) (add-item-identifier a1 "urn:1") (add-item-identifier a2 "urn:2") (add-item-identifier a3 "urn:3") (add-topic-identifier b :subject-identifier "urn:a") (add-topic-identifier c :subject-identifier "urn:a") (values map (append (association-facts map (list a1 a2 a3) nil) (list :order (mapcar (lambda (h) (position (canonical-association h) (topic-map-associations map) :test #'eq)) (list a1 mid a2 a3))))))) (defun api-core-subject-rejection () ;; Equal Associations whose Reifiers cannot merge: the conflict is signalled and the map is not changed. (let* ((map (make-topic-map)) (ty (si map "type")) (r (si map "r")) (a (si map "a")) (b (si map "b")) (x (intern-topic map :subject-identifier "http://psi.topicmaps.org/iso13250/model/type")) (y (intern-topic map :subject-identifier "http://psi.topicmaps.org/iso13250/model/instance")) (a1 (make-association map ty (list (list r a)))) (a2 (make-association map ty (list (list r b))))) (set-item-reifier a1 x) (set-item-reifier a2 y) (let* ((before (topic-maps.ctm.tests::map-state map)) (condition (handler-case (progn (add-topic-identifier b :subject-identifier "urn:a") nil) (error (c) c)))) (values map (list :condition (and condition (type-of condition)) :code (and condition (condition-code condition)) :unchanged (equal before (topic-maps.ctm.tests::map-state map)) :associations (length (topic-map-associations map))))))) (defparameter *api-scenarios* '(("api-identifiers-and-handles" api-identifiers-and-handles) ("api-reified-associations" api-reified-associations) ("api-reified-roles" api-reified-roles) ("api-three-way" api-three-way) ("api-core-subject-rejection" api-core-subject-rejection)) "API scenarios whose CXTM and facts are recorded.") (defun condition-code (c) (cond ((typep c 'topic-maps.ctm:ctm-error) (topic-maps.ctm:error-code c)) ((typep c 'reification-error) (reification-error-code c)) ((typep c 'core-subject-error) (core-subject-error-code c)) (t nil))) (defun outcome (thunk) (handler-case (list :read (funcall thunk)) (error (c) (list :refused (type-of c) (condition-code c))))) (defun document-outcome (text) (outcome (lambda () (cxtm (read-case text) +document+)))) (defun as-recorded (value) "VALUE as it reads back from a fixture file: printed and read in the keyword package." (let ((*package* (find-package "KEYWORD"))) (read-from-string (prin1-to-string value)))) (defun api-outcome (function) (multiple-value-bind (map facts) (funcall function) (list (cxtm map +document+) facts))) (defun record-expected () "Write the expected outcomes with the implementation now loaded. Run once, at unchanged 6162ed68." (ensure-directories-exist (fixture-directory)) (flet ((record (name value) (with-open-file (out (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory)) :direction :output :if-exists :supersede :external-format :utf-8) (write-string value out)))) (dolist (case *documents*) (destructuring-bind (kind value &rest rest) (document-outcome (second case)) (declare (ignore rest)) (unless (eq kind :read) (error "Case ~A was refused: ~S" (first case) value)) (record (first case) value))) (with-open-file (facts (merge-pathnames "api-facts.sexp" (fixture-directory)) :direction :output :if-exists :supersede) (let ((*package* (find-package "KEYWORD"))) (dolist (case *api-scenarios*) (destructuring-bind (text value) (api-outcome (symbol-function (second case))) (record (first case) text) (prin1 (cons (first case) value) facts) (terpri facts)))))) (with-open-file (out (merge-pathnames "rejections.sexp" (fixture-directory)) :direction :output :if-exists :supersede) (let ((*package* (find-package "KEYWORD"))) (dolist (case *rejections*) (prin1 (cons (first case) (rest (document-outcome (second case)))) out) (terpri out))))) (defun expected-cxtm (name) (uiop:read-file-string (merge-pathnames (concatenate 'string name ".cxtm") (fixture-directory)) :external-format :utf-8)) (defun read-forms (name) (with-open-file (in (merge-pathnames name (fixture-directory))) (let ((*read-eval* nil) (*package* (find-package "KEYWORD"))) (loop for form = (read in nil) while form collect form)))) (defun recorded-outcome-tests () (dolist (case *documents*) (let ((o (document-outcome (second case)))) (check (format nil "document:~A:read" (first case)) (eq :read (first o))) (check (format nil "document:~A:cxtm-equals-6162ed68" (first case)) (string= (second o) (expected-cxtm (first case)))))) (let ((facts (read-forms "api-facts.sexp"))) (dolist (case *api-scenarios*) (destructuring-bind (text value) (api-outcome (symbol-function (second case))) (check (format nil "api:~A:cxtm-equals-6162ed68" (first case)) (string= text (expected-cxtm (first case)))) (check (format nil "api:~A:facts-equal-6162ed68" (first case)) (equal (as-recorded value) (rest (assoc (first case) facts :test #'string=))))))) (let ((expected (read-forms "rejections.sexp"))) (dolist (case *rejections*) (let ((recorded (rest (assoc (first case) expected :test #'string=))) (o (document-outcome (second case)))) (check (format nil "rejection:~A:recorded" (first case)) recorded) (check (format nil "rejection:~A:class-and-code-equal-6162ed68" (first case)) (equal (as-recorded (rest o)) recorded)))))) ;;; The search itself, against the 6162ed68 search on unnormalized maps (defun precondition-holds-p (associations) "The index's precondition: no Association with two Roles of one signature, no Scope with a repeated theme." (every (lambda (a) (and (null (topic-maps.tmdm::equal-pair (topic-maps.tmdm::%association-roles a) #'topic-maps.tmdm::same-role-signature-p)) (= (length (topic-maps.tmdm::%association-scope a)) (length (remove-duplicates (topic-maps.tmdm::%association-scope a) :test #'eq))))) associations)) (defun random-association-map (random &key (stale t) (repeated-listing t) (reifiers nil) (size 8) (max-roles 4) (max-themes 3)) "An unnormalized Map: a few raw Topics, raw Associations whose types, Role types, players and themes come from small pools (so equal Associations are frequent), sometimes a repeated Role signature or theme (the fallback), sometimes a reference to a replaced Topic (a raw stale reference), sometimes an Association listed twice, and, with REIFIERS, distinct reifier Topics. Nothing is merged." (let* ((map (make-topic-map)) (live (loop repeat (+ 3 (random 5 random)) collect (topic-maps.tmdm::%make-topic map))) (old (and stale (zerop (random 3 random)) (let ((s (topic-maps.tmdm::%make-topic map))) (setf (topic-maps.tmdm::%topic-forward s) (pick random live)) s))) (associations nil)) (setf (topic-maps.tmdm::%topic-map-topics map) live) (flet ((ref (pool) (if (and old (zerop (random 7 random))) old (pick random (subseq live 0 (min pool (length live))))))) (dotimes (k (+ 1 (random size random))) (let ((a (topic-maps.tmdm::%make-association map (ref 2)))) (setf (topic-maps.tmdm::%association-roles a) (loop repeat (random max-roles random) collect (topic-maps.tmdm::%make-association-role a (ref 2) (ref 3)))) (when (and (topic-maps.tmdm::%association-roles a) (zerop (random 6 random))) (let ((r (first (topic-maps.tmdm::%association-roles a)))) (push (topic-maps.tmdm::%make-association-role a (topic-maps.tmdm::%association-role-type r) (topic-maps.tmdm::%association-role-player r)) (topic-maps.tmdm::%association-roles a)))) (let ((themes (loop repeat (random max-themes random) collect (ref 3)))) (setf (topic-maps.tmdm::%association-scope a) (if (zerop (random 6 random)) themes (remove-duplicates themes :test #'eq :from-end t)))) (push a associations) (when (and repeated-listing (zerop (random 12 random))) (push a associations))))) (setf associations (nreverse associations) (topic-maps.tmdm::%topic-map-associations map) associations) (when reifiers (let ((free nil)) (dolist (a (remove-duplicates associations)) (when (zerop (random 3 random)) (let ((r (topic-maps.tmdm::%make-topic map))) (push r free) (setf (topic-maps.tmdm::%topic-map-topics map) (append (topic-maps.tmdm::%topic-map-topics map) (list r)) (topic-maps.tmdm::%association-reifier a) r)))))) map)) (defun asymmetric-pair-p (associations) (loop for (a . rest) on associations thereis (some (lambda (b) (not (eq (topic-maps.tmdm::equal-associations-p a b) (topic-maps.tmdm::equal-associations-p b a)))) rest))) (defun selection-equivalence-tests (&key (maps 6000) (seed 20261028)) (let ((random (sb-ext:seed-random-state seed)) (pairs 0) (none 0) (index-path 0) (fallback 0) (asymmetric 0) (stale 0) (listed-twice 0) (differences 0)) (dotimes (n maps) (let* ((map (random-association-map random)) (associations (topic-maps.tmdm::%topic-map-associations map)) (indexed (topic-maps.tmdm::next-association-merge map)) (oracle (topic-maps.tmdm::scan-next-association-merge map))) (cond ((not (equal indexed oracle)) (incf differences)) (oracle (incf pairs)) (t (incf none))) (if (precondition-holds-p associations) (incf index-path) (incf fallback)) (when (asymmetric-pair-p associations) (incf asymmetric)) (when (some (lambda (a) (some (lambda (x) (topic-maps.tmdm::%topic-forward x)) (list* (topic-maps.tmdm::%association-type a) (append (topic-maps.tmdm::%association-scope a) (loop for r in (topic-maps.tmdm::%association-roles a) collect (topic-maps.tmdm::%association-role-player r)))))) associations) (incf stale)) (when (/= (length associations) (length (remove-duplicates associations))) (incf listed-twice)))) (check "selection:indexed-equals-oracle-on-every-map" (zerop differences)) (check "selection:maps-with-a-pair-exercised" (> pairs (floor maps 4))) (check "selection:maps-without-a-pair-exercised" (> none (floor maps 20))) (check "selection:index-path-exercised" (> index-path (floor maps 4))) (check "selection:fallback-exercised" (> fallback (floor maps 20))) (check "selection:asymmetric-equality-exercised" (> asymmetric (floor maps 100))) (check "selection:raw-stale-references-exercised" (> stale (floor maps 20))) (check "selection:association-listed-twice-exercised" (> listed-twice (floor maps 50))) (list :maps maps :pair pairs :none none :index-path index-path :fallback fallback :asymmetric asymmetric :stale stale :listed-twice listed-twice :differences differences))) (defun asymmetry-tests () ;; With a repeated Role signature equality is not symmetric; only the pairwise search may decide then. (let* ((map (make-topic-map)) (ty (topic-maps.tmdm::%make-topic map)) (r (topic-maps.tmdm::%make-topic map)) (p (topic-maps.tmdm::%make-topic map)) (q (topic-maps.tmdm::%make-topic map)) (a (topic-maps.tmdm::%make-association map ty)) (b (topic-maps.tmdm::%make-association map ty))) (setf (topic-maps.tmdm::%topic-map-topics map) (list ty r p q) (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)) (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))) (check "asymmetry:a-equals-b" (topic-maps.tmdm::equal-associations-p a b)) (check "asymmetry:b-does-not-equal-a" (not (topic-maps.tmdm::equal-associations-p b a))) (setf (topic-maps.tmdm::%topic-map-associations map) (list a b)) (check "asymmetry:a-first-is-a-pair" (equal (list a b) (topic-maps.tmdm::scan-next-association-merge map))) (check "asymmetry:a-first-indexed-agrees" (equal (list a b) (topic-maps.tmdm::next-association-merge map))) (setf (topic-maps.tmdm::%topic-map-associations map) (list b a)) (check "asymmetry:b-first-is-no-pair" (null (topic-maps.tmdm::scan-next-association-merge map))) (check "asymmetry:b-first-indexed-agrees" (null (topic-maps.tmdm::next-association-merge map))))) ;;; Every search during a run compared with the oracle, nested searches of cascades included (defvar *shadow* nil) (defun shadow-report () *shadow*) (defmacro with-shadow-search (&body body) "Run BODY with every NEXT-ASSOCIATION-MERGE call compared with SCAN-NEXT-ASSOCIATION-MERGE on the same map state." `(let ((*shadow* (list :calls 0 :pairs 0 :inside-normalization 0 :nested 0 :mismatches 0)) (depth 0)) (sb-int:encapsulate 'topic-maps.tmdm::next-association-merge :shadow (lambda (original map) (let ((oracle (topic-maps.tmdm::scan-next-association-merge map)) (indexed (funcall original map))) (incf (getf *shadow* :calls)) (when (> depth 0) (incf (getf *shadow* :inside-normalization))) (when (> depth 1) (incf (getf *shadow* :nested))) (when indexed (incf (getf *shadow* :pairs))) (unless (equal indexed oracle) (incf (getf *shadow* :mismatches))) indexed))) (sb-int:encapsulate 'topic-maps.tmdm::normalize-associations :depth (lambda (original map) (incf depth) (unwind-protect (funcall original map) (decf depth)))) (unwind-protect (progn ,@body) (sb-int:unencapsulate 'topic-maps.tmdm::normalize-associations :depth) (sb-int:unencapsulate 'topic-maps.tmdm::next-association-merge :shadow)))) (defmacro counting (functions &body body) "BODY's value and a plist of how often each of FUNCTIONS was called." `(let ((counts (list ,@(loop for f in functions append (list (intern (symbol-name f) "KEYWORD") 0))))) ,@(loop for f in functions collect `(sb-int:encapsulate ',f :count (lambda (original &rest arguments) (incf (getf counts ,(intern (symbol-name f) "KEYWORD"))) (apply original arguments)))) (unwind-protect (values (progn ,@body) counts) ,@(loop for f in functions collect `(sb-int:unencapsulate ',f :count))))) ;;; Invalidation: the index lives for one search. After every mutation the search starts again from the map. (defun merge-walk (random) "Follow normalization on a random unnormalized Map with reifiers: at every step the indexed and the oracle search must agree (the shadow also compares every nested search of the reifier cascades), then the pair is merged exactly as NORMALIZE-ASSOCIATIONS does. Returns the number of steps and how the walk ended." (let ((map (random-association-map random :stale nil :repeated-listing nil :reifiers t :size 14 :max-roles 3 :max-themes 2)) (steps 0)) (dolist (a (topic-maps.tmdm::%topic-map-associations map)) (topic-maps.tmdm::normalize-roles a)) (loop (let ((indexed (topic-maps.tmdm::next-association-merge map)) (oracle (topic-maps.tmdm::scan-next-association-merge map))) (unless (equal indexed oracle) (return (values steps :differs))) (unless oracle (return (values steps :done))) (handler-case (topic-maps.tmdm::merge-two-associations map (first oracle) (second oracle)) (error () (return (values steps :merge-refused)))) (incf steps))))) (defun invalidation-tests (&key (walks 1500) (seed 20261029)) (let ((random (sb-ext:seed-random-state seed)) (steps 0) (differs 0) (done 0) (multi-step 0) (refused 0) result counts) (multiple-value-setq (result counts) (counting (topic-maps.tmdm::merge-two-topics topic-maps.tmdm::merge-two-associations topic-maps.tmdm::copy-map-graph) (with-shadow-search (dotimes (n walks) (multiple-value-bind (count how) (merge-walk random) (incf steps count) (when (> count 1) (incf multi-step)) (case how (:differs (incf differs)) (:done (incf done)) (:merge-refused (incf refused))))) (copy-list (shadow-report))))) (check "invalidation:agrees-after-every-merge-step" (zerop differs)) (check "invalidation:every-nested-search-agrees" (zerop (getf result :mismatches))) (check "invalidation:walks-with-several-merges-exercised" (> multi-step (floor walks 10))) (check "invalidation:walks-reaching-a-fixed-point-exercised" (> done (floor walks 2))) (check "invalidation:reifier-cascades-merged-topics" (> (getf counts :merge-two-topics) (floor walks 20))) (check "invalidation:searches-inside-merge-cascades-exercised" (> (getf result :inside-normalization) 0)) (check "invalidation:preflight-copies-exercised" (> (getf counts :copy-map-graph) 0)) (list :walks walks :merge-steps steps :several-merges multi-step :fixed-point done :merge-refused refused :differences differs :shadow result :counts counts))) (defun stale-index-tests () ;; A pair found before a merge names Associations that are no longer live; the search after the merge never returns them. (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")) (x (topic-maps.tmdm::%make-association map ty)) (y (topic-maps.tmdm::%make-association map ty)) (z (topic-maps.tmdm::%make-association map ty)) (w (topic-maps.tmdm::%make-association map (si map "other")))) (setf (topic-maps.tmdm::%association-roles x) (list (topic-maps.tmdm::%make-association-role x r a)) (topic-maps.tmdm::%association-roles y) (list (topic-maps.tmdm::%make-association-role y r a)) (topic-maps.tmdm::%association-roles z) (list (topic-maps.tmdm::%make-association-role z r a)) (topic-maps.tmdm::%association-roles w) (list (topic-maps.tmdm::%make-association-role w r b) (topic-maps.tmdm::%make-association-role w r c)) (topic-maps.tmdm::%topic-map-associations map) (list w x y z)) (let ((before (topic-maps.tmdm::next-association-merge map))) (check "stale:pair-found-before-the-merge" (equal (list x y) before)) (topic-maps.tmdm::merge-two-associations map x y) (let ((after (topic-maps.tmdm::next-association-merge map)) (merged (canonical-association x))) (check "stale:positive-control-old-handles-are-no-longer-listed" (notany (lambda (h) (member h (topic-maps.tmdm::%topic-map-associations map))) before)) (check "stale:old-handles-forward-to-the-representative" (and (eq merged (canonical-association x)) (eq merged (canonical-association y)))) (check "stale:representative-takes-the-first-position" (equal (list w merged z) (topic-maps.tmdm::%topic-map-associations map))) (check "stale:search-after-the-merge-names-listed-associations-only" (every (lambda (h) (member h (topic-maps.tmdm::%topic-map-associations map))) after)) (check "stale:search-after-the-merge-finds-the-next-pair" (equal (list merged z) after)) (check "stale:search-agrees-with-the-oracle" (equal after (topic-maps.tmdm::scan-next-association-merge map))) (check "stale:the-earlier-pair-differs" (not (equal before after))))))) ;;; Whole reads: indexed and oracle searches run the same normalization to the same result (defun random-document (random) "A CTM document of Associations from small pools, scopes, repeated Roles, reifiers and identifier statements that merge players, types, Role types, themes and reifiers." (let ((tops (+ 2 (random 3 random)))) (with-output-to-string (s) (flet ((topic () (format nil "t~D" (random tops random))) (role () (format nil "r~D" (random 2 random))) (reifier () (format nil "z~D" (random 8 random)))) (dotimes (i (+ 6 (random 14 random))) (ecase (random 9 random) ((0 1) (format s "a~D(~A: ~A, ~A: ~A)~%" (random 2 random) (role) (topic) (role) (topic))) (2 (format s "a~D(~A: ~A)@~A~%" (random 2 random) (role) (topic) (topic))) (3 (format s "a~D(~A: ~A, ~A: ~A)@~A,~A~%" (random 2 random) (role) (topic) (role) (topic) (topic) (topic))) (4 (format s "a~D(~A: ~A) ~~ ~A~%" (random 2 random) (role) (topic) (reifier))) (5 (format s "a~D(~A: ~A, ~A: ~A) ~~ ~A~%" (random 2 random) (role) (topic) (role) (topic) (reifier))) (6 (format s "~A ^ ~A .~%" (topic) (ii (topic)))) (7 (format s "~A ^ ~A .~%" (pick random '("a0" "a1" "r0" "r1" "z0" "z1")) (ii (pick random '("a0" "a1" "r0" "r1" "t0" "z2"))))) (8 (format s "~A - \"n~D\" .~%" (topic) (random 2 random))))))))) (defmacro with-oracle-search (&body body) `(progn (sb-int:encapsulate 'topic-maps.tmdm::next-association-merge :oracle (lambda (original map) (declare (ignore original)) (topic-maps.tmdm::scan-next-association-merge map))) (unwind-protect (progn ,@body) (sb-int:unencapsulate 'topic-maps.tmdm::next-association-merge :oracle)))) (defun reads-equal-tests (&key (documents 600) (seed 20261030)) (let ((random (sb-ext:seed-random-state seed)) (read 0) (refused 0) (differences 0) (merging 0) (association-merges 0) (topic-merges 0) (reified 0) (shadow-mismatches 0)) (dotimes (n documents) (let ((text (random-document random))) (multiple-value-bind (indexed indexed-counts) (counting (topic-maps.tmdm::merge-two-associations topic-maps.tmdm::merge-two-topics) (with-shadow-search (prog1 (document-outcome text) (incf shadow-mismatches (getf (shadow-report) :mismatches))))) (multiple-value-bind (oracle oracle-counts) (with-oracle-search (counting (topic-maps.tmdm::merge-two-associations topic-maps.tmdm::merge-two-topics) (document-outcome text))) (cond ((or (not (equal indexed oracle)) (not (equal indexed-counts oracle-counts))) (incf differences)) (t (incf association-merges (getf indexed-counts :merge-two-associations)) (incf topic-merges (getf indexed-counts :merge-two-topics)) (when (plusp (getf indexed-counts :merge-two-associations)) (incf merging)) (cond ((eq :read (first oracle)) (incf read) (when (search "reifier=" (second oracle)) (incf reified))) (t (incf refused))))))))) (check "reads:indexed-equals-oracle-on-every-document" (zerop differences)) (check "reads:every-search-of-every-read-agrees" (zerop shadow-mismatches)) (check "reads:documents-read-exercised" (> read (floor documents 2))) (check "reads:association-merging-documents-exercised" (> merging (floor documents 4))) (check "reads:topic-merges-exercised" (> topic-merges documents)) (check "reads:reified-documents-exercised" (> reified (floor documents 10))) (list :documents documents :read read :refused refused :merging merging :association-merges association-merges :topic-merges topic-merges :reified reified :differences differences :shadow-mismatches shadow-mismatches))) ;;; Scale: many Associations of one type, the shape of the project CTM's search (defun seconds-to (thunk) (let ((start (get-internal-real-time))) (values (funcall thunk) (float (/ (- (get-internal-real-time) start) internal-time-units-per-second) 1d0)))) (defun scale-tests (&key (associations 600) (budget 60)) (multiple-value-bind (map seconds) (seconds-to (lambda () (read-case (same-type-document associations 9)))) (check "scale:duplicates-merged" (= associations (length (topic-map-associations map)))) (check (format nil "scale:read-within-~Ds" budget) (< seconds budget)) (list :associations associations :seconds seconds))) (defun run-tests () (let ((topic-maps.ctm.tests::*checks* nil) (search nil) (walks nil) (reads nil) (seconds nil)) (recorded-outcome-tests) (asymmetry-tests) (stale-index-tests) (setf search (selection-equivalence-tests) walks (invalidation-tests) reads (reads-equal-tests)) (setf seconds (scale-tests)) (format t "~&ASSOCIATION-INDEX-SELECTION: ~S~%ASSOCIATION-INDEX-WALKS: ~S~%ASSOCIATION-INDEX-READS: ~S~%ASSOCIATION-INDEX-SCALE: ~S~%" search walks reads seconds) (setf *last-checks* (reverse topic-maps.ctm.tests::*checks*)) (format t "~&ASSOCIATION-INDEX-PASS: ~D checks; ~D documents, ~D API scenarios and ~D rejections equal to the outcomes recorded at 6162ed68.~%" (length *last-checks*) (length *documents*) (length *api-scenarios*) (length *rejections*)) *last-checks*))