File size: 2,279 Bytes
44810a8 | 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 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | import pytest
import torch
from core.fsm_builder import ReachabilityFSM
def test_fsm_basic_reachability():
# Linear graph: 0 -> 1 -> 2 (Goal)
vocab_size = 10
fsm = ReachabilityFSM(num_states=3, vocab_size=vocab_size)
fsm.add_transition(0, token_id=1, to_state=1)
fsm.add_transition(1, token_id=2, to_state=2)
fsm.set_goal_states([2])
# Max steps = 2
reach = fsm.build_reachability(max_steps=2, allow_early_finish=True)
# t = 0: only state 2 is True
assert reach[0, 2].item() is True
assert reach[0, 1].item() is False
assert reach[0, 0].item() is False
# t = 1: state 1 and 2 are True
assert reach[1, 2].item() is True
assert reach[1, 1].item() is True
assert reach[1, 0].item() is False
# t = 2: state 0, 1, 2 are all True
assert reach[2, 0].item() is True
assert reach[2, 1].item() is True
assert reach[2, 2].item() is True
def test_fsm_deadend_reachability():
# Branching graph:
# 0 -> 1 -> 2 (Goal) via token 1, 2 (needs 2 steps)
# 0 -> 3 -> 4 (Dead-end) via token 3, 4 (sink)
vocab_size = 10
fsm = ReachabilityFSM(num_states=5, vocab_size=vocab_size)
fsm.add_transition(0, token_id=1, to_state=1)
fsm.add_transition(1, token_id=2, to_state=2)
fsm.add_transition(0, token_id=3, to_state=3)
fsm.add_transition(3, token_id=4, to_state=4)
fsm.set_goal_states([2])
reach = fsm.build_reachability(max_steps=5, allow_early_finish=True)
# States 3 and 4 should NEVER be reachable to goal
for t in range(6):
assert reach[t, 3].item() is False
assert reach[t, 4].item() is False
# State 0 is reachable only when t >= 2
assert reach[0, 0].item() is False
assert reach[1, 0].item() is False
assert reach[2, 0].item() is True
assert reach[3, 0].item() is True
def test_fsm_multi_goal():
# 0 -> 1 (Goal A), 0 -> 2 (Goal B)
vocab_size = 5
fsm = ReachabilityFSM(num_states=3, vocab_size=vocab_size)
fsm.add_transition(0, 1, 1)
fsm.add_transition(0, 2, 2)
fsm.set_goal_states([1, 2])
reach = fsm.build_reachability(max_steps=1)
assert reach[0, 1].item() is True
assert reach[0, 2].item() is True
assert reach[0, 0].item() is False
assert reach[1, 0].item() is True
|