luaur-analysis 0.1.3

Luau type checker and type inference (Rust).
Documentation 
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

extern crate alloc;

use alloc::sync::Arc;
use alloc::vec::Vec;
use std::collections::HashMap;

use crate::records::file_resolver::FileResolver;
use crate::records::require_cycle::RequireCycle;
use crate::records::source_node::SourceNode;
use crate::type_aliases::module_name_file_resolver::ModuleName;
use luaur_common::macros::luau_assert::LUAU_ASSERT;
use luaur_common::records::dense_hash_set::DenseHashSet;

pub fn get_require_cycles(
    _resolver: &FileResolver,
    source_nodes: &HashMap<ModuleName, Arc<SourceNode>>,
    start: &SourceNode,
) -> Vec<RequireCycle> {
    let mut result: Vec<RequireCycle> = Vec::new();

    let mut seen: DenseHashSet<*const SourceNode> = DenseHashSet::new(core::ptr::null());
    let mut stack: Vec<*const SourceNode> = Vec::new();
    let mut path: Vec<*const SourceNode> = Vec::new();

    for (dep_name, dep_location) in &start.require_locations {
        let mut cycle: Vec<ModuleName> = Vec::new();

        let dit = source_nodes.get(dep_name);
        if dit.is_none() {
            continue;
        }

        stack.push(dit.unwrap().as_ref() as *const SourceNode);

        while let Some(top_ptr) = stack.pop() {
            let top: *const SourceNode = top_ptr;

            if top.is_null() {
                // special marker for post-order processing
                LUAU_ASSERT!(!path.is_empty());
                let last_path = unsafe { *path.last().unwrap() };
                path.pop();

                // we reached the node! path must form a cycle now
                if last_path == (start as *const SourceNode) {
                    for &node in &path {
                        // Safety: nodes in path are real pointers (never null)
                        cycle.push(unsafe { (*node).name.clone() });
                    }

                    // Safety: last_path is part of the cycle, so it's non-null
                    cycle.push(unsafe { (*last_path).name.clone() });
                    break;
                }
            } else if !seen.contains(&top) {
                // Safety: top is a real pointer (never null)
                seen.insert(top);

                // push marker for post-order processing
                path.push(top);
                stack.push(core::ptr::null());

                // note: we push require edges in the opposite order
                // because it's a stack, the last edge to be pushed gets processed first
                // this ensures that the cyclic path we report is the first one in DFS order
                let require_locations = unsafe { &(*top).require_locations };
                for i in (1..=require_locations.len()).rev() {
                    let req_name = &require_locations[i - 1].0;

                    let rit = source_nodes.get(req_name);
                    if let Some(rit_node) = rit {
                        stack.push(rit_node.as_ref() as *const SourceNode);
                    }
                }
            }
        }

        path.clear();
        stack.clear();

        if !cycle.is_empty() {
            // Safety: dep_location is owned by start and cycle is built from valid nodes.
            result.push(RequireCycle {
                location: dep_location.clone(),
                path: cycle,
            });

            // only clear seen vector when we find a cycle
            seen.clear();
        }
    }

    result
}