use std::cmp;
use std::collections::{HashMap, HashSet};
use std::error::Error;
use std::fmt;
use std::num::NonZeroU64;
use std::time::Duration;
use crate::fsm_engine::Fsm;
use super::config::{
validate_gesture_config, ConfigError, FrameworkConfig, GestureConfig, HoldAfterTapPolicy,
};
use super::gesture_fsm::{self, Event, Motion, State};
use super::types::{
ButtonEvent, ButtonPhase, ControlEdge, ControlId, GestureKind, KeyId, Timestamp,
};
#[derive(Debug, Clone)]
pub struct GestureRecognizer {
control: ControlId,
config: GestureConfig,
fsm: Fsm<State, Event, Motion>,
processed_to: Timestamp,
down_at: Option<Timestamp>,
press_recognized_at: Option<Timestamp>,
tap_count: u8,
last_tap_up: Option<Timestamp>,
tap_causal_recognized_at: Option<Timestamp>,
tap_deadline: Option<Timestamp>,
next_hold_index: usize,
next_repeat_at: Option<Timestamp>,
}
impl GestureRecognizer {
pub fn new(control: ControlId, config: GestureConfig) -> Result<Self, ConfigError> {
validate_gesture_config(&config, Some(control))?;
Ok(Self::new_validated(control, config))
}
pub(crate) fn new_validated(control: ControlId, config: GestureConfig) -> Self {
Self {
control,
config,
fsm: gesture_fsm::new(),
processed_to: Timestamp::ZERO,
down_at: None,
press_recognized_at: None,
tap_count: 0,
last_tap_up: None,
tap_causal_recognized_at: None,
tap_deadline: None,
next_hold_index: 0,
next_repeat_at: None,
}
}
pub fn control(&self) -> ControlId {
self.control
}
pub fn next_deadline(&self) -> Option<Timestamp> {
match *self.fsm.current_state() {
State::Idle => None,
State::AwaitNextTap => self.tap_deadline,
State::Pressed | State::Holding => {
let hold = self.next_hold_deadline();
match (hold, self.next_repeat_at) {
(Some(left), Some(right)) => Some(cmp::min(left, right)),
(Some(value), None) | (None, Some(value)) => Some(value),
(None, None) => None,
}
}
}
}
fn prepare_edge(
&mut self,
edge: ControlEdge,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
self.validate_edge_timing(edge)?;
match edge.phase {
ButtonPhase::Down => self.advance_impl(edge.occurred_at, false, output),
ButtonPhase::Up => self.advance_impl(edge.occurred_at, true, output),
}
}
fn apply_edge(
&mut self,
edge: ControlEdge,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
match edge.phase {
ButtonPhase::Down => self.on_down(edge),
ButtonPhase::Up => self.on_up(edge, output),
}
}
fn on_down(&mut self, edge: ControlEdge) -> Result<(), GestureError> {
if *self.fsm.current_state() == State::Idle && edge.occurred_at < self.processed_to {
self.processed_to = edge.occurred_at;
}
self.ensure_deadline_fits(edge.occurred_at)?;
let motion = self.step(Event::Down)?;
debug_assert_eq!(motion, Motion::StartPress);
self.down_at = Some(edge.occurred_at);
self.press_recognized_at = Some(edge.recognized_at);
self.next_hold_index = 0;
self.next_repeat_at = self
.config
.repeat
.as_ref()
.map(|repeat| edge.occurred_at.saturating_add(repeat.starts_after));
self.tap_deadline = None;
self.processed_to = cmp::max(self.processed_to, edge.occurred_at);
Ok(())
}
fn on_up(
&mut self,
edge: ControlEdge,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
let state = *self.fsm.current_state();
match state {
State::Holding => {
let motion = self.step(Event::HeldUp)?;
debug_assert_eq!(motion, Motion::CompleteHold);
let down_at = self
.down_at
.take()
.ok_or(GestureError::MissingPressContext {
control: self.control,
})?;
let held_for = edge.occurred_at.checked_duration_since(down_at).ok_or(
GestureError::EventBeforePress {
control: self.control,
},
)?;
output.push(ButtonEvent::gesture(
self.control,
GestureKind::HoldEnd { held_for },
edge.occurred_at,
edge.recognized_at,
));
self.clear_press_context();
Ok(())
}
State::Pressed => {
let down_at = self.down_at.ok_or(GestureError::MissingPressContext {
control: self.control,
})?;
let held_for = edge.occurred_at.checked_duration_since(down_at).ok_or(
GestureError::EventBeforePress {
control: self.control,
},
)?;
let is_tap = held_for <= self.config.tap_max;
if !is_tap {
let motion = self.step(Event::UpInvalid)?;
debug_assert_eq!(motion, Motion::AbortPress);
self.commit_pending_taps(edge.recognized_at, output);
self.clear_press_context();
return Ok(());
}
let new_count = self
.tap_count
.checked_add(1)
.expect("tap count never exceeds configured u8 maximum");
if new_count >= self.config.max_taps {
let motion = self.step(Event::UpTapComplete)?;
debug_assert_eq!(motion, Motion::CompleteTap);
self.tap_count = new_count;
self.last_tap_up = Some(edge.occurred_at);
self.tap_causal_recognized_at = Some(max_timestamp(
self.tap_causal_recognized_at,
edge.recognized_at,
));
self.commit_pending_taps(edge.recognized_at, output);
} else {
let deadline = edge
.occurred_at
.checked_add(self.config.multi_tap_window)
.ok_or(GestureError::DeadlineOverflow {
control: self.control,
})?;
let motion = self.step(Event::UpTapWait)?;
debug_assert_eq!(motion, Motion::RecordTap);
self.tap_count = new_count;
self.last_tap_up = Some(edge.occurred_at);
self.tap_causal_recognized_at = Some(max_timestamp(
self.tap_causal_recognized_at,
edge.recognized_at,
));
self.tap_deadline = Some(deadline);
}
self.clear_press_context();
Ok(())
}
State::Idle | State::AwaitNextTap => Err(GestureError::UnexpectedEdge {
control: self.control,
phase: ButtonPhase::Up,
state: state_name(state),
}),
}
}
fn advance_impl(
&mut self,
now: Timestamp,
inclusive: bool,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
if now < self.processed_to && *self.fsm.current_state() != State::Idle {
return Err(GestureError::TimeRegression {
control: self.control,
previous: self.processed_to,
now,
});
}
while let Some(deadline) = self.next_deadline() {
let due = if inclusive {
deadline <= now
} else {
deadline < now
};
if !due {
break;
}
match *self.fsm.current_state() {
State::AwaitNextTap => self.expire_tap_window(deadline, output)?,
State::Pressed | State::Holding => {
self.process_due_hold_events(now, inclusive, output)?;
}
State::Idle => break,
}
}
if *self.fsm.current_state() != State::Idle {
self.processed_to = cmp::max(self.processed_to, now);
}
Ok(())
}
fn resolve_suspension(
&mut self,
now: Timestamp,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
match *self.fsm.current_state() {
State::AwaitNextTap => {
self.tap_causal_recognized_at =
Some(max_timestamp(self.tap_causal_recognized_at, now));
}
State::Pressed | State::Holding => {
self.press_recognized_at = Some(max_timestamp(self.press_recognized_at, now));
}
State::Idle => {}
}
self.advance_impl(now, true, output)
}
fn process_due_hold_events(
&mut self,
now: Timestamp,
inclusive: bool,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
while let Some(deadline) = self.next_hold_deadline() {
let due = if inclusive {
deadline <= now
} else {
deadline < now
};
if !due {
break;
}
let threshold = self.config.hold_thresholds[self.next_hold_index];
if self.next_hold_index == 0 {
let motion = self.step(Event::HoldReached)?;
debug_assert_eq!(motion, Motion::StartHold);
if self.tap_count > 0 {
match self.config.hold_after_tap {
HoldAfterTapPolicy::CancelPendingTaps => self.clear_tap_context(),
HoldAfterTapPolicy::CommitPendingTaps => {
let recognized_at = max_timestamp(
self.press_recognized_at,
max_timestamp(self.tap_causal_recognized_at, deadline),
);
self.commit_pending_taps(recognized_at, output);
}
}
}
output.push(ButtonEvent::gesture(
self.control,
GestureKind::HoldStart { threshold },
deadline,
max_timestamp(self.press_recognized_at, deadline),
));
} else {
let motion = self.step(Event::HoldMilestoneReached)?;
debug_assert_eq!(motion, Motion::EmitHoldMilestone);
output.push(ButtonEvent::gesture(
self.control,
GestureKind::HoldMilestone { threshold },
deadline,
max_timestamp(self.press_recognized_at, deadline),
));
}
self.next_hold_index += 1;
}
if *self.fsm.current_state() == State::Holding {
self.process_due_repeats(now, inclusive, output)?;
}
Ok(())
}
fn process_due_repeats(
&mut self,
now: Timestamp,
inclusive: bool,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
let Some(repeat) = &self.config.repeat else {
return Ok(());
};
let interval = repeat.interval;
let Some(next_repeat) = self.next_repeat_at else {
return Ok(());
};
let due = if inclusive {
next_repeat <= now
} else {
next_repeat < now
};
if !due {
return Ok(());
}
let elapsed = now
.checked_duration_since(next_repeat)
.expect("repeat deadline is not in the future");
let interval_ns = interval.as_nanos();
let due_count_u128 = elapsed.as_nanos() / interval_ns + 1;
let due_count = u64::try_from(due_count_u128).unwrap_or(u64::MAX);
let count = NonZeroU64::new(due_count).expect("a due repeat count is non-zero");
let offset = duration_mul(interval, due_count.saturating_sub(1));
let occurred_at = next_repeat.saturating_add(offset);
let motion = self.step(Event::RepeatDue)?;
debug_assert_eq!(motion, Motion::EmitRepeat);
output.push(ButtonEvent::gesture(
self.control,
GestureKind::Repeat { count },
occurred_at,
max_timestamp(self.press_recognized_at, occurred_at),
));
let next_offset = duration_mul(interval, due_count);
let candidate = next_repeat.saturating_add(next_offset);
self.next_repeat_at = (candidate > next_repeat).then_some(candidate);
Ok(())
}
fn expire_tap_window(
&mut self,
deadline: Timestamp,
output: &mut Vec<ButtonEvent>,
) -> Result<(), GestureError> {
let motion = self.step(Event::TapWindowExpired)?;
debug_assert_eq!(motion, Motion::CompleteTap);
let recognized_at = max_timestamp(self.tap_causal_recognized_at, deadline);
self.commit_pending_taps(recognized_at, output);
Ok(())
}
fn commit_pending_taps(&mut self, recognized_at: Timestamp, output: &mut Vec<ButtonEvent>) {
if self.tap_count > 0 {
let occurred_at = self
.last_tap_up
.expect("a non-zero tap count has a release timestamp");
output.push(ButtonEvent::gesture(
self.control,
GestureKind::Tap {
count: self.tap_count,
},
occurred_at,
max_timestamp(self.tap_causal_recognized_at, recognized_at),
));
}
self.clear_tap_context();
}
fn next_hold_deadline(&self) -> Option<Timestamp> {
let down_at = self.down_at?;
let threshold = *self.config.hold_thresholds.get(self.next_hold_index)?;
down_at.checked_add(threshold)
}
fn ensure_deadline_fits(&self, down_at: Timestamp) -> Result<(), GestureError> {
if self
.config
.hold_thresholds
.last()
.is_some_and(|threshold| down_at.checked_add(*threshold).is_none())
|| self
.config
.repeat
.as_ref()
.is_some_and(|repeat| down_at.checked_add(repeat.starts_after).is_none())
{
return Err(GestureError::DeadlineOverflow {
control: self.control,
});
}
Ok(())
}
fn validate_edge_timing(&self, edge: ControlEdge) -> Result<(), GestureError> {
if edge.occurred_at > edge.recognized_at {
return Err(GestureError::InvalidCausality {
control: self.control,
occurred_at: edge.occurred_at,
recognized_at: edge.recognized_at,
});
}
Ok(())
}
fn step(&mut self, event: Event) -> Result<Motion, GestureError> {
self.fsm
.step(&event)
.map(|(_, motion)| *motion)
.map_err(|source| GestureError::InvalidTransition {
control: self.control,
detail: source.to_string(),
})
}
fn clear_press_context(&mut self) {
self.down_at = None;
self.press_recognized_at = None;
self.next_hold_index = 0;
self.next_repeat_at = None;
}
fn clear_tap_context(&mut self) {
self.tap_count = 0;
self.last_tap_up = None;
self.tap_causal_recognized_at = None;
self.tap_deadline = None;
}
}
#[derive(Debug, Clone)]
pub struct GestureBank {
recognizers: HashMap<ControlId, GestureRecognizer>,
}
impl GestureBank {
pub fn new(config: &FrameworkConfig) -> Result<Self, ConfigError> {
config.validate()?;
Ok(Self::new_validated(config))
}
pub(crate) fn new_validated(config: &FrameworkConfig) -> Self {
let mut recognizers = HashMap::new();
for button in &config.buttons {
let control = ControlId::Key(button.id);
recognizers.insert(
control,
GestureRecognizer::new_validated(control, config.gesture_config(control).clone()),
);
}
for chord in &config.chords {
let control = ControlId::Chord(chord.id);
recognizers.insert(
control,
GestureRecognizer::new_validated(control, config.gesture_config(control).clone()),
);
}
Self { recognizers }
}
pub fn process_edges(
&mut self,
edges: impl IntoIterator<Item = ControlEdge>,
) -> Result<Vec<ButtonEvent>, GestureError> {
let mut output = Vec::new();
for edge in edges {
let recognizer = self
.recognizers
.get_mut(&edge.control)
.ok_or(GestureError::UnknownControl(edge.control))?;
recognizer.prepare_edge(edge, &mut output)?;
output.push(ButtonEvent::state(edge));
recognizer.apply_edge(edge, &mut output)?;
}
Ok(output)
}
pub fn advance_before(
&mut self,
now: Timestamp,
suspended_keys: &HashSet<KeyId>,
) -> Result<Vec<ButtonEvent>, GestureError> {
self.advance_impl(now, false, suspended_keys)
}
pub fn advance_through(
&mut self,
now: Timestamp,
suspended_keys: &HashSet<KeyId>,
) -> Result<Vec<ButtonEvent>, GestureError> {
self.advance_impl(now, true, suspended_keys)
}
pub fn next_deadline(&self) -> Option<Timestamp> {
self.next_deadline_excluding(&HashSet::new())
}
pub fn resolve_suspensions(
&mut self,
keys: &HashSet<KeyId>,
now: Timestamp,
) -> Result<Vec<ButtonEvent>, GestureError> {
let mut ordered: Vec<_> = keys.iter().copied().collect();
ordered.sort_unstable();
let mut output = Vec::new();
for key in ordered {
let control = ControlId::Key(key);
let recognizer = self
.recognizers
.get_mut(&control)
.ok_or(GestureError::UnknownControl(control))?;
recognizer.resolve_suspension(now, &mut output)?;
}
Ok(output)
}
pub fn next_deadline_excluding(&self, suspended_keys: &HashSet<KeyId>) -> Option<Timestamp> {
self.recognizers
.iter()
.filter(|(control, _)| {
!matches!(control, ControlId::Key(key) if suspended_keys.contains(key))
})
.filter_map(|(_, recognizer)| recognizer.next_deadline())
.min()
}
fn advance_impl(
&mut self,
now: Timestamp,
inclusive: bool,
suspended_keys: &HashSet<KeyId>,
) -> Result<Vec<ButtonEvent>, GestureError> {
let mut controls: Vec<_> = self.recognizers.keys().copied().collect();
controls.sort_unstable();
let mut output = Vec::new();
for control in controls {
if matches!(control, ControlId::Key(key) if suspended_keys.contains(&key)) {
continue;
}
let recognizer = self
.recognizers
.get_mut(&control)
.expect("control came from recognizer map");
recognizer.advance_impl(now, inclusive, &mut output)?;
}
Ok(output)
}
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum GestureError {
UnknownControl(ControlId),
TimeRegression {
control: ControlId,
previous: Timestamp,
now: Timestamp,
},
InvalidCausality {
control: ControlId,
occurred_at: Timestamp,
recognized_at: Timestamp,
},
UnexpectedEdge {
control: ControlId,
phase: ButtonPhase,
state: &'static str,
},
EventBeforePress {
control: ControlId,
},
MissingPressContext {
control: ControlId,
},
DeadlineOverflow {
control: ControlId,
},
InvalidTransition {
control: ControlId,
detail: String,
},
}
impl fmt::Display for GestureError {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::UnknownControl(control) => write!(f, "unknown gesture control {control:?}"),
Self::TimeRegression {
control,
previous,
now,
} => write!(
f,
"gesture time for {control:?} regressed from {previous} to {now}"
),
Self::InvalidCausality {
control,
occurred_at,
recognized_at,
} => write!(
f,
"gesture edge for {control:?} occurs at {occurred_at} after recognition at {recognized_at}"
),
Self::UnexpectedEdge {
control,
phase,
state,
} => write!(
f,
"unexpected {phase:?} for {control:?} in gesture state {state:?}"
),
Self::EventBeforePress { control } => {
write!(f, "release for {control:?} predates its press")
}
Self::MissingPressContext { control } => {
write!(f, "gesture state for {control:?} has no press context")
}
Self::DeadlineOverflow { control } => {
write!(f, "gesture deadline for {control:?} overflows Timestamp")
}
Self::InvalidTransition { control, detail } => {
write!(f, "gesture FSM for {control:?} rejected an event: {detail}")
}
}
}
}
impl Error for GestureError {
fn source(&self) -> Option<&(dyn Error + 'static)> {
None
}
}
fn max_timestamp(optional: Option<Timestamp>, value: Timestamp) -> Timestamp {
optional.map_or(value, |candidate| cmp::max(candidate, value))
}
fn state_name(state: State) -> &'static str {
match state {
State::Idle => "Idle",
State::Pressed => "Pressed",
State::AwaitNextTap => "AwaitNextTap",
State::Holding => "Holding",
}
}
fn duration_mul(duration: Duration, count: u64) -> Duration {
let nanos = duration.as_nanos().saturating_mul(u128::from(count));
let seconds = nanos / 1_000_000_000;
if seconds > u128::from(u64::MAX) {
return Duration::MAX;
}
Duration::new(seconds as u64, (nanos % 1_000_000_000) as u32)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::key::config::{HoldAfterTapPolicy, RepeatConfig};
use crate::key::types::{ButtonEventKind, ChordId, GestureKind, KeyId};
fn time(ms: u64) -> Timestamp {
Timestamp::from_millis(ms)
}
fn edge(control: ControlId, phase: ButtonPhase, ms: u64) -> ControlEdge {
ControlEdge {
control,
phase,
occurred_at: time(ms),
recognized_at: time(ms),
}
}
fn gestures(events: &[ButtonEvent]) -> Vec<&GestureKind> {
events
.iter()
.filter_map(|event| match &event.kind {
ButtonEventKind::Gesture { kind, .. } => Some(kind),
ButtonEventKind::State { .. } => None,
})
.collect()
}
#[test]
fn single_tap_emits_at_window_deadline() {
let control = ControlId::Key(KeyId(1));
let mut recognizer = GestureRecognizer::new(control, GestureConfig::default()).unwrap();
let mut output = Vec::new();
recognizer
.prepare_edge(edge(control, ButtonPhase::Down, 0), &mut output)
.unwrap();
recognizer
.apply_edge(edge(control, ButtonPhase::Down, 0), &mut output)
.unwrap();
recognizer
.prepare_edge(edge(control, ButtonPhase::Up, 20), &mut output)
.unwrap();
recognizer
.apply_edge(edge(control, ButtonPhase::Up, 20), &mut output)
.unwrap();
recognizer
.advance_impl(time(519), true, &mut output)
.unwrap();
assert!(gestures(&output).is_empty());
recognizer
.advance_impl(time(520), true, &mut output)
.unwrap();
assert_eq!(gestures(&output), vec![&GestureKind::Tap { count: 1 }]);
}
#[test]
fn second_down_at_exact_window_deadline_joins_sequence() {
let control = ControlId::Key(KeyId(1));
let mut recognizer = GestureRecognizer::new(control, GestureConfig::default()).unwrap();
let mut output = Vec::new();
for value in [
edge(control, ButtonPhase::Down, 0),
edge(control, ButtonPhase::Up, 20),
edge(control, ButtonPhase::Down, 520),
edge(control, ButtonPhase::Up, 540),
] {
recognizer.prepare_edge(value, &mut output).unwrap();
recognizer.apply_edge(value, &mut output).unwrap();
}
assert_eq!(gestures(&output), vec![&GestureKind::Tap { count: 2 }]);
}
#[test]
fn release_at_hold_threshold_emits_start_then_end() {
let control = ControlId::Key(KeyId(1));
let mut recognizer = GestureRecognizer::new(control, GestureConfig::default()).unwrap();
let mut output = Vec::new();
let down = edge(control, ButtonPhase::Down, 0);
recognizer.prepare_edge(down, &mut output).unwrap();
recognizer.apply_edge(down, &mut output).unwrap();
let up = edge(control, ButtonPhase::Up, 1_000);
recognizer.prepare_edge(up, &mut output).unwrap();
recognizer.apply_edge(up, &mut output).unwrap();
assert_eq!(
gestures(&output),
vec![
&GestureKind::HoldStart {
threshold: Duration::from_secs(1),
},
&GestureKind::HoldEnd {
held_for: Duration::from_secs(1),
},
]
);
}
#[test]
fn repeat_jump_is_coalesced() {
let control = ControlId::Chord(ChordId(2));
let config = GestureConfig {
repeat: Some(RepeatConfig {
starts_after: Duration::from_millis(1_200),
interval: Duration::from_millis(100),
}),
..GestureConfig::default()
};
let mut recognizer = GestureRecognizer::new(control, config).unwrap();
let mut output = Vec::new();
let down = edge(control, ButtonPhase::Down, 0);
recognizer.prepare_edge(down, &mut output).unwrap();
recognizer.apply_edge(down, &mut output).unwrap();
recognizer
.advance_impl(time(1_600), true, &mut output)
.unwrap();
assert!(gestures(&output).contains(&&GestureKind::Repeat {
count: NonZeroU64::new(5).unwrap(),
}));
}
#[test]
fn commit_policy_emits_pending_tap_before_hold() {
let control = ControlId::Key(KeyId(1));
let config = GestureConfig {
hold_after_tap: HoldAfterTapPolicy::CommitPendingTaps,
..GestureConfig::default()
};
let mut recognizer = GestureRecognizer::new(control, config).unwrap();
let mut output = Vec::new();
for value in [
edge(control, ButtonPhase::Down, 0),
edge(control, ButtonPhase::Up, 20),
edge(control, ButtonPhase::Down, 100),
] {
recognizer.prepare_edge(value, &mut output).unwrap();
recognizer.apply_edge(value, &mut output).unwrap();
}
recognizer
.advance_impl(time(1_100), true, &mut output)
.unwrap();
assert_eq!(
gestures(&output),
vec![
&GestureKind::Tap { count: 1 },
&GestureKind::HoldStart {
threshold: Duration::from_secs(1),
},
]
);
}
}