erg_compiler/module/
graph.rs

1use std::fmt;
2
3use erg_common::consts::DEBUG_MODE;
4use erg_common::dict::Dict;
5use erg_common::pathutil::NormalizedPathBuf;
6use erg_common::set;
7use erg_common::set::Set;
8use erg_common::shared::{MappedRwLockReadGuard, RwLockReadGuard, Shared};
9use erg_common::tsort::{tsort, Graph, Node, TopoSortError};
10
11#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
12pub enum IncRefError {
13    CycleDetected,
14}
15
16impl IncRefError {
17    pub const fn is_cycle_detected(&self) -> bool {
18        matches!(self, Self::CycleDetected)
19    }
20}
21
22#[derive(Debug, Clone, Default)]
23pub struct ModuleGraph {
24    graph: Graph<NormalizedPathBuf, ()>,
25    index: Dict<NormalizedPathBuf, usize>,
26}
27
28impl fmt::Display for ModuleGraph {
29    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
30        writeln!(f, "ModuleGraph {{")?;
31        for node in self.graph.iter() {
32            writeln!(f, "{} depends on {{", node.id.display())?;
33            for dep in node.depends_on.iter() {
34                writeln!(f, "{}, ", dep.display())?;
35            }
36            writeln!(f, "}}, ")?;
37        }
38        write!(f, "}}")
39    }
40}
41
42impl IntoIterator for ModuleGraph {
43    type Item = Node<NormalizedPathBuf, ()>;
44    type IntoIter = std::vec::IntoIter<Self::Item>;
45
46    fn into_iter(self) -> Self::IntoIter {
47        self.graph.into_iter()
48    }
49}
50
51impl ModuleGraph {
52    pub fn new() -> Self {
53        Self {
54            graph: Graph::new(),
55            index: Dict::new(),
56        }
57    }
58
59    pub fn get_node(&self, path: &NormalizedPathBuf) -> Option<&Node<NormalizedPathBuf, ()>> {
60        self.index.get(path).map(|&i| &self.graph[i])
61    }
62
63    pub fn get_mut_node(
64        &mut self,
65        path: &NormalizedPathBuf,
66    ) -> Option<&mut Node<NormalizedPathBuf, ()>> {
67        self.index.get(path).map(|&i| &mut self.graph[i])
68    }
69
70    /// if `path` directly depends on `target`, returns `true`, else `false`.
71    /// if `path` not found, returns `false`.
72    /// O(1)
73    pub fn depends_on(&self, path: &NormalizedPathBuf, target: &NormalizedPathBuf) -> bool {
74        let path = NormalizedPathBuf::new(path.to_path_buf());
75        let target = NormalizedPathBuf::new(target.to_path_buf());
76        self.get_node(&path)
77            .map(|n| n.depends_on.contains(&target))
78            .unwrap_or(false)
79    }
80
81    /// if `path` depends on `target`, returns `true`, else `false`.
82    /// if `path` not found, returns `false`.
83    pub fn deep_depends_on(&self, path: &NormalizedPathBuf, target: &NormalizedPathBuf) -> bool {
84        let path = NormalizedPathBuf::new(path.to_path_buf());
85        let target = NormalizedPathBuf::new(target.to_path_buf());
86        let mut visited = set! {};
87        self.deep_depends_on_(&path, &target, &mut visited)
88    }
89
90    fn deep_depends_on_<'p>(
91        &'p self,
92        path: &'p NormalizedPathBuf,
93        target: &NormalizedPathBuf,
94        visited: &mut Set<&'p NormalizedPathBuf>,
95    ) -> bool {
96        if !visited.insert(path) {
97            return false;
98        }
99        self.get_node(path)
100            .map(|n| {
101                n.depends_on.contains(target)
102                    || n.depends_on
103                        .iter()
104                        .any(|p| self.deep_depends_on_(p, target, visited))
105            })
106            .unwrap_or(false)
107    }
108
109    /// (usually) `path` is not contained.
110    /// O(N)
111    pub fn children<'p>(
112        &'p self,
113        path: &'p NormalizedPathBuf,
114    ) -> impl Iterator<Item = NormalizedPathBuf> + 'p {
115        self.graph
116            .iter()
117            .filter(|n| n.depends_on.contains(path))
118            .map(|n| n.id.clone())
119    }
120
121    /// (usually) `path` is not contained.
122    /// O(1)
123    pub fn parents(&self, path: &NormalizedPathBuf) -> Option<&Set<NormalizedPathBuf>> {
124        self.get_node(path).map(|n| &n.depends_on)
125    }
126
127    /// ```erg
128    /// # a.er
129    /// b = import "b"
130    /// # -> a: child, b: parent
131    /// # b.er
132    /// c = import "c"
133    /// # -> ancestors(a) == {b, c}
134    /// ```
135    /// O(N)
136    pub fn ancestors<'p>(&'p self, path: &'p NormalizedPathBuf) -> Set<&'p NormalizedPathBuf> {
137        let mut ancestors = set! {};
138        let mut visited = set! {};
139        self.ancestors_(path, &mut ancestors, &mut visited);
140        ancestors
141    }
142
143    fn ancestors_<'p>(
144        &'p self,
145        path: &'p NormalizedPathBuf,
146        ancestors: &mut Set<&'p NormalizedPathBuf>,
147        visited: &mut Set<&'p NormalizedPathBuf>,
148    ) {
149        if !visited.insert(path) {
150            return;
151        }
152        if let Some(parents) = self.parents(path) {
153            for parent in parents.iter() {
154                if ancestors.insert(parent) {
155                    self.ancestors_(parent, ancestors, visited);
156                }
157            }
158        }
159    }
160
161    pub fn add_node_if_none(&mut self, path: &NormalizedPathBuf) {
162        if path.is_dir() {
163            if DEBUG_MODE {
164                panic!("path is a directory: {path}");
165            }
166            return;
167        }
168        if self.index.get(path).is_none() {
169            let node = Node::new(path.clone(), (), set! {});
170            self.graph.push(node);
171            self.index.insert(path.clone(), self.graph.len() - 1);
172        }
173    }
174
175    /// returns Err (and do nothing) if this operation makes a cycle
176    pub fn inc_ref(
177        &mut self,
178        referrer: &NormalizedPathBuf,
179        depends_on: NormalizedPathBuf,
180    ) -> Result<(), IncRefError> {
181        if depends_on.is_dir() {
182            if DEBUG_MODE {
183                panic!("path is a directory: {depends_on}");
184            }
185            return Ok(());
186        }
187        self.add_node_if_none(referrer);
188        if referrer == &depends_on {
189            return Ok(());
190        }
191        if self.deep_depends_on(&depends_on, referrer) {
192            return Err(IncRefError::CycleDetected);
193        }
194        if let Some(node) = self.get_mut_node(referrer) {
195            node.push_dep(depends_on);
196        } else {
197            unreachable!("node not found: {}", referrer.display());
198        }
199        Ok(())
200    }
201
202    pub fn iter(&self) -> impl Iterator<Item = &Node<NormalizedPathBuf, ()>> {
203        self.graph.iter()
204    }
205
206    pub fn sorted(self) -> Result<Self, TopoSortError> {
207        tsort(self.graph).map(|graph| {
208            let index = graph
209                .iter()
210                .map(|n| n.id.clone())
211                .enumerate()
212                .map(|(i, path)| (path, i))
213                .collect();
214            Self { graph, index }
215        })
216    }
217
218    #[allow(clippy::result_unit_err)]
219    pub fn sort(&mut self) -> Result<(), TopoSortError> {
220        *self = std::mem::take(self).sorted()?;
221        Ok(())
222    }
223
224    /// Do not erase relationships with modules that depend on `path`.
225    /// O(N)
226    pub fn remove(&mut self, path: &NormalizedPathBuf) {
227        if let Some(&i) = self.index.get(path) {
228            self.graph.remove(i);
229            self.index.remove(path);
230            // shift indices
231            for index in self.index.values_mut() {
232                if *index > i {
233                    *index -= 1;
234                }
235            }
236        }
237        for node in self.graph.iter_mut() {
238            node.depends_on.retain(|p| p != path);
239        }
240    }
241
242    /// O(N)
243    pub fn rename_path(&mut self, old: &NormalizedPathBuf, new: NormalizedPathBuf) {
244        for node in self.graph.iter_mut() {
245            if &node.id == old {
246                node.id = new.clone();
247            }
248            if node.depends_on.contains(old) {
249                node.depends_on.insert(new.clone());
250            }
251            node.depends_on.retain(|p| p != old);
252        }
253    }
254
255    pub fn initialize(&mut self) {
256        self.graph.clear();
257        self.index.clear();
258    }
259
260    pub fn display_parents(
261        &self,
262        lev: usize,
263        id: &NormalizedPathBuf,
264        appeared: &mut Set<NormalizedPathBuf>,
265    ) -> String {
266        let mut s = String::new();
267        let Some(parents) = self.parents(id) else {
268            return s;
269        };
270        for parent in parents.iter() {
271            s.push_str(&format!("{}-> {}\n", "    ".repeat(lev), parent.display()));
272            if appeared.contains(parent) {
273                continue;
274            }
275            s.push_str(&self.display_parents(lev + 1, parent, appeared));
276            appeared.insert(parent.clone());
277        }
278        s
279    }
280
281    pub fn display(&self) -> String {
282        let mut s = String::new();
283        let mut appeared = set! {};
284        for node in self.graph.iter() {
285            let mut children = self.children(&node.id);
286            if children.next().is_some() || appeared.contains(&node.id) {
287                continue;
288            }
289            s.push_str(&format!("{}\n", node.id.display()));
290            s.push_str(&self.display_parents(1, &node.id, &mut appeared));
291            appeared.insert(node.id.clone());
292        }
293        s
294    }
295}
296
297#[derive(Debug, Clone, Default)]
298pub struct SharedModuleGraph(Shared<ModuleGraph>);
299
300impl fmt::Display for SharedModuleGraph {
301    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
302        write!(f, "{}", self.0.borrow())
303    }
304}
305
306impl IntoIterator for SharedModuleGraph {
307    type Item = Node<NormalizedPathBuf, ()>;
308    type IntoIter = std::vec::IntoIter<Self::Item>;
309
310    fn into_iter(self) -> Self::IntoIter {
311        self.0.into_inner().into_iter()
312    }
313}
314
315impl SharedModuleGraph {
316    pub fn new() -> Self {
317        Self(Shared::new(ModuleGraph::new()))
318    }
319
320    pub fn get_node(
321        &self,
322        path: &NormalizedPathBuf,
323    ) -> Option<MappedRwLockReadGuard<'_, Node<NormalizedPathBuf, ()>>> {
324        RwLockReadGuard::try_map(self.0.borrow(), |graph| graph.get_node(path)).ok()
325    }
326
327    /// if `path` directly depends on `target`, returns `true`, else `false`.
328    /// if `path` not found, returns `false`.
329    /// O(1)
330    pub fn depends_on(&self, path: &NormalizedPathBuf, target: &NormalizedPathBuf) -> bool {
331        self.0.borrow().depends_on(path, target)
332    }
333
334    pub fn deep_depends_on(&self, path: &NormalizedPathBuf, target: &NormalizedPathBuf) -> bool {
335        self.0.borrow().deep_depends_on(path, target)
336    }
337
338    /// (usually) `path` is not contained.
339    /// O(N)
340    pub fn children(&self, path: &NormalizedPathBuf) -> Set<NormalizedPathBuf> {
341        self.0.borrow().children(path).collect()
342    }
343
344    /// (usually) `path` is not contained.
345    /// O(N)
346    pub fn ancestors(&self, path: &NormalizedPathBuf) -> Set<NormalizedPathBuf> {
347        self.0.borrow().ancestors(path).cloned()
348    }
349
350    pub fn add_node_if_none(&self, path: &NormalizedPathBuf) {
351        self.0.borrow_mut().add_node_if_none(path);
352    }
353
354    pub fn inc_ref(
355        &self,
356        referrer: &NormalizedPathBuf,
357        depends_on: NormalizedPathBuf,
358    ) -> Result<(), IncRefError> {
359        self.0.borrow_mut().inc_ref(referrer, depends_on)
360    }
361
362    pub fn ref_inner(&self) -> RwLockReadGuard<'_, ModuleGraph> {
363        self.0.borrow()
364    }
365
366    pub fn remove(&self, path: &NormalizedPathBuf) {
367        self.0.borrow_mut().remove(path);
368    }
369
370    pub fn rename_path(&self, old: &NormalizedPathBuf, new: NormalizedPathBuf) {
371        self.0.borrow_mut().rename_path(old, new);
372    }
373
374    #[allow(clippy::result_unit_err)]
375    pub fn sort(&self) -> Result<(), TopoSortError> {
376        self.0.borrow_mut().sort()
377    }
378
379    pub fn entries(&self) -> Set<NormalizedPathBuf> {
380        self.0.borrow().iter().map(|n| n.id.clone()).collect()
381    }
382
383    pub fn initialize(&self) {
384        self.0.borrow_mut().initialize();
385    }
386
387    pub fn clone_inner(&self) -> ModuleGraph {
388        self.0.borrow().clone()
389    }
390
391    pub fn display(&self) -> String {
392        self.0.borrow().display()
393    }
394}
erg_compiler/module/graph.rs

erg_compiler/module/
graph.rs
