brush_core/

completion.rs

//! Implements programmable command completion support.

use clap::ValueEnum;
use std::{
    borrow::Cow,
    collections::HashMap,
    path::{Path, PathBuf},
};
use strum::IntoEnumIterator;

use crate::{
    Shell, commands, env, error, escape, expansion, extensions, interfaces, jobs, namedoptions,
    patterns,
    sys::{self, users},
    trace_categories, traps,
    variables::{self, ShellValueLiteral},
};
use brush_parser::unquote_str;

/// Type of action to take to generate completion candidates.
#[derive(Clone, Debug, ValueEnum)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub enum CompleteAction {
    /// Complete with valid aliases.
    #[clap(name = "alias")]
    Alias,
    /// Complete with names of array shell variables.
    #[clap(name = "arrayvar")]
    ArrayVar,
    /// Complete with names of key bindings.
    #[clap(name = "binding")]
    Binding,
    /// Complete with names of shell builtins.
    #[clap(name = "builtin")]
    Builtin,
    /// Complete with names of executable commands.
    #[clap(name = "command")]
    Command,
    /// Complete with directory names.
    #[clap(name = "directory")]
    Directory,
    /// Complete with names of disabled shell builtins.
    #[clap(name = "disabled")]
    Disabled,
    /// Complete with names of enabled shell builtins.
    #[clap(name = "enabled")]
    Enabled,
    /// Complete with names of exported shell variables.
    #[clap(name = "export")]
    Export,
    /// Complete with filenames.
    #[clap(name = "file")]
    File,
    /// Complete with names of shell functions.
    #[clap(name = "function")]
    Function,
    /// Complete with valid user groups.
    #[clap(name = "group")]
    Group,
    /// Complete with names of valid shell help topics.
    #[clap(name = "helptopic")]
    HelpTopic,
    /// Complete with the system's hostname(s).
    #[clap(name = "hostname")]
    HostName,
    /// Complete with the command names of shell-managed jobs.
    #[clap(name = "job")]
    Job,
    /// Complete with valid shell keywords.
    #[clap(name = "keyword")]
    Keyword,
    /// Complete with the command names of running shell-managed jobs.
    #[clap(name = "running")]
    Running,
    /// Complete with names of system services.
    #[clap(name = "service")]
    Service,
    /// Complete with the names of options settable via shopt.
    #[clap(name = "setopt")]
    SetOpt,
    /// Complete with the names of options settable via set -o.
    #[clap(name = "shopt")]
    ShOpt,
    /// Complete with the names of trappable signals.
    #[clap(name = "signal")]
    Signal,
    /// Complete with the command names of stopped shell-managed jobs.
    #[clap(name = "stopped")]
    Stopped,
    /// Complete with valid usernames.
    #[clap(name = "user")]
    User,
    /// Complete with names of shell variables.
    #[clap(name = "variable")]
    Variable,
}

/// Options influencing how command completions are generated.
#[derive(Clone, Debug, Eq, Hash, PartialEq, ValueEnum)]
pub enum CompleteOption {
    /// Perform rest of default completions if no completions are generated.
    #[clap(name = "bashdefault")]
    BashDefault,
    /// Use default filename completion if no completions are generated.
    #[clap(name = "default")]
    Default,
    /// Treat completions as directory names.
    #[clap(name = "dirnames")]
    DirNames,
    /// Treat completions as filenames.
    #[clap(name = "filenames")]
    FileNames,
    /// Suppress default auto-quotation of completions.
    #[clap(name = "noquote")]
    NoQuote,
    /// Do not sort completions.
    #[clap(name = "nosort")]
    NoSort,
    /// Do not append a trailing space to completions at the end of the input line.
    #[clap(name = "nospace")]
    NoSpace,
    /// Also generate directory completions.
    #[clap(name = "plusdirs")]
    PlusDirs,
}

/// Encapsulates the shell's programmable command completion configuration.
#[derive(Clone, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Config {
    commands: HashMap<String, Spec>,

    /// Optionally, a completion spec to be used as a default, when earlier
    /// matches yield no candidates.
    pub default: Option<Spec>,
    /// Optionally, a completion spec to be used when the command line is empty.
    pub empty_line: Option<Spec>,
    /// Optionally, a completion spec to be used for the initial word of a command line.
    pub initial_word: Option<Spec>,

    /// Optionally, stores the current completion options in effect. May be mutated
    /// while a completion generation is in-flight.
    pub current_completion_options: Option<GenerationOptions>,

    /// Fallback options to use when 'default' completions are requested (not to be
    /// confused with the 'default' completion spec, nor 'bashdefault' completions).
    pub fallback_options: FallbackOptions,
}

/// Options for fallback completions.
#[derive(Clone, Debug)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct FallbackOptions {
    /// If true, mark directory completions with a trailing slash.
    pub mark_directories: bool,
    /// If true, mark symlinked directory completions with a trailing slash.
    pub mark_symlinked_directories: bool,
}

impl Default for FallbackOptions {
    fn default() -> Self {
        Self {
            mark_directories: true,
            mark_symlinked_directories: false,
        }
    }
}

/// Options for generating completions.
#[derive(Clone, Debug, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct GenerationOptions {
    //
    // Options
    /// Perform rest of default completions if no completions are generated.
    pub bash_default: bool,
    /// Use default readline-style filename completion if no completions are generated.
    pub default: bool,
    /// Treat completions as directory names.
    pub dir_names: bool,
    /// Treat completions as filenames.
    pub file_names: bool,
    /// Do not add usual quoting for completions.
    pub no_quote: bool,
    /// Do not sort completions.
    pub no_sort: bool,
    /// Do not append typical space to a completion at the end of the input line.
    pub no_space: bool,
    /// Also complete with directory names.
    pub plus_dirs: bool,
}

/// Encapsulates a command completion specification; provides policy for how to
/// generate completions for a given input.
#[derive(Clone, Debug, Default)]
#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
pub struct Spec {
    //
    // Options
    /// Options to use for completion.
    pub options: GenerationOptions,

    //
    // Generators
    /// Actions to take to generate completions.
    pub actions: Vec<CompleteAction>,
    /// Optionally, a glob pattern whose expansion will be used as completions.
    pub glob_pattern: Option<String>,
    /// Optionally, a list of words to use as completions.
    pub word_list: Option<String>,
    /// Optionally, the name of a shell function to invoke to generate completions.
    pub function_name: Option<String>,
    /// Optionally, the name of a command to execute to generate completions.
    pub command: Option<String>,

    //
    // Filters
    /// Optionally, a pattern to filter completions.
    pub filter_pattern: Option<String>,
    /// If true, completion candidates matching `filter_pattern` are removed;
    /// otherwise, those not matching it are removed.
    pub filter_pattern_excludes: bool,

    //
    // Transformers
    /// Optionally, provides a prefix to be prepended to all completion candidates.
    pub prefix: Option<String>,
    /// Optionally, provides a suffix to be prepended to all completion candidates.
    pub suffix: Option<String>,
}

/// Describes what triggered the completion process.
#[derive(Clone, Copy, Debug, Default)]
pub enum CompletionTrigger {
    /// Interactive completion triggered by Tab key (normal completion).
    #[default]
    InteractiveComplete,
    /// Programmatic generation via the `compgen` builtin.
    Programmatic,
}

impl CompletionTrigger {
    /// Returns the `COMP_TYPE` value for this trigger.
    pub const fn comp_type(self) -> i32 {
        match self {
            Self::InteractiveComplete => 9, // TAB = normal completion
            Self::Programmatic => 0,
        }
    }

    /// Returns the `COMP_KEY` value for this trigger.
    pub const fn comp_key(self) -> i32 {
        match self {
            Self::InteractiveComplete => 9, // TAB key
            Self::Programmatic => 0,
        }
    }
}

/// Encapsulates context used during completion generation.
#[derive(Debug)]
pub struct Context<'a> {
    /// The token to complete.
    pub token_to_complete: &'a str,

    /// If available, the name of the command being invoked.
    pub command_name: Option<&'a str>,
    /// If there was one, the token preceding the one being completed.
    pub preceding_token: Option<&'a str>,

    /// The 0-based index of the token to complete.
    pub token_index: usize,

    /// The input line.
    pub input_line: &'a str,
    /// The 0-based index of the cursor in the input line.
    pub cursor_index: usize,
    /// The tokens in the input line.
    pub tokens: &'a [&'a CompletionToken<'a>],

    /// What triggered the completion.
    pub trigger: CompletionTrigger,
}

impl Spec {
    /// Generates completion candidates using this specification.
    ///
    /// # Arguments
    ///
    /// * `shell` - The shell instance to use for completion generation.
    /// * `context` - The context in which completion is being generated.
    #[expect(clippy::too_many_lines)]
    pub async fn get_completions(
        &self,
        shell: &mut Shell<impl extensions::ShellExtensions>,
        context: &Context<'_>,
    ) -> Result<Answer, crate::error::Error> {
        // Store the current options in the shell; this is needed since the compopt
        // built-in has the ability of modifying the options for an in-flight
        // completion process.
        shell.completion_config_mut().current_completion_options = Some(self.options.clone());

        // Generate completions based on any provided actions (and on words).
        let mut candidates = self.generate_action_completions(shell, context).await?;
        if let Some(word_list) = &self.word_list {
            let params = shell.default_exec_params();
            // Per POSIX / bash docs, -W word list is subject to shell expansion
            // and field splitting but NOT pathname expansion (globbing).
            let options = crate::expansion::ExpanderOptions {
                pathname_expand: false,
                ..Default::default()
            };
            let words = crate::expansion::full_expand_and_split_word_with_options(
                shell, &params, word_list, &options,
            )
            .await?;
            for word in words {
                if word.starts_with(context.token_to_complete) {
                    candidates.push(word);
                }
            }
        }

        if let Some(glob_pattern) = &self.glob_pattern {
            let pattern = patterns::Pattern::from(glob_pattern.as_str())
                .set_extended_globbing(shell.options().extended_globbing)
                .set_case_insensitive(shell.options().case_insensitive_pathname_expansion);

            let expansions = pattern
                .expand(
                    shell.working_dir(),
                    Some(&patterns::Pattern::accept_all_expand_filter),
                    &patterns::FilenameExpansionOptions::default(),
                )?
                .into_paths();

            for expansion in expansions {
                candidates.push(expansion);
            }
        }
        if let Some(function_name) = &self.function_name {
            let call_result = self
                .call_completion_function(shell, function_name.as_str(), context)
                .await?;

            match call_result {
                Answer::RestartCompletionProcess => return Ok(call_result),
                Answer::Candidates(mut new_candidates, _options) => {
                    candidates.append(&mut new_candidates);
                }
            }
        }
        if let Some(command) = &self.command {
            let mut new_candidates = self
                .call_completion_command(shell, command.as_str(), context)
                .await?;
            candidates.append(&mut new_candidates);
        }

        // Apply filter pattern, if present. Anything the filter selects gets removed.
        if let Some(filter_pattern) = &self.filter_pattern
            && !filter_pattern.is_empty()
        {
            let mut updated = Vec::new();

            for candidate in candidates {
                let matches = completion_filter_pattern_matches(
                    filter_pattern.as_str(),
                    candidate.as_str(),
                    context.token_to_complete,
                    shell,
                )?;

                if self.filter_pattern_excludes != matches {
                    updated.push(candidate);
                }
            }

            candidates = updated;
        }

        // Add prefix and/or suffix, if present.
        if self.prefix.is_some() || self.suffix.is_some() {
            let empty = String::new();
            let prefix = self.prefix.as_ref().unwrap_or(&empty);
            let suffix = self.suffix.as_ref().unwrap_or(&empty);

            let mut updated = Vec::new();
            for candidate in candidates {
                updated.push(std::format!("{prefix}{candidate}{suffix}"));
            }

            candidates = updated;
        }

        //
        // Now apply options
        //

        let options = if let Some(options) = &shell.completion_config().current_completion_options {
            options
        } else {
            &self.options
        };

        let mut processing_options = ProcessingOptions {
            treat_as_filenames: options.file_names,
            no_autoquote_filenames: options.no_quote,
            no_trailing_space_at_end_of_line: options.no_space,
        };

        if options.plus_dirs || options.dir_names {
            // Also add dir name completion.
            let mut dir_candidates = get_file_completions(
                shell,
                context.token_to_complete,
                /* must_be_dir */ true,
            )
            .await;
            candidates.append(&mut dir_candidates);
        }

        // If we still have no candidates, and bashdefault completions were requested, then generate
        // those.
        if candidates.is_empty() && options.bash_default {
            // TODO(completions): it's not clear what default "bash" completions means. From basic
            // testing, this doesn't seem to include basic file and directory name
            // completion.
            tracing::debug!(target: trace_categories::COMPLETION, "unimplemented: complete -o bashdefault");
        }

        // If we still have no candidates, and default completions were requested, then generate
        // those.
        if candidates.is_empty() && options.default {
            // N.B. We approximate "default" readline completion behavior by getting file and
            // dir completions.
            let must_be_dir = options.dir_names;

            let mut default_candidates =
                get_file_completions(shell, context.token_to_complete, must_be_dir).await;
            candidates.append(&mut default_candidates);

            if shell.completion_config().fallback_options.mark_directories {
                processing_options.treat_as_filenames = true;
            }
        }

        // Sort, unless blocked by options.
        if !self.options.no_sort {
            candidates.sort();
        }

        Ok(Answer::Candidates(candidates, processing_options))
    }

    #[expect(clippy::too_many_lines)]
    async fn generate_action_completions(
        &self,
        shell: &Shell<impl extensions::ShellExtensions>,
        context: &Context<'_>,
    ) -> Result<Vec<String>, error::Error> {
        let mut candidates = Vec::new();

        let token = context.token_to_complete;

        for action in &self.actions {
            match action {
                CompleteAction::Alias => {
                    for name in shell.aliases().keys() {
                        if name.starts_with(token) {
                            candidates.push(name.clone());
                        }
                    }
                }
                CompleteAction::ArrayVar => {
                    for (name, var) in shell.env().iter() {
                        if var.value().is_array() && name.starts_with(token) {
                            candidates.push(name.to_owned());
                        }
                    }
                }
                CompleteAction::Binding => {
                    for input_func in interfaces::InputFunction::iter() {
                        let name: &'static str = input_func.into();
                        if name.starts_with(token) {
                            candidates.push(name.to_string());
                        }
                    }
                }
                CompleteAction::Builtin => {
                    for name in shell.builtins().keys() {
                        if name.starts_with(token) {
                            candidates.push(name.to_owned());
                        }
                    }
                }
                CompleteAction::Command => {
                    let mut command_completions =
                        get_external_command_completions(shell, context.token_to_complete);
                    candidates.append(&mut command_completions);
                    for name in shell.builtins().keys() {
                        if name.starts_with(token) {
                            candidates.push(name.to_owned());
                        }
                    }
                    for keyword in shell.get_keywords() {
                        if keyword.starts_with(token) {
                            candidates.push(keyword.to_string());
                        }
                    }
                    for (name, _) in shell.funcs().iter() {
                        candidates.push(name.to_owned());
                    }
                }
                CompleteAction::Directory => {
                    let mut file_completions =
                        get_file_completions(shell, context.token_to_complete, true).await;
                    candidates.append(&mut file_completions);
                }
                CompleteAction::Disabled => {
                    for (name, registration) in shell.builtins() {
                        if registration.disabled && name.starts_with(token) {
                            candidates.push(name.to_owned());
                        }
                    }
                }
                CompleteAction::Enabled => {
                    for (name, registration) in shell.builtins() {
                        if !registration.disabled && name.starts_with(token) {
                            candidates.push(name.to_owned());
                        }
                    }
                }
                CompleteAction::Export => {
                    for (key, value) in shell.env().iter() {
                        if value.is_exported() && key.starts_with(token) {
                            candidates.push(key.to_owned());
                        }
                    }
                }
                CompleteAction::File => {
                    let mut file_completions =
                        get_file_completions(shell, context.token_to_complete, false).await;
                    candidates.append(&mut file_completions);
                }
                CompleteAction::Function => {
                    for (name, _) in shell.funcs().iter() {
                        candidates.push(name.to_owned());
                    }
                }
                CompleteAction::Group => {
                    for group_name in users::get_all_groups()? {
                        if group_name.starts_with(token) {
                            candidates.push(group_name);
                        }
                    }
                }
                CompleteAction::HelpTopic => {
                    // For now, we only have help topics for built-in commands.
                    for name in shell.builtins().keys() {
                        if name.starts_with(token) {
                            candidates.push(name.to_owned());
                        }
                    }
                }
                CompleteAction::HostName => {
                    // N.B. We only retrieve one hostname.
                    if let Ok(name) = sys::network::get_hostname() {
                        let name = name.to_string_lossy();
                        if name.starts_with(token) {
                            candidates.push(name.to_string());
                        }
                    }
                }
                CompleteAction::Job => {
                    for job in &shell.jobs().jobs {
                        let command_name = job.command_name();
                        if command_name.starts_with(token) {
                            candidates.push(command_name.to_owned());
                        }
                    }
                }
                CompleteAction::Keyword => {
                    for keyword in shell.get_keywords() {
                        if keyword.starts_with(token) {
                            candidates.push(keyword.to_string());
                        }
                    }
                }
                CompleteAction::Running => {
                    for job in &shell.jobs().jobs {
                        if matches!(job.state, jobs::JobState::Running) {
                            let command_name = job.command_name();
                            if command_name.starts_with(token) {
                                candidates.push(command_name.to_owned());
                            }
                        }
                    }
                }
                CompleteAction::Service => {
                    tracing::debug!(target: trace_categories::COMPLETION, "unimplemented: complete -A service");
                }
                CompleteAction::SetOpt => {
                    for option in namedoptions::options(namedoptions::ShellOptionKind::SetO).iter()
                    {
                        if option.name.starts_with(token) {
                            candidates.push(option.name.to_owned());
                        }
                    }
                }
                CompleteAction::ShOpt => {
                    for option in namedoptions::options(namedoptions::ShellOptionKind::Shopt).iter()
                    {
                        if option.name.starts_with(token) {
                            candidates.push(option.name.to_owned());
                        }
                    }
                }
                CompleteAction::Signal => {
                    for signal in traps::TrapSignal::iterator() {
                        if signal.as_str().starts_with(token) {
                            candidates.push(signal.as_str().to_string());
                        }
                    }
                }
                CompleteAction::Stopped => {
                    for job in &shell.jobs().jobs {
                        if matches!(job.state, jobs::JobState::Stopped) {
                            let command_name = job.command_name();
                            if command_name.starts_with(token) {
                                candidates.push(job.command_name().to_owned());
                            }
                        }
                    }
                }
                CompleteAction::User => {
                    for user_name in users::get_all_users()? {
                        if user_name.starts_with(token) {
                            candidates.push(user_name);
                        }
                    }
                }
                CompleteAction::Variable => {
                    for (key, _) in shell.env().iter() {
                        if key.starts_with(token) {
                            candidates.push(key.to_owned());
                        }
                    }
                }
            }
        }

        Ok(candidates)
    }

    async fn call_completion_command(
        &self,
        shell: &Shell<impl extensions::ShellExtensions>,
        command_name: &str,
        context: &Context<'_>,
    ) -> Result<Vec<String>, error::Error> {
        // Move to a subshell so we can start filling out variables.
        let mut shell = shell.clone();

        let vars_and_values: Vec<(&str, ShellValueLiteral)> = vec![
            ("COMP_LINE", context.input_line.into()),
            ("COMP_POINT", context.cursor_index.to_string().into()),
            ("COMP_KEY", context.trigger.comp_key().to_string().into()),
            ("COMP_TYPE", context.trigger.comp_type().to_string().into()),
        ];

        // Fill out variables.
        for (var, value) in vars_and_values {
            shell.env_mut().update_or_add(
                var,
                value,
                |v| {
                    v.export();
                    Ok(())
                },
                env::EnvironmentLookup::Anywhere,
                env::EnvironmentScope::Global,
            )?;
        }

        // Compute args.
        let mut args = vec![
            context.command_name.unwrap_or(""),
            context.token_to_complete,
        ];
        if let Some(preceding_token) = context.preceding_token {
            args.push(preceding_token);
        }

        // Compose the full command line.
        let mut command_line = command_name.to_owned();
        for arg in args {
            command_line.push(' ');

            let escaped_arg = escape::quote_if_needed(arg, escape::QuoteMode::SingleQuote);
            command_line.push_str(escaped_arg.as_ref());
        }

        // Run the command.
        let params = shell.default_exec_params();
        let output =
            commands::invoke_command_in_subshell_and_get_output(&mut shell, &params, command_line)
                .await?;

        // Split results.
        let mut candidates = Vec::new();
        for line in output.lines() {
            candidates.push(line.to_owned());
        }

        Ok(candidates)
    }

    async fn call_completion_function(
        &self,
        shell: &mut Shell<impl extensions::ShellExtensions>,
        function_name: &str,
        context: &Context<'_>,
    ) -> Result<Answer, error::Error> {
        // TODO(completions): Don't pollute the persistent environment with these?
        let vars_and_values: Vec<(&str, ShellValueLiteral)> = vec![
            ("COMP_LINE", context.input_line.into()),
            ("COMP_POINT", context.cursor_index.to_string().into()),
            ("COMP_KEY", context.trigger.comp_key().to_string().into()),
            ("COMP_TYPE", context.trigger.comp_type().to_string().into()),
            (
                "COMP_WORDS",
                context
                    .tokens
                    .iter()
                    .map(|t| t.text)
                    .collect::<Vec<_>>()
                    .into(),
            ),
            ("COMP_CWORD", context.token_index.to_string().into()),
        ];

        tracing::debug!(target: trace_categories::COMPLETION, "[calling completion func '{function_name}']: {}",
            vars_and_values.iter().map(|(k, v)| std::format!("{k}={v}")).collect::<Vec<String>>().join(" "));

        let mut vars_to_remove = Vec::with_capacity(vars_and_values.len());
        for (var, value) in vars_and_values {
            shell.env_mut().update_or_add(
                var,
                value,
                |_| Ok(()),
                env::EnvironmentLookup::Anywhere,
                env::EnvironmentScope::Global,
            )?;

            vars_to_remove.push(var);
        }

        let mut args = vec![
            context.command_name.unwrap_or(""),
            context.token_to_complete,
        ];
        if let Some(preceding_token) = context.preceding_token {
            args.push(preceding_token);
        }

        // Suppress trap delivery during completion function invocation.
        // N.B. We use manual acquire/release rather than an RAII guard because an
        // RAII guard would need to hold `&mut Shell`, preventing the mutable borrow
        // required by `invoke_function()`. This is safe because `invoke_result` is
        // captured into a variable (never early-returned with `?`), so
        // `release_trap_delivery_block()` always runs.
        shell.acquire_trap_delivery_block();

        let params = shell.default_exec_params();
        let invoke_result = shell
            .invoke_function(function_name, args.iter(), &params)
            .await;

        tracing::debug!(target: trace_categories::COMPLETION, "[completion function '{function_name}' returned: {invoke_result:?}]");

        shell.release_trap_delivery_block();

        // Make a best-effort attempt to unset the temporary variables.
        for var_name in vars_to_remove {
            let _ = shell.env_mut().unset(var_name);
        }

        let result = invoke_result.unwrap_or_else(|e| {
            tracing::warn!(target: trace_categories::COMPLETION, "error while running completion function '{function_name}': {e}");
            1 // Report back a non-zero exit code.
        });

        // When the function returns the special value 124, then it's a request
        // for us to restart the completion process.
        if result == 124 {
            Ok(Answer::RestartCompletionProcess)
        } else {
            if let Some(reply) = shell.env_mut().unset("COMPREPLY")? {
                tracing::debug!(target: trace_categories::COMPLETION, "[completion function yielded: {reply:?}]");

                match reply.value() {
                    variables::ShellValue::IndexedArray(values) => {
                        return Ok(Answer::Candidates(
                            values.values().map(|v| v.to_owned()).collect(),
                            ProcessingOptions::default(),
                        ));
                    }
                    variables::ShellValue::String(s) => {
                        let candidates = vec![s.to_owned()];
                        return Ok(Answer::Candidates(candidates, ProcessingOptions::default()));
                    }
                    _ => (),
                }
            }

            Ok(Answer::Candidates(Vec::new(), ProcessingOptions::default()))
        }
    }
}

/// Represents a set of generated command completions.
#[derive(Debug, Default)]
pub struct Completions {
    /// The index in the input line where the completions should be inserted. Represented
    /// as a byte offset into the input line; must be at a clean character boundary.
    pub insertion_index: usize,
    /// The number of elements in the input line that should be removed before insertion.
    /// Represented as a byte count; must capture an exact character boundary.
    pub delete_count: usize,
    /// The ordered set of completions.
    pub candidates: Vec<String>,
    /// Options for processing the candidates.
    pub options: ProcessingOptions,
}

/// Options governing how command completion candidates are processed after being generated.
#[derive(Debug)]
pub struct ProcessingOptions {
    /// Treat completions as file names.
    pub treat_as_filenames: bool,
    /// Don't auto-quote completions that are file names.
    pub no_autoquote_filenames: bool,
    /// Don't append a trailing space to completions at the end of the input line.
    pub no_trailing_space_at_end_of_line: bool,
}

/// Represents a token in the input line being completed.
#[derive(Debug, Clone, Copy)]
pub struct CompletionToken<'a> {
    /// The text of the token.
    pub text: &'a str,
    /// The start of the token, expressed as a byte offset into the input line.
    pub start: usize,
}

impl CompletionToken<'_> {
    /// Returns the length of the token, expressed as a byte count.
    pub const fn length(&self) -> usize {
        self.text.len()
    }

    /// Returns the end of the token, expressed as a byte offset into the input line.
    pub const fn end(&self) -> usize {
        self.start + self.length()
    }
}

impl Default for ProcessingOptions {
    fn default() -> Self {
        Self {
            treat_as_filenames: true,
            no_autoquote_filenames: false,
            no_trailing_space_at_end_of_line: false,
        }
    }
}

/// Encapsulates a completion answer.
pub enum Answer {
    /// The completion process generated a set of candidates along with options
    /// controlling how to process them.
    Candidates(Vec<String>, ProcessingOptions),
    /// The completion process needs to be restarted.
    RestartCompletionProcess,
}

const EMPTY_COMMAND: &str = "_EmptycmD_";
const DEFAULT_COMMAND: &str = "_DefaultCmD_";
const INITIAL_WORD: &str = "_InitialWorD_";

impl Config {
    /// Removes all registered completion specs.
    pub fn clear(&mut self) {
        self.commands.clear();
        self.empty_line = None;
        self.default = None;
        self.initial_word = None;
    }

    /// Ensures the named completion spec is no longer registered; returns whether a
    /// removal operation was required.
    ///
    /// # Arguments
    ///
    /// * `name` - The name of the completion spec to remove.
    pub fn remove(&mut self, name: &str) -> bool {
        match name {
            EMPTY_COMMAND => {
                let result = self.empty_line.is_some();
                self.empty_line = None;
                result
            }
            DEFAULT_COMMAND => {
                let result = self.default.is_some();
                self.default = None;
                result
            }
            INITIAL_WORD => {
                let result = self.initial_word.is_some();
                self.initial_word = None;
                result
            }
            _ => self.commands.remove(name).is_some(),
        }
    }

    /// Returns an iterator over the completion specs.
    pub fn iter(&self) -> impl Iterator<Item = (&String, &Spec)> {
        self.commands.iter()
    }

    /// If present, returns the completion spec for the command of the given name.
    ///
    /// # Arguments
    ///
    /// * `name` - The name of the command.
    pub fn get(&self, name: &str) -> Option<&Spec> {
        match name {
            EMPTY_COMMAND => self.empty_line.as_ref(),
            DEFAULT_COMMAND => self.default.as_ref(),
            INITIAL_WORD => self.initial_word.as_ref(),
            _ => self.commands.get(name),
        }
    }

    /// If present, sets the provided completion spec to be associated with the
    /// command of the given name.
    ///
    /// # Arguments
    ///
    /// * `name` - The name of the command.
    /// * `spec` - The completion spec to associate with the command.
    pub fn set(&mut self, name: &str, spec: Spec) {
        match name {
            EMPTY_COMMAND => {
                self.empty_line = Some(spec);
            }
            DEFAULT_COMMAND => {
                self.default = Some(spec);
            }
            INITIAL_WORD => {
                self.initial_word = Some(spec);
            }
            _ => {
                self.commands.insert(name.to_owned(), spec);
            }
        }
    }

    /// Returns a mutable reference to the completion spec for the command of the
    /// given name; if the command already was associated with a spec, returns
    /// a reference to that existing spec. Otherwise registers a new default
    /// spec and returns a mutable reference to it.
    ///
    /// # Arguments
    ///
    /// * `name` - The name of the command.
    #[allow(
        clippy::missing_panics_doc,
        clippy::unwrap_used,
        reason = "these unwrap calls should not fail"
    )]
    pub fn get_or_add_mut(&mut self, name: &str) -> &mut Spec {
        match name {
            EMPTY_COMMAND => {
                if self.empty_line.is_none() {
                    self.empty_line = Some(Spec::default());
                }
                self.empty_line.as_mut().unwrap()
            }
            DEFAULT_COMMAND => {
                if self.default.is_none() {
                    self.default = Some(Spec::default());
                }
                self.default.as_mut().unwrap()
            }
            INITIAL_WORD => {
                if self.initial_word.is_none() {
                    self.initial_word = Some(Spec::default());
                }
                self.initial_word.as_mut().unwrap()
            }
            _ => self.commands.entry(name.to_owned()).or_default(),
        }
    }

    /// Generates completions for the given input line and cursor position.
    ///
    /// # Arguments
    ///
    /// * `shell` - The shell instance to use for completion generation.
    /// * `input` - The input line for which completions are being generated.
    /// * `position` - The 0-based index of the cursor in the input line.
    #[expect(clippy::string_slice)]
    pub async fn get_completions(
        &self,
        shell: &mut Shell<impl extensions::ShellExtensions>,
        input: &str,
        position: usize,
    ) -> Result<Completions, error::Error> {
        const MAX_RESTARTS: u32 = 10;

        // Make a best-effort attempt to tokenize.
        let tokens = Self::tokenize_input_for_completion(shell, input);

        let cursor = position;
        let mut preceding_token = None;
        let mut completion_prefix = "";
        let mut insertion_index = cursor;
        let mut completion_token_index = tokens.len();

        // Copy a set of references to the tokens; we will adjust this list as
        // we find we need to insert an empty token.
        let mut adjusted_tokens: Vec<&CompletionToken<'_>> = tokens.iter().collect();

        // Try to find which token we are in.
        for (i, token) in tokens.iter().enumerate() {
            // If the cursor is before the start of the token, then it's between
            // this token and the one that preceded it (or it's before the first
            // token if this is the first token).
            if cursor < token.start {
                // TODO(completions): Should insert an empty token here; the position looks to have
                // been between this token and the preceding one.
                completion_token_index = i;
                break;
            }
            // If the cursor is anywhere from the first char of the token up to
            // (and including) the first char after the token, then this we need
            // to generate completions to replace/update this token. We'll pay
            // attention to the position to figure out the prefix that we should
            // be completing.
            else if cursor >= token.start && cursor <= token.end() {
                // Update insertion index.
                insertion_index = token.start;

                // Update prefix.
                let offset_into_token = cursor - insertion_index;
                let token_str = token.text;
                completion_prefix = &token_str[..offset_into_token];

                // Update token index.
                completion_token_index = i;

                break;
            }

            // Otherwise, we need to keep looking. Update what we think the
            // preceding token may be.
            preceding_token = Some(token);
        }

        // If the position is after the last token, then we need to insert an empty
        // token for the new token to be generated.
        let empty_token = CompletionToken {
            text: "",
            start: input.len(),
        };
        if completion_token_index == tokens.len() {
            adjusted_tokens.push(&empty_token);
        }

        // Get the completions.
        let mut result = Answer::RestartCompletionProcess;
        let mut restart_count = 0;
        while matches!(result, Answer::RestartCompletionProcess) {
            if restart_count > MAX_RESTARTS {
                tracing::warn!("possible infinite loop detected in completion process");
                break;
            }

            let completion_context = Context {
                token_to_complete: completion_prefix,
                preceding_token: preceding_token.map(|t| t.text),
                command_name: adjusted_tokens.first().map(|token| token.text),
                input_line: input,
                token_index: completion_token_index,
                tokens: adjusted_tokens.as_slice(),
                cursor_index: position,
                trigger: CompletionTrigger::InteractiveComplete,
            };

            result = self
                .get_completions_for_token(shell, completion_context)
                .await;

            restart_count += 1;
        }

        match result {
            Answer::Candidates(candidates, options) => Ok(Completions {
                insertion_index,
                delete_count: completion_prefix.len(),
                candidates,
                options,
            }),
            Answer::RestartCompletionProcess => Ok(Completions {
                insertion_index,
                delete_count: 0,
                candidates: Vec::new(),
                options: ProcessingOptions::default(),
            }),
        }
    }

    fn tokenize_input_for_completion<'a>(
        shell: &Shell<impl extensions::ShellExtensions>,
        input: &'a str,
    ) -> Vec<CompletionToken<'a>> {
        const FALLBACK: &str = " \t\n\"\'@><=;|&(:";

        let delimiter_str = shell
            .env_str("COMP_WORDBREAKS")
            .unwrap_or_else(|| FALLBACK.into());

        let delimiters: Vec<_> = delimiter_str.chars().collect();

        simple_tokenize_by_delimiters(input, delimiters.as_slice())
    }

    async fn get_completions_for_token(
        &self,
        shell: &mut Shell<impl extensions::ShellExtensions>,
        context: Context<'_>,
    ) -> Answer {
        // See if we can find a completion spec matching the current command.
        let mut found_spec: Option<&Spec> = None;

        if let Some(command_name) = context.command_name {
            if context.token_index == 0 {
                if let Some(spec) = &self.initial_word {
                    found_spec = Some(spec);
                }
            } else {
                if let Some(spec) = shell.completion_config().commands.get(command_name) {
                    found_spec = Some(spec);
                } else if let Some(file_name) = PathBuf::from(command_name).file_name() {
                    if let Some(spec) = shell
                        .completion_config()
                        .commands
                        .get(&file_name.to_string_lossy().to_string())
                    {
                        found_spec = Some(spec);
                    }
                }

                if found_spec.is_none() {
                    if let Some(spec) = &self.default {
                        found_spec = Some(spec);
                    }
                }
            }
        } else {
            if let Some(spec) = &self.empty_line {
                found_spec = Some(spec);
            }
        }

        // Try to generate completions.
        if let Some(spec) = found_spec {
            spec.to_owned()
                .get_completions(shell, &context)
                .await
                .unwrap_or_else(|_err| Answer::Candidates(Vec::new(), ProcessingOptions::default()))
        } else {
            // If we didn't find a spec, then fall back to basic completion.
            get_completions_using_basic_lookup(shell, &context).await
        }
    }
}

async fn get_file_completions(
    shell: &Shell<impl extensions::ShellExtensions>,
    token_to_complete: &str,
    must_be_dir: bool,
) -> Vec<String> {
    // Basic-expand the token-to-be-completed; it won't have been expanded to this point.
    let mut throwaway_shell = shell.clone();
    let params = throwaway_shell.default_exec_params();
    let options = expansion::ExpanderOptions {
        execute_command_substitutions: false,
        ..Default::default()
    };
    let expanded_token = expansion::basic_expand_word_with_options(
        &mut throwaway_shell,
        &params,
        &unquote_str(token_to_complete),
        &options,
    )
    .await
    .unwrap_or_else(|_err| token_to_complete.to_owned());

    // Normalize path separators before building the glob pattern, because backslash
    // is the escape character in glob syntax and must not be confused with a Windows
    // path separator.
    let expanded_token = sys::fs::normalize_path_separators(&expanded_token).into_owned();

    let glob = std::format!("{expanded_token}*");

    let path_filter = |path: &Path| !must_be_dir || shell.absolute_path(path).is_dir();

    let pattern = patterns::Pattern::from(glob)
        .set_extended_globbing(shell.options().extended_globbing)
        .set_case_insensitive(shell.options().case_insensitive_pathname_expansion);

    let mut completions: Vec<String> = pattern
        .expand(
            shell.working_dir(),
            Some(&path_filter),
            &patterns::FilenameExpansionOptions::default(),
        )
        .unwrap_or_default()
        .into_paths()
        .into_iter()
        .map(|p| match sys::fs::normalize_path_separators(&p) {
            std::borrow::Cow::Borrowed(_) => p,
            std::borrow::Cow::Owned(normalized) => normalized,
        })
        .collect();

    match expanded_token.as_str() {
        "." => {
            completions.push(".".into());
            completions.push("..".into());
        }
        ".." => {
            completions.push("..".into());
        }
        _ => {}
    }

    completions.sort();
    completions.dedup();
    completions
}

fn get_external_command_completions(
    shell: &Shell<impl extensions::ShellExtensions>,
    prefix: &str,
) -> Vec<String> {
    let mut candidates = Vec::new();

    // Look for external commands.
    for path in shell.find_executables_in_path_with_prefix(
        prefix,
        shell.options().case_insensitive_pathname_expansion,
    ) {
        if let Some(file_name) = path.file_name() {
            candidates.push(file_name.to_string_lossy().to_string());
        }
    }

    candidates.into_iter().collect()
}

/// Attempts to complete a variable name from the given token.
/// Returns `Some(Answer)` if the token looks like a variable reference being typed,
/// or `None` if file/command completion should be used instead.
///
/// # Arguments
///
/// * `shell` - The shell instance to use for variable lookup.
/// * `token` - The token being completed. May be empty.
fn try_get_variable_completions(
    shell: &Shell<impl extensions::ShellExtensions>,
    token: &str,
) -> Option<Answer> {
    // Determine if this is a braced or unbraced variable reference
    let (var_prefix, use_braces) = if let Some(prefix) = token.strip_prefix("${") {
        // For braced: only complete if brace isn't closed yet
        if prefix.contains('}') {
            return None;
        }
        (prefix, true)
    } else if let Some(prefix) = token.strip_prefix('$') {
        (prefix, false)
    } else {
        return None;
    };

    // If there's a path separator, this is a path like $HOME/foo, not a variable to complete
    if sys::fs::contains_path_separator(var_prefix) {
        return None;
    }

    // Find matching variables
    let mut candidates: Vec<String> = shell
        .env()
        .iter()
        .filter(|(key, _)| key.starts_with(var_prefix))
        .map(|(key, _)| {
            if use_braces {
                format!("${{{key}}}")
            } else {
                format!("${key}")
            }
        })
        .collect();
    candidates.sort();

    // Variable completions should not be treated as filenames (no escaping needed)
    let options = ProcessingOptions {
        treat_as_filenames: false,
        ..ProcessingOptions::default()
    };

    Some(Answer::Candidates(candidates, options))
}

/// Adds command-position completions to candidates.
/// This includes external commands, builtins, functions, aliases, and keywords.
fn add_command_completions(
    shell: &Shell<impl extensions::ShellExtensions>,
    prefix: &str,
    candidates: &mut Vec<String>,
) {
    // Add external commands.
    let mut command_completions = get_external_command_completions(shell, prefix);
    candidates.append(&mut command_completions);

    // Add built-in commands.
    for (name, registration) in shell.builtins() {
        if !registration.disabled && name.starts_with(prefix) {
            candidates.push(name.to_owned());
        }
    }

    // Add shell functions.
    for (name, _) in shell.funcs().iter() {
        if name.starts_with(prefix) {
            candidates.push(name.to_owned());
        }
    }

    // Add aliases.
    for name in shell.aliases().keys() {
        if name.starts_with(prefix) {
            candidates.push(name.to_owned());
        }
    }

    // Add keywords.
    for keyword in shell.get_keywords() {
        if keyword.starts_with(prefix) {
            candidates.push(keyword.to_string());
        }
    }
}

async fn get_completions_using_basic_lookup(
    shell: &Shell<impl extensions::ShellExtensions>,
    context: &Context<'_>,
) -> Answer {
    let token = context.token_to_complete;

    // Try variable completion first (e.g., $HO -> $HOME, ${HO -> ${HOME})
    if let Some(answer) = try_get_variable_completions(shell, token) {
        return answer;
    }

    // File completions
    let mut candidates = get_file_completions(shell, token, false).await;

    // If this appears to be the command token (and if there's *some* prefix without
    // a path separator) then also consider whether we should search the path for
    // completions too.
    // TODO(completions): Do a better job than just checking if index == 0.
    let is_command_position =
        context.token_index == 0 && !token.is_empty() && !sys::fs::contains_path_separator(token);

    if is_command_position {
        add_command_completions(shell, token, &mut candidates);
        candidates.sort();
    }

    Answer::Candidates(candidates, ProcessingOptions::default())
}

/// Tokenizes input by splitting on delimiter characters. Words (non-delimiter sequences)
/// are emitted as tokens. Consecutive non-whitespace delimiters are grouped into a single
/// token. Whitespace delimiters separate tokens but are not emitted themselves.
#[allow(clippy::string_slice, reason = "used indices come from char_indices")]
fn simple_tokenize_by_delimiters<'a>(
    input: &'a str,
    delimiters: &[char],
) -> Vec<CompletionToken<'a>> {
    let mut tokens = vec![];
    let mut word_start = None;
    let mut word_is_delimiters = false;
    let mut quote_char: Option<char> = None;
    let mut escaped = false;

    for (i, c) in input.char_indices() {
        let mut is_active_delimiter = false;
        if escaped {
            escaped = false;
        } else if let Some(q) = quote_char {
            if c == '\\' && q == '"' {
                // an escape in double-quoted string works as an escape.
                escaped = true;
            } else if c == q {
                // end of quote.
                quote_char = None;
            }
        } else {
            if c == '\\' {
                escaped = true;
            } else if word_start.is_none() && (c == '\'' || c == '\"') {
                // start a new quote.
                quote_char = Some(c);
            } else {
                is_active_delimiter = delimiters.contains(&c);
            }
        }

        if is_active_delimiter {
            // If we were building a regular word and this is a delimiter, then finish it.
            // Similarly, if this is a whitespace delimiter, finish any delimiter sequence.
            if let Some(start) = word_start {
                if !word_is_delimiters || c.is_ascii_whitespace() {
                    tokens.push(CompletionToken {
                        text: &input[start..i],
                        start,
                    });
                    word_start = None;
                    word_is_delimiters = false;
                }

                if !c.is_ascii_whitespace() {
                    if word_start.is_none() {
                        word_start = Some(i);
                        word_is_delimiters = true;
                    }
                }
            } else if !c.is_ascii_whitespace() {
                // Non-whitespace delimiter: start or continue delimiter sequence
                if word_start.is_none() {
                    word_start = Some(i);
                    word_is_delimiters = true;
                }
            }
        } else {
            // Regular character (not a delimiter). Finish any delimiter sequence.
            if word_is_delimiters {
                if let Some(start) = word_start {
                    tokens.push(CompletionToken {
                        text: &input[start..i],
                        start,
                    });
                    word_start = None;
                    word_is_delimiters = false;
                }
            }

            // Start or continue a word
            if word_start.is_none() {
                word_start = Some(i);
            }
        }
    }

    // Add any remaining delimiter sequence
    if let Some(start) = word_start {
        tokens.push(CompletionToken {
            text: &input[start..],
            start,
        });
    }

    tokens
}

fn completion_filter_pattern_matches(
    pattern: &str,
    candidate: &str,
    token_being_completed: &str,
    shell: &Shell<impl extensions::ShellExtensions>,
) -> Result<bool, error::Error> {
    let pattern = replace_unescaped_ampersands(pattern, token_being_completed);

    //
    // TODO(completions): Replace unescaped '&' with the word being completed.
    //

    let pattern = patterns::Pattern::from(pattern.as_ref())
        .set_extended_globbing(shell.options().extended_globbing)
        .set_case_insensitive(shell.options().case_insensitive_pathname_expansion);

    let matches = pattern.exactly_matches(candidate)?;

    Ok(matches)
}

fn replace_unescaped_ampersands<'a>(pattern: &'a str, replacement: &str) -> Cow<'a, str> {
    let mut in_escape = false;
    let mut insertion_points = vec![];

    for (i, c) in pattern.char_indices() {
        if !in_escape && c == '&' {
            insertion_points.push(i);
        }
        in_escape = !in_escape && c == '\\';
    }

    if insertion_points.is_empty() {
        return pattern.into();
    }

    let mut result = pattern.to_owned();
    for i in insertion_points.iter().rev() {
        result.replace_range(*i..=*i, replacement);
    }

    result.into()
}

#[cfg(test)]
mod tests {
    use super::*;
    use pretty_assertions::assert_matches;

    #[test]
    #[allow(clippy::too_many_lines)]
    fn completion_tokenization() {
        assert_matches!(
            simple_tokenize_by_delimiters("one two", &[' ']).as_slice(),
            [
                CompletionToken {
                    text: "one",
                    start: 0,
                },
                CompletionToken {
                    text: "two",
                    start: 4,
                }
            ]
        );

        assert_matches!(
            simple_tokenize_by_delimiters("one \t two", &[' ', '\t']).as_slice(),
            [
                CompletionToken {
                    text: "one",
                    start: 0,
                },
                CompletionToken {
                    text: "two",
                    start: 6,
                }
            ]
        );

        assert_matches!(simple_tokenize_by_delimiters("    ", &[' ']).as_slice(), []);

        assert_matches!(
            simple_tokenize_by_delimiters(":", &[':']).as_slice(),
            [CompletionToken {
                text: ":",
                start: 0,
            }]
        );

        assert_matches!(
            simple_tokenize_by_delimiters("a:::b", &[':', ' ']).as_slice(),
            [
                CompletionToken {
                    text: "a",
                    start: 0,
                },
                CompletionToken {
                    text: ":::",
                    start: 1,
                },
                CompletionToken {
                    text: "b",
                    start: 4,
                }
            ]
        );

        assert_matches!(
            simple_tokenize_by_delimiters("a: : :b", &[':', ' ']).as_slice(),
            [
                CompletionToken {
                    text: "a",
                    start: 0,
                },
                CompletionToken {
                    text: ":",
                    start: 1,
                },
                CompletionToken {
                    text: ":",
                    start: 3,
                },
                CompletionToken {
                    text: ":",
                    start: 5,
                },
                CompletionToken {
                    text: "b",
                    start: 6,
                }
            ]
        );

        assert_matches!(
            simple_tokenize_by_delimiters("one two:three", &[':', ' ']).as_slice(),
            [
                CompletionToken {
                    text: "one",
                    start: 0,
                },
                CompletionToken {
                    text: "two",
                    start: 4,
                },
                CompletionToken {
                    text: ":",
                    start: 7,
                },
                CompletionToken {
                    text: "three",
                    start: 8,
                }
            ]
        );

        assert_matches!(
            simple_tokenize_by_delimiters("one'two", &['\'']).as_slice(),
            [
                CompletionToken {
                    text: "one",
                    start: 0,
                },
                CompletionToken {
                    text: "'",
                    start: 3,
                },
                CompletionToken {
                    text: "two",
                    start: 4,
                },
            ]
        );

        assert_matches!(
            simple_tokenize_by_delimiters("one 'two:three'", &[':', ' ']).as_slice(),
            [
                CompletionToken {
                    text: "one",
                    start: 0,
                },
                CompletionToken {
                    text: "'two:three'",
                    start: 4,
                },
            ]
        );

        assert_matches!(
            simple_tokenize_by_delimiters("one \\'two \"two four\"", &[':', ' ']).as_slice(),
            [
                CompletionToken {
                    text: "one",
                    start: 0,
                },
                CompletionToken {
                    text: "\\'two",
                    start: 4,
                },
                CompletionToken {
                    text: "\"two four\"",
                    start: 10,
                },
            ]
        );
    }
}