[Monotone-devel] branch review for net.venge.monotone.multihead

[Nathaniel Smith]

I committed some wording and formatting tweaks while reading over
this; so these are remaining comments since then.

tests/merge_multiple_heads_1/__driver__.lua:

+-- Check in ce first so that the old dumb "in whatever order
+-- get_branch_heads returns" algorithm will do it wrong.

^^ The get_branch_heads returns a std::set<revision_id>, which is
always sorted lexicographically (because std::set is a sorted
tree-based structure, and revision_id::operator< sorts
lexicographically).  So the order in which things are committed
doesn't actually affect anything.

cmd_merging.cc:

          rid_map_iter target
            = heads_for_ancestor.insert(std::make_pair(ancestor,
                                                       set<revision_id>()))
              .first;
          
          I(target->first == ancestor);
          
          target->second.insert(*i);
          target->second.insert(*j);
^^ this code seems like it would be clearer as
  std::set<revision_id> targets;
  targets.insert(*i);
  targets.insert(*j);
  heads_for_ancestor.insert(std::make_pair(ancestor, targets);
?

    for (rid_set_iter i = ancestors.begin(); i != ancestors.end(); ++i)
      {
        rid_map_iter target = heads_for_ancestor.find(*i);
        I(target != heads_for_ancestor.end());
        I(target->second.size() >= 2);
        
        rid_set_iter j = target->second.begin();
        revision_id left = *j;
        for (++j; j != target->second.end(); ++j)
          {

This overall structure of passes, each containing arbitrarily many
merges, seems unnecessarily baroque, and adds additional code paths
that may contain bugs.  (It is not at all obvious, for instance, what
happens when there are multiple candidate merge pairs that share the
same merge ancestor.  Or what about:

    A
   / \
  B   C
 / \ / \
D   E   F

Here it looks like it will merge (D, E) and (E, F) in one pass, which
is a bit silly; merging (D, E) and then the result of that with F, or
vice versa, would be better.  If nothing else, it violates the
invariant that each call to the merger reduces the number of heads by
exactly 1.)

I think it would be better to just go through the loop, each time
picking _some_ pair of heads that is as good as any to merge next,
merging them, and then going through again from the top.  Simpler to
reason about, and easier to describe to the user what's going on as
well (the second number in the current "merge %d / %d" message is
quite meaningless to a user).

Also, this makes it easy to skip the whole machinery when there are
only two heads, which is probably a nice speed win in the common case.


In the current code, it's also very unclear what happens in the case:
   A
  /|\
 B C D
In fact, tracing through, it looks like what happens is that each pair
(B, C), (B, D), (C, D) is inserted into the heads_for_ancestor map,
but because it is a map and not a multimap, whichever pair is seen
first gets entered, and the rest get silently dropped on the floor
(because they are all entered under the same key).  Since they are, in
fact, equivalent in the eyes of the ordering logic, this won't
actually cause incorrect behavior, but it's very hard to see what's
going on.  A useful rule of thumb in the monotone codebase is that if
you expect the STL behavior of dropping duplicate inserts on the
floor, then put a comment on the insert, and if you don't, then use
safe_insert from safe_map.hh.
 
-- Nathaniel

-- 
  /* Tell the world that we're going to be the grim
   * reaper of innocent orphaned children.
   */
-- Linux kernel 2.4.5, main.c