yash_env/semantics/command/
search.rs

1// This file is part of yash, an extended POSIX shell.
2// Copyright (C) 2021 WATANABE Yuki
3//
4// This program is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8//
9// This program is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13//
14// You should have received a copy of the GNU General Public License
15// along with this program.  If not, see <https://www.gnu.org/licenses/>.
16
17//! Command search
18//!
19//! The [command search], implemented by [`search`], is part of the execution of
20//! a [simple command]. It determines a command target that is to be invoked. A
21//! [target](Target) can be a built-in utility, function, or external utility.
22//!
23//! If the command name contains a slash, the target is always an external
24//! utility. Otherwise, the shell searches the following candidates for the
25//! target (in the order of priority):
26//!
27//! 1. [Special] built-ins
28//! 1. Functions
29//! 1. Other built-ins
30//! 1. External utilities
31//!
32//! For a [substitutive](Substitutive) built-in or external utility to be chosen
33//! as a target, a corresponding executable file must be present in a directory
34//! specified in the `PATH` variable.
35//!
36//! [command search]: https://pubs.opengroup.org/onlinepubs/9799919799/utilities/V3_chap02.html#tag_19_09_01_04
37//! [simple command]: https://pubs.opengroup.org/onlinepubs/9799919799/utilities/V3_chap02.html#tag_19_09_01
38
39use crate::Env;
40use crate::System;
41use crate::builtin::Builtin;
42use crate::builtin::Type::{Special, Substitutive};
43use crate::function::Function;
44use crate::path::PathBuf;
45use crate::variable::Expansion;
46use crate::variable::PATH;
47use std::ffi::CStr;
48use std::ffi::CString;
49use std::rc::Rc;
50
51/// Target of a simple command execution
52///
53/// This is the result of the [command search](search).
54///
55/// # Notes on equality
56///
57/// Although this type implements `PartialEq`, comparison between instances of
58/// this type may not always yield predictable results due to the presence of
59/// function pointers in [`Builtin`]. As a result, it is recommended to avoid
60/// relying on equality comparisons for values of this type. See
61/// <https://doc.rust-lang.org/std/ptr/fn.fn_addr_eq.html> for the
62/// characteristics of function pointer comparisons.
63#[derive(Clone, Debug, Eq, PartialEq)]
64pub enum Target {
65    /// Built-in utility
66    Builtin {
67        /// Definition of the built-in
68        builtin: Builtin,
69
70        /// Path to the external utility that is shadowed by the substitutive
71        /// built-in
72        ///
73        /// This value is only used for substitutive built-ins. For other types
74        /// of built-ins, this value is always empty.
75        ///
76        /// The path may not necessarily be absolute. If the `PATH` variable
77        /// contains a relative directory name and the external utility is found
78        /// in that directory, the path will be relative.
79        path: CString,
80    },
81
82    /// Function
83    Function(Rc<Function>),
84
85    /// External utility
86    External {
87        /// Path to the external utility
88        ///
89        /// The path may not necessarily be absolute. If the `PATH` variable
90        /// contains a relative directory name and the external utility is found
91        /// in that directory, the path will be relative.
92        ///
93        /// The path may not name an existing executable file, either. If the
94        /// command name contains a slash, the name is immediately regarded as a
95        /// path to an external utility, regardless of whether the named
96        /// external utility actually exists.
97        path: CString,
98    },
99}
100
101impl From<Rc<Function>> for Target {
102    #[inline]
103    fn from(function: Rc<Function>) -> Target {
104        Target::Function(function)
105    }
106}
107
108impl From<Function> for Target {
109    #[inline]
110    fn from(function: Function) -> Target {
111        Target::Function(function.into())
112    }
113}
114
115// impl From<CString> for Target
116// not implemented because of ambiguity between substitutive built-ins and
117// external utilities
118
119/// Collection of data used in [classifying](classify) command names
120pub trait ClassifyEnv {
121    /// Retrieves the built-in by name.
122    #[must_use]
123    fn builtin(&self, name: &str) -> Option<Builtin>;
124
125    /// Retrieves the function by name.
126    #[must_use]
127    fn function(&self, name: &str) -> Option<&Rc<Function>>;
128}
129
130/// Part of the shell execution environment command path search depends on
131pub trait PathEnv {
132    /// Accesses the `$PATH` variable in the environment.
133    ///
134    /// This function returns an `Expansion` rather than a reference to a
135    /// variable value because the path may be dynamically computed in the
136    /// function.
137    #[must_use]
138    fn path(&self) -> Expansion<'_>;
139
140    /// Whether there is an executable file at the specified path.
141    #[must_use]
142    fn is_executable_file(&self, path: &CStr) -> bool;
143    // TODO Cache the results of external utility search
144}
145
146impl PathEnv for Env {
147    /// Returns the value of the `$PATH` variable.
148    ///
149    /// This function assumes that the `$PATH` variable has no quirks. If the
150    /// variable has a quirk, the function panics.
151    fn path(&self) -> Expansion<'_> {
152        self.variables
153            .get(PATH)
154            .and_then(|var| {
155                assert_eq!(var.quirk, None, "PATH does not support quirks");
156                var.value.as_ref()
157            })
158            .into()
159    }
160
161    fn is_executable_file(&self, path: &CStr) -> bool {
162        self.system.is_executable_file(path)
163    }
164}
165
166impl ClassifyEnv for Env {
167    fn builtin(&self, name: &str) -> Option<Builtin> {
168        self.builtins.get(name).copied()
169    }
170
171    #[inline]
172    fn function(&self, name: &str) -> Option<&Rc<Function>> {
173        self.functions.get(name)
174    }
175}
176
177/// Performs command search.
178///
179/// This function effectively combines the [`classify`] and [`search_path`]
180/// functions into a single operation performing full command search.
181///
182/// See [`search_path`] for why this function requires a mutable reference to
183/// the environment.
184///
185/// See the [module documentation](self) for details of the command search
186/// process.
187#[must_use]
188pub fn search<E: ClassifyEnv + PathEnv>(env: &mut E, name: &str) -> Option<Target> {
189    let mut target = classify(env, name);
190
191    'fill_path: {
192        let path = match &mut target {
193            Target::Builtin { builtin, path } if builtin.r#type == Substitutive => {
194                // Must verify the external counterpart exists.
195                path
196            }
197
198            Target::External { path } => {
199                if name.contains('/') {
200                    // Just access the given path.
201                    *path = CString::new(name).ok()?;
202                    break 'fill_path;
203                } else {
204                    // Need to actually find it in PATH.
205                    path
206                }
207            }
208
209            Target::Builtin { .. } | Target::Function(_) => {
210                // Nothing to do.
211                break 'fill_path;
212            }
213        };
214
215        if let Some(real_path) = search_path(env, name) {
216            *path = real_path;
217        } else {
218            return None;
219        }
220    }
221
222    Some(target)
223}
224
225/// Determines the type of command target without performing a full search.
226///
227/// This function is a simplified version of [`search`] that only classifies the
228/// command name into one of the target types. It does not return the actual
229/// target path, so it is more efficient than `search` if the caller only needs
230/// to know the type of target. However, since the function does not search for
231/// external utilities, it cannot determine whether a substitutive built-in or
232/// an external utility is the actual target. This function always assumes that
233/// searching for an external utility would succeed and returns a target with
234/// an empty path in such cases.
235#[must_use]
236pub fn classify<E: ClassifyEnv>(env: &E, name: &str) -> Target {
237    if name.contains('/') {
238        return Target::External {
239            path: CString::default(),
240        };
241    }
242
243    let builtin = env.builtin(name);
244    if let Some(builtin) = builtin {
245        if builtin.r#type == Special {
246            let path = CString::default();
247            return Target::Builtin { builtin, path };
248        }
249    }
250
251    if let Some(function) = env.function(name) {
252        return Rc::clone(function).into();
253    }
254
255    if let Some(builtin) = builtin {
256        let path = CString::default();
257        return Target::Builtin { builtin, path };
258    }
259
260    Target::External {
261        path: CString::default(),
262    }
263}
264
265/// Searches the `$PATH` for an executable file.
266///
267/// Returns the path to the executable if found. Note that the returned path may
268/// not be absolute if the `$PATH` contains a relative path.
269///
270/// This function requires a mutable reference to the environment because it may
271/// need to update a cache of the results of external utility search (TODO:
272/// which is not yet implemented). The function does not otherwise modify the
273/// environment.
274#[must_use]
275pub fn search_path<E: PathEnv>(env: &mut E, name: &str) -> Option<CString> {
276    env.path()
277        .split()
278        .filter_map(|dir| {
279            let candidate = PathBuf::from_iter([dir, name])
280                .into_unix_string()
281                .into_vec();
282            CString::new(candidate).ok()
283        })
284        .find(|path| env.is_executable_file(path))
285}
286
287#[allow(clippy::field_reassign_with_default)]
288#[cfg(test)]
289mod tests {
290    use super::*;
291    use crate::builtin::Type::{Elective, Extension, Mandatory};
292    use crate::function::{FunctionBody, FunctionBodyObject, FunctionSet};
293    use crate::source::Location;
294    use crate::variable::Value;
295    use assert_matches::assert_matches;
296    use std::collections::HashMap;
297    use std::collections::HashSet;
298
299    #[derive(Default)]
300    struct DummyEnv {
301        builtins: HashMap<&'static str, Builtin>,
302        functions: FunctionSet,
303        path: Expansion<'static>,
304        executables: HashSet<String>,
305    }
306
307    impl PathEnv for DummyEnv {
308        fn path(&self) -> Expansion<'_> {
309            self.path.as_ref()
310        }
311        fn is_executable_file(&self, path: &CStr) -> bool {
312            if let Ok(path) = path.to_str() {
313                self.executables.contains(path)
314            } else {
315                false
316            }
317        }
318    }
319
320    impl ClassifyEnv for DummyEnv {
321        fn builtin(&self, name: &str) -> Option<Builtin> {
322            self.builtins.get(name).copied()
323        }
324        fn function(&self, name: &str) -> Option<&Rc<Function>> {
325            self.functions.get(name)
326        }
327    }
328
329    #[derive(Clone, Debug)]
330    struct FunctionBodyStub;
331
332    impl std::fmt::Display for FunctionBodyStub {
333        fn fmt(&self, _: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
334            unreachable!()
335        }
336    }
337    impl FunctionBody for FunctionBodyStub {
338        async fn execute(&self, _: &mut Env) -> crate::semantics::Result {
339            unreachable!()
340        }
341    }
342
343    fn function_body_stub() -> Rc<dyn FunctionBodyObject> {
344        Rc::new(FunctionBodyStub)
345    }
346
347    #[test]
348    fn nothing_is_found_in_empty_env() {
349        let mut env = DummyEnv::default();
350        let target = search(&mut env, "foo");
351        assert!(target.is_none(), "target = {target:?}");
352    }
353
354    #[test]
355    fn nothing_is_found_with_name_unmatched() {
356        let mut env = DummyEnv::default();
357        env.builtins
358            .insert("foo", Builtin::new(Special, |_, _| unreachable!()));
359        let function = Function::new("foo", function_body_stub(), Location::dummy(""));
360        env.functions.define(function).unwrap();
361
362        let target = search(&mut env, "bar");
363        assert!(target.is_none(), "target = {target:?}");
364    }
365
366    #[test]
367    fn classify_defaults_to_external() {
368        // In an empty environment, any name is not a built-in or function, so it
369        // is classified as an external utility.
370        let env = DummyEnv::default();
371        let target = classify(&env, "foo");
372        assert_eq!(
373            target,
374            Target::External {
375                path: CString::default()
376            }
377        );
378    }
379
380    #[test]
381    fn special_builtin_is_found() {
382        let mut env = DummyEnv::default();
383        let builtin = Builtin::new(Special, |_, _| unreachable!());
384        env.builtins.insert("foo", builtin);
385
386        assert_matches!(
387            search(&mut env, "foo"),
388            Some(Target::Builtin { builtin: result, path }) => {
389                assert_eq!(result.r#type, builtin.r#type);
390                assert_eq!(*path, *c"");
391            }
392        );
393        assert_matches!(
394            classify(&env, "foo"),
395            Target::Builtin { builtin: result, path } => {
396                assert_eq!(result.r#type, builtin.r#type);
397                assert_eq!(*path, *c"");
398            }
399        );
400    }
401
402    #[test]
403    fn function_is_found_if_not_hidden_by_special_builtin() {
404        let mut env = DummyEnv::default();
405        let function = Rc::new(Function::new(
406            "foo",
407            function_body_stub(),
408            Location::dummy("location"),
409        ));
410        env.functions.define(function.clone()).unwrap();
411
412        assert_matches!(search(&mut env, "foo"), Some(Target::Function(result)) => {
413            assert_eq!(result, function);
414        });
415        assert_matches!(classify(&env, "foo"), Target::Function(result) => {
416            assert_eq!(result, function);
417        });
418    }
419
420    #[test]
421    fn special_builtin_takes_priority_over_function() {
422        let mut env = DummyEnv::default();
423        let builtin = Builtin::new(Special, |_, _| unreachable!());
424        env.builtins.insert("foo", builtin);
425        let function = Function::new("foo", function_body_stub(), Location::dummy("location"));
426        env.functions.define(function).unwrap();
427
428        assert_matches!(
429            search(&mut env, "foo"),
430            Some(Target::Builtin { builtin: result, path }) => {
431                assert_eq!(result.r#type, builtin.r#type);
432                assert_eq!(*path, *c"");
433            }
434        );
435        assert_matches!(
436            classify(&env, "foo"),
437            Target::Builtin { builtin: result, path } => {
438                assert_eq!(result.r#type, builtin.r#type);
439                assert_eq!(*path, *c"");
440            }
441        );
442    }
443
444    #[test]
445    fn mandatory_builtin_is_found_if_not_hidden_by_function() {
446        let mut env = DummyEnv::default();
447        let builtin = Builtin::new(Mandatory, |_, _| unreachable!());
448        env.builtins.insert("foo", builtin);
449
450        assert_matches!(
451            search(&mut env, "foo"),
452            Some(Target::Builtin { builtin: result, path }) => {
453                assert_eq!(result.r#type, builtin.r#type);
454                assert_eq!(*path, *c"");
455            }
456        );
457        assert_matches!(
458            classify(&env, "foo"),
459            Target::Builtin { builtin: result, path } => {
460                assert_eq!(result.r#type, builtin.r#type);
461                assert_eq!(*path, *c"");
462            }
463        );
464    }
465
466    #[test]
467    fn elective_builtin_is_found_if_not_hidden_by_function() {
468        let mut env = DummyEnv::default();
469        let builtin = Builtin::new(Elective, |_, _| unreachable!());
470        env.builtins.insert("foo", builtin);
471
472        assert_matches!(
473            search(&mut env, "foo"),
474            Some(Target::Builtin { builtin: result, path }) => {
475                assert_eq!(result.r#type, builtin.r#type);
476                assert_eq!(*path, *c"");
477            }
478        );
479        assert_matches!(
480            classify(&env, "foo"),
481            Target::Builtin { builtin: result, path } => {
482                assert_eq!(result.r#type, builtin.r#type);
483                assert_eq!(*path, *c"");
484            }
485        );
486    }
487
488    #[test]
489    fn extension_builtin_is_found_if_not_hidden_by_function_or_option() {
490        let mut env = DummyEnv::default();
491        let builtin = Builtin::new(Extension, |_, _| unreachable!());
492        env.builtins.insert("foo", builtin);
493
494        assert_matches!(
495            search(&mut env, "foo"),
496            Some(Target::Builtin { builtin: result, path }) => {
497                assert_eq!(result.r#type, builtin.r#type);
498                assert_eq!(*path, *c"");
499            }
500        );
501        assert_matches!(
502            classify(&env, "foo"),
503            Target::Builtin { builtin: result, path } => {
504                assert_eq!(result.r#type, builtin.r#type);
505                assert_eq!(*path, *c"");
506            }
507        );
508    }
509
510    #[test]
511    fn function_takes_priority_over_mandatory_builtin() {
512        let mut env = DummyEnv::default();
513        env.builtins
514            .insert("foo", Builtin::new(Mandatory, |_, _| unreachable!()));
515
516        let function = Rc::new(Function::new(
517            "foo",
518            function_body_stub(),
519            Location::dummy("location"),
520        ));
521        env.functions.define(function.clone()).unwrap();
522
523        assert_matches!(search(&mut env, "foo"), Some(Target::Function(result)) => {
524            assert_eq!(result, function);
525        });
526        assert_matches!(classify(&env, "foo"), Target::Function(result) => {
527            assert_eq!(result, function);
528        });
529    }
530
531    #[test]
532    fn function_takes_priority_over_elective_builtin() {
533        let mut env = DummyEnv::default();
534        env.builtins
535            .insert("foo", Builtin::new(Elective, |_, _| unreachable!()));
536
537        let function = Rc::new(Function::new(
538            "foo",
539            function_body_stub(),
540            Location::dummy("location"),
541        ));
542        env.functions.define(function.clone()).unwrap();
543
544        assert_matches!(search(&mut env, "foo"), Some(Target::Function(result)) => {
545            assert_eq!(result, function);
546        });
547        assert_matches!(classify(&env, "foo"), Target::Function(result) => {
548            assert_eq!(result, function);
549        });
550    }
551
552    #[test]
553    fn function_takes_priority_over_extension_builtin() {
554        let mut env = DummyEnv::default();
555        env.builtins
556            .insert("foo", Builtin::new(Extension, |_, _| unreachable!()));
557
558        let function = Rc::new(Function::new(
559            "foo",
560            function_body_stub(),
561            Location::dummy("location"),
562        ));
563        env.functions.define(function.clone()).unwrap();
564
565        assert_matches!(search(&mut env, "foo"), Some(Target::Function(result)) => {
566            assert_eq!(result, function);
567        });
568        assert_matches!(classify(&env, "foo"), Target::Function(result) => {
569            assert_eq!(result, function);
570        });
571    }
572
573    #[test]
574    fn substitutive_builtin_is_found_if_external_executable_exists() {
575        let mut env = DummyEnv::default();
576        let builtin = Builtin::new(Substitutive, |_, _| unreachable!());
577        env.builtins.insert("foo", builtin);
578        env.path = Expansion::from("/bin");
579        env.executables.insert("/bin/foo".to_string());
580
581        assert_matches!(
582            search(&mut env, "foo"),
583            Some(Target::Builtin { builtin: result, path }) => {
584                assert_eq!(result.r#type, builtin.r#type);
585                assert_eq!(*path, *c"/bin/foo");
586            }
587        );
588        assert_matches!(
589            classify(&env, "foo"),
590            Target::Builtin { builtin: result, path } => {
591                assert_eq!(result.r#type, builtin.r#type);
592                assert_eq!(*path, *c"");
593            }
594        );
595    }
596
597    #[test]
598    fn substitutive_builtin_is_not_found_without_external_executable() {
599        let mut env = DummyEnv::default();
600        let builtin = Builtin::new(Substitutive, |_, _| unreachable!());
601        env.builtins.insert("foo", builtin);
602
603        let target = search(&mut env, "foo");
604        assert!(target.is_none(), "target = {target:?}");
605    }
606
607    #[test]
608    fn substitutive_builtin_is_classified_even_without_external_executable() {
609        let mut env = DummyEnv::default();
610        let builtin = Builtin::new(Substitutive, |_, _| unreachable!());
611        env.builtins.insert("foo", builtin);
612
613        assert_matches!(
614            classify(&env, "foo"),
615            Target::Builtin { builtin: result, path } => {
616                assert_eq!(result.r#type, builtin.r#type);
617                assert_eq!(*path, *c"");
618            }
619        );
620    }
621
622    #[test]
623    fn function_takes_priority_over_substitutive_builtin() {
624        let mut env = DummyEnv::default();
625        let builtin = Builtin::new(Substitutive, |_, _| unreachable!());
626        env.builtins.insert("foo", builtin);
627        env.path = Expansion::from("/bin");
628        env.executables.insert("/bin/foo".to_string());
629
630        let function = Rc::new(Function::new(
631            "foo",
632            function_body_stub(),
633            Location::dummy("location"),
634        ));
635        env.functions.define(function.clone()).unwrap();
636
637        assert_matches!(search(&mut env, "foo"), Some(Target::Function(result)) => {
638            assert_eq!(result, function);
639        });
640        assert_matches!(classify(&env, "foo"), Target::Function(result) => {
641            assert_eq!(result, function);
642        });
643    }
644
645    #[test]
646    fn external_utility_is_found_if_external_executable_exists() {
647        let mut env = DummyEnv::default();
648        env.path = Expansion::from("/bin");
649        env.executables.insert("/bin/foo".to_string());
650
651        assert_matches!(search(&mut env, "foo"), Some(Target::External { path }) => {
652            assert_eq!(*path, *c"/bin/foo");
653        });
654        assert_matches!(classify(&env, "foo"), Target::External { path } => {
655            assert_eq!(*path, *c"");
656        });
657    }
658
659    #[test]
660    fn returns_external_utility_if_name_contains_slash() {
661        // In this case, the external utility file does not have to exist.
662        let mut env = DummyEnv::default();
663        // The special built-in should be ignored because the command name
664        // contains a slash.
665        let builtin = Builtin::new(Special, |_, _| unreachable!());
666        env.builtins.insert("bar/baz", builtin);
667
668        assert_matches!(search(&mut env, "bar/baz"), Some(Target::External { path }) => {
669            assert_eq!(*path, *c"bar/baz");
670        });
671        assert_matches!(classify(&env, "bar/baz"), Target::External { path } => {
672            assert_eq!(*path, *c"");
673        });
674    }
675
676    #[test]
677    fn external_target_is_first_executable_found_in_path_scalar() {
678        let mut env = DummyEnv::default();
679        env.path = Expansion::from("/usr/local/bin:/usr/bin:/bin");
680        env.executables.insert("/usr/bin/foo".to_string());
681        env.executables.insert("/bin/foo".to_string());
682
683        assert_matches!(search(&mut env, "foo"), Some(Target::External { path }) => {
684            assert_eq!(*path, *c"/usr/bin/foo");
685        });
686
687        env.executables.insert("/usr/local/bin/foo".to_string());
688
689        assert_matches!(search(&mut env, "foo"), Some(Target::External { path }) => {
690            assert_eq!(*path, *c"/usr/local/bin/foo");
691        });
692    }
693
694    #[test]
695    fn external_target_is_first_executable_found_in_path_array() {
696        let mut env = DummyEnv::default();
697        env.path = Expansion::from(Value::array(["/usr/local/bin", "/usr/bin", "/bin"]));
698        env.executables.insert("/usr/bin/foo".to_string());
699        env.executables.insert("/bin/foo".to_string());
700
701        assert_matches!(search(&mut env, "foo"), Some(Target::External { path }) => {
702            assert_eq!(*path, *c"/usr/bin/foo");
703        });
704
705        env.executables.insert("/usr/local/bin/foo".to_string());
706
707        assert_matches!(search(&mut env, "foo"), Some(Target::External { path }) => {
708            assert_eq!(*path, *c"/usr/local/bin/foo");
709        });
710    }
711
712    #[test]
713    fn empty_string_in_path_names_current_directory() {
714        let mut env = DummyEnv::default();
715        env.path = Expansion::from("/x::/y");
716        env.executables.insert("foo".to_string());
717
718        assert_matches!(search(&mut env, "foo"), Some(Target::External { path }) => {
719            assert_eq!(*path, *c"foo");
720        });
721    }
722}
yash_env/semantics/command/search.rs

yash_env/semantics/command/
search.rs
