luaur_analysis/methods/
tarjan_loop.rs

1use crate::enums::tarjan_result::TarjanResult;
2use crate::records::tarjan::Tarjan;
3use luaur_common::macros::luau_assert::LUAU_ASSERT;
4
5impl Tarjan {
6    pub fn loop_item(&mut self) -> TarjanResult {
7        while !self.worklist.is_empty() {
8            let (index, mut curr_edge, mut last_edge) = {
9                let top = self.worklist.last().unwrap();
10                (top.index, top.curr_edge, top.last_edge)
11            };
12
13            // First visit
14            if curr_edge == -1 {
15                self.child_count += 1;
16                if self.child_limit > 0 && self.child_limit <= self.child_count {
17                    return TarjanResult::TooManyChildren;
18                }
19
20                self.stack.push(index);
21
22                self.nodes[index as usize].on_stack = true;
23
24                curr_edge = self.edges_ty.len() as i32;
25
26                // Fill in edge list of this vertex
27                let ty = self.nodes[index as usize].ty;
28                if !ty.is_null() {
29                    self.visit_children_type_id_i32(ty, index);
30                } else {
31                    let tp = self.nodes[index as usize].tp;
32                    if !tp.is_null() {
33                        self.visit_children_type_pack_id_i32(tp, index);
34                    }
35                }
36
37                last_edge = self.edges_ty.len() as i32;
38
39                // Persist updated curr/last edge values back into worklist entry
40                if let Some(top) = self.worklist.last_mut() {
41                    top.curr_edge = curr_edge;
42                    top.last_edge = last_edge;
43                }
44            }
45
46            // Visit children
47            let mut found_fresh = false;
48            while curr_edge < last_edge {
49                let mut child_index: i32 = -1;
50                let mut fresh = false;
51
52                let edge_ty = self.edges_ty[curr_edge as usize];
53                if !edge_ty.is_null() {
54                    let (ci, fr) = self.indexify_type_id(edge_ty);
55                    child_index = ci;
56                    fresh = fr;
57                } else {
58                    let edge_tp = self.edges_tp[curr_edge as usize];
59                    if !edge_tp.is_null() {
60                        let (ci, fr) = self.indexify_type_pack_id(edge_tp);
61                        child_index = ci;
62                        fresh = fr;
63                    } else {
64                        LUAU_ASSERT!(false);
65                    }
66                }
67
68                if fresh {
69                    // Original recursion point, update the parent continuation point and start the new element
70                    if let Some(top) = self.worklist.last_mut() {
71                        top.curr_edge = curr_edge + 1;
72                        // top.last_edge unchanged
73                    }
74                    self.worklist.push(
75                        crate::records::tarjan_worklist_vertex::TarjanWorklistVertex {
76                            index: child_index,
77                            curr_edge: -1,
78                            last_edge: -1,
79                        },
80                    );
81                    found_fresh = true;
82                    break;
83                } else if self.nodes[child_index as usize].on_stack {
84                    let ll = self.nodes[index as usize].lowlink;
85                    let other = child_index;
86                    if other < ll {
87                        self.nodes[index as usize].lowlink = other;
88                    }
89                }
90
91                self.visit_edge(child_index, index);
92
93                curr_edge += 1;
94            }
95
96            if found_fresh {
97                continue;
98            }
99
100            if self.nodes[index as usize].lowlink == index {
101                self.visit_scc(index);
102
103                while !self.stack.is_empty() {
104                    let popped = *self.stack.last().unwrap();
105                    self.stack.pop();
106
107                    self.nodes[popped as usize].on_stack = false;
108                    if popped == index {
109                        break;
110                    }
111                }
112            }
113
114            self.worklist.pop();
115
116            // Original return from recursion into a child
117            if !self.worklist.is_empty() {
118                let (parent_index, _parent_curr_edge, parent_end_edge) = {
119                    let top = self.worklist.last().unwrap();
120                    (top.index, top.curr_edge, top.last_edge)
121                };
122
123                // No need to keep child edges around
124                let new_len = parent_end_edge as usize;
125                self.edges_ty.truncate(new_len);
126                self.edges_tp.truncate(new_len);
127
128                let child_lowlink = self.nodes[index as usize].lowlink;
129                let parent_lowlink_ref = &mut self.nodes[parent_index as usize].lowlink;
130                if child_lowlink < *parent_lowlink_ref {
131                    *parent_lowlink_ref = child_lowlink;
132                }
133
134                self.visit_edge(index, parent_index);
135            }
136        }
137
138        TarjanResult::Ok
139    }
140}
luaur_analysis/methods/tarjan_loop.rs

luaur_analysis/methods/
tarjan_loop.rs
