# # 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();