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}