[Monotone-devel] All branch authors, please read (was Re: I fooled the cycle detection code)

[graydon hoare]

Christof Petig <christof <at> petig-baender.de> writes:

> After some strange but legal criss cross merging yesterday, monotone
> refused its work with the following error:
> 
> monotone: fatal: std::runtime_error: cycle in table 'manifest_deltas',
> at node b4c5672e5c1a1749b6cf4eb78165e18e6480ff67 <-
> 2a6e1fb46bd1c2f3a197ba0c3a9a3a76428af358  **)

Yes. This bug has arisen due to a recent change. Timothy made a "fix" 2005-11-05
(which was a good fix) to the merge algorithm to replace both sides of a merge
with deltas in the storage layer. We were not previously doing so -- we were
only replacing one side -- which meant that we were previously accumulating full
file and manifest shapshots in the storage layer every time we did a merge.
Timothy's fix reduced the size of a database -- with a decent amount of merge
traffic in it -- quite dramatically.

However, his change made the storage graph into a DAG. He did not know that the
delta-reconstruction algorithm in database.cc relied on the storage graph being
an inverted tree. So the upshot is that as you start to accumulate merges,
you'll be gambling. Eventually you'll hit a storage DAG which the storage
reconstructor misinterprets as a cyclical tree, and you'll get an error like the
one Christof got above.

The solution is relatively easy and I've applied it to the mainline today: now
the reconstruction algorithm understands DAGs in the storage graph. Please,
everyone who has picked up a propagate from the mainline since 2005-11-05,
propagate the change I put in today before you get your own branch wedged (in
the worst case if you get it wedged before you get the fix, you can get it
unwedged as Christof has, but it's a bit awkward).

-graydon