luaur_analysis/methods/
constraint_solver_run.rs

1//! `void ConstraintSolver::run()` (`Analysis/src/ConstraintSolver.cpp:506-765`,
2//! the main solver loop, hand-ported faithfully). The C++ `runSolverPass` lambda
3//! is lowered to the private `run_solver_pass` method below.
4
5use alloc::string::String;
6use core::ptr::NonNull;
7
8use crate::functions::dump_bindings::dump_bindings;
9use crate::functions::dump_constraint_solver::dump;
10use crate::functions::follow_type::follow_type_id;
11use crate::functions::to_string_to_string_alt_c::to_string_type_id;
12use crate::functions::to_string_to_string_alt_q::to_string_constraint_to_string_options;
13use crate::records::constraint::Constraint;
14use crate::records::constraint_solver::ConstraintSolver;
15use crate::records::constraint_solving_incomplete_error::ConstraintSolvingIncompleteError;
16use crate::type_aliases::constraint_vertex::ConstraintVertex;
17use crate::type_aliases::type_id::TypeId;
18use luaur_ast::records::location::Location;
19use luaur_common::records::dense_hash_set::DenseHashSet;
20use luaur_common::{FFlag, FInt};
21
22impl ConstraintSolver {
23    pub fn constraint_solver_run(&mut self) {
24        // LUAU_TIMETRACE_SCOPE("ConstraintSolver::run", "Typechecking");
25
26        if self.is_done() {
27            return;
28        }
29
30        if FFlag::DebugLuauLogSolver.get() {
31            let (human, name) = match &self.module {
32                Some(m) => (m.human_readable_name.clone(), m.name.clone()),
33                None => (String::new(), String::new()),
34            };
35            std::print!("Starting solver for module {} ({})\n", human, name);
36            let mut opts = self.opts.clone();
37            dump(self as *mut ConstraintSolver, &mut opts);
38            self.opts = opts;
39            std::print!("Bindings:\n");
40            dump_bindings(self.root_scope, &mut self.opts.clone());
41        }
42
43        if !self.logger.is_null() {
44            let unsolved = self.unsolved_constraints.clone();
45            unsafe { (*self.logger).capture_initial_solver_state(&*self.root_scope, &unsolved) };
46        }
47
48        // Free types that have no constraints at all can be generalized right away.
49        if FFlag::LuauConstraintGraph.get() {
50            luaur_common::macros::luau_assert::LUAU_ASSERT!(!self.cgraph.is_null());
51            // TODO CLI-206649: We can fold constraint set into constraint graph.
52            let free_types: alloc::vec::Vec<TypeId> = self.constraint_set.free_types.order.clone();
53            for ty in free_types {
54                if !unsafe { (*self.cgraph).has_unsolved_dependencies(ConstraintVertex::V0(ty)) } {
55                    self.generalize_one_type(ty);
56                }
57            }
58        } else {
59            let free_types: alloc::vec::Vec<TypeId> = self.constraint_set.free_types.order.clone();
60            for ty in free_types {
61                let empty = match self.deprecated_type_to_constraint_set.get(&ty) {
62                    Some(set) => set.is_empty(),
63                    None => true,
64                };
65                if empty {
66                    self.generalize_one_type(ty);
67                }
68            }
69        }
70
71        self.constraint_set.free_types.clear();
72
73        let mut progress;
74        loop {
75            progress = self.run_solver_pass(false);
76            if !progress {
77                progress |= self.run_solver_pass(true);
78            }
79            if !progress {
80                break;
81            }
82        }
83
84        if !self.unsolved_constraints.is_empty() {
85            self.report_error_type_error_data_location(
86                ConstraintSolvingIncompleteError::default().into(),
87                &Location::default(),
88            );
89        }
90
91        // After we have run all the constraints, type functions should be generalized
92        // At this point, we can try to perform one final simplification to suss out
93        // whether type functions are truly uninhabited or if they can reduce
94
95        self.constraint_solver_finalize_type_functions();
96
97        if FFlag::DebugLuauLogSolver.get() || FFlag::DebugLuauLogBindings.get() {
98            dump_bindings(self.root_scope, &mut self.opts.clone());
99        }
100
101        if !self.logger.is_null() {
102            let unsolved = self.unsolved_constraints.clone();
103            unsafe { (*self.logger).capture_final_solver_state(&*self.root_scope, &unsolved) };
104        }
105    }
106
107    /// C++ `auto runSolverPass = [&](bool force) { ... };`
108    fn run_solver_pass(&mut self, force: bool) -> bool {
109        let mut progress = false;
110
111        let mut i: usize = 0;
112        while i < self.unsolved_constraints.len() {
113            let c: *const Constraint = self.unsolved_constraints[i];
114            if FFlag::LuauConstraintGraph.get() {
115                if !force
116                    && unsafe { (*self.cgraph).has_unsolved_dependencies(ConstraintVertex::V2(c)) }
117                {
118                    i += 1;
119                    continue;
120                }
121            } else if !force && self.deprecate_d_is_blocked(c) {
122                i += 1;
123                continue;
124            }
125
126            if let Some(finish_time) = self.limits.finishTime() {
127                if luaur_common::functions::get_clock::get_clock() > finish_time {
128                    self.constraint_solver_throw_time_limit_error();
129                }
130            }
131            if let Some(token) = self.limits.cancellationToken() {
132                if token.requested() {
133                    self.constraint_solver_throw_user_cancel_error();
134                }
135            }
136
137            // If we were _given_ a limit, and the current limit has hit zero,
138            // then early exit from constraint solving.
139            if FInt::LuauSolverConstraintLimit.get() > 0 && self.solver_constraint_limit == 0 {
140                break;
141            }
142
143            let save_me: String = if FFlag::DebugLuauLogSolver.get() {
144                to_string_constraint_to_string_options(unsafe { &*c }, &mut self.opts.clone())
145            } else {
146                String::new()
147            };
148
149            let mut snapshot = None;
150            if !self.logger.is_null() {
151                let unsolved = self.unsolved_constraints.clone();
152                snapshot = Some(unsafe {
153                    (*self.logger).prepare_step_snapshot(&*self.root_scope, c, force, &unsolved)
154                });
155            }
156
157            if FFlag::DebugLuauAssertOnForcedConstraint.get() {
158                luaur_common::macros::luau_assert::LUAU_ASSERT!(!force);
159            }
160
161            let success = self.try_dispatch_not_null_constraint_bool(c, force);
162
163            progress |= success;
164
165            if success {
166                if !self.logger.is_null() {
167                    if let Some(snap) = snapshot.take() {
168                        unsafe {
169                            (*self.logger).commit_step_snapshot(
170                                luaur_common::records::variant::Variant2::V0(snap),
171                            )
172                        };
173                    }
174                }
175
176                if FFlag::LuauConstraintGraph.get() {
177                    luaur_common::macros::luau_assert::LUAU_ASSERT!(!self.cgraph.is_null());
178                    let unblock_result = unsafe {
179                        (*self.cgraph)
180                            .unblock_constraint(NonNull::new(c as *mut Constraint).unwrap())
181                    };
182
183                    // We need to handle the logger here.
184                    if !self.logger.is_null() {
185                        unsafe { (*self.logger).pop_block_not_null_constraint(c) };
186                    }
187
188                    self.unsolved_constraints.remove(i);
189
190                    let unblocked_types: alloc::vec::Vec<TypeId> =
191                        unblock_result.types.order.clone();
192                    for ty in unblocked_types {
193                        if !unsafe {
194                            (*self.cgraph).has_unsolved_dependencies(ConstraintVertex::V0(ty))
195                        } {
196                            let mut snap = None;
197                            if !self.logger.is_null() {
198                                let unsolved = self.unsolved_constraints.clone();
199                                snap = Some(unsafe {
200                                    (*self.logger).prepare_generalization_snapshot(
201                                        to_string_type_id(ty),
202                                        &*self.root_scope,
203                                        &unsolved,
204                                    )
205                                });
206                            }
207
208                            self.generalize_one_type(ty);
209
210                            if !self.logger.is_null() {
211                                if let Some(mut s) = snap.take() {
212                                    s.after = to_string_type_id(ty);
213                                    unsafe {
214                                        (*self.logger).commit_step_snapshot(
215                                            luaur_common::records::variant::Variant2::V1(s),
216                                        )
217                                    };
218                                }
219                            }
220
221                            self.unblock_type_id_location(ty, Location::default());
222                        }
223                    }
224
225                    // TODO CLI-206534: We never eagerly generalize free type
226                    // packs. Maybe we should.
227                } else {
228                    self.constraint_solver_deprecate_d_unblock(c);
229                    self.unsolved_constraints.remove(i);
230                    if let Some(entry) = self.deprecated_constraint_to_mutated_types.find(&c) {
231                        let mutated: alloc::vec::Vec<TypeId> = entry.order.clone();
232                        let mut seen: DenseHashSet<TypeId> = DenseHashSet::new(core::ptr::null());
233                        for ty in mutated {
234                            // There is a high chance that this type has been rebound
235                            // across blocked types, rebound free types, pending
236                            // expansion types, etc, so we need to follow it.
237                            let ty = unsafe { follow_type_id(ty) };
238                            if seen.contains(&ty) {
239                                continue;
240                            }
241                            seen.insert(ty);
242
243                            let present = self.deprecated_type_to_constraint_set.contains_key(&ty);
244                            if present {
245                                let (became_small, became_empty) = {
246                                    let set = self
247                                        .deprecated_type_to_constraint_set
248                                        .get_mut(&ty)
249                                        .unwrap();
250                                    set.remove(&c);
251                                    (set.len() <= 1, set.is_empty())
252                                };
253                                if became_small {
254                                    self.unblock_type_id_location(ty, Location::default());
255                                }
256
257                                if became_empty {
258                                    let mut snap = None;
259                                    if !self.logger.is_null() {
260                                        let unsolved = self.unsolved_constraints.clone();
261                                        snap = Some(unsafe {
262                                            (*self.logger).prepare_generalization_snapshot(
263                                                to_string_type_id(ty),
264                                                &*self.root_scope,
265                                                &unsolved,
266                                            )
267                                        });
268                                    }
269
270                                    self.generalize_one_type(ty);
271
272                                    if !self.logger.is_null() {
273                                        if let Some(mut s) = snap.take() {
274                                            s.after = to_string_type_id(ty);
275                                            unsafe {
276                                                (*self.logger).commit_step_snapshot(
277                                                    luaur_common::records::variant::Variant2::V1(s),
278                                                )
279                                            };
280                                        }
281                                    }
282                                }
283                            }
284                        }
285                    }
286                }
287
288                if FFlag::DebugLuauLogSolver.get() {
289                    if force {
290                        std::print!("Force ");
291                    }
292                    std::print!("Dispatched\n\t{}\n", save_me);
293
294                    if force {
295                        if FFlag::LuauConstraintGraph.get() {
296                            let mut opts = self.opts.clone();
297                            unsafe {
298                                (*self.cgraph).dump_blocked(
299                                    NonNull::new(c as *mut Constraint).unwrap(),
300                                    &mut opts,
301                                )
302                            };
303                            self.opts = opts;
304                        }
305                    }
306
307                    let mut opts = self.opts.clone();
308                    dump(self as *mut ConstraintSolver, &mut opts);
309                    self.opts = opts;
310                }
311            } else {
312                i += 1;
313            }
314
315            if force && success {
316                return true;
317            }
318        }
319
320        progress
321    }
322}
luaur_analysis/methods/constraint_solver_run.rs

luaur_analysis/methods/
constraint_solver_run.rs
