diff options
Diffstat (limited to 'mingling_macros/src')
| -rw-r--r-- | mingling_macros/src/bench_cell.rs | 210 | ||||
| -rw-r--r-- | mingling_macros/src/func/program_final_gen.rs | 87 | ||||
| -rw-r--r-- | mingling_macros/src/lib.rs | 42 | ||||
| -rw-r--r-- | mingling_macros/src/systems.rs | 86 | ||||
| -rw-r--r-- | mingling_macros/src/systems/dispatch_auto.rs | 110 | ||||
| -rw-r--r-- | mingling_macros/src/systems/dispatch_phf_gen.rs | 260 | ||||
| -rw-r--r-- | mingling_macros/src/systems/dispatch_tree_gen.rs | 288 |
7 files changed, 982 insertions, 101 deletions
diff --git a/mingling_macros/src/bench_cell.rs b/mingling_macros/src/bench_cell.rs new file mode 100644 index 0000000..7353966 --- /dev/null +++ b/mingling_macros/src/bench_cell.rs @@ -0,0 +1,210 @@ +//! Workspace-internal `bench_cell!` implementation for the `mingling_bench` +//! harness (compiled only with the `bench_support` feature). + +use proc_macro::TokenStream; +use quote::quote; +use syn::parse::{Parse, ParseStream}; +use syn::{Ident, LitStr, Result as SynResult, Token, bracketed}; + +use crate::systems::dispatch_auto; +use crate::systems::dispatch_list_gen::gen_dispatch_args; +use crate::systems::dispatch_phf_gen::gen_dispatch_args_phf; +use crate::systems::dispatch_tree_gen::gen_dispatch_args_trie; + +struct BenchCellInput { + strategy: Ident, + module: Ident, + entries: Vec<(LitStr, Ident)>, +} + +impl Parse for BenchCellInput { + fn parse(input: ParseStream<'_>) -> SynResult<Self> { + let strategy = input.parse()?; + input.parse::<Token![,]>()?; + let module = input.parse()?; + input.parse::<Token![,]>()?; + let content; + bracketed!(content in input); + let mut entries = Vec::new(); + while !content.is_empty() { + let name = content.parse()?; + content.parse::<Token![=>]>()?; + let disp = content.parse()?; + entries.push((name, disp)); + if content.is_empty() { + break; + } + content.parse::<Token![,]>()?; + } + Ok(Self { + strategy, + module, + entries, + }) + } +} + +pub(crate) fn bench_cell_impl(input: TokenStream) -> TokenStream { + let input = syn::parse_macro_input!(input as BenchCellInput); + + let entries: Vec<(String, String, String)> = input + .entries + .iter() + .map(|(name, disp)| (name.value(), disp.to_string(), String::new())) + .collect(); + + let (dispatch, extra, chosen) = match input.strategy.to_string().as_str() { + "dispatch_linear" => (gen_dispatch_args(&entries), quote! {}, "dispatch_linear"), + "dispatch_tree" => { + let (d, e) = gen_dispatch_args_trie(&entries); + (d, e, "dispatch_tree") + } + "dispatch_phf" => (gen_dispatch_args_phf(&entries), quote! {}, "dispatch_phf"), + "dispatch_auto" => match dispatch_auto::select_strategy(&entries) { + dispatch_auto::DispatchStrategy::Linear => { + (gen_dispatch_args(&entries), quote! {}, "dispatch_linear") + } + dispatch_auto::DispatchStrategy::Trie => { + let (d, e) = gen_dispatch_args_trie(&entries); + (d, e, "dispatch_tree") + } + dispatch_auto::DispatchStrategy::Phf => { + (gen_dispatch_args_phf(&entries), quote! {}, "dispatch_phf") + } + }, + other => panic!("bench_cell: unknown strategy `{other}`"), + }; + + // Keep the generated dispatch out of the harness loop's inline budget: + // the loop calls it once per iteration, and large tables (hundreds of + // arms) would otherwise make LLVM attempt to inline a huge function into + // the 50k-iteration loop, exploding compile time and memory. Production + // codegen would not inline such functions either. The trie generator + // also emits its shared `__trie_fallback` method via `extra`, so parse + // the whole item list (a `syn::File`) and annotate the first function + // (dispatch_args). + let mut file: syn::File = syn::parse2(dispatch) + .unwrap_or_else(|e| panic!("bench_cell: generated dispatch_args failed to parse: {e}")); + if let Some(syn::Item::Fn(dispatch_fn)) = file.items.first_mut() { + dispatch_fn.attrs.push(syn::parse_quote!(#[inline(never)])); + } + let dispatch = quote!(#file); + + // The trie fallback is a generic method that must live in an inherent + // impl of the cell type (it references no `Self` associated types). + let extra_impl = if extra.is_empty() { + quote! {} + } else { + quote! { + impl X { + #extra + } + } + }; + + let module = &input.module; + let name_lits: Vec<proc_macro2::Literal> = input + .entries + .iter() + .map(|(name, _)| proc_macro2::Literal::string(&name.value())) + .collect(); + + let mut dispatchers = proc_macro2::TokenStream::new(); + for (_, disp) in &input.entries { + dispatchers.extend(quote! { + #[derive(Default)] + pub struct #disp; + impl Dispatcher<X> for #disp { + fn begin(&self, _args: Vec<String>) -> ChainProcess<X> { + ChainProcess::Ok((AnyOutput::new(Dummy), NextProcess::Chain)) + } + } + }); + } + + quote! { + pub mod #module { + use ::mingling::{AnyOutput, ChainProcess, Dispatcher, Grouped, NextProcess}; + + #dispatchers + + #[derive(Clone, Copy)] + pub struct X; + unsafe impl Grouped<X> for X { + fn member_id() -> X { + X + } + } + + pub struct Dummy; + unsafe impl Grouped<X> for Dummy { + fn member_id() -> X { + X + } + } + + pub struct EntryFallback(pub Vec<String>); + unsafe impl Grouped<X> for EntryFallback { + fn member_id() -> X { + X + } + } + + impl crate::BenchDispatch for X { + type Enum = X; + fn build_entry_fallback(args: Vec<String>) -> AnyOutput<Self::Enum> { + AnyOutput::new(EntryFallback(args)) + } + #dispatch + } + + #extra_impl + + pub static NAMES: &[&str] = &[#(#name_lits),*]; + + /// The strategy this cell was generated with (for `dispatch_auto` + /// cells this is the auto-selected strategy). + pub static STRATEGY: &str = #chosen; + + /// Time dispatch over a corpus; returns (hit_ns, miss_ns), best of + /// 5 rounds of 50k dispatches. + pub fn measure(hits: &[Vec<String>], misses: &[Vec<String>]) -> (f64, f64) { + let mut acc = 0usize; + for i in 0..2_000 { + let r = <X as crate::BenchDispatch>::dispatch_args(&hits[i % hits.len()]); + acc = acc.wrapping_add(match r { + Ok(_) => 1, + Err(_) => 2, + }); + } + std::hint::black_box(acc); + + let time = |corpus: &[Vec<String>]| -> f64 { + let mut best = f64::MAX; + for _ in 0..5 { + let start = std::time::Instant::now(); + let mut acc = 0usize; + for i in 0..50_000 { + let r = <X as crate::BenchDispatch>::dispatch_args( + &corpus[i % corpus.len()], + ); + acc = acc.wrapping_add(match r { + Ok(_) => 1, + Err(_) => 2, + }); + } + let el = start.elapsed().as_nanos() as f64 / 50_000.0; + std::hint::black_box(acc); + if el < best { + best = el; + } + } + best + }; + + (time(hits), time(misses)) + } + } + } + .into() +} diff --git a/mingling_macros/src/func/program_final_gen.rs b/mingling_macros/src/func/program_final_gen.rs index ceee66d..b67531e 100644 --- a/mingling_macros/src/func/program_final_gen.rs +++ b/mingling_macros/src/func/program_final_gen.rs @@ -15,9 +15,17 @@ use crate::RENDERERS_EXIST; #[cfg(feature = "structural_renderer")] use crate::STRUCTURAL_RENDERERS; use crate::get_global_set; -#[cfg(not(feature = "dispatch_tree"))] +#[cfg(all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")))] +use crate::systems::dispatch_auto; +#[cfg(all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")))] use crate::systems::dispatch_list_gen; -#[cfg(feature = "dispatch_tree")] +#[cfg(feature = "dispatch_phf")] +use crate::systems::dispatch_phf_gen; +#[cfg(all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")))] +use crate::systems::dispatch_phf_gen; +#[cfg(all(not(feature = "dispatch_phf"), feature = "dispatch_tree"))] +use crate::systems::dispatch_tree_gen; +#[cfg(all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")))] use crate::systems::dispatch_tree_gen; #[cfg(feature = "async")] @@ -27,7 +35,8 @@ const ASYNC_ENABLED: bool = false; /// Generate the `get_nodes()` function body for a `ProgramCollect` impl. /// -/// Shared by both dispatch strategies (trie and linear list); it only depends +/// Shared by all three dispatch strategies (linear list, trie, perfect hash); +/// it only depends /// on the compile-time-collected `__internal_dispatcher_*` statics. fn gen_get_nodes(entries: &[(String, String, String)]) -> proc_macro2::TokenStream { let mut node_entries = Vec::new(); @@ -170,28 +179,67 @@ pub(crate) fn program_final_gen_impl(_input: TokenStream) -> TokenStream { }) .collect(); - // The `dispatch_tree` feature only selects the internal matching strategy: - // a char-level trie when enabled, a linear longest-prefix list otherwise. - #[cfg(feature = "dispatch_tree")] - let dispatch_gen = { + // The dispatch strategy is selected by features: + // - `dispatch_phf` (perfect hash) has priority + // - `dispatch_tree` (char-level trie) + // - `dispatch_linear`, or no dispatch feature at all ("auto" mode), picks + // the best strategy from the command table via + // `dispatch_auto::select_strategy`. + // The three dispatch features are mutually exclusive (see the crate-level + // `compile_error!` in lib.rs). + // + // `dispatch_extra` carries items that must live in an inherent impl of + // the program type (currently the trie's `__trie_fallback` method). + #[cfg(feature = "dispatch_phf")] + let (dispatch_gen, dispatch_extra) = { let get_nodes_fn = gen_get_nodes(&entries); - let dispatch_fn = dispatch_tree_gen::gen_dispatch_args_trie(&entries); + let dispatch_fn = dispatch_phf_gen::gen_dispatch_args_phf(&entries); - quote! { - #get_nodes_fn - #dispatch_fn - } + ( + quote! { + #get_nodes_fn + #dispatch_fn + }, + quote! {}, + ) }; - #[cfg(not(feature = "dispatch_tree"))] - let dispatch_gen = { + #[cfg(all(not(feature = "dispatch_phf"), feature = "dispatch_tree"))] + let (dispatch_gen, dispatch_extra) = { let get_nodes_fn = gen_get_nodes(&entries); - let dispatch_fn = dispatch_list_gen::gen_dispatch_args(&entries); + let (dispatch_fn, extra) = dispatch_tree_gen::gen_dispatch_args_trie(&entries); - quote! { - #get_nodes_fn - #dispatch_fn - } + ( + quote! { + #get_nodes_fn + #dispatch_fn + }, + extra, + ) + }; + + #[cfg(all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")))] + let (dispatch_gen, dispatch_extra) = { + let get_nodes_fn = gen_get_nodes(&entries); + let (dispatch_fn, extra) = match dispatch_auto::select_strategy(&entries) { + dispatch_auto::DispatchStrategy::Linear => { + (dispatch_list_gen::gen_dispatch_args(&entries), quote! {}) + } + dispatch_auto::DispatchStrategy::Trie => { + dispatch_tree_gen::gen_dispatch_args_trie(&entries) + } + dispatch_auto::DispatchStrategy::Phf => { + (dispatch_phf_gen::gen_dispatch_args_phf(&entries), quote! {}) + } + }; + + ( + quote! { + #get_nodes_fn + #dispatch_fn + }, + extra, + ) }; #[cfg(feature = "comp")] @@ -436,6 +484,7 @@ pub(crate) fn program_final_gen_impl(_input: TokenStream) -> TokenStream { pub fn this() -> &'static ::mingling::Program<#name> { &::mingling::this::<#name>() } + #dispatch_extra } }; diff --git a/mingling_macros/src/lib.rs b/mingling_macros/src/lib.rs index 1aaedb1..1f4c44d 100644 --- a/mingling_macros/src/lib.rs +++ b/mingling_macros/src/lib.rs @@ -10,6 +10,19 @@ #![deny(clippy::nursery)] #![allow(clippy::redundant_pub_crate)] +// Dispatch strategies are mutually exclusive: `dispatch_linear`, `dispatch_tree`, +// and `dispatch_phf` each select the matching strategy generated by +// `gen_program!`. Enabling more than one would make the selection ambiguous; +// enabling none selects the automatic strategy (currently the linear list). +#[cfg(any( + all(feature = "dispatch_linear", feature = "dispatch_tree"), + all(feature = "dispatch_linear", feature = "dispatch_phf"), + all(feature = "dispatch_tree", feature = "dispatch_phf"), +))] +compile_error!( + "the `dispatch_linear`, `dispatch_tree`, and `dispatch_phf` features are mutually exclusive: enable at most one (none = auto)" +); + use proc_macro::TokenStream; use std::collections::BTreeSet; use std::sync::Mutex; @@ -20,6 +33,9 @@ mod derive; mod func; mod systems; +#[cfg(feature = "bench_support")] +mod bench_cell; + #[cfg(any(feature = "comp", feature = "pathf"))] mod build; @@ -1018,9 +1034,12 @@ pub fn register_metadata(input: TokenStream) -> TokenStream { /// This macro is called internally by `dispatcher!` and `dispatcher_clap!`. /// Each call stores the node name into the global `COMPILE_TIME_DISPATCHERS` /// registry and generates a static variable for the dispatcher instance. This -/// data is later consumed by `gen_program!` to generate command matching: a -/// character-level **trie** when the `dispatch_tree` feature is enabled, or a -/// linear longest-prefix list otherwise. +/// data is later consumed by `gen_program!` to generate command matching: +/// a **minimal perfect hash** (`dispatch_phf` feature), a character-level +/// **trie** (`dispatch_tree` feature), or a linear longest-prefix list +/// (`dispatch_linear` feature; with no dispatch feature enabled, "auto" mode +/// picks the best strategy from the command table). +/// The three dispatch features are mutually exclusive. /// /// The trie dispatch works by grouping commands by their character prefix, /// enabling O(n) lookup (where n is input length) instead of linear iteration @@ -1037,12 +1056,27 @@ pub fn register_metadata(input: TokenStream) -> TokenStream { /// # See also /// /// - `dispatcher!` — The primary way to declare dispatchers (calls this internally). -/// - `dispatch_tree_gen` / `dispatch_list_gen` modules — The matching-strategy generators. +/// - `dispatch_tree_gen` / `dispatch_list_gen` / `dispatch_phf_gen` modules — The matching-strategy generators. #[proc_macro] pub fn register_dispatcher(input: TokenStream) -> TokenStream { func::register_dispatcher::register_dispatcher(input) } +/// Generates a benchmark cell for the workspace-internal `mingling_bench` +/// harness (requires the `bench_support` feature). +/// +/// Input: `bench_cell!(strategy, module_name, "command" => DispType, ...)`. +/// `strategy` is one of `dispatch_linear`, `dispatch_tree`, `dispatch_phf`. +/// The expansion defines a +/// module containing per-entry dispatcher structs, the `crate::BenchDispatch` +/// impl (with the strategy-specific generated `dispatch_args`), the +/// command-name table, and a `measure` function that times hit/miss corpora. +#[cfg(feature = "bench_support")] +#[proc_macro] +pub fn bench_cell(input: TokenStream) -> TokenStream { + bench_cell::bench_cell_impl(input) +} + /// Declares a help rendering function for an entry type. /// /// The `#[help]` attribute converts a function into a help provider. Help diff --git a/mingling_macros/src/systems.rs b/mingling_macros/src/systems.rs index 3279b51..f9decf4 100644 --- a/mingling_macros/src/systems.rs +++ b/mingling_macros/src/systems.rs @@ -1,7 +1,89 @@ -#[cfg(not(feature = "dispatch_tree"))] +// Dispatch-strategy generators. Exactly one of {linear list, char trie, +// perfect-hash} is wired into `gen_program!` at a time (see +// `func/program_final_gen.rs`); with no dispatch feature enabled the "auto" +// strategy picks one from the table (see `dispatch_auto`). The +// workspace-internal `bench_support` feature compiles all three so the +// `bench_cell!` macro can generate the `dev/bench/dispatch` harness cells. + +#[cfg(any( + all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")), + feature = "bench_support" +))] pub(crate) mod dispatch_list_gen; -#[cfg(feature = "dispatch_tree")] +#[cfg(any(not(feature = "dispatch_phf"), feature = "bench_support"))] pub(crate) mod dispatch_tree_gen; +#[cfg(any( + all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")), + feature = "dispatch_phf", + feature = "bench_support" +))] +pub(crate) mod dispatch_phf_gen; + +#[cfg(any( + all(not(feature = "dispatch_phf"), not(feature = "dispatch_tree")), + feature = "bench_support" +))] +pub(crate) mod dispatch_auto; + pub(crate) mod res_injection; + +// TEMPORARY diagnostic probe — remove after bench matrix tuning. +#[cfg(test)] +mod size_probe { + use crate::systems::dispatch_list_gen::gen_dispatch_args; + use crate::systems::dispatch_phf_gen::gen_dispatch_args_phf; + use crate::systems::dispatch_tree_gen::gen_dispatch_args_trie; + + fn entries_nested(count: usize, depth: usize) -> Vec<(String, String, String)> { + let mut out = Vec::new(); + let groups = count.div_ceil(depth); + 'outer: for g in 0..groups { + let base = format!("n{g:03}"); + for d in 0..depth { + let mut name = base.clone(); + for k in 1..=d { + name.push_str(&format!(" w{k}")); + } + out.push((name, format!("D{}", out.len()), String::new())); + if out.len() == count { + break 'outer; + } + } + } + out + } + + fn entries_single(count: usize, len: usize) -> Vec<(String, String, String)> { + (0..count) + .map(|i| (format!("c{:0len$}", i), format!("D{i}"), String::new())) + .collect() + } + + #[test] + fn probe() { + for &(count, depth) in &[(128usize, 4usize), (1024, 4), (1024, 16)] { + let e = entries_nested(count, depth); + let t = gen_dispatch_args_trie(&e).0.to_string(); + let l = gen_dispatch_args(&e).to_string(); + let p = gen_dispatch_args_phf(&e).to_string(); + eprintln!( + "nested count={count} depth={depth}: trie={}B lin={}B phf={}B", + t.len(), + l.len(), + p.len() + ); + } + let e = entries_single(1024, 32); + let t = gen_dispatch_args_trie(&e).0.to_string(); + let l = gen_dispatch_args(&e).to_string(); + let p = gen_dispatch_args_phf(&e).to_string(); + eprintln!( + "single count=1024 len=32: trie={}B lin={}B phf={}B", + t.len(), + l.len(), + p.len() + ); + } +} diff --git a/mingling_macros/src/systems/dispatch_auto.rs b/mingling_macros/src/systems/dispatch_auto.rs new file mode 100644 index 0000000..54784e2 --- /dev/null +++ b/mingling_macros/src/systems/dispatch_auto.rs @@ -0,0 +1,110 @@ +// Doc Not Optimize +//! Auto dispatch-strategy selection (no dispatch feature enabled). +//! +//! Picks the matching strategy at macro-expansion time from the normalized +//! command table. The rules are calibrated against the `dev/bench/dispatch` +//! matrix (len 4/8/16/32 × count 128/256 × single/multi/nested4/nested10), +//! where "optimal" is the per-cell minimum of hit×miss geomean: +//! +//! - deep nested chains at modest sizes (`max_words ≥ 8`, `n ≤ 128`) → +//! **linear list**: a few short memcmps beat the trie's per-level `nth(0)` +//! walk plus the fallback call on non-leaf hits; +//! - single-word tables with long names → **perfect hash**: one hash beats +//! the trie's char walk once names grow past ~16 chars; +//! - small tables (`n ≤ 64`) → linear vs trie by a cost model (linear wins +//! on short names, loses once `count × length` grows); +//! - everything else → **char trie** (O(depth) hit cost independent of table +//! size, best miss path, linear code size after the fallback-chain fix). + +/// Linear per-check memcmp cost: `LIN_A + LIN_B × len` ns, plus a miss term +/// that shrinks as names grow (long names are rejected by the length +/// precheck on the miss path). +const LIN_A: f64 = 0.5; +const LIN_B: f64 = 0.04; +const LIN_MISS_A: f64 = 0.18; +const LIN_MISS_B: f64 = 0.005; + +/// Trie per-command overhead: `TRIE_FIXED + TRIE_PER_CHAR × max_len` plus an +/// extra term when exact endpoints exist at multiple depths (nested chains +/// force a fallback call on non-leaf hits). +const TRIE_FIXED: f64 = 25.0; +const TRIE_PER_CHAR: f64 = 1.5; +const TRIE_NESTED: f64 = 25.0; +const TRIE_MISS: f64 = 3.0; + +#[derive(Clone, Copy, PartialEq, Eq, Debug)] +pub(crate) enum DispatchStrategy { + Linear, + Trie, + Phf, +} + +/// Pick the dispatch strategy for a normalized entry table. +/// +/// Casting `usize` counts to `f64` is intentional: these are cost-model +/// heuristics, not exact numeric computations. Any rounding error is tiny +/// relative to the measured performance margins between strategies, so +/// precision loss here is harmless. +#[allow(clippy::cast_precision_loss)] +pub(crate) fn select_strategy(entries: &[(String, String, String)]) -> DispatchStrategy { + if entries.is_empty() { + return DispatchStrategy::Linear; + } + + let mut names: Vec<String> = Vec::with_capacity(entries.len()); + for (name, _, _) in entries { + names.push(name.replace('.', " ")); + } + + let n = names.len() as f64; + let avg_len = names.iter().map(|s| s.chars().count()).sum::<usize>() as f64 / n; + let max_len = names.iter().map(|s| s.chars().count()).max().unwrap_or(0) as f64; + let max_words = names + .iter() + .map(|s| s.split_whitespace().count()) + .max() + .unwrap_or(0); + + // Nested prefix chains (a command that is a strict prefix of another) + // make the trie fall back on non-leaf hits. + let mut sorted: Vec<&String> = names.iter().collect(); + sorted.sort(); + let nested = sorted.windows(2).any(|w| w[1].starts_with(w[0].as_str())); + + // Nested tables at modest sizes: decide linear vs trie by the cost + // model. The linear list wins on short names (its few memcmps beat the + // trie's char walk plus fallback calls) and loses once names grow. + if nested && n <= 128.0 { + let miss_linear = n * LIN_MISS_B.mul_add(-avg_len, LIN_MISS_A).max(0.0); + let cost_linear = (n / 2.0).mul_add(LIN_B.mul_add(avg_len, LIN_A), miss_linear); + let cost_trie = TRIE_PER_CHAR.mul_add(max_len, TRIE_FIXED) + TRIE_NESTED + TRIE_MISS; + return if cost_linear < cost_trie { + DispatchStrategy::Linear + } else { + DispatchStrategy::Trie + }; + } + + // Single-word tables with long names: one hash beats the char walk once + // names grow past ~16 chars (measured on single-word len16/32). + if max_words == 1 && (avg_len >= 24.0 || (n <= 128.0 && avg_len >= 16.0)) { + return DispatchStrategy::Phf; + } + + // Small tables: linear vs trie by the cost model. The linear list wins + // on short names but collapses as `count × length` grows. + if n <= 64.0 { + let miss_linear = n * LIN_MISS_B.mul_add(-avg_len, LIN_MISS_A).max(0.0); + let cost_linear = (n / 2.0).mul_add(LIN_B.mul_add(avg_len, LIN_A), miss_linear); + let cost_trie = TRIE_PER_CHAR.mul_add(max_len, TRIE_FIXED) + + if nested { TRIE_NESTED } else { 0.0 } + + TRIE_MISS; + return if cost_linear < cost_trie { + DispatchStrategy::Linear + } else { + DispatchStrategy::Trie + }; + } + + DispatchStrategy::Trie +} 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())) + } + } +} diff --git a/mingling_macros/src/systems/dispatch_tree_gen.rs b/mingling_macros/src/systems/dispatch_tree_gen.rs index 2b264f7..08fc78b 100644 --- a/mingling_macros/src/systems/dispatch_tree_gen.rs +++ b/mingling_macros/src/systems/dispatch_tree_gen.rs @@ -1,57 +1,122 @@ // Doc Not Optimize +//! Char-level trie dispatch generator (`dispatch_tree` feature). +//! +//! Builds a hardcoded match tree: at each depth, group nodes by character. +//! Single-node groups use `starts_with`; multi-node groups recurse with +//! `nth()` match. +//! +//! The "longest registered prefix" fallback (try the exact endpoint at this +//! node, then its parent, …) is **not** inlined into every arm. Instead each +//! trie node gets an id and every arm *calls* a single generic +//! `__trie_fallback<G>` method that runs that node's exact-endpoint checks +//! and tail-recurses to the parent, returning `None` when nothing in the +//! chain matches (the caller then produces the no-match result). This keeps +//! the generated code linear in the table size: inlining the whole fallback +//! chain per arm grew quadratically with nesting depth (a 1024×16 nested +//! table emitted ~13 MB of tokens). +//! +//! The generator returns two token streams: the `dispatch_args` method (for +//! the `ProgramCollect` trait impl) and the `__trie_fallback` method (for an +//! inherent impl of the program type). The fallback uses the concrete `Self` +//! (the program type implements `ProgramCollect` with `Enum = Self`, and the +//! bench harness's `BenchDispatch` mirrors that), so it lives outside the +//! trait. + use std::collections::BTreeMap; use proc_macro2::TokenStream; use quote::quote; -/// Generate the `dispatch_args()` function body for a `ProgramCollect` impl. -/// -/// Builds a hardcoded match tree: at each depth, group nodes by character. -/// Single-node groups use `starts_with`; multi-node groups recurse with `nth()` match. -pub(crate) fn gen_dispatch_args_trie(entries: &[(String, String, String)]) -> TokenStream { - let nodes: Vec<(String, String)> = entries - .iter() - .map(|(name, disp, _)| (name.replace('.', " "), disp.clone())) - .collect(); +/// A trie node recorded for the shared longest-prefix fallback: its +/// exact-endpoint checks and its parent's node id. +struct FallbackNode { + node_id: usize, + parent: Option<usize>, + exact_checks: Vec<TokenStream>, +} - let dispatch_body = build_dispatch_body( - &nodes, - 0, - "e! { - return Ok(Self::build_entry_fallback(raw.to_vec())); - }, - ); +/// Emit a `starts_with` dispatch arm. +/// +/// `group_ty` is the type the dispatchers are generic over: `Self::Enum` +/// inside `dispatch_args` (trait impl) or `Self` inside the fallback +/// (inherent impl). `wrap_some` selects `return Some(match __cp …)` +/// (fallback) vs `return match __cp …` (dispatch). +fn make_starts_with_arm( + name: &str, + disp_type: &str, + group_ty: &TokenStream, + wrap_some: bool, +) -> TokenStream { + let name_space = format!("{name} "); + let name_lit = syn::LitStr::new(&name_space, proc_macro2::Span::call_site()); + let disp_ident = proc_macro2::Ident::new(disp_type, proc_macro2::Span::call_site()); + let prefix_word_count = name.split_whitespace().count(); + let ret = if wrap_some { + quote! { + return Some(match __cp { + ::mingling::ChainProcess::Ok(any_output) => Ok(any_output.0), + ::mingling::ChainProcess::Err(chain_process_error) => { + Err(chain_process_error.into()) + } + }); + } + } else { + quote! { + return match __cp { + ::mingling::ChainProcess::Ok(any_output) => Ok(any_output.0), + ::mingling::ChainProcess::Err(chain_process_error) => { + Err(chain_process_error.into()) + } + }; + } + }; + quote! { + if raw_str.starts_with(#name_lit) { + let prefix_len = #prefix_word_count; + let trimmed_args: Vec<String> = raw.iter().skip(prefix_len).cloned().collect(); + let __cp = <#disp_ident as ::mingling::Dispatcher<#group_ty>>::begin( + &#disp_ident::default(), + trimmed_args, + ); + #ret + } + } +} +/// Call site of the shared fallback from inside `dispatch_args`: if the +/// fallback chain resolved an exact endpoint, return it; otherwise fall +/// through (the terminal no-match result follows the root match). +fn fallback_call(node_id: usize) -> TokenStream { + let id_lit = proc_macro2::Literal::usize_unsuffixed(node_id); quote! { - fn dispatch_args( - raw: &[String], - ) -> Result<::mingling::AnyOutput<Self::Enum>, ::mingling::error::ProgramInternalExecuteError> - { - let raw_string = format!("{} ", raw.join(" ")); - let raw_str = raw_string.as_str(); - let mut raw_chars = raw_str.chars(); - #dispatch_body + if let Some(__r) = Self::__trie_fallback(raw, raw_str, #id_lit) { + return __r; } } } /// Recursively build the trie match body. /// -/// `nodes`: slice of (`display_name`, `disp_type`) for commands that share the same prefix so far. -/// `depth`: The character index currently being matched. -/// `no_match`: fallback code to run when no node in this subtree matches the input. +/// `nodes`: slice of (`display_name`, `disp_type`) for commands that share the +/// same prefix so far. `depth`: the character index currently being matched. +/// `node_id` / `parent_id`: trie node identity used by the shared +/// longest-prefix fallback; `fallbacks` collects one entry per interior node +/// for the `__trie_fallback` method emitted by the caller. /// /// Matching follows the same "longest registered prefix" rule used by the -/// dynamic dispatcher: a child (longer) path is preferred over an exact +/// other generators: a child (longer) path is preferred over an exact /// endpoint at the same depth. Only when every descendant fails to match is -/// the exact endpoint here dispatched. +/// the exact endpoint here dispatched (via the fallback). fn build_dispatch_body( nodes: &[(String, String)], depth: usize, - no_match: &TokenStream, + node_id: usize, + parent_id: Option<usize>, + next_id: &mut usize, + fallbacks: &mut Vec<FallbackNode>, ) -> TokenStream { if nodes.is_empty() { - return no_match.clone(); + return parent_id.map_or_else(|| quote! {}, fallback_call); } let mut groups: BTreeMap<char, Vec<(String, String)>> = BTreeMap::new(); @@ -68,43 +133,21 @@ fn build_dispatch_body( } } - let make_starts_with_arm = |name: &str, disp_type: &str| -> TokenStream { - let name_space = format!("{name} "); - let name_lit = syn::LitStr::new(&name_space, proc_macro2::Span::call_site()); - let disp_ident = proc_macro2::Ident::new(disp_type, proc_macro2::Span::call_site()); - let prefix_word_count = name.split_whitespace().count(); - quote! { - if raw_str.starts_with(#name_lit) { - let prefix_len = #prefix_word_count; - let trimmed_args: Vec<String> = raw.iter().skip(prefix_len).cloned().collect(); - let __cp = <#disp_ident as ::mingling::Dispatcher<Self::Enum>>::begin( - &#disp_ident::default(), - trimmed_args, - ); - return match __cp { - ::mingling::ChainProcess::Ok(any_output) => Ok(any_output.0), - ::mingling::ChainProcess::Err(chain_process_error) => { - Err(chain_process_error.into()) - } - }; - } - } - }; - - // Fallback code for when neither a child path nor the exact endpoint(s) - // here match: run the exact endpoint checks for this node first (they must - // win over nothing at all), then pass control back up to the caller. - let exact_checks: Vec<TokenStream> = exact_nodes - .iter() - .map(|(name, disp_type)| make_starts_with_arm(name, disp_type)) - .collect(); - - let level_no_match = { - let mut body = exact_checks.clone(); - body.push(no_match.clone()); - quote! { #(#body)* } - }; + // Register this node in the fallback table (interior nodes only — leaf + // exact checks run inline in the walk). The fallback's exact checks use + // the concrete `Self` (see the module docs) and wrap results in `Some`. + if !groups.is_empty() { + fallbacks.push(FallbackNode { + node_id, + parent: parent_id, + exact_checks: exact_nodes + .iter() + .map(|(name, disp_type)| make_starts_with_arm(name, disp_type, "e!(Self), true)) + .collect(), + }); + } + let self_enum = quote!(Self::Enum); let mut arms = Vec::new(); for (&ch, sub_nodes) in &groups { @@ -112,17 +155,27 @@ fn build_dispatch_body( if sub_nodes.len() == 1 { let (name, disp_type) = &sub_nodes[0]; - let arm = make_starts_with_arm(name, disp_type); - // Try the child first; if it does not match, fall through to the - // exact endpoint(s) here so the longer path wins when present. + let arm = make_starts_with_arm(name, disp_type, &self_enum, false); + let fb = fallback_call(node_id); + // Try the child first; if it does not match, defer to this node's + // longest-prefix fallback so the longer path wins when present. arms.push(quote! { Some(#ch_char) => { #arm - #level_no_match + #fb } }); } else { - let sub_body = build_dispatch_body(sub_nodes, depth + 1, &level_no_match); + let child_id = *next_id; + *next_id += 1; + let sub_body = build_dispatch_body( + sub_nodes, + depth + 1, + child_id, + Some(node_id), + next_id, + fallbacks, + ); arms.push(quote! { Some(#ch_char) => { #sub_body @@ -132,18 +185,101 @@ fn build_dispatch_body( } if groups.is_empty() { - // No children exist for this node; only the exact endpoint(s) apply. - let mut body = exact_checks; - body.push(no_match.clone()); + // No children exist for this node; only the exact endpoint(s) apply, + // then defer to the parent's fallback (longest-prefix semantics). + let mut body = exact_nodes + .iter() + .map(|(name, disp_type)| make_starts_with_arm(name, disp_type, &self_enum, false)) + .collect::<Vec<TokenStream>>(); + if let Some(p) = parent_id { + body.push(fallback_call(p)); + } quote! { #(#body)* } } else { + let fb = fallback_call(node_id); quote! { match raw_chars.nth(0) { #(#arms)* _ => { - #level_no_match + #fb } } } } } + +/// Generate the `dispatch_args()` method (for the `ProgramCollect` trait +/// impl) plus the `__trie_fallback` method (for an inherent impl of the +/// program type). Returns `(dispatch_method, extra_inherent_items)`. +pub(crate) fn gen_dispatch_args_trie( + entries: &[(String, String, String)], +) -> (TokenStream, TokenStream) { + let nodes: Vec<(String, String)> = entries + .iter() + .map(|(name, disp, _)| (name.replace('.', " "), disp.clone())) + .collect(); + + let mut next_id = 1usize; + let mut fallbacks: Vec<FallbackNode> = Vec::new(); + let dispatch_body = build_dispatch_body(&nodes, 0, 0, None, &mut next_id, &mut fallbacks); + + let fallback_arms: Vec<TokenStream> = fallbacks + .iter() + .map(|fb| { + let id_lit = proc_macro2::Literal::usize_unsuffixed(fb.node_id); + let exact = &fb.exact_checks; + let tail = fb.parent.map_or_else( + || quote! { None }, + |p| { + let p_lit = proc_macro2::Literal::usize_unsuffixed(p); + quote! { Self::__trie_fallback(raw, raw_str, #p_lit) } + }, + ); + quote! { + #id_lit => { + #(#exact)* + #tail + } + } + }) + .collect(); + + let dispatch_fn = quote! { + fn dispatch_args( + raw: &[String], + ) -> Result<::mingling::AnyOutput<Self::Enum>, ::mingling::error::ProgramInternalExecuteError> + { + let raw_string = format!("{} ", raw.join(" ")); + let raw_str = raw_string.as_str(); + let mut raw_chars = raw_str.chars(); + #dispatch_body + Ok(Self::build_entry_fallback(raw.to_vec())) + } + }; + + let fallback_fn = quote! { + /// Longest-prefix fallback: run the exact-endpoint checks of trie + /// node `__node`, then defer to its parent (tail-recursively), or + /// return `None` at the root when nothing matched. Shared by all + /// arms instead of being inlined into each one, keeping the generated + /// code linear in the table size. Lives in an inherent impl, where + /// `Self` is the program type (`ProgramCollect`'s `Enum = Self`). + #[allow(dead_code)] + #[inline(never)] + fn __trie_fallback( + raw: &[String], + raw_str: &str, + __node: usize, + ) -> Option<Result< + ::mingling::AnyOutput<Self>, + ::mingling::error::ProgramInternalExecuteError, + >> { + match __node { + #(#fallback_arms)* + _ => None, + } + } + }; + + (dispatch_fn, fallback_fn) +} |