osp_cli/completion/

suggest.rs

use crate::completion::context::{ProviderSelection, TreeResolver};
use crate::completion::model::{
    CommandLine, CompletionAnalysis, CompletionNode, CompletionTree, Suggestion, SuggestionEntry,
    SuggestionOutput, ValueType,
};
use fuzzy_matcher::FuzzyMatcher;
use fuzzy_matcher::skim::SkimMatcherV2;
use std::collections::BTreeSet;
use std::sync::OnceLock;

const MATCH_SCORE_EXACT: u32 = 0;
const MATCH_SCORE_EMPTY_STUB: u32 = 1_000;
const MATCH_SCORE_PREFIX_BASE: u32 = 100;
const MATCH_SCORE_BOUNDARY_PREFIX_BASE: u32 = 200;
const MATCH_SCORE_FUZZY_BASE: u32 = 10_000;
const MATCH_SCORE_FUZZY_NORMALIZED_MAX: u32 = 100_000;
// Lower scores win:
// exact < prefix < boundary-prefix < fuzzy fallback.

struct PositionalRequest<'a> {
    context_node: &'a CompletionNode,
    flag_scope_node: &'a CompletionNode,
    arg_index: usize,
    stub: &'a str,
    cmd: &'a CommandLine,
    show_subcommands: bool,
    show_flag_names: bool,
}

enum SuggestionMode<'a> {
    Pipe,
    FlagNames {
        flag_scope_node: &'a CompletionNode,
    },
    FlagValues {
        flag_scope_node: &'a CompletionNode,
        flag: String,
    },
    Positionals {
        context_node: &'a CompletionNode,
        flag_scope_node: &'a CompletionNode,
        arg_index: usize,
        show_subcommands: bool,
        show_flag_names: bool,
    },
}

#[derive(Debug, Clone)]
pub struct SuggestionEngine {
    tree: CompletionTree,
}

impl SuggestionEngine {
    pub fn new(tree: CompletionTree) -> Self {
        Self { tree }
    }

    pub fn generate(&self, analysis: &CompletionAnalysis) -> Vec<SuggestionOutput> {
        let mode = self.suggestion_mode(analysis);
        self.emit_suggestions(mode, analysis)
    }

    fn suggestion_mode<'a>(&'a self, analysis: &'a CompletionAnalysis) -> SuggestionMode<'a> {
        let cmd = &analysis.parsed.cursor_cmd;
        let stub = analysis.cursor.token_stub.as_str();

        if cmd.has_pipe() {
            return SuggestionMode::Pipe;
        }

        let nodes = TreeResolver::new(&self.tree).resolved_nodes(&analysis.context);
        if stub.starts_with('-') {
            return SuggestionMode::FlagNames {
                flag_scope_node: nodes.flag_scope_node,
            };
        }

        let (needs_flag_value, last_flag) =
            self.last_flag_needs_value(nodes.flag_scope_node, cmd, stub);
        if needs_flag_value && let Some(flag) = last_flag {
            return SuggestionMode::FlagValues {
                flag_scope_node: nodes.flag_scope_node,
                flag,
            };
        }

        SuggestionMode::Positionals {
            context_node: nodes.context_node,
            flag_scope_node: nodes.flag_scope_node,
            arg_index: self.arg_index(cmd, stub, analysis.context.matched_path.len()),
            show_subcommands: analysis.context.subcommand_context,
            show_flag_names: stub.is_empty() && !analysis.context.subcommand_context,
        }
    }

    fn emit_suggestions(
        &self,
        mode: SuggestionMode<'_>,
        analysis: &CompletionAnalysis,
    ) -> Vec<SuggestionOutput> {
        let cmd = &analysis.parsed.cursor_cmd;
        let stub = analysis.cursor.token_stub.as_str();

        let mut out = match mode {
            SuggestionMode::Pipe => self.pipe_suggestions(stub),
            SuggestionMode::FlagNames { flag_scope_node } => self
                .flag_name_suggestions(flag_scope_node, stub, cmd)
                .into_iter()
                .map(SuggestionOutput::Item)
                .collect(),
            SuggestionMode::FlagValues {
                flag_scope_node,
                flag,
            } => self.flag_value_suggestions(flag_scope_node, &flag, stub, cmd),
            SuggestionMode::Positionals {
                context_node,
                flag_scope_node,
                arg_index,
                show_subcommands,
                show_flag_names,
            } => {
                let request = PositionalRequest {
                    context_node,
                    flag_scope_node,
                    arg_index,
                    stub,
                    cmd,
                    show_subcommands,
                    show_flag_names,
                };
                let mut out = self.positional_suggestions(request);
                sort_suggestion_outputs(&mut out);
                return out;
            }
        };

        sort_suggestion_outputs(&mut out);
        out
    }

    fn positional_suggestions(&self, request: PositionalRequest<'_>) -> Vec<SuggestionOutput> {
        let mut out = Vec::new();

        if request.show_subcommands {
            out.extend(
                self.subcommand_suggestions(request.context_node, request.stub)
                    .into_iter()
                    .map(SuggestionOutput::Item),
            );
        } else {
            out.extend(self.arg_value_suggestions(
                request.context_node,
                request.arg_index,
                request.stub,
            ));
        }

        if request.show_flag_names {
            out.extend(
                self.flag_name_suggestions(request.flag_scope_node, request.stub, request.cmd)
                    .into_iter()
                    .filter(|suggestion| !request.cmd.has_flag(&suggestion.text))
                    .map(SuggestionOutput::Item),
            );
        }

        out
    }

    fn pipe_suggestions(&self, stub: &str) -> Vec<SuggestionOutput> {
        self.tree
            .pipe_verbs
            .iter()
            .filter_map(|(verb, tooltip)| {
                let score = self.match_score(stub, verb)?;
                Some(SuggestionOutput::Item(Suggestion {
                    text: verb.clone(),
                    meta: Some(tooltip.clone()),
                    display: None,
                    is_exact: score == 0,
                    sort: None,
                    match_score: score,
                }))
            })
            .collect()
    }

    fn flag_name_suggestions(
        &self,
        node: &CompletionNode,
        stub: &str,
        cmd: &CommandLine,
    ) -> Vec<Suggestion> {
        let allowlist = self.resolved_flag_allowlist(node, cmd);
        let required = self.required_flags(node, cmd);

        node.flags
            .iter()
            .filter_map(|(flag, meta)| {
                let score = self.match_score(stub, flag)?;
                Some((flag, meta, score))
            })
            .filter(|(flag, _, _)| {
                allowlist
                    .as_ref()
                    .is_none_or(|allowed| allowed.contains(flag.as_str()))
            })
            .filter(|(flag, _, _)| !cmd.has_flag(flag) || stub == *flag)
            .map(|(flag, meta, score)| Suggestion {
                text: flag.clone(),
                meta: meta.tooltip.clone(),
                display: required.contains(flag.as_str()).then(|| format!("{flag}*")),
                is_exact: score == 0,
                sort: None,
                match_score: score,
            })
            .collect()
    }

    fn flag_value_suggestions(
        &self,
        node: &CompletionNode,
        flag: &str,
        stub: &str,
        cmd: &CommandLine,
    ) -> Vec<SuggestionOutput> {
        let Some(flag_node) = node.flags.get(flag) else {
            return Vec::new();
        };

        if flag_node.flag_only {
            return Vec::new();
        }

        if flag_node.value_type == Some(ValueType::Path) {
            return vec![SuggestionOutput::PathSentinel];
        }

        if let Some(output) =
            self.provider_specific_flag_value_suggestions(flag_node, flag, stub, cmd)
        {
            return output;
        }

        self.entry_suggestions(&flag_node.suggestions, stub)
    }

    fn arg_value_suggestions(
        &self,
        node: &CompletionNode,
        index: usize,
        stub: &str,
    ) -> Vec<SuggestionOutput> {
        let Some(arg) = node.args.get(index) else {
            return Vec::new();
        };

        if arg.value_type == Some(ValueType::Path) {
            return vec![SuggestionOutput::PathSentinel];
        }

        self.entry_suggestions(&arg.suggestions, stub)
    }

    fn subcommand_suggestions(&self, node: &CompletionNode, stub: &str) -> Vec<Suggestion> {
        node.children
            .iter()
            .filter_map(|(name, child)| {
                let score = self.match_score(stub, name)?;
                Some(Suggestion {
                    text: name.clone(),
                    meta: child_completion_meta(child),
                    display: None,
                    is_exact: score == 0,
                    sort: child.sort.clone(),
                    match_score: score,
                })
            })
            .collect()
    }

    fn last_flag_needs_value(
        &self,
        node: &CompletionNode,
        cmd: &CommandLine,
        stub: &str,
    ) -> (bool, Option<String>) {
        let Some(last_occurrence) = cmd.last_flag_occurrence() else {
            return (false, None);
        };
        let last_flag = &last_occurrence.name;

        let Some(flag_node) = node.flags.get(last_flag) else {
            return (false, None);
        };

        if flag_node.flag_only {
            return (false, None);
        }

        if last_occurrence.values.is_empty() {
            return (true, Some(last_flag.clone()));
        }

        if !stub.is_empty()
            && last_occurrence.values.last().is_some_and(|value| {
                value
                    .to_ascii_lowercase()
                    .starts_with(&stub.to_ascii_lowercase())
            })
        {
            return (true, Some(last_flag.clone()));
        }

        (flag_node.multi, Some(last_flag.clone()))
    }

    fn arg_index(&self, cmd: &CommandLine, stub: &str, matched_head_len: usize) -> usize {
        cmd.head()
            .iter()
            .skip(matched_head_len)
            .chain(cmd.positional_args())
            .filter(|token| token.as_str() != stub)
            .count()
    }

    fn provider_specific_flag_value_suggestions(
        &self,
        flag_node: &crate::completion::model::FlagNode,
        flag: &str,
        stub: &str,
        cmd: &CommandLine,
    ) -> Option<Vec<SuggestionOutput>> {
        // Provider completion has two special cases:
        // - selecting `--provider` may be constrained by the current `--os`
        // - many flags expose provider-specific value sets once a provider is chosen
        //
        // `osp-cli` marks these selector flags as context-only in
        // `repl/completion.rs`; the suggestion engine still needs a small
        // amount of flag-name-specific logic until that relationship is fully
        // expressed in completion metadata.
        let provider = ProviderSelection::from_command(cmd);

        if flag == "--provider" {
            let os_token = provider.normalized_os();
            if let Some(os_token) = os_token {
                let filtered = flag_node
                    .suggestions
                    .iter()
                    .filter(|entry| {
                        flag_node
                            .os_provider_map
                            .get(os_token)
                            .is_none_or(|providers| providers.iter().any(|p| p == &entry.value))
                    })
                    .cloned()
                    .collect::<Vec<_>>();
                if !filtered.is_empty() {
                    return Some(self.entry_suggestions(&filtered, stub));
                }
            }
        }

        let provider_values = flag_node.suggestions_by_provider.get(provider.name()?)?;
        Some(self.entry_suggestions(provider_values, stub))
    }

    fn entry_suggestions(&self, entries: &[SuggestionEntry], stub: &str) -> Vec<SuggestionOutput> {
        entries
            .iter()
            .filter_map(|entry| {
                let score = self.match_score(stub, &entry.value)?;
                Some(SuggestionOutput::Item(entry_to_suggestion(entry, score)))
            })
            .collect()
    }

    fn match_score(&self, stub: &str, candidate: &str) -> Option<u32> {
        // Lower scores are better:
        // - exact match wins with 0
        // - 100-range keeps ordinary prefix matches together
        // - 200-range keeps word-boundary prefixes behind direct prefixes
        // - 10_000+ is fuzzy fallback, where higher fuzzy scores reduce the
        //   penalty and therefore sort earlier
        if stub.is_empty() {
            return Some(MATCH_SCORE_EMPTY_STUB);
        }

        let stub_lc = stub.to_ascii_lowercase();
        let candidate_lc = candidate.to_ascii_lowercase();

        if stub_lc == candidate_lc {
            return Some(MATCH_SCORE_EXACT);
        }
        if candidate_lc.starts_with(&stub_lc) {
            return Some(MATCH_SCORE_PREFIX_BASE + (candidate_lc.len() - stub_lc.len()) as u32);
        }

        if let Some(boundary) = boundary_prefix_index(&candidate_lc, &stub_lc) {
            return Some(MATCH_SCORE_BOUNDARY_PREFIX_BASE + boundary as u32);
        }

        let fuzzy = fuzzy_matcher().fuzzy_match(&candidate_lc, &stub_lc)?;
        let normalized = fuzzy.max(0) as u32;
        let penalty = MATCH_SCORE_FUZZY_NORMALIZED_MAX.saturating_sub(normalized);
        Some(MATCH_SCORE_FUZZY_BASE + penalty)
    }

    fn resolved_flag_allowlist(
        &self,
        node: &CompletionNode,
        cmd: &CommandLine,
    ) -> Option<BTreeSet<String>> {
        let hints = node.flag_hints.as_ref()?;
        let mut allowed = hints.common.iter().cloned().collect::<BTreeSet<_>>();

        if let Some(provider) = ProviderSelection::from_command(cmd).name() {
            if let Some(provider_specific) = hints.by_provider.get(provider) {
                allowed.extend(provider_specific.iter().cloned());
            }
            // Once provider is selected, hide selector flags.
            allowed.remove("--provider");
            allowed.remove("--nrec");
            allowed.remove("--vmware");
        }

        if cmd.has_flag("--linux") {
            allowed.remove("--windows");
        }
        if cmd.has_flag("--windows") {
            allowed.remove("--linux");
        }

        Some(allowed)
    }

    fn required_flags(&self, node: &CompletionNode, cmd: &CommandLine) -> BTreeSet<String> {
        let mut required = BTreeSet::new();
        let Some(hints) = node.flag_hints.as_ref() else {
            return required;
        };

        required.extend(hints.required_common.iter().cloned());
        if let Some(provider) = ProviderSelection::from_command(cmd).name()
            && let Some(provider_required) = hints.required_by_provider.get(provider)
        {
            required.extend(provider_required.iter().cloned());
        }
        required
    }
}

fn child_completion_meta(child: &CompletionNode) -> Option<String> {
    let summary = child_subcommand_summary(child);
    match (child.tooltip.as_deref(), summary) {
        (Some(tooltip), Some(summary)) => Some(format!("{tooltip} ({summary})")),
        (Some(tooltip), None) => Some(tooltip.to_string()),
        (None, Some(summary)) => Some(summary),
        (None, None) => None,
    }
}

fn child_subcommand_summary(child: &CompletionNode) -> Option<String> {
    if child.children.is_empty() {
        return None;
    }

    let preview = child.children.keys().take(3).cloned().collect::<Vec<_>>();
    if preview.is_empty() {
        return None;
    }

    let mut summary = format!("subcommands: {}", preview.join(", "));
    if child.children.len() > preview.len() {
        summary.push_str(", ...");
    }
    Some(summary)
}

fn sort_suggestion_outputs(outputs: &mut Vec<SuggestionOutput>) {
    let mut items: Vec<Suggestion> = outputs
        .iter()
        .filter_map(|entry| match entry {
            SuggestionOutput::Item(item) => Some(item.clone()),
            SuggestionOutput::PathSentinel => None,
        })
        .collect();
    let path_sentinel_count = outputs
        .iter()
        .filter(|entry| matches!(entry, SuggestionOutput::PathSentinel))
        .count();

    items.sort_by(compare_suggestions);

    // Path sentinels are not ranked suggestions; they are control markers that
    // tell the caller to ask the shell for filesystem completion after all
    // normal ranked suggestions have been shown.
    outputs.clear();
    outputs.extend(items.into_iter().map(SuggestionOutput::Item));
    outputs.extend(std::iter::repeat_n(
        SuggestionOutput::PathSentinel,
        path_sentinel_count,
    ));
}

fn compare_suggestions(left: &Suggestion, right: &Suggestion) -> std::cmp::Ordering {
    (not_exact(left), left.match_score)
        .cmp(&(not_exact(right), right.match_score))
        .then_with(|| compare_sort_value(left.sort.as_deref(), right.sort.as_deref()))
        .then_with(|| {
            left.text
                .to_ascii_lowercase()
                .cmp(&right.text.to_ascii_lowercase())
        })
}

fn compare_sort_value(left: Option<&str>, right: Option<&str>) -> std::cmp::Ordering {
    match (left, right) {
        (Some(left), Some(right)) => {
            match (
                left.trim().parse::<f64>().ok(),
                right.trim().parse::<f64>().ok(),
            ) {
                (Some(left_num), Some(right_num)) => left_num
                    .partial_cmp(&right_num)
                    .unwrap_or(std::cmp::Ordering::Equal),
                _ => left.to_ascii_lowercase().cmp(&right.to_ascii_lowercase()),
            }
        }
        (Some(_), None) => std::cmp::Ordering::Less,
        (None, Some(_)) => std::cmp::Ordering::Greater,
        (None, None) => std::cmp::Ordering::Equal,
    }
}

fn not_exact(suggestion: &Suggestion) -> bool {
    !suggestion.is_exact
}

fn entry_to_suggestion(entry: &SuggestionEntry, match_score: u32) -> Suggestion {
    Suggestion {
        text: entry.value.clone(),
        meta: entry.meta.clone(),
        display: entry.display.clone(),
        is_exact: match_score == 0,
        sort: entry.sort.clone(),
        match_score,
    }
}

fn boundary_prefix_index(candidate: &str, stub: &str) -> Option<usize> {
    candidate
        .match_indices(stub)
        .find(|(idx, _)| {
            *idx == 0
                || candidate
                    .as_bytes()
                    .get(idx.saturating_sub(1))
                    .is_some_and(|byte| matches!(byte, b'-' | b'_' | b'.' | b':' | b'/'))
        })
        .map(|(idx, _)| idx)
}

fn fuzzy_matcher() -> &'static SkimMatcherV2 {
    static MATCHER: OnceLock<SkimMatcherV2> = OnceLock::new();
    MATCHER.get_or_init(SkimMatcherV2::default)
}

#[cfg(test)]
mod tests {
    use std::collections::BTreeMap;

    use crate::completion::model::{
        ArgNode, CommandLine, CompletionNode, CompletionTree, CursorState, FlagHints, FlagNode,
        FlagOccurrence, SuggestionEntry, SuggestionOutput, ValueType,
    };

    use crate::completion::CompletionEngine;

    fn tree() -> CompletionTree {
        let mut provision = CompletionNode::default();
        provision.flags.insert(
            "--provider".to_string(),
            FlagNode {
                suggestions: vec![
                    SuggestionEntry::from("nrec"),
                    SuggestionEntry::from("vmware"),
                ],
                os_provider_map: BTreeMap::from([
                    ("alma".to_string(), vec!["nrec".to_string()]),
                    ("rhel".to_string(), vec!["vmware".to_string()]),
                ]),
                ..FlagNode::default()
            },
        );
        provision.flags.insert(
            "--os".to_string(),
            FlagNode {
                suggestions: vec![SuggestionEntry::from("alma"), SuggestionEntry::from("rhel")],
                ..FlagNode::default()
            },
        );

        let mut orch = CompletionNode::default();
        orch.children.insert("provision".to_string(), provision);

        CompletionTree {
            root: CompletionNode::default().with_child("orch", orch),
            pipe_verbs: BTreeMap::from([("F".to_string(), "Filter".to_string())]),
        }
    }

    fn values(output: Vec<SuggestionOutput>) -> Vec<String> {
        output
            .into_iter()
            .filter_map(|entry| match entry {
                SuggestionOutput::Item(item) => Some(item.text),
                SuggestionOutput::PathSentinel => None,
            })
            .collect()
    }

    fn generate(engine: &CompletionEngine, cmd: CommandLine, stub: &str) -> Vec<SuggestionOutput> {
        let analysis = engine.analyze_command(cmd.clone(), cmd, CursorState::synthetic(stub));
        engine.suggestions_for_analysis(&analysis)
    }

    fn values_for_line(engine: &CompletionEngine, line: &str) -> Vec<String> {
        let (_, output) = engine.complete(line, line.len());
        values(output)
    }

    fn command(head: &[&str]) -> CommandLine {
        let mut cmd = CommandLine::default();
        for segment in head {
            cmd.push_head(*segment);
        }
        cmd
    }

    fn with_flag(mut cmd: CommandLine, name: &str, values: &[&str]) -> CommandLine {
        cmd.push_flag_occurrence(FlagOccurrence {
            name: name.to_string(),
            values: values.iter().map(|value| (*value).to_string()).collect(),
        });
        cmd
    }

    #[test]
    fn suggests_flags_in_scope() {
        let engine = CompletionEngine::new(tree());
        let cmd = command(&["orch", "provision"]);

        let values = values(generate(&engine, cmd, "--"));
        assert!(values.contains(&"--provider".to_string()));
        assert!(values.contains(&"--os".to_string()));
    }

    #[test]
    fn fuzzy_matches_flag_names() {
        let engine = CompletionEngine::new(tree());
        let cmd = command(&["orch", "provision"]);

        let values = values(generate(&engine, cmd, "--prv"));
        assert!(values.contains(&"--provider".to_string()));
    }

    #[test]
    fn suggests_flag_values() {
        let engine = CompletionEngine::new(tree());
        let cmd = with_flag(command(&["orch", "provision"]), "--provider", &[]);

        let values = values(generate(&engine, cmd, ""));

        assert!(values.contains(&"nrec".to_string()));
        assert!(values.contains(&"vmware".to_string()));
    }

    #[test]
    fn filters_provider_values_by_os() {
        let engine = CompletionEngine::new(tree());
        let cmd = with_flag(
            with_flag(command(&["orch", "provision"]), "--os", &["alma"]),
            "--provider",
            &[],
        );

        let values = values(generate(&engine, cmd, ""));

        assert!(values.contains(&"nrec".to_string()));
        assert!(!values.contains(&"vmware".to_string()));
    }

    #[test]
    fn suggests_pipe_verbs_after_pipe() {
        let engine = CompletionEngine::new(tree());
        let mut cmd = CommandLine::default();
        cmd.set_pipe(Vec::new());

        let output = generate(&engine, cmd, "F");
        assert!(
            output
                .iter()
                .any(|entry| matches!(entry, SuggestionOutput::Item(item) if item.text == "F"))
        );
    }

    #[test]
    fn fuzzy_matches_long_pipe_verbs() {
        let mut tree = tree();
        tree.pipe_verbs
            .insert("VALUE".to_string(), "Extract values".to_string());
        tree.pipe_verbs
            .insert("VAL".to_string(), "Extract".to_string());
        let engine = CompletionEngine::new(tree);
        let mut cmd = CommandLine::default();
        cmd.set_pipe(Vec::new());

        let output = generate(&engine, cmd, "vlu");
        assert!(
            output
                .iter()
                .any(|entry| matches!(entry, SuggestionOutput::Item(item) if item.text == "VALUE"))
        );
        let values = values(output);
        assert_eq!(values.first().map(String::as_str), Some("VALUE"));
    }

    #[test]
    fn single_value_flag_switches_to_other_flags_after_value() {
        let mut cmd_node = CompletionNode::default();
        cmd_node.flags.insert(
            "--context".to_string(),
            FlagNode {
                suggestions: vec![
                    SuggestionEntry::from("uio"),
                    SuggestionEntry::from("tsd"),
                    SuggestionEntry::from("edu"),
                ],
                ..FlagNode::default()
            },
        );
        cmd_node.flags.insert(
            "--terminal".to_string(),
            FlagNode {
                suggestions: vec![SuggestionEntry::from("cli"), SuggestionEntry::from("repl")],
                ..FlagNode::default()
            },
        );

        let tree = CompletionTree {
            root: CompletionNode::default().with_child("alias", cmd_node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);

        let cmd = with_flag(command(&["alias"]), "--context", &["uio"]);
        let values = values(generate(&engine, cmd, ""));
        assert!(!values.contains(&"uio".to_string()));
        assert!(values.contains(&"--terminal".to_string()));
    }

    #[test]
    fn multi_value_flag_stays_in_value_mode_until_dash() {
        let mut cmd_node = CompletionNode::default();
        cmd_node.flags.insert(
            "--tags".to_string(),
            FlagNode {
                multi: true,
                suggestions: vec![
                    SuggestionEntry::from("red"),
                    SuggestionEntry::from("green"),
                    SuggestionEntry::from("blue"),
                ],
                ..FlagNode::default()
            },
        );
        cmd_node.flags.insert(
            "--mode".to_string(),
            FlagNode {
                suggestions: vec![SuggestionEntry::from("fast"), SuggestionEntry::from("full")],
                ..FlagNode::default()
            },
        );

        let tree = CompletionTree {
            root: CompletionNode::default().with_child("tag", cmd_node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);

        let cmd = with_flag(command(&["tag"]), "--tags", &["red"]);
        let values_for_space = values(generate(&engine, cmd.clone(), ""));
        assert!(values_for_space.contains(&"red".to_string()));
        assert!(!values_for_space.contains(&"--mode".to_string()));

        let values_for_dash = values(generate(&engine, cmd, "-"));
        assert!(values_for_dash.contains(&"--mode".to_string()));
    }

    #[test]
    fn repeated_flag_without_value_stays_in_value_mode_for_last_occurrence() {
        let mut cmd_node = CompletionNode::default();
        cmd_node.flags.insert(
            "--tags".to_string(),
            FlagNode {
                multi: true,
                suggestions: vec![
                    SuggestionEntry::from("red"),
                    SuggestionEntry::from("green"),
                    SuggestionEntry::from("blue"),
                ],
                ..FlagNode::default()
            },
        );
        cmd_node.flags.insert(
            "--mode".to_string(),
            FlagNode {
                suggestions: vec![SuggestionEntry::from("fast"), SuggestionEntry::from("full")],
                ..FlagNode::default()
            },
        );

        let tree = CompletionTree {
            root: CompletionNode::default().with_child("tag", cmd_node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);

        let values = values_for_line(&engine, "tag --tags red --mode fast --tags ");
        assert!(values.contains(&"red".to_string()));
        assert!(values.contains(&"green".to_string()));
        assert!(!values.contains(&"--mode".to_string()));
    }

    #[test]
    fn repeated_flag_partial_value_uses_last_occurrence_context() {
        let mut cmd_node = CompletionNode::default();
        cmd_node.flags.insert(
            "--tags".to_string(),
            FlagNode {
                multi: true,
                suggestions: vec![
                    SuggestionEntry::from("red"),
                    SuggestionEntry::from("green"),
                    SuggestionEntry::from("blue"),
                ],
                ..FlagNode::default()
            },
        );

        let tree = CompletionTree {
            root: CompletionNode::default().with_child("tag", cmd_node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);

        let values = values_for_line(&engine, "tag --tags red --tags bl");
        assert!(values.contains(&"blue".to_string()));
    }

    #[test]
    fn args_after_double_dash_advance_index() {
        let cmd_node = CompletionNode {
            args: vec![
                ArgNode {
                    suggestions: vec![SuggestionEntry::from("one")],
                    ..ArgNode::default()
                },
                ArgNode {
                    suggestions: vec![SuggestionEntry::from("two"), SuggestionEntry::from("three")],
                    ..ArgNode::default()
                },
            ],
            ..CompletionNode::default()
        };
        let tree = CompletionTree {
            root: CompletionNode::default().with_child("cmd", cmd_node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);
        let mut cmd = command(&["cmd"]);
        cmd.push_positional("one");

        let values = values(generate(&engine, cmd, ""));
        assert!(values.contains(&"two".to_string()));
        assert!(values.contains(&"three".to_string()));
        assert!(!values.contains(&"one".to_string()));
    }

    #[test]
    fn path_arg_emits_path_sentinel() {
        let cmd_node = CompletionNode {
            args: vec![ArgNode {
                value_type: Some(ValueType::Path),
                ..ArgNode::default()
            }],
            ..CompletionNode::default()
        };
        let tree = CompletionTree {
            root: CompletionNode::default().with_child("cmd", cmd_node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);
        let cmd = command(&["cmd"]);

        let output = generate(&engine, cmd, "");
        assert!(
            output
                .iter()
                .any(|entry| matches!(entry, SuggestionOutput::PathSentinel))
        );
    }

    #[test]
    fn flag_hints_filter_provider_specific_flags_and_hide_selectors() {
        let mut node = CompletionNode::default();
        node.flags
            .insert("--provider".to_string(), FlagNode::default());
        node.flags.insert(
            "--nrec".to_string(),
            FlagNode {
                flag_only: true,
                ..FlagNode::default()
            },
        );
        node.flags.insert(
            "--vmware".to_string(),
            FlagNode {
                flag_only: true,
                ..FlagNode::default()
            },
        );
        node.flags
            .insert("--comment".to_string(), FlagNode::default());
        node.flags
            .insert("--flavor".to_string(), FlagNode::default());
        node.flags
            .insert("--vcenter".to_string(), FlagNode::default());
        node.flag_hints = Some(FlagHints {
            common: vec![
                "--provider".to_string(),
                "--nrec".to_string(),
                "--vmware".to_string(),
                "--comment".to_string(),
            ],
            by_provider: BTreeMap::from([
                ("nrec".to_string(), vec!["--flavor".to_string()]),
                ("vmware".to_string(), vec!["--vcenter".to_string()]),
            ]),
            required_common: vec!["--comment".to_string()],
            required_by_provider: BTreeMap::from([(
                "nrec".to_string(),
                vec!["--flavor".to_string()],
            )]),
        });

        let tree = CompletionTree {
            root: CompletionNode::default().with_child("provision", node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);

        let cmd = with_flag(command(&["provision"]), "--provider", &["nrec"]);
        let output = generate(&engine, cmd, "--");
        let values = values(output.clone());
        assert!(values.contains(&"--comment".to_string()));
        assert!(values.contains(&"--flavor".to_string()));
        assert!(!values.contains(&"--provider".to_string()));
        assert!(!values.contains(&"--nrec".to_string()));
        assert!(!values.contains(&"--vmware".to_string()));
        assert!(!values.contains(&"--vcenter".to_string()));

        let items = output
            .into_iter()
            .filter_map(|entry| match entry {
                SuggestionOutput::Item(item) => Some(item),
                SuggestionOutput::PathSentinel => None,
            })
            .collect::<Vec<_>>();
        let by_text = items
            .into_iter()
            .map(|item| (item.text.clone(), item))
            .collect::<BTreeMap<_, _>>();
        assert_eq!(
            by_text
                .get("--comment")
                .and_then(|item| item.display.as_deref()),
            Some("--comment*")
        );
        assert_eq!(
            by_text
                .get("--flavor")
                .and_then(|item| item.display.as_deref()),
            Some("--flavor*")
        );
    }

    #[test]
    fn provider_alias_flag_enables_provider_specific_allowlist() {
        let mut node = CompletionNode::default();
        node.flags
            .insert("--provider".to_string(), FlagNode::default());
        node.flags.insert(
            "--nrec".to_string(),
            FlagNode {
                flag_only: true,
                ..FlagNode::default()
            },
        );
        node.flags
            .insert("--flavor".to_string(), FlagNode::default());
        node.flag_hints = Some(FlagHints {
            common: vec!["--provider".to_string(), "--nrec".to_string()],
            by_provider: BTreeMap::from([("nrec".to_string(), vec!["--flavor".to_string()])]),
            ..FlagHints::default()
        });

        let tree = CompletionTree {
            root: CompletionNode::default().with_child("provision", node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);
        let cmd = with_flag(command(&["provision"]), "--nrec", &[]);

        let values = values(generate(&engine, cmd, "--"));
        assert!(values.contains(&"--flavor".to_string()));
        assert!(!values.contains(&"--provider".to_string()));
    }

    #[test]
    fn path_flag_emits_path_sentinel() {
        let mut node = CompletionNode::default();
        node.flags.insert(
            "--file".to_string(),
            FlagNode {
                value_type: Some(ValueType::Path),
                ..FlagNode::default()
            },
        );

        let tree = CompletionTree {
            root: CompletionNode::default().with_child("cmd", node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);
        let cmd = with_flag(command(&["cmd"]), "--file", &[]);

        let output = generate(&engine, cmd, "");
        assert!(
            output
                .iter()
                .any(|entry| matches!(entry, SuggestionOutput::PathSentinel))
        );
    }

    #[test]
    fn flag_suggestions_preserve_meta_and_display_fields() {
        let mut node = CompletionNode::default();
        node.flags.insert(
            "--flavor".to_string(),
            FlagNode {
                suggestions: vec![
                    SuggestionEntry {
                        value: "m1.small".to_string(),
                        meta: Some("1 vCPU".to_string()),
                        display: Some("small".to_string()),
                        sort: Some("10".to_string()),
                    },
                    SuggestionEntry::from("m1.medium"),
                ],
                ..FlagNode::default()
            },
        );
        let tree = CompletionTree {
            root: CompletionNode::default().with_child("orch", node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);
        let cmd = with_flag(command(&["orch"]), "--flavor", &[]);

        let output = generate(&engine, cmd, "");
        let items = output
            .into_iter()
            .filter_map(|entry| match entry {
                SuggestionOutput::Item(item) => Some(item),
                SuggestionOutput::PathSentinel => None,
            })
            .collect::<Vec<_>>();

        let rich = items
            .iter()
            .find(|item| item.text == "m1.small")
            .expect("m1.small suggestion should exist");
        assert_eq!(rich.meta.as_deref(), Some("1 vCPU"));
        assert_eq!(rich.display.as_deref(), Some("small"));
        assert_eq!(rich.sort.as_deref(), Some("10"));
    }

    #[test]
    fn arg_suggestions_honor_numeric_sort_after_match_score() {
        let cmd_node = CompletionNode {
            args: vec![ArgNode {
                suggestions: vec![
                    SuggestionEntry {
                        value: "v10".to_string(),
                        meta: None,
                        display: None,
                        sort: Some("10".to_string()),
                    },
                    SuggestionEntry {
                        value: "v2".to_string(),
                        meta: None,
                        display: None,
                        sort: Some("2".to_string()),
                    },
                ],
                ..ArgNode::default()
            }],
            ..CompletionNode::default()
        };
        let tree = CompletionTree {
            root: CompletionNode::default().with_child("cmd", cmd_node),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);
        let cmd = command(&["cmd"]);

        let values = values(generate(&engine, cmd, ""));
        assert_eq!(values, vec!["v2".to_string(), "v10".to_string()]);
    }

    #[test]
    fn subcommand_suggestions_honor_child_sort_after_match_score() {
        let tree = CompletionTree {
            root: CompletionNode::default()
                .with_child("orch", CompletionNode::default().sort("20"))
                .with_child("config", CompletionNode::default().sort("10")),
            ..CompletionTree::default()
        };
        let engine = CompletionEngine::new(tree);

        let output = values(generate(&engine, CommandLine::default(), ""));

        assert_eq!(output[..2], ["config", "orch"]);
    }
}