Correctness of the new algorithm for detecting missing contexts

pmeunier

Dec 25, 2023, 11:46 AM

MMQCFCIE6XK64R3QDV3ZSPAD3POWLKHZ2ZPUJP326FDLZROSYOCQC

Dependencies

[2] OXZVZDQZ Simplification of missing context repairs
[3] VO5OQW4W Removing anyhow in libpijul
[4] ZDK3GNDB Tag transactions (including a massive refactoring of errors)
[5] SXEYMYF7 Fixing the bad changes in history (unfortunately, by rebooting).
[6] I24UEJQL Various post-fire fixes
[*] ZCPGCKKY Fixing a bug where zombie files could be deleted by unrecord, but not their contents

Change contents

edit in libpijul/src/apply.rs at line 560

[8.507]

[3.962669]

}
}

struct StackElt {
vertex: Vertex<ChangeId>,
last_alive: Vertex<ChangeId>,
is_on_path: bool,
}

impl StackElt {
fn is_alive(&self) -> bool {
self.vertex == self.last_alive
replacement in libpijul/src/apply.rs at line 580

[2.1875]→[2.1875:1937](∅→∅)

let mut stack = vec![(root.inode_vertex(), true, false)];

[2.1875]

[2.1937]

let mut stack = vec![StackElt {
vertex: root.inode_vertex(),
last_alive: root.inode_vertex(),
is_on_path: false
}];
replacement in libpijul/src/apply.rs at line 588

[3.97504]→[2.1977:2083](∅→∅)

while let Some((current, alive, on_path)) = stack.pop() {
stack.push((current, alive, true));

[3.97504]

[2.2083]

while let Some(elt) = stack.pop() {
replacement in libpijul/src/apply.rs at line 590

[2.2084]→[2.2084:2138](∅→∅)

let is_first_visit = visited.insert(current);

[2.2084]

[2.2138]

// If `current` is alive and already visited, pass.
if visited.contains(&(elt.vertex, elt.vertex)) {
continue
}

// Else, visit its children.
stack.push(StackElt { is_on_path: true, .. elt });

let is_first_visit = visited.insert((elt.vertex, elt.last_alive));
replacement in libpijul/src/apply.rs at line 601

[2.2170]→[2.2170:2192](∅→∅)

if !on_path {

[2.2170]

[2.2192]

if !elt.is_on_path {
replacement in libpijul/src/apply.rs at line 605

[2.2385]→[2.2385:2484](∅→∅)

for e in iter_adjacent(txn, channel, current, EdgeFlags::empty(), EdgeFlags::all())? {

[2.2385]

[2.2484]

for e in iter_adjacent(txn, channel, elt.vertex, EdgeFlags::empty(), EdgeFlags::all())? {
replacement in libpijul/src/apply.rs at line 611

[2.2716]→[2.2716:2765](∅→∅)

stack[len - 1].1 = true;

[2.2716]

[2.2765]

stack[len - 1].last_alive = elt.vertex;
replacement in libpijul/src/apply.rs at line 618

[2.2940]→[2.2940:2996](∅→∅)

stack.push((*child, false, false));

[2.2940]

[2.2996]

stack.push(StackElt {
vertex: *child,
last_alive: elt.last_alive,
is_on_path: false
});
replacement in libpijul/src/apply.rs at line 627

[2.3039]→[2.3039:3174](∅→∅)

if len >= 2 && stack[len - 1].1 {
if let Some(last_on_path) = (&stack[..len - 1]).iter().rev().position(|x| x.2) {

[2.3039]

[2.3174]

if len >= 2 && stack[len - 1].is_alive() {

// If `elt` is alive, it doesn't matter which part
// `last_alive` the current path comes from, we can stop
// here.
visited.remove(&(elt.vertex, elt.last_alive));
visited.insert((elt.vertex, elt.vertex));

// The visited vertex is alive. Change the last_alive of its children
for x in &mut stack[len..] {
x.last_alive = elt.vertex
}

if let Some(last_on_path) = (&stack[..len - 1]).iter().rev().position(|x| x.is_on_path) {
replacement in libpijul/src/apply.rs at line 645

[2.3352]→[2.3352:4496](∅→∅)

if !stack[last_on_path].1 {
if let Some(last_alive_on_path) =
(&stack[..last_on_path]).iter().rev().position(|x| x.1)
{
let last_alive_on_path = last_on_path - 1 - last_alive_on_path;
debug!("repair zombies {:?} {:?}", last_alive_on_path, len - 1);
// We need to reconnect, and we can do it now
// since we won't have a chance to visit that
// edge (because non-PARENT edge we are
// inserting now starts from a vertex that is
// on the path, which means we've already
// pushed all its children onto the stack.).
put_graph_with_rev(
txn,
channel,
EdgeFlags::PSEUDO,
stack[last_alive_on_path].0,
stack[len - 1].0,
ChangeId::ROOT,
)?;
}

[2.3352]

[2.4496]

if !stack[last_on_path].is_alive() {
// We need to reconnect, and we can do it now
// since we won't have a chance to visit that
// edge (because non-PARENT edge we are
// inserting now starts from a vertex that is
// on the path, which means we've already
// pushed all its children onto the stack.).
put_graph_with_rev(
txn,
channel,
EdgeFlags::PSEUDO,
elt.last_alive,
stack[len - 1].vertex,
ChangeId::ROOT,
)?;