[Monotone-devel] Re: suturing, resurrection, renaming and unique file identifiers

[Mikkel Fahnøe Jørgensen]

2008/5/27 Mikkel Fahnøe Jørgensen <address@hidden>:
> When a change is merged to a target revision, we can find
> the merge candidate not by comparing file id's but by finding common
> history in sliding the change forward along the path of file id
> changes until we reach one or more files in the current merge target
> revision.

I should perhaps clarify:

This is not simply sliding forward along a path. First a common
ancestor must be identified between files in the two revisions.
This ancestor is useful for merging, but the purpose here is to
establish a common identity between two files.

If we only have a single unique file id, we only need the common
ancestor due to merging since we can directly establish that the file
is present in both revisions.

In the general case with progressive file id's, we have a routing problem:
For each file in one revision we must find a path to one or more files
in the other revision.
If we find no such path, we introduce a new file, or try to join
existing files based on user input, path names and heuristics, or
report a conflict.

An idea for optimizing such routing could be to use a bloom filter
(known from text indexing and dictionaries) that tracks all id's of
all past file revisions. When can then trace back a file id from a
parallel branch until the bloom filter matches an ancestor file id,
which is likely a common ancestor (bloom filters have false positives
but never false negatives). But there could well be better ways to
pre-calculate relevant routing information.

Once we have the common ancestor, the remaining problem is sliding
forward. But we must eliminate those forward traces that does not lead
to our desired revision, hence it may be better to view the problem
fully as a routing problem instead of seeking ancestors.

Mikkel