# # patch "ChangeLog" # from [321cebaad41a0e794e9d8be4a2eef0448c617984] # to [3b84e3897943b6c7c29701343f1da2e52d4ff9b7] # # patch "revision.cc" # from [55e8cf987d6eb6854eb178ba131619312837bb28] # to [6909bf9dd29f340f7d10b8c2f9f217082b52e160] # ======================================================================== --- ChangeLog 321cebaad41a0e794e9d8be4a2eef0448c617984 +++ ChangeLog 3b84e3897943b6c7c29701343f1da2e52d4ff9b7 @@ -1,5 +1,13 @@ 2005-10-08 Nathaniel Smith + * revision.cc (calculate_change_sets_recursive): + (find_subgraph_for_composite_search) + (calculate_composite_change_set, calculate_arbitrary_change_set): + Remove. + (construct_revision_from_ancestry): Likewise. + +2005-10-08 Nathaniel Smith + * revision.cc (check_sane_history): Remove. 2005-08-31 Marcel van der Boom ======================================================================== --- revision.cc 55e8cf987d6eb6854eb178ba131619312837bb28 +++ revision.cc 6909bf9dd29f340f7d10b8c2f9f217082b52e160 @@ -708,195 +708,6 @@ } } -/* -// FIXME_ROSTERS: disabled until rewritten to use rosters - -// -// The idea with this algorithm is to walk from child up to ancestor, -// recursively, accumulating all the change_sets associated with -// intermediate nodes into *one big change_set*. -// -// clever readers will realize this is an overlapping-subproblem type -// situation and thus needs to keep a dynamic programming map to keep -// itself in linear complexity. -// -// in fact, we keep two: one which maps to computed results (partial_csets) -// and one which just keeps a set of all nodes we traversed -// (visited_nodes). in theory it could be one map with an extra bool stuck -// on each entry, but I think that would make it even less readable. it's -// already quite ugly. -// - -static bool -calculate_change_sets_recursive(revision_id const & ancestor, - revision_id const & child, - app_state & app, - change_set & cumulative_cset, - std::map > & partial_csets, - std::set & visited_nodes, - std::set const & subgraph) -{ - - if (ancestor == child) - return true; - - if (subgraph.find(child) == subgraph.end()) - return false; - - visited_nodes.insert(child); - - bool relevant_child = false; - - revision_set rev; - app.db.get_revision(child, rev); - - L(F("exploring changesets from parents of %s, seeking towards %s\n") - % child % ancestor); - - for(edge_map::const_iterator i = rev.edges.begin(); i != rev.edges.end(); ++i) - { - bool relevant_parent = false; - revision_id curr_parent = edge_old_revision(i); - - if (curr_parent.inner()().empty()) - continue; - - change_set cset_to_curr_parent; - - L(F("considering parent %s of %s\n") % curr_parent % child); - - std::map >::const_iterator j = - partial_csets.find(curr_parent); - if (j != partial_csets.end()) - { - // a recursive call has traversed this parent before and built an - // existing cset. just reuse that rather than re-traversing - cset_to_curr_parent = *(j->second); - relevant_parent = true; - } - else if (visited_nodes.find(curr_parent) != visited_nodes.end()) - { - // a recursive call has traversed this parent, but there was no - // path from it to the root, so the parent is irrelevant. skip. - relevant_parent = false; - } - else - relevant_parent = calculate_change_sets_recursive(ancestor, curr_parent, app, - cset_to_curr_parent, - partial_csets, - visited_nodes, - subgraph); - - if (relevant_parent) - { - L(F("revision %s is relevant, composing with edge to %s\n") - % curr_parent % child); - concatenate_change_sets(cset_to_curr_parent, edge_changes(i), cumulative_cset); - relevant_child = true; - break; - } - else - L(F("parent %s of %s is not relevant\n") % curr_parent % child); - } - - // store the partial edge from ancestor -> child, so that if anyone - // re-traverses this edge they'll just fetch from the partial_edges - // cache. - if (relevant_child) - partial_csets.insert(std::make_pair(child, - boost::shared_ptr - (new change_set(cumulative_cset)))); - - return relevant_child; -} - -// this finds (by breadth-first search) the set of nodes you'll have to -// walk over in calculate_change_sets_recursive, to build the composite -// changeset. this is to prevent the recursive algorithm from going way -// back in history on an unlucky guess of parent. - -static void -find_subgraph_for_composite_search(revision_id const & ancestor, - revision_id const & child, - app_state & app, - std::set & subgraph) -{ - std::set frontier; - frontier.insert(child); - subgraph.insert(child); - while (!frontier.empty()) - { - std::set next_frontier; - for (std::set::const_iterator i = frontier.begin(); - i != frontier.end(); ++i) - { - revision_set rev; - app.db.get_revision(*i, rev); - L(F("adding parents of %s to subgraph\n") % *i); - - for(edge_map::const_iterator j = rev.edges.begin(); j != rev.edges.end(); ++j) - { - revision_id curr_parent = edge_old_revision(j); - if (null_id(curr_parent)) - continue; - subgraph.insert(curr_parent); - if (curr_parent == ancestor) - { - L(F("found parent %s of %s\n") % curr_parent % *i); - return; - } - else - L(F("adding parent %s to next frontier\n") % curr_parent); - next_frontier.insert(curr_parent); - } - } - frontier = next_frontier; - } -} - -void -calculate_composite_change_set(revision_id const & ancestor, - revision_id const & child, - app_state & app, - change_set & composed) -{ - I(composed.empty()); - L(F("calculating composite changeset between %s and %s\n") - % ancestor % child); - if (ancestor == child) - return; - std::set visited; - std::set subgraph; - std::map > partial; - find_subgraph_for_composite_search(ancestor, child, app, subgraph); - calculate_change_sets_recursive(ancestor, child, app, composed, partial, - visited, subgraph); -} - -void -calculate_arbitrary_change_set(revision_id const & start, - revision_id const & end, - app_state & app, - change_set & composed) -{ - L(F("calculating changeset from %s to %s\n") % start % end); - revision_id r_ca_id; - change_set ca_to_start, ca_to_end, start_to_ca; - N(find_least_common_ancestor(start, end, r_ca_id, app), - F("no common ancestor for %s and %s\n") % start % end); - L(F("common ancestor is %s\n") % r_ca_id); - calculate_composite_change_set(r_ca_id, start, app, ca_to_start); - calculate_composite_change_set(r_ca_id, end, app, ca_to_end); - manifest_id m_ca_id; - manifest_map m_ca; - app.db.get_revision_manifest(r_ca_id, m_ca_id); - app.db.get_manifest(m_ca_id, m_ca); - invert_change_set(ca_to_start, m_ca, start_to_ca); - concatenate_change_sets(start_to_ca, ca_to_end, composed); -} - -*/ - // Stuff related to rebuilding the revision graph. Unfortunately this is a // real enough error case that we need support code for it. @@ -1474,157 +1285,6 @@ } } -/* -revision_id -anc_graph::construct_revision_from_ancestry(u64 child) -{ - L(F("processing node %d\n") % child); - - if (node_to_new_rev.find(child) != node_to_new_rev.end()) - { - L(F("node %d already processed, skipping\n") % child); - return node_to_new_rev.find(child)->second; - } - - manifest_id child_man; - get_node_manifest(child, child_man); - - revision_set rev; - rev.new_manifest = child_man; - - typedef std::multimap::const_iterator ci; - std::pair range = ancestry.equal_range(child); - if (range.first == range.second) - { - L(F("node %d is a root node\n") % child); - revision_id null_rid; - manifest_id null_mid; - boost::shared_ptr cs(new change_set()); - std::set blah; - analyze_manifest_changes(app, null_mid, child_man, blah, *cs); - rev.edges.insert(std::make_pair(null_rid, - std::make_pair(null_mid, cs))); - } - else if (std::distance(range.first, range.second) == 1) - { - I(child == range.first->first); - u64 parent = range.first->second; - if (node_to_new_rev.find(parent) == node_to_new_rev.end()) - construct_revision_from_ancestry(parent); - revision_id parent_rid = node_to_new_rev.find(parent)->second; - L(F("parent node %d = revision %s\n") % parent % parent_rid); - manifest_id parent_man; - get_node_manifest(parent, parent_man); - boost::shared_ptr cs(new change_set()); - std::set need_killing_files; - analyze_manifest_changes(app, parent_man, child_man, need_killing_files, - *cs); - rev.edges.insert(std::make_pair(parent_rid, - std::make_pair(parent_man, cs))); - } - else - { - // this section has lots and lots of rigmorale, in order to handle the - // following case: A -> B -> D, A -> C -> D. File "foo" exists in - // manifests A, C, and D only. (I.e., it was deleted and then re-added - // along the B path, and left alone along the C path.) The problem here - // is that we have to synthesize a delete/add pair on the C -> D edge, - // to make sure that the A -> D changeset is path invariant -- we have - // to make sure that no matter how you go from A to D, we will learn - // that A's "foo" and D's "foo" are actually logically distinct files. - // - // In order to do this, before we generate the changeset for any merged - // revision, we calculate the changeset through from the parents's - // common ancestor to the _other_ parent, which will tell us which files - // have been deleted since then. We also calculate the changeset - // through from the parents's common ancestor to the current parent, - // which tells us which files have already been deleted on our side, and - // so don't need to be deleted again. - // - // Finally, we feed the list of deleted files to analyze_manifest, which - // uses that information to break file ancestries when necessary. - // - // we only know how to preserve file ids when there are exactly two - // parents, so assert that there are. - std::vector parents, others; - { - u64 left_p, right_p; - ci i = range.first; - I(child == i->first); - left_p = i->second; - ++i; - I(child == i->first); - right_p = i->second; - ++i; - I(i == range.second); - parents.push_back(left_p); - others.push_back(right_p); - parents.push_back(right_p); - others.push_back(left_p); - } - // make sure our parents are all saved. - for (std::vector::const_iterator i = parents.begin(); i != parents.end(); ++i) - { - if (node_to_new_rev.find(*i) == node_to_new_rev.end()) - construct_revision_from_ancestry(*i); - I(node_to_new_rev.find(*i) != node_to_new_rev.end()); - } - // actually process the two nodes - for (int i = 0; i != 2; ++i) - { - u64 parent = idx(parents, i); - u64 other_parent = idx(others, i); - L(F("processing edge from child %d -> parent %d\n") % child % parent); - - revision_id parent_rid = node_to_new_rev.find(parent)->second; - revision_id other_parent_rid = node_to_new_rev.find(other_parent)->second; - // this is stupidly inefficient, in that we do this whole expensive - // changeset finding thing twice in a row. oh well. - revision_id lca; - std::set need_killing_files; - if (find_least_common_ancestor(parent_rid, other_parent_rid, lca, app)) - { - change_set parent_cs, other_parent_cs; - calculate_composite_change_set(lca, other_parent_rid, app, other_parent_cs); - calculate_composite_change_set(lca, parent_rid, app, parent_cs); - std::set_difference(other_parent_cs.rearrangement.deleted_files.begin(), - other_parent_cs.rearrangement.deleted_files.end(), - parent_cs.rearrangement.deleted_files.begin(), - parent_cs.rearrangement.deleted_files.end(), - std::inserter(need_killing_files, - need_killing_files.begin())); - } - - L(F("parent node %d = revision %s\n") % parent % parent_rid); - manifest_id parent_man; - get_node_manifest(parent, parent_man); - boost::shared_ptr cs(new change_set()); - analyze_manifest_changes(app, parent_man, child_man, need_killing_files, - *cs); - rev.edges.insert(std::make_pair(parent_rid, - std::make_pair(parent_man, cs))); - } - } - - revision_id rid; - calculate_ident(rev, rid); - node_to_new_rev.insert(std::make_pair(child, rid)); - - if (!app.db.revision_exists (rid)) - { - L(F("mapped node %d to revision %s\n") % child % rid); - app.db.put_revision(rid, rev); - ++n_revs_out; - } - else - { - L(F("skipping already existing revision %s\n") % rid); - } - - return rid; -} -*/ - void build_changesets_from_existing_revs(app_state & app) {