xremap 0.15.5

use crate::action::Action;
use crate::client::WMClient;
use crate::config::key_press::{KeyPress, Modifier};
use crate::config::keymap::{build_override_table, OverrideEntry};
use crate::config::keymap_action::KeymapAction;
use crate::config::modmap_operator::{Interruptable, Keys, ModmapOperator, MultiPurposeKey, PressReleaseKey};
use crate::config::nested_remap::Remap;
use crate::device::InputDeviceInfo;
use crate::event::{Event, KeyEvent, RelativeEvent};
use crate::operator_handler::OperatorHandler;
use crate::Config;
use evdev::KeyCode as Key;
use lazy_static::lazy_static;
use log::{debug, warn};
use nix::sys::time::TimeSpec;
use nix::sys::timerfd::{Expiration, TimerFd, TimerSetTimeFlags};
use std::cmp::Ordering;
use std::collections::{HashMap, HashSet};
use std::error::Error;
use std::rc::Rc;
use std::time::{Duration, Instant};

// This const is used to map evdev relative event codes to a pseudo keycode
pub const DISGUISED_EVENT_OFFSETTER: u16 = 59974;

// This const defines a keycode used to match any key.
// It's the offset of XHIRES_LEFTSCROLL + 1
pub const KEY_MATCH_ANY: Key = Key(DISGUISED_EVENT_OFFSETTER + 26);

pub struct EventHandler {
    // Currently pressed modifier keys, in the order they were pressed.
    modifiers: Vec<Key>,
    // Modifiers that are currently pressed but not in the source KeyPress
    extra_modifiers: HashSet<Key>,
    // Make sure the original event is released even if remapping changes while holding the key
    pressed_keys: HashMap<Key, Key>,
    // State machine for multi-purpose keys
    multi_purpose_keys: HashMap<Key, MultiPurposeKeyState>,
    // Current nested remaps
    override_remaps: Vec<HashMap<Key, Vec<OverrideEntry>>>,
    // Key triggered on a timeout of nested remaps
    override_timeout_key: Option<Vec<Key>>,
    // Trigger a timeout of nested remaps through select(2)
    override_timer: TimerFd,
    // { set_mode: String }
    mode: String,
    // { set_mark: true }
    mark_set: bool,
    // { escape_next_key: true }
    escape_next_key: bool,
    // keypress_delay_ms
    keypress_delay: Duration,
    // Buffered actions to be dispatched. TODO: Just return actions from each function instead of using this.
    actions: Vec<Action>,
}

struct TaggedAction {
    action: KeymapAction,
    exact_match: bool,
}

impl EventHandler {
    pub fn new(override_timer: TimerFd, mode: &str, keypress_delay: Duration) -> EventHandler {
        EventHandler {
            modifiers: vec![],
            extra_modifiers: HashSet::new(),
            pressed_keys: HashMap::new(),
            multi_purpose_keys: HashMap::new(),
            override_remaps: vec![],
            override_timeout_key: None,
            override_timer,
            mode: mode.to_string(),
            mark_set: false,
            escape_next_key: false,
            keypress_delay,
            actions: vec![],
        }
    }

    // Handle an Event and return Actions. This should be the only public method of EventHandler.
    pub fn on_events(
        &mut self,
        mut events: Vec<Event>,
        config: &Config,
        wmclient: &mut WMClient,
        operator_handler: &mut Option<OperatorHandler>,
    ) -> Result<Vec<Action>, Box<dyn Error>> {
        if let Some(handler) = operator_handler {
            wmclient.clear_app_class_and_title();
            events = handler.map_events(events, wmclient);
        };

        debug_assert!(self.actions.is_empty());
        // a vector to collect mouse movement events to be able to send them all at once as one MouseMovementEventCollection.
        let mut mouse_movement_collection: Vec<RelativeEvent> = Vec::new();
        for event in events {
            wmclient.clear_app_class_and_title();

            if let Event::KeyEvent(_, key_event) = &event {
                debug!("=> {}: {:?}", key_event.value(), &key_event.key);
            }

            // Apply modmap
            let modmap_events = self.apply_modmap(config, event, wmclient)?;

            // Apply keymap
            for event in modmap_events.into_iter() {
                match event {
                    Event::KeyEvent(device, key_event) => {
                        self.on_key_event(key_event.key, key_event.value(), &device, config, wmclient)?;
                    }
                    Event::RelativeEvent(device, relative_event) => {
                        let key = Key(relative_event.to_disguised_key());

                        // Send as disguised-event
                        let was_remapped = self.on_key_event(key, PRESS, &device, config, wmclient)?;

                        if !was_remapped {
                            if relative_event.code <= 2 {
                                // The relative event keycodes 1 and 2 is REL_X and REL_Y. Meaning mouse move.
                                mouse_movement_collection.push(relative_event);
                            } else {
                                self.send_action(Action::RelativeEvent(relative_event));
                            }
                        }
                    }

                    Event::OtherEvents(event) => self.send_action(Action::InputEvent(event)),
                    Event::OverrideTimeout => self.timeout_override()?,
                    Event::Tick => {
                        // Can be ignored. It's for operators.
                    }
                }
            }
        }
        // if there is at least one mouse movement event, sending all of them as one MouseMovementEventCollection
        if !mouse_movement_collection.is_empty() {
            self.send_action(Action::MouseMovementEventCollection(mouse_movement_collection));
        }
        Ok(self.actions.drain(..).collect())
    }

    // Handle EventType::KEY
    fn on_key_event(
        &mut self,
        key: Key,
        value: i32,
        device: &Rc<InputDeviceInfo>,
        config: &Config,
        wmclient: &mut WMClient,
    ) -> Result<bool, Box<dyn Error>> {
        // Apply keymap
        if config.virtual_modifiers.contains(&key) {
            self.update_modifier(key, value);
            return Ok(true);
        } else if MODIFIER_KEYS.contains(&key) {
            self.update_modifier(key, value);
        } else if is_pressed(value) {
            if self.escape_next_key {
                self.escape_next_key = false
            } else if let Some(actions) = self.find_keymap(config, &key, device, wmclient)? {
                self.dispatch_actions(&actions, &key)?;
                return Ok(true);
            } else if let Some(actions) = self.find_keymap(config, &KEY_MATCH_ANY, device, wmclient)? {
                self.dispatch_actions(&actions, &KEY_MATCH_ANY)?;
                return Ok(true);
            }
        }

        if key.code() >= DISGUISED_EVENT_OFFSETTER {
            Ok(false)
        } else {
            self.send_key(&key, value);

            Ok(true)
        }
    }

    fn timeout_override(&mut self) -> Result<(), Box<dyn Error>> {
        if let Some(keys) = &self.override_timeout_key.take() {
            for key in keys {
                self.send_key(key, PRESS);
                self.send_key(key, RELEASE);
            }
        }
        self.remove_override()
    }

    fn remove_override(&mut self) -> Result<(), Box<dyn Error>> {
        self.override_timer.unset()?;
        self.override_remaps.clear();
        self.override_timeout_key = None;
        Ok(())
    }

    fn send_keys(&mut self, keys: &Vec<Key>, value: i32) {
        for key in keys {
            self.send_key(key, value);
        }
    }

    fn send_key(&mut self, key: &Key, value: i32) {
        let event = KeyEvent::new_with(key.code(), value);
        self.send_action(Action::KeyEvent(event));
    }

    fn send_action(&mut self, action: Action) {
        self.actions.push(action);
    }

    // Repeat/Release what's originally pressed even if remapping changes while holding it
    fn maintain_pressed_keys(&mut self, key: Key, value: i32, events: &mut [(Key, i32)]) {
        // Not handling multi-purpose keys for now; too complicated
        if events.len() != 1 || value != events[0].1 {
            // When multiple keys are emitted, then it also comes here which makes it fail.
            return;
        }

        let event = events[0];
        if value == PRESS {
            self.pressed_keys.insert(key, event.0);
        } else {
            if let Some(original_key) = self.pressed_keys.get(&key) {
                events[0].0 = *original_key;
            }
            if value == RELEASE {
                self.pressed_keys.remove(&key);
            }
        }
    }

    fn dispatch_keys(
        &mut self,
        key_action: ModmapOperator,
        key: Key,
        value: i32,
    ) -> Result<Vec<(Key, i32)>, Box<dyn Error>> {
        let keys = match key_action {
            ModmapOperator::Keys(modmap_keys) => modmap_keys
                .into_vec()
                .into_iter()
                .map(|modmap_key| (modmap_key, value))
                .collect(),
            ModmapOperator::MultiPurposeKey(MultiPurposeKey {
                hold,
                tap,
                hold_threshold,
                tap_timeout,
                free_hold,
                interruptable,
            }) => {
                match value {
                    PRESS => {
                        // Move this to input validation.
                        let hold_threshold = if hold_threshold <= tap_timeout {
                            hold_threshold
                        } else {
                            warn!("hold_threshold_millis must be smaller than tap_timeout_millis. Setting hold_threshold_millis to tap_timeout_millis: {:?}", tap_timeout);
                            tap_timeout
                        };

                        self.multi_purpose_keys.insert(
                            key,
                            MultiPurposeKeyState {
                                hold,
                                tap,
                                interruptable,
                                hold_threshold_at: if hold_threshold == Duration::ZERO {
                                    Instant::now()
                                } else {
                                    Instant::now() + hold_threshold
                                },
                                tap_timeout_at: if free_hold {
                                    // An approximation of never.
                                    Instant::now() + Duration::from_secs_f32(1e10)
                                } else {
                                    Instant::now() + tap_timeout
                                },
                                state: if hold_threshold == Duration::ZERO {
                                    MultiPurposeKeyStateEnum::HoldPreferred
                                } else {
                                    MultiPurposeKeyStateEnum::TapPreferred
                                },
                            },
                        );
                        return Ok(vec![]); // delay the press
                    }
                    REPEAT => {
                        if let Some(state) = self.multi_purpose_keys.get_mut(&key) {
                            return Ok(state.repeat());
                        }
                    }
                    RELEASE => {
                        if let Some(state) = self.multi_purpose_keys.remove(&key) {
                            return Ok(state.release());
                        }
                    }
                    _ => panic!("unexpected key event value: {value}"),
                }
                // fallthrough on state discrepancy
                vec![(key, value)]
            }
            ModmapOperator::PressReleaseKey(PressReleaseKey {
                skip_key_event,
                press,
                repeat,
                release,
            }) => {
                // Just hook actions, and then emit the original event. We might want to
                // support reordering the key event and dispatched actions later.
                let actions_to_dispatch = match value {
                    PRESS => press,
                    RELEASE => release,
                    _ => repeat,
                };
                self.dispatch_actions(
                    &actions_to_dispatch
                        .into_iter()
                        .map(|action| TaggedAction {
                            action,
                            exact_match: false,
                        })
                        .collect(),
                    &key,
                )?;

                match skip_key_event {
                    true => vec![],              // do not dispatch the original key
                    false => vec![(key, value)], // dispatch the original key
                }
            }
        };
        Ok(keys)
    }

    // Typically only receives one key as argument. It can be more, when also matched
    // in modmap. But that's probably not a meaningful use case, should probably
    // interrupt before modmap, rather than after.
    fn flush_timeout_keys(&mut self, key_values: Vec<(Key, i32)>) -> Vec<(Key, i32)> {
        let mut pressed = vec![];
        for (key, value) in key_values.iter() {
            if *value == PRESS {
                pressed.push(*key);
            }
        }

        if !pressed.is_empty() {
            let mut flushed: Vec<(Key, i32)> = vec![];
            for (_, state) in self.multi_purpose_keys.iter_mut() {
                flushed.extend(state.interrupted_by_press(&*pressed));
            }

            // filter out key presses that are part of the flushed events
            let flushed_presses: HashSet<Key> = flushed
                .iter()
                .filter_map(|(k, v)| (*v == PRESS).then_some(*k))
                .collect();
            // There's generally no protection against spurious press, so
            // it's probably also not needed here.
            let key_values: Vec<(Key, i32)> = key_values
                .into_iter()
                .filter(|(key, value)| !(*value == PRESS && flushed_presses.contains(key)))
                .collect();

            flushed.extend(key_values);
            flushed
        } else {
            key_values
        }
    }

    fn apply_modmap(
        &mut self,
        config: &Config,
        event: Event,
        wmclient: &mut WMClient,
    ) -> Result<Vec<Event>, Box<dyn Error>> {
        match &event {
            Event::KeyEvent(device, key_event) => {
                let key = key_event.key;
                let value = key_event.value();

                let mut key_values = if let Some(key_action) = self.find_modmap(config, &key, &device, wmclient) {
                    self.dispatch_keys(key_action, key, value)?
                } else {
                    vec![(key, value)]
                };
                self.maintain_pressed_keys(key, value, &mut key_values);
                if !self.multi_purpose_keys.is_empty() {
                    key_values = self.flush_timeout_keys(key_values);
                }

                let events: Vec<_> = key_values
                    .into_iter()
                    .map(|(key, value)| Event::KeyEvent(device.clone(), KeyEvent::new_with(key.code(), value)))
                    .collect();

                Ok(events)
            }
            Event::RelativeEvent(device, relative_event) => {
                // Can't use `flush_timeout_keys`, because it would also emit the disguised key.
                let pressed = vec![Key(relative_event.to_disguised_key())];

                let mut events = vec![];
                for (_, state) in self.multi_purpose_keys.iter_mut() {
                    events.extend(state.interrupted_by_press(&pressed));
                }

                let mut events: Vec<_> = events
                    .into_iter()
                    .map(|(key, value)| Event::KeyEvent(device.clone(), KeyEvent::new_with(key.code(), value)))
                    .collect();

                events.push(event);

                Ok(events)
            }
            _ => Ok(vec![event]),
        }
    }

    fn find_modmap(
        &mut self,
        config: &Config,
        key: &Key,
        device: &InputDeviceInfo,
        wmclient: &mut WMClient,
    ) -> Option<ModmapOperator> {
        for modmap in &config.modmap {
            if let Some(key_action) = modmap.remap.get(key) {
                if let Some(window_matcher) = &modmap.window {
                    if !wmclient.match_window(window_matcher) {
                        continue;
                    }
                }
                if let Some(application_matcher) = &modmap.application {
                    if !wmclient.match_application(application_matcher) {
                        continue;
                    }
                }
                if let Some(device_matcher) = &modmap.device {
                    if !device_matcher.matches(device) {
                        continue;
                    }
                }
                if let Some(modes) = &modmap.mode {
                    if !modes.contains(&self.mode) {
                        continue;
                    }
                }
                return Some(key_action.clone());
            }
        }
        None
    }

    fn find_keymap(
        &mut self,
        config: &Config,
        key: &Key,
        device: &InputDeviceInfo,
        wmclient: &mut WMClient,
    ) -> Result<Option<Vec<TaggedAction>>, Box<dyn Error>> {
        if !self.override_remaps.is_empty() {
            let entries: Vec<OverrideEntry> = self
                .override_remaps
                .iter()
                .flat_map(|map| map.get(key).cloned().unwrap_or_default())
                .collect();

            // Empty if the key isn't defined in any of the nested remaps, that are active.
            if !entries.is_empty() {
                self.remove_override()?;

                for exact_match in [true, false] {
                    let mut remaps = vec![];
                    for entry in &entries {
                        if entry.exact_match && !exact_match {
                            continue;
                        }
                        let (extra_modifiers, missing_modifiers) = self.diff_modifiers(&entry.modifiers);
                        if (exact_match && !extra_modifiers.is_empty()) || !missing_modifiers.is_empty() {
                            continue;
                        }

                        let actions = with_extra_modifiers(&entry.actions, &extra_modifiers, entry.exact_match);
                        let is_remap = is_remap(&entry.actions);

                        // If the first/top match was a remap, continue to find rest of the eligible remaps for this key
                        if remaps.is_empty() && !is_remap {
                            return Ok(Some(actions));
                        } else if is_remap {
                            remaps.extend(actions);
                        }
                    }
                    if !remaps.is_empty() {
                        return Ok(Some(remaps));
                    }
                }
            }
            // An override remap is set but not used. Flush the pending key.
            self.timeout_override()?;
        }

        if let Some(entries) = config.keymap_table.get(key) {
            for exact_match in [true, false] {
                let mut remaps = vec![];
                for entry in entries {
                    if entry.exact_match && !exact_match {
                        continue;
                    }
                    let (extra_modifiers, missing_modifiers) = self.diff_modifiers(&entry.modifiers);
                    if (exact_match && !extra_modifiers.is_empty()) || !missing_modifiers.is_empty() {
                        continue;
                    }
                    if let Some(window_matcher) = &entry.title {
                        if !wmclient.match_window(window_matcher) {
                            continue;
                        }
                    }

                    if let Some(application_matcher) = &entry.application {
                        if !wmclient.match_application(application_matcher) {
                            continue;
                        }
                    }
                    if let Some(device_matcher) = &entry.device {
                        if !device_matcher.matches(device) {
                            continue;
                        }
                    }
                    if let Some(modes) = &entry.mode {
                        if !modes.contains(&self.mode) {
                            continue;
                        }
                    }

                    let actions = with_extra_modifiers(&entry.actions, &extra_modifiers, entry.exact_match);
                    let is_remap = is_remap(&entry.actions);

                    // If the first/top match was a remap, continue to find rest of the eligible remaps for this key
                    if remaps.is_empty() && !is_remap {
                        return Ok(Some(actions));
                    } else if is_remap {
                        remaps.extend(actions)
                    }
                }
                if !remaps.is_empty() {
                    return Ok(Some(remaps));
                }
            }
        }
        Ok(None)
    }

    fn dispatch_actions(&mut self, actions: &Vec<TaggedAction>, key: &Key) -> Result<(), Box<dyn Error>> {
        debug_assert!(self.extra_modifiers.len() == 0);
        for action in actions {
            self.dispatch_action(action, key)?;
        }
        Ok(())
    }

    fn dispatch_action(&mut self, action: &TaggedAction, key: &Key) -> Result<(), Box<dyn Error>> {
        match &action.action {
            KeymapAction::KeyPressAndRelease(key_press) => self.send_key_press_and_release(key_press),
            KeymapAction::KeyPress(key) => self.send_key(key, PRESS),
            KeymapAction::KeyRepeat(key) => self.send_key(key, REPEAT),
            KeymapAction::KeyRelease(key) => self.send_key(key, RELEASE),
            KeymapAction::Remap(Remap {
                remap,
                timeout,
                timeout_key,
            }) => {
                let set_timeout = self.override_remaps.is_empty();
                self.override_remaps
                    .push(build_override_table(remap, action.exact_match));

                // Set timeout only if this is the first of multiple eligible remaps,
                // so the behaviour is consistent with how current normal keymap override works
                if set_timeout {
                    if let Some(timeout) = timeout {
                        let expiration = Expiration::OneShot(TimeSpec::from_duration(*timeout));
                        // TODO: Consider handling the timer in ActionDispatcher
                        self.override_timer.unset()?;
                        self.override_timer.set(expiration, TimerSetTimeFlags::empty())?;
                        self.override_timeout_key = timeout_key.clone().or_else(|| Some(vec![*key]))
                    }
                }
            }
            KeymapAction::Launch(command) => self.run_command(command.clone()),
            KeymapAction::SetMode(mode) => {
                self.mode = mode.clone();
                println!("mode: {mode}");
            }
            KeymapAction::SetMark(set) => self.mark_set = *set,
            KeymapAction::WithMark(key_press) => self.send_key_press_and_release(&self.with_mark(key_press)),
            KeymapAction::EscapeNextKey(escape_next_key) => self.escape_next_key = *escape_next_key,
            KeymapAction::Sleep(millis) => self.send_action(Action::Delay(Duration::from_millis(*millis))),
            KeymapAction::SetExtraModifiers(keys) => {
                self.extra_modifiers.clear();
                for key in keys {
                    self.extra_modifiers.insert(*key);
                }
            }
            KeymapAction::CloseByAppClass(app_class) => self.actions.push(Action::CloseByAppClass(app_class.clone())),
        }
        Ok(())
    }

    fn send_key_press_and_release(&mut self, key_press: &KeyPress) {
        // Build extra or missing modifiers. Note that only MODIFIER_KEYS are handled
        // because virtual modifiers shouldn't make an impact outside xremap.
        let (mut extra_modifiers, mut missing_modifiers) = self.diff_modifiers(&key_press.modifiers);
        extra_modifiers.retain(|key| MODIFIER_KEYS.contains(key) && !self.extra_modifiers.contains(key));
        missing_modifiers.retain(|key| MODIFIER_KEYS.contains(key));

        // Emulate the modifiers of KeyPress
        self.send_keys(&missing_modifiers, PRESS);
        self.send_keys(&extra_modifiers, RELEASE);

        // Press the main key
        self.send_key(&key_press.key, PRESS);
        self.send_key(&key_press.key, RELEASE);

        self.send_action(Action::Delay(self.keypress_delay));

        // Resurrect the original modifiers
        self.send_keys(&extra_modifiers, PRESS);
        self.send_action(Action::Delay(self.keypress_delay));
        self.send_keys(&missing_modifiers, RELEASE);
    }

    fn with_mark(&self, key_press: &KeyPress) -> KeyPress {
        if self.mark_set && !Modifier::Shift.is_in(&self.modifiers) {
            let mut modifiers = key_press.modifiers.clone();
            modifiers.push(Modifier::Shift);
            KeyPress {
                key: key_press.key,
                modifiers,
            }
        } else {
            key_press.clone()
        }
    }

    fn run_command(&mut self, command: Vec<String>) {
        self.send_action(Action::Command(command));
    }

    // Return (extra_modifiers, missing_modifiers)
    fn diff_modifiers(&self, modifiers: &[Modifier]) -> (Vec<Key>, Vec<Key>) {
        let extra_modifiers: Vec<Key> = self
            .modifiers
            .iter()
            .filter(|modifier| !contains_modifier(modifiers, modifier))
            .copied()
            .collect();
        let missing_modifiers: Vec<Key> = modifiers
            .iter()
            .filter_map(|modifier| {
                if modifier.is_in(&self.modifiers) {
                    None
                } else {
                    match modifier {
                        Modifier::Shift => Some(Key::KEY_LEFTSHIFT),
                        Modifier::Control => Some(Key::KEY_LEFTCTRL),
                        Modifier::Alt => Some(Key::KEY_LEFTALT),
                        Modifier::Windows => Some(Key::KEY_LEFTMETA),
                        Modifier::Key(key) => Some(*key),
                    }
                }
            })
            .collect();
        (extra_modifiers, missing_modifiers)
    }

    fn update_modifier(&mut self, key: Key, value: i32) {
        if value == PRESS {
            if !self.modifiers.contains(&key) {
                self.modifiers.push(key);
            }
        } else if value == RELEASE {
            self.modifiers.retain(|&x| x != key);
        }
    }
}

fn is_remap(actions: &[KeymapAction]) -> bool {
    if actions.is_empty() {
        // When actions is empty it could either be regarded as an empty remap
        //  or no actions. In principle that shouldn't matter, but remap is
        //  implemented to gather all defined remaps, not just the first match.
        // Here we regard an empty actions as non-remap, so the matching will stop
        //  here, and no actions are performed. The possibly following remaps are
        //  hence ignored.
        return false;
    }

    actions.iter().all(|x| matches!(x, KeymapAction::Remap(..)))
}

fn with_extra_modifiers(actions: &[KeymapAction], extra_modifiers: &[Key], exact_match: bool) -> Vec<TaggedAction> {
    let mut result: Vec<TaggedAction> = vec![];
    if !extra_modifiers.is_empty() {
        // Virtually release extra modifiers so that they won't be physically released on KeyPress
        result.push(TaggedAction {
            action: KeymapAction::SetExtraModifiers(extra_modifiers.to_vec()),
            exact_match,
        });
    }
    result.extend(actions.iter().map(|action| TaggedAction {
        action: action.clone(),
        exact_match,
    }));
    if !extra_modifiers.is_empty() {
        // Resurrect the modifier status
        result.push(TaggedAction {
            action: KeymapAction::SetExtraModifiers(vec![]),
            exact_match,
        });
    }
    result
}

fn contains_modifier(modifiers: &[Modifier], key: &Key) -> bool {
    for modifier in modifiers {
        if match modifier {
            Modifier::Shift => key == &Key::KEY_LEFTSHIFT || key == &Key::KEY_RIGHTSHIFT,
            Modifier::Control => key == &Key::KEY_LEFTCTRL || key == &Key::KEY_RIGHTCTRL,
            Modifier::Alt => key == &Key::KEY_LEFTALT || key == &Key::KEY_RIGHTALT,
            Modifier::Windows => key == &Key::KEY_LEFTMETA || key == &Key::KEY_RIGHTMETA,
            Modifier::Key(modifier_key) => key == modifier_key,
        } {
            return true;
        }
    }
    false
}

lazy_static! {
    pub static ref MODIFIER_KEYS: [Key; 8] = [
        // Shift
        Key::KEY_LEFTSHIFT,
        Key::KEY_RIGHTSHIFT,
        // Control
        Key::KEY_LEFTCTRL,
        Key::KEY_RIGHTCTRL,
        // Alt
        Key::KEY_LEFTALT,
        Key::KEY_RIGHTALT,
        // Windows
        Key::KEY_LEFTMETA,
        Key::KEY_RIGHTMETA,
    ];
}

// ---

fn is_pressed(value: i32) -> bool {
    value == PRESS || value == REPEAT
}

// InputEvent#value
pub const RELEASE: i32 = 0;
pub const PRESS: i32 = 1;
pub const REPEAT: i32 = 2;

// ---

#[derive(Debug, PartialEq)]
enum MultiPurposeKeyStateEnum {
    // If released then the tab-action is emitted
    // If interrupted then the tab-action is emitted
    // If timeout go to HoldPreferred state
    TapPreferred,
    // If released then the tab-action is emitted
    // If interrupted then the hold-action is emitted
    // If timeout then hold-action is emitted
    HoldPreferred,
    // Tab-action has been pressed and released.
    TapChosen,
    // Hold-action has been pressed, but has not been released yet.
    HoldDown,
}

#[derive(Debug)]
struct MultiPurposeKeyState {
    hold: Keys,
    tap: Keys,
    interruptable: Interruptable,
    hold_threshold_at: Instant,
    tap_timeout_at: Instant,
    state: MultiPurposeKeyStateEnum,
}

impl MultiPurposeKeyState {
    /// It causes a problem, that repeat is used for timeout. Partially because its interval
    /// gives low precision. And because the repeat events will stop if another key is pressed. Also
    /// BTN_RIGHT does not emit repeat events, so mouse buttons can't be remapped this way.   
    fn repeat(&mut self) -> Vec<(Key, i32)> {
        if matches!(self.state, MultiPurposeKeyStateEnum::TapPreferred) && Instant::now() >= self.hold_threshold_at {
            // Timeout. Setting state before going into the switch is necessary
            self.state = MultiPurposeKeyStateEnum::HoldPreferred;
        }

        match self.state {
            MultiPurposeKeyStateEnum::TapPreferred => {
                vec![] // still delay repeat
            }
            MultiPurposeKeyStateEnum::HoldPreferred if Instant::now() < self.tap_timeout_at => {
                vec![] // still delay repeat
            }
            MultiPurposeKeyStateEnum::HoldPreferred => {
                // timeout
                self.state = MultiPurposeKeyStateEnum::HoldDown;
                let mut keys = self.hold.clone().into_vec();
                keys.sort_by(modifiers_first);
                keys.into_iter().map(|key| (key, PRESS)).collect()
            }
            MultiPurposeKeyStateEnum::HoldDown => {
                let mut keys = self.hold.clone().into_vec();
                keys.sort_by(modifiers_first);
                keys.into_iter().map(|key| (key, REPEAT)).collect()
            }
            MultiPurposeKeyStateEnum::TapChosen => {
                vec![] // tap-action already released, so ignores repeat
            }
        }
    }

    /// This function consumes the MultiPurposeKeyStateEnum, so there's no need to set self.state
    fn release(mut self) -> Vec<(Key, i32)> {
        if matches!(self.state, MultiPurposeKeyStateEnum::TapPreferred) && Instant::now() >= self.hold_threshold_at {
            // Timeout. Setting state before going into the switch is necessary
            self.state = MultiPurposeKeyStateEnum::HoldPreferred;
        }

        match self.state {
            MultiPurposeKeyStateEnum::TapPreferred => {
                // Before hold_threshold_at timeout
                self.press_and_release(&self.tap)
            }
            MultiPurposeKeyStateEnum::HoldPreferred if Instant::now() < self.tap_timeout_at => {
                self.press_and_release(&self.tap)
            }
            MultiPurposeKeyStateEnum::HoldPreferred => self.press_and_release(&self.hold),
            MultiPurposeKeyStateEnum::HoldDown => {
                let mut release_keys = self.hold.clone().into_vec();
                release_keys.sort_by(modifiers_last);
                release_keys.into_iter().map(|key| (key, RELEASE)).collect()
            }
            MultiPurposeKeyStateEnum::TapChosen => {
                vec![] // nothing to release
            }
        }
    }

    // Other keys were pressed, so the multipurpose key
    // should emit presses of its held-value if it can be interrupted by those keys.
    fn interrupted_by_press(&mut self, pressed: &[Key]) -> Vec<(Key, i32)> {
        if !pressed.iter().any(|key| self.interruptable.is_interrupted_by(*key)) {
            return vec![];
        }

        if matches!(self.state, MultiPurposeKeyStateEnum::TapPreferred) && Instant::now() >= self.hold_threshold_at {
            // Timeout. Setting state before going into the switch is necessary
            self.state = MultiPurposeKeyStateEnum::HoldPreferred;
        }

        match self.state {
            MultiPurposeKeyStateEnum::TapPreferred => {
                self.state = MultiPurposeKeyStateEnum::TapChosen;
                self.press_and_release(&self.tap)
            }
            MultiPurposeKeyStateEnum::HoldPreferred => {
                self.state = MultiPurposeKeyStateEnum::HoldDown;

                let mut keys = self.hold.clone().into_vec();
                keys.sort_by(modifiers_first);
                keys.into_iter().map(|key| (key, PRESS)).collect()
            }
            MultiPurposeKeyStateEnum::HoldDown | MultiPurposeKeyStateEnum::TapChosen => vec![],
        }
    }

    fn press_and_release(&self, keys_to_use: &Keys) -> Vec<(Key, i32)> {
        let mut release_keys = keys_to_use.clone().into_vec();
        release_keys.sort_by(modifiers_last);
        let release_events: Vec<(Key, i32)> = release_keys.into_iter().map(|key| (key, RELEASE)).collect();

        let mut press_keys = keys_to_use.clone().into_vec();
        press_keys.sort_by(modifiers_first);
        let mut events: Vec<(Key, i32)> = press_keys.into_iter().map(|key| (key, PRESS)).collect();
        events.extend(release_events);
        events
    }
}

/// Orders modifier keys ahead of non-modifier keys.
/// Unfortunately the underlying type doesn't allow direct
/// comparison, but that's ok for our purposes.
fn modifiers_first(a: &Key, b: &Key) -> Ordering {
    if MODIFIER_KEYS.contains(a) {
        if MODIFIER_KEYS.contains(b) {
            Ordering::Equal
        } else {
            Ordering::Less
        }
    } else if MODIFIER_KEYS.contains(b) {
        Ordering::Greater
    } else {
        // Neither are modifiers
        Ordering::Equal
    }
}

fn modifiers_last(a: &Key, b: &Key) -> Ordering {
    modifiers_first(a, b).reverse()
}