When unrecording a deletion, the down context could be dead.
The first bug fixed here was that unrecord didn't re-detect missing contexts after unapplying the patch. This was done in apply with libpijul::apply::collect_missing_contexts, but not in unrecord.
The second bug was that the repair (for both apply and unrecord) didn't insert the extra edges needed to reconnect the broken link in some cases. In particular, when the two ends of the edge had already been visited by the "repair DFS".
HP7CKJIW6TOQZFAZKKJFF76LGE7EMQVDTRH2RWPM4POIG2WRKHBAC
4RQHY7LHPHKUWAUQEXFRHKK37RAEFR3RC2QOSUTFTGZRFVWJIVXQC
HWIOJHTRHIPEQ6KTFH53YLZDUSEYBZQBUPTWABMOG4L4HBS6DPZAC
H5DIAL52H2LOXEL4JO7YGBYVNZBFOQFQ2UCGFL2KDUEDLCVGQBSQC
3CFU4DQNHPPJC2B63RSVAVGHTQZT3RT5CCHHYC4ZM6DQ4GVQULSQC
GHO6DWPILBBTL6CVZKERJBTFL3EY6ZT4YM4E5R4S6YPGVFKFHCVAC
SXEYMYF7P4RZMZ46WPL4IZUTSQ2ATBWYZX7QNVMS3SGOYXYOHAGQC
KQTD46KVVWMJ3W6O55BEJLCVTNTDLUH6QT46AEFT7OU2SELXG4IAC
DJYHARZ7CSRMX6ZFM6P52SM2EC57VTSHWAIMFSD7Q3EL7UYZGLXQC
IXC43DSHDSXCE2X6H6N47GGVKTYM2D2BUUWF34CFWMFT6Z45NOOAC
ZJWCPRMHAYZYGCPYBTBIPBBFVCVDSFNGUL36HMC2DHCWZZKNA7PAC
L4EZSH6BBU46PVEG2HRPKIMIX7HUXUUEX5PGYYW2I3GXWKSFZAHAC
6YMDOZIB5LVYLFIDGN2WNT5JTHEAMS4TFPVDEZ3OWXWOKJOC5QDAC
ZDK3GNDBWXJ2OXFDYB72ZCEBGLBF4MKE5K3PVHDZATHJ7HJIDPRQC
CCLLB7OIFNFYJZTG3UCI7536TOCWSCSXR67VELSB466R24WLJSDAC
I24UEJQLCH2SOXA4UHIYWTRDCHSOPU7AFTRUOTX7HZIAV4AZKYEQC
YN63NUZO4LVJ7XPMURDULTXBVJKW5MVCTZ24R7Z52QMHO3HPDUVQC
ATZ3BWSEFJBLVGDUZFESRNHVCIO6ZRZ3ALPANZSVGVO7A5BUAFQQC
RSFUX6MLPHII3DRELHN62DOJCHFCDNKSRMWJDSFGTWN5S4RJVSSQC
FMLTNQ4EYXA54OGII5AX2G2I7YFDVNMTOM7GDDTCKBTWGZPABH2AC
3AMEP2Y5J6GA4AWQONF4JVA3XSR3ASLHHKMYG44R72SOUY3UQCDAC
IIV3EL2XYI2X7HZWKXEXQFAE3R3KC2Q7SGOT3Q332HSENMYVF32QC
FXEDPLRI7PXLDXV634ZA6D5Q3ZWG3ESTKJTMRPJ4MAHI7PKU3M6AC
5FI6SBEZ6RERERUAIWQJVAY66BEZ7YQOYOUNK2DPOLRGS2X326RAC
VO5OQW4W2656DIYYRNZ3PO7TQ4JOKQ3GVWE5ALUTYVMX3WMXJOYQC
I52XSRUH5RVHQBFWVMAQPTUSPAJ4KNVID2RMI3UGCVKFLYUO6WZAC
ZCPGCKKYDBXUTIYGKGRA7C43CJ2WNWH3L6Q7ETSVLYB6AE4HAGTQC
QWIYNMI5SOTLRPYE4O3AG7R75JXM2TB3ZADU646PG6ACPBGSYUYAC
OXZVZDQZEVP7NV3HS6HK5QA7RUD35ODVQ3LL7PWJHTS7DEFM3XTAC
X7OHUPL5VYT6ECER2KNGRNFLRX7SBZOM5QWSQ4PBO2UPIE7XM6MAC
GA3P7FOMATKDOGCZDYWLZJHAUNOWMRIP3BXTYFEH7PNWTTYYVLIAC
GQTC4TJABT3U6DDUBSILVUIGW2XHAHEDDT2QMJYLKT4ONSIV4PRQC
YXAVFTPP2PQAYMKGQH7QNKFVGKDI2UHVWB7SIDA4QEYSBP75ZGUQC
// does a patch introduced by an edge parallel to
// this one remove this edge from the graph?
// does a patch (call it q) other than the one (p) we're
// unrecording remove this same edge (a, b, intro) from the graph?
// This can happen e.g. if an edge is deleted twice, in which case
// this unrecord is likely to introduce a zombie conflict between
// p and q.
/// Same as crate::apply::collect_missing_contexts, but with the
/// directions reversed.
fn collect_missing_contexts<T: GraphMutTxnT + TreeTxnT>(
txn: &T,
channel: &T::Graph,
ws: &mut crate::apply::Workspace,
change: &Change,
change_id: ChangeId,
inodes: &mut HashSet<Position<ChangeId>>,
) -> Result<(), crate::apply::LocalApplyError<T>> {
debug!("collect_missing_contexts");
inodes.extend(
ws.missing_context
.unknown_parents
.drain(..)
.map(|x| internal_pos(txn, &x.2, change_id).unwrap()),
);
for atom in change.changes.iter().flat_map(|r| r.iter()) {
match atom {
// NewVertex is already collected when applying.
Atom::NewVertex(_) => {}
Atom::EdgeMap(ref n) => {
crate::apply::has_missing_edge_context(
txn, channel, change_id, change, &n, inodes, true,
)?;
}
}
}
Ok(())
}
pub(crate) graphs: Graphs,
pub(crate) covered_parents: HashSet<(Vertex<ChangeId>, Vertex<ChangeId>)>,
pub(crate) files: HashSet<Vertex<ChangeId>>,
pub graphs: Graphs,
pub covered_parents: HashSet<(Vertex<ChangeId>, Vertex<ChangeId>)>,
pub files: HashSet<Vertex<ChangeId>>,
let time = txn.get_changeset(txn.changes(&channel), id)?.unwrap();
let time = u64::from_le(time.0);
debug!("time = {:?}", time);
min_time = min_time.min(time);
if let Some(time) = txn.get_changeset(txn.changes(&channel), id)? {
let time = u64::from_le(time.0);
debug!("time = {:?}", time);
min_time = min_time.min(time);
}
}) => Ok(Atom::NewVertex(NewVertex {
up_context: up_context
.iter()
.map(|&up| Position {
change: up
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
pos: up.pos,
})
.collect(),
down_context: down_context
.iter()
.map(|&down| Position {
change: down
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
pos: down.pos,
})
.collect(),
start: *start,
end: *end,
flag: *flag,
inode: Position {
change: inode
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
pos: inode.pos,
},
})),
Atom::EdgeMap(EdgeMap { edges, inode }) => Ok(Atom::EdgeMap(EdgeMap {
edges: edges
.iter()
.map(|edge| NewEdge {
previous: edge.previous,
flag: edge.flag,
from: Position {
change: edge
.from
}) => {
debug!(
"globalize vertex {:?} {:?}",
up_context.len(),
down_context.len()
);
Ok(Atom::NewVertex(NewVertex {
up_context: up_context
.iter()
.map(|&up| Position {
change: up
pos: edge.from.pos,
},
to: Vertex {
change: edge
.to
pos: up.pos,
})
.collect(),
down_context: down_context
.iter()
.map(|&down| Position {
change: down
start: edge.to.start,
end: edge.to.end,
},
introduced_by: edge.introduced_by.as_ref().map(|a| {
if let Some(a) = txn.get_external(a).unwrap() {
a.into()
} else {
panic!("introduced by {:?}", a);
}
}),
})
.collect(),
inode: Position {
change: inode
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
pos: inode.pos,
},
})),
pos: down.pos,
})
.collect(),
start: *start,
end: *end,
flag: *flag,
inode: Position {
change: inode
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
pos: inode.pos,
},
}))
}
Atom::EdgeMap(EdgeMap { edges, inode }) => {
debug!("globalize edgemap {:?}", edges.len());
Ok(Atom::EdgeMap(EdgeMap {
edges: edges
.iter()
.map(|edge| NewEdge {
previous: edge.previous,
flag: edge.flag,
from: Position {
change: edge
.from
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
pos: edge.from.pos,
},
to: Vertex {
change: edge
.to
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
start: edge.to.start,
end: edge.to.end,
},
introduced_by: edge.introduced_by.as_ref().map(|a| {
if let Some(a) = txn.get_external(a).unwrap() {
a.into()
} else {
panic!("introduced by {:?}", a);
}
}),
})
.collect(),
inode: Position {
change: inode
.change
.as_ref()
.and_then(|a| txn.get_external(a).unwrap().map(Into::into)),
pos: inode.pos,
},
}))
}
parents: HashSet<Vertex<ChangeId>>,
children: HashSet<Vertex<ChangeId>>,
pseudo: Vec<(Vertex<ChangeId>, SerializedEdge, Position<Option<Hash>>)>,
deleted_by: HashSet<ChangeId>,
up_context: Vec<Vertex<ChangeId>>,
down_context: Vec<Vertex<ChangeId>>,
pub(crate) missing_context: crate::missing_context::Workspace,
rooted: HashMap<Vertex<ChangeId>, bool>,
adjbuf: Vec<SerializedEdge>,
alive_folder: HashMap<Vertex<ChangeId>, bool>,
folder_stack: Vec<(Vertex<ChangeId>, bool)>,
pub parents: HashSet<Vertex<ChangeId>>,
pub children: HashSet<Vertex<ChangeId>>,
pub pseudo: Vec<(Vertex<ChangeId>, SerializedEdge, Position<Option<Hash>>)>,
pub deleted_by: HashSet<ChangeId>,
pub up_context: Vec<Vertex<ChangeId>>,
pub down_context: Vec<Vertex<ChangeId>>,
pub missing_context: crate::missing_context::Workspace,
pub rooted: HashMap<Vertex<ChangeId>, bool>,
pub adjbuf: Vec<SerializedEdge>,
pub alive_folder: HashMap<Vertex<ChangeId>, bool>,
pub folder_stack: Vec<(Vertex<ChangeId>, bool)>,
// Reconnect with ancestor.
for v in stack.iter().rev() {
if v.is_on_path {
debug!("on path: {:?}", v);
// 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,
v.vertex,
elt.vertex,
ChangeId::ROOT,
)?;
break;
} else {
// Remember that those dead vertices have
// `elt.vertex` as a descendant.
descendants.insert((v.vertex, elt.vertex));
}
}
}
if !inodes.contains(&inode) {
for e in n.edges.iter() {
assert!(!e.flag.contains(EdgeFlags::PARENT));
if e.flag.contains(EdgeFlags::DELETED) {
trace!("repairing context deleted {:?}", e);
if has_missing_context_deleted(txn, channel, change_id, |h| change.knows(&h), e)
.map_err(LocalApplyError::from_missing)?
{
inodes.insert(inode);
break;
}
} else {
trace!("repairing context nondeleted {:?}", e);
if has_missing_context_nondeleted(txn, channel, change_id, e)
.map_err(LocalApplyError::from_missing)?
{
inodes.insert(inode);
break;
}
// If the inode is already in there, no need to do anything.
if inodes.contains(&inode) {
return Ok(());
}
let ext: Hash = if reverse {
(*txn.get_external(&change_id).unwrap().unwrap()).into()
} else {
// Unused, hence we avoid one Sanakirja lookup.
Hash::None
};
for e in n.edges.iter() {
let e = if reverse {
e.reverse(Some(ext))
} else {
e.clone()
};
assert!(!e.flag.contains(EdgeFlags::PARENT));
if e.flag.contains(EdgeFlags::DELETED) {
trace!("repairing context deleted {:?}", e);
if has_missing_context_deleted(txn, channel, change_id, |h| change.knows(&h), &e)
.map_err(LocalApplyError::from_missing)?
{
inodes.insert(inode);
break;
}
} else {
trace!("repairing context nondeleted {:?}", e);
if has_missing_context_nondeleted(txn, channel, change_id, &e)
.map_err(LocalApplyError::from_missing)?
{
inodes.insert(inode);
break;