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