Skip to main content

fallow_types/
extract_function_contracts.rs

1//! Persisted call evidence for plain functions: the parameter contract of each
2//! module-scope function binding, the direct calls of admitted callees, and
3//! the references that let a local function escape.
4//!
5//! A rule reads these facts to report a parameter that gets the same value at
6//! each call, or an optional parameter that no caller passes. The facts are
7//! syntactic. The analysis resolves each call target through the module graph
8//! and abstains when a caller can be invisible.
9
10/// Call evidence of one module.
11#[derive(Debug, Clone, Default, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
12pub struct FunctionContractFacts {
13    /// One contract for each function that a module-scope binding holds.
14    pub declarations: Vec<FunctionContract>,
15    /// Direct calls whose callee is an admitted import binding or a local
16    /// function binding, one entry per callee, ordered by the first site.
17    pub calls: Vec<FunctionCalls>,
18    /// References to a local function binding that are not a direct callee,
19    /// in source order.
20    pub escapes: Vec<LocalFunctionEscape>,
21    /// `true` for a Vue, Svelte, Astro, Glimmer or MDX host. A template, an
22    /// inline script, or another script block of the file can call a binding,
23    /// and the facts do not hold those calls. A consumer must treat each
24    /// contract of the file, and each import that the file calls, as open.
25    pub template_callers: bool,
26    /// `true` when the module calls `eval` directly, at any depth. A direct
27    /// `eval` can call each binding in scope with any value, so a consumer
28    /// must treat each contract of the module, and each import that the
29    /// module calls, as open. A contract whose own body or default values
30    /// call `eval` also has [`ContractIncomplete::DirectEval`].
31    pub direct_eval: bool,
32    /// The uses of each `import()` or `require` call whose source gives no
33    /// file and no pattern, such as `import(name)`. Such a call can load each
34    /// module of the project.
35    pub opaque_loads: OpaqueLoads,
36    /// The local names of the exported module-scope `const` bindings whose
37    /// initializer is a literal, in source order. A call argument that names
38    /// one of these bindings through an import has a known identity.
39    pub literal_consts: Vec<Box<str>>,
40}
41
42impl FunctionContractFacts {
43    /// Each call site with its callee, ordered by callee and then by site.
44    pub fn call_sites(&self) -> impl Iterator<Item = (CallTarget, &str, &CallSite)> {
45        self.calls.iter().flat_map(|calls| {
46            calls
47                .sites
48                .iter()
49                .map(|site| (calls.target, &*calls.member_path, site))
50        })
51    }
52
53    /// `true` when the module has no call evidence to store.
54    #[must_use]
55    pub fn is_empty(&self) -> bool {
56        self.declarations.is_empty()
57            && self.calls.is_empty()
58            && self.escapes.is_empty()
59            && !self.template_callers
60            && !self.direct_eval
61            && self.opaque_loads.is_empty()
62            && self.literal_consts.is_empty()
63    }
64}
65
66/// How the code of one module uses the values of its loads with an unknown
67/// source. A consumer must treat each exported contract of the project with
68/// one of `names` as its export name as open. When `escapes` is `true`, the
69/// consumer must treat each exported contract of the project as open. For
70/// each of `loaders`, the consumer reads the results of the calls of that
71/// function with the same rules.
72#[derive(Debug, Clone, Default, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
73pub struct OpaqueLoads {
74    /// The export names that the code reads on a loaded value, sorted and
75    /// without repeats. `default` names the default export.
76    pub names: Vec<String>,
77    /// `true` when a loaded value goes to code that the facts do not follow,
78    /// for example an alias, a call argument, a spread, or a return from a
79    /// function that has no contract.
80    pub escapes: bool,
81    /// The functions of the module that return a loaded value, sorted and
82    /// without repeats. Each caller of such a function gets the loaded value.
83    pub loaders: Vec<LoaderReturn>,
84}
85
86impl OpaqueLoads {
87    /// `true` when no load reads a name, no loaded value escapes, and no
88    /// function returns a loaded value.
89    #[must_use]
90    pub const fn is_empty(&self) -> bool {
91        self.names.is_empty() && !self.escapes && self.loaders.is_empty()
92    }
93
94    /// Add the names, the escape and the loaders of `other`.
95    pub fn merge(&mut self, other: Self) {
96        self.names.extend(other.names);
97        self.names.sort_unstable();
98        self.names.dedup();
99        self.escapes |= other.escapes;
100        self.loaders.extend(other.loaders);
101        self.loaders.sort_unstable();
102        self.loaders.dedup();
103    }
104
105    /// Move each loader index past `base`, for the facts of a later script
106    /// block of one host file.
107    pub fn shift_loaders(&mut self, base: u32) {
108        for loader in &mut self.loaders {
109            loader.contract = loader.contract.saturating_add(base);
110        }
111    }
112}
113
114/// A function contract that returns the value of a load with an unknown
115/// source, such as `const load = (path) => import(path)`.
116#[derive(
117    Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash, bitcode::Encode, bitcode::Decode,
118)]
119pub struct LoaderReturn {
120    /// Index into [`FunctionContractFacts::declarations`].
121    pub contract: u32,
122    /// `true` when a call of the function gives a promise of the loaded
123    /// value: the function is `async`, or it returns the promise of an
124    /// `import()`.
125    pub promise: bool,
126}
127
128/// How the code uses the results of the calls of one callee, read with the
129/// rules of [`OpaqueLoads`]. The extractor does not know what the callee
130/// returns, so it reads the results in two ways. When the callee is a
131/// loader ([`OpaqueLoads::loaders`]), a consumer reads the way that matches
132/// the loader.
133#[derive(Debug, Clone, Default, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
134pub struct CallResultReads {
135    /// The uses when each call gives the loaded value.
136    pub value: OpaqueLoads,
137    /// The uses when each call gives a promise of the loaded value.
138    pub promise: OpaqueLoads,
139}
140
141impl CallResultReads {
142    /// Add the uses of `other`.
143    pub fn merge(&mut self, other: Self) {
144        self.value.merge(other.value);
145        self.promise.merge(other.promise);
146    }
147
148    /// Move each loader index past `base`.
149    pub fn shift_loaders(&mut self, base: u32) {
150        self.value.shift_loaders(base);
151        self.promise.shift_loaders(base);
152    }
153}
154
155/// The parameter contract of a function that a module-scope binding holds:
156/// `function f() {}`, or `const f = () => {}` and `const f = function () {}`.
157#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
158pub struct FunctionContract {
159    /// The module-scope binding name.
160    pub binding_name: Box<str>,
161    /// Start byte of the binding identifier.
162    pub span_start: u32,
163    /// One fact for each formal parameter, in order. A TypeScript `this`
164    /// parameter is not a formal parameter.
165    pub params: Vec<ParamFact>,
166    /// `true` when a `return` of the function has an expression, or the arrow
167    /// function has an expression body.
168    pub returns_value: bool,
169    /// `true` for an `async` function declaration, function expression or
170    /// arrow function. A call of an async function always gives a promise.
171    pub is_async: bool,
172    /// The first reason found that the extractor cannot see each use of the
173    /// parameters. `None` for a closed contract.
174    pub incomplete: Option<ContractIncomplete>,
175}
176
177/// One formal parameter of a [`FunctionContract`].
178#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
179pub struct ParamFact {
180    /// The parameter name. `None` for an object or array pattern.
181    pub name: Option<Box<str>>,
182    /// Start byte of the parameter: the `...` of a rest parameter, else the
183    /// binding or pattern.
184    pub span_start: u32,
185    /// The binding shape of the parameter.
186    pub kind: ParamKind,
187    /// `true` for a TypeScript `?` marker.
188    pub optional: bool,
189    /// `true` when the parameter has a default value.
190    pub has_default: bool,
191    /// `true` for a rest parameter.
192    pub is_rest: bool,
193    /// The count of conditions whose test is the parameter or its negation:
194    /// the test of an `if`, a `?:`, a loop, or `p`, `!p` and `!!p` there.
195    pub condition_reads: u32,
196    /// `true` when the module writes the parameter binding: in the body, in
197    /// a default value, or in a nested function or arrow, for example
198    /// `p = !p`, `p ??= x`, `[p] = xs` or `p++`. For an object or array
199    /// pattern, `true` when the module writes any binding of the pattern. A
200    /// `var` or function declaration in the body that redeclares the
201    /// parameter also counts as a write. A written parameter can hold a
202    /// value that no caller passes.
203    pub written: bool,
204    /// The option keys of an object pattern, in source order. Empty for
205    /// each other parameter kind, and for an object pattern whose default is
206    /// not absent or an empty object literal, because such a default can
207    /// set a key that no caller passes.
208    pub keys: Vec<OptionKeyFact>,
209}
210
211/// One key of an object-pattern [`ParamFact`]: `retries` in
212/// `{ retries = 3, signal: abort }`.
213///
214/// Only a static key whose value is a plain binding, with or without a
215/// default, is recorded. A computed or numeric key, a nested pattern, and a
216/// key that `Object.prototype` holds, such as `toString`, are not recorded.
217#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
218pub struct OptionKeyFact {
219    /// The property key.
220    pub key: Box<str>,
221    /// The local binding name: `abort` for `signal: abort`.
222    pub binding: Box<str>,
223    /// Start byte of the binding identifier.
224    pub span_start: u32,
225    /// `true` when the key has a default value.
226    pub has_default: bool,
227    /// The count of conditions whose test is the binding or its negation,
228    /// as [`ParamFact::condition_reads`] counts them.
229    pub condition_reads: u32,
230    /// `true` when the module writes the binding.
231    pub written: bool,
232}
233
234/// The binding shape of a [`ParamFact`].
235#[derive(Debug, Clone, Copy, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
236pub enum ParamKind {
237    /// A plain identifier.
238    Identifier,
239    /// An object destructuring pattern.
240    Object,
241    /// An array destructuring pattern.
242    Array,
243}
244
245/// Why a [`FunctionContract`] is open.
246#[derive(Debug, Clone, Copy, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
247pub enum ContractIncomplete {
248    /// The function has TypeScript overload signatures.
249    Overload,
250    /// The body or a default value reads `arguments`, also in a decorator,
251    /// a method parameter decorator, an `extends` clause or a computed key
252    /// of a class inside the function.
253    ArgumentsRead,
254    /// The function calls `eval` directly.
255    DirectEval,
256    /// A `let` or `var` declaration holds the function.
257    MutableBinding,
258    /// The module assigns the binding again.
259    Reassigned,
260    /// A parameter has a decorator.
261    Decorator,
262    /// The function is a generator.
263    Generator,
264    /// A second declaration has the same name.
265    DuplicateDeclaration,
266}
267
268/// The direct calls of one callee: an admitted import binding with a member
269/// path, or a local function binding.
270///
271/// The extractor groups the sites per callee, so the target and the path are
272/// stored once. Optional calls, computed callees and calls through bindings
273/// that are not admitted are not stored.
274#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
275pub struct FunctionCalls {
276    /// The binding that the callee names.
277    pub target: CallTarget,
278    /// Dot-separated static member suffix after an import binding, empty for
279    /// a bare call. Always empty for a local target.
280    ///
281    /// For a namespace import, the first segment is the export name. For a
282    /// named or default import of a function, a non-empty path, for example
283    /// `call`, `apply` or `bind`, is not a plain call of the function, so a
284    /// consumer must treat the function as open for that site.
285    pub member_path: Box<str>,
286    /// Each call of this callee, in source order. Never empty.
287    pub sites: Vec<CallSite>,
288    /// The uses of the results of the sites whose result the code uses.
289    pub results: CallResultReads,
290}
291
292/// One direct call of a [`FunctionCalls`] callee.
293#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
294pub struct CallSite {
295    /// The count of arguments, spread arguments included.
296    pub arg_count: u32,
297    /// One fact for each argument before the first spread, to a fixed
298    /// maximum. A string literal longer than a fixed maximum is
299    /// [`ArgFact::Unknown`]. A spread moves each later argument to an
300    /// unknown parameter, so no fact is kept from the spread on. Empty when
301    /// each kept argument is [`ArgFact::Unknown`], so `arg_count` then holds
302    /// the shape.
303    ///
304    /// Do not index this list directly. Use [`CallSite::arg_at`], which
305    /// gives one of three outcomes for a parameter position: a known fact,
306    /// an unknown value, or an omitted argument.
307    pub args: Vec<ArgFact>,
308    /// The index of the first spread argument.
309    pub spread_from: Option<u32>,
310    /// `false` when the call, with or without `await` or `void`, is a whole
311    /// expression statement.
312    pub result_used: bool,
313    /// Start byte of the call expression.
314    pub span_start: u32,
315}
316
317impl CallSite {
318    /// The argument that this call passes at parameter position `index`.
319    ///
320    /// - From the first spread on, each position is [`ArgAt::Unknown`],
321    ///   because a spread can fill any later position.
322    /// - A position at or past `arg_count` is [`ArgAt::Omitted`].
323    /// - A position with a stored fact other than [`ArgFact::Unknown`] is
324    ///   [`ArgAt::Fact`].
325    /// - Each other position is [`ArgAt::Unknown`]: a stored unknown fact,
326    ///   a position past the kept facts, or a call with an empty `args`.
327    #[must_use]
328    pub fn arg_at(&self, index: u32) -> ArgAt<'_> {
329        if self.spread_from.is_some_and(|spread| index >= spread) {
330            return ArgAt::Unknown;
331        }
332        if index >= self.arg_count {
333            return ArgAt::Omitted;
334        }
335        match usize::try_from(index).ok().and_then(|at| self.args.get(at)) {
336            Some(ArgFact::Unknown) | None => ArgAt::Unknown,
337            Some(fact) => ArgAt::Fact(fact),
338        }
339    }
340}
341
342/// The argument of a [`CallSite`] at one parameter position. This type is
343/// not stored in the cache.
344#[derive(Debug, Clone, Copy, PartialEq, Eq)]
345pub enum ArgAt<'a> {
346    /// A known argument fact. Never [`ArgFact::Unknown`].
347    Fact(&'a ArgFact),
348    /// The call passes a value that the facts do not know.
349    Unknown,
350    /// The call passes no argument at this position.
351    Omitted,
352}
353
354/// The binding that a [`FunctionCalls`] callee names.
355#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, bitcode::Encode, bitcode::Decode)]
356pub enum CallTarget {
357    /// Index into `ModuleInfo.imports` of an admitted runtime ESM import.
358    Import(u32),
359    /// Index into [`FunctionContractFacts::declarations`].
360    Local(u32),
361}
362
363/// The syntactic value of one call argument.
364#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
365pub enum ArgFact {
366    /// A literal value.
367    Literal(LiteralValue),
368    /// The value of the parameter at this index of the called function. Only
369    /// a self-call has this fact: a call of a local function inside the
370    /// body or a default value of that same function. The argument is the
371    /// unchanged identifier of a formal identifier parameter that the module
372    /// never writes, so the call passes the value that the outer call got. A
373    /// rest parameter never gets this fact, because the callee gets `[r]`
374    /// for `f(r)`.
375    Param(u32),
376    /// An immutable binding: a module-scope `const` with a literal
377    /// initializer, or an enum member.
378    Binding(BindingArg),
379    /// An object literal with no spread, no computed key, no numeric key,
380    /// and no `__proto__` key. Each key appears once, with the value of its
381    /// last property.
382    Object(Vec<KeyArg>),
383    /// Each other expression. `args` never holds a spread argument, because
384    /// the list stops before the first spread.
385    Unknown,
386}
387
388/// An argument that names an immutable binding.
389///
390/// The extractor checks a local binding. For an import, the analysis
391/// resolves the origin export and checks that it is a `const` with a literal
392/// initializer ([`FunctionContractFacts::literal_consts`]), or an enum with
393/// the member.
394#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
395pub struct BindingArg {
396    /// Where the root identifier of the argument comes from.
397    pub root: BindingRoot,
398    /// The dot-separated static path.
399    ///
400    /// - For [`BindingRoot::Local`]: the binding name, then the enum member
401    ///   for an enum (`Mode.Grid`).
402    /// - For [`BindingRoot::Import`] of a named or default import: empty for
403    ///   a constant, else the enum member.
404    /// - For [`BindingRoot::Import`] of a namespace import: the export name,
405    ///   then the enum member.
406    pub path: Box<str>,
407}
408
409/// The root of a [`BindingArg`].
410#[derive(Debug, Clone, Copy, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
411pub enum BindingRoot {
412    /// A module-scope `const` with a literal initializer, or a module-scope
413    /// enum with the member, of the module that holds the call.
414    Local,
415    /// Index into `ModuleInfo.imports` of an admitted runtime ESM import.
416    Import(u32),
417}
418
419/// One key of an [`ArgFact::Object`] argument.
420#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
421pub struct KeyArg {
422    /// The property key.
423    pub key: Box<str>,
424    /// The value of the key.
425    pub value: KeyValue,
426}
427
428/// The value of one [`KeyArg`]. The same facts as [`ArgFact`], with no
429/// nested object.
430#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
431pub enum KeyValue {
432    /// A literal value.
433    Literal(LiteralValue),
434    /// An immutable binding.
435    Binding(BindingArg),
436    /// A self-call passes the unchanged binding of the same key of the same
437    /// object-pattern parameter, at the same position:
438    /// `walk(node, { depth })` inside `walk(node, { depth })`.
439    PassThrough,
440    /// Each other value, a method, a getter or a setter.
441    Unknown,
442}
443
444/// A literal argument value in canonical form.
445#[derive(Debug, Clone, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
446pub enum LiteralValue {
447    /// `true` or `false`.
448    Boolean(bool),
449    /// `null`.
450    Null,
451    /// The unshadowed identifier `undefined`.
452    Undefined,
453    /// The IEEE 754 bits of a numeric literal or its negation, so `1` and
454    /// `1.0` are equal. `-0` and `0` are different values, because
455    /// `Object.is` and `1 / x` tell them apart.
456    Number(u64),
457    /// The value of a string literal or of a template literal with no
458    /// expression.
459    String(Box<str>),
460}
461
462/// A reference to a local function binding that is not a direct callee, for
463/// example `items.map(format)`, `const g = format`, `<Format />` or
464/// `` format`x` ``.
465#[derive(Debug, Clone, Copy, PartialEq, Eq, bitcode::Encode, bitcode::Decode)]
466pub struct LocalFunctionEscape {
467    /// Index into [`FunctionContractFacts::declarations`].
468    pub contract: u32,
469    /// Start byte of the reference.
470    pub span_start: u32,
471}
472
473#[cfg(test)]
474mod tests {
475    use super::*;
476
477    fn site(arg_count: u32, args: Vec<ArgFact>, spread_from: Option<u32>) -> CallSite {
478        CallSite {
479            arg_count,
480            args,
481            spread_from,
482            result_used: false,
483            span_start: 0,
484        }
485    }
486
487    const TRUE: ArgFact = ArgFact::Literal(LiteralValue::Boolean(true));
488
489    #[test]
490    fn a_position_from_the_spread_on_is_unknown() {
491        let call = site(2, vec![TRUE], Some(1));
492        assert_eq!(call.arg_at(0), ArgAt::Fact(&TRUE));
493        assert_eq!(call.arg_at(1), ArgAt::Unknown);
494        assert_eq!(call.arg_at(3), ArgAt::Unknown);
495        assert_eq!(site(1, Vec::new(), Some(0)).arg_at(3), ArgAt::Unknown);
496    }
497
498    #[test]
499    fn a_position_past_the_count_is_omitted() {
500        assert_eq!(site(0, Vec::new(), None).arg_at(0), ArgAt::Omitted);
501        assert_eq!(site(1, vec![TRUE], None).arg_at(1), ArgAt::Omitted);
502    }
503
504    #[test]
505    fn empty_args_with_a_count_are_unknown() {
506        let call = site(2, Vec::new(), None);
507        assert_eq!(call.arg_at(0), ArgAt::Unknown);
508        assert_eq!(call.arg_at(1), ArgAt::Unknown);
509        assert_eq!(call.arg_at(2), ArgAt::Omitted);
510    }
511
512    #[test]
513    fn a_stored_unknown_is_unknown_and_a_param_is_a_fact() {
514        let call = site(2, vec![ArgFact::Unknown, ArgFact::Param(0)], None);
515        assert_eq!(call.arg_at(0), ArgAt::Unknown);
516        assert_eq!(call.arg_at(1), ArgAt::Fact(&ArgFact::Param(0)));
517    }
518
519    #[test]
520    fn a_position_past_the_kept_facts_is_unknown() {
521        // The extractor keeps 16 argument facts and the full count.
522        let call = site(40, vec![TRUE; 16], None);
523        assert_eq!(call.arg_at(15), ArgAt::Fact(&TRUE));
524        assert_eq!(call.arg_at(16), ArgAt::Unknown);
525        assert_eq!(call.arg_at(39), ArgAt::Unknown);
526        assert_eq!(call.arg_at(40), ArgAt::Omitted);
527    }
528}