The unified diff between revisions [3ba209c9..] and [b6853a1b..] is displayed below. It can also be downloaded as a raw diff.
#
#
# patch "automate.cc"
# from [68d579fc833b4a0ec52a0c8e5b130af7517ab7ed]
# to [d86c347f85ee7ce7a59f699c8e51feaa1fa57bfb]
#
# patch "enumerator.cc"
# from [31a5efd62fdaaada910d5b15b7fe31648a0ad17a]
# to [b1bf503af4b757eaf326935c4aa3acce3d9ff200]
#
# patch "enumerator.hh"
# from [b2662b4dea76a8d832663ed48342920248449f70]
# to [1880dae7a6147b0ddd8064bfc4679334b520aeab]
#
# patch "revision.cc"
# from [8cda143f1b14ea5d67e40c9dc325b5ec6f2fd1a7]
# to [77ddcf19bb049ae3ca74b008441bcaa7079232d5]
#
# patch "revision.hh"
# from [5e3733994a6c92c4f15f0d78aa26669458443d46]
# to [c6f7e1c8ac336bdec754f0fd1b822124e58eeb5f]
#
============================================================
--- automate.cc 68d579fc833b4a0ec52a0c8e5b130af7517ab7ed
+++ automate.cc d86c347f85ee7ce7a59f699c8e51feaa1fa57bfb
@@ -283,7 +283,7 @@ automate_toposort(std::vector<utf8> args
revs.insert(rid);
}
std::vector<revision_id> sorted;
- toposort(revs, sorted, app);
+ toposort(revs, sorted, app.db);
for (std::vector<revision_id>::const_iterator i = sorted.begin();
i != sorted.end(); ++i)
output << (*i).inner()() << std::endl;
@@ -329,7 +329,7 @@ automate_ancestry_difference(std::vector
ancestry_difference(a, bs, ancestors, app);
std::vector<revision_id> sorted;
- toposort(ancestors, sorted, app);
+ toposort(ancestors, sorted, app.db);
for (std::vector<revision_id>::const_iterator i = sorted.begin();
i != sorted.end(); ++i)
output << (*i).inner()() << std::endl;
============================================================
--- enumerator.cc 31a5efd62fdaaada910d5b15b7fe31648a0ad17a
+++ enumerator.cc b1bf503af4b757eaf326935c4aa3acce3d9ff200
@@ -27,10 +27,14 @@ revision_enumerator::revision_enumerator
set<revision_id> const & terminal)
: cb(cb), app(app), terminal_nodes(terminal)
{
+ // TODO: needs sorting out with the toposort stuff.
+ I(false);
+ /*
for (set<revision_id>::const_iterator i = initial.begin();
i != initial.end(); ++i)
revs.push_back(*i);
- load_graphs();
+ */
+ load_revs();
}
revision_enumerator::revision_enumerator(enumerator_callbacks & cb,
@@ -38,147 +42,173 @@ revision_enumerator::revision_enumerator
: cb(cb), app(app)
{
revision_id root;
- revs.push_back(root);
- load_graphs();
+ load_revs();
}
void
-revision_enumerator::load_graphs()
+revision_enumerator::load_revs()
{
- app.db.get_revision_ancestry(graph);
- for (multimap<revision_id, revision_id>::const_iterator i = graph.begin();
- i != graph.end(); ++i)
+ // TODO: this totally disrespects the initial and terminal stuff.
+ // It should probably be integrated into the toposort code itself.
+ vector<revision_id> topo_vec;
+ toposort(topo_vec, app.db);
+ for (vector<revision_id>::const_iterator r = topo_vec.begin();
+ r != topo_vec.end(); r++)
{
- inverse_graph.insert(make_pair(i->second, i->first));
+ if (null_id(*r))
+ continue;
+ topo_revs.push_back(*r);
}
}
-bool
-revision_enumerator::all_parents_enumerated(revision_id const & child)
-{
- typedef multimap<revision_id, revision_id>::const_iterator ci;
- pair<ci,ci> range = inverse_graph.equal_range(child);
- for (ci i = range.first; i != range.second; ++i)
- {
- if (i->first == child)
- {
- if (enumerated_nodes.find(i->second) == enumerated_nodes.end())
- return false;
- }
- }
- return true;
-}
-
bool
revision_enumerator::done()
{
- return revs.empty() && items.empty();
+ return topo_revs.empty() && items.empty();
}
-void
-revision_enumerator::step()
+void
+revision_enumerator::process_bunch()
{
- while (!done())
+ // we build up a set of files and revs to send
+ vector<revision_id> bunch_revs;
+ set<file_id> bunch_files;
+ multimap<file_id, file_id> bunch_file_deltas;
+
+ // files that should be sent first
+ set<file_id> top_files;
+ // files that will be sent either as full files are as the dst of deltas
+ set<file_id> dst_files;
+
+ while (bunch_revs.size() < 100 && !topo_revs.empty())
{
- if (items.empty() && !revs.empty())
- {
- revision_id r = revs.front();
- revs.pop_front();
+ revision_id r = topo_revs.front();
+ topo_revs.pop_front();
+ if (!cb.process_this_rev(r))
+ continue;
- // It's possible we've enumerated this node elsewhere since last
- // time around. Cull rather than reprocess.
- if (enumerated_nodes.find(r) != enumerated_nodes.end())
- continue;
-
- if (!all_parents_enumerated(r))
+ bunch_revs.push_back(r);
+
+ revision_set rs;
+ app.db.get_revision(r, rs);
+ for (edge_map::const_iterator i = rs.edges.begin();
+ i != rs.edges.end(); ++i)
+ {
+ cset const & cs = edge_changes(i);
+
+ // Queue up all the file-adds
+ for (map<split_path, file_id>::const_iterator fa = cs.files_added.begin();
+ fa != cs.files_added.end(); ++fa)
{
- revs.push_back(r);
- continue;
+ if (cb.queue_this_file(fa->second.inner()))
+ {
+ dst_files.insert(fa->second);
+ top_files.insert(fa->second);
+ bunch_files.insert(fa->second);
+ }
}
-
- if (terminal_nodes.find(r) == terminal_nodes.end())
+
+ // Queue up all the file-deltas
+ for (map<split_path, std::pair<file_id, file_id> >::const_iterator fd
+ = cs.deltas_applied.begin();
+ fd != cs.deltas_applied.end(); ++fd)
{
- typedef multimap<revision_id, revision_id>::const_iterator ci;
- pair<ci,ci> range = graph.equal_range(r);
- for (ci i = range.first; i != range.second; ++i)
+ if (cb.queue_this_file(fd->second.second.inner()))
{
- if (i->first == r)
- if (enumerated_nodes.find(i->first) == enumerated_nodes.end())
- revs.push_back(i->second);
+ if (dst_files.find(fd->second.first) == dst_files.end())
+ {
+ top_files.insert(fd->second.first);
+ }
+
+ bunch_file_deltas.insert(make_pair(fd->second.first,
+ fd->second.second));
+ dst_files.insert(fd->second.second);
}
}
+ }
+ }
- enumerated_nodes.insert(r);
+ // XXX required?
+ set<file_id> sent_files;
- if (null_id(r))
- continue;
+ // now we can queue up the file items in order.
+ for (set<file_id>::const_iterator t = top_files.begin();
+ t != top_files.end(); t++)
+ {
+ if (sent_files.find(*t) != sent_files.end())
+ {
+ L(FL("already sent top_file %s") % t->inner()());
+ continue;
+ }
- if (cb.process_this_rev(r))
- {
- L(FL("revision_enumerator::step expanding "
- "contents of rev '%d'\n") % r);
+ L(FL("top_file %s") % t->inner()());
- revision_set rs;
- app.db.get_revision(r, rs);
- for (edge_map::const_iterator i = rs.edges.begin();
- i != rs.edges.end(); ++i)
- {
- cset const & cs = edge_changes(i);
-
- // Queue up all the file-adds
- for (map<split_path, file_id>::const_iterator fa = cs.files_added.begin();
- fa != cs.files_added.end(); ++fa)
- {
- if (cb.queue_this_file(fa->second.inner()))
- {
- enumerator_item item;
- item.tag = enumerator_item::fdata;
- item.ident_a = fa->second.inner();
- items.push_back(item);
- }
- }
-
- // Queue up all the file-deltas
- for (map<split_path, std::pair<file_id, file_id> >::const_iterator fd
- = cs.deltas_applied.begin();
- fd != cs.deltas_applied.end(); ++fd)
- {
- if (cb.queue_this_file(fd->second.second.inner()))
- {
- enumerator_item item;
- item.tag = enumerator_item::fdelta;
- item.ident_a = fd->second.first.inner();
- item.ident_b = fd->second.second.inner();
- items.push_back(item);
- }
- }
- }
-
- // Queue up the rev itself
- {
- enumerator_item item;
- item.tag = enumerator_item::rev;
- item.ident_a = r.inner();
- items.push_back(item);
- }
- }
-
- // Queue up some or all of the rev's certs
- vector<hexenc<id> > hashes;
- app.db.get_revision_certs(r, hashes);
- for (vector<hexenc<id> >::const_iterator i = hashes.begin();
- i != hashes.end(); ++i)
+ if (bunch_files.find(*t) != bunch_files.end())
+ {
+ // a full file to send.
+ enumerator_item item;
+ item.tag = enumerator_item::fdata;
+ item.ident_a = t->inner();
+ items.push_back(item);
+ sent_files.insert(*t);
+ L(FL("send full_file %s") % t->inner()());
+ }
+
+ // XXX: doing BFS now, should try DFS too.
+ deque<file_id> frontier;
+ frontier.push_back(*t);
+
+ while (!frontier.empty())
+ {
+ file_id f = frontier.front();
+ frontier.pop_front();
+
+ L(FL("frontier %s") % f.inner()());
+
+ for (multimap<file_id,file_id>::const_iterator
+ d = bunch_file_deltas.lower_bound(f);
+ d != bunch_file_deltas.upper_bound(f);
+ d++)
{
- if (cb.queue_this_cert(*i))
+ if (sent_files.find(d->second) != sent_files.end())
{
- enumerator_item item;
- item.tag = enumerator_item::cert;
- item.ident_a = *i;
- items.push_back(item);
+ L(FL("already sent delta %s") % d->second.inner()());
+ continue;
}
+ sent_files.insert(d->second);
+ frontier.push_back(d->second);
+
+ enumerator_item item;
+ item.tag = enumerator_item::fdelta;
+ item.ident_a = d->first.inner();
+ item.ident_b = d->second.inner();
+ items.push_back(item);
+ L(FL("file_delta %s->%s") % d->first.inner()() % d->second.inner()());
}
}
+ }
+ // and the revs
+ for (vector<revision_id>::const_iterator r = bunch_revs.begin();
+ r != bunch_revs.end(); r++)
+ {
+ enumerator_item item;
+ item.tag = enumerator_item::rev;
+ item.ident_a = r->inner();
+ items.push_back(item);
+ }
+}
+
+void
+revision_enumerator::step()
+{
+ while (!done())
+ {
+ if (items.empty() && !topo_revs.empty())
+ {
+ process_bunch();
+ }
+
if (!items.empty())
{
L(FL("revision_enumerator::step extracting item\n"));
============================================================
--- enumerator.hh b2662b4dea76a8d832663ed48342920248449f70
+++ enumerator.hh 1880dae7a6147b0ddd8064bfc4679334b520aeab
@@ -50,10 +50,8 @@ revision_enumerator
app_state & app;
std::set<revision_id> terminal_nodes;
std::set<revision_id> enumerated_nodes;
- std::deque<revision_id> revs;
std::deque<enumerator_item> items;
- std::multimap<revision_id, revision_id> graph;
- std::multimap<revision_id, revision_id> inverse_graph;
+ std::deque<revision_id> topo_revs;
revision_enumerator(enumerator_callbacks & cb,
app_state & app,
@@ -61,8 +59,8 @@ revision_enumerator
std::set<revision_id> const & terminal);
revision_enumerator(enumerator_callbacks & cb,
app_state & app);
- void load_graphs();
- bool all_parents_enumerated(revision_id const & child);
+ void load_revs();
+ void process_bunch();
void step();
bool done();
};
============================================================
--- revision.cc 8cda143f1b14ea5d67e40c9dc325b5ec6f2fd1a7
+++ revision.cc 77ddcf19bb049ae3ca74b008441bcaa7079232d5
@@ -361,17 +361,15 @@ void
// passed in set. if anyone ever needs to toposort the whole graph, then,
// this function would be a good thing to generalize...
void
-toposort(std::set<revision_id> const & revisions,
- std::vector<revision_id> & sorted,
- app_state & app)
+toposort(std::vector<revision_id> & sorted, database & db)
{
sorted.clear();
typedef std::multimap<revision_id, revision_id>::iterator gi;
typedef std::map<revision_id, int>::iterator pi;
std::multimap<revision_id, revision_id> graph;
- app.db.get_revision_ancestry(graph);
+ db.get_revision_ancestry(graph);
std::set<revision_id> leaves;
- app.db.get_revision_ids(leaves);
+ db.get_revision_ids(leaves);
std::map<revision_id, int> pcount;
for (gi i = graph.begin(); i != graph.end(); ++i)
pcount.insert(std::make_pair(i->first, 0));
@@ -387,8 +385,7 @@ toposort(std::set<revision_id> const & r
// now stick them in our ordering (if wanted) and remove them from the
// graph, calculating the new roots as we go
L(FL("new root: %s\n") % (roots.front()));
- if (revisions.find(roots.front()) != revisions.end())
- sorted.push_back(roots.front());
+ sorted.push_back(roots.front());
for(gi i = graph.lower_bound(roots.front());
i != graph.upper_bound(roots.front()); i++)
if(--(pcount[i->second]) == 0)
@@ -402,6 +399,21 @@ toposort(std::set<revision_id> const & r
i != leaves.end(); ++i)
{
L(FL("new leaf: %s\n") % (*i));
+ sorted.push_back(*i);
+ }
+}
+
+void
+toposort(std::set<revision_id> const & revisions,
+ std::vector<revision_id> & sorted,
+ database & db)
+{
+ std::vector<revision_id> all;
+ toposort(all, db);
+ sorted.clear();
+ for (std::vector<revision_id>::const_iterator i = all.begin();
+ i != all.end(); i++)
+ {
if (revisions.find(*i) != revisions.end())
sorted.push_back(*i);
}
============================================================
--- revision.hh 5e3733994a6c92c4f15f0d78aa26669458443d46
+++ revision.hh c6f7e1c8ac336bdec754f0fd1b822124e58eeb5f
@@ -125,9 +125,13 @@ toposort(std::set<revision_id> const & r
void
toposort(std::set<revision_id> const & revisions,
std::vector<revision_id> & sorted,
- app_state & app);
+ database & db);
void
+toposort(std::vector<revision_id> & sorted,
+ database & db);
+
+void
erase_ancestors(std::set<revision_id> & revisions, app_state & app);
void