# # # patch "ChangeLog" # from [bf3af7ed2c2ac9a6ba448559ce973cd2717e8f61] # to [5c7a02e46cc98a53c9f26888d298517c5bf71171] # # patch "roster.cc" # from [754fbedfa28eae838ffc880b773b09eb561db8f9] # to [67380c22a3dfef07d49edbc75646a4b0668de5cb] # ============================================================ --- ChangeLog bf3af7ed2c2ac9a6ba448559ce973cd2717e8f61 +++ ChangeLog 5c7a02e46cc98a53c9f26888d298517c5bf71171 @@ -1,8 +1,18 @@ 2006-01-15 Nathaniel Smith + * roster.cc (union_corpses): New function. + (unify_roster_oneway, unify_rosters): Remove unused new_ids + argument. Add call to union_corpses. Add big comment explaining + what's going on. + (test_unify_rosters_end_to_end_ids) + (test_unify_rosters_end_to_end_attr_corpses): Split and improve + tests. + +2006-01-15 Nathaniel Smith + * roster.cc (test_unify_rosters_end_to_end): Add failing test for unify_roster's handling of attr corpses. - + 2006-01-15 Nathaniel Smith * cert.cc (load_key_pair): ============================================================ --- roster.cc 754fbedfa28eae838ffc880b773b09eb561db8f9 +++ roster.cc 67380c22a3dfef07d49edbc75646a4b0668de5cb @@ -1024,7 +1024,6 @@ // This handles all the stuff in a_new. void unify_roster_oneway(roster_t & a, set & a_new, roster_t & b, set & b_new, - set & new_ids, node_id_source & nis) { for (set::const_iterator i = a_new.begin(); i != a_new.end(); ++i) @@ -1042,7 +1041,6 @@ node_id new_nid = nis.next(); a.replace_node_id(aid, new_nid); b.replace_node_id(bid, new_nid); - new_ids.insert(new_nid); b_new.erase(bid); } else @@ -1053,18 +1051,94 @@ } + void + union_corpses(roster_t & left, roster_t & right) + { + // left and right should be equal, except that each may have some attr + // corpses that the other does not + map::const_iterator left_i = left.all_nodes().begin(); + map::const_iterator right_i = right.all_nodes().begin(); + while (left_i != left.all_nodes().end() || right_i != right.all_nodes().end()) + { + I(left_i->second->self == right_i->second->self); + parallel::iter j(left_i->second->attrs, + right_i->second->attrs); + // we batch up the modifications until the end, so as not to be + // changing things around under the parallel::iter's feet + set left_missing, right_missing; + while (j.next()) + { + MM(j); + switch (j.state()) + { + case parallel::invalid: + I(false); + + case parallel::in_left: + // this is a corpse + I(!j.left_data().first); + right_missing.insert(j.left_key()); + break; + + case parallel::in_right: + // this is a corpse + I(!j.right_data().first); + left_missing.insert(j.right_key()); + break; + + case parallel::in_both: + break; + } + } + for (set::const_iterator j = left_missing.begin(); + j != left_missing.end(); ++j) + safe_insert(left_i->second->attrs, + make_pair(*j, make_pair(false, attr_value()))); + for (set::const_iterator j = right_missing.begin(); + j != right_missing.end(); ++j) + safe_insert(right_i->second->attrs, + make_pair(*j, make_pair(false, attr_value()))); + ++left_i; + ++right_i; + } + I(left_i == left.all_nodes().end()); + I(right_i == right.all_nodes().end()); + } + // After this, left should == right, and there should be no temporary ids. // Destroys sets, because that's handy (it has to scan over both, but it can // skip some double-scanning) void unify_rosters(roster_t & left, set & left_new, roster_t & right, set & right_new, - // these new_ids all come from the given node_id_source - set & new_ids, node_id_source & nis) { - unify_roster_oneway(left, left_new, right, right_new, new_ids, nis); - unify_roster_oneway(right, right_new, left, left_new, new_ids, nis); + // Our basic problem is this: when interpreting a revision with multiple + // csets, those csets all give enough information for us to get the same + // manifest, and even a bit more than that. However, there is some + // information that is not exposed at the manifest level, and csets alone + // do not give us all we need. This function is responsible taking the + // two rosters that we get from pure cset application, and fixing them up + // so that they are wholly identical. + + // The first thing that is missing is identification of files. If one + // cset says "add_file" and the other says nothing, then the add_file is + // not really an add_file. One of our rosters will have a temp id for + // this file, and the other will not. In this case, we replace the temp + // id with the other side's permanent id. However, if both csets say + // "add_file", then this really is a new id; both rosters will have temp + // ids, and we replace both of them with a newly allocated id. After + // this, the two rosters will have identical node_ids at every path. + unify_roster_oneway(left, left_new, right, right_new, nis); + unify_roster_oneway(right, right_new, left, left_new, nis); + + // The other thing we need to fix up is attr corpses. Live attrs are made + // identical by the csets; but if, say, on one side of a fork an attr is + // added and then deleted, then one of our incoming merge rosters will + // have a corpse for that attr, and the other will not. We need to make + // sure at both of them end up with the corpse. This function fixes up + // that. + union_corpses(left, right); } template void @@ -1521,8 +1595,6 @@ MM(new_markings); { temp_node_id_source temp_nis; - // SPEEDUP?: the copies on the next two lines are probably the main - // bottleneck in this code new_roster = left_roster; roster_t from_right_r(right_roster); MM(from_right_r); @@ -1536,7 +1608,7 @@ set new_ids; unify_rosters(new_roster, from_left_er.new_nodes, from_right_r, from_right_er.new_nodes, - new_ids, nis); + nis); I(new_roster == from_right_r); } @@ -4501,19 +4573,19 @@ roster_t left, right; for (size_t i = 0; i < 30; ++i) { - set left_new, right_new, resolved_new; + set left_new, right_new; create_some_new_temp_nodes(tmp_nis, left, left_new, right, right_new); create_some_new_temp_nodes(tmp_nis, right, right_new, left, left_new); - unify_rosters(left, left_new, right, right_new, resolved_new, test_nis); + unify_rosters(left, left_new, right, right_new, test_nis); check_post_roster_unification_ok(left, right); } L(FL("TEST: end checking unification of rosters (randomly)")); } static void -test_unify_rosters_end_to_end() +test_unify_rosters_end_to_end_ids() { - L(FL("TEST: begin checking unification of rosters (end to end)")); + L(FL("TEST: begin checking unification of rosters (end to end, ids)")); revision_id has_rid = left_rid; revision_id has_not_rid = right_rid; file_id my_fid(std::string("9012901290129012901290129012901290129012")); @@ -4537,18 +4609,9 @@ { new_id = has_roster.create_file_node(my_fid, nis); has_roster.attach_node(new_id, split("foo")); - // a tricky thing that unify_roster has to deal with is making sure that - // attr corpses survive. so let's put in an attr corpse. (technically - // this is not quite a possible graph, since we're claiming that the file - // was _just_ created, and just-created files never have attr corpses on - // them, but it should still work fine.) - safe_insert(has_roster.get_node(new_id)->attrs, - make_pair(attr_key("testkey"), make_pair(false, attr_value("")))); marking_t file_marking; file_marking.birth_revision = has_rid; file_marking.parent_name = file_marking.file_content = singleton(has_rid); - safe_insert(file_marking.attrs, - make_pair(attr_key("testkey"), singleton(has_rid))); safe_insert(has_markings, make_pair(new_id, file_marking)); } @@ -4567,9 +4630,6 @@ new_rid, new_roster, new_markings, nis); I(new_roster.get_node(split("foo"))->self == new_id); - I(new_roster.get_node(split("foo"))->attrs - == has_roster.get_node(split("foo"))->attrs); - I(safe_get(new_markings, new_id) == safe_get(new_markings, new_id)); } // added in right, then merged { @@ -4582,9 +4642,6 @@ new_rid, new_roster, new_markings, nis); I(new_roster.get_node(split("foo"))->self == new_id); - I(new_roster.get_node(split("foo"))->attrs - == has_roster.get_node(split("foo"))->attrs); - I(safe_get(new_markings, new_id) == safe_get(new_markings, new_id)); } // added in merge // this is a little "clever", it uses the same has_not_roster twice, but the @@ -4601,10 +4658,104 @@ I(new_roster.get_node(split("foo"))->self != has_roster.get_node(split("foo"))->self); } - L(FL("TEST: end checking unification of rosters (end to end)")); + L(FL("TEST: end checking unification of rosters (end to end, ids)")); } +static void +test_unify_rosters_end_to_end_attr_corpses() +{ + L(FL("TEST: begin checking unification of rosters (end to end, attr corpses)")); + revision_id first_rid = left_rid; + revision_id second_rid = right_rid; + file_id my_fid(std::string("9012901290129012901290129012901290129012")); + testing_node_id_source nis; + + // Both rosters have the file "foo"; in one roster, it has the attr corpse + // "testfoo1", and in the other, it has the attr corpse "testfoo2". Only + // the second roster has the file "bar"; it has the attr corpse "testbar". + + roster_t first_roster; MM(first_roster); + marking_map first_markings; MM(first_markings); + node_id foo_id; + { + first_roster.attach_node(first_roster.create_dir_node(nis), split("")); + marking_t marking; + marking.birth_revision = old_rid; + marking.parent_name = singleton(old_rid); + safe_insert(first_markings, make_pair(first_roster.root()->self, marking)); + + foo_id = first_roster.create_file_node(my_fid, nis); + first_roster.attach_node(foo_id, split("foo")); + marking.file_content = singleton(old_rid); + safe_insert(first_markings, + make_pair(first_roster.get_node(split("foo"))->self, marking)); + } + + roster_t second_roster = first_roster; MM(second_roster); + marking_map second_markings = first_markings; MM(second_markings); + { + second_roster.attach_node(second_roster.create_file_node(my_fid, nis), + split("bar")); + safe_insert(second_roster.get_node(split("bar"))->attrs, + make_pair(attr_key("testbar"), make_pair(false, attr_value()))); + marking_t marking; + marking.birth_revision = second_rid; + marking.parent_name = marking.file_content = singleton(second_rid); + safe_insert(marking.attrs, + make_pair(attr_key("testbar"), singleton(second_rid))); + safe_insert(second_markings, + make_pair(second_roster.get_node(split("bar"))->self, marking)); + } + + // put in the attrs on foo + { + safe_insert(first_roster.get_node(foo_id)->attrs, + make_pair(attr_key("testfoo1"), make_pair(false, attr_value()))); + safe_insert(first_markings.find(foo_id)->second.attrs, + make_pair(attr_key("testfoo1"), singleton(first_rid))); + safe_insert(second_roster.get_node(foo_id)->attrs, + make_pair(attr_key("testfoo2"), make_pair(false, attr_value()))); + safe_insert(second_markings.find(foo_id)->second.attrs, + make_pair(attr_key("testfoo2"), singleton(second_rid))); + } + + cset add_cs; MM(add_cs); + safe_insert(add_cs.files_added, make_pair(split("bar"), my_fid)); + cset no_add_cs; MM(no_add_cs); + + { + roster_t new_roster; MM(new_roster); + marking_map new_markings; MM(new_markings); + make_roster_for_merge(first_rid, first_roster, first_markings, add_cs, + singleton(first_rid), + second_rid, second_roster, second_markings, no_add_cs, + singleton(second_rid), + new_rid, new_roster, new_markings, + nis); + I(new_roster.get_node(split("foo"))->attrs.size() == 2); + I(new_roster.get_node(split("bar"))->attrs + == second_roster.get_node(split("bar"))->attrs); + I(new_roster.get_node(split("bar"))->attrs.size() == 1); + } + { + roster_t new_roster; MM(new_roster); + marking_map new_markings; MM(new_markings); + make_roster_for_merge(second_rid, second_roster, second_markings, no_add_cs, + singleton(second_rid), + first_rid, first_roster, first_markings, add_cs, + singleton(first_rid), + new_rid, new_roster, new_markings, + nis); + I(new_roster.get_node(split("foo"))->attrs.size() == 2); + I(new_roster.get_node(split("bar"))->attrs + == second_roster.get_node(split("bar"))->attrs); + I(new_roster.get_node(split("bar"))->attrs.size() == 1); + } + + L(FL("TEST: end checking unification of rosters (end to end, attr corpses)")); +} + void add_roster_tests(test_suite * suite) { @@ -4612,7 +4763,8 @@ suite->add(BOOST_TEST_CASE(&check_sane_roster_screwy_dir_map)); suite->add(BOOST_TEST_CASE(&test_die_die_die_merge)); suite->add(BOOST_TEST_CASE(&test_same_nid_diff_type)); - suite->add(BOOST_TEST_CASE(&test_unify_rosters_end_to_end)); + suite->add(BOOST_TEST_CASE(&test_unify_rosters_end_to_end_ids)); + suite->add(BOOST_TEST_CASE(&test_unify_rosters_end_to_end_attr_corpses)); suite->add(BOOST_TEST_CASE(&test_unify_rosters_randomized)); suite->add(BOOST_TEST_CASE(&test_all_mark_scenarios)); suite->add(BOOST_TEST_CASE(&bad_attr_test));