# # # patch "cmd_merging.cc" # from [83cf17ff88126ef9cf541b1ce8851f8ce32228cd] # to [e0c8a13558e04e4efd35a3f290984fd24abd9b98] # # patch "merge.cc" # from [48d7db2994ac47a9b4d0d2a4a5c3bd4c5ef7083d] # to [35f671a616eda3a70deece487b9fe44900c17d92] # # patch "roster.cc" # from [0e36c692b2a4b063ba1d83b719d9f14aa74da61e] # to [97f54be64fef75c3d99c81582dbdc7d636d13b9c] # # patch "roster.hh" # from [d02b407aeb462016c8aa3f392e328471204b229a] # to [a6b7d285ee2e18db35b4b7139d5be562a9136fa6] # # patch "roster_merge.cc" # from [ae7195e5186616430fcb9f70bb9e57c00c17c9c7] # to [797095308451d07094dc20f8791dc529822822a0] # # patch "roster_merge.hh" # from [acd967c8284e347b89d75807a3a3936c9de41ac5] # to [d10a16027738710cd50617a340b149a29d102d2f] # # patch "ss-existence-merge.text" # from [386b5afa05acf3c4744b4363265c167bab866521] # to [4f5e53ab1b719beae34333bfb7417248a8411b92] # ============================================================ --- cmd_merging.cc 83cf17ff88126ef9cf541b1ce8851f8ce32228cd +++ cmd_merging.cc e0c8a13558e04e4efd35a3f290984fd24abd9b98 @@ -48,7 +48,8 @@ three_way_merge(revision_id const & ance revision_id const & right_rid, roster_t const & right_roster, roster_merge_result & result, marking_map & left_markings, - marking_map & right_markings) + marking_map & right_markings, + temp_node_id_source & nis) { MM(ancestor_roster); MM(left_roster); @@ -85,7 +86,7 @@ three_way_merge(revision_id const & ance // And do the merge roster_merge(left_roster, left_markings, left_uncommon_ancestors, right_roster, right_markings, right_uncommon_ancestors, - result); + nis, result); } static bool @@ -268,7 +269,7 @@ CMD(update, "update", "", CMD_REF(worksp roster_merge(*working_roster, working_markings, working_uncommon_ancestors, chosen_roster, chosen_markings, chosen_uncommon_ancestors, - result); + nis, result); } else { @@ -299,7 +300,7 @@ CMD(update, "update", "", CMD_REF(worksp three_way_merge(base_rid, *base_roster, working_rid, *working_roster, chosen_rid, chosen_roster, - result, working_markings, chosen_markings); + result, working_markings, chosen_markings, nis); } @@ -639,8 +640,8 @@ CMD(merge_into_dir, "merge_into_dir", "" db.get_roster(left_rid, left_roster, left_marking_map); db.get_roster(right_rid, right_roster, right_marking_map); db.get_uncommon_ancestors(left_rid, right_rid, - left_uncommon_ancestors, - right_uncommon_ancestors); + left_uncommon_ancestors, + right_uncommon_ancestors); if (!idx(args,2)().empty()) { @@ -663,6 +664,7 @@ CMD(merge_into_dir, "merge_into_dir", "" i->second.parent_name.insert(left_rid); } + temp_node_id_source nis; roster_merge_result result; roster_merge(left_roster, left_marking_map, @@ -670,7 +672,7 @@ CMD(merge_into_dir, "merge_into_dir", "" right_roster, right_marking_map, right_uncommon_ancestors, - result); + nis, result); content_merge_database_adaptor dba(db, left_rid, right_rid, left_marking_map, right_marking_map); @@ -778,11 +780,12 @@ CMD(merge_into_workspace, "merge_into_wo left_uncommon_ancestors, right_uncommon_ancestors); + temp_node_id_source nis; roster_merge_result merge_result; MM(merge_result); roster_merge(*left.first, *left.second, left_uncommon_ancestors, *right.first, *right.second, right_uncommon_ancestors, - merge_result); + nis, merge_result); revision_id lca_id; cached_roster lca; @@ -896,10 +899,11 @@ show_conflicts_core (database & db, db.get_roster(r_id, *r_roster, r_marking); set l_uncommon_ancestors, r_uncommon_ancestors; db.get_uncommon_ancestors(l_id, r_id, l_uncommon_ancestors, r_uncommon_ancestors); + temp_node_id_source nis; roster_merge_result result; roster_merge(*l_roster, l_marking, l_uncommon_ancestors, *r_roster, r_marking, r_uncommon_ancestors, - result); + nis, result); // note that left and right are in the order specified on the command line // they are not in lexical order as they are with other merge commands so @@ -955,6 +959,7 @@ show_conflicts_core (database & db, result.report_multiple_name_conflicts(*l_roster, *r_roster, adaptor, basic_io, output); result.report_duplicate_name_conflicts(*l_roster, *r_roster, adaptor, basic_io, output); result.report_content_drop_conflicts(*l_roster, *r_roster, basic_io, output); + result.report_suture_drop_conflicts(*l_roster, *r_roster, basic_io, output); result.report_attribute_conflicts(*l_roster, *r_roster, adaptor, basic_io, output); result.report_file_content_conflicts(lua, *l_roster, *r_roster, adaptor, basic_io, output); @@ -1162,7 +1167,7 @@ CMD(pluck, "pluck", "", CMD_REF(workspac three_way_merge(from_rid, *from_roster, working_rid, *working_roster, to_rid, *to_roster, - result, left_markings, right_markings); + result, left_markings, right_markings, nis); roster_t & merged_roster = result.roster; ============================================================ --- merge.cc 48d7db2994ac47a9b4d0d2a4a5c3bd4c5ef7083d +++ merge.cc 35f671a616eda3a70deece487b9fe44900c17d92 @@ -141,6 +141,7 @@ resolve_merge_conflicts(lua_hooks & lua, // resolve the ones we can. result.resolve_duplicate_name_conflicts(lua, left_roster, right_roster, adaptor); result.resolve_content_drop_conflicts(left_roster, right_roster); + result.resolve_suture_drop_conflicts(left_roster, right_roster); result.resolve_file_content_conflicts(lua, left_roster, right_roster, adaptor); } } @@ -155,6 +156,7 @@ resolve_merge_conflicts(lua_hooks & lua, result.report_multiple_name_conflicts(left_roster, right_roster, adaptor, false, std::cout); result.report_duplicate_name_conflicts(left_roster, right_roster, adaptor, false, std::cout); result.report_content_drop_conflicts(left_roster, right_roster, false, std::cout); + result.report_suture_drop_conflicts(left_roster, right_roster, false, std::cout); result.report_attribute_conflicts(left_roster, right_roster, adaptor, false, std::cout); result.report_file_content_conflicts(lua, left_roster, right_roster, adaptor, false, std::cout); ============================================================ --- roster.cc 0e36c692b2a4b063ba1d83b719d9f14aa74da61e +++ roster.cc 97f54be64fef75c3d99c81582dbdc7d636d13b9c @@ -83,7 +83,7 @@ roster_t::required_roster_format(marking unsigned int result = oldest_supported_roster_format; for (marking_map::const_iterator i = mm.begin(); i != mm.end(); ++i) - if (i->second.birth_cause.first != marking_t::add) + if (i->second.birth_record.cause != marking_t::add) result = 2; return result; @@ -113,33 +113,40 @@ template <> void } template <> void -dump(std::pair > const & birth_cause, string & out) +dump(marking_t::birth_cause_t const & birth_cause, string & out) { ostringstream oss; string tmp; - switch (birth_cause.first) + switch (birth_cause) { case marking_t::add: out = syms::birth_add(); return; case marking_t::suture: - dump(birth_cause.second.first, tmp); - oss << syms::birth_suture() << " " << tmp; - dump(birth_cause.second.second, tmp); - oss << " " << tmp; - out = oss.str(); + out = syms::birth_suture(); return; case marking_t::split: - dump(birth_cause.second.first, tmp); - oss << syms::birth_split() << tmp; - out = oss.str(); + I(false); // FIXME_SPLIT: return; } } template <> void +dump(std::set const & parents, string & out) +{ + ostringstream oss; + string tmp; + for (std::set::const_iterator i = parents.begin(); i != parents.end(); i++) + { + dump(*i, tmp); + oss << " " << tmp; + } + out = oss.str(); +} + +template <> void dump(set const & revids, string & out) { out.clear(); @@ -160,8 +167,10 @@ dump(marking_t const & marking, string & ostringstream oss; string tmp; oss << "birth_revision: " << marking.birth_revision << '\n'; - dump(marking.birth_cause, tmp); - oss << "birth_cause: " << tmp << '\n'; + dump(marking.birth_record.cause, tmp); + oss << "birth_record.cause: " << tmp << '\n'; + dump(marking.birth_record.parents, tmp); + oss << "birth_record.parents: " << tmp << '\n'; dump(marking.parent_name, tmp); oss << "parent_name: " << tmp << '\n'; dump(marking.file_content, tmp); @@ -1614,9 +1623,9 @@ namespace new_marking.birth_revision = new_rid; if (n->ancestors.first == n->self || n->ancestors.first == the_null_node) - new_marking.birth_cause = make_pair(marking_t::add, null_ancestors); + new_marking.birth_record = marking_t::birth_record_t(); else - new_marking.birth_cause = make_pair(marking_t::suture, n->ancestors); + new_marking.birth_record = marking_t::birth_record_t(marking_t::suture, n->ancestors); I(new_marking.parent_name.empty()); new_marking.parent_name.insert(new_rid); @@ -1645,7 +1654,7 @@ namespace I(same_type(parent_n, n) && parent_n->self == n->self); new_marking.birth_revision = parent_marking.birth_revision; - new_marking.birth_cause = parent_marking.birth_cause; + new_marking.birth_record = parent_marking.birth_record; mark_unmerged_scalar(parent_marking.parent_name, make_pair(parent_n->parent, parent_n->name), @@ -1694,7 +1703,7 @@ namespace // not a suture; a user add in a two-parent workspace. I(left_marking.birth_revision == right_marking.birth_revision); new_marking.birth_revision = left_marking.birth_revision; - new_marking.birth_cause = make_pair (marking_t::add, null_ancestors); + new_marking.birth_record = marking_t::birth_record_t(); } else { @@ -1705,20 +1714,20 @@ namespace // ln was previously sutured, now rn is being added to the // suture. Keep the birth revision for the original suture. new_marking.birth_revision = left_marking.birth_revision; - new_marking.birth_cause = left_marking.birth_cause; + new_marking.birth_record = left_marking.birth_record; } else if (rn->self == n->self) { // rn was previously sutured, now ln is being added to the // suture. Keep the birth revision for the original suture. new_marking.birth_revision = right_marking.birth_revision; - new_marking.birth_cause = right_marking.birth_cause; + new_marking.birth_record = right_marking.birth_record; } else { // new suture new_marking.birth_revision = new_rid; - new_marking.birth_cause = make_pair (marking_t::suture, make_pair(ln->self, rn->self)); + new_marking.birth_record = marking_t::birth_record_t (marking_t::suture, make_pair(ln->self, rn->self)); } } @@ -1874,7 +1883,7 @@ mark_merge_roster(roster_t const & left_ node_t const & left_node = lni->second; marking_t const & left_marking = safe_get(left_markings, n->self); - switch (left_marking.birth_cause.first) + switch (left_marking.birth_record.cause) { case marking_t::add: // Must be unborn on the right (as opposed to dead); @@ -1892,11 +1901,14 @@ mark_merge_roster(roster_t const & left_ case marking_t::suture: { // If one of the ancestor nodes is in right, merge marks with it. - node_id right_nid = left_marking.birth_cause.second.first; + // FIXME_SUTURE: handle recursive parents + I(left_marking.birth_record.parents.size() == 2); + set::const_iterator left_parents_i = left_marking.birth_record.parents.begin(); + node_id right_nid = *left_parents_i; node_map::const_iterator rni = right_roster.all_nodes().find(right_nid); if (rni == right_roster.all_nodes().end()) { - right_nid = left_marking.birth_cause.second.second; + right_nid = *(++left_parents_i); rni = right_roster.all_nodes().find(right_nid); } @@ -2792,7 +2804,7 @@ push_marking(basic_io::stanza & st, I(!null_id(mark.birth_revision)); st.push_binary_pair(syms::birth, mark.birth_revision.inner()); - switch (mark.birth_cause.first) + switch (mark.birth_record.cause) { case marking_t::add: if (marking_format > 1) @@ -2803,18 +2815,19 @@ push_marking(basic_io::stanza & st, { I(marking_format > 1); std::vector data; - data.push_back(lexical_cast(mark.birth_cause.second.first)); - data.push_back(lexical_cast(mark.birth_cause.second.second)); + for (set::const_iterator parents_i = mark.birth_record.parents.begin(); + parents_i != mark.birth_record.parents.end(); + parents_i++) + { + data.push_back(lexical_cast(*parents_i)); + } st.push_str_multi(syms::birth_cause, syms::birth_suture, data); } break; case marking_t::split: { - I(marking_format > 1); - std::vector data; - data.push_back(lexical_cast(mark.birth_cause.second.first)); - st.push_str_multi(syms::birth_cause, syms::birth_split, data); + I(false); // FIXME_SPLIT: } break; }; @@ -2866,24 +2879,20 @@ parse_marking(basic_io::parser & pa, if (pa.symp (syms::birth_add)) { pa.sym(); - marking.birth_cause = make_pair (marking_t::add, null_ancestors); + marking.birth_record = marking_t::birth_record_t(); } else if (pa.symp (syms::birth_suture)) { pa.sym(); pa.str(tmp_1); pa.str(tmp_2); - marking.birth_cause = make_pair (marking_t::suture, + marking.birth_record = marking_t::birth_record_t (marking_t::suture, make_pair(lexical_cast(tmp_1), lexical_cast(tmp_2))); } else if (pa.symp (syms::birth_split)) { - pa.sym(); - pa.str(tmp_1); - marking.birth_cause = make_pair (marking_t::split, - make_pair(lexical_cast(tmp_1), - the_null_node)); + I(false); // FIXME_SPLIT: } else { ============================================================ --- roster.hh d02b407aeb462016c8aa3f392e328471204b229a +++ roster.hh a6b7d285ee2e18db35b4b7139d5be562a9136fa6 @@ -143,12 +143,23 @@ struct marking_t struct marking_t { typedef enum {add, suture, split} birth_cause_t; + struct birth_record_t + { + birth_cause_t cause; + std::set parents; // parents of sutured nodes, recursive; see ss-existence-merge.text + birth_record_t() : cause(add){}; + birth_record_t(birth_cause_t cause, + std::set parents) : + cause(cause), parents(parents){}; + birth_record_t(birth_cause_t cause, + std::pair parents) : + cause(cause){this->parents.insert(parents.first); this->parents.insert(parents.second);}; + }; + revision_id birth_revision; - // if suture, the node_ids indicate the ancestors. If split, the first - // node_id indicates the ancestor. - std::pair > birth_cause; + birth_record_t birth_record; // These sets hold the minimal marking map for the merge scalars; see // ss-mark-merge.text. @@ -156,11 +167,11 @@ struct marking_t std::set file_content; std::map > attrs; - marking_t() : birth_cause (std::make_pair (add, null_ancestors)) {}; bool operator==(marking_t const & other) const { return birth_revision == other.birth_revision - && birth_cause == birth_cause + && birth_record.cause == birth_record.cause + && birth_record.parents == birth_record.parents && parent_name == other.parent_name && file_content == other.file_content && attrs == other.attrs; ============================================================ --- roster_merge.cc ae7195e5186616430fcb9f70bb9e57c00c17c9c7 +++ roster_merge.cc 797095308451d07094dc20f8791dc529822822a0 @@ -200,6 +200,7 @@ roster_merge_result::has_non_content_con || !multiple_name_conflicts.empty() || !duplicate_name_conflicts.empty() || !content_drop_conflicts.empty() + || !suture_drop_conflicts.empty() || !attribute_conflicts.empty(); } static void @@ -215,6 +216,7 @@ dump_conflicts(roster_merge_result const dump(result.multiple_name_conflicts, out); dump(result.duplicate_name_conflicts, out); dump(result.content_drop_conflicts, out); + dump(result.suture_drop_conflicts, out); dump(result.attribute_conflicts, out); dump(result.file_content_conflicts, out); @@ -266,6 +268,7 @@ namespace symbol const content("content"); symbol const content_drop("content_drop"); symbol const directory_loop_created("directory_loop_created"); + symbol const dropped("dropped"); symbol const duplicate_name("duplicate_name"); symbol const invalid_name("invalid_name"); symbol const left_attr_state("left_attr_state"); @@ -290,6 +293,7 @@ namespace symbol const right_file_id("right_file_id"); symbol const right_name("right_name"); symbol const right_type("right_type"); + symbol const suture_drop("suture_drop"); } } @@ -1270,8 +1274,6 @@ roster_merge_result::report_content_drop { content_drop_conflict const & conflict = content_drop_conflicts[i]; - I(!roster.is_attached(conflict.nid)); - basic_io::stanza st; file_path name; @@ -1309,7 +1311,7 @@ roster_merge_result::report_content_drop } else { - P(F("conflict: file '%s' dropped on the right, changed on the left") % name); + P(F("conflict: file '%s' dropped on the left, changed on the right") % name); } break; @@ -1339,7 +1341,106 @@ roster_merge_result::report_content_drop } } +static void +push_node_id_set(roster_t const & roster, + basic_io::stanza & st, + symbol const & k, + set nids) +{ + file_path name; + std::vector names; + + for (set::const_iterator i = nids.begin(); i != nids.end(); i++) + { + roster.get_name(*i, name); + names.push_back(name.as_internal()); + } + st.push_str_multi(k, names); +} + void +roster_merge_result::report_suture_drop_conflicts(roster_t const & left_roster, + roster_t const & right_roster, + bool const basic_io, + std::ostream & output) const +{ + for (size_t i = 0; i < suture_drop_conflicts.size(); ++i) + { + suture_drop_conflict const & conflict = suture_drop_conflicts[i]; + + basic_io::stanza st; + + file_path name; + + switch (conflict.sutured_side) + { + case resolve_conflicts::left_side: + left_roster.get_name (conflict.sutured_nid, name); + I(file_type == get_type (left_roster, conflict.sutured_nid)); + + if (basic_io) + { + st.push_str_pair(syms::conflict, syms::suture_drop); + st.push_str_pair(syms::left_type, "file"); + st.push_file_pair(syms::left_name, name); + push_node_id_set(left_roster, st, syms::dropped, conflict.dropped_nids); + } + else + { + P(F("conflict: file '%s' sutured on the left, some parents dropped on the right") % name); + for (set::const_iterator i = conflict.dropped_nids.begin(); i != conflict.dropped_nids.end(); i++) + { + roster.get_name(*i, name); + P(F("dropped:") % name); + } + } + + break; + + case resolve_conflicts::right_side: + right_roster.get_name (conflict.sutured_nid, name); + I(file_type == get_type (right_roster, conflict.sutured_nid)); + + if (basic_io) + { + st.push_str_pair(syms::conflict, syms::suture_drop); + st.push_str_pair(syms::right_type, "file"); + st.push_file_pair(syms::right_name, name); + push_node_id_set(right_roster, st, syms::dropped, conflict.dropped_nids); + } + else + { + P(F("conflict: file '%s' sutured on the right, changed on the left") % name); + } + + break; + } + + if (basic_io) + { + switch (conflict.resolution.first) + { + case resolve_conflicts::none: + break; + + case resolve_conflicts::ignore_drop: + st.push_file_pair(syms::resolved_ignore_drop, conflict.resolution.second); + break; + + case resolve_conflicts::respect_drop: + st.push_symbol(syms::resolved_respect_drop); + break; + + default: + I(false); + } + + put_stanza(st, output); + } + } +} + +void roster_merge_result::report_attribute_conflicts(roster_t const & left_roster, roster_t const & right_roster, content_merge_adaptor & adaptor, @@ -1773,6 +1874,77 @@ static void } // parse_content_drop_conflicts static void +parse_suture_drop_conflicts(basic_io::parser & pars, + std::vector & conflicts, + roster_t const & left_roster, + roster_t const & right_roster) +{ + for (std::vector::iterator i = conflicts.begin(); + i != conflicts.end(); + ++i) + { + string tmp; + string name; + resolve_conflicts::side_t sutured_side; + node_id sutured_nid; + set dropped_nids; + + suture_drop_conflict & conflict = *i; + + pars.esym(syms::suture_drop); + + if (pars.symp (syms::left_type)) + { + sutured_side = resolve_conflicts::left_side; + pars.sym(); + pars.str(tmp); + I(tmp == "file"); + pars.esym(syms::left_name); pars.str(name); + + parse_node_id_set(left_roster, dropped_nids, pars); + } + else + { + sutured_side = resolve_conflicts::right_side; + pars.sym(); + pars.str(tmp); + I(tmp == "file"); + pars.esym (syms::right_name); pars.str(name); + + parse_node_id_set(right_roster, dropped_nids, pars); + } + + N(sutured_side == conflict.sutured_side && + sutured_nid == conflict.sutured_nid && + dropped_nids == conflict.dropped_nids, + F("conflicts file does not match current conflicts: suture_drop, name %s") + % name); + + // check for a resolution + if ((!pars.symp (syms::conflict)) && pars.tok.in.lookahead != EOF) + { + if (pars.symp (syms::resolved_ignore_drop)) + { + conflict.resolution.first = resolve_conflicts::ignore_drop; + pars.sym(); + pars.str(tmp); + conflict.resolution.second = file_path_internal(tmp); + } + else + N(false, F("%s is not a supported conflict resolution for %s") % pars.token % "suture_drop"); + } + + if (pars.tok.in.lookahead != EOF) + pars.esym (syms::conflict); + else + { + std::vector::iterator tmp = i; + N(++tmp == conflicts.end(), F("conflicts file does not match current conflicts")); + } + } +} // parse_suture_drop_conflicts + +static void parse_file_content_conflicts(basic_io::parser & pars, std::vector & conflicts, roster_t const & left_roster, @@ -1843,8 +2015,7 @@ parse_resolve_conflicts_str(basic_io::pa parse_resolve_conflicts_str(basic_io::parser & pars, roster_merge_result & result) { char const * error_message_1 = "can't specify a %s conflict resolution for more than one conflict"; - char const * error_message_2 = "conflict resolution %s applies only to %s conflicts"; - char const * error_message_3 = "conflict resolution %s is not appropriate for current conflicts"; + char const * error_message_2 = "conflict resolution %s is not appropriate for current conflicts"; while (pars.tok.in.lookahead != EOF) { @@ -1853,16 +2024,27 @@ parse_resolve_conflicts_str(basic_io::pa { pars.sym(); - N(result.content_drop_conflicts.size() > 0, - F(error_message_2) % syms::resolved_ignore_drop % syms::content_drop); + N(result.content_drop_conflicts.size() + result.suture_drop_conflicts.size() > 0, + F(error_message_2) % syms::resolved_ignore_drop); - N(result.content_drop_conflicts.size() == 1, - F(error_message_1) % syms::resolved_ignore_drop); + if (result.content_drop_conflicts.size() == 1) + { + content_drop_conflict & conflict = *result.content_drop_conflicts.begin(); + string tmp; + pars.str(tmp); + conflict.resolution = make_pair(resolve_conflicts::ignore_drop, file_path_internal(tmp)); + } + else if (result.suture_drop_conflicts.size() == 1) + { + suture_drop_conflict & conflict = *result.suture_drop_conflicts.begin(); + string tmp; + pars.str(tmp); + conflict.resolution = make_pair(resolve_conflicts::ignore_drop, file_path_internal(tmp)); + } + else + N(false, + F(error_message_1) % syms::resolved_ignore_drop); - content_drop_conflict & conflict = *result.content_drop_conflicts.begin(); - string tmp; - pars.str(tmp); - conflict.resolution = make_pair(resolve_conflicts::ignore_drop, file_path_internal(tmp)); } else if (pars.symp (syms::resolved_rename_left)) { @@ -1941,7 +2123,7 @@ parse_resolve_conflicts_str(basic_io::pa pars.str(); } else - N(false, F(error_message_3) % syms::resolved_suture); + N(false, F(error_message_2) % syms::resolved_suture); } else N(false, F("%s is not a supported conflict resolution") % pars.token); @@ -2015,6 +2197,7 @@ parse_resolve_conflicts_opts (options co parse_duplicate_name_conflicts(pars, result.duplicate_name_conflicts, left_roster, right_roster); parse_content_drop_conflicts(pars, result.content_drop_conflicts, left_roster, right_roster); + parse_suture_drop_conflicts(pars, result.suture_drop_conflicts, left_roster, right_roster); parse_file_content_conflicts(pars, result.file_content_conflicts, left_roster, right_roster); if (src.lookahead != EOF) @@ -2051,6 +2234,7 @@ roster_merge_result::resolve_duplicate_n void roster_merge_result::resolve_duplicate_name_conflicts(lua_hooks & lua, + temp_node_id_source nis, roster_t const & left_roster, roster_t const & right_roster, content_merge_adaptor & adaptor) @@ -2063,10 +2247,6 @@ roster_merge_result::resolve_duplicate_n // roster. The resolution is either to suture the two files together, or to // rename one or both. - // This is the only conflict resolution that needs to create new nodes, so - // we can declare the node id source here. - temp_node_id_source nis; - for (std::vector::const_iterator i = duplicate_name_conflicts.begin(); i != duplicate_name_conflicts.end(); ++i) @@ -2240,12 +2420,14 @@ roster_merge_result::resolve_content_dro new_n->attrs = old_n->attrs; I(is_file_t(new_n)); downcast_to_file_t(new_n)->content = downcast_to_file_t(old_n)->content; + I(!roster.is_attached(conflict.nid)); roster.attach_node(conflict.nid, dir_n->self, basename); } break; case resolve_conflicts::respect_drop: P(F("keeping drop of %s") % old_n->name); + I(!roster.is_attached(conflict.nid)); roster.drop_detached_node(conflict.nid); break; @@ -2259,6 +2441,84 @@ void } void +roster_merge_result::resolve_suture_drop_conflicts(roster_t const & left_roster, + roster_t const & right_roster) +{ + MM(left_roster); + MM(right_roster); + MM(this->roster); // New roster + + // Conflict node is present but unattached in the new roster, with null + // file content id. The resolution is to fill in or delete the node. + + for (std::vector::const_iterator i = suture_drop_conflicts.begin(); + i != suture_drop_conflicts.end(); + ++i) + { + suture_drop_conflict const & conflict = *i; + MM(conflict); + + file_path name; + node_t old_n; + + switch (conflict.sutured_side) + { + case resolve_conflicts::left_side: + left_roster.get_name(conflict.sutured_nid, name); + old_n = left_roster.get_node (conflict.sutured_nid); + break; + + case resolve_conflicts::right_side: + right_roster.get_name(conflict.sutured_nid, name); + old_n = right_roster.get_node (conflict.sutured_nid); + break; + } + + switch (conflict.resolution.first) + { + case resolve_conflicts::none: + N(false, F("no resolution specified for conflict: suture_drop %s") % name); + break; + + case resolve_conflicts::ignore_drop: + { + file_path dirname; + path_component basename; + + N(roster.has_node(conflict.sutured_nid), + F("%s was sutured in this merge; resolution must be 'resolved_suture'") % name); + + node_t new_n = roster.get_node(conflict.sutured_nid); + + P(F("ignoring drop of %s; new name %s") % name % conflict.resolution.second); + N(!roster.has_node(conflict.resolution.second), + F("%s already exists") % conflict.resolution.second); + + name.dirname_basename(dirname, basename); + + node_t dir_n = roster.get_node(dirname); + + N(dir_n != 0, F("%s directory does not exist") % dirname); + + // fill in node in result roster + new_n->attrs = old_n->attrs; + I(is_file_t(new_n)); + downcast_to_file_t(new_n)->content = downcast_to_file_t(old_n)->content; + I(!roster.is_attached(conflict.sutured_nid)); + roster.attach_node(conflict.sutured_nid, dir_n->self, basename); + } + break; + + default: + I(false); + } + + } // end for + + suture_drop_conflicts.clear(); +} + +void roster_merge_result::resolve_file_content_conflicts(lua_hooks & lua, roster_t const & left_roster, roster_t const & right_roster, @@ -2345,6 +2605,7 @@ roster_merge_result::clear() multiple_name_conflicts.clear(); duplicate_name_conflicts.clear(); content_drop_conflicts.clear(); + suture_drop_conflicts.clear(); attribute_conflicts.clear(); file_content_conflicts.clear(); @@ -2440,65 +2701,191 @@ namespace I(false); } - struct handled_nodes + inline void + find_common_ancestor_nodes(set const & birth_parents, + marking_map const & markings, + set const & uncommon_ancestors, + set & result) { - node_id sutured_nid; - node_id ancestor_nid; + for (set::const_iterator i = birth_parents.begin(); + i != birth_parents.end(); + i++) + { + if (uncommon_ancestors.find(safe_get(markings, *i).birth_revision) == uncommon_ancestors.end()) + { + result.insert(*i); + } + } + } - handled_nodes () : sutured_nid(the_null_node), ancestor_nid(the_null_node){}; + inline void + insert_sutured(node_t const & n, + marking_t::birth_record_t const & birth_record, + marking_map const & parent_markings, + set const & uncommon_ancestors, + roster_t const & other_parent_roster, + marking_map const & other_markings, + resolve_conflicts::side_t parent_side, + temp_node_id_source nis, + roster_merge_result & result, + set & already_handled) + { + set common_parents; + set unfound_parents; + set conflict_nodes; + set extra_parents; - handled_nodes (node_id sutured_nid, node_id ancestor_nid) : - sutured_nid(sutured_nid), ancestor_nid(ancestor_nid) {}; + bool partial_suture = false; // other_parent has sutured node with parents = subset of common_parents + bool extra_suture = false; // other_parent has sutured node with some parents in, some not in common_parents - bool operator== (handled_nodes right) - {return this.ancestor_nid == right.ancestor_nid;} + find_common_ancestor_nodes(birth_record.parents, parent_markings, uncommon_ancestors, common_parents); - }; + unfound_parents = common_parents; - inline void - find_common_ancestor_nodes() - { - std::pair birth_ancestors = birth_cause.second; - // FIXME: more here :) + if (common_parents.size() == 1) + { + // exactly one common parent; case ib, ic, id + if (!other_parent_roster.has_node(*common_parents.begin())) + { + // deleted; case ib + result.suture_drop_conflicts.push_back(suture_drop_conflict(n->self, parent_side, common_parents)); + } + + // let mark-merge handle the rest + switch (parent_side) + { + case resolve_conflicts::left_side: + create_node_for(n, make_pair (n->self, *common_parents.begin()), result.roster); + return; + + case resolve_conflicts::right_side: + create_node_for(n, make_pair (*common_parents.begin(), n->self), result.roster); + return; + } + } + + for (node_map::const_iterator i = other_parent_roster.all_nodes().begin(); + i != other_parent_roster.all_nodes().end() && + !unfound_parents.empty(); + i++) + { + marking_t::birth_record_t const & this_birth = safe_get(other_markings, i->first).birth_record; + + switch (this_birth.cause) + { + case marking_t::add: + { + set::iterator pi = unfound_parents.find(i->first); + + if (pi != unfound_parents.end()) + { + unfound_parents.erase(pi); + } + } + break; + + case marking_t::split: + I(false); // FIXME_SPLIT: not supported yet + break; + + case marking_t::suture: + if (this_birth.parents == common_parents) + { + // case ie + + switch (parent_side) + { + case resolve_conflicts::left_side: + result.roster.create_file_node (file_id(), nis, make_pair(n->self, i->first)); + return; + + case resolve_conflicts::right_side: + result.roster.create_file_node (file_id(), nis, make_pair(i->first, n->self)); + return; + } + } + else + { + conflict_nodes.insert(i->first); + + for (set::const_iterator i = this_birth.parents.begin(); i != this_birth.parents.end(); i++) + { + if (unfound_parents.find(*i) == unfound_parents.end()) + extra_parents.insert(*i); + else + unfound_parents.erase(i); + } + } + }; // switch this_birth.cause + }; // for all nodes in other_parent + + if (unfound_parents.empty()) + { + if (conflict_nodes.size() > 0) + { + result.suture_suture_conflicts.push_back + (suture_suture_conflict(n->self, parent_side, common_parents, conflict_nodes, extra_parents)); + create_node_for(n, result.roster); + } + else + { + create_node_for(n, result.roster); + + for (set::const_iterator i = common_parents.begin(); i != common_parents.end(); i++) + { + already_handled.insert(*i); + } + + check_scalars_modified(common_parents, parent_roster, other_parent_roster, result); + } + } + else + { + result.suture_drop_conflicts.push_back (suture_drop_conflict(n->self, parent_side, unfound_parents)); + create_node_for(n, result.roster); + } } inline void insert_if_unborn_or_sutured(node_t const & n, - marking_map const & markings, + roster_t const & parent_roster, + marking_map const & parent_markings, set const & uncommon_ancestors, - roster_t const & parent_roster, roster_t const & other_parent_roster, + marking_map const & other_parent_markings, resolve_conflicts::side_t parent_side, + temp_node_id_source nis, roster_merge_result & result, - set & already_handled) + set & already_handled) { - MM(markings); + MM(parent_markings); MM(uncommon_ancestors); // See ss-existence-merge.text for cases. n is either the left or // right parent node. - // First we see if we've already handled this node, due to suturing. - set::iterator i = already_handled.find(n->self); - if (i != already_handled.end()) - { - already_handled.erase(i); - return; - } + // First we see if we've already handled this node. + { + set::iterator i = already_handled.find(n->self); + if (i != already_handled.end()) + { + already_handled.erase(i); + return; + } + } // We are in case i, iii or iv. We determine which by searching for the // birth revision of node n in uncommon_ancestors. - revision_id const & birth = safe_get(markings, n->self).birth_revision; + revision_id const & birth = safe_get(parent_markings, n->self).birth_revision; set::const_iterator const uncommon_birth_i = uncommon_ancestors.find(birth); if (uncommon_birth_i != uncommon_ancestors.end()) { // case i - std::pair > const & birth_cause = - safe_get(markings, n->self).birth_cause; + marking_t::birth_record_t const & birth_record = safe_get(parent_markings, n->self).birth_record; - switch (birth_cause.first) + switch (birth_record.cause) { case marking_t::add: // case ia @@ -2511,51 +2898,8 @@ namespace case marking_t::suture: // case ib, ic, id, ie; check state of suture parents - { - set common_ancestor_nodes = - find_common_ancestor_nodes(n, marking_map, uncommon_ancestors); - - bool ancestor_deleted = false; - - for (set::const_iterator i = common_ancestor_nodes.begin(); - i != common_ancestor_nodes.end(); - i++) - { - if (!other_parent_roster.has_node(*i)) - { - if (!has_sutured_node(other_parent_roster, other_marking_map, *i)) - { - ancestor_deleted = true; - break; - } - } - }; - - if (ancestor_deleted) - { - } - else - { - I(!right_anc_in_other); - - // Set ancestors so mark-merge step will know how to check for - // conflicts. We can't tell whether n is in left or right, so - // we always put it in ancestors.first. - create_node_for(n, make_pair (n->self, birth_ancestors.first), result.roster); - already_handled.insert(handled_node(n->self, birth_ancestors.first)); - } - else if (right_anc_in_other) - { - I(!left_anc_in_other); - create_node_for(n, make_pair (n->self, birth_ancestors.second), result.roster); - already_handled.insert(handled_node(n->self, birth_ancestors.second)); - } - else - { - // both ancestors deleted in other parent - create_node_for(n, result.roster); - } - } + insert_sutured (n, birth_record, parent_markings, uncommon_ancestors, + other_parent_roster, other_parent_markings, parent_side, nis, result, already_handled); break; } } @@ -2569,7 +2913,7 @@ namespace // FIXME: consider other scalars conflicting with drop - set const & content_marks = safe_get(markings, n->self).file_content; + set const & content_marks = safe_get(parent_markings, n->self).file_content; for (set::const_iterator it = content_marks.begin(); it != content_marks.end(); it++) { if (uncommon_ancestors.find(*it) != uncommon_ancestors.end()) @@ -2840,6 +3184,7 @@ roster_merge(roster_t const & left_paren roster_t const & right_parent, marking_map const & right_markings, set const & right_uncommon_ancestors, + temp_node_id_source nis, roster_merge_result & result) { set already_handled; @@ -2871,15 +3216,17 @@ roster_merge(roster_t const & left_paren case parallel::in_left: // case ii, iii, iva, va, vc insert_if_unborn_or_sutured(i.left_data(), - left_markings, left_uncommon_ancestors, left_parent, - right_parent, resolve_conflicts::left_side, result, already_handled); + left_parent, left_markings, left_uncommon_ancestors, + right_parent, right_markings, + resolve_conflicts::left_side, nis, result, already_handled); break; case parallel::in_right: // case ii, iii, ivb, vb, vd insert_if_unborn_or_sutured(i.right_data(), - right_markings, right_uncommon_ancestors, right_parent, - left_parent, resolve_conflicts::right_side, result, already_handled); + right_parent, right_markings, right_uncommon_ancestors, + left_parent, left_markings, + resolve_conflicts::right_side, nis, result, already_handled); break; case parallel::in_both: ============================================================ --- roster_merge.hh acd967c8284e347b89d75807a3a3936c9de41ac5 +++ roster_merge.hh d10a16027738710cd50617a340b149a29d102d2f @@ -18,7 +18,28 @@ #include "diff_patch.hh" #include "roster.hh" // needs full definition of roster_t available -// our general strategy is to return a (possibly insane) roster, and a list of +// When adding a new conflict type, add all of the following: +// +// - in this file: +// -- A struct definition +// -- A dump template declaration +// -- A vector of the conflicts in roster_merge_result +// -- 'report' and 'resolve' functions in roster_merge_result +// - in roster_merge.cc: +// -- bodies for dump, report, resolve +// -- line in roster_merge_result::has_non_content_conflicts +// -- line in dump_conflicts +// -- 'parse_*_conflicts' +// -- case in parse_resolve_conflicts_str +// -- line in parse_resolve_conflicts_opts +// -- line in roster_merge_result::clear +// -- cases to record conflicts in roster_merge and subroutines +// - in merge.cc: +// -- resolve and report lines in resolve_merge_conflicts +// - in cmd_merging.cc: +// -- line in show_conflicts_core + +// Our general strategy is to return a (possibly insane) roster, and a list of // conflicts encountered in that roster. Each conflict encountered in merging // the roster creates an entry in this list. // @@ -107,13 +128,13 @@ struct duplicate_name_conflict right_resolution.first = resolve_conflicts::none;}; }; -// files with content_drop conflicts are left attached in result roster -// (unless unattached for another reason), with parent content hash. +// files with content_drop conflicts are unattached in result roster, with +// parent content hash. struct content_drop_conflict { node_id nid; + resolve_conflicts::side_t parent_side; // node is in parent_side roster, not in other roster file_id fid; - resolve_conflicts::side_t parent_side; // node is in parent_side roster, not in other roster // resolution is one of none, ignore_drop, respect_drop. If ignore_drop, // provide new name to allow avoiding name conflicts. @@ -123,38 +144,77 @@ struct content_drop_conflict nid(the_null_node), parent_side(resolve_conflicts::left_side) {resolution.first = resolve_conflicts::none;}; content_drop_conflict(node_id nid, file_id fid, resolve_conflicts::side_t parent_side) : - nid(nid), fid(fid), parent_side(parent_side){resolution.first = resolve_conflicts::none;}; + nid(nid), parent_side(parent_side), fid(fid) {resolution.first = resolve_conflicts::none;}; }; -// files with suture_drop conflicts are left attached in result roster -// (unless unattached for another reason), with parent content hash. +// files with suture_drop conflicts are unattached in result roster, with +// sutured parent content hash. struct suture_drop_conflict { // We don't store the file_id in the conflict, to support suturing and // conflicting directories in the future. + // + // sutured_nid is in sutured_side roster, not in other roster + // dropped_nids are dropped in other roster node_id sutured_nid; - node_id ancestor_nid; - resolve_conflicts::side_t parent_side; // node is in parent_side roster, not in other roster + resolve_conflicts::side_t sutured_side; + std::set dropped_nids; - // resolution is one of none, ignore_drop, respect_drop. If ignore_drop, + // resolution is one of none, ignore_drop. If ignore_drop, // provide new name to allow avoiding name conflicts. std::pair resolution; suture_drop_conflict () : sutured_nid(the_null_node), - ancestor_nid(the_null_node), - parent_side(resolve_conflicts::left_side) + sutured_side(resolve_conflicts::left_side) {resolution.first = resolve_conflicts::none;}; suture_drop_conflict(node_id sutured_nid, - node_id ancestor_nid, - resolve_conflicts::side_t parent_side) : + resolve_conflicts::side_t sutured_side, + std::set dropped_nids) : sutured_nid(sutured_nid), - ancestor_nid(ancestor_nid), - parent_side(parent_side) + sutured_side(sutured_side), + dropped_nids(dropped_nids) {resolution.first = resolve_conflicts::none;}; }; +// files with suture_suture conflicts are left attached in result roster +// (unless unattached for another reason), with sutured parent content hash. +struct suture_suture_conflict +{ + // We don't store the file_id in the conflict, to support suturing and + // conflicting directories in the future. + // + // sutured_nid is in sutured_side roster, not in other roster + // common_parents are parents of suture_nid common to both parent rosters + // conflict_nids are in other roster, have subset of common_parents + // extra_nids are in other roster, have some parents in common_parents, other parents not in common_parents + node_id sutured_nid; + resolve_conflicts::side_t sutured_side; + std::set common_parents; + std::set conflict_nids; + std::set extra_nids; + + // There is no resolution; user must suture the nodes in the other parent + // to match the sutured parent, or undo the sutures in the sutured parent + // to match the other parent. + + suture_suture_conflict () : + sutured_nid(the_null_node), + sutured_side(resolve_conflicts::left_side) {}; + + suture_suture_conflict(node_id sutured_nid, + resolve_conflicts::side_t sutured_side, + std::set common_parents, + std::set conflict_nids, + std::set extra_nids) : + sutured_nid(sutured_nid), + sutured_side(sutured_side), + common_parents(common_parents), + conflict_nids(conflict_nids), + extra_nids(extra_nids) {}; +}; + // nodes with attribute conflicts are left attached in the resulting tree (unless // detached for some other reason), but with the given attribute left out of // their full_attr_map_t. Note that this doesn't actually leave the resulting @@ -203,6 +263,7 @@ template <> void dump(content_drop_confl template <> void dump(attribute_conflict const & conflict, std::string & out); template <> void dump(file_content_conflict const & conflict, std::string & out); template <> void dump(content_drop_conflict const & conflict, std::string & out); +template <> void dump(suture_drop_conflict const & conflict, std::string & out); struct roster_merge_result { @@ -215,6 +276,8 @@ struct roster_merge_result // - multiple name conflicts // - directory loop conflicts // - content_drop conflicts + // - suture_drop conflicts + // - suture_suture conflicts // - attribute conflicts // - file content conflicts @@ -226,6 +289,8 @@ struct roster_merge_result std::vector multiple_name_conflicts; std::vector duplicate_name_conflicts; std::vector content_drop_conflicts; + std::vector suture_drop_conflicts; + std::vector suture_suture_conflicts; std::vector attribute_conflicts; std::vector file_content_conflicts; @@ -271,6 +336,7 @@ struct roster_merge_result bool const basic_io, std::ostream & output) const; void resolve_duplicate_name_conflicts(lua_hooks & lua, + temp_node_id_source nis, roster_t const & left_roster, roster_t const & right_roster, content_merge_adaptor & adaptor); @@ -282,6 +348,13 @@ struct roster_merge_result void resolve_content_drop_conflicts(roster_t const & left_roster, roster_t const & right_roster); + void report_suture_drop_conflicts(roster_t const & left_roster, + roster_t const & right_roster, + bool const basic_io, + std::ostream & output) const; + void resolve_suture_drop_conflicts(roster_t const & left_roster, + roster_t const & right_roster); + void report_attribute_conflicts(roster_t const & left, roster_t const & right, content_merge_adaptor & adaptor, @@ -314,6 +387,7 @@ roster_merge(roster_t const & left_paren roster_t const & right_parent, marking_map const & right_markings, std::set const & right_uncommon_ancestors, + temp_node_id_source nis, roster_merge_result & result); void ============================================================ --- ss-existence-merge.text 386b5afa05acf3c4744b4363265c167bab866521 +++ ss-existence-merge.text 4f5e53ab1b719beae34333bfb7417248a8411b92 @@ -166,7 +166,7 @@ ic) suture is modified in the other parent's uncommon ancestors. Node 1 is copied into the child. - Note that this is the same as case iiib, with the roles of nodes 1 + Note that this is the same as case iiia, with the roles of nodes 1 and 3 swapped. This case also extends to sutured parents: @@ -182,7 +182,23 @@ ic) All parents of sutured nodes must be unmodified. Some of the parents may be born in A's uncommon ancestors. + Another variant is when some of the common parents of node 1 are + also sutured in the other parent: + D4a A2e I5d H2e + \ / \ / + A6f E4a F3b + \ \ / + G5d \ B1c + \ \ / + C1c + + Since we cannot easily tell if the scalars a and e were modified + in the suture f, we declare this to be case id; a conflict. + However, if there is a node in A that has exactly the same set of + suture parents as node 1 in B, then we have case ie. + + D2b E3a F2b G3a \ / / / A1c B2d H3e @@ -197,21 +213,47 @@ id) Node 1 was born in a suture in an uncommon ancestor. It exists in one parent, and is unborn in the other. One or both parents of the - suture are modified in the other parent's uncommon ancestors. This - is a scalar/suture conflict. + suture are modified in the other parent's uncommon ancestors. - Note that this is the same as case iiic, with the roles of nodes 1 + If there is exactly one parent of the suture that is common to A + and B, it can be merged by the mark-merge step. We could extend + this special case to allow exactly one modified parent of the + suture. Otherwise this is a scalar/suture conflict. + + Note that this is the same as case iiib, with the roles of nodes 1 and 3 swapped. As for case 1c, this case extends to sutured parents. + D2 E3 F2 G3 + \ / \ / + A1 B4 + \ / + C5 +ie) + D2 E3 F2 G3 + \ / \ / + A4 B1 + \ / + C5 + + Node 1 was born in a suture in an uncommon ancestor. It exists in + one parent, and is unborn in the other. The parents of node 1 in + one parent are also the parents of node 4 in the other. + + Nodes 4 and 1 are sutured in the child, and their contents merged. + This is done automatically; it is not a conflict. + + Note that this is the resolution of case id), after user sutures. + + D2 E3 F2 G5 \ / \ / A1 B4 \ / C1? -ie) +if) D2 E5 F2 G3 \ / \ / A4 B1 @@ -220,8 +262,8 @@ ie) Node 1 was born in a suture in an uncommon ancestor. It exists in one parent, and is unborn in the other. A parent of the suture was - sutured into a different node in the other parent's uncommon - ancestors. This is a suture/suture conflict. + sutured with different parents into a different node in the other + parent's uncommon ancestors. This is a suture/suture conflict. A1 B1 @@ -233,34 +275,16 @@ ii) \ / values; it is merged in the child. - D1 E2 - \ / - A1 B3 - \ / - C3 -iiia) - D1 E2 - \ / - A3 B1 - \ / - C3 - - Node 1 was born in a common ancestor. Node 3 was born in a suture - in an uncommon ancestor, with node 1 as a parent; node 2 was also - born in an uncommon ancestor. Node 1 exists in one parent, and is - sutured in the other. Node 1 is merged with the sutured node 3 in - the child. - D1a E2b - \ / + \ / A2b A1a B3c \ \ / C3c -iiib) +iiia) D1a E2b - \ / - A3c B1a B2b - \ / / + \ / + A3c B1a B2b + \ / / C3c Nodes 1 and 2 were born in common ancestors. Node 3 was born in a @@ -289,27 +313,26 @@ iiib) A2b A1d B3c \ \ / C3? C3? -iiic) +iiib) D1a E2b \ / A3c B1d B2b \ / / C3? C3? - Nodes 1 and 2 were born in common ancestors. Node 3 was born in a - suture in an uncommon ancestor, with nodes 1 and 2 as parents; - node 1 (and possibly 2) is modified in B. + Node 3 was born in a suture in an uncommon ancestor, with nodes 1 + and 2 as parents; node 1 (and possibly 2) is modified in B. - If the scalar for only node 1 is modified, this could be handled - in the same way as iiia; nodes 1 and 3 are merged in the child. - However, if both nodes 1 and 2 are modified, then we need to do two - merges, and the order may matter. So we require the user to suture - nodes 1 and 2 in both parents before doing this merge; this is a - non-resolvable conflict content/suture conflict. + As for case iiia, this extends to an arbitrary number of sutured + nodes. - As for case iiib, this extends to an arbitrary number of sutured - nodes; if any ancestor node of the final sutured node is modified, - we have a conflict. + If there is exactly one parent of the suture that is common to A + and B, it can be merged by the mark-merge step. We could extend + this special case to allow exactly one modified parent of the + suture. Otherwise more than one parent is modified in B, and we + need to do more than one merge, and the order may matter. So we + require the user to suture all parents before doing this merge; + this is a scalar/suture conflict. A1 B~1 @@ -373,9 +396,10 @@ how a node was born. This is done in the To distinguish among these cases, we need to store information about how a node was born. This is done in the marking map, by storing -birth_cause, a pair containing an enumeral and a pair of node_ids. The -enumeral indicates add or suture; if suture, the node_ids -indicate the ancestors. +birth_cause, a pair containing an enumeral and a set of node_ids. The +enumeral indicates add or suture; if suture, the node_ids indicate all +of the suture parents (including parents of parents that are sutures, +etc). Then when node 1 exists in A but not B, we search A's uncommon ancestors for the birth revision of node 1. If found, we have case i; @@ -387,24 +411,32 @@ revision B. distinguished by the state of the parents of the sutured node in revision B. -First we find the set of common ancestor nodes of node 1; the -parents of the suture that created node 1, and recursively for any -other sutures in the revision tree holding A's uncommon ancestor -revisions, that were born in common ancestors of A and B. +First we find the set of common ancestor nodes of node 1; the parents +of the suture that created node 1, and recursively for any other +sutures in the revision tree holding A's uncommon ancestor revisions, +that were born in common ancestors of A and B. This is done by +checking the set of parents in the birth record for revisions in A's +uncommon ancestors. Then we check to see if node 1's common ancestor nodes exist in B, -either directly, or as the parents of sutures. +either directly, or as the parents of sutures. We do this by searching +thru all nodes in B. If a node is in the common ancestor nodes, we +note that it was found. If a node is sutured, we check its parent set +for the common ancestor nodes, noting any that are found, and any that +are not in the common ancestor nodes. -If any of node 1's common ancestor nodes do not exist in B at all, or -were sutured and then dropped, we have case ib. +If any of node 1's common ancestor nodes are not found, we have case ib. -If all of node 1's common ancestor nodes exist in B, and none were -sutured into different nodes than in A, and all their scalars are -unmodified, we have case 1c. If any scalars are modified, we have case -id. +If all of node 1's common ancestor nodes are found, we have case ic or id. -If any were sutured into different nodes, we have case ie. +If a node is found with an exactly matching parent set, we have case ie. +To distinguish case ic from id, we check if any common ancestor nodes +were sutured; if so, we have case id. Otherwise we check to see if any +scalars are modified; if so, we have case id. Otherwise, we have case +1c. + + If node 1 was born in a common ancestor of A and B, we have case iii or iv. @@ -412,40 +444,24 @@ iii. If not found, it is case iv. a node that is a suture and has 1 as a parent. If found, it is case iii. If not found, it is case iv. -To distinguish case iiia from iiib and iiic, we search A's uncommon -ancestor revisions for the birth revision of the other parent of the -suture. If found, it is case iiia; if not, case iiib or iiic. +To distinguish case iiia from iiib, we form the set of common ancestor +nodes as above, but this time for node 3. Then the processing is the +same as for case i. -To distinguish case iiib from iiic, we form the set of sibling nodes; -nodes that are parents of sutures that are parents of the final -suture. Then we check the scalar values on the sibling nodes; if any -have changed, it is case iiic. - To distinguish case iva from ivb, we search A's uncommon ancestor -revisions for revisions in the A's scalar marking map; if found, node +revisions for revisions in A's scalar marking map; if found, node 1 is modified, and we have case ivb. -Since case ic is the same as iiib, and id is the same as case iiic, we +Since case ic is the same as iiia, and id is the same as case iiib, we will encounter each case twice, once for node 1 and once for node 3. We handle both nodes when we encounter either, so we maintain a set 'already_handled' of already handled nodes; if a node is in already_handled, we simply ignore it. -The processing for case i is more efficient than the processing for -case iii, so we process the nodes in decreasing numerical order. Since -sutured nodes have higher node ids than their parents, case i will -always be encountered before case iii. +The processing for case i is slightly more efficient than the +processing for case iii, so we process the nodes in decreasing +numerical order. Since sutured nodes have higher node ids than their +parents, case i will always be encountered before case iii. -FIXME: not clear if the following paragraph is correct or needed: - -This lets us detect nodes that are sutured then dropped, as follows. -When we encounter case ic or id, we put all of the common ancestor -nodes in the child, and in already_handled. Then when we encounter any -ancestor node later, we remove it from already_handled. If there are -any nodes left in already_handled when all nodes are processed, they -are case id, and we declare conflicts for them. Thus already_handled -must store pairs of node_ids; the sutured node id and ancestor node -ids. - (end of file)