# # patch "roster4.cc" # from [c2cf7808c90fa0525d4445f5b864eb8fdc54bdd5] # to [68b5118779405839c6afe6de0b0a9bc943c15ca4] # # patch "roster4.hh" # from [9a8d95210af80e86f73c23d6d146032ea15fca5e] # to [715a1573fd4d56de42c71441acfbc10f03ea89c7] # ======================================================================== --- roster4.cc c2cf7808c90fa0525d4445f5b864eb8fdc54bdd5 +++ roster4.cc 68b5118779405839c6afe6de0b0a9bc943c15ca4 @@ -679,63 +679,6 @@ out = oss.str(); } -marking_t::marking_t() -{ -} - - -marking_t::marking_t(revision_id const & birth_rid, - revision_id const & current_rid, - node_t n) - : birth_revision(birth_rid) -{ - set singleton; - singleton.insert(current_rid); - parent_name = singleton; - if (is_file_t(n)) - file_content = singleton; - for (full_attr_map_t::const_iterator i = n->attrs.begin(); - i != n->attrs.end(); ++i) - attrs.insert(make_pair(i->first, singleton)); -} - -marking_t -marking_t::freshen(node_t old_node, - node_t new_node, - revision_id const & current_rid) const -{ - I(same_type(old_node, new_node)); - set singleton; - singleton.insert(current_rid); - - marking_t mk = marking_t(*this); - - if (old_node->parent != new_node->parent - || old_node->name != new_node->name) - mk.parent_name = singleton; - - if (is_file_t(old_node)) - { - file_t fold = downcast_to_file_t(old_node); - file_t fnew = downcast_to_file_t(new_node); - if (!(fold->content == fnew->content)) - mk.file_content = singleton; - } - - for (full_attr_map_t::const_iterator i = new_node->attrs.begin(); - i != new_node->attrs.end(); ++i) - { - full_attr_map_t::const_iterator j = old_node->attrs.find(i->first); - I(j != old_node->attrs.end()); - map >::iterator k = mk.attrs.find(i->first); - I(k != mk.attrs.end()); - if (i->second != j->second) - k->second = singleton; - } - return mk; -} - - void roster_t::check_finite_depth() const { @@ -1079,6 +1022,66 @@ } void + mark_new_node(revision_id const & new_rid, node_t n, marking_t & new_marking) + { + new_marking.birth_revision = new_rid; + I(new_marking.parent_name.empty()); + new_marking.parent_name.insert(new_rid); + I(new_marking.file_content.empty()); + if (is_file_t(n)) + new_marking.file_content.insert(new_rid); + I(new_marking.attrs.empty()); + set singleton; + singleton.insert(new_rid); + for (full_attr_map_t::const_iterator i = n->attrs.begin(); + i != n->attrs.end(); ++i) + new_marking.attrs.insert(make_pair(i->first, singleton)); + } + + void + mark_unmerged_node(marking_t const & parent_marking, node_t parent_n, + revision_id const & new_rid, node_t n, + marking_t & new_marking) + { + // SPEEDUP?: the common case here is that the parent and child nodes are + // exactly identical, in which case the markings are also exactly + // identical. There might be a win in first doing an overall + // comparison/copy, in case it can be better optimized as a block + // comparison and a block copy... + + I(same_type(parent_n, n) && parent_n->self == n->self); + + new_marking.birth_revision = parent_marking.birth_revision; + + mark_unmerged_scalar(parent_marking.parent_name, + std::make_pair(parent_n->parent, parent_n->name), + new_rid, + std::make_pair(n->parent, n->name), + new_marking.parent_name); + + if (is_file_t(n)) + mark_unmerged_scalar(parent_marking.file_content, + downcast_to_file_t(parent_n)->content, + new_rid, + downcast_to_file_t(n)->content, + new_marking.file_content); + + for (full_attr_map_t::const_iterator i = n->attrs.begin(); + i != n->attrs.end(); ++i) + { + set & new_marks = new_marking.attrs[i->first]; + I(new_marks.empty()); + full_attr_map_t::const_iterator j = parent_n->attrs.find(i->first); + if (j == parent_n->attrs.end()) + new_marks.insert(new_rid); + else + mark_unmerged_scalar(safe_get(parent_marking.attrs, i->first), + j->second, + new_rid, i->second, new_marks); + } + } + + void mark_merged_node(marking_t const & left_marking, set left_uncommon_ancestors, node_t ln, @@ -1089,7 +1092,7 @@ node_t n, marking_t & new_marking) { - + I(same_type(ln, n) && same_type(rn, n)); I(left_marking.birth_revision == right_marking.birth_revision); new_marking.birth_revision = left_marking.birth_revision; @@ -1111,9 +1114,7 @@ lf->content, right_marking.file_content, right_uncommon_ancestors, rf->content, - new_rid, - f->content, - new_marking.file_content); + new_rid, f->content, new_marking.file_content); } // attrs for (full_attr_map_t::const_iterator i = n->attrs.begin(); @@ -1154,6 +1155,18 @@ ri->second, new_rid, i->second, new_marks); } + + // some extra sanity checking -- attributes are not allowed to be deleted, + // so we double check that they haven't. + // SPEEDUP?: this code could probably be made more efficient -- but very + // rarely will any node have more than, say, one attribute, so it probably + // doesn't matter. + for (full_attr_map_t::const_iterator i = ln->attrs.begin(); + i != ln->attrs.end(); ++i) + I(n->attrs.find(i->first) != n->attrs.end()); + for (full_attr_map_t::const_iterator i = rn->attrs.begin(); + i != rn->attrs.end(); ++i) + I(n->attrs.find(i->first) != n->attrs.end()); } @@ -1162,8 +1175,8 @@ // parents, rather than just the structure of the roster itself. void mark_merge_roster(roster_t const & left_r, roster_t const & right_r, - marking_map const & left_marking, - marking_map const & right_marking, + marking_map const & left_marking_map, + marking_map const & right_marking_map, set const & left_uncommon_ancestors, set const & right_uncommon_ancestors, revision_id const & new_rid, @@ -1178,86 +1191,47 @@ // parallel map::const_iterator lni = left_r.all_nodes().find(i->first); map::const_iterator rni = right_r.all_nodes().find(i->first); - marking_map::const_iterator lmi = left_marking.find(i->first); - marking_map::const_iterator rmi = right_marking.find(i->first); + bool exists_in_left = (lni != left_r.all_nodes().end()); bool exists_in_right = (rni != right_r.all_nodes().end()); + marking_t new_marking; + if (!exists_in_left && !exists_in_right) - { - // If the node didn't exist at all in either right or left - // side, it was added; there's no need to examine the left - // and right sides further, we know all the markings for - // this node will be the set {new_rid}, and set the birth - // revision to new_rid. - marking.insert(make_pair(i->first, marking_t(new_rid, new_rid, n))); - } + mark_new_node(new_rid, n, new_marking); else if (!exists_in_left && exists_in_right) { - node_t const & rn = rni->second; - I(same_type(n, rn) && n->self == rn->self); - I(right_uncommon_ancestors.find(rmi->second.birth_revision) + node_t const & right_node = rni->second; + marking_t const & right_marking = safe_get(right_marking_map, n->self); + // must be unborn on the left (as opposed to dead) + I(right_uncommon_ancestors.find(right_marking.birth_revision) != right_uncommon_ancestors.end()); - - // Two sub-cases: - if (shallow_equal(n, rn, false)) - { - // 1. The right edge is of the form a->a, and - // represents no decision on the part of the user, - // just a propagation of an existing state. In this - // case we carry the old mark-set forward from the - // right marking. - marking.insert(*rmi); - } - else - { - // 2. The right edge represents a change to the node -- - // thus a decision on the part of the user -- in which case - // we need to "freshen" the marks based on the changes - // which occurred along the edge. - marking.insert(make_pair(i->first, - rmi->second.freshen(rn, n, new_rid))); - } + mark_unmerged_node(right_marking, right_node, + new_rid, n, new_marking); } else if (exists_in_left && !exists_in_right) { - node_t const & ln = lni->second; - I(same_type(n, ln) && n->self == ln->self); - I(left_uncommon_ancestors.find(lmi->second.birth_revision) + node_t const & left_node = lni->second; + marking_t const & left_marking = safe_get(left_marking_map, n->self); + // must be unborn on the right (as opposed to dead) + I(left_uncommon_ancestors.find(left_marking.birth_revision) != left_uncommon_ancestors.end()); - - // Same two sub-cases here as above: - if (shallow_equal(n, ln, false)) - marking.insert(*lmi); - else - marking.insert(make_pair(i->first, - lmi->second.freshen(ln, n, new_rid))); + mark_unmerged_node(left_marking, left_node, + new_rid, n, new_marking); } else { - node_t const & ln = lni->second; - node_t const & rn = rni->second; - I(same_type(n, rn)); - I(same_type(n, ln)); - I(lmi->second.birth_revision == rmi->second.birth_revision); - marking_t marks; - mark_merged_node(lmi->second, left_uncommon_ancestors, ln, - rmi->second, right_uncommon_ancestors, rn, - new_rid, n, marks); - // attributes can never be deleted, so just double-check that they - // haven't been (sanity-checking). - // this is kinda inefficent, but very rarely will any node have - // more than 1 attribute. - for (full_attr_map_t::const_iterator j = ln->attrs.begin(); - j != ln->attrs.end(); ++j) - I(n->attrs.find(j->first) != n->attrs.end()); - for (full_attr_map_t::const_iterator j = rn->attrs.begin(); - j != rn->attrs.end(); ++j) - I(n->attrs.find(j->first) != n->attrs.end()); + node_t const & left_node = lni->second; + node_t const & right_node = rni->second; + mark_merged_node(safe_get(left_marking_map, n->self), + left_uncommon_ancestors, left_node, + safe_get(right_marking_map, n->self), + right_uncommon_ancestors, right_node, + new_rid, n, new_marking); + } - marking.insert(make_pair(i->first, marks)); - } + safe_insert(marking, make_pair(i->first, new_marking)); } } @@ -1326,7 +1300,9 @@ node_id handle_new(node_id nid) { node_t n = r.get_node(nid); - markings.insert(make_pair(nid, marking_t(rid, rid, n))); + marking_t new_marking; + mark_new_node(rid, n, new_marking); + safe_insert(markings, make_pair(nid, new_marking)); return nid; } @@ -1956,7 +1932,11 @@ revision_id rid(std::string("0123456789abcdef0123456789abcdef01234567")); for (node_map::const_iterator i = r.all_nodes().begin(); i != r.all_nodes().end(); ++i) - mm.insert(std::make_pair(i->first, marking_t(rid, rid, i->second))); + { + marking_t fake_marks; + mark_new_node(rid, i->second, fake_marks); + mm.insert(std::make_pair(i->first, fake_marks)); + } } static void ======================================================================== --- roster4.hh 9a8d95210af80e86f73c23d6d146032ea15fca5e +++ roster4.hh 715a1573fd4d56de42c71441acfbc10f03ea89c7 @@ -140,13 +140,7 @@ std::set parent_name; std::set file_content; std::map > attrs; - marking_t(); - marking_t(revision_id const & birth_rid, - revision_id const & current_rid, - node_t n); - marking_t freshen(node_t old_node, - node_t new_node, - revision_id const & current_rid) const; + marking_t() {}; bool operator==(marking_t const & other) const { return birth_revision == other.birth_revision