Skip to main content

btn_recognizer/
fsm_engine.rs

1//! 哈希表驱动的有限状态机引擎
2//!
3//! 核心数据结构: `HashMap<(CS, EVT), (NS, MOTION)>`
4//!
5//! - **CS** (Current State): 当前状态
6//! - **EVT** (Event): 触发事件
7//! - **NS** (Next State): 迁移后的目标状态
8//! - **MOTION** (Motion): 迁移时执行的副作用/动作
9//!
10//! 这是 Mealy 机模型 —— 输出(motion)绑定在转移弧上,而非状态节点上。
11
12use std::collections::hash_map::Entry;
13use std::collections::HashMap;
14use std::error::Error;
15use std::fmt::{self, Debug};
16use std::hash::Hash;
17
18// ── Error ──────────────────────────────────────────────────────────
19
20/// FSM 运行时错误
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub enum FsmError<S, E>
23where
24    S: Debug + Clone,
25    E: Debug + Clone,
26{
27    /// 在当前状态下收到未注册的事件 —— 状态机存在"空洞"
28    NoTransition { state: S, event: E },
29}
30
31impl<S, E> fmt::Display for FsmError<S, E>
32where
33    S: Debug + Clone,
34    E: Debug + Clone,
35{
36    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
37        match self {
38            Self::NoTransition { state, event } => {
39                write!(f, "FSM NoTransition: state={state:?} event={event:?}")
40            }
41        }
42    }
43}
44
45impl<S, E> Error for FsmError<S, E>
46where
47    S: Debug + Clone,
48    E: Debug + Clone,
49{
50}
51
52/// FSM 构建错误。
53///
54/// 构建器会延迟报告注册阶段发现的错误,从而保留
55/// `Fsm::builder().on(...).build()` 的链式调用风格。
56#[derive(Debug, Clone, PartialEq, Eq)]
57pub enum BuildError<S, E>
58where
59    S: Debug + Clone,
60    E: Debug + Clone,
61{
62    /// 构建器没有设置初始状态。
63    MissingInitialState,
64    /// 同一个 `(state, event)` 被注册了多次。
65    DuplicateTransition { state: S, event: E },
66}
67
68impl<S, E> fmt::Display for BuildError<S, E>
69where
70    S: Debug + Clone,
71    E: Debug + Clone,
72{
73    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
74        match self {
75            Self::MissingInitialState => write!(f, "FSM initial state is required"),
76            Self::DuplicateTransition { state, event } => {
77                write!(
78                    f,
79                    "FSM duplicate transition: state={state:?} event={event:?}"
80                )
81            }
82        }
83    }
84}
85
86impl<S, E> Error for BuildError<S, E>
87where
88    S: Debug + Clone,
89    E: Debug + Clone,
90{
91}
92
93// ── Transition & TransitionKey ─────────────────────────────────────
94
95/// 转移弧:目标状态 + 副作用动作
96#[derive(Debug, Clone, PartialEq, Eq)]
97struct Transition<S, M> {
98    next_state: S,
99    motion: M,
100}
101
102/// HashMap key: `(current_state, event)`
103type TransitionKey<S, E> = (S, E);
104
105// ── Fsm ────────────────────────────────────────────────────────────
106
107/// 哈希表驱动的有限状态机
108///
109/// # 类型参数
110/// - `S`: 状态类型,需实现 `Hash + Eq + Clone + Debug`
111/// - `E`: 事件类型,需实现 `Hash + Eq + Clone + Debug`
112/// - `M`: 动作类型,需实现 `Clone + Debug`
113///
114/// # 示例
115/// ```
116/// use fsm_engine::Fsm;
117///
118/// #[derive(Debug, Clone, PartialEq, Eq, Hash)]
119/// enum State { A, B }
120///
121/// #[derive(Debug, Clone, PartialEq, Eq, Hash)]
122/// enum Event { Go }
123///
124/// #[derive(Debug, Clone)]
125/// enum Motion { Print }
126///
127/// let fsm = Fsm::builder()
128///     .initial_state(State::A)
129///     .on(State::A, Event::Go, State::B, Motion::Print)
130///     .build()
131///     .unwrap();
132/// ```
133#[derive(Debug, Clone)]
134pub struct Fsm<S, E, M>
135where
136    S: Hash + Eq + Clone + Debug,
137    E: Hash + Eq + Clone + Debug,
138    M: Clone + Debug,
139{
140    /// 转移表:`HashMap<(cs, evt), (ns, motion)>`
141    transitions: HashMap<TransitionKey<S, E>, Transition<S, M>>,
142    /// 当前状态
143    state: S,
144    /// 初始状态(用于 reset)
145    initial_state: S,
146}
147
148impl<S, E, M> Fsm<S, E, M>
149where
150    S: Hash + Eq + Clone + Debug,
151    E: Hash + Eq + Clone + Debug,
152    M: Clone + Debug,
153{
154    // ── 构造器入口 ────────────────────────────────────────────────
155
156    /// 获取 Builder,用于声明式地构建转移表
157    pub fn builder() -> FsmBuilder<S, E, M> {
158        FsmBuilder::new()
159    }
160
161    // ── 运行时 API ────────────────────────────────────────────────
162
163    /// 摄入一个事件,触发状态迁移并返回 `(下一状态, 动作)`
164    ///
165    /// # Errors
166    /// 若当前状态下没有为该事件注册的转移,返回 `FsmError::NoTransition`
167    pub fn step(&mut self, event: &E) -> Result<(&S, &M), FsmError<S, E>> {
168        let key = (self.state.clone(), event.clone());
169        let transition = self
170            .transitions
171            .get(&key)
172            .ok_or_else(|| FsmError::NoTransition {
173                state: self.state.clone(),
174                event: event.clone(),
175            })?;
176
177        self.state = transition.next_state.clone();
178        Ok((&self.state, &transition.motion))
179    }
180
181    /// 只做状态迁移,忽略 motion(语法糖)
182    pub fn step_state(&mut self, event: &E) -> Result<&S, FsmError<S, E>> {
183        self.step(event).map(|(s, _)| s)
184    }
185
186    /// 查询当前状态
187    pub fn current_state(&self) -> &S {
188        &self.state
189    }
190
191    /// 查询初始状态
192    pub fn initial_state(&self) -> &S {
193        &self.initial_state
194    }
195
196    /// 重置到初始状态
197    pub fn reset(&mut self) {
198        self.state = self.initial_state.clone();
199    }
200
201    /// 转移表的大小(注册的转移弧数量)
202    pub fn transition_count(&self) -> usize {
203        self.transitions.len()
204    }
205
206    /// 检查某个转移是否存在
207    pub fn has_transition(&self, state: &S, event: &E) -> bool {
208        self.transitions
209            .contains_key(&(state.clone(), event.clone()))
210    }
211
212    /// 遍历所有已注册的转移弧,返回 `Vec<(cs, evt, ns, motion)>`
213    pub fn transitions(&self) -> Vec<(&S, &E, &S, &M)> {
214        self.transitions
215            .iter()
216            .map(|((cs, evt), t)| (cs, evt, &t.next_state, &t.motion))
217            .collect()
218    }
219}
220
221// ── Builder ────────────────────────────────────────────────────────
222
223/// FSM 构建器 —— 声明式地构造转移表
224///
225/// # 示例
226/// ```
227/// # use fsm_engine::{Fsm, FsmBuilder};
228/// let fsm = Fsm::<i32, &str, ()>::builder()
229///     .initial_state(0)
230///     .on(0, "inc", 1, ())
231///     .on(1, "inc", 2, ())
232///     .on(1, "dec", 0, ())
233///     .build()
234///     .unwrap();
235/// ```
236#[derive(Debug, Clone)]
237pub struct FsmBuilder<S, E, M>
238where
239    S: Hash + Eq + Clone + Debug,
240    E: Hash + Eq + Clone + Debug,
241    M: Clone + Debug,
242{
243    transitions: HashMap<TransitionKey<S, E>, Transition<S, M>>,
244    initial_state: Option<S>,
245    error: Option<BuildError<S, E>>,
246}
247
248impl<S, E, M> FsmBuilder<S, E, M>
249where
250    S: Hash + Eq + Clone + Debug,
251    E: Hash + Eq + Clone + Debug,
252    M: Clone + Debug,
253{
254    pub fn new() -> Self {
255        Self {
256            transitions: HashMap::new(),
257            initial_state: None,
258            error: None,
259        }
260    }
261
262    /// 设置初始状态
263    pub fn initial_state(mut self, state: S) -> Self {
264        self.initial_state = Some(state);
265        self
266    }
267
268    /// 注册一条转移弧: `(cs, evt) → (ns, motion)`
269    ///
270    /// 重复注册同一个 `(cs, evt)` 时保留第一条转移,并由 [`Self::build`]
271    /// 返回 [`BuildError::DuplicateTransition`]。若存在多个重复定义,报告
272    /// 第一个被检测到的重复键。
273    pub fn on(mut self, cs: S, evt: E, ns: S, motion: M) -> Self {
274        match self.transitions.entry((cs, evt)) {
275            Entry::Vacant(entry) => {
276                entry.insert(Transition {
277                    next_state: ns,
278                    motion,
279                });
280            }
281            Entry::Occupied(entry) => {
282                if self.error.is_none() {
283                    let (state, event) = entry.key();
284                    self.error = Some(BuildError::DuplicateTransition {
285                        state: state.clone(),
286                        event: event.clone(),
287                    });
288                }
289            }
290        }
291        self
292    }
293
294    /// 从任意迭代器批量注册转移弧。
295    ///
296    /// 重复键的处理与 [`Self::on`] 一致,在 [`Self::build`] 时报告错误。
297    pub fn on_many<I>(mut self, transitions: I) -> Self
298    where
299        I: IntoIterator<Item = (S, E, S, M)>,
300    {
301        for (cs, evt, ns, motion) in transitions {
302            self = self.on(cs, evt, ns, motion);
303        }
304        self
305    }
306
307    /// 消费 builder,产出 Fsm 实例
308    ///
309    /// # Errors
310    ///
311    /// - 未设置初始状态时返回 [`BuildError::MissingInitialState`]。
312    /// - 注册了重复转移时返回 [`BuildError::DuplicateTransition`]。
313    ///
314    /// 若两类错误同时存在,优先报告缺少初始状态。
315    pub fn build(self) -> Result<Fsm<S, E, M>, BuildError<S, E>> {
316        let initial_state = self.initial_state.ok_or(BuildError::MissingInitialState)?;
317
318        if let Some(error) = self.error {
319            return Err(error);
320        }
321
322        Ok(Fsm {
323            transitions: self.transitions,
324            state: initial_state.clone(),
325            initial_state,
326        })
327    }
328}
329
330// ── 默认实现 ───────────────────────────────────────────────────────
331
332impl<S, E, M> Default for FsmBuilder<S, E, M>
333where
334    S: Hash + Eq + Clone + Debug,
335    E: Hash + Eq + Clone + Debug,
336    M: Clone + Debug,
337{
338    fn default() -> Self {
339        Self::new()
340    }
341}
342
343// ── 测试 ───────────────────────────────────────────────────────────
344
345#[cfg(test)]
346mod tests {
347    use super::*;
348
349    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
350    enum State {
351        Idle,
352        Running,
353        Stopped,
354    }
355
356    #[derive(Debug, Clone, PartialEq, Eq, Hash)]
357    enum Event {
358        Start,
359        Stop,
360        Reset,
361    }
362
363    #[derive(Debug, Clone, PartialEq)]
364    enum Motion {
365        Log(String),
366        Alert,
367        None,
368    }
369
370    fn build_test_fsm() -> Fsm<State, Event, Motion> {
371        Fsm::builder()
372            .initial_state(State::Idle)
373            .on(
374                State::Idle,
375                Event::Start,
376                State::Running,
377                Motion::Log("started".into()),
378            )
379            .on(State::Running, Event::Stop, State::Stopped, Motion::Alert)
380            .on(State::Stopped, Event::Reset, State::Idle, Motion::None)
381            .build()
382            .unwrap()
383    }
384
385    #[test]
386    fn test_basic_transition() {
387        let mut fsm = build_test_fsm();
388        assert_eq!(*fsm.current_state(), State::Idle);
389
390        let (ns, motion) = fsm.step(&Event::Start).unwrap();
391        assert_eq!(*ns, State::Running);
392        assert_eq!(*motion, Motion::Log("started".into()));
393    }
394
395    #[test]
396    fn test_no_transition_error() {
397        let mut fsm = build_test_fsm();
398        let error = fsm.step(&Event::Stop).unwrap_err();
399        assert_eq!(
400            error,
401            FsmError::NoTransition {
402                state: State::Idle,
403                event: Event::Stop,
404            }
405        );
406        assert_eq!(*fsm.current_state(), State::Idle);
407    }
408
409    #[test]
410    fn test_reset() {
411        let mut fsm = build_test_fsm();
412        fsm.step(&Event::Start).unwrap();
413        fsm.step(&Event::Stop).unwrap();
414        assert_eq!(*fsm.current_state(), State::Stopped);
415
416        fsm.reset();
417        assert_eq!(*fsm.current_state(), State::Idle);
418    }
419
420    #[test]
421    fn test_full_cycle() {
422        let mut fsm = build_test_fsm();
423        fsm.step(&Event::Start).unwrap();
424        fsm.step(&Event::Stop).unwrap();
425        fsm.step(&Event::Reset).unwrap();
426        assert_eq!(*fsm.current_state(), State::Idle);
427    }
428
429    #[test]
430    fn test_builder_requires_initial_state() {
431        let error = Fsm::<State, Event, Motion>::builder().build().unwrap_err();
432        assert_eq!(error, BuildError::MissingInitialState);
433    }
434
435    #[test]
436    fn test_duplicate_transition_is_a_build_error() {
437        let error = Fsm::builder()
438            .initial_state(State::Idle)
439            .on(State::Idle, Event::Start, State::Running, Motion::Alert)
440            .on(State::Idle, Event::Start, State::Stopped, Motion::None)
441            .build()
442            .unwrap_err();
443
444        assert_eq!(
445            error,
446            BuildError::DuplicateTransition {
447                state: State::Idle,
448                event: Event::Start,
449            }
450        );
451    }
452
453    #[test]
454    fn test_first_duplicate_transition_is_reported() {
455        let error = Fsm::builder()
456            .initial_state(State::Idle)
457            .on(State::Idle, Event::Start, State::Running, Motion::Alert)
458            .on(State::Idle, Event::Start, State::Stopped, Motion::None)
459            .on(State::Running, Event::Stop, State::Idle, Motion::Alert)
460            .on(State::Running, Event::Stop, State::Stopped, Motion::None)
461            .build()
462            .unwrap_err();
463
464        assert_eq!(
465            error,
466            BuildError::DuplicateTransition {
467                state: State::Idle,
468                event: Event::Start,
469            }
470        );
471    }
472
473    #[test]
474    fn test_missing_initial_state_takes_precedence() {
475        let error = Fsm::builder()
476            .on(State::Idle, Event::Start, State::Running, Motion::Alert)
477            .on(State::Idle, Event::Start, State::Stopped, Motion::None)
478            .build()
479            .unwrap_err();
480
481        assert_eq!(error, BuildError::MissingInitialState);
482    }
483
484    #[test]
485    fn test_on_many_accepts_into_iterator() {
486        let transitions = [
487            (State::Idle, Event::Start, State::Running, Motion::Alert),
488            (State::Running, Event::Stop, State::Stopped, Motion::None),
489        ];
490
491        let fsm = Fsm::builder()
492            .initial_state(State::Idle)
493            .on_many(transitions)
494            .on_many(std::iter::once((
495                State::Stopped,
496                Event::Reset,
497                State::Idle,
498                Motion::Alert,
499            )))
500            .build()
501            .unwrap();
502
503        assert_eq!(fsm.transition_count(), 3);
504    }
505
506    #[test]
507    fn test_error_types_implement_std_error() {
508        fn assert_error<T: std::error::Error>() {}
509
510        assert_error::<FsmError<State, Event>>();
511        assert_error::<BuildError<State, Event>>();
512    }
513
514    #[test]
515    fn test_transition_count() {
516        let fsm = build_test_fsm();
517        assert_eq!(fsm.transition_count(), 3);
518    }
519}