#
# 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)
{