#
# patch "ChangeLog"
# from [55e1dd795c1b8f0884719a7aebd5cf2766b04e53]
# to [31a85aecdad1cba7e58f7cbf2c1ed4703797a4e9]
#
# patch "change_set.cc"
# from [d653b309754b89d55c8c8801122d282e363f2d7f]
# to [f20e89774ae99040b5867f1d59803b660d29a071]
#
# patch "pcdv.cc"
# from [fb89aec9ecf3531efeea6d7f84d8045e24152b59]
# to [ce879c3270c0d3b7d92a49374a2d138685807a7e]
#
# patch "pcdv.hh"
# from [7ba58f71a35e6f8e212bc926d0ec2f15d00c2dd6]
# to [729ea8ceeea750b9f559fed0403eba28f3270593]
#
========================================================================
--- ChangeLog 55e1dd795c1b8f0884719a7aebd5cf2766b04e53
+++ ChangeLog 31a85aecdad1cba7e58f7cbf2c1ed4703797a4e9
@@ -1,3 +1,11 @@
+2005-08-18 Timothy Brownawell
+
+ PASS 'make check'
+ * pcdv.{cc,hh}: Bugfix tree_state::merge_with_rearrangement .
+ Improve suture-handling code.
+ * pcdv.cc, change_set.cc: Clean up "printf debugging".
+ * change_set.cc: remove commented-out remains of old tree merger
+
2005-08-17 Timothy Brownawell
Improve testsuite compliance: 1 failure remaining.
========================================================================
--- change_set.cc d653b309754b89d55c8c8801122d282e363f2d7f
+++ change_set.cc f20e89774ae99040b5867f1d59803b660d29a071
@@ -1637,50 +1637,6 @@
// begin stuff related to merging
-/*
-static void
-extend_renumbering_via_added_files(path_analysis const & a,
- path_analysis const & b,
- state_renumbering & existing_renumbering,
- state_renumbering & renumbering)
-{
- directory_map a_second_map;
- build_directory_map(a.second, a_second_map);
-
- for (path_state::const_iterator i = b.first.begin();
- i != b.first.end(); ++i)
- {
- path_item item = path_state_item(i);
- if (path_item_type(item) == ptype_file && null_name(path_item_name(item)))
- {
- path_state::const_iterator j = b.second.find(path_state_tid(i));
- I(j != b.second.end());
- path_component leaf_name = path_item_name(path_state_item(j));
-
- I(path_item_type(path_state_item(j)) == ptype_file);
- if (! null_name(leaf_name))
- {
- tid added_parent_tid = path_item_parent(path_state_item(j));
- state_renumbering::const_iterator ren = existing_renumbering.find(added_parent_tid);
- if (ren != existing_renumbering.end())
- added_parent_tid = ren->second;
- directory_map::const_iterator dirent = a_second_map.find(added_parent_tid);
- if (dirent != a_second_map.end())
- {
- boost::shared_ptr node = dirent->second;
- directory_node::const_iterator entry = node->find(leaf_name);
- if (entry != node->end() && directory_entry_type(entry) == ptype_file)
- {
- I(renumbering.find(path_state_tid(i)) == renumbering.end());
- renumbering.insert(std::make_pair(path_state_tid(i),
- directory_entry_tid(entry)));
- }
- }
- }
- }
- }
-}
-*/
static bool
find_item(tid t, path_state const & ps,
path_item & item)
@@ -1691,354 +1647,7 @@
item = path_state_item(i);
return true;
}
-/*
-static bool
-find_items(tid t, path_analysis const & pa,
- path_item & first, path_item & second)
-{
- if (find_item(t, pa.first, first))
- {
- I(find_item(t, pa.second, second));
- I(path_item_type(first) == path_item_type(second));
- return true;
- }
- else
- {
- I(!find_item(t, pa.second, second));
- return false;
- }
-}
-static void
-resolve_conflict(tid t, ptype ty,
- path_analysis const & a_tmp,
- path_analysis const & b_tmp,
- path_item & resolved,
- path_state & resolved_conflicts,
- app_state & app)
-{
- path_state::const_iterator i = resolved_conflicts.find(t);
-
- path_item a_item, b_item;
- find_item(t, a_tmp.second, a_item);
- find_item(t, b_tmp.second, b_item);
-
- file_path anc, a, b, res;
- get_full_path(a_tmp.first, t, anc);
- get_full_path(a_tmp.second, t, a);
- get_full_path(b_tmp.second, t, b);
-
- if (i != resolved_conflicts.end())
- {
- resolved = path_state_item(i);
- }
- else if (null_name(path_item_name(a_item)) &&
- ! null_name(path_item_name(b_item)))
- {
- L(F("delete of %s dominates rename to %s\n") % anc % b);
- resolved = a_item;
- resolved_conflicts.insert(std::make_pair(t, resolved));
- }
- else if (null_name(path_item_name(b_item)) &&
- ! null_name(path_item_name(a_item)))
- {
- L(F("delete of %s dominates rename to %s\n") % anc % a);
- resolved = b_item;
- resolved_conflicts.insert(std::make_pair(t, resolved));
- }
- else
- {
- switch (ty)
- {
- case ptype_file:
- N(app.lua.hook_resolve_file_conflict(anc, a, b, res),
- F("unable to resolve file conflict '%s' -> '%s' vs. '%s'") % anc % a % b);
- break;
- case ptype_directory:
- N(app.lua.hook_resolve_dir_conflict(anc, a, b, res),
- F("unable to resolve dir conflict '%s' -> '%s' vs. '%s'") % anc % a % b);
- break;
- }
-
- N((res == a || res == b),
- F("illegal conflict resolution '%s', wanted '%s' or '%s'\n") % res % a % b);
-
- if (res == a)
- I(find_item(t, a_tmp.second, resolved));
- else
- I(find_item(t, b_tmp.second, resolved));
-
- resolved_conflicts.insert(std::make_pair(t, resolved));
- }
-}
-
-static void
-ensure_no_rename_clobbers(path_analysis const & a,
- path_analysis const & b)
-{
- // there is a special non-mergable pair of changes which we need
- // to identify here:
- //
- // tid i : x -> y in change A
- // tid j : z -> x in change B
- //
- // on the surface it looks like it ought to be mergable, since there is
- // no conflict in the tids. except for one problem: B effectively
- // clobbered i with j. there is nothing you can append to change B to
- // revive the identity of i; in fact you risk having i and j identified
- // if you form the naive merge concatenation BA. indeed, since A and B
- // both supposedly start in the same state (in which i occupies name x),
- // it really ought not to be possible to form B; you should have to
- // accompany it with some sort of statement about the fate of i.
- //
- // as it stands, we're going to fault when we see this. if it turns out
- // that there's a legal way of constructing such changes, one option is
- // to synthesize a delete of i in B; essentially read "z->x" as an
- // implicit "delete x first if it exists in post-state".
- //
- // however, for the time being this is a fault because we believe they
- // should be globally illegal clobbers.
-
- directory_map b_first_map, b_second_map;
- build_directory_map (b.first, b_first_map);
- build_directory_map (b.second, b_second_map);
- tid a_tid, b_tid;
-
- for (path_state::const_iterator i = a.first.begin();
- i != a.first.end(); ++i)
- {
- file_path anc_path, a_second_path;
- a_tid = path_state_tid(i);
- get_full_path(a.first, a_tid, anc_path);
-
- if (! lookup_path(anc_path, b_first_map, b_tid))
- {
- file_path b_second_path;
- reconstruct_path(anc_path, b_first_map, b.second, b_second_path);
-
- N(! lookup_path(b_second_path, b_second_map, b_tid),
- (F("tid %d (%s) clobbered tid %d (%s)\n")
- % b_tid % b_second_path
- % a_tid % anc_path));
- }
- }
-
-}
-
-static void
-project_missing_changes(path_analysis const & a_tmp,
- path_analysis const & b_tmp,
- path_analysis & b_merged,
- path_state & resolved_conflicts,
- app_state & app)
-{
-
- // for each tid t adjusted in a:
- // - if t exists in b:
- // - if the change to t in b == change in a, skip
- // - else resolve conflict
- // - if conflict resolved in favour of a, append to merged
- // - if resolved in favour of b, skip
- // - else (no t in b) insert a's change to t in merged
-
- for (path_state::const_iterator i = a_tmp.first.begin();
- i != a_tmp.first.end(); ++i)
- {
- tid t = path_state_tid(i);
- path_item a_first_item, a_second_item;
- path_item b_first_item, b_second_item;
- I(find_items(t, a_tmp, a_first_item, a_second_item));
- if (find_items(t, b_tmp, b_first_item, b_second_item))
- {
- I(a_first_item == b_first_item);
- if (a_second_item == b_second_item)
- {
- L(F("skipping common change on %s (tid %d)\n")
- % path_item_name(a_first_item) % t);
- }
- else if (a_first_item == a_second_item)
- {
- L(F("skipping neutral change of %s -> %s (tid %d)\n")
- % path_item_name(a_first_item)
- % path_item_name(a_second_item)
- % t);
- }
- else if (b_first_item == b_second_item)
- {
- L(F("propagating change on %s -> %s (tid %d)\n")
- % path_item_name(b_first_item)
- % path_item_name(b_second_item)
- % t);
- b_merged.first.insert(std::make_pair(t, b_second_item));
- b_merged.second.insert(std::make_pair(t, a_second_item));
- }
- else
- {
- // conflict
- path_item resolved;
- resolve_conflict(t, path_item_type(a_first_item), a_tmp, b_tmp,
- resolved, resolved_conflicts, app);
-
- if (resolved == a_second_item)
- {
- L(F("conflict detected, resolved in A's favour\n"));
- b_merged.first.insert(std::make_pair(t, b_second_item));
- b_merged.second.insert(std::make_pair(t, a_second_item));
- }
- else
- {
- L(F("conflict detected, resolved in B's favour\n"));
- }
- }
- }
- else
- {
- // there was no entry in b at all for this tid, copy it
- b_merged.first.insert(std::make_pair(t, a_first_item));
- b_merged.second.insert(std::make_pair(t, a_second_item));
- }
- }
-
- // now drive through b.second's view of the directory structure, in case
- // some intermediate b-only directories showed up the preimages of
- // A-favoured conflicts.
- extend_state(b_tmp.second, b_merged.first);
- extend_state(b_merged.first, b_merged.second);
-}
-
-static void
-rebuild_analysis(path_analysis const & src,
- path_analysis & dst,
- tid_source & ts)
-{
- state_renumbering renumbering;
-
- for (path_state::const_iterator i = src.first.begin();
- i != src.first.end(); ++i)
- renumbering.insert(std::make_pair(path_state_tid(i), ts.next()));
-
- dst = src;
- apply_state_renumbering(renumbering, dst);
-}
-
-static void
-merge_disjoint_analyses(path_analysis const & a,
- path_analysis const & b,
- path_analysis & a_renumbered,
- path_analysis & b_renumbered,
- path_analysis & a_merged,
- path_analysis & b_merged,
- tid_source & ts,
- app_state & app)
-{
- // we have anc->a and anc->b and we want to construct a->merged and
- // b->merged, leading to the eventual identity concatenate(a,a_merged) ==
- // concatenate(b,b_merged).
-
- path_analysis a_tmp(a), b_tmp(b);
- state_renumbering renumbering;
- MM(renumbering);
-
- ensure_tids_disjoint(a_tmp, b_tmp);
-
- // fault on a particular class of mal-formed changesets
- ensure_no_rename_clobbers(a_tmp, b_tmp);
- ensure_no_rename_clobbers(b_tmp, a_tmp);
-
- // a.first and b.first refer to the same state-of-the-world.
- //
- // we begin by driving all the entries in a.first into b.first and vice
- // versa.
-
- {
- directory_map a_first_map, b_first_map;
- build_directory_map(a_tmp.first, a_first_map);
- build_directory_map(b_tmp.first, b_first_map);
- ensure_entries_exist(a_tmp.first, b_first_map, b_tmp.first, ts);
- ensure_entries_exist(b_tmp.first, a_first_map, a_tmp.first, ts);
- }
-
- // we then drive any of the new arrivals in a.first to a.second, and
- // likewise on b
-
- {
- directory_map a_second_map, b_second_map;
- build_directory_map(a_tmp.second, a_second_map);
- build_directory_map(b_tmp.second, b_second_map);
- ensure_entries_exist(a_tmp.first, a_second_map, a_tmp.second, ts);
- ensure_entries_exist(b_tmp.first, b_second_map, b_tmp.second, ts);
- }
-
- // we then index, identify, and renumber all the immediately apparant
- // entries in each side.
-
- {
- std::map a_first_files, a_first_dirs;
- std::map b_first_files, b_first_dirs;
- index_entries(a_tmp.first, a_first_files, a_first_dirs);
- index_entries(b_tmp.first, b_first_files, b_first_dirs);
- extend_renumbering_from_path_identities(a_first_files, b_first_files, renumbering);
- extend_renumbering_from_path_identities(a_first_dirs, b_first_dirs, renumbering);
- }
-
- // once renamed, b_tmp will have moved a fair bit closer to a_tmp, in
- // terms of tids. there is still one set of files we haven't accounted
- // for, however: files added in a and b.
-
- {
- state_renumbering aux_renumbering;
- extend_renumbering_via_added_files(a_tmp, b_tmp, renumbering, aux_renumbering);
- for (state_renumbering::const_iterator i = aux_renumbering.begin();
- i != aux_renumbering.end(); ++i)
- {
- I(renumbering.find(i->first) == renumbering.end());
- renumbering.insert(*i);
- }
- }
-
- // renumbering now contains a *complete* renumbering of b->a,
- // so we reset a_tmp and b_tmp, and renumber b_tmp under this
- // scheme.
-
- a_tmp = a;
- b_tmp = b;
- apply_state_renumbering(renumbering, b_tmp);
-
- a_renumbered = a_tmp;
- b_renumbered = b_tmp;
-
- // now we're ready to merge (and resolve conflicts)
- path_state resolved_conflicts;
- project_missing_changes(a_tmp, b_tmp, b_merged, resolved_conflicts, app);
- project_missing_changes(b_tmp, a_tmp, a_merged, resolved_conflicts, app);
-
- {
- // now check: the merge analyses, when concatenated with their
- // predecessors, should lead to the same composite rearrangement
-
- tid_source ts_tmp;
- path_analysis anc_a_check, a_merge_check, a_check;
- path_analysis anc_b_check, b_merge_check, b_check;
- change_set::path_rearrangement a_re, b_re;
-
- rebuild_analysis(a, anc_a_check, ts_tmp);
- rebuild_analysis(b, anc_b_check, ts_tmp);
- rebuild_analysis(a_merged, a_merge_check, ts_tmp);
- rebuild_analysis(b_merged, b_merge_check, ts_tmp);
-
- std::set anc_a_killed, anc_b_killed;
- extract_killed(anc_a_check, anc_a_killed);
- extract_killed(anc_b_check, anc_b_killed);
-
- concatenate_disjoint_analyses(anc_a_check, a_merge_check, anc_a_killed, a_check);
- concatenate_disjoint_analyses(anc_b_check, b_merge_check, anc_b_killed, b_check);
- compose_rearrangement(a_check, a_re);
- compose_rearrangement(b_check, b_re);
- I(a_re == b_re);
- }
-
-}
-*/
struct itempaths
{
file_path anc;
@@ -2396,7 +2005,7 @@
rl.push_back(l);
rl.push_back(r);
tree_state m = tree_state::merge_with_resolution(rl, res, "abccb");
- I(m.conflict(m).empty());
+ N(m.conflict(m).empty(), F("Provided filename resolution is inconsistent."));
// calculate outputs
std::map ip;
========================================================================
--- pcdv.cc fb89aec9ecf3531efeea6d7f84d8045e24152b59
+++ pcdv.cc ce879c3270c0d3b7d92a49374a2d138685807a7e
@@ -839,6 +839,7 @@
for (set::const_iterator i = leafset.begin();
i != leafset.end(); ++i)
todo.push_back(*i);
+ // erase_ancestors(leafset)
while (todo.size())
{
item_data::const_iterator i = versions->find(todo.front());
@@ -1036,6 +1037,19 @@
}
}
+item_id
+tree_state::getid(item_id from) const
+{
+ std::map::const_iterator i = sutures->find(from);
+ item_id out = from;
+ while (i != sutures->end())
+ {
+ out = i->second;
+ i = sutures->find(out);
+ }
+ return out;
+}
+
const int deleted_dir(1);
const int deleted_file(2);
const int renamed_dir(3);
@@ -1140,6 +1154,7 @@
pi = items->size() - 1;
pd = cit.intern(pdir());
outmap.insert(make_pair(pd, pi));
+ L(F("New implied directory %1%") % pdir);
}
}
@@ -1153,9 +1168,13 @@
// deleted dirs, deleted files, renamed dirs, renamed files, added files
// sort key is (depth, class, rev#)
orderer todo;
+ typedef boost::tuple::const_iterator,
+ item_id,
+ item_id> unch;
+ std::set unchanged;
std::map outmap;// for tree poststate
+ std::set done;
std::vector > premaps;//for tree prestates
- std::vector > postmaps;//for rearrangement poststates
{
int n;
std::vector::const_iterator i;
@@ -1168,8 +1187,9 @@
tree_state out(mash(trees));
fpid rootid = cit.intern(file_path()());
outmap.insert(make_pair(rootid, -1));
+ done.insert(-1);
- // populate outmap with any unchanged entries
+ // find any unchanged entries
{
std::vector::const_iterator x;
std::vector::const_iterator i;
@@ -1177,44 +1197,71 @@
i != trees.end() && x != changes.end(); ++i, ++x)
{
premaps.push_back(std::map());
- std::vector >
- curr = i->current_with_dirs();
- for (std::vector >::const_iterator
- j = curr.begin(); j != curr.end(); ++j)
+ for (std::map::const_iterator
+ j = i->states->begin(); j != i->states->end(); ++j)
{
- fpid myid = cit.intern(j->second());
+ std::set s = j->second.current_names();
+ I(s.size() == 1);
+ file_path fp = i->get_full_name(*s.begin());
+ if ((fp == file_path()))
+ continue;
+ fpid myid = cit.intern(fp());
premaps.back().insert(make_pair(myid, j->first));
// does it stay put?
- bool deldir = (x->deleted_dirs.find(j->second)
+ bool deldir = (x->deleted_dirs.find(fp)
!= x->deleted_dirs.end());
- bool delfile = (x->deleted_files.find(j->second)
+ bool delfile = (x->deleted_files.find(fp)
!= x->deleted_files.end());
- bool mvdir = (x->renamed_dirs.find(j->second)
+ bool mvdir = (x->renamed_dirs.find(fp)
!= x->renamed_dirs.end());
- bool mvfile = (x->renamed_files.find(j->second)
+ bool mvfile = (x->renamed_files.find(fp)
!= x->renamed_files.end());
if (!deldir && !delfile && !mvdir && !mvfile)
- {
- std::pair::iterator, bool> r;
- r = outmap.insert(make_pair(myid, j->first));
- if (r.first->second != j->first)
- {
- W(F("Colliding over %1%") % j->second());
- out.add_suture(r.first->second, j->first);
- }
- }
+ unchanged.insert(boost::make_tuple(i,
+ j->first,
+ (*s.begin()).first));
}
}
}
+ int lastlevel = 0;
for (orderer::const_iterator i = todo.begin(); i != todo.end(); ++i)
{
file_path const & from(i->second.get<0>());
file_path const & to(i->second.get<1>());
bool is_dir(i->second.get<2>());
+ int level(i->first.get<0>());
int type(i->first.get<1>());
int which(i->first.get<2>());
+ if (level > lastlevel)
+ {
+ for (std::set::iterator i = unchanged.begin();
+ i != unchanged.end(); ++i)
+ {
+ item_id myid = out.getid(i->get<1>());
+ item_id pid = out.getid(i->get<2>());
+ // process this item if its parent has been processed
+ if (done.find(pid) == done.end())
+ continue;
+ // but don't process the same item twice
+ if (done.find(myid) != done.end())
+ continue;
+ std::map::const_iterator
+ j = out.states->find(myid);
+ I(j != out.states->end());
+ file_path fp = out.get_full_name(j->second);
+ done.insert(myid);
+ std::pair::iterator, bool> r;
+ r = outmap.insert(make_pair(cit.intern(fp()), myid));
+ if (r.first->second != myid)
+ {
+ W(F("Colliding over %1%") % fp);
+ out.add_suture(r.first->second, myid);
+ }
+ }
+ lastlevel = level;
+ }
item_id current_id;
std::map::iterator j = out.states->end();
bool addednew = false;
@@ -1235,7 +1282,7 @@
I(p.second);
j = p.first;
addednew = true;
-// P(F("New item: %1%") % current_id);
+ L(F("New item: %1%") % to);
}
else
{
@@ -1256,8 +1303,6 @@
}
I(j != out.states->end());
item_status & current_item(j->second);
-// P(F("%1% (%2%) from %3% to %4%, by %5% (type %6%) in %7%") % current_id
-// % out.get_full_name(j->second) % from % to % which % type % revision);
// ...find where it goes...
if (type == deleted_file || type == deleted_dir)
@@ -1265,6 +1310,7 @@
current_item = current_item.rename(out.itx->intern(revision),
item_id(-1),
make_null_component());
+ done.insert(current_id);
continue;
}
{
@@ -1300,14 +1346,39 @@
current_item.is_dir = is_dir;
file_path recon = out.get_full_name(current_item);
I(recon == to);
+ done.insert(current_id);
std::pair::iterator, bool> r;
r = outmap.insert(make_pair(cit.intern(to()), current_id));
if (r.first->second != current_id)
{
W(F("Colliding over %1%") % to);
- out.add_suture(r.first->second, j->first);
+ out.add_suture(r.first->second, current_id);
}
}
+ for (std::set::iterator i = unchanged.begin();
+ i != unchanged.end(); ++i)
+ {
+ item_id myid = out.getid(i->get<1>());
+ item_id pid = out.getid(i->get<2>());
+ // process this item if its parent has been processed
+ if (done.find(pid) == done.end())
+ continue;
+ // but don't process the same item twice
+ if (done.find(myid) != done.end())
+ continue;
+ std::map::const_iterator
+ j = out.states->find(myid);
+ I(j != out.states->end());
+ file_path fp = out.get_full_name(j->second);
+ done.insert(myid);
+ std::pair::iterator, bool> r;
+ r = outmap.insert(make_pair(cit.intern(fp()), myid));
+ if (r.first->second != myid)
+ {
+ W(F("Colliding over %1%") % fp);
+ out.add_suture(r.first->second, myid);
+ }
+ }
out.apply_sutures();
return out;
}
@@ -1386,13 +1457,6 @@
I(right.size() == 1);
c.lnames.push_back(get_full_name(*left.begin()));
c.rnames.push_back(other.get_full_name(*right.begin()));
- P(F("split: '%1%' vs '%2%' ('%3%' vs '%4%' (dirs are %5% vs %6%))")
- % get_full_name(*left.begin())
- % other.get_full_name(*right.begin())
- % merged.get_full_name(*left.begin())
- % merged.get_full_name(*right.begin())
- % left.begin()->first
- % right.begin()->first);
out.push_back(c);
}
for (std::set::const_iterator
@@ -1656,7 +1720,7 @@
}
}
}
- ++lastlevel;
+ lastlevel = i->first;
}
item_id const & id(i->second.first);
splitpath sp(i->second.second);
@@ -1784,8 +1848,7 @@
{
std::map::const_iterator
i = states->find(x.first);
- if (i != states->end());
- else E(false, F("Missing: %1%") % x.first);
+ I(i != states->end());
std::set y = i->second.current_names();
if (y.size() != 1)
{
========================================================================
--- pcdv.hh 7ba58f71a35e6f8e212bc926d0ec2f15d00c2dd6
+++ pcdv.hh 729ea8ceeea750b9f559fed0403eba28f3270593
@@ -255,6 +255,7 @@
void add_suture(item_id l, item_id r);
void apply_sutures() const;
+ item_id getid(item_id from) const;
public:
~tree_state();