luaur_analysis/methods/
frontend_parse_graph.rs

1use crate::enums::mark::Mark;
2use crate::records::frontend::Frontend;
3use crate::records::source_node::SourceNode;
4use crate::records::type_check_limits::TypeCheckLimits;
5use crate::type_aliases::module_name_file_resolver::ModuleName;
6use alloc::vec::Vec;
7use luaur_common::macros::luau_assert::LUAU_ASSERT;
8use luaur_common::macros::luau_timetrace_argument::LUAU_TIMETRACE_ARGUMENT;
9use luaur_common::macros::luau_timetrace_scope::LUAU_TIMETRACE_SCOPE;
10use luaur_common::records::dense_hash_map::DenseHashMap;
11
12impl Frontend {
13    pub fn parse_graph(
14        &mut self,
15        build_queue: &mut Vec<ModuleName>,
16        root: &ModuleName,
17        limits: &TypeCheckLimits,
18        for_autocomplete: bool,
19    ) -> bool {
20        LUAU_TIMETRACE_SCOPE!("Frontend::parseGraph", "Frontend");
21        LUAU_TIMETRACE_ARGUMENT!("root", root.as_str());
22
23        let mut seen: DenseHashMap<*mut SourceNode, Mark> =
24            DenseHashMap::new(core::ptr::null_mut());
25        let mut stack: Vec<*mut SourceNode> = Vec::new();
26        let mut path: Vec<*mut SourceNode> = Vec::new();
27        let mut cyclic = false;
28
29        {
30            let (source_node, _) = self.get_source_node(root, limits);
31            if !source_node.is_null() {
32                stack.push(source_node);
33            }
34        }
35
36        while !stack.is_empty() {
37            let top = stack.pop().unwrap();
38
39            if top.is_null() {
40                // special marker for post-order processing
41                LUAU_ASSERT!(!path.is_empty());
42
43                let top = path.pop().unwrap();
44
45                // note: topseen ref gets invalidated in any seen[] access, beware - only one seen[] access per iteration!
46                let topseen = seen.get_or_insert(top);
47                LUAU_ASSERT!(*topseen == Mark::Temporary);
48                *topseen = Mark::Permanent;
49
50                build_queue.push(unsafe { (*top).name.clone() });
51
52                // at this point we know all valid dependencies are processed into SourceNodes
53                let require_set = unsafe { &(*top).require_set };
54                for dep in require_set.iter() {
55                    if let Some(source_node_arc) = self.source_nodes.get(dep) {
56                        let source_node_ref: *mut SourceNode =
57                            source_node_arc.as_ref() as *const SourceNode as *mut SourceNode;
58                        let dependents = unsafe { &mut (*source_node_ref).dependents };
59                        dependents.insert(unsafe { (*top).name.clone() });
60                    }
61                }
62            } else {
63                // note: topseen ref gets invalidated in any seen[] access, beware - only one seen[] access per iteration!
64                let topseen = seen.get_or_insert(top);
65
66                if *topseen != Mark::None {
67                    cyclic |= *topseen == Mark::Temporary;
68                    continue;
69                }
70
71                *topseen = Mark::Temporary;
72
73                // push marker for post-order processing
74                stack.push(core::ptr::null_mut());
75                path.push(top);
76
77                // push children
78                let require_set = unsafe { &(*top).require_set };
79                for dep in require_set.iter() {
80                    // Resolve the already-known SourceNode pointer (if any) in a scope so the
81                    // immutable borrow of `self.source_nodes` is released before the mutable
82                    // `self.get_source_node` call below.
83                    let known: Option<*mut SourceNode> = {
84                        if let Some(source_node_arc) = self.source_nodes.get(dep) {
85                            // this is a critical optimization: we do *not* traverse non-dirty subtrees.
86                            // this relies on the fact that markDirty marks reverse-dependencies dirty as well
87                            // thus if a node is not dirty, all its transitive deps aren't dirty, which means that they won't ever need
88                            // to be built, *and* can't form a cycle with any nodes we did process.
89                            if !source_node_arc.has_dirty_module(for_autocomplete) {
90                                None
91                            } else {
92                                Some(source_node_arc.as_ref() as *const SourceNode
93                                    as *mut SourceNode)
94                            }
95                        } else {
96                            // no SourceNode known yet; fall through to getSourceNode
97                            Some(core::ptr::null_mut())
98                        }
99                    };
100
101                    match known {
102                        // dependency is known but not dirty: skip
103                        None => continue,
104                        // dependency is known and dirty
105                        Some(ptr) if !ptr.is_null() => {
106                            // This module might already be in the outside build queue
107                            // Note: canSkip is not available in this context, so we skip this check
108
109                            // note: this check is technically redundant *except* that getSourceNode has somewhat broken memoization
110                            // calling getSourceNode twice in succession will reparse the file, since getSourceNode leaves dirty flag set
111                            if seen.contains_key(&ptr) {
112                                stack.push(ptr);
113                                continue;
114                            }
115                        }
116                        // dependency not yet resolved
117                        Some(_) => {}
118                    }
119
120                    let (source_node, _) = self.get_source_node(dep, limits);
121                    if !source_node.is_null() {
122                        stack.push(source_node);
123
124                        // note: this assignment is paired with .contains() check above and effectively deduplicates getSourceNode()
125                        seen.try_insert(source_node, Mark::None);
126                    }
127                }
128            }
129        }
130
131        cyclic
132    }
133}
luaur_analysis/methods/frontend_parse_graph.rs

luaur_analysis/methods/
frontend_parse_graph.rs
