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}