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

yash_semantics/
command_search.rs
