Skip to main content

milo_guards_code/
lib.rs

1//! Reads code of another language and says what it is certain to do:
2//! [`read`] and [`understand`].
3//!
4//! A shell line can hand an interpreter code (`python3 -c`, `node -e`), and
5//! an agent can write a script or run a snippet directly. The code does what
6//! the shell commands that do the same would do, so what matters to a guard
7//! is which files it deletes, writes, reads and moves, and what it runs. This
8//! crate reads Python and JavaScript (Node, Bun and Deno) with their own
9//! tree-sitter grammars and answers two questions of a piece of code:
10//!
11//! - **What is it certain to do?** [`read`] gives the [`Act`]s the code
12//!   makes, in the order it makes them: a delete, a write, a read, a move, a
13//!   program started, an environment changed, each with the paths it names.
14//!   What the reader cannot follow comes out as an [`Act::Unread`] and the
15//!   other acts of code it does not run as written (a call it has no row
16//!   for, code loaded from the network), never left out.
17//! - **Does it understand the code?** [`understand`] holds the code to a
18//!   strict allow-list: a few plain statements whose every call, name and
19//!   import is on a short list that only computes. Code outside it is
20//!   [`Understanding::NotUnderstood`], and a caller must not take "no acts"
21//!   for "does nothing" for such code. The acts are kept whatever the code
22//!   looks like; that it is understood is what makes finding none safe.
23//!
24//! The reader judges nothing. Whether a delete of a path is risky is the
25//! caller's, which turns an act into what it already judges: a delete is
26//! `rm -rf PATH`, a write a write to that path, a command line a script a
27//! shell reads. It does no I/O and reads no environment: a path is the text
28//! the code gives, never what is on disk, and the same code gives the same
29//! answer on every machine. Code it cannot read is not understood, never
30//! understood by default, and nothing it is given makes it panic or run past
31//! its limits (see [`MAX_DEPTH`], [`MAX_TREE_DEPTH`] and [`MAX_LEN`]).
32//!
33//! ```
34//! use milo_guards_code::{read, understand, Act, Arg, Language, Understanding};
35//!
36//! // A snippet that computes is understood, and does nothing to a file.
37//! let code = "print(1 + 1)";
38//! assert!(read(Language::Python, code).acts.is_empty());
39//! assert_eq!(
40//!     understand(Language::Python, code),
41//!     Understanding::Understood { imports: true },
42//! );
43//!
44//! // A delete is an act with the path it names, kept whatever the code is.
45//! let code = "import shutil\nshutil.rmtree('/home/me')";
46//! let reading = read(Language::Python, code);
47//! assert!(matches!(&reading.acts[..], [Act::Remove(Arg::Known(path))] if path == "/home/me"));
48//! assert_eq!(understand(Language::Python, code), Understanding::NotUnderstood);
49//!
50//! // A name only known when the code runs is an argument it does not know.
51//! let reading = read(Language::JavaScript, "require('fs').rmSync(process.argv[1])");
52//! assert!(matches!(&reading.acts[..], [Act::Remove(Arg::Unknown(_))]));
53//! ```
54
55use std::collections::{HashMap, HashSet};
56
57use tree_sitter::Node;
58
59mod javascript;
60mod python;
61mod strict;
62mod unit;
63
64pub use unit::{Arg, MAX_DEPTH, MAX_LEN, MAX_TREE_DEPTH};
65
66/// The languages whose code is read.
67#[derive(Debug, Clone, Copy, PartialEq, Eq)]
68pub enum Language {
69    /// Python, as the reference interpreter reads it.
70    Python,
71    /// JavaScript, as Node, Bun and Deno read it.
72    JavaScript,
73}
74
75/// What reading code found, in the order the code gives it.
76#[derive(Debug, Clone)]
77pub enum Act {
78    /// `rm -rf PATH`: a file or a whole tree goes.
79    Remove(Arg),
80    /// Writes into a file, makes one, or truncates it.
81    Write(Arg),
82    /// Reads a file (`open(path)`, `readFileSync(path)`, the source of a
83    /// copy): judged as `cat PATH` is, so a key it names is a read of one.
84    Read(Arg),
85    /// Reads a folder and everything under it (`TarFile.add`, the folder
86    /// `shutil.make_archive` packs): judged as `grep -r` is, so a folder that
87    /// holds a key, or the home directory, is a read of one.
88    ReadTree(Arg),
89    /// A path handed to a call the reader does not know: it may read it,
90    /// write it or delete it, so the caller cannot take the code for
91    /// understood, unless the path is a key, which is judged as `cat PATH` is.
92    Opaque(Arg),
93    /// `mv FROM TO`.
94    Move {
95        /// What moves.
96        from: Arg,
97        /// Where it goes.
98        to: Arg,
99    },
100    /// `ln TARGET LINK`.
101    Link {
102        /// What the link points to.
103        target: Arg,
104        /// The link itself.
105        link: Arg,
106    },
107    /// `chmod MODE PATH`; `mode` is in octal where the code gives a number.
108    Chmod {
109        /// The path whose permissions change.
110        path: Arg,
111        /// The mode it is given.
112        mode: Arg,
113    },
114    /// `chown OWNER PATH`.
115    Chown(Arg),
116    /// The process moves to another directory: the paths after it are read
117    /// from there.
118    Chdir(Arg),
119    /// What a call that starts a program does, run from the directory its
120    /// `cwd` option names: judged as if the code had moved there first, and
121    /// back where it was after.
122    In(Arg, Vec<Act>),
123    /// A command line a shell runs: `os.system`, `child_process.exec`.
124    Script(Arg),
125    /// A program and its arguments, run without a shell: the program first.
126    Program(Vec<Arg>),
127    /// Code the code runs from a literal (`exec("…")`), to be read in its own
128    /// language.
129    Code(Language, String),
130    /// Something the reader cannot follow, as a short piece of the code.
131    Unread(String),
132    /// Code loaded from the network (`import … from 'https://…'`): it is
133    /// downloaded and run, and not read.
134    Downloaded(String),
135    /// Code loaded from a file outside the workspace (`require('/tmp/x.js')`,
136    /// `fork('../x.js')`), which is not the workspace's own and is not read.
137    Loads(String),
138    /// A write to the environment of the process itself (`os.environ[...] =`,
139    /// `os.putenv`, `process.env.X =`): a program the code starts after it
140    /// is given the variable.
141    Environment,
142    /// What a call that starts a program does, given an environment the code
143    /// sets: it may hold a variable that loads code (`PYTHONPATH`,
144    /// `NODE_OPTIONS`), so the caller cannot take the program for the one it
145    /// reads.
146    Started(Vec<Act>),
147}
148
149/// Variables, by name, that make a program load code that is not its own or
150/// run other than it says.
151const LOADING: [&str; 17] = [
152    "PYTHONPATH",
153    "NODE_OPTIONS",
154    "NODE_PATH",
155    "LD_PRELOAD",
156    "LD_LIBRARY_PATH",
157    "DYLD_INSERT_LIBRARIES",
158    "DYLD_LIBRARY_PATH",
159    "BASH_ENV",
160    "ENV",
161    "PATH",
162    "PYTHONSTARTUP",
163    "SHELLOPTS",
164    "PROMPT_COMMAND",
165    "PS4",
166    "IFS",
167    "CDPATH",
168    "HOME",
169];
170
171/// Whether the variable `name` is one a caller judges: one of [`LOADING`],
172/// or one of a family that loads code (`LD_*`, `DYLD_*`, `PYTHON*`, `NODE_*`,
173/// `BASH_FUNC_*`, `GIT_*`).
174pub(crate) fn judged_variable(name: &str) -> bool {
175    let name = name.to_ascii_uppercase();
176    LOADING.contains(&name.as_str())
177        || ["LD_", "DYLD_", "PYTHON", "NODE_", "BASH_FUNC_", "GIT_"]
178            .iter()
179            .any(|prefix| name.starts_with(prefix))
180}
181
182/// Mark the programs `acts` start as given an environment, when the code
183/// writes to its own environment anywhere (a function may be called after
184/// the write, a loop's second pass follows the first).
185pub(crate) fn mark_environment(acts: Vec<Act>) -> Vec<Act> {
186    fn writes(act: &Act) -> bool {
187        match act {
188            Act::Environment => true,
189            Act::In(_, acts) | Act::Started(acts) => acts.iter().any(writes),
190            _ => false,
191        }
192    }
193    fn mark(act: Act) -> Act {
194        match act {
195            Act::Program(_) | Act::Script(_) => Act::Started(vec![act]),
196            Act::In(dir, acts) => Act::In(dir, acts.into_iter().map(mark).collect()),
197            other => other,
198        }
199    }
200    if acts.iter().any(writes) {
201        acts.into_iter().map(mark).collect()
202    } else {
203        acts
204    }
205}
206
207/// Everything one piece of code does.
208#[derive(Debug, Default)]
209pub struct Reading {
210    /// What the code does, in the order it does it.
211    pub acts: Vec<Act>,
212    /// Whether the code nests too deeply to read in full.
213    pub deep: bool,
214}
215
216impl Reading {
217    fn unread(&mut self, code: &str) {
218        self.acts.push(Act::Unread(shorten(code)));
219    }
220}
221
222/// Read `code` in `language`: what it does to files and what it runs.
223///
224/// What the reader finds is kept wherever the code comes from and however it
225/// is written; that it found nothing says nothing of whether the code does
226/// nothing (see [`understand`]).
227pub fn read(language: Language, code: &str) -> Reading {
228    let mut reading = match language {
229        Language::Python => python::read(code),
230        Language::JavaScript => javascript::read(code),
231    };
232    reading.acts = mark_environment(std::mem::take(&mut reading.acts));
233    reading
234}
235
236/// Whether the code is read whole (see [`understand`]).
237#[derive(Debug, Clone, Copy, PartialEq, Eq)]
238pub enum Understanding {
239    /// Something in the code is outside the allow-list: it does not parse,
240    /// holds no statement, or has a function, a loop, a call or an import the
241    /// reader has no row for.
242    NotUnderstood,
243    /// The code is a few plain statements that compute, and its only acts are
244    /// the ones [`read`] gives.
245    Understood {
246        /// Whether the code may load a module, which looks in the folder the
247        /// code runs in first: all Python code does, with or without an
248        /// `import` (an uncaught exception imports `traceback`), so it is
249        /// understood only when that folder is the caller's own. JavaScript
250        /// that is understood has no import at all.
251        imports: bool,
252    },
253}
254
255/// Whether `code` is read whole: nothing in it is outside the allow-list.
256///
257/// The code is held to a strict subset, for Python and JavaScript alike:
258///
259/// - it parses, and holds at least one statement;
260/// - its statements are expression statements, assignments to a plain name
261///   and `if`/`else`, so the code runs straight through;
262/// - its calls are on a short list that only computes (`print`, `len`, `str`,
263///   `time.time`, `console.log`, `Math.max`, the methods of a string or a
264///   list), or `open` in Python, which the reader judges by its path and
265///   mode;
266/// - its imports are the modules built into the interpreter binary (`sys`,
267///   `errno`, `itertools`, `time`) in Python 3, and `sys` and `errno` alone
268///   in Python 2 (see [`understand_python2`]), which no file in the folder
269///   the code runs in can stand in for, and it has no import, `require` or
270///   `eval` in JavaScript;
271/// - it names nothing that is not a name it set, a call on the list or a
272///   module on the list that it imported, and sets none of those;
273/// - it reaches into nothing: no attribute that starts with an underscore,
274///   and in JavaScript no member other than `length` and the methods on the
275///   list.
276///
277/// The list is an allow-list of what the grammar may hold, never a list of
278/// what is known to be dangerous: code with anything else in it is
279/// [`Understanding::NotUnderstood`] because the reader has no row for what it
280/// does, whatever [`read`] found in it.
281pub fn understand(language: Language, code: &str) -> Understanding {
282    match strict::reads_whole(language, code) {
283        None => Understanding::NotUnderstood,
284        Some(imports) => Understanding::Understood { imports },
285    }
286}
287
288/// Whether `code` that Python 2 runs is read whole: the same subset as
289/// [`understand`] for [`Language::Python`], but with only `sys` and `errno` to
290/// import. `time` and `itertools` are shared files of Python 2's
291/// `lib-dynload`, which the import path reaches after the folder the code runs
292/// in, and `builtins` is no built-in module there (it is `__builtin__`), so a
293/// file of that name in the folder would run.
294pub fn understand_python2(code: &str) -> Understanding {
295    match strict::reads_whole_python2(code) {
296        None => Understanding::NotUnderstood,
297        Some(imports) => Understanding::Understood { imports },
298    }
299}
300
301/// Whether Python, when it reads `code` as bytes (from its input, or the
302/// bytes literal given to `exec`, `eval` or `compile`), honours a coding
303/// declaration that decodes it to other text than the reader sees: it
304/// always reads the text as UTF-8. UTF-8 itself, and the ASCII-compatible
305/// encodings for a text that is all ASCII, read the same. Such code is not
306/// read: a caller that hands Python code its input does not take it for
307/// understood.
308pub fn declares_other_encoding(code: &str) -> bool {
309    python::declares_other_encoding(code)
310}
311
312/// A node above the one a [`walk`] is at, and the field it fills in its own
313/// parent.
314#[derive(Clone, Copy)]
315pub(crate) struct Ancestor<'t> {
316    pub(crate) node: Node<'t>,
317    pub(crate) field: Option<&'static str>,
318}
319
320/// Visit every node under `root`, in the order the code reads, without
321/// recursion so a deep tree cannot overflow the stack. `visit` is given the
322/// node, the field it fills in its parent, and the nodes above it (the root
323/// first), so no reader asks the tree for a node's parent, which walks it from
324/// the top; it returns whether to go on.
325pub(crate) fn walk<'t>(
326    root: Node<'t>,
327    mut visit: impl FnMut(Node<'t>, Option<&'static str>, &[Ancestor<'t>]) -> bool,
328) {
329    let mut cursor = root.walk();
330    let mut above: Vec<Ancestor<'t>> = Vec::new();
331    loop {
332        let node = cursor.node();
333        let field = cursor.field_name();
334        if !visit(node, field, &above) {
335            return;
336        }
337        if cursor.goto_first_child() {
338            above.push(Ancestor { node, field });
339            continue;
340        }
341        loop {
342            if cursor.goto_next_sibling() {
343                break;
344            }
345            if !cursor.goto_parent() {
346                return;
347            }
348            above.pop();
349        }
350    }
351}
352
353/// A piece of code short enough to show in a prompt: its first line, cut.
354fn shorten(code: &str) -> String {
355    let line = code.lines().next().unwrap_or_default().trim();
356    let mut short: String = line.chars().take(60).collect();
357    if short.len() < line.len() {
358        short.push('…');
359    }
360    short
361}
362
363/// A path as a caller's rules take it: its text when the code gives it,
364/// and what it is made of when only known when it runs.
365fn path(value: Option<String>, code: &str) -> Arg {
366    match value {
367        Some(text) => Arg::Known(text),
368        None => Arg::Unknown(shorten(code)),
369    }
370}
371
372/// A string the code gives, as far as the reader knows it: the text up to
373/// the first part only known when it runs, and whether that was all of it.
374/// A concatenation, a join and a template keep the start they know
375/// (`'/home/me/.ssh/' + name`), as a shell word with `$name` in it does.
376#[derive(Debug, Default)]
377pub(crate) struct Parts {
378    pub(crate) text: String,
379    pub(crate) whole: bool,
380}
381
382impl Parts {
383    pub(crate) fn whole(text: String) -> Self {
384        Self { text, whole: true }
385    }
386
387    pub(crate) fn partial(text: String) -> Self {
388        Self { text, whole: false }
389    }
390
391    /// Nothing is known of it.
392    pub(crate) fn unknown() -> Self {
393        Self::default()
394    }
395
396    /// The text when it is the whole string.
397    pub(crate) fn value(self) -> Option<String> {
398        self.whole.then_some(self.text)
399    }
400}
401
402/// The place a string names when the code hands it to a call, for a string
403/// that is one: an absolute path, one in the home directory, one that goes up
404/// from where the code runs, or a `file:` URL (whose path is the place, and
405/// is only known when it runs if it holds an escape). A bare name is the
406/// workspace's own, and the rest of the strings are words.
407pub(crate) fn named_path(text: &str) -> Option<Arg> {
408    if text.contains('\n') {
409        return None;
410    }
411    if text.is_char_boundary(5) && text[..5].eq_ignore_ascii_case("file:") {
412        let rest = &text[5..];
413        let rest = match rest.strip_prefix("//") {
414            Some(after) => after.find('/').map_or("", |at| &after[at..]),
415            None => rest,
416        };
417        return Some(if rest.is_empty() || rest.contains('%') {
418            Arg::Unknown(shorten(text))
419        } else {
420            Arg::Known(rest.to_string())
421        });
422    }
423    (text.starts_with(['/', '~']) || text == ".." || text.starts_with("../"))
424        .then(|| Arg::Known(text.to_string()))
425}
426
427/// A read of a path that starts as `known` says and ends in something only
428/// known when it runs: the folder it is under, with the rest left open
429/// (`'/home/me/.ssh/id_' + n` is a file in `/home/me/.ssh/`). `None` when no
430/// folder is known.
431fn under(known: &str, code: &str) -> Option<Arg> {
432    let end = known.rfind('/')? + 1;
433    Some(Arg::Below {
434        folder: known[..end].to_string(),
435        source: shorten(code),
436    })
437}
438
439/// A path read from the start of `parts`: its text when whole, the folder it
440/// is under when only the start is known, else a path only known when the
441/// code runs.
442fn read_path(parts: Parts, code: &str) -> Arg {
443    if parts.whole {
444        Arg::Known(parts.text)
445    } else {
446        under(&parts.text, code).unwrap_or_else(|| Arg::Unknown(shorten(code)))
447    }
448}
449
450/// The argument lists a call that starts a program may run with, when a word
451/// of the list may be any of several strings (a name a loop sets to each of
452/// them): one list for each choice of one string for each word, so each is
453/// judged. Past [`MAX_CHOICES`] lists the words that are left are each one
454/// word only known when it runs. A word with no choice is one only known
455/// when it runs too.
456pub(crate) fn argument_lists(words: Vec<Vec<Arg>>) -> Vec<Vec<Arg>> {
457    let mut lists: Vec<Vec<Arg>> = vec![Vec::new()];
458    for choices in words {
459        let choices =
460            if choices.is_empty() || lists.len().saturating_mul(choices.len()) > MAX_CHOICES {
461                let shown = choices.first().map_or("an argument", Arg::text);
462                vec![Arg::Unknown(shorten(shown))]
463            } else {
464                choices
465            };
466        lists = lists
467            .iter()
468            .flat_map(|list| {
469                choices.iter().map(move |choice| {
470                    let mut next = list.clone();
471                    next.push(choice.clone());
472                    next
473                })
474            })
475            .collect();
476    }
477    lists
478}
479
480/// The longest string worked out from names the code sets: a longer one is
481/// no string the reader knows. A name set to a string built from itself, or
482/// from another that was (`a = a + a`, repeated), doubles it with each line,
483/// so without a limit a few hundred bytes of code take seconds and gigabytes.
484/// Only where a name is put back as its strings, which is where that
485/// growth comes from; a path is not longer than this.
486pub(crate) const MAX_STRING: usize = 4 * 1024;
487
488/// The most bytes of strings noted for all names together: past it the name
489/// that went over is dropped, not read as any string. A few times the
490/// longest line, so the strings a line writes out are all noted.
491const MAX_NOTED: usize = 4 * MAX_LEN;
492
493/// The most paths one piece of code reads out of names: past it the read is
494/// of code the reader does not follow. A name read with every string it holds
495/// is that many reads, and so is every use of it.
496const MAX_EXPANDED: usize = 1024;
497
498/// The strings the code sets one name to.
499#[derive(Debug, Default)]
500struct Noted {
501    strings: Vec<String>,
502    seen: HashSet<String>,
503    /// Folders the name stands for a path somewhere below
504    /// (`for p in Path(d).glob('*')`).
505    folders: Vec<String>,
506    /// Whether the name was set to more than the reader keeps: it stands for
507    /// a string it does not know.
508    dropped: bool,
509}
510
511/// What a name is read as.
512#[derive(Debug)]
513pub(crate) enum Holds {
514    /// The code sets it to no string the reader knows.
515    Nothing,
516    /// Exactly one string.
517    One(String),
518    /// A path under a folder.
519    Below(String),
520    /// Strings that were dropped, or too many to give one: no string.
521    Lost,
522}
523
524/// The paths a read of a name may be.
525#[derive(Debug)]
526pub(crate) enum Expansion {
527    /// The name is none the reader noted a string for.
528    Nothing,
529    /// Every path it may be.
530    Paths(Vec<Arg>),
531    /// Some it does not know.
532    Lost,
533}
534
535/// The strings each name is set to in the code, as the reader knows them,
536/// for the reads of files. Every string is kept, up to a number of bytes in
537/// all; a name that went over it, or was set to a string longer than
538/// [`MAX_STRING`], is dropped, and a read of it is code the reader does not
539/// follow.
540#[derive(Debug, Default)]
541pub(crate) struct Constants {
542    names: HashMap<String, Noted>,
543    bytes: usize,
544    expanded: usize,
545    /// Evaluations made, one for each choice of a string for each name that
546    /// holds more than one, in all.
547    evaluations: usize,
548    /// The names that hold more than one string which the value being worked
549    /// out used, in the order it met them, and the string each is read as in
550    /// this evaluation.
551    multi: Vec<String>,
552    picks: HashMap<String, usize>,
553    /// Set when what was just worked out used a string that was dropped, or
554    /// was cut at [`MAX_STRING`]: a read of it is then not read in full.
555    pub(crate) lost: bool,
556    /// The names bound in a way the reader does not work out whole (set to a
557    /// value it cannot give, unpacked, looped over, a parameter, `del`eted,
558    /// bound by nested code): whatever strings it noted for one, the name may
559    /// stand for another, so a read of it is a path that is not fully known.
560    unresolved: HashSet<String>,
561    /// The names a value was worked out from in this round: one marked
562    /// unresolved after that makes the round stale.
563    consulted: HashSet<String>,
564    /// Whether a name was marked unresolved after a value was worked out from
565    /// it in this round, which makes that value stale.
566    changed: bool,
567    /// Set when the rounds did not settle, or nested code binds names the
568    /// reader cannot list: every name is then unresolved.
569    everything: bool,
570}
571
572/// The most rounds of noting strings: one more is only needed when a name is
573/// found to be unresolved after a value was worked out from it, and each round
574/// marks one more name, so past this every name is taken as unresolved.
575pub(crate) const MAX_ROUNDS: usize = 6;
576
577/// The most times one value is worked out again for a choice of strings, and
578/// the most times in all for a piece of code.
579const MAX_CHOICES: usize = 256;
580const MAX_EVALUATIONS: usize = 64 * 1024;
581
582impl Constants {
583    /// Note `value` as a string `name` is set to.
584    pub(crate) fn note(&mut self, name: &str, value: String) {
585        let noted = self.names.entry(name.to_string()).or_default();
586        if noted.dropped || noted.seen.contains(&value) {
587            return;
588        }
589        if value.len() > MAX_STRING || self.bytes + 2 * value.len() > MAX_NOTED {
590            self.drop_name(name);
591            return;
592        }
593        self.bytes += 2 * value.len();
594        noted.seen.insert(value.clone());
595        noted.strings.push(value);
596    }
597
598    /// Note that `name` stands for a path somewhere under `folder`.
599    pub(crate) fn note_folder(&mut self, name: &str, folder: String) {
600        let noted = self.names.entry(name.to_string()).or_default();
601        if noted.dropped || noted.folders.contains(&folder) {
602            return;
603        }
604        if folder.len() > MAX_STRING || self.bytes + folder.len() > MAX_NOTED {
605            self.drop_name(name);
606            return;
607        }
608        self.bytes += folder.len();
609        noted.folders.push(folder);
610    }
611
612    /// Whether `text`, a string being built where names are put back as their
613    /// strings (`on`), is longer than [`MAX_STRING`]: it is then no string the
614    /// reader knows. Asked at each step of a loop that builds one, so a
615    /// join of thousands of long names is never built.
616    pub(crate) fn over(&mut self, on: bool, text: &str) -> bool {
617        let over = on && text.len() > MAX_STRING;
618        self.lost |= over;
619        over
620    }
621
622    /// `name` is set to something the reader cannot hold: it stands for no
623    /// string, whatever else it is set to.
624    pub(crate) fn drop_name(&mut self, name: &str) {
625        let noted = self.names.entry(name.to_string()).or_default();
626        let freed: usize = noted
627            .strings
628            .iter()
629            .map(|text| 2 * text.len())
630            .sum::<usize>()
631            + noted.folders.iter().map(String::len).sum::<usize>();
632        self.bytes = self.bytes.saturating_sub(freed);
633        *noted = Noted {
634            dropped: true,
635            ..Noted::default()
636        };
637    }
638
639    /// What `name` is, where a string is wanted from it (an operand of a
640    /// `+`, a join, a template). Sets [`Self::lost`] when it is a name that
641    /// holds strings the reader does not give.
642    pub(crate) fn holds(&mut self, name: &str) -> Holds {
643        // A name that may be another string than the ones noted is no value
644        // any path worked out from it is read as.
645        if self.everything || self.unresolved.contains(name) {
646            self.lost = true;
647        } else {
648            self.consulted.insert(name.to_string());
649        }
650        let Some(noted) = self.names.get(name) else {
651            return Holds::Nothing;
652        };
653        if let Some(string) = self.picks.get(name).and_then(|at| noted.strings.get(*at)) {
654            return Holds::One(string.clone());
655        }
656        match (
657            noted.dropped,
658            noted.strings.as_slice(),
659            noted.folders.as_slice(),
660        ) {
661            (true, _, _) => {
662                self.lost = true;
663                Holds::Lost
664            }
665            (false, [one], []) => Holds::One(one.clone()),
666            (false, [], [folder]) => Holds::Below(folder.clone()),
667            (false, [], []) => Holds::Nothing,
668            // More than one string: the value is worked out again for each,
669            // by [`Self::advance`]; for now it is none.
670            (false, [_, _, ..], []) => {
671                if !self.multi.iter().any(|met| met == name) {
672                    self.multi.push(name.to_string());
673                }
674                Holds::Nothing
675            }
676            _ => {
677                self.lost = true;
678                Holds::Lost
679            }
680        }
681    }
682
683    /// `name` is bound in a way the reader does not work out whole. When a
684    /// value was already worked out from it in this round, that value is stale
685    /// and the round is made again.
686    pub(crate) fn mark(&mut self, name: &str) {
687        if self.unresolved.insert(name.to_string()) && self.consulted.contains(name) {
688            self.changed = true;
689        }
690    }
691
692    /// Every name is unresolved: nested code binds names that cannot be
693    /// listed, or the rounds did not settle.
694    pub(crate) fn everything(&mut self) {
695        self.everything = true;
696    }
697
698    /// Whether the round just made worked a value out from a name that was
699    /// marked unresolved after it.
700    pub(crate) fn stale(&self) -> bool {
701        self.changed
702    }
703
704    /// Note the strings again from nothing, keeping what is unresolved.
705    pub(crate) fn start_round(&mut self) {
706        self.names.clear();
707        self.bytes = 0;
708        self.evaluations = 0;
709        self.consulted.clear();
710        self.changed = false;
711        self.lost = false;
712        self.begin();
713    }
714
715    /// Start working a value out: no name that holds more than one string is
716    /// read as any of them yet.
717    pub(crate) fn begin(&mut self) {
718        self.multi.clear();
719        self.picks.clear();
720    }
721
722    /// Whether the evaluation just made met a name that holds more than one
723    /// string and was not read as one of them: its result is not a value.
724    pub(crate) fn pending(&self) -> bool {
725        self.multi.iter().any(|name| !self.picks.contains_key(name))
726    }
727
728    /// Move to the next choice of one string for each name that holds more
729    /// than one, the last name first. `false` when every choice has been
730    /// made, or when there are more than [`MAX_CHOICES`] of them (or the
731    /// piece of code has asked for [`MAX_EVALUATIONS`]), which sets
732    /// [`Self::lost`].
733    pub(crate) fn advance(&mut self) -> bool {
734        if self.multi.is_empty() {
735            return false;
736        }
737        self.evaluations += 1;
738        if self.evaluations > MAX_EVALUATIONS {
739            self.lost = true;
740            return false;
741        }
742        // A name met for the first time is read as its first string, and
743        // the same choice is worked out again.
744        let mut met = false;
745        for name in &self.multi {
746            if !self.picks.contains_key(name) {
747                self.picks.insert(name.clone(), 0);
748                met = true;
749            }
750        }
751        if met {
752            return true;
753        }
754        let total: usize = self
755            .multi
756            .iter()
757            .map(|name| self.names.get(name).map_or(1, |noted| noted.strings.len()))
758            .fold(1, usize::saturating_mul);
759        if total > MAX_CHOICES {
760            self.lost = true;
761            return false;
762        }
763        for name in self.multi.iter().rev() {
764            let count = self.names.get(name).map_or(1, |noted| noted.strings.len());
765            let at = self.picks.get(name).copied().unwrap_or(0);
766            if at + 1 < count {
767                self.picks.insert(name.clone(), at + 1);
768                return true;
769            }
770            self.picks.insert(name.clone(), 0);
771        }
772        false
773    }
774
775    /// Count `count` more paths read out of names: `false` when that is more
776    /// than a piece of code may read ([`MAX_EXPANDED`]), which they are not.
777    pub(crate) fn spend(&mut self, count: usize) -> bool {
778        if self.expanded + count > MAX_EXPANDED {
779            return false;
780        }
781        self.expanded += count;
782        true
783    }
784
785    /// Every path a read of `name` may be, when the code sets it to
786    /// strings.
787    pub(crate) fn paths(&mut self, name: &str, code: &str) -> Expansion {
788        let Some(noted) = self.names.get(name) else {
789            return Expansion::Nothing;
790        };
791        if noted.dropped {
792            return Expansion::Lost;
793        }
794        let count = noted.strings.len() + noted.folders.len();
795        if count == 0 {
796            return Expansion::Nothing;
797        }
798        // Bound another way as well: the name may be a path not known at all,
799        // besides the ones noted.
800        let unresolved = self.everything || self.unresolved.contains(name);
801        let count = count + usize::from(unresolved);
802        if self.expanded + count > MAX_EXPANDED {
803            return Expansion::Lost;
804        }
805        self.expanded += count;
806        let Some(noted) = self.names.get(name) else {
807            return Expansion::Nothing;
808        };
809        let strings = noted.strings.iter().map(|text| Arg::Known(text.clone()));
810        let folders = noted
811            .folders
812            .iter()
813            .filter_map(|folder| under(folder, code));
814        let mut paths: Vec<Arg> = strings.chain(folders).collect();
815        if unresolved {
816            paths.push(Arg::Unknown(shorten(code)));
817        }
818        Expansion::Paths(paths)
819    }
820}
821
822/// `next` joined to `base` as `os.path.join` and `path.join` do: an absolute
823/// `next` stands alone. A `~` is the home directory wherever it comes in the
824/// code, as the shell reads it: code in a double-quoted argument had `$HOME`
825/// put in as `~`, so a literal tilde cannot be told from it.
826fn join(base: &str, next: &str) -> String {
827    if next.starts_with(['/', '~']) || base.is_empty() {
828        next.to_string()
829    } else if base.ends_with('/') {
830        format!("{base}{next}")
831    } else {
832        format!("{base}/{next}")
833    }
834}
835
836/// The directory an environment variable names, where one is known: the
837/// home directory, the working directory, the temporary one.
838fn environment(name: &str) -> Option<String> {
839    match name {
840        "HOME" | "USERPROFILE" => Some("~".to_string()),
841        "PWD" => Some(".".to_string()),
842        "TMPDIR" | "TEMP" | "TMP" => Some("/tmp".to_string()),
843        _ => None,
844    }
845}
846
847/// An integer literal as the octal digits `chmod` takes: `0o755`, `0755`,
848/// `493`, `0x1ED`.
849fn mode(literal: &str) -> Option<String> {
850    let text = literal.replace('_', "");
851    let lower = text.to_ascii_lowercase();
852    let number = if let Some(digits) = lower.strip_prefix("0o") {
853        u32::from_str_radix(digits, 8)
854    } else if let Some(digits) = lower.strip_prefix("0x") {
855        u32::from_str_radix(digits, 16)
856    } else if let Some(digits) = lower.strip_prefix("0b") {
857        u32::from_str_radix(digits, 2)
858    } else if lower.len() > 1 && lower.starts_with('0') {
859        u32::from_str_radix(&lower[1..], 8)
860    } else {
861        lower.parse()
862    };
863    number.ok().map(|number| format!("{number:o}"))
864}
865
866/// The process id a literal gives, as the decimal text `kill` takes: `9`,
867/// `-1`, `(-1)`, `0x1`, `- 1`, `1_0`. `None` for a value only known when it
868/// runs, a float, and a number with a leading zero (an octal in one language
869/// and no number in the other).
870fn pid(literal: &str) -> Option<String> {
871    let mut text: String = literal.chars().filter(|c| !c.is_whitespace()).collect();
872    while text.len() > 1 && text.starts_with('(') && text.ends_with(')') {
873        text = text[1..text.len() - 1].to_string();
874    }
875    let mut negative = false;
876    while let Some(rest) = text.strip_prefix(['-', '+']) {
877        negative ^= text.starts_with('-');
878        text = rest.to_string();
879    }
880    let lower = text.replace('_', "").to_ascii_lowercase();
881    let number = if let Some(digits) = lower.strip_prefix("0x") {
882        i64::from_str_radix(digits, 16)
883    } else if let Some(digits) = lower.strip_prefix("0o") {
884        i64::from_str_radix(digits, 8)
885    } else if let Some(digits) = lower.strip_prefix("0b") {
886        i64::from_str_radix(digits, 2)
887    } else if lower.len() > 1 && lower.starts_with('0')
888        || !lower.bytes().all(|b| b.is_ascii_digit())
889    {
890        return None;
891    } else {
892        lower.parse()
893    };
894    let number = number.ok()?;
895    Some(if negative { -number } else { number }.to_string())
896}
897
898/// What `os.kill(PID, …)` and `process.kill(PID, …)` do: the `kill` command
899/// with that process id. A process id only known when it runs may be every
900/// process (`-1`) or the first (`1`), so it comes back as code the reader
901/// does not follow.
902fn kill(literal: &str) -> Act {
903    match pid(literal) {
904        Some(pid) => Act::Program(vec![
905            Arg::Known("kill".to_string()),
906            Arg::Known("--".to_string()),
907            Arg::Known(pid),
908        ]),
909        None => Act::Unread(shorten(literal)),
910    }
911}
912
913/// The value of a quoted-style mode argument (`open`'s `'w'`, `fs.openSync`'s
914/// flags): whether it writes. `None` mode is the default, which reads.
915fn writes(mode: Option<&str>) -> bool {
916    mode.is_some_and(|mode| mode.contains(['w', 'a', 'x', '+']))
917}
918
919/// Whether a module specifier is a `data:` URL, whose code runs where it is
920/// written: as the URL parser reads it, leading control characters and
921/// spaces and any tab or newline are dropped, and the scheme has no case.
922fn data_url(specifier: &str) -> bool {
923    let cleaned: String = specifier
924        .trim_start_matches(|c: char| c <= ' ')
925        .chars()
926        .filter(|c| !matches!(c, '\t' | '\n' | '\r'))
927        .take(5)
928        .collect();
929    cleaned.eq_ignore_ascii_case("data:")
930}
931
932/// Where a module a specifier names is loaded from, when it is not the
933/// workspace's own.
934#[derive(Debug, Clone, Copy, PartialEq, Eq)]
935enum Foreign {
936    /// From the network (`https:`, `http:`) or a registry that downloads it
937    /// (`jsr:`, `npm:`).
938    Downloaded,
939    /// From a file outside the workspace: an absolute path, a `file:` URL, or
940    /// one that goes up from where the code runs (`../x.js`).
941    Outside,
942}
943
944/// Where the module `specifier` is loaded from, when it is not a file of the
945/// workspace's own (a relative `./x.js`) or a package it installed (`fs`,
946/// `node:fs`, `lodash`). As the URL parser reads it, leading control
947/// characters and spaces and any tab or newline are dropped and the scheme has
948/// no case.
949fn foreign_module(specifier: &str) -> Option<Foreign> {
950    let cleaned: String = specifier
951        .trim_start_matches(|c: char| c <= ' ')
952        .chars()
953        .filter(|c| !matches!(c, '\t' | '\n' | '\r'))
954        .collect();
955    let lower = cleaned.to_ascii_lowercase();
956    if ["http:", "https:", "jsr:", "npm:"]
957        .iter()
958        .any(|scheme| lower.starts_with(scheme))
959    {
960        return Some(Foreign::Downloaded);
961    }
962    let drive = {
963        let mut chars = cleaned.chars();
964        chars.next().is_some_and(|c| c.is_ascii_alphabetic()) && chars.next() == Some(':')
965    };
966    (lower.starts_with("file:")
967        || cleaned.starts_with(['/', '\\', '~'])
968        || cleaned == ".."
969        || cleaned.starts_with("../")
970        || cleaned.starts_with("..\\")
971        || drive)
972        .then_some(Foreign::Outside)
973}
974
975/// Whether the module `specifier` is a `data:` URL, whose code runs where it
976/// is written, so no one reads it elsewhere. As the URL parser reads it,
977/// leading control characters and spaces and any tab or newline are dropped,
978/// and the scheme has no case.
979pub fn is_data_url(specifier: &str) -> bool {
980    data_url(specifier)
981}
982
983/// Whether the module `specifier` is loaded from outside the workspace: from
984/// the network (`https:`, `http:`) or a registry that downloads it (`jsr:`,
985/// `npm:`), or from a file that is not the workspace's own (an absolute path,
986/// one in the home directory, a `file:` URL, one that goes up from where the
987/// code runs). A relative `./x.js` and an installed package (`fs`,
988/// `node:fs`, `lodash`) are not. The reader finds code that loads one as an
989/// [`Act::Downloaded`] or an [`Act::Loads`]; this is the same answer for a
990/// specifier a caller meets outside the code, such as a `--import` option.
991pub fn is_foreign_module(specifier: &str) -> bool {
992    foreign_module(specifier).is_some()
993}
994
995/// What loading the module `specifier` does when it is not the workspace's
996/// own: downloaded and run, or a file outside it.
997pub(crate) fn loads(specifier: &str, code: &str) -> Option<Act> {
998    Some(match foreign_module(specifier)? {
999        Foreign::Downloaded => Act::Downloaded(shorten(code)),
1000        Foreign::Outside => Act::Loads(shorten(code)),
1001    })
1002}