FAILURE MAP
← Case archive

FA-31446 / Keyboard interactions / Open access

Overlapping keyboard sequence matcher: A timer expires a valid exact-boundary sequence or uses absolute time · case 01

The event trace violates the tick expiry rule and produces incorrect keyboard state or command output.

Verified by executionVariant 1 · 10 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

A timer expires a valid exact-boundary sequence or uses absolute time.

VERIFIED REPAIR

Use the contract transition `if last is not None and now-last>timeout: buffer=[]; last=None` at the tick expiry fault site; preserve the other state transitions.

Unsuccessful approach: The partial repair changes this transition to if last is not None and now>timeout: buffer=[]; last=None, which still violates the model contract on the explicit regression traces.

Case contract

Case [sequence,timeout,events]. Nonempty sequence is list of key names. Events [kind,key,time,repeat]. Only nonrepeat down feeds matcher. Accepted downs more than timeout after the previous accepted down discard the prefix; tick likewise expires it. Cancel resets prefix and clock. Keep longest suffix matching a sequence prefix, and after a match retain the longest proper overlapping prefix. Return match timestamps, partial prefix and last accepted time. Inputs are finite ordered event traces; return the stated deterministic state. Batch entries are independent. N varies the number of independent input transactions.

Why this case matters

Controlled keyboard event processing model for debugging application event logic.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(cases):
    def run(c):
        sequence,timeout,events=c
        buffer=[]; last=None; matches=[]
        for kind,key,now,repeat in events:
            if kind=='cancel': buffer=[]; last=None
            elif kind=='tick':
                if last is not None and now-last>=timeout: buffer=[]; last=None
            elif kind=='down' and not repeat:
                if last is not None and now-last>timeout: buffer=[]
                candidate=buffer+[key]
                last=now
                buffer=[]
                for size in range(min(len(sequence),len(candidate)),0,-1):
                    if candidate[-size:]==sequence[:size]:
                        buffer=candidate[-size:]
                        break
                if buffer==sequence:
                    matches.append(now)
                    buffer=[]
                    for size in range(len(sequence)-1,0,-1):
                        if sequence[-size:]==sequence[:size]:
                            buffer=sequence[:size]
                            break
        return [matches,buffer,last]
    return [run(c) for c in cases]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('sequence-prefix scenario 0', solve([[['A', 'B'], 5, []]] * N), [[[], [], None]] * N)
check('sequence-prefix scenario 1', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 15, False]]]] * N), [[[15], [], 15]] * N)
check('sequence-prefix scenario 2', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['tick', '', 15, False]]]] * N), [[[], ['A'], 10]] * N)
check('sequence-prefix scenario 3', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 16, False]]]] * N), [[[], [], 16]] * N)
check('sequence-prefix scenario 4', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 11, True], ['up', 'B', 12, False]]]] * N), [[[], ['A'], 10]] * N)
check('sequence-prefix scenario 5', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['cancel', '', 11, False]]]] * N), [[[], [], None]] * N)
check('sequence-prefix scenario 6', solve([[['A', 'B', 'A'], 5, [['down', 'A', 10, False], ['down', 'B', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'A', 14, False]]]] * N), [[[12, 14], ['A'], 14]] * N)
check('sequence-prefix scenario 7', solve([[['A', 'B', 'A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'A', 14, False], ['down', 'B', 15, False]]]] * N), [[[13, 15], ['A', 'B'], 15]] * N)
check('sequence-prefix scenario 8', solve([[['A', 'A', 'B'], 5, [['down', 'A', 10, False], ['down', 'A', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False]]]] * N), [[[13], [], 13]] * N)
check('sequence-prefix scenario 9', solve([[['A', 'B', 'C'], 5, [['down', 'A', 10, False], ['down', 'X', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'C', 14, False]]]] * N), [[[14], [], 14]] * N)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
sequence-prefix scenario 0[[[], [], None]][[[], [], None]]Passed
sequence-prefix scenario 1[[[15], [], 15]][[[15], [], 15]]Passed
sequence-prefix scenario 2[[[], [], None]][[[], ['A'], 10]]Failed
sequence-prefix scenario 3[[[], [], 16]][[[], [], 16]]Passed
sequence-prefix scenario 4[[[], ['A'], 10]][[[], ['A'], 10]]Passed
sequence-prefix scenario 5[[[], [], None]][[[], [], None]]Passed
sequence-prefix scenario 6[[[12, 14], ['A'], 14]][[[12, 14], ['A'], 14]]Passed
sequence-prefix scenario 7[[[13, 15], ['A', 'B'], 15]][[[13, 15], ['A', 'B'], 15]]Passed
sequence-prefix scenario 8[[[13], [], 13]][[[13], [], 13]]Passed
sequence-prefix scenario 9[[[14], [], 14]][[[14], [], 14]]Passed

SHA-256 / 7888a1e798c29aed84a194b1aa00ff11dad2f008e94012fb9f3fffb5e4459039

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(cases):
    def run(c):
        sequence,timeout,events=c
        buffer=[]; last=None; matches=[]
        for kind,key,now,repeat in events:
            if kind=='cancel': buffer=[]; last=None
            elif kind=='tick':
                if last is not None and now>timeout: buffer=[]; last=None
            elif kind=='down' and not repeat:
                if last is not None and now-last>timeout: buffer=[]
                candidate=buffer+[key]
                last=now
                buffer=[]
                for size in range(min(len(sequence),len(candidate)),0,-1):
                    if candidate[-size:]==sequence[:size]:
                        buffer=candidate[-size:]
                        break
                if buffer==sequence:
                    matches.append(now)
                    buffer=[]
                    for size in range(len(sequence)-1,0,-1):
                        if sequence[-size:]==sequence[:size]:
                            buffer=sequence[:size]
                            break
        return [matches,buffer,last]
    return [run(c) for c in cases]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('sequence-prefix scenario 0', solve([[['A', 'B'], 5, []]] * N), [[[], [], None]] * N)
check('sequence-prefix scenario 1', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 15, False]]]] * N), [[[15], [], 15]] * N)
check('sequence-prefix scenario 2', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['tick', '', 15, False]]]] * N), [[[], ['A'], 10]] * N)
check('sequence-prefix scenario 3', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 16, False]]]] * N), [[[], [], 16]] * N)
check('sequence-prefix scenario 4', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 11, True], ['up', 'B', 12, False]]]] * N), [[[], ['A'], 10]] * N)
check('sequence-prefix scenario 5', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['cancel', '', 11, False]]]] * N), [[[], [], None]] * N)
check('sequence-prefix scenario 6', solve([[['A', 'B', 'A'], 5, [['down', 'A', 10, False], ['down', 'B', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'A', 14, False]]]] * N), [[[12, 14], ['A'], 14]] * N)
check('sequence-prefix scenario 7', solve([[['A', 'B', 'A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'A', 14, False], ['down', 'B', 15, False]]]] * N), [[[13, 15], ['A', 'B'], 15]] * N)
check('sequence-prefix scenario 8', solve([[['A', 'A', 'B'], 5, [['down', 'A', 10, False], ['down', 'A', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False]]]] * N), [[[13], [], 13]] * N)
check('sequence-prefix scenario 9', solve([[['A', 'B', 'C'], 5, [['down', 'A', 10, False], ['down', 'X', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'C', 14, False]]]] * N), [[[14], [], 14]] * N)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
sequence-prefix scenario 0[[[], [], None]][[[], [], None]]Passed
sequence-prefix scenario 1[[[15], [], 15]][[[15], [], 15]]Passed
sequence-prefix scenario 2[[[], [], None]][[[], ['A'], 10]]Failed
sequence-prefix scenario 3[[[], [], 16]][[[], [], 16]]Passed
sequence-prefix scenario 4[[[], ['A'], 10]][[[], ['A'], 10]]Passed
sequence-prefix scenario 5[[[], [], None]][[[], [], None]]Passed
sequence-prefix scenario 6[[[12, 14], ['A'], 14]][[[12, 14], ['A'], 14]]Passed
sequence-prefix scenario 7[[[13, 15], ['A', 'B'], 15]][[[13, 15], ['A', 'B'], 15]]Passed
sequence-prefix scenario 8[[[13], [], 13]][[[13], [], 13]]Passed
sequence-prefix scenario 9[[[14], [], 14]][[[14], [], 14]]Passed

SHA-256 / 75504365828932e3c9a6ba78d9da473d6097b600efbd912afcb30bfad960d5a1

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json

N = 1
observations = []
def solve(cases):
    def run(c):
        sequence,timeout,events=c
        buffer=[]; last=None; matches=[]
        for kind,key,now,repeat in events:
            if kind=='cancel': buffer=[]; last=None
            elif kind=='tick':
                if last is not None and now-last>timeout: buffer=[]; last=None
            elif kind=='down' and not repeat:
                if last is not None and now-last>timeout: buffer=[]
                candidate=buffer+[key]
                last=now
                buffer=[]
                for size in range(min(len(sequence),len(candidate)),0,-1):
                    if candidate[-size:]==sequence[:size]:
                        buffer=candidate[-size:]
                        break
                if buffer==sequence:
                    matches.append(now)
                    buffer=[]
                    for size in range(len(sequence)-1,0,-1):
                        if sequence[-size:]==sequence[:size]:
                            buffer=sequence[:size]
                            break
        return [matches,buffer,last]
    return [run(c) for c in cases]
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
check('sequence-prefix scenario 0', solve([[['A', 'B'], 5, []]] * N), [[[], [], None]] * N)
check('sequence-prefix scenario 1', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 15, False]]]] * N), [[[15], [], 15]] * N)
check('sequence-prefix scenario 2', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['tick', '', 15, False]]]] * N), [[[], ['A'], 10]] * N)
check('sequence-prefix scenario 3', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 16, False]]]] * N), [[[], [], 16]] * N)
check('sequence-prefix scenario 4', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 11, True], ['up', 'B', 12, False]]]] * N), [[[], ['A'], 10]] * N)
check('sequence-prefix scenario 5', solve([[['A', 'B'], 5, [['down', 'A', 10, False], ['cancel', '', 11, False]]]] * N), [[[], [], None]] * N)
check('sequence-prefix scenario 6', solve([[['A', 'B', 'A'], 5, [['down', 'A', 10, False], ['down', 'B', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'A', 14, False]]]] * N), [[[12, 14], ['A'], 14]] * N)
check('sequence-prefix scenario 7', solve([[['A', 'B', 'A', 'B'], 5, [['down', 'A', 10, False], ['down', 'B', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'A', 14, False], ['down', 'B', 15, False]]]] * N), [[[13, 15], ['A', 'B'], 15]] * N)
check('sequence-prefix scenario 8', solve([[['A', 'A', 'B'], 5, [['down', 'A', 10, False], ['down', 'A', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False]]]] * N), [[[13], [], 13]] * N)
check('sequence-prefix scenario 9', solve([[['A', 'B', 'C'], 5, [['down', 'A', 10, False], ['down', 'X', 11, False], ['down', 'A', 12, False], ['down', 'B', 13, False], ['down', 'C', 14, False]]]] * N), [[[14], [], 14]] * N)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
sequence-prefix scenario 0[[[], [], None]][[[], [], None]]Passed
sequence-prefix scenario 1[[[15], [], 15]][[[15], [], 15]]Passed
sequence-prefix scenario 2[[[], ['A'], 10]][[[], ['A'], 10]]Passed
sequence-prefix scenario 3[[[], [], 16]][[[], [], 16]]Passed
sequence-prefix scenario 4[[[], ['A'], 10]][[[], ['A'], 10]]Passed
sequence-prefix scenario 5[[[], [], None]][[[], [], None]]Passed
sequence-prefix scenario 6[[[12, 14], ['A'], 14]][[[12, 14], ['A'], 14]]Passed
sequence-prefix scenario 7[[[13, 15], ['A', 'B'], 15]][[[13, 15], ['A', 'B'], 15]]Passed
sequence-prefix scenario 8[[[13], [], 13]][[[13], [], 13]]Passed
sequence-prefix scenario 9[[[14], [], 14]][[[14], [], 14]]Passed

SHA-256 / 07ca1aca25789f6c51484071e2ada1e97c6d1b587e4d1f28d02b6a39885e9687

Verification & scope

Offline stipulated event model, not a browser implementation or web standard conformance claim. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:42:02.183498+00:00.

Case digest / 593643a7ee67a600efa11bde532affb5f22520904760ff877b9e78035562463c