feat: add dispatch strategy features with auto-selection and benchmark

support

Add `dispatch_linear`, `dispatch_tree`, and `dispatch_phf` as mutually
exclusive features for selecting the command dispatch strategy. When no
strategy feature is enabled, an auto-selection heuristic picks the
optimal strategy based on command table characteristics (size, name
length, nesting depth).

Add the `bench_support` feature to compile all three generators for the
benchmark harness, and introduce `bench_cell!` to generate benchmark
cells comparing strategies.

The PHF generator uses a CHD minimal perfect hash for O(1) lookup
independent of table size, while the trie generator was refactored to
use a shared fallback method, keeping code size linear in table size.

1 files changed, 260 insertions, 0 deletions

diff --git a/mingling_macros/src/systems/dispatch_phf_gen.rs b/mingling_macros/src/systems/dispatch_phf_gen.rs
new file mode 100644
index 0000000..97210e2
--- /dev/null
+++ b/mingling_macros/src/systems/dispatch_phf_gen.rs
@@ -0,0 +1,260 @@
+// Doc Not Optimize
+//! Perfect-hash dispatch generator (`dispatch_phf` feature).
+//!
+//! Generates a `dispatch_args()` body using a **CHD minimal perfect hash**
+//! (Belazzougui, Botelho, Dietzfelbinger) computed at macro-expansion time
+//! over the normalized command names.
+//!
+//! Semantics match `dispatch_list_gen` / `dispatch_tree_gen` exactly:
+//! - the longest registered name that is a word-aligned prefix of the input
+//!   wins (scan the input word-by-word from the longest possible prefix down
+//!   to the first word);
+//! - every hash hit is verified with an exact byte equality against the
+//!   stored key (the hash alone is not a proof of membership);
+//! - duplicate normalized names are dropped, keeping the first registration
+//!   ("first wins", same as the other generators).
+//!
+//! Runtime cost per lookup: one byte scan over the first `max_words` words
+//! plus at most `max_words` (typically 1–3) double-hash + verify attempts.
+//! Code size is O(1) in the number of commands.
+
+use std::collections::HashSet;
+
+use proc_macro2::TokenStream;
+use quote::quote;
+
+/// Hash used both at macro time (seed search) and inside the generated code.
+/// FNV-1a over the bytes followed by a splitmix64 finalizer for good
+/// avalanche; fully deterministic and platform independent.
+fn phf_hash(s: &str, seed: u64) -> u64 {
+    let mut h = 0xcbf2_9ce4_8422_2325u64 ^ seed;
+    for &b in s.as_bytes() {
+        h ^= u64::from(b);
+        h = h.wrapping_mul(0x0100_0000_01b3);
+    }
+    h ^= h >> 33;
+    h = h.wrapping_mul(0xff51_afd7_ed55_8ccd);
+    h ^= h >> 33;
+    h = h.wrapping_mul(0xc4ce_b9fe_1a85_ec53);
+    h ^= h >> 33;
+    h
+}
+
+/// CHD construction: bucket the keys by `h1`, then per bucket find a
+/// displacement `d` such that `(h0(key) + d) % n` is globally collision free.
+/// Returns `(seed0, seed1, bucket_count, displacements)`.
+///
+/// Note: this function performs `u64` → `usize` casts that may truncate on
+/// 32-bit platforms. This is intentional and acceptable here because the
+/// number of keys is derived from the macro input (command names), which is
+/// far smaller than `u32::MAX` in practice on all supported targets.
+#[allow(clippy::cast_possible_truncation)]
+fn build_chd(keys: &[String]) -> (u64, u64, usize, Vec<u64>) {
+    let n = keys.len();
+    debug_assert!(n > 0);
+    let m = n as u64;
+    let b = n.div_ceil(2).max(1);
+
+    for attempt in 0..10_000u64 {
+        // Fixed magic constants used as seed bases; the `^ attempt * prime`
+        // pattern produces a fresh seed pair on each attempt.
+        #[allow(clippy::unreadable_literal)]
+        let seed0 = 0x9e37_79b9_7f4a_7c15u64 ^ attempt.wrapping_mul(0xbf58_476d_1ce4_e5b9);
+        #[allow(clippy::unreadable_literal)]
+        let seed1 = 0x94d0_49bb_1331_11ebu64 ^ attempt.wrapping_mul(0xd6e8_feb8_6659_fd93);
+
+        let mut buckets: Vec<Vec<usize>> = vec![Vec::new(); b];
+        for (i, key) in keys.iter().enumerate() {
+            let h1 = (phf_hash(key, seed1) % b as u64) as usize;
+            buckets[h1].push(i);
+        }
+
+        // Place the largest buckets first; they have the least freedom.
+        let mut order: Vec<usize> = (0..b).collect();
+        order.sort_by_key(|&j| std::cmp::Reverse(buckets[j].len()));
+
+        let mut disp = vec![0u64; b];
+        let mut occupied = vec![false; m as usize];
+        let mut ok = true;
+
+        'attempt: for &j in &order {
+            if buckets[j].is_empty() {
+                continue;
+            }
+            for d in 0..m {
+                let mut seen: HashSet<usize> = HashSet::with_capacity(buckets[j].len());
+                for &i in &buckets[j] {
+                    let h0 = (phf_hash(&keys[i], seed0) % m) as usize;
+                    let slot = (h0 + d as usize) % m as usize;
+                    if occupied[slot] || !seen.insert(slot) {
+                        break;
+                    }
+                }
+                if seen.len() == buckets[j].len() {
+                    for &i in &buckets[j] {
+                        let h0 = (phf_hash(&keys[i], seed0) % m) as usize;
+                        let slot = (h0 + d as usize) % m as usize;
+                        occupied[slot] = true;
+                    }
+                    disp[j] = d;
+                    continue 'attempt;
+                }
+            }
+            ok = false;
+            break;
+        }
+
+        if ok {
+            return (seed0, seed1, b, disp);
+        }
+    }
+
+    panic!("dispatch_phf: failed to construct a perfect hash for {n} keys");
+}
+
+// This function is long because it's generating a large body of code we
+// don't want to split; keeping it as one codegen function is far easier to
+// maintain than splitting it into many small pieces.
+#[allow(clippy::too_many_lines)]
+/// Generate the `dispatch_args()` function body for a `ProgramCollect` impl.
+pub(crate) fn gen_dispatch_args_phf(entries: &[(String, String, String)]) -> TokenStream {
+    // Normalize names (dots become spaces), dropping duplicate names while
+    // keeping the first registration ("first wins").
+    let mut seen = HashSet::new();
+    let mut nodes: Vec<(String, String)> = Vec::new();
+    for (name, disp, _) in entries {
+        let name = name.replace('.', " ");
+        if seen.insert(name.clone()) {
+            nodes.push((name, disp.clone()));
+        }
+    }
+
+    let fallback_body = quote! {
+        fn dispatch_args(
+            raw: &[String],
+        ) -> Result<::mingling::AnyOutput<Self::Enum>, ::mingling::error::ProgramInternalExecuteError>
+        {
+            Ok(Self::build_entry_fallback(raw.to_vec()))
+        }
+    };
+    if nodes.is_empty() {
+        return fallback_body;
+    }
+
+    let max_words = nodes
+        .iter()
+        .map(|(name, _)| name.split_whitespace().count())
+        .max()
+        .unwrap();
+    let keys: Vec<String> = nodes.iter().map(|(name, _)| name.clone()).collect();
+    let (seed0, seed1, b, disp) = build_chd(&keys);
+
+    let name_lits: Vec<proc_macro2::Literal> = nodes
+        .iter()
+        .map(|(name, _)| proc_macro2::Literal::string(name))
+        .collect();
+    let disp_lits: Vec<proc_macro2::Literal> = disp
+        .iter()
+        .map(|d| proc_macro2::Literal::u64_unsuffixed(*d))
+        .collect();
+
+    let arms: Vec<TokenStream> = nodes
+        .iter()
+        .enumerate()
+        .map(|(idx, (_, disp_type))| {
+            let idx_lit = proc_macro2::Literal::usize_unsuffixed(idx);
+            let disp_ident = proc_macro2::Ident::new(disp_type, proc_macro2::Span::call_site());
+            quote! {
+                #idx_lit => <#disp_ident as ::mingling::Dispatcher<Self::Enum>>::begin(
+                    &#disp_ident::default(),
+                    __args,
+                ),
+            }
+        })
+        .collect();
+
+    let max_words_lit = proc_macro2::Literal::usize_unsuffixed(max_words);
+    let seed0_lit = proc_macro2::Literal::u64_unsuffixed(seed0);
+    let seed1_lit = proc_macro2::Literal::u64_unsuffixed(seed1);
+    let b_lit = proc_macro2::Literal::usize_unsuffixed(b);
+    let m_lit = proc_macro2::Literal::usize_unsuffixed(keys.len());
+
+    quote! {
+        fn dispatch_args(
+            raw: &[String],
+        ) -> Result<::mingling::AnyOutput<Self::Enum>, ::mingling::error::ProgramInternalExecuteError>
+        {
+            const __DISPATCH_PHF_MAX_WORDS: usize = #max_words_lit;
+            const __DISPATCH_PHF_SEED0: u64 = #seed0_lit;
+            const __DISPATCH_PHF_SEED1: u64 = #seed1_lit;
+            const __DISPATCH_PHF_BUCKETS: usize = #b_lit;
+            const __DISPATCH_PHF_MOD: usize = #m_lit;
+            static __DISPATCH_PHF_KEYS: &[&str] = &[#(#name_lits),*];
+            static __DISPATCH_PHF_DISP: &[u64] = &[#(#disp_lits),*];
+
+            #[inline(always)]
+            fn __dispatch_phf_hash(s: &str, seed: u64) -> u64 {
+                let mut h = 0xcbf29ce484222325u64 ^ seed;
+                for &b in s.as_bytes() {
+                    h ^= b as u64;
+                    h = h.wrapping_mul(0x100000001b3);
+                }
+                h ^= h >> 33;
+                h = h.wrapping_mul(0xff51afd7ed558ccd);
+                h ^= h >> 33;
+                h = h.wrapping_mul(0xc4ceb9fe1a85ec53);
+                h ^= h >> 33;
+                h
+            }
+
+            let raw_string = format!("{} ", raw.join(" "));
+            let raw_str = raw_string.as_str();
+            let bytes = raw_str.as_bytes();
+
+            // Record the byte offset of the space that terminates each word
+            // (`raw_str` always ends with a trailing space).
+            let mut __ends = [0usize; #max_words_lit];
+            let mut __w = 0usize;
+            let mut __i = 0usize;
+            while __w < __DISPATCH_PHF_MAX_WORDS && __i < bytes.len() {
+                if bytes[__i] == b' ' {
+                    __ends[__w] = __i;
+                    __w += 1;
+                }
+                __i += 1;
+            }
+
+            // Scan the input from the longest possible prefix down to the
+            // first word, so the longest registered prefix wins (mirroring
+            // the linear list and trie generators).
+            let mut __k = __w;
+            while __k > 0 {
+                let __cand = &raw_str[..__ends[__k - 1]];
+                let __h1 = (__dispatch_phf_hash(__cand, __DISPATCH_PHF_SEED1)
+                    % __DISPATCH_PHF_BUCKETS as u64) as usize;
+                let __d = __DISPATCH_PHF_DISP[__h1];
+                let __idx = ((__dispatch_phf_hash(__cand, __DISPATCH_PHF_SEED0)
+                    % __DISPATCH_PHF_MOD as u64)
+                    + __d)
+                    % __DISPATCH_PHF_MOD as u64;
+                let __idx = __idx as usize;
+                if __DISPATCH_PHF_KEYS[__idx].as_bytes() == __cand.as_bytes() {
+                    let __args: Vec<String> = raw.iter().skip(__k).cloned().collect();
+                    let __cp = match __idx {
+                        #(#arms)*
+                        _ => unreachable!("dispatch_phf: perfect-hash index out of range"),
+                    };
+                    return match __cp {
+                        ::mingling::ChainProcess::Ok(any_output) => Ok(any_output.0),
+                        ::mingling::ChainProcess::Err(chain_process_error) => {
+                            Err(chain_process_error.into())
+                        }
+                    };
+                }
+                __k -= 1;
+            }
+
+            Ok(Self::build_entry_fallback(raw.to_vec()))
+        }
+    }
+}