1use crate::pristine::{ChangeId, SerializedEdge, Vertex};
2use crate::{HashMap, HashSet};
3
4mod debug;
5mod dfs;
6mod output;
7pub mod retrieve;
8mod tarjan;
9pub use output::*;
10pub use retrieve::*;
11
12#[derive(Debug, Clone)]
13pub struct AliveVertex {
14 pub vertex: Vertex<ChangeId>,
15 flags: Flags,
16 pub children: usize,
17 pub n_children: usize,
18 index: usize,
19 lowlink: usize,
20 pub scc: usize,
21 pub extra: Vec<(Option<SerializedEdge>, VertexId)>,
22}
23
24pub struct Redundant {
25 pub(crate) v: Vertex<ChangeId>,
26 pub(crate) e: SerializedEdge,
27}
28
29bitflags! {
30 #[derive(PartialEq, Eq, PartialOrd, Ord, Hash, Debug, Clone, Copy)]
31 struct Flags: u8 {
32 const ZOMBIE = 4;
33 const VISITED = 2;
34 const ONSTACK = 1;
35 }
36}
37
38#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash, Ord, PartialOrd)]
39pub struct VertexId(pub usize);
40
41impl VertexId {
42 pub const DUMMY: VertexId = VertexId(0);
43}
44
45impl AliveVertex {
46 const DUMMY: AliveVertex = AliveVertex {
47 vertex: Vertex::BOTTOM,
48 flags: Flags::empty(),
49 children: 0,
50 n_children: 0,
51 index: 0,
52 lowlink: 0,
53 scc: 0,
54 extra: Vec::new(),
55 };
56
57 pub fn new(vertex: Vertex<ChangeId>) -> Self {
58 AliveVertex {
59 vertex,
60 flags: Flags::empty(),
61 children: 0,
62 n_children: 0,
63 index: 0,
64 lowlink: 0,
65 scc: 0,
66 extra: Vec::new(),
67 }
68 }
69}
70#[derive(Debug)]
71pub struct Graph {
72 pub lines: Vec<AliveVertex>,
73 pub children: Vec<(Option<SerializedEdge>, VertexId)>,
74 total_bytes: usize,
75}
76
77impl Graph {
78 pub fn len_vertices(&self) -> usize {
79 self.lines.len()
80 }
81 pub fn len_bytes(&self) -> usize {
82 self.total_bytes
83 }
84}
85
86impl std::ops::Index<VertexId> for Graph {
87 type Output = AliveVertex;
88 fn index(&self, idx: VertexId) -> &Self::Output {
89 self.lines.index(idx.0)
90 }
91}
92impl std::ops::IndexMut<VertexId> for Graph {
93 fn index_mut(&mut self, idx: VertexId) -> &mut Self::Output {
94 self.lines.index_mut(idx.0)
95 }
96}
97
98impl Graph {
99 pub fn push_child_to_last(&mut self, e: Option<SerializedEdge>, j: VertexId) {
100 let line = self.lines.last_mut().unwrap();
101 self.children.push((e, j));
102 line.n_children += 1;
103 }
104
105 pub fn children(
106 &self,
107 i: VertexId,
108 ) -> impl Iterator<Item = &(Option<SerializedEdge>, VertexId)> {
109 let line = &self[i];
110 self.children[line.children..line.children + line.n_children]
111 .iter()
112 .chain(self[i].extra.iter())
113 }
114
115 fn child(&self, i: VertexId, j: usize) -> &(Option<SerializedEdge>, VertexId) {
116 let line = &self[i];
117 if j < line.n_children {
118 &self.children[self[i].children + j]
119 } else {
120 &line.extra[j - line.n_children]
121 }
122 }
123}
124
125pub(crate) fn remove_redundant_children(
126 graph: &Graph,
127 vids: &HashMap<Vertex<ChangeId>, crate::alive::VertexId>,
128 vertices: &mut HashSet<Vertex<ChangeId>>,
129 target: Vertex<ChangeId>,
130) {
131 let mut min = usize::MAX;
132 let mut stack = Vec::new();
133 for p in vertices.iter() {
134 let vid = if let Some(vid) = vids.get(p) {
135 *vid
136 } else {
137 continue;
138 };
139 min = min.min(graph[vid].scc);
140 stack.push(vid);
141 }
142 let target_scc = if let Some(&target) = vids.get(&target) {
143 graph[target].scc
144 } else {
145 usize::MAX
146 };
147 let mut visited = HashSet::default();
148 while let Some(p) = stack.pop() {
149 if !visited.insert(p) {
150 continue;
151 }
152 for &(_, child) in graph.children(p) {
153 if graph[p].scc < target_scc && graph[p].scc != graph[child].scc {
154 assert!(graph[p].scc > graph[child].scc);
155 vertices.remove(&graph[child].vertex);
156 }
157 if graph[child].scc >= min {
158 stack.push(child);
159 }
160 }
161 }
162}
163
164pub(crate) fn remove_redundant_parents(
165 graph: &Graph,
166 vids: &HashMap<Vertex<ChangeId>, crate::alive::VertexId>,
167 vertices: &mut HashSet<Vertex<ChangeId>>,
168 covered: &mut HashSet<(Vertex<ChangeId>, Vertex<ChangeId>)>,
169 target: Vertex<ChangeId>,
170) {
171 let mut min = usize::MAX;
172 let mut stack = Vec::new();
173 for p in vertices.iter() {
174 let vid = if let Some(vid) = vids.get(p) {
175 *vid
176 } else {
177 continue;
178 };
179 min = min.min(graph[vid].scc);
180 stack.push((vid, false));
181 }
182 stack.sort_by(|(a, _), (b, _)| graph[*a].scc.cmp(&graph[*b].scc));
183 let target_scc = if let Some(&target) = vids.get(&target) {
184 graph[target].scc
185 } else {
186 0
187 };
188 let mut visited = HashSet::default();
189 while let Some((p, _)) = stack.pop() {
190 if !visited.insert(p) {
191 continue;
192 }
193 if graph[p].scc > target_scc
194 && (vertices.contains(&graph[p].vertex) || covered.contains(&(graph[p].vertex, target)))
195 {
196 for (pp, pp_on_path) in stack.iter() {
197 if graph[*pp].scc != graph[p].scc && *pp_on_path {
198 vertices.remove(&graph[*pp].vertex);
199 covered.insert((graph[*pp].vertex, target));
200 }
201 }
202 }
203 stack.push((p, true));
204 for &(_, child) in graph.children(p) {
205 if graph[child].scc >= min {
206 stack.push((child, false));
207 }
208 if graph[p].scc > target_scc
209 && graph[child].scc != graph[p].scc
210 && covered.contains(&(graph[child].vertex, target))
211 {
212 assert!(graph[child].scc < graph[p].scc);
213 vertices.remove(&graph[p].vertex);
214 covered.insert((graph[p].vertex, target));
215 }
216 }
217 }
218}