Mixed zombie/order conflicts: fixing the bottom vertex

pmeunier

Feb 9, 2024, 3:32 PM

H5DIAL52H2LOXEL4JO7YGBYVNZBFOQFQ2UCGFL2KDUEDLCVGQBSQC

Dependencies

• [2] QWIYNMI5 Formatting + big-endian Sanakirja
• [3] MMQCFCIE Correctness of the new algorithm for detecting missing contexts
• [4] AHAXT26R repair_zombies: do not add pseudo-edges from FOLDER vertices
• [5] VO5OQW4W Removing anyhow in libpijul
• [6] OXZVZDQZ Simplification of missing context repairs
• [*] SXEYMYF7 Fixing the bad changes in history (unfortunately, by rebooting).
• [*] I24UEJQL Various post-fire fixes

Change contents

• edit in libpijul/src/pristine/vertex.rs at line 40
  [8.526060]

  [8.526060]
  + pub const MAX: Vertex<ChangeId> = Vertex {

  + // u64::MAX is the maximum both for LE and BE byte orders.

  + change: ChangeId(L64(u64::MAX)),

  + start: ChangePosition(L64(u64::MAX)),

  + end: ChangePosition(L64(u64::MAX)),

  + };

  +
• edit in libpijul/src/apply.rs at line 8
  [9.89919]

  [3.93395]
  + use std::collections::BTreeSet;
• edit in libpijul/src/apply.rs at line 564
  [3.9]

  [3.9]
  + #[derive(Debug)]
• replacement in libpijul/src/apply.rs at line 588
  [3.1938]→[3.1938:1976](∅→∅)
  − let mut visited = HashSet::new();
  [3.1938]

  [3.97503]
  + let mut visited = BTreeSet::new();

  + let mut descendants = BTreeSet::new();
• replacement in libpijul/src/apply.rs at line 592
  [3.2084]→[3.395:512](∅→∅)
  − // If `current` is alive and already visited, pass.

  − if visited.contains(&(elt.vertex, elt.vertex)) {
  [3.394]

  [2.35835]
  + debug!("elt {:?}", elt);

  + if elt.is_on_path {

  + continue;

  + }

  +

  + // Has this vertex been visited already?

  + debug!("visited {:?}", visited);

  + if !visited.insert(elt.vertex) {

  + debug!("already visited!");

  + debug!("descendants {:#?}", descendants);

  + for (_, r) in descendants.range((elt.vertex, Vertex::ROOT)..=(elt.vertex, Vertex::MAX))

  + {

  + put_graph_with_rev(

  + txn,

  + channel,

  + EdgeFlags::PSEUDO,

  + elt.last_alive,

  + *r,

  + ChangeId::ROOT,

  + )?;

  + }

  +
• edit in libpijul/src/apply.rs at line 622
  [2.35948]→[3.640:716](∅→∅),[3.640]→[3.640:716](∅→∅)
  −

  − let is_first_visit = visited.insert((elt.vertex, elt.last_alive));
• replacement in libpijul/src/apply.rs at line 624
  [3.2170]→[3.717:746](∅→∅),[3.746]→[3.2192:2385](∅→∅),[3.2192]→[3.2192:2385](∅→∅),[3.2385]→[2.35949:36146](∅→∅),[3.849]→[3.2484:2512](∅→∅),[2.36146]→[3.2484:2512](∅→∅),[3.2484]→[3.2484:2512](∅→∅)
  − if !elt.is_on_path {

  − // If this is the first visit, find the children, starting

  − // with in flag order (alive first), since we don't want

  − // to reconnect vertices multiple times.

  − for e in iter_adjacent(

  − txn,

  − channel,

  − elt.vertex,

  − EdgeFlags::empty(),

  − EdgeFlags::all(),

  − )? {

  − let e = e?;
  [3.2170]

  [3.2512]
  + // If this is the first visit, find the children, in flag

  + // order (alive first), since we don't want to reconnect

  + // vertices multiple times.

  + for e in iter_adjacent(

  + txn,

  + channel,

  + elt.vertex,

  + EdgeFlags::empty(),

  + EdgeFlags::all(),

  + )? {

  + let e = e?;
• replacement in libpijul/src/apply.rs at line 636
  [3.2513]→[3.2513:2716](∅→∅),[3.2716]→[3.850:914](∅→∅),[3.914]→[3.2765:2817](∅→∅),[3.2765]→[3.2765:2817](∅→∅),[3.2817]→[3.0:185](∅→∅),[3.185]→[2.36147:36182](∅→∅),[3.219]→[3.2817:2835](∅→∅),[2.36182]→[3.2817:2835](∅→∅),[3.2817]→[3.2817:2835](∅→∅),[3.2835]→[3.2835:2836](∅→∅),[3.2836]→[3.2836:2940](∅→∅),[3.2940]→[3.915:1049](∅→∅),[3.1049]→[2.36183:36226](∅→∅),[2.36226]→[3.1091:1115](∅→∅),[3.1091]→[3.1091:1115](∅→∅)
  − if e.flag().contains(EdgeFlags::PARENT) {

  − if e.flag() & (EdgeFlags::BLOCK | EdgeFlags::DELETED) == EdgeFlags::BLOCK {

  − // This vertex is alive!

  − stack[len - 1].last_alive = elt.vertex;

  − }

  − continue;

  − } else if e.flag().contains(EdgeFlags::FOLDER) {

  − // If we are here, at least one children of `root`

  − // is FOLDER, hence all are.

  − return Ok(());

  − }

  −

  − if is_first_visit {

  − let child = txn.find_block(channel, e.dest())?;

  − stack.push(StackElt {

  − vertex: *child,

  − last_alive: elt.last_alive,

  − is_on_path: false,

  − });
  [3.2513]

  [3.2996]
  + if e.flag().contains(EdgeFlags::PARENT) {

  + if e.flag() & (EdgeFlags::BLOCK | EdgeFlags::DELETED) == EdgeFlags::BLOCK {

  + // This vertex is alive!

  + stack[len - 1].last_alive = elt.vertex;
• edit in libpijul/src/apply.rs at line 641
  [3.3014]

  [3.3014]
  + continue;

  + } else if e.flag().contains(EdgeFlags::FOLDER) {

  + // If we are here, at least one child of `root` is

  + // FOLDER, hence all are.

  + return Ok(());
• edit in libpijul/src/apply.rs at line 647
  [3.3028]

  [3.3028]
  +

  + let child = txn.find_block(channel, e.dest())?;

  + stack.push(StackElt {

  + vertex: *child,

  + last_alive: elt.last_alive,

  + is_on_path: false,

  + });
• edit in libpijul/src/apply.rs at line 657
  [3.1168]→[3.1168:1435](∅→∅)
  − // 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));

  −
• replacement in libpijul/src/apply.rs at line 662
  [3.1615]→[2.36227:36341](∅→∅),[3.1718]→[3.3174:3352](∅→∅),[2.36341]→[3.3174:3352](∅→∅),[3.3174]→[3.3174:3352](∅→∅),[3.3352]→[3.1719:2453](∅→∅)
  − if let Some(last_on_path) = (&stack[..len - 1]).iter().rev().position(|x| x.is_on_path)

  − {

  − let last_on_path = len - 2 - last_on_path;

  − // If the last vertex on the path to `current` is not

  − // alive, a reconnect is needed.

  − 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,

  − )?;
  [3.1615]

  [3.4496]
  + for v in (&stack[..len - 1]).iter().rev() {

  + if v.is_on_path {

  + // If the last vertex on the path to `current` is not

  + // alive, a reconnect is needed.

  + if v.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,

  + )?;

  + break;

  + } else {

  + // Remember that those dead vertices have

  + // `stack[len-1].vertex` as a descendant.

  + descendants.insert((v.vertex, stack[len - 1].vertex));

  + }