# # # patch "ChangeLog" # from [673dfb7df15012a25244211cf8a7a842505fc5b2] # to [e1b713d4173a6d8a31e5f0ff5c3009176849fe49] # # patch "cmd_merging.cc" # from [f0c2f8111ce3cbe34655a8f66dfbb4eb7a6de6e1] # to [e3fc51ecd791f5680ec13c2a7033d3889ea94519] # ============================================================ --- ChangeLog 673dfb7df15012a25244211cf8a7a842505fc5b2 +++ ChangeLog e1b713d4173a6d8a31e5f0ff5c3009176849fe49 @@ -1,3 +1,11 @@ +2006-07-11 Zack Weinberg + + * cmd_merging.cc (merge_two): New function. + (CMD(merge)): Rewrite again - only merge one pair of heads on each + pass. Also, skip all the work of finding a good choice if there + are only two heads. Use merge_two. + (CMD(explicit_merge)): Use merge_two. + 2006-07-11 Richard Levitte * po/sv.po: Two new strings to translate. ============================================================ --- cmd_merging.cc f0c2f8111ce3cbe34655a8f66dfbb4eb7a6de6e1 +++ cmd_merging.cc e3fc51ecd791f5680ec13c2a7033d3889ea94519 @@ -294,15 +294,62 @@ maybe_update_inodeprints(app); } +// Subroutine of CMD(merge) and CMD(explicit_merge). Merge LEFT with RIGHT, +// placing results onto BRANCH. Note that interactive_merge_and_store may +// bomb out, and therefore so may this. +static void +merge_two(revision_id const & left, revision_id const & right, + string const & branch, string const & caller, app_state & app) +{ + // The following mess constructs a neatly formatted log message that looks + // like this: + // CALLER of 'LEFT' + // and 'RIGHT' + // to branch 'BRANCH' + // where the last line is left out if we're merging onto the current branch. + // We use a stringstream because boost::format does not support %-*s. + using std::ostringstream; + using std::setw; + using std::max; + ostringstream log; + size_t fieldwidth = max(caller.size() + strlen(" of '"), strlen("and '")); + + if (branch != app.branch_name()) + fieldwidth = max(fieldwidth, strlen("to branch '")); + + log << setw(fieldwidth - strlen(" of '")) << caller << " of '" << left + << "'\n" << setw(fieldwidth) << "and '" << right + << "'\n"; + + if (branch != app.branch_name()) + log << setw(fieldwidth) << "to branch '" << branch << "'\n"; + + // Now it's time for the real work. + P(F("[left] %s") % left); + P(F("[right] %s") % right); + + revision_id merged; + transaction_guard guard(app.db); + interactive_merge_and_store(left, right, merged, app); + + packet_db_writer dbw(app); + cert_revision_in_branch(merged, branch, app, dbw); + cert_revision_changelog(merged, log.str(), app, dbw); + + guard.commit(); + P(F("[merged] %s") % merged); +} + // should merge support --message, --message-file? It seems somewhat weird, // since a single 'merge' command may perform arbitrarily many actual merges. +// (Possibility: append the --message/--message-file text to the synthetic +// log message constructed in merge_two().) CMD(merge, N_("tree"), "", N_("merge unmerged heads of branch"), OPT_BRANCH_NAME % OPT_DATE % OPT_AUTHOR) { - set heads; + typedef std::pair revpair; typedef set::const_iterator rid_set_iter; - size_t pass = 1; if (args.size() != 0) throw usage(name); @@ -310,6 +357,7 @@ N(app.branch_name() != "", F("please specify a branch, with --branch=BRANCH")); + set heads; get_branch_heads(app.branch_name(), app, heads); N(heads.size() != 0, F("branch '%s' is empty") % app.branch_name); @@ -320,87 +368,78 @@ } P(F("%d heads on branch '%s'") % heads.size() % app.branch_name); - while (heads.size() > 1); - { - if (heads.size() > 2) - P(F("pass %d: calculating optimal next merge") % pass); - - map > heads_for_ancestor; - set ancestors; - typedef map >::iterator rid_map_iter; - // For every pair of heads, determine their merge ancestor, and remember - // the ancestor->head mapping. Note that more than one pair might have - // the same ancestor (e.g. if we have three heads all with the same - // parent); thus we use a set on the RHS of the map, not a pair. - for (rid_set_iter i = heads.begin(); i != heads.end(); ++i) - for (rid_set_iter j = i; j != heads.end(); ++j) - { - // It is not possible to initialize j to i+1 (set iterators - // expose neither operator+ nor a nondestructive next() method) - if (j == i) - continue; - - revision_id ancestor; - find_common_ancestor_for_merge(*i, *j, ancestor, app); - ancestors.insert(ancestor); - - rid_map_iter target - = heads_for_ancestor.insert(std::make_pair(ancestor, - set())) - .first; - - I(target->first == ancestor); - - target->second.insert(*i); - target->second.insert(*j); - } - - // Erasing ancestors from ANCESTORS will now produce a set of merge - // ancestors each of which is not itself an ancestor of any other - // merge ancestor. There is (believed to be) no good ordering of - // merges on that set. - erase_ancestors(ancestors, app); - - size_t count = 1; - 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) + + map heads_for_ancestor; + set ancestors; + size_t pass = 1, todo = heads.size() - 1; + + // If there are more than two heads to be merged, on each iteration we + // merge a pair whose least common ancestor is not an ancestor of any + // other pair's least common ancestor. For example, if the history graph + // looks like this: + // + // X + // / \ + // Y C + // / \ + // A B + // + // A and B will be merged first, and then the result will be merged with C. + while (heads.size() > 2) + { + P(F("merge %d / %d: choosing next pair of heads") % pass % todo); + + // For every pair of heads, determine their merge ancestor, and + // remember the ancestor->head mapping. + for (rid_set_iter i = heads.begin(); i != heads.end(); ++i) + for (rid_set_iter j = i; j != heads.end(); ++j) { - revision_id right = *j; - P(F("merge %d / %d") % count % ancestors.size()); - P(F("[left] %s") % left); - P(F("[right] %s") % right); + // It is not possible to initialize j to i+1 (set iterators + // expose neither operator+ nor a nondestructive next() method) + if (j == i) + continue; + + revision_id ancestor; + find_common_ancestor_for_merge(*i, *j, ancestor, app); - revision_id merged; - transaction_guard guard(app.db); - interactive_merge_and_store(left, right, merged, app); - - // merged 1 edge; now we commit this, update merge source and - // try next one - - packet_db_writer dbw(app); - cert_revision_in_branch(merged, app.branch_name(), app, dbw); - - string log = (FL("merge of %s\n" - " and %s\n") % left % right).str(); - cert_revision_changelog(merged, log, app, dbw); - - guard.commit(); - P(F("[merged] %s") % merged); - left = merged; - ++count; + // More than one pair might have the same ancestor (e.g. if we + // have three heads all with the same parent); as this table + // will be recalculated on every pass, we just take the first + // one we find. + if (ancestors.insert(ancestor).second) + heads_for_ancestor[ancestor] = revpair(*i, *j); } - } - get_branch_heads(app.branch_name(), app, heads); - ++pass; - } + // Erasing ancestors from ANCESTORS will now produce a set of merge + // ancestors each of which is not itself an ancestor of any other + // merge ancestor. + erase_ancestors(ancestors, app); + I(ancestors.size() > 0); + + // Take the first ancestor from the above set and merge its + // corresponding pair of heads. + revpair p = heads_for_ancestor[*ancestors.begin()]; + + P(F("merge %d / %d:") % pass % todo); + merge_two(p.first, p.second, app.branch_name(), string("merge"), app); + + ancestors.clear(); + heads_for_ancestor.clear(); + get_branch_heads(app.branch_name(), app, heads); + pass++; + } + + // Last one. + I(pass == todo); + if (todo > 1) + P(F("merge %d / %d:") % pass % todo); + + rid_set_iter i = heads.begin(); + revision_id left = *i++; + revision_id right = *i++; + I(i == heads.end()); + + merge_two(left, right, app.branch_name(), string("merge"), app); P(F("note: your workspaces have not been updated")); } @@ -598,27 +637,7 @@ N(!is_ancestor(right, left, app), F("%s is already an ancestor of %s") % right % left); - // Somewhat redundant, but consistent with output of plain "merge" command. - P(F("[source] %s") % left); - P(F("[source] %s") % right); - - revision_id merged; - transaction_guard guard(app.db); - interactive_merge_and_store(left, right, merged, app); - - packet_db_writer dbw(app); - - cert_revision_in_branch(merged, branch, app, dbw); - - string log = (FL("explicit_merge of '%s'\n" - " and '%s'\n" - " to branch '%s'\n") - % left % right % branch).str(); - - cert_revision_changelog(merged, log, app, dbw); - - guard.commit(); - P(F("[merged] %s") % merged); + merge_two(left, right, branch, string("explicit merge"), app); } CMD(show_conflicts, N_("informative"), N_("REV REV"),