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
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

use codespan::FileId;
use codespan_reporting::diagnostic::Label;

use crate::{
    ast::Schema,
    ctx::Ctx,
    util::sorted_map::{sorted_map, SortedMap, SortedSet},
};

#[derive(Default)]
pub struct AstMap {
    asts: SortedMap<FileId, (Schema, Vec<FileId>)>,
}

impl AstMap {
    pub fn get_file(&self, file_id: FileId) -> Option<&Schema> {
        Some(&self.asts.get(&file_id)?.0)
    }

    pub fn add_files_recursively(&mut self, ctx: &mut Ctx, file_id: FileId) {
        let mut queue = vec![file_id];

        while let Some(file_id) = queue.pop() {
            match self.asts.entry(file_id) {
                sorted_map::Entry::Occupied(_) => continue,
                sorted_map::Entry::Vacant(entry) => {
                    if let Some(cst) = ctx.parse_file(file_id) {
                        let ast = crate::ast::convert::convert(ctx, file_id, cst);
                        let dependencies = ast
                            .includes
                            .iter()
                            .filter_map(|literal| {
                                ctx.add_relative_path(
                                    file_id,
                                    &literal.value,
                                    [Label::primary(file_id, literal.span)],
                                )
                            })
                            .collect::<Vec<_>>();
                        queue.extend_from_slice(&dependencies);
                        entry.insert((ast, dependencies));
                    }
                }
            }
        }
    }

    pub fn iter(&self) -> impl Iterator<Item = &Schema> {
        self.asts.values().map(|(schema, _)| schema)
    }

    pub fn reachability(&self) -> SortedMap<FileId, SortedSet<FileId>> {
        let size = self.asts.len();
        let mut reachability: Vec<bool> = vec![false; size * size];
        macro_rules! get {
            ($i:expr, $j:expr) => {
                &mut reachability[$i * size + $j]
            };
        }

        for (i, (_schema, dependencies)) in self.asts.values().enumerate() {
            *get!(i, i) = true;
            for file_id in dependencies {
                if let Some(j) = self.asts.index_of(file_id) {
                    *get!(i, j) = true;
                }
            }
        }

        for k in 0..size {
            for i in 0..size {
                for j in 0..size {
                    if *get!(i, k) && *get!(k, j) {
                        *get!(i, j) = true;
                    }
                }
            }
        }

        let mut result = SortedMap::new();
        for (i, (key, _)) in self.asts.iter().enumerate() {
            let mut can_reach: SortedSet<FileId> = SortedSet::new();
            for j in 0..size {
                if *get!(i, j) {
                    can_reach.insert(self.asts.0[j].0);
                }
            }
            result.insert(*key, can_reach);
        }
        result
    }
}

#[cfg(test)]
mod tests {
    use codespan::Files;

    use super::*;

    #[test]
    fn test_floyd_warshall() {
        let mut files = Files::default();
        let file_id1 = files.add("", "");
        let file_id2 = files.add("", "");
        let file_id3 = files.add("", "");
        for (file_id1, file_id2, file_id3) in [
            (file_id1, file_id2, file_id3),
            (file_id1, file_id3, file_id2),
            (file_id2, file_id1, file_id3),
            (file_id3, file_id1, file_id2),
            (file_id2, file_id3, file_id1),
            (file_id3, file_id2, file_id1),
        ] {
            let mut asts = SortedMap::new();
            asts.insert(file_id1, (Schema::new(file_id1), vec![file_id2]));
            asts.insert(file_id2, (Schema::new(file_id2), vec![file_id3]));
            asts.insert(file_id3, (Schema::new(file_id3), vec![]));
            let reachability = AstMap { asts }.reachability();
            let mut file_id1_reach = [file_id1, file_id2, file_id3];
            let mut file_id2_reach = [file_id2, file_id3];
            let file_id3_reach = [file_id3];
            file_id1_reach.sort();
            file_id2_reach.sort();

            assert!(reachability
                .get(&file_id1)
                .unwrap()
                .iter()
                .eq(&file_id1_reach));
            assert!(reachability
                .get(&file_id2)
                .unwrap()
                .iter()
                .eq(&file_id2_reach));
            assert!(reachability
                .get(&file_id3)
                .unwrap()
                .iter()
                .eq(&file_id3_reach));
        }
    }
}