1 use super::LocalApplyError;
2 use crate::change::NewEdge;
3 use crate::missing_context::*;
4 use crate::pristine::*;
5
put_newedge<T, F, K>( txn: &mut T, graph: &mut T::Graph, ws: &mut super::Workspace, change: ChangeId, inode: Position<Option<Hash>>, n: &NewEdge<Option<Hash>>, apply_check: F, mut known: K, ) -> Result<(), LocalApplyError<T::GraphError>> where T: GraphMutTxnT, F: Fn(Vertex<ChangeId>, Vertex<ChangeId>) -> bool, K: FnMut(&Hash) -> bool,6 pub fn put_newedge<T, F, K>(
7 txn: &mut T,
8 graph: &mut T::Graph,
9 ws: &mut super::Workspace,
10 change: ChangeId,
11 inode: Position<Option<Hash>>,
12 n: &NewEdge<Option<Hash>>,
13 apply_check: F,
14 mut known: K,
15 ) -> Result<(), LocalApplyError<T::GraphError>>
16 where
17 T: GraphMutTxnT,
18 F: Fn(Vertex<ChangeId>, Vertex<ChangeId>) -> bool,
19 K: FnMut(&Hash) -> bool,
20 {
21 debug!("put_newedge {:?} {:?}", n, change);
22 check_valid(txn, graph, inode, n, ws)?;
23 let n_introduced_by = if let Some(n) = internal(txn, &n.introduced_by, change)? {
24 n
25 } else {
26 return Err(LocalApplyError::InvalidChange.into());
27 };
28
29 let mut source = find_source_vertex(txn, graph, &n.from, change, inode, n.flag, ws)?;
30 let mut target = find_target_vertex(txn, graph, &n.to, change, inode, n.flag, ws)?;
31
32 if n.flag.contains(EdgeFlags::FOLDER) {
33 ws.missing_context.files.insert(target);
34 }
35
36 let mut zombies = Vec::new();
37
38 loop {
39 if !n.flag.contains(EdgeFlags::DELETED) {
40 collect_nondeleted_zombies::<_, _>(
41 txn,
42 graph,
43 &mut known,
44 source,
45 target,
46 &mut zombies,
47 )?;
48 }
49 if target.end > n.to.end {
50 assert!(!n.flag.contains(EdgeFlags::FOLDER));
51 ws.missing_context.graphs.split(inode, target, n.to.end);
52 txn.split_block(graph, &target, n.to.end, &mut ws.adjbuf)?;
53 target.end = n.to.end
54 }
55
56 if n.flag.contains(EdgeFlags::DELETED) {
57 debug_assert!(ws.children.is_empty());
58 debug_assert!(ws.parents.is_empty());
59 collect_pseudo_edges(txn, graph, ws, inode, target)?;
60 if !n.flag.contains(EdgeFlags::FOLDER) {
61 reconnect_pseudo_edges(txn, graph, inode, ws, target)?;
62 }
63 ws.children.clear();
64 ws.parents.clear();
65 }
66
67 del_graph_with_rev(txn, graph, n.previous, source, target, n_introduced_by)?;
68 if apply_check(source, target) {
69 put_graph_with_rev(txn, graph, n.flag, source, target, change)?;
70 for intro in zombies.drain(..) {
71 put_graph_with_rev(txn, graph, EdgeFlags::DELETED, source, target, intro)?;
72 }
73 }
74
75 if target.end >= n.to.end {
76 debug!("{:?} {:?}", target, n.to);
77 debug_assert_eq!(target.end, n.to.end);
78 break;
79 }
80
81 source = target;
82 target = *txn
83 .find_block(graph, target.end_pos())
84 .map_err(LocalApplyError::from)?;
85 assert_ne!(source, target);
86
87 if !n.flag.contains(EdgeFlags::BLOCK) {
88 break;
89 }
90 }
91 if n.flag.contains(EdgeFlags::DELETED) {
92 collect_zombie_context(txn, graph, &mut ws.missing_context, inode, n, change, known)
93 .map_err(LocalApplyError::from_missing)?;
94 }
95 Ok(())
96 }
97
collect_nondeleted_zombies<T, K>( txn: &mut T, graph: &mut T::Graph, mut known: K, source: Vertex<ChangeId>, target: Vertex<ChangeId>, zombies: &mut Vec<ChangeId>, ) -> Result<(), LocalApplyError<T::GraphError>> where T: GraphMutTxnT, K: FnMut(&Hash) -> bool,98 fn collect_nondeleted_zombies<T, K>(
99 txn: &mut T,
100 graph: &mut T::Graph,
101 mut known: K,
102 source: Vertex<ChangeId>,
103 target: Vertex<ChangeId>,
104 zombies: &mut Vec<ChangeId>,
105 ) -> Result<(), LocalApplyError<T::GraphError>>
106 where
107 T: GraphMutTxnT,
108 K: FnMut(&Hash) -> bool,
109 {
110 for v in iter_deleted_parents(txn, graph, source)? {
111 let v = v?;
112 let intro = v.introduced_by();
113 if !known(&txn.get_external(&intro)?.unwrap().into()) {
114 zombies.push(intro)
115 }
116 }
117 for v in iter_adjacent(txn, graph, target, EdgeFlags::empty(), EdgeFlags::all())? {
118 let v = v?;
119 if v.flag().contains(EdgeFlags::PARENT) {
120 continue;
121 }
122 for v in iter_deleted_parents(txn, graph, target)? {
123 let v = v?;
124 let intro = v.introduced_by();
125 if !known(&txn.get_external(&intro)?.unwrap().into()) {
126 zombies.push(intro)
127 }
128 }
129 }
130 Ok(())
131 }
132
check_valid<T: GraphMutTxnT>( txn: &mut T, graph: &mut T::Graph, inode: Position<Option<Hash>>, n: &NewEdge<Option<Hash>>, ws: &mut super::Workspace, ) -> Result<(), LocalApplyError<T::GraphError>>133 fn check_valid<T: GraphMutTxnT>(
134 txn: &mut T,
135 graph: &mut T::Graph,
136 inode: Position<Option<Hash>>,
137 n: &NewEdge<Option<Hash>>,
138 ws: &mut super::Workspace,
139 ) -> Result<(), LocalApplyError<T::GraphError>> {
140 if n.flag.contains(EdgeFlags::DELETED) {
141 ws.missing_context
142 .load_graph(txn, graph, inode)
143 .map_err(|_| LocalApplyError::InvalidChange)?;
144 }
145 if (n.previous.is_block() && !n.flag.is_block())
146 || (n.previous.is_folder() != n.flag.is_folder())
147 {
148 return Err(LocalApplyError::InvalidChange.into());
149 }
150
151 debug_assert!(ws.children.is_empty());
152 debug_assert!(ws.parents.is_empty());
153 Ok(())
154 }
155
find_source_vertex<T: GraphMutTxnT>( txn: &mut T, channel: &mut T::Graph, from: &Position<Option<Hash>>, change: ChangeId, inode: Position<Option<Hash>>, flag: EdgeFlags, ws: &mut super::Workspace, ) -> Result<Vertex<ChangeId>, LocalApplyError<T::GraphError>>156 pub(crate) fn find_source_vertex<T: GraphMutTxnT>(
157 txn: &mut T,
158 channel: &mut T::Graph,
159 from: &Position<Option<Hash>>,
160 change: ChangeId,
161 inode: Position<Option<Hash>>,
162 flag: EdgeFlags,
163 ws: &mut super::Workspace,
164 ) -> Result<Vertex<ChangeId>, LocalApplyError<T::GraphError>> {
165 debug!("find_source_vertex");
166 let mut source = *txn.find_block_end(&channel, internal_pos(txn, &from, change)?)?;
167 debug!("source = {:?}", source);
168 if source.start < from.pos && source.end > from.pos {
169 assert!(!flag.contains(EdgeFlags::FOLDER));
170 ws.missing_context.graphs.split(inode, source, from.pos);
171 txn.split_block(channel, &source, from.pos, &mut ws.adjbuf)?;
172 source.end = from.pos;
173 }
174 Ok(source)
175 }
176
find_target_vertex<T: GraphMutTxnT>( txn: &mut T, channel: &mut T::Graph, to: &Vertex<Option<Hash>>, change: ChangeId, inode: Position<Option<Hash>>, flag: EdgeFlags, ws: &mut super::Workspace, ) -> Result<Vertex<ChangeId>, LocalApplyError<T::GraphError>>177 pub(crate) fn find_target_vertex<T: GraphMutTxnT>(
178 txn: &mut T,
179 channel: &mut T::Graph,
180 to: &Vertex<Option<Hash>>,
181 change: ChangeId,
182 inode: Position<Option<Hash>>,
183 flag: EdgeFlags,
184 ws: &mut super::Workspace,
185 ) -> Result<Vertex<ChangeId>, LocalApplyError<T::GraphError>> {
186 let to_pos = internal_pos(txn, &to.start_pos(), change)?;
187 debug!("find_target_vertex, to = {:?}", to);
188 let mut target = *txn.find_block(channel, to_pos)?;
189 debug!("target = {:?}", target);
190 if target.start < to.start {
191 assert!(!flag.contains(EdgeFlags::FOLDER));
192 ws.missing_context.graphs.split(inode, target, to.start);
193 txn.split_block(channel, &target, to.start, &mut ws.adjbuf)?;
194 target.start = to.start;
195 }
196 Ok(target)
197 }
198
collect_pseudo_edges<T: GraphMutTxnT>( txn: &mut T, channel: &mut T::Graph, apply: &mut super::Workspace, inode: Position<Option<Hash>>, v: Vertex<ChangeId>, ) -> Result<(), LocalApplyError<T::GraphError>>199 fn collect_pseudo_edges<T: GraphMutTxnT>(
200 txn: &mut T,
201 channel: &mut T::Graph,
202 apply: &mut super::Workspace,
203 inode: Position<Option<Hash>>,
204 v: Vertex<ChangeId>,
205 ) -> Result<(), LocalApplyError<T::GraphError>> {
206 for e in iter_adjacent(
207 txn,
208 &channel,
209 v,
210 EdgeFlags::empty(),
211 EdgeFlags::all() - EdgeFlags::DELETED,
212 )? {
213 let e = e?;
214 debug!("collect_pseudo_edges {:?} {:?}", v, e);
215 if !e.flag().contains(EdgeFlags::FOLDER) {
216 if e.flag().contains(EdgeFlags::PARENT) {
217 let p = txn.find_block_end(channel, e.dest())?;
218 if is_alive(txn, channel, p)? {
219 apply.parents.insert(*p);
220 }
221 } else {
222 let p = txn.find_block(channel, e.dest())?;
223 if e.flag().contains(EdgeFlags::BLOCK)
224 || (p.is_empty() && !e.flag().contains(EdgeFlags::PSEUDO))
225 || is_alive(txn, channel, p).unwrap()
226 {
227 apply.children.insert(*p);
228 }
229 }
230 }
231 if e.flag().contains(EdgeFlags::PSEUDO) {
232 apply.pseudo.push((v, *e, inode));
233 }
234 }
235 Ok(())
236 }
237
reconnect_pseudo_edges<T: GraphMutTxnT>( txn: &mut T, channel: &mut T::Graph, inode: Position<Option<Hash>>, ws: &mut super::Workspace, target: Vertex<ChangeId>, ) -> Result<(), LocalApplyError<T::GraphError>>238 fn reconnect_pseudo_edges<T: GraphMutTxnT>(
239 txn: &mut T,
240 channel: &mut T::Graph,
241 inode: Position<Option<Hash>>,
242 ws: &mut super::Workspace,
243 target: Vertex<ChangeId>,
244 ) -> Result<(), LocalApplyError<T::GraphError>> {
245 if ws.parents.is_empty() || ws.children.is_empty() {
246 return Ok(());
247 }
248
249 let (graph, vids) = if let Some(x) = ws.missing_context.graphs.get(inode) {
250 x
251 } else {
252 return Err(LocalApplyError::InvalidChange.into());
253 };
254
255 crate::alive::remove_redundant_parents(
256 &graph,
257 &vids,
258 &mut ws.parents,
259 &mut ws.missing_context.covered_parents,
260 target,
261 );
262 for &p in ws.parents.iter() {
263 ws.missing_context.covered_parents.insert((p, target));
264 }
265
266 crate::alive::remove_redundant_children(&graph, &vids, &mut ws.children, target);
267
268 for &p in ws.parents.iter() {
269 debug_assert!(is_alive(txn, channel, &p).unwrap());
270 for &c in ws.children.iter() {
271 if p != c {
272 debug_assert!(is_alive(txn, channel, &c).unwrap());
273 put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, p, c, ChangeId::ROOT)?;
274 }
275 }
276 }
277 Ok(())
278 }
collect_zombie_context<T: GraphMutTxnT, K>( txn: &mut T, channel: &mut T::Graph, ws: &mut crate::missing_context::Workspace, inode: Position<Option<Hash>>, n: &NewEdge<Option<Hash>>, change_id: ChangeId, mut known: K, ) -> Result<(), MissingError<T::GraphError>> where K: FnMut(&Hash) -> bool,279 fn collect_zombie_context<T: GraphMutTxnT, K>(
280 txn: &mut T,
281 channel: &mut T::Graph,
282 ws: &mut crate::missing_context::Workspace,
283 inode: Position<Option<Hash>>,
284 n: &NewEdge<Option<Hash>>,
285 change_id: ChangeId,
286 mut known: K,
287 ) -> Result<(), MissingError<T::GraphError>>
288 where
289 K: FnMut(&Hash) -> bool,
290 {
291 if n.flag.contains(EdgeFlags::FOLDER) {
292 return Ok(());
293 }
294 let mut pos = internal_pos(txn, &n.to.start_pos(), change_id)?;
295 let end_pos = internal_pos(txn, &n.to.end_pos(), change_id)?;
296 let mut unknown_parents = Vec::new();
297 while let Ok(&dest_vertex) = txn.find_block(&channel, pos) {
298 debug!("collect zombie context: {:?}", dest_vertex);
299 for v in iter_adjacent(
300 txn,
301 channel,
302 dest_vertex,
303 EdgeFlags::empty(),
304 EdgeFlags::all() - EdgeFlags::DELETED,
305 )? {
306 let v = v?;
307 if v.introduced_by() == change_id || v.dest().change.is_root() {
308 continue;
309 }
310 if v.introduced_by().is_root() {
311 ws.pseudo.push((dest_vertex, *v));
312 continue;
313 }
314 if v.flag().contains(EdgeFlags::PARENT) {
315 // Unwrap ok, since `v` is in the channel.
316 let intro = txn.get_external(&v.introduced_by())?.unwrap().into();
317 if !known(&intro) {
318 debug!("unknown: {:?}", v);
319 unknown_parents.push((dest_vertex, *v))
320 }
321 }
322 }
323 zombify(txn, channel, ws, change_id, inode, n.flag, &unknown_parents)?;
324 if dest_vertex.end < end_pos.pos {
325 pos.pos = dest_vertex.end
326 } else {
327 break;
328 }
329 }
330 Ok(())
331 }
332
zombify<T: GraphMutTxnT>( txn: &mut T, channel: &mut T::Graph, ws: &mut crate::missing_context::Workspace, change_id: ChangeId, inode: Position<Option<Hash>>, flag: EdgeFlags, unknown: &[(Vertex<ChangeId>, SerializedEdge)], ) -> Result<(), MissingError<T::GraphError>>333 fn zombify<T: GraphMutTxnT>(
334 txn: &mut T,
335 channel: &mut T::Graph,
336 ws: &mut crate::missing_context::Workspace,
337 change_id: ChangeId,
338 inode: Position<Option<Hash>>,
339 flag: EdgeFlags,
340 unknown: &[(Vertex<ChangeId>, SerializedEdge)],
341 ) -> Result<(), MissingError<T::GraphError>> {
342 for &(dest_vertex, edge) in unknown.iter() {
343 let p = *txn.find_block_end(channel, edge.dest())?;
344 ws.unknown_parents
345 .push((dest_vertex, p, inode, edge.flag()));
346 let fold = flag & EdgeFlags::FOLDER;
347 debug!("zombify p {:?}, dest_vertex {:?}", p, dest_vertex);
348 let mut v = p;
349 while let Ok(&u) = txn.find_block_end(channel, v.start_pos()) {
350 if u != v {
351 debug!("u = {:?}, v = {:?}", u, v);
352 put_graph_with_rev(
353 txn,
354 channel,
355 EdgeFlags::DELETED | EdgeFlags::BLOCK | fold,
356 u,
357 v,
358 change_id,
359 )?;
360 v = u
361 } else {
362 break;
363 }
364 }
365 // Zombify the first chunk of the split.
366 for parent in iter_adjacent(
367 txn,
368 channel,
369 v,
370 EdgeFlags::PARENT,
371 EdgeFlags::all() - EdgeFlags::DELETED,
372 )? {
373 let parent = parent?;
374 if !parent.flag().contains(EdgeFlags::PSEUDO) {
375 ws.parents.insert(*parent);
376 }
377 }
378 debug!("ws.parents = {:?}", ws.parents);
379 for parent in ws.parents.drain() {
380 let parent_dest = *txn.find_block_end(channel, parent.dest())?;
381 let mut flag = EdgeFlags::DELETED | EdgeFlags::BLOCK;
382 if parent.flag().contains(EdgeFlags::FOLDER) {
383 flag |= EdgeFlags::FOLDER
384 }
385 put_graph_with_rev(txn, channel, flag, parent_dest, v, change_id)?;
386 }
387 }
388 Ok(())
389 }
390