2008/5/27 Mikkel Fahnøe Jørgensen <[EMAIL PROTECTED]>: > 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
_______________________________________________ Monotone-devel mailing list Monotone-devel@nongnu.org http://lists.nongnu.org/mailman/listinfo/monotone-devel