use std::cmp::Ordering;
use std::collections::{HashMap, HashSet};
use std::error::Error;
use std::fmt;
use super::config::{
ButtonConfig, ChordConfig, ChordReleasePolicy, ConfigError, FrameworkConfig, GestureConfig,
};
use super::types::{ButtonEdge, ButtonPhase, ChordId, ControlEdge, ControlId, KeyId, Timestamp};
#[derive(Debug, Clone)]
struct ChordRule {
config: ChordConfig,
members: HashSet<KeyId>,
}
#[derive(Debug, Clone, Copy)]
struct Eligibility {
rule: usize,
deadline: Timestamp,
}
#[derive(Debug, Clone)]
struct PendingDown {
edge: ButtonEdge,
order: u64,
eligible: Vec<Eligibility>,
}
#[derive(Debug, Clone)]
struct ActiveChord {
rule: usize,
pressed_members: HashSet<KeyId>,
up_emitted: bool,
}
#[derive(Debug, Clone, Copy)]
struct OrderedInput {
edge: ButtonEdge,
order: u64,
}
#[derive(Debug, Clone, Copy)]
struct OrderedOutput {
edge: ControlEdge,
order: u64,
}
#[derive(Debug, Clone)]
pub struct ChordResolver {
rules: Vec<ChordRule>,
rules_by_key: HashMap<KeyId, Vec<usize>>,
pending: HashMap<KeyId, PendingDown>,
active: Vec<ActiveChord>,
last_update: Option<Timestamp>,
next_order: u64,
}
impl ChordResolver {
pub fn try_new(chords: &[ChordConfig]) -> Result<Self, ConfigError> {
let mut keys = HashSet::new();
for chord in chords {
keys.extend(chord.members.iter().copied());
}
let config = FrameworkConfig {
buttons: keys
.into_iter()
.map(|key| ButtonConfig::active_low(key, std::time::Duration::ZERO))
.collect(),
chords: chords.to_vec(),
default_gestures: GestureConfig::default(),
gesture_overrides: HashMap::new(),
};
config.validate()?;
Ok(Self::new_validated(chords))
}
pub(crate) fn new_validated(chords: &[ChordConfig]) -> Self {
let rules: Vec<_> = chords
.iter()
.cloned()
.map(|config| ChordRule {
members: config.members.iter().copied().collect(),
config,
})
.collect();
let mut rules_by_key: HashMap<KeyId, Vec<usize>> = HashMap::new();
for (index, rule) in rules.iter().enumerate() {
for &key in &rule.config.members {
rules_by_key.entry(key).or_default().push(index);
}
}
Self {
rules,
rules_by_key,
pending: HashMap::new(),
active: Vec::new(),
last_update: None,
next_order: 0,
}
}
#[cfg(test)]
fn new(chords: &[ChordConfig]) -> Self {
Self::try_new(chords).expect("test chord configuration is valid")
}
pub fn pending_keys(&self) -> Vec<KeyId> {
let mut pending: Vec<_> = self.pending.values().collect();
pending.sort_by_key(|entry| entry.order);
pending.into_iter().map(|entry| entry.edge.key).collect()
}
pub fn next_deadline(&self) -> Option<Timestamp> {
self.pending
.values()
.flat_map(|pending| pending.eligible.iter())
.map(|eligible| eligible.deadline)
.min()
}
pub fn advance_before(&mut self, now: Timestamp) -> Result<Vec<ControlEdge>, ChordError> {
self.ensure_monotonic(now)?;
let output = self.expire_eligibility(now, false);
self.last_update = Some(now);
Ok(output)
}
pub fn advance_through(&mut self, now: Timestamp) -> Result<Vec<ControlEdge>, ChordError> {
self.ensure_monotonic(now)?;
let output = self.expire_eligibility(now, true);
self.last_update = Some(now);
Ok(output)
}
pub fn process_batch(
&mut self,
now: Timestamp,
edges: &[ButtonEdge],
) -> Result<Vec<ControlEdge>, ChordError> {
self.validate_batch(now, edges)?;
let mut output = self.expire_eligibility(now, false);
let base_order = self.next_order;
self.next_order += edges.len() as u64;
let input: Vec<_> = edges
.iter()
.copied()
.enumerate()
.map(|(index, edge)| OrderedInput {
edge,
order: base_order + index as u64,
})
.collect();
let (mut active_output, captured) = self.apply_active_edges(&input);
let mut individual_output = Vec::new();
for item in input
.iter()
.filter(|item| item.edge.phase == ButtonPhase::Up)
{
if captured.contains(&item.edge.key) {
continue;
}
if let Some(pending) = self.pending.remove(&item.edge.key) {
let recognized_at = pending.edge.recognized_at.max(item.edge.recognized_at);
individual_output.push(OrderedOutput {
edge: key_control_edge(pending.edge, recognized_at),
order: pending.order,
});
individual_output.push(OrderedOutput {
edge: key_control_edge(item.edge, recognized_at),
order: item.order,
});
} else {
individual_output.push(OrderedOutput {
edge: key_control_edge(item.edge, item.edge.recognized_at),
order: item.order,
});
}
}
for item in input
.iter()
.filter(|item| item.edge.phase == ButtonPhase::Down)
{
if captured.contains(&item.edge.key) {
continue;
}
let eligible = self.eligibility_for(item.edge);
if eligible.is_empty() {
individual_output.push(OrderedOutput {
edge: key_control_edge(item.edge, item.edge.recognized_at),
order: item.order,
});
} else {
self.pending.insert(
item.edge.key,
PendingDown {
edge: item.edge,
order: item.order,
eligible,
},
);
}
}
let mut chord_output = self.activate_complete_chords();
individual_output.extend(self.remove_blocked_eligibility(now));
sort_ordered_output(&mut individual_output);
active_output.sort_by(|left, right| {
left.edge
.occurred_at
.cmp(&right.edge.occurred_at)
.then_with(|| left.order.cmp(&right.order))
.then_with(|| left.edge.control.cmp(&right.edge.control))
});
output.extend(active_output.into_iter().map(|item| item.edge));
output.append(&mut chord_output);
output.extend(individual_output.into_iter().map(|item| item.edge));
output.extend(self.expire_eligibility(now, true));
self.last_update = Some(now);
Ok(output)
}
fn ensure_monotonic(&self, now: Timestamp) -> Result<(), ChordError> {
if let Some(previous) = self.last_update {
if now < previous {
return Err(ChordError::TimeRegression { previous, now });
}
}
Ok(())
}
fn validate_batch(&self, now: Timestamp, edges: &[ButtonEdge]) -> Result<(), ChordError> {
self.ensure_monotonic(now)?;
let count = u64::try_from(edges.len()).map_err(|_| ChordError::OrderOverflow)?;
self.next_order
.checked_add(count)
.ok_or(ChordError::OrderOverflow)?;
let mut seen = HashSet::with_capacity(edges.len());
for edge in edges {
if !seen.insert(edge.key) {
return Err(ChordError::DuplicateKeyInBatch(edge.key));
}
if edge.occurred_at > edge.recognized_at {
return Err(ChordError::InvalidEdgeCausality {
key: edge.key,
occurred_at: edge.occurred_at,
recognized_at: edge.recognized_at,
});
}
if edge.recognized_at > now {
return Err(ChordError::EdgeAfterBatch {
key: edge.key,
recognized_at: edge.recognized_at,
batch_at: now,
});
}
if edge.phase != ButtonPhase::Down || self.captures(edge.key) {
continue;
}
if let Some(pending) = self.pending.get(&edge.key) {
if pending
.eligible
.iter()
.any(|eligible| eligible.deadline >= now)
{
return Err(ChordError::DuplicatePendingDown(edge.key));
}
}
if let Some(rule_indices) = self.rules_by_key.get(&edge.key) {
for &rule in rule_indices {
edge.occurred_at
.checked_add(self.rules[rule].config.window)
.ok_or(ChordError::DeadlineOverflow {
chord: self.rules[rule].config.id,
key: edge.key,
started_at: edge.occurred_at,
})?;
}
}
}
Ok(())
}
fn eligibility_for(&self, edge: ButtonEdge) -> Vec<Eligibility> {
let Some(rule_indices) = self.rules_by_key.get(&edge.key) else {
return Vec::new();
};
let captured = self.captured_keys();
rule_indices
.iter()
.copied()
.filter(|&rule| self.rules[rule].members.is_disjoint(&captured))
.map(|rule| Eligibility {
rule,
deadline: edge
.occurred_at
.checked_add(self.rules[rule].config.window)
.expect("deadline overflow is validated before mutation"),
})
.collect()
}
fn captured_keys(&self) -> HashSet<KeyId> {
self.active
.iter()
.flat_map(|active| self.rules[active.rule].config.members.iter().copied())
.collect()
}
fn captures(&self, key: KeyId) -> bool {
self.active
.iter()
.any(|active| self.rules[active.rule].members.contains(&key))
}
fn apply_active_edges(
&mut self,
input: &[OrderedInput],
) -> (Vec<OrderedOutput>, HashSet<KeyId>) {
let captured = self.captured_keys();
let mut output = Vec::new();
for active in &mut self.active {
let rule = &self.rules[active.rule];
let relevant: Vec<_> = input
.iter()
.copied()
.filter(|item| rule.members.contains(&item.edge.key))
.collect();
if relevant.is_empty() {
continue;
}
for item in &relevant {
match item.edge.phase {
ButtonPhase::Down => {
active.pressed_members.insert(item.edge.key);
}
ButtonPhase::Up => {
active.pressed_members.remove(&item.edge.key);
}
}
}
let trigger = match rule.config.release {
ChordReleasePolicy::AnyMember if !active.up_emitted => relevant
.iter()
.filter(|item| item.edge.phase == ButtonPhase::Up)
.min_by_key(|item| (item.edge.occurred_at, item.order))
.copied(),
ChordReleasePolicy::AllMembers
if !active.up_emitted && active.pressed_members.is_empty() =>
{
relevant
.iter()
.filter(|item| item.edge.phase == ButtonPhase::Up)
.max_by_key(|item| (item.edge.occurred_at, item.order))
.copied()
}
_ => None,
};
if let Some(trigger) = trigger {
active.up_emitted = true;
output.push(OrderedOutput {
edge: ControlEdge {
control: ControlId::Chord(rule.config.id),
phase: ButtonPhase::Up,
occurred_at: trigger.edge.occurred_at,
recognized_at: trigger.edge.recognized_at,
},
order: trigger.order,
});
}
}
self.active
.retain(|active| !active.pressed_members.is_empty());
(output, captured)
}
fn activate_complete_chords(&mut self) -> Vec<ControlEdge> {
let mut complete: Vec<_> = (0..self.rules.len())
.filter(|&rule| self.rule_is_complete(rule))
.collect();
complete.sort_by(|&left, &right| compare_rules(&self.rules[left], &self.rules[right]));
let mut selected = Vec::new();
let mut claimed = HashSet::new();
for rule in complete {
if self.rules[rule].members.is_disjoint(&claimed) {
claimed.extend(self.rules[rule].members.iter().copied());
selected.push(rule);
}
}
let mut output = Vec::with_capacity(selected.len());
for rule_index in selected {
let rule = &self.rules[rule_index];
let occurred_at = rule
.config
.members
.iter()
.map(|key| self.pending[key].edge.occurred_at)
.max()
.expect("validated chords contain at least two members");
let recognized_at = rule
.config
.members
.iter()
.map(|key| self.pending[key].edge.recognized_at)
.max()
.expect("validated chords contain at least two members")
.max(occurred_at);
output.push(ControlEdge {
control: ControlId::Chord(rule.config.id),
phase: ButtonPhase::Down,
occurred_at,
recognized_at,
});
for key in &rule.config.members {
self.pending.remove(key);
}
self.active.push(ActiveChord {
rule: rule_index,
pressed_members: rule.members.clone(),
up_emitted: false,
});
}
output
}
fn rule_is_complete(&self, rule_index: usize) -> bool {
let rule = &self.rules[rule_index];
let mut earliest = None;
let mut latest = None;
for key in &rule.config.members {
let Some(pending) = self.pending.get(key) else {
return false;
};
if !pending
.eligible
.iter()
.any(|eligible| eligible.rule == rule_index)
{
return false;
}
earliest = Some(
earliest.map_or(pending.edge.occurred_at, |value: Timestamp| {
value.min(pending.edge.occurred_at)
}),
);
latest = Some(latest.map_or(pending.edge.occurred_at, |value: Timestamp| {
value.max(pending.edge.occurred_at)
}));
}
latest
.expect("validated chords have members")
.checked_duration_since(earliest.expect("validated chords have members"))
.is_some_and(|span| span <= rule.config.window)
}
fn remove_blocked_eligibility(&mut self, now: Timestamp) -> Vec<OrderedOutput> {
let captured = self.captured_keys();
let mut orphaned = Vec::new();
for (&key, pending) in &mut self.pending {
pending
.eligible
.retain(|eligible| self.rules[eligible.rule].members.is_disjoint(&captured));
if pending.eligible.is_empty() {
orphaned.push(key);
}
}
orphaned
.into_iter()
.map(|key| {
let pending = self
.pending
.remove(&key)
.expect("orphaned pending key still exists");
OrderedOutput {
edge: key_control_edge(pending.edge, now),
order: pending.order,
}
})
.collect()
}
fn expire_eligibility(&mut self, now: Timestamp, inclusive: bool) -> Vec<ControlEdge> {
let mut orphaned = Vec::new();
for (&key, pending) in &mut self.pending {
let mut final_deadline = None;
pending.eligible.retain(|eligible| {
let expired = if inclusive {
eligible.deadline <= now
} else {
eligible.deadline < now
};
if expired {
final_deadline = Some(
final_deadline.map_or(eligible.deadline, |deadline: Timestamp| {
deadline.max(eligible.deadline)
}),
);
}
!expired
});
if pending.eligible.is_empty() {
orphaned.push((key, final_deadline.expect("an orphan lost an eligibility")));
}
}
let mut output: Vec<_> = orphaned
.into_iter()
.map(|(key, deadline)| {
let pending = self
.pending
.remove(&key)
.expect("orphaned pending key still exists");
OrderedOutput {
edge: key_control_edge(pending.edge, deadline),
order: pending.order,
}
})
.collect();
sort_ordered_output(&mut output);
output.into_iter().map(|item| item.edge).collect()
}
}
fn compare_rules(left: &ChordRule, right: &ChordRule) -> Ordering {
right
.config
.priority
.cmp(&left.config.priority)
.then_with(|| right.config.members.len().cmp(&left.config.members.len()))
.then_with(|| left.config.id.cmp(&right.config.id))
}
fn key_control_edge(edge: ButtonEdge, recognized_floor: Timestamp) -> ControlEdge {
ControlEdge {
control: ControlId::Key(edge.key),
phase: edge.phase,
occurred_at: edge.occurred_at,
recognized_at: edge.recognized_at.max(recognized_floor),
}
}
fn sort_ordered_output(output: &mut [OrderedOutput]) {
output.sort_by(|left, right| {
left.edge
.occurred_at
.cmp(&right.edge.occurred_at)
.then_with(|| left.order.cmp(&right.order))
});
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ChordError {
TimeRegression {
previous: Timestamp,
now: Timestamp,
},
InvalidEdgeCausality {
key: KeyId,
occurred_at: Timestamp,
recognized_at: Timestamp,
},
EdgeAfterBatch {
key: KeyId,
recognized_at: Timestamp,
batch_at: Timestamp,
},
DuplicateKeyInBatch(KeyId),
DuplicatePendingDown(KeyId),
DeadlineOverflow {
chord: ChordId,
key: KeyId,
started_at: Timestamp,
},
OrderOverflow,
}
impl fmt::Display for ChordError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::TimeRegression { previous, now } => {
write!(f, "chord resolver time regressed from {previous} to {now}")
}
Self::InvalidEdgeCausality {
key,
occurred_at,
recognized_at,
} => write!(
f,
"{key} occurred at {occurred_at} after recognition at {recognized_at}"
),
Self::EdgeAfterBatch {
key,
recognized_at,
batch_at,
} => write!(
f,
"{key} was recognized at {recognized_at}, after batch time {batch_at}"
),
Self::DuplicateKeyInBatch(key) => {
write!(f, "batch contains more than one edge for {key}")
}
Self::DuplicatePendingDown(key) => {
write!(f, "received another down edge while {key} is pending")
}
Self::DeadlineOverflow {
chord,
key,
started_at,
} => write!(
f,
"{chord} deadline overflows for {key} pressed at {started_at}"
),
Self::OrderOverflow => write!(f, "chord resolver input order counter overflowed"),
}
}
}
impl Error for ChordError {}
#[cfg(test)]
mod tests {
use std::time::Duration;
use super::*;
fn time(ms: u64) -> Timestamp {
Timestamp::from_millis(ms)
}
fn chord(
id: u16,
members: &[u16],
window_ms: u64,
priority: i16,
release: ChordReleasePolicy,
) -> ChordConfig {
ChordConfig {
id: ChordId(id),
members: members.iter().copied().map(KeyId).collect(),
window: Duration::from_millis(window_ms),
priority,
release,
}
}
fn edge(key: u16, phase: ButtonPhase, occurred_ms: u64, recognized_ms: u64) -> ButtonEdge {
ButtonEdge {
key: KeyId(key),
phase,
occurred_at: time(occurred_ms),
recognized_at: time(recognized_ms),
}
}
fn at(key: u16, phase: ButtonPhase, ms: u64) -> ButtonEdge {
edge(key, phase, ms, ms)
}
fn key_edge(key: u16, phase: ButtonPhase, occurred: u64, recognized: u64) -> ControlEdge {
ControlEdge {
control: ControlId::Key(KeyId(key)),
phase,
occurred_at: time(occurred),
recognized_at: time(recognized),
}
}
fn chord_edge(id: u16, phase: ButtonPhase, occurred: u64, recognized: u64) -> ControlEdge {
ControlEdge {
control: ControlId::Chord(ChordId(id)),
phase,
occurred_at: time(occurred),
recognized_at: time(recognized),
}
}
#[test]
fn non_member_edges_pass_through_immediately() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
assert_eq!(
resolver.process_batch(time(10), &[at(9, ButtonPhase::Down, 10)]),
Ok(vec![key_edge(9, ButtonPhase::Down, 10, 10)])
);
assert_eq!(
resolver.process_batch(time(20), &[at(9, ButtonPhase::Up, 20)]),
Ok(vec![key_edge(9, ButtonPhase::Up, 20, 20)])
);
}
#[test]
fn first_member_is_pending_until_its_deadline() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
assert_eq!(
resolver.process_batch(time(10), &[at(1, ButtonPhase::Down, 10)]),
Ok(Vec::new())
);
assert_eq!(resolver.pending_keys(), vec![KeyId(1)]);
assert_eq!(resolver.next_deadline(), Some(time(60)));
}
#[test]
fn exact_window_endpoint_matches_before_expiry() {
let mut resolver =
ChordResolver::new(&[chord(7, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(time(0), &[at(1, ButtonPhase::Down, 0)])
.unwrap();
assert_eq!(
resolver.process_batch(time(50), &[at(2, ButtonPhase::Down, 50)]),
Ok(vec![chord_edge(7, ButtonPhase::Down, 50, 50)])
);
assert!(resolver.pending_keys().is_empty());
assert_eq!(resolver.next_deadline(), None);
}
#[test]
fn zero_window_requires_members_in_the_same_atomic_batch() {
let config = [chord(1, &[1, 2], 0, 0, ChordReleasePolicy::AnyMember)];
let mut resolver = ChordResolver::new(&config);
assert_eq!(
resolver.process_batch(
time(0),
&[at(1, ButtonPhase::Down, 0), at(2, ButtonPhase::Down, 0)],
),
Ok(vec![chord_edge(1, ButtonPhase::Down, 0, 0)])
);
let mut resolver = ChordResolver::new(&config);
assert_eq!(
resolver.process_batch(time(0), &[at(1, ButtonPhase::Down, 0)]),
Ok(vec![key_edge(1, ButtonPhase::Down, 0, 0)])
);
assert_eq!(
resolver.process_batch(time(0), &[at(2, ButtonPhase::Down, 0)]),
Ok(vec![key_edge(2, ButtonPhase::Down, 0, 0)])
);
}
#[test]
fn member_after_window_replays_first_down() {
let mut resolver =
ChordResolver::new(&[chord(7, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(time(0), &[at(1, ButtonPhase::Down, 0)])
.unwrap();
assert_eq!(
resolver.process_batch(time(51), &[at(2, ButtonPhase::Down, 51)]),
Ok(vec![key_edge(1, ButtonPhase::Down, 0, 50)])
);
assert_eq!(resolver.pending_keys(), vec![KeyId(2)]);
}
#[test]
fn early_up_replays_down_then_up_with_causal_recognition() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(time(10), &[edge(1, ButtonPhase::Down, 5, 10)])
.unwrap();
assert_eq!(
resolver.process_batch(time(20), &[at(1, ButtonPhase::Up, 20)]),
Ok(vec![
key_edge(1, ButtonPhase::Down, 5, 20),
key_edge(1, ButtonPhase::Up, 20, 20),
])
);
}
#[test]
fn early_up_replay_preserves_global_original_order() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2, 3], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(time(0), &[at(1, ButtonPhase::Down, 0)])
.unwrap();
resolver
.process_batch(time(5), &[at(2, ButtonPhase::Down, 5)])
.unwrap();
assert_eq!(
resolver.process_batch(
time(10),
&[at(1, ButtonPhase::Up, 10), at(2, ButtonPhase::Up, 10)],
),
Ok(vec![
key_edge(1, ButtonPhase::Down, 0, 10),
key_edge(2, ButtonPhase::Down, 5, 10),
key_edge(1, ButtonPhase::Up, 10, 10),
key_edge(2, ButtonPhase::Up, 10, 10),
])
);
}
#[test]
fn before_excludes_endpoint_and_through_includes_it() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(time(0), &[at(1, ButtonPhase::Down, 0)])
.unwrap();
assert_eq!(resolver.advance_before(time(50)), Ok(Vec::new()));
assert_eq!(resolver.next_deadline(), Some(time(50)));
assert_eq!(
resolver.advance_through(time(50)),
Ok(vec![key_edge(1, ButtonPhase::Down, 0, 50)])
);
}
#[test]
fn different_windows_expire_independently() {
let mut resolver = ChordResolver::new(&[
chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember),
chord(2, &[1, 3], 100, 0, ChordReleasePolicy::AnyMember),
]);
resolver
.process_batch(time(0), &[at(1, ButtonPhase::Down, 0)])
.unwrap();
assert_eq!(resolver.next_deadline(), Some(time(50)));
assert_eq!(resolver.advance_through(time(50)), Ok(Vec::new()));
assert_eq!(resolver.pending_keys(), vec![KeyId(1)]);
assert_eq!(resolver.next_deadline(), Some(time(100)));
assert_eq!(
resolver.advance_through(time(100)),
Ok(vec![key_edge(1, ButtonPhase::Down, 0, 100)])
);
}
#[test]
fn late_advance_replays_multiple_timeouts_in_original_order() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2, 3], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(time(0), &[at(1, ButtonPhase::Down, 0)])
.unwrap();
resolver
.process_batch(time(5), &[at(2, ButtonPhase::Down, 5)])
.unwrap();
assert_eq!(
resolver.advance_through(time(100)),
Ok(vec![
key_edge(1, ButtonPhase::Down, 0, 50),
key_edge(2, ButtonPhase::Down, 5, 55),
])
);
}
#[test]
fn overlapping_complete_chords_choose_higher_priority() {
let mut resolver = ChordResolver::new(&[
chord(10, &[1, 2], 50, 1, ChordReleasePolicy::AnyMember),
chord(20, &[2, 3], 50, 2, ChordReleasePolicy::AnyMember),
]);
let output = resolver
.process_batch(
time(0),
&[
at(1, ButtonPhase::Down, 0),
at(2, ButtonPhase::Down, 0),
at(3, ButtonPhase::Down, 0),
],
)
.unwrap();
assert_eq!(
output,
vec![
chord_edge(20, ButtonPhase::Down, 0, 0),
key_edge(1, ButtonPhase::Down, 0, 0),
]
);
assert!(resolver.pending_keys().is_empty());
}
#[test]
fn unblocked_eligibility_survives_an_overlapping_chord_claim() {
let mut resolver = ChordResolver::new(&[
chord(1, &[1, 2], 50, 10, ChordReleasePolicy::AnyMember),
chord(2, &[2, 3], 50, 0, ChordReleasePolicy::AnyMember),
chord(3, &[3, 4], 50, 5, ChordReleasePolicy::AnyMember),
]);
assert_eq!(
resolver.process_batch(
time(0),
&[
at(1, ButtonPhase::Down, 0),
at(2, ButtonPhase::Down, 0),
at(3, ButtonPhase::Down, 0),
],
),
Ok(vec![chord_edge(1, ButtonPhase::Down, 0, 0)])
);
assert_eq!(resolver.pending_keys(), vec![KeyId(3)]);
assert_eq!(
resolver.process_batch(time(10), &[at(4, ButtonPhase::Down, 10)]),
Ok(vec![chord_edge(3, ButtonPhase::Down, 10, 10)])
);
}
#[test]
fn member_count_breaks_equal_priority_tie() {
let mut resolver = ChordResolver::new(&[
chord(10, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember),
chord(20, &[2, 3, 4], 50, 0, ChordReleasePolicy::AnyMember),
]);
let output = resolver
.process_batch(
time(0),
&[
at(1, ButtonPhase::Down, 0),
at(2, ButtonPhase::Down, 0),
at(3, ButtonPhase::Down, 0),
at(4, ButtonPhase::Down, 0),
],
)
.unwrap();
assert_eq!(output[0], chord_edge(20, ButtonPhase::Down, 0, 0));
assert!(output.contains(&key_edge(1, ButtonPhase::Down, 0, 0)));
}
#[test]
fn chord_id_breaks_equal_rank_tie() {
let mut resolver = ChordResolver::new(&[
chord(2, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember),
chord(1, &[2, 3], 50, 0, ChordReleasePolicy::AnyMember),
]);
let output = resolver
.process_batch(
time(0),
&[
at(1, ButtonPhase::Down, 0),
at(2, ButtonPhase::Down, 0),
at(3, ButtonPhase::Down, 0),
],
)
.unwrap();
assert_eq!(output[0], chord_edge(1, ButtonPhase::Down, 0, 0));
}
#[test]
fn disjoint_complete_chords_activate_together_in_rank_order() {
let mut resolver = ChordResolver::new(&[
chord(1, &[1, 2], 50, 1, ChordReleasePolicy::AnyMember),
chord(2, &[3, 4], 50, 5, ChordReleasePolicy::AnyMember),
]);
assert_eq!(
resolver.process_batch(
time(10),
&[
at(4, ButtonPhase::Down, 10),
at(2, ButtonPhase::Down, 10),
at(1, ButtonPhase::Down, 10),
at(3, ButtonPhase::Down, 10),
],
),
Ok(vec![
chord_edge(2, ButtonPhase::Down, 10, 10),
chord_edge(1, ButtonPhase::Down, 10, 10),
])
);
}
#[test]
fn any_member_release_emits_once_and_suppresses_until_all_are_up() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(
time(0),
&[at(1, ButtonPhase::Down, 0), at(2, ButtonPhase::Down, 0)],
)
.unwrap();
assert_eq!(
resolver.process_batch(time(10), &[at(1, ButtonPhase::Up, 10)]),
Ok(vec![chord_edge(1, ButtonPhase::Up, 10, 10)])
);
assert_eq!(
resolver.process_batch(time(15), &[at(1, ButtonPhase::Down, 15)]),
Ok(Vec::new())
);
assert_eq!(
resolver.process_batch(time(20), &[at(2, ButtonPhase::Up, 20)]),
Ok(Vec::new())
);
assert_eq!(
resolver.process_batch(time(25), &[at(1, ButtonPhase::Up, 25)]),
Ok(Vec::new())
);
assert_eq!(
resolver.process_batch(time(30), &[at(1, ButtonPhase::Down, 30)]),
Ok(Vec::new())
);
assert_eq!(resolver.pending_keys(), vec![KeyId(1)]);
}
#[test]
fn all_members_release_waits_for_simultaneously_released_state() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AllMembers)]);
resolver
.process_batch(
time(0),
&[at(1, ButtonPhase::Down, 0), at(2, ButtonPhase::Down, 0)],
)
.unwrap();
assert_eq!(
resolver.process_batch(time(10), &[at(1, ButtonPhase::Up, 10)]),
Ok(Vec::new())
);
assert_eq!(
resolver.process_batch(time(15), &[at(1, ButtonPhase::Down, 15)]),
Ok(Vec::new())
);
assert_eq!(
resolver.process_batch(time(20), &[at(2, ButtonPhase::Up, 20)]),
Ok(Vec::new())
);
assert_eq!(
resolver.process_batch(time(25), &[at(1, ButtonPhase::Up, 25)]),
Ok(vec![chord_edge(1, ButtonPhase::Up, 25, 25)])
);
}
#[test]
fn chord_recognition_uses_latest_member_times() {
let mut resolver =
ChordResolver::new(&[chord(1, &[1, 2], 50, 0, ChordReleasePolicy::AnyMember)]);
resolver
.process_batch(time(10), &[edge(1, ButtonPhase::Down, 0, 10)])
.unwrap();
assert_eq!(
resolver.process_batch(time(30), &[edge(2, ButtonPhase::Down, 20, 30)]),
Ok(vec![chord_edge(1, ButtonPhase::Down, 20, 30)])
);
}
#[test]
fn regression_and_invalid_edge_times_do_not_advance_clock() {
let mut resolver = ChordResolver::new(&[]);
assert_eq!(resolver.advance_through(time(10)), Ok(Vec::new()));
assert_eq!(
resolver.advance_before(time(9)),
Err(ChordError::TimeRegression {
previous: time(10),
now: time(9),
})
);
let mut resolver = ChordResolver::new(&[]);
assert_eq!(
resolver.process_batch(time(10), &[edge(1, ButtonPhase::Down, 11, 10)]),
Err(ChordError::InvalidEdgeCausality {
key: KeyId(1),
occurred_at: time(11),
recognized_at: time(10),
})
);
assert_eq!(resolver.advance_through(time(9)), Ok(Vec::new()));
let mut resolver = ChordResolver::new(&[]);
assert_eq!(
resolver.process_batch(time(10), &[edge(1, ButtonPhase::Down, 9, 11)]),
Err(ChordError::EdgeAfterBatch {
key: KeyId(1),
recognized_at: time(11),
batch_at: time(10),
})
);
assert_eq!(resolver.advance_through(time(9)), Ok(Vec::new()));
}
#[test]
fn rejects_duplicate_key_in_atomic_batch() {
let mut resolver = ChordResolver::new(&[]);
assert_eq!(
resolver.process_batch(
time(10),
&[at(1, ButtonPhase::Down, 10), at(1, ButtonPhase::Up, 10)],
),
Err(ChordError::DuplicateKeyInBatch(KeyId(1)))
);
}
#[test]
fn reports_deadline_overflow_before_mutating() {
let mut resolver = ChordResolver::new(&[ChordConfig {
id: ChordId(1),
members: vec![KeyId(1), KeyId(2)],
window: Duration::from_nanos(1),
priority: 0,
release: ChordReleasePolicy::AnyMember,
}]);
let end = Timestamp::from_duration(Duration::MAX);
assert_eq!(
resolver.process_batch(
end,
&[ButtonEdge {
key: KeyId(1),
phase: ButtonPhase::Down,
occurred_at: end,
recognized_at: end,
}],
),
Err(ChordError::DeadlineOverflow {
chord: ChordId(1),
key: KeyId(1),
started_at: end,
})
);
assert!(resolver.pending_keys().is_empty());
}
}