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}