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
//! Faithful port of `Luau::detail::prune`
//! (`Analysis/src/TopoSortStatements.cpp:386-401`).
//!
//! ```cpp
//! // Clip arcs to and from the node
//! void prune(Node* next)
//! {
//! for (const auto& node : next->provides)
//! {
//! auto it = node->depends.find(next);
//! LUAU_ASSERT(it != node->depends.end());
//! node->depends.erase(it);
//! }
//!
//! for (const auto& node : next->depends)
//! {
//! auto it = node->provides.find(next);
//! LUAU_ASSERT(it != node->provides.end());
//! node->provides.erase(it);
//! }
//! }
//! ```
use crate::records::node::Node;
use luaur_common::macros::luau_assert::LUAU_ASSERT;
/// Clip arcs to and from the node.
///
/// # Safety
/// `next` and every pointer reachable through its `provides` / `depends` sets
/// must be live `Node`s. None of the visited nodes alias `next` (the graph has
/// no self-edges), so erasing `next` from their sets is sound.
pub fn prune(next: *mut Node) {
// The C++ loops iterate `next->provides` / `next->depends` (which are never
// mutated here) while erasing `next` from *other* nodes' sets. Snapshot the
// pointer sets first so the mutation of the neighbours cannot alias the
// borrow of `next`.
let provides: alloc::vec::Vec<*mut Node> =
unsafe { (*next).provides.iter().copied().collect() };
let depends: alloc::vec::Vec<*mut Node> = unsafe { (*next).depends.iter().copied().collect() };
for node in provides {
let removed = unsafe { (*node).depends.remove(&next) };
LUAU_ASSERT!(removed);
}
for node in depends {
let removed = unsafe { (*node).provides.remove(&next) };
LUAU_ASSERT!(removed);
}
}