turbopack_ecmascript/analyzer/
linker.rs

1use std::{collections::hash_map::Entry, fmt::Display, future::Future, mem::take};
2
3use anyhow::Result;
4use parking_lot::Mutex;
5use rustc_hash::{FxHashMap, FxHashSet};
6use swc_core::ecma::ast::Id;
7use turbo_rcstr::rcstr;
8
9use super::{Bump, JsValue, ThreadLocal, graph::VarGraph};
10use crate::analyzer::BumpVec;
11
12pub async fn link<'a, 'l, B, RB, F, RF>(
13    arena: &'a ThreadLocal<Bump>,
14    graph: &'l VarGraph<'a>,
15    mut val: JsValue<'a>,
16    early_visitor: &'l B,
17    visitor: &'l F,
18    fun_args_values: &Mutex<FxHashMap<u32, BumpVec<'a, JsValue<'a>>>>,
19    var_cache: &Mutex<FxHashMap<Id, JsValue<'a>>>,
20) -> Result<(JsValue<'a>, u32)>
21where
22    RB: 'l + Future<Output = Result<(JsValue<'a>, bool)>> + Send,
23    B: 'l + Fn(JsValue<'a>) -> RB + Sync,
24    RF: 'l + Future<Output = Result<(JsValue<'a>, bool)>> + Send,
25    F: 'l + Fn(JsValue<'a>) -> RF + Sync,
26{
27    val.normalize(arena.get_or_default());
28    let (val, steps) = link_internal_iterative(
29        arena,
30        graph,
31        val,
32        early_visitor,
33        visitor,
34        fun_args_values,
35        var_cache,
36    )
37    .await?;
38    Ok((val, steps))
39}
40
41const LIMIT_NODE_SIZE: u32 = 100;
42const LIMIT_IN_PROGRESS_NODES: u32 = 500;
43const LIMIT_LINK_STEPS: u32 = 1500;
44
45#[derive(Debug, PartialEq)]
46enum Step<'a> {
47    /// Take all children out of the value (replacing temporarily with unknown) and queue them
48    /// for processing using individual `Enter`s.
49    Enter(JsValue<'a>),
50    /// Pop however many children there are from `done` and reinsert them into the value
51    Leave(JsValue<'a>),
52    /// Remove the variable from `cycle_stack` which detects e.g. circular reassignments
53    LeaveVar(Id),
54    LeaveLate(JsValue<'a>),
55    /// Call the visitor callbacks, and requeue the value for further processing if it changed.
56    Visit(JsValue<'a>),
57    EarlyVisit(JsValue<'a>),
58    /// Remove the call from `fun_args_values`
59    LeaveCall(u32),
60    /// Placeholder that is used to momentarily reserve a slot that is only filled after
61    /// pushing some more steps
62    TemporarySlot,
63}
64
65impl Display for Step<'_> {
66    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
67        match self {
68            Step::Enter(val) => write!(f, "Enter({val})"),
69            Step::EarlyVisit(val) => write!(f, "EarlyVisit({val})"),
70            Step::Leave(val) => write!(f, "Leave({val})"),
71            Step::LeaveVar(var) => write!(f, "LeaveVar({var:?})"),
72            Step::LeaveLate(val) => write!(f, "LeaveLate({val})"),
73            Step::Visit(val) => write!(f, "Visit({val})"),
74            Step::LeaveCall(func_ident) => write!(f, "LeaveCall({func_ident})"),
75            Step::TemporarySlot => write!(f, "TemporarySlot"),
76        }
77    }
78}
79// If a variable was already visited in this linking call, don't visit it again.
80
81pub(crate) async fn link_internal_iterative<'a, 'l, B, RB, F, RF>(
82    arena: &'a ThreadLocal<Bump>,
83    graph: &'l VarGraph<'a>,
84    val: JsValue<'a>,
85    early_visitor: &'l B,
86    visitor: &'l F,
87    fun_args_values: &Mutex<FxHashMap<u32, BumpVec<'a, JsValue<'a>>>>,
88    var_cache: &Mutex<FxHashMap<Id, JsValue<'a>>>,
89) -> Result<(JsValue<'a>, u32)>
90where
91    RB: 'l + Future<Output = Result<(JsValue<'a>, bool)>> + Send,
92    B: 'l + Fn(JsValue<'a>) -> RB + Sync,
93    RF: 'l + Future<Output = Result<(JsValue<'a>, bool)>> + Send,
94    F: 'l + Fn(JsValue<'a>) -> RF + Sync,
95{
96    let mut work_queue_stack: Vec<Step<'a>> = Vec::new();
97    let mut done: Vec<JsValue<'a>> = Vec::new();
98    // Tracks the number of nodes in the queue and done combined
99    let mut total_nodes = 0;
100    let mut cycle_stack: FxHashSet<Id> = FxHashSet::default();
101    // Tracks the number linking steps so far
102    let mut steps = 0;
103
104    total_nodes += val.total_nodes();
105    work_queue_stack.push(Step::Enter(val));
106
107    while let Some(step) = work_queue_stack.pop() {
108        steps += 1;
109
110        match step {
111            // Enter a variable
112            // - replace it with value from graph
113            // - process value
114            // - (Step::LeaveVar potentially caches the value)
115            Step::Enter(JsValue::Variable(var)) => {
116                if cycle_stack.contains(&var) {
117                    done.push(JsValue::unknown(
118                        JsValue::Variable(var.clone()),
119                        false,
120                        rcstr!("circular variable reference"),
121                    ));
122                } else {
123                    total_nodes -= 1;
124                    let var_cache_lock = (cycle_stack.is_empty()
125                        && fun_args_values.lock().is_empty())
126                    .then(|| var_cache.lock());
127                    if let Some(val) = var_cache_lock.as_deref().and_then(|cache| cache.get(&var)) {
128                        total_nodes += val.total_nodes();
129                        done.push(val.clone_in(arena.get_or_default()));
130                    } else if let Some(value) = graph.values.get(&var) {
131                        cycle_stack.insert(var.clone());
132                        work_queue_stack.push(Step::LeaveVar(var));
133                        total_nodes += value.total_nodes();
134                        work_queue_stack.push(Step::Enter(value.clone_in(arena.get_or_default())));
135                    } else {
136                        total_nodes += 1;
137                        done.push(JsValue::unknown(
138                            JsValue::Variable(var.clone()),
139                            false,
140                            rcstr!("no value of this variable analyzed"),
141                        ));
142                    }
143                };
144            }
145            // Leave a variable
146            Step::LeaveVar(var) => {
147                cycle_stack.remove(&var);
148                if cycle_stack.is_empty() && fun_args_values.lock().is_empty() {
149                    var_cache
150                        .lock()
151                        .insert(var, done.last().unwrap().clone_in(arena.get_or_default()));
152                }
153            }
154            // Enter a function argument
155            // We want to replace the argument with the value from the function call
156            Step::Enter(JsValue::Argument(func_ident, index)) => {
157                total_nodes -= 1;
158                if let Some(args) = fun_args_values.lock().get(&func_ident) {
159                    if let Some(val) = args.get(index) {
160                        total_nodes += val.total_nodes();
161                        done.push(val.clone_in(arena.get_or_default()));
162                    } else {
163                        total_nodes += 1;
164                        done.push(JsValue::unknown_empty(
165                            false,
166                            rcstr!("unknown function argument (out of bounds)"),
167                        ));
168                    }
169                } else {
170                    total_nodes += 1;
171                    done.push(JsValue::unknown(
172                        JsValue::Argument(func_ident, index),
173                        false,
174                        rcstr!("function calls are not analyzed yet"),
175                    ));
176                }
177            }
178            // Visit a function call
179            // This need special handling, since we want to replace the function call and process
180            // the function return value after that.
181            Step::Visit(JsValue::Call(_, call))
182                if matches!(call.callee(), JsValue::Function(..)) =>
183            {
184                let (callee, args) = call.into_parts();
185                let JsValue::Function(function_nodes, func_ident, mut return_value) = callee else {
186                    unreachable!()
187                };
188                total_nodes -= 2; // Call + Function
189                if let Entry::Vacant(entry) = fun_args_values.lock().entry(func_ident) {
190                    // Return value will stay in total_nodes
191                    for arg in args.iter() {
192                        total_nodes -= arg.total_nodes();
193                    }
194                    entry.insert(args);
195                    work_queue_stack.push(Step::LeaveCall(func_ident));
196                    work_queue_stack.push(Step::Enter(take(&mut *return_value)));
197                } else {
198                    total_nodes -= return_value.total_nodes();
199                    for arg in args.iter() {
200                        total_nodes -= arg.total_nodes();
201                    }
202                    total_nodes += 1;
203                    done.push(JsValue::unknown(
204                        JsValue::call_from_parts(
205                            arena.get_or_default(),
206                            JsValue::Function(function_nodes, func_ident, return_value),
207                            args,
208                        ),
209                        true,
210                        rcstr!("recursive function call"),
211                    ));
212                }
213            }
214            // Leaving a function call evaluation
215            // - remove function arguments from the map
216            Step::LeaveCall(func_ident) => {
217                fun_args_values.lock().remove(&func_ident);
218            }
219            // Enter a function
220            // We don't want to process the function return value yet, this will happen after
221            // function calls
222            // - just put it into done
223            Step::Enter(func @ JsValue::Function(..)) => {
224                done.push(func);
225            }
226            // Enter a value
227            // - take and queue children for processing
228            // - on leave: insert children again and optimize
229            Step::Enter(mut val) => {
230                if !val.has_children() {
231                    visit(
232                        arena,
233                        &mut total_nodes,
234                        &mut done,
235                        &mut work_queue_stack,
236                        visitor,
237                        val,
238                    )
239                    .await?;
240                } else {
241                    let i = work_queue_stack.len();
242                    work_queue_stack.push(Step::TemporarySlot);
243                    let mut has_early_children = false;
244                    val.for_each_early_children_mut(&mut |child| {
245                        has_early_children = true;
246                        work_queue_stack.push(Step::Enter(take(child)));
247                        false
248                    });
249                    if has_early_children {
250                        work_queue_stack[i] = Step::EarlyVisit(val);
251                    } else {
252                        val.for_each_children_mut(&mut |child| {
253                            work_queue_stack.push(Step::Enter(take(child)));
254                            false
255                        });
256                        work_queue_stack[i] = Step::Leave(val);
257                    }
258                }
259            }
260            // Early visit a value
261            // - reconstruct the value from early children
262            // - visit the value
263            // - insert late children and process for Leave
264            Step::EarlyVisit(mut val) => {
265                val.for_each_early_children_mut(&mut |child| {
266                    let val = done.pop().unwrap();
267                    *child = val;
268                    true
269                });
270                val.debug_assert_total_nodes_up_to_date();
271                total_nodes -= val.total_nodes();
272                if val.total_nodes() > LIMIT_NODE_SIZE {
273                    total_nodes += 1;
274                    done.push(JsValue::unknown_empty(true, rcstr!("node limit reached")));
275                    continue;
276                }
277
278                let (mut val, visit_modified) = early_visitor(val).await?;
279                val.debug_assert_total_nodes_up_to_date();
280                if visit_modified && val.total_nodes() > LIMIT_NODE_SIZE {
281                    total_nodes += 1;
282                    done.push(JsValue::unknown_empty(true, rcstr!("node limit reached")));
283                    continue;
284                }
285
286                let count = val.total_nodes();
287                if total_nodes + count > LIMIT_IN_PROGRESS_NODES {
288                    // There is always space for one more node since we just popped at least one
289                    // count
290                    total_nodes += 1;
291                    done.push(JsValue::unknown_empty(
292                        true,
293                        rcstr!("in progress nodes limit reached"),
294                    ));
295                    continue;
296                }
297                total_nodes += count;
298
299                if visit_modified {
300                    // When the early visitor has changed the value, we need to enter it again
301                    work_queue_stack.push(Step::Enter(val));
302                } else {
303                    // Otherwise we can just process the late children
304                    let i = work_queue_stack.len();
305                    work_queue_stack.push(Step::TemporarySlot);
306                    val.for_each_late_children_mut(&mut |child| {
307                        work_queue_stack.push(Step::Enter(take(child)));
308                        false
309                    });
310                    work_queue_stack[i] = Step::LeaveLate(val);
311                }
312            }
313            // Leave a value
314            Step::Leave(mut val) => {
315                val.for_each_children_mut(&mut |child| {
316                    let val = done.pop().unwrap();
317                    *child = val;
318                    true
319                });
320                val.debug_assert_total_nodes_up_to_date();
321
322                total_nodes -= val.total_nodes();
323
324                if val.total_nodes() > LIMIT_NODE_SIZE {
325                    total_nodes += 1;
326                    done.push(JsValue::unknown_empty(true, rcstr!("node limit reached")));
327                    continue;
328                }
329                val.normalize_shallow(arena.get_or_default());
330
331                val.debug_assert_total_nodes_up_to_date();
332
333                total_nodes += val.total_nodes();
334                work_queue_stack.push(Step::Visit(val));
335            }
336            // Leave a value from EarlyVisit
337            Step::LeaveLate(mut val) => {
338                val.for_each_late_children_mut(&mut |child| {
339                    let val = done.pop().unwrap();
340                    *child = val;
341                    true
342                });
343                val.debug_assert_total_nodes_up_to_date();
344
345                total_nodes -= val.total_nodes();
346
347                if val.total_nodes() > LIMIT_NODE_SIZE {
348                    total_nodes += 1;
349                    done.push(JsValue::unknown_empty(true, rcstr!("node limit reached")));
350                    continue;
351                }
352                val.normalize_shallow(arena.get_or_default());
353
354                val.debug_assert_total_nodes_up_to_date();
355
356                total_nodes += val.total_nodes();
357                work_queue_stack.push(Step::Visit(val));
358            }
359            // Visit a value with the visitor
360            // - visited value is put into done
361            Step::Visit(val) => {
362                visit(
363                    arena,
364                    &mut total_nodes,
365                    &mut done,
366                    &mut work_queue_stack,
367                    visitor,
368                    val,
369                )
370                .await?;
371            }
372            Step::TemporarySlot => unreachable!(),
373        }
374
375        if steps > LIMIT_LINK_STEPS {
376            // Unroll the stack and apply steps that modify "global" state.
377            for step in work_queue_stack.into_iter().rev() {
378                match step {
379                    Step::LeaveVar(var) => {
380                        cycle_stack.remove(&var);
381                        if cycle_stack.is_empty() && fun_args_values.lock().is_empty() {
382                            var_cache.lock().insert(
383                                var,
384                                JsValue::unknown_empty(
385                                    true,
386                                    rcstr!("max number of linking steps reached"),
387                                ),
388                            );
389                        }
390                    }
391                    Step::LeaveCall(func_ident) => {
392                        fun_args_values.lock().remove(&func_ident);
393                    }
394                    _ => {}
395                }
396            }
397
398            tracing::trace!("link limit hit {}", steps);
399            return Ok((
400                JsValue::unknown_empty(true, rcstr!("max number of linking steps reached")),
401                steps,
402            ));
403        }
404    }
405
406    let final_value = done.pop().unwrap();
407
408    debug_assert!(work_queue_stack.is_empty());
409    debug_assert_eq!(total_nodes, final_value.total_nodes());
410
411    Ok((final_value, steps))
412}
413
414async fn visit<'a, 'l, F, RF>(
415    arena: &'a ThreadLocal<Bump>,
416    total_nodes: &mut u32,
417    done: &mut Vec<JsValue<'a>>,
418    work_queue_stack: &mut Vec<Step<'a>>,
419    visitor: &'l F,
420    val: JsValue<'a>,
421) -> Result<()>
422where
423    RF: 'l + Future<Output = Result<(JsValue<'a>, bool)>> + Send,
424    F: 'l + Fn(JsValue<'a>) -> RF + Sync,
425{
426    *total_nodes -= val.total_nodes();
427
428    let (mut val, visit_modified) = visitor(val).await?;
429    if visit_modified {
430        val.normalize_shallow(arena.get_or_default());
431        #[cfg(debug_assertions)]
432        val.debug_assert_total_nodes_up_to_date();
433        if val.total_nodes() > LIMIT_NODE_SIZE {
434            *total_nodes += 1;
435            done.push(JsValue::unknown_empty(true, rcstr!("node limit reached")));
436            return Ok(());
437        }
438    }
439
440    let count = val.total_nodes();
441    if *total_nodes + count > LIMIT_IN_PROGRESS_NODES {
442        // There is always space for one more node since we just popped at least one
443        // count
444        *total_nodes += 1;
445        done.push(JsValue::unknown_empty(
446            true,
447            rcstr!("in progress nodes limit reached"),
448        ));
449        return Ok(());
450    }
451    *total_nodes += count;
452    if visit_modified {
453        work_queue_stack.push(Step::Enter(val));
454    } else {
455        done.push(val);
456    }
457    Ok(())
458}
turbopack_ecmascript/analyzer/linker.rs

turbopack_ecmascript/analyzer/
linker.rs
