File size: 2,331 Bytes
450ac2f | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 | import pytest
from crosswire.core import CandidateSpace, Contract, Machine
def _machine():
transitions = (((1, 0), (0, 3), (1, 2)), ((1, 1), (1, 1), (1, 2)))
return Machine("test", transitions, 3, 4, 0)
def test_cegp_policy_selects_distinguishing_probe():
m = _machine()
c = Contract(goal=1, hazard=2, horizon=4)
space = CandidateSpace(m, c)
survivors = tuple(range(10)) # subset of adapters
seen = set()
probe = space.choose_probe(survivors, "counterexample", remaining_steps=3, seen=seen)
assert probe is not None
assert 1 <= len(probe) <= 3
# Check that the probe actually separates at least two surviving adapters
preds = {aid: space.predict(aid, probe) for aid in survivors}
assert len(set(preds.values())) > 1
def test_cegp_respects_remaining_steps_and_seen():
m = _machine()
c = Contract(goal=1, hazard=2, horizon=4)
space = CandidateSpace(m, c)
survivors = (0, 1, 2)
seen = {(0,), (1,), (2,)}
probe = space.choose_probe(survivors, "counterexample", remaining_steps=1, seen=seen)
# Since all 1-symbol words are seen, and remaining_steps=1, no eligible probe remains
assert probe is None
def test_cegp_synthesizes_extended_distinguishing_witness_beyond_pool():
from crosswire.fixtures import make_case
case = make_case("long_trace", seed=17)
space = CandidateSpace(Machine.from_dict(case.public["reference"]), Contract.from_dict(case.public["contract"]))
# In long_trace, adapters 4 and 65 only differ at length 4 (transitions after 3 advances)
# Standard 3-step probes cannot distinguish them:
for w in space._probes:
assert space.predict(4, w) == space.predict(65, w)
# But distinguishing_word finds the 4-step witness!
witness = space.distinguishing_word(4, 65, max_length=6)
assert witness is not None
assert len(witness) == 4
assert space.predict(4, witness) != space.predict(65, witness)
# And choose_probe with counterexample policy selects it when given remaining_steps >= 4!
seen = set(space._probes)
probe = space.choose_probe((4, 65), "counterexample", remaining_steps=4, seen=seen)
assert probe is not None
assert len(probe) == 4
assert space.predict(4, probe) != space.predict(65, probe)
|