FAILURE MAP
← Case archive

FA-31486 / Keyboard interactions / Open access

Overlapping keyboard sequence matcher: Sequence completion loses a multi-key overlapping prefix for the next match · case 01

The event trace violates the overlap retention rule and produces incorrect keyboard state or command output.

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

ROOT CAUSE

Sequence completion loses a multi-key overlapping prefix for the next match.

VERIFIED REPAIR

Use the contract transition `buffer=sequence[:size] break` at the overlap retention fault site; preserve the other state transitions.

Unsuccessful approach: The partial repair changes this transition to buffer=sequence[-1:] break, 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=[]
                            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], ['A'], 14]][[[12, 14], ['A'], 14]]Failed
sequence-prefix scenario 7[[[13], ['A', 'B'], 15]][[[13, 15], ['A', 'B'], 15]]Failed
sequence-prefix scenario 8[[[13], [], 13]][[[13], [], 13]]Passed
sequence-prefix scenario 9[[[14], [], 14]][[[14], [], 14]]Passed

SHA-256 / 7de1fc8b2025e6b19b285ace2022b6fb10a1359de8c7bbbf926136c1ba7b59bc

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-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[-1:]
                            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], ['A', 'B'], 15]][[[13, 15], ['A', 'B'], 15]]Failed
sequence-prefix scenario 8[[[13], [], 13]][[[13], [], 13]]Passed
sequence-prefix scenario 9[[[14], [], 14]][[[14], [], 14]]Passed

SHA-256 / 0cddb93a221e9e5cf3c0002cfeed9ac3211aecc7948c6ba95cab76d4eb59a88d

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.567274+00:00.

Case digest / 8db78dfc4f5d711cedc749ca6051a0dbd0c9193dd4938b5725542f136fc21611