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