chomsky-uir 0.0.0

Universal Intermediate Representation (UIR) for Chomsky framework based on E-Graph
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

use dashmap::DashMap;

pub type Id = usize;

#[derive(Debug, Clone, Default)]
pub struct UnionFind {
    pub parents: DashMap<Id, Id>,
}

impl UnionFind {
    pub fn new() -> Self {
        Self {
            parents: DashMap::new(),
        }
    }

    pub fn find(&self, i: Id) -> Id {
        if !self.parents.contains_key(&i) {
            self.parents.insert(i, i);
            return i;
        }

        let mut curr = i;
        let mut path = Vec::new();
        while let Some(p) = self.parents.get(&curr) {
            if *p == curr {
                break;
            }
            path.push(curr);
            curr = *p;
        }

        for id in path {
            self.parents.insert(id, curr);
        }
        curr
    }

    pub fn union(&self, i: Id, j: Id) -> Id {
        let root_i = self.find(i);
        let root_j = self.find(j);
        if root_i != root_j {
            self.parents.insert(root_i, root_j);
        }
        root_j
    }
}