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
//! Node: `cxx:Function:Luau.Analysis:Analysis/src/TxnLog.cpp:187:occurs`
//! Source: `Analysis/src/TxnLog.cpp:187-217` (hand-ported)
use crate::functions::follow_once::follow_once;
use crate::records::txn_log::TxnLog;
use crate::type_aliases::type_id::TypeId;
/// We must take extra care not to replace a type with a BoundType to itself. We
/// check each BoundType along the chain.
///
/// This function returns true if any of the bound types pointed at by `needle`
/// point at `haystack`.
pub fn occurs_txn_log_type_id_type_id(log: &mut TxnLog, needle: TypeId, haystack: TypeId) -> bool {
let mut tortoise: TypeId = needle;
let mut hare: TypeId = needle;
loop {
if tortoise == haystack {
return true;
}
let g = follow_once(log, tortoise);
if g.is_null() {
return false;
}
tortoise = g;
// Cycle detection: The hare steps twice for each step that the tortoise takes.
// If ever the two meet, it can only be because the track is cyclic.
// When we hit the end of the chain, hare becomes nullptr.
if !hare.is_null() {
hare = follow_once(log, hare);
if !hare.is_null() {
hare = follow_once(log, hare);
if hare == tortoise {
return true;
}
}
}
}
}