# 
# patch "ChangeLog"
#  from [b057c2543646fc3da2fa4a0f6ad90194f3b52a94]
#    to [5cec6a775da7b25da5dcc392abec0e8ed4054030]
# 
# patch "commands.cc"
#  from [c37e80febb5d27822b14f8fb0ebb0a509e5efb79]
#    to [314b18e558832d2fc334767f00d057ad4c623fa7]
# 
# patch "pcdv.cc"
#  from [ec5439e5a58d5895d73ce163d6c8ac96ce7d908e]
#    to [0bd04eacd73e9056c97f92d2a08772f5a624f147]
# 
# patch "pcdv.hh"
#  from [42bf317c405625ccb402ce51c6ec96b65c187907]
#    to [6dc79305b5e65ce553a85b79f998f0c7da205f2d]
# 
========================================================================
--- ChangeLog	b057c2543646fc3da2fa4a0f6ad90194f3b52a94
+++ ChangeLog	5cec6a775da7b25da5dcc392abec0e8ed4054030
@@ -1,3 +1,8 @@
+2005-08-03  Timothy Brownawell  <address@hidden>
+
+	* pcdv.{cc,hh}: Work on merge functions for trees.
+	* commands.cc: Misc. changes to pcdv driver
+
 2005-08-02  Timothy Brownawell  <address@hidden>
 
 	* pcdv.{cc,hh}: Add history-aware filetree merge.
========================================================================
--- commands.cc	c37e80febb5d27822b14f8fb0ebb0a509e5efb79
+++ commands.cc	314b18e558832d2fc334767f00d057ad4c623fa7
@@ -3888,14 +3888,18 @@
             vector<revision_id> & roots,
             app_state & app)
 {
-  manifest_id mid;
-  app.db.get_revision_manifest(start, mid);
-  manifest_map m;
-  app.db.get_manifest(mid, m);
-  manifest_map::const_iterator i = m.find(fp);
-  I(i != m.end());
-  file_id ident = manifest_entry_id(i);
-  fileids.insert(make_pair(start, make_pair(ident, fp)));
+  if (!(fp == file_path()))
+    {
+      manifest_id mid;
+      app.db.get_revision_manifest(start, mid);
+      manifest_map m;
+      app.db.get_manifest(mid, m);
+      manifest_map::const_iterator i = m.find(fp);
+      I(i != m.end());
+      file_id ident = manifest_entry_id(i);
+      fileids.insert(make_pair(start, make_pair(ident, fp)));
+    }
+
   std::deque<std::pair<revision_id, file_path> > todo;
   todo.push_back(make_pair(start, fp));
   ticker num("file_id count", "F", 1);
@@ -3967,6 +3971,162 @@
     }
 }
 
+void
+prdiff(change_set::path_rearrangement const & a,
+       change_set::path_rearrangement const & b)
+{
+  std::set<file_path>::const_iterator sa, sb;
+  std::map<file_path, file_path>::const_iterator ma, mb;
+
+  sa = a.deleted_files.begin();
+  sb = b.deleted_files.begin();
+  while (sa != a.deleted_files.end() || sb != b.deleted_files.end())
+    {
+      if (sa == a.deleted_files.end())
+        {
+          P(F("> delete_file %1%") % *sb);
+          ++sb;
+        }
+      else if (sb == b.deleted_files.end())
+        {
+          P(F("< delete_file %1%") % *sa);
+          ++sa;
+        }
+      else if (*sa < *sb)
+        {
+          P(F("< delete_file %1%") % *sa);
+         ++sa;
+        }
+      else if (*sb < *sa)
+        {
+          P(F("> delete_file %1%") % *sb);
+          ++sb;
+        }
+      else
+        ++sa, ++sb;
+    }
+
+  sa = a.deleted_dirs.begin();
+  sb = b.deleted_dirs.begin();
+  while (sa != a.deleted_dirs.end() || sb != b.deleted_dirs.end())
+    {
+      if (sa == a.deleted_dirs.end())
+        {
+          P(F("> delete_dir %1%") % *sb);
+          ++sb;
+        }
+      else if (sb == b.deleted_dirs.end())
+        {
+          P(F("< delete_dir %1%") % *sa);
+          ++sa;
+        }
+      else if (*sa < *sb)
+        {
+          P(F("< delete_dir %1%") % *sa);
+         ++sa;
+        }
+      else if (*sb < *sa)
+        {
+          P(F("> delete_dir %1%") % *sb);
+          ++sb;
+        }
+      else
+        ++sa, ++sb;
+    }
+
+  sa = a.added_files.begin();
+  sb = b.added_files.begin();
+  while (sa != a.added_files.end() || sb != b.added_files.end())
+    {
+      if (sa == a.added_files.end())
+        {
+          P(F("> add_file %1%") % *sb);
+          ++sb;
+        }
+      else if (sb == b.added_files.end())
+        {
+          P(F("< add_file %1%") % *sa);
+          ++sa;
+        }
+      else if (*sa < *sb)
+        {
+          P(F("< add_file %1%") % *sa);
+         ++sa;
+        }
+      else if (*sb < *sa)
+        {
+          P(F("> add_file %1%") % *sb);
+          ++sb;
+        }
+      else
+        ++sa, ++sb;
+    }
+
+  ma = a.renamed_files.begin();
+  mb = b.renamed_files.begin();
+  while (ma != a.renamed_files.end() || mb != b.renamed_files.end())
+    {
+      if (ma == a.renamed_files.end())
+        {
+          P(F("> rename_file %1%") % mb->first);
+          P(F(">          to %1%") % mb->second);
+          ++mb;
+        }
+      else if (mb == b.renamed_files.end())
+        {
+          P(F("< rename_file %1%") % ma->first);
+          P(F(">          to %1%") % ma->second);
+          ++ma;
+        }
+      else if (*ma < *mb)
+        {
+          P(F("< rename_file %1%") % ma->first);
+          P(F(">          to %1%") % ma->second);
+         ++ma;
+        }
+      else if (*mb < *ma)
+        {
+          P(F("> rename_file %1%") % mb->first);
+          P(F(">          to %1%") % mb->second);
+          ++mb;
+        }
+      else
+        ++ma, ++mb;
+    }
+
+  ma = a.renamed_dirs.begin();
+  mb = b.renamed_dirs.begin();
+  while (ma != a.renamed_dirs.end() || mb != b.renamed_dirs.end())
+    {
+      if (ma == a.renamed_dirs.end())
+        {
+          P(F("> rename_dir %1%") % mb->first);
+          P(F(">         to %1%") % mb->second);
+          ++mb;
+        }
+      else if (mb == b.renamed_dirs.end())
+        {
+          P(F("< rename_dir %1%") % ma->first);
+          P(F(">         to %1%") % ma->second);
+          ++ma;
+        }
+      else if (*ma < *mb)
+        {
+          P(F("< rename_dir %1%") % ma->first);
+          P(F(">         to %1%") % ma->second);
+         ++ma;
+        }
+      else if (*mb < *ma)
+        {
+          P(F("> rename_dir %1%") % mb->first);
+          P(F(">         to %1%") % mb->second);
+          ++mb;
+        }
+      else
+        ++ma, ++mb;
+    }
+}
+
 CMD(pcdv, "debug", "REVISION REVISION FILENAME",
     "precise-cdv merge FILENAME in the two given revisions",
     OPT_NONE)
@@ -4032,8 +4192,22 @@
           treevec.push_back(from);
           revec.push_back(edge_changes(i).rearrangement);
         }
-      tree_state newtree(tree_state::merge(treevec, revec,
+      tree_state newtree(tree_state::merge_with_rearrangement(treevec, revec,
                                            roots.front().inner()()));
+      if (rs.edges.size() > 1)
+        for (unsigned int i = 0; i != rs.edges.size(); ++i)
+          {
+            std::set<path_conflict::resolution> res;
+            change_set::path_rearrangement changes;
+            idx(treevec, i).get_changes_for_merge(newtree, changes);
+            if (!(idx(revec, i) == changes))
+              {
+//                P(F("From parent #%1% to %2%") % i % roots.front());
+//                P(F("Real vs. calc"));
+//                prdiff(idx(revec, i), changes);
+//                I(false);
+              }
+          }
       trees.insert(make_pair(roots.front(), newtree));
 
       std::map<revision_id, std::pair<file_id, file_path> >::const_iterator
@@ -4101,6 +4275,52 @@
       roots.pop_front();
     }
 
+  std::map<revision_id, tree_state>::const_iterator lt(trees.find(left));
+  std::map<revision_id, tree_state>::const_iterator rt(trees.find(right));
+  I(lt != trees.end());
+  I(rt != trees.end());
+  std::vector<path_conflict> conf(lt->second.conflict(rt->second));
+/*
+  std::vector<std::pair<item_id, file_path> > t(lt->second.current());
+  for (std::vector<std::pair<item_id, file_path> >::const_iterator
+         i = t.begin(); i != t.end(); ++i)
+    {
+      P(F("%1%: %2%") % i->first % i->second);
+    }
+*/
+  P(F("There are %1% conflicts:") % conf.size());
+  for (std::vector<path_conflict>::const_iterator i = conf.begin();
+       i != conf.end(); ++i)
+    {
+      P(F("Type: %1%") % ((i->type == path_conflict::collision)
+                          ?"Collision":"Split"));
+      for (unsigned int j = 0; j < i->items.size(); ++j)
+        {
+          P(F("Item %1%:") % idx(i->items, j));
+          P(F("Lname: %1%") % idx(i->lnames, j));
+          P(F("Rname: %1%") % idx(i->rnames, j));
+        }
+      P(F("Name: %1%") % i->name);
+    }
+  if (conf.empty())
+    {
+      std::set<path_conflict::resolution> res;
+      std::vector<tree_state> parents;
+      parents.push_back(lt->second);
+      parents.push_back(rt->second);
+      change_set::path_rearrangement changes;
+      data dat;
+      tree_state mt(tree_state::merge_with_resolution(parents, res, "xxx"));
+      lt->second.get_changes_for_merge(mt, changes);
+//      P(F("Left changes:"));
+//      write_path_rearrangement(changes, dat);
+//      P(F("%1%") % dat);
+      rt->second.get_changes_for_merge(mt, changes);
+//      P(F("Right changes:"));
+//      write_path_rearrangement(changes, dat);
+//      P(F("%1%") % dat);
+    }
+
   map<revision_id, file_state>::iterator l = files.find(left);
   N(l != files.end(), F("Not found: %s.") % left);
   map<revision_id, file_state>::iterator r = files.find(right);
@@ -4109,16 +4329,7 @@
   P(F("Done building history."));
 
   vector<merge_section> result(l->second.conflict(r->second));
-  P(F(""));
   show_conflict(consolidate(result));
-  std::map<revision_id, tree_state>::const_iterator lt(trees.find(left));
-  std::map<revision_id, tree_state>::const_iterator rt(trees.find(right));
-  std::vector<std::pair<item_id, file_path> > t(lt->second.current());
-  for (std::vector<std::pair<item_id, file_path> >::const_iterator
-         i = t.begin(); i != t.end(); ++i)
-    {
-      P(F("%1%: %2%") % i->first % i->second);
-    }
 }
 
 
========================================================================
--- pcdv.cc	ec5439e5a58d5895d73ce163d6c8ac96ce7d908e
+++ pcdv.cc	0bd04eacd73e9056c97f92d2a08772f5a624f147
@@ -1,6 +1,7 @@
 #include <set>
 #include <map>
 #include <deque>
+#include <boost/tuple/tuple_comparison.hpp>
 
 #include "sanity.hh"
 #include "pcdv.hh"
@@ -497,9 +498,9 @@
         newstate.states->insert(make_pair(r->first,r->second.copy())), ++r;
       else if (r == other.states->end())
         newstate.states->insert(make_pair(l->first,l->second.copy())), ++l;
-      else if (l->first < r->first)
+      else if (l->first > r->first)
         newstate.states->insert(make_pair(r->first,r->second.copy())), ++r;
-      else if (r->first < l->first)
+      else if (r->first > l->first)
         newstate.states->insert(make_pair(l->first,l->second.copy())), ++l;
       else
         {
@@ -770,20 +771,26 @@
 
 item_status::item_status():
              versions(new item_data()),
-             leaves(new vector<revid>())
+             leaves(),
+             is_dir(false)
 {
   versions->insert(make_pair(revid(-1),
                              make_pair(make_pair(item_id(-1),
                                                  make_null_component()),
                                        vector<revid>())));
-  leaves->push_back(revid(-1));
+  std::vector<revid> * l = new std::vector<revid>();
+  l->push_back(revid(-1));
+  leaves.reset(l);
 }
 
 item_status::item_status(boost::shared_ptr<item_data> ver):
              versions(ver),
-             leaves(new vector<revid>())
+             leaves(),
+             is_dir(false)
 {
-  leaves->push_back(revid(-1));
+  std::vector<revid> * l = new std::vector<revid>();
+  l->push_back(revid(-1));
+  leaves.reset(l);
   versions->insert(make_pair(revid(-1),
                              make_pair(make_pair(item_id(-1),
                                                  make_null_component()),
@@ -792,7 +799,8 @@
 
 item_status::item_status(item_status const & x):
                versions(x.versions),
-               leaves(x.leaves)
+               leaves(x.leaves),
+               is_dir(x.is_dir)
 {}
 
 item_status::~item_status()
@@ -819,6 +827,7 @@
 item_status::merge(item_status const & other) const
 {
   I(versions == other.versions);
+  I(is_dir == other.is_dir);
   set<revid> leafset, done;
   std::deque<revid> todo;
   for (vector<revid>::const_iterator i = leaves->begin();
@@ -876,6 +885,12 @@
       I(j != versions->end());
       out.insert(j->second.first);
     }
+  if (out.size() > 1
+      && out.find(make_pair(-1, make_null_component())) != out.end())
+    {
+      out.clear();
+      out.insert(make_pair(-1, make_null_component()));
+    }
   return out;
 }
 
@@ -883,23 +898,44 @@
 item_status::rename(revid rev, item_id new_parent, path_component new_name) const
 {
   item_state newstate(make_pair(new_parent, new_name));
+//  {
+    item_data::iterator i = versions->find(rev);
+    if (i != versions->end())
+      {
+//        I(i->second.first == newstate);
+// An error, but it's triggered by errors already in the monotone db.
+// These are of the form cs_left = {}, cs_right = {drop, add}
+// So, warn instead of failing.
+        if (i->second.first == newstate)
+          return *this;
+        W(F("Renaming a file to multiple names within one revision."));
+      }
+//  }
   vector<revid> newleaves, badleaves;
-  for (vector<revid>::iterator i = leaves->begin();
+  newleaves.push_back(rev);
+  for (vector<revid>::const_iterator i = leaves->begin();
         i != leaves->end(); ++i)
     {
       item_data::const_iterator j = versions->find(*i);
       I(j != versions->end());
       if (j->second.first == newstate)
         newleaves.push_back(*i);
-      else
+      else if (*i != rev)
         badleaves.push_back(*i);
     }
+  if (i != versions->end())
+    versions->erase(i);
+  versions->insert(make_pair(rev, make_pair(newstate, badleaves)));
   if (badleaves.empty())
-    return *this;
+    {
+      std::set<item_state> c = current_names();
+      I(c.size() == 1);
+      I(*c.begin() == newstate);
+      return *this;
+    }
 
-  newleaves.push_back(rev);
-  versions->insert(make_pair(rev, make_pair(newstate, badleaves)));
-  return new_version(newleaves);
+  item_status out(new_version(newleaves));
+  return out;
 }
 
 
@@ -927,8 +963,8 @@
 const int renamed_file(4);
 const int added_dir(5); // not used
 const int added_file(6);
-typedef std::multimap<std::pair<int, std::pair<int, int> >,
-                      std::pair<file_path, file_path> > orderer;
+typedef std::multimap<boost::tuple<int, int, int>,
+                    boost::tuple<file_path, file_path, bool> > orderer;
 
 void
 process_rearrangement(change_set::path_rearrangement const & changes,
@@ -939,18 +975,18 @@
     {
       std::vector<path_component> splitted;
       split_path(*i, splitted);
-      todo.insert(make_pair(make_pair(splitted.size(),
-                                      make_pair(deleted_dir, num)),
-                            make_pair(*i, file_path())));
+      todo.insert(make_pair(boost::make_tuple(splitted.size(),
+                                              deleted_dir, num),
+                            boost::make_tuple(*i, file_path(), true)));
     }
   for (std::set<file_path>::const_iterator i = changes.deleted_files.begin();
        i != changes.deleted_files.end(); ++i)
     {
       std::vector<path_component> splitted;
       split_path(*i, splitted);
-      todo.insert(make_pair(make_pair(splitted.size(),
-                                      make_pair(deleted_file, num)),
-                            make_pair(*i, file_path())));
+      todo.insert(make_pair(boost::make_tuple(splitted.size(),
+                                              deleted_file, num),
+                            boost::make_tuple(*i, file_path(), false)));
     }
   for (std::map<file_path, file_path>::const_iterator
          i = changes.renamed_dirs.begin();
@@ -958,9 +994,9 @@
     {
       std::vector<path_component> splitted;
       split_path(i->second, splitted);
-      todo.insert(make_pair(make_pair(splitted.size(),
-                                      make_pair(renamed_dir, num)),
-                            make_pair(i->first, i->second)));
+      todo.insert(make_pair(boost::make_tuple(splitted.size(),
+                                              renamed_dir, num),
+                            boost::make_tuple(i->first, i->second, true)));
     }
   for (std::map<file_path, file_path>::const_iterator
          i = changes.renamed_files.begin();
@@ -968,24 +1004,69 @@
     {
       std::vector<path_component> splitted;
       split_path(i->second, splitted);
-      todo.insert(make_pair(make_pair(splitted.size(),
-                                      make_pair(renamed_file, num)),
-                            make_pair(i->first, i->second)));
+      todo.insert(make_pair(boost::make_tuple(splitted.size(),
+                                              renamed_file, num),
+                            boost::make_tuple(i->first, i->second, false)));
     }
   for (std::set<file_path>::const_iterator i = changes.added_files.begin();
        i != changes.added_files.end(); ++i)
     {
       std::vector<path_component> splitted;
       split_path(*i, splitted);
-      todo.insert(make_pair(make_pair(splitted.size(),
-                                      make_pair(added_file, num)),
-                            make_pair(file_path(), *i)));
+      todo.insert(make_pair(boost::make_tuple(splitted.size(),
+                                              added_file, num),
+                            boost::make_tuple(file_path(), *i, false)));
     }
 
 }
 
+
+void
+tree_state::ensure_dir_exists(std::vector<path_component> const & parts,
+                             std::map<fpid, item_id> & outmap,
+                             interner<fpid> & cit,
+                             std::string const & revision)
+{
+  // parent directory implied, did not previously exist
+  std::vector<path_component> p(parts);
+  bool newfile;
+  file_path pdir;
+  fpid pd;
+  do
+    {
+      p.pop_back();
+      if (p.size())
+        compose_path(p, pdir);
+      else
+        pdir = file_path();
+      pd = cit.intern(pdir(), newfile);
+    }
+  while (newfile);
+  // found a parent that already exists
+  std::map<fpid, item_id>::const_iterator k = outmap.find(pd);
+  I(k != outmap.end());
+  item_id pi(k->second);
+  while (p.size() != parts.size())
+    {
+      p.push_back(idx(parts, p.size()));
+      compose_path(p, pdir);
+      boost::shared_ptr<item_status::item_data> ver;
+      ver.reset(new item_status::item_data());
+      items->push_back(ver);
+      revid r(itx->intern(revision));
+      item_status newitem(item_status(ver).rename(r, pi, p.back()));
+      newitem.is_dir = true;
+      states->insert(make_pair(items->size()-1,
+                               newitem));
+      pi = items->size() - 1;
+      pd = cit.intern(pdir());
+      outmap.insert(make_pair(pd, pi));
+    }
+}
+
+
 tree_state
-tree_state::merge(std::vector<tree_state> const & trees,
+tree_state::merge_with_rearrangement(std::vector<tree_state> const & trees,
                   std::vector<change_set::path_rearrangement> const & changes,
                   std::string revision)
 {
@@ -993,7 +1074,6 @@
   // deleted dirs, deleted files, renamed dirs, renamed files, added files
   // sort key is (depth, class, rev#)
   orderer todo;
-  typedef int fpid;
   std::map<fpid, item_id> outmap;// for tree poststate
   std::vector<std::map<fpid, item_id> > premaps;//for tree prestates
   std::vector<std::map<fpid, item_id> > postmaps;//for rearrangement poststates
@@ -1017,13 +1097,11 @@
     for (i = trees.begin(), x = changes.begin();
          i != trees.end() && x != changes.end(); ++i, ++x)
       {
-//      P(F("Next parent:"));
         premaps.push_back(std::map<fpid, item_id>());
         std::vector<std::pair<item_id, file_path> > curr = i->current();
         for (std::vector<std::pair<item_id, file_path> >::const_iterator
                j = curr.begin(); j != curr.end(); ++j)
           {
-//          P(F("%1%: %2%") % j->first % j->second);
             fpid myid = cit.intern(j->second());
             premaps.back().insert(make_pair(myid, j->first));
 
@@ -1044,13 +1122,16 @@
 
   for (orderer::const_iterator i = todo.begin(); i != todo.end(); ++i)
     {
-      file_path const & from(i->second.first);
-      file_path const & to(i->second.second);
-      int type(i->first.second.first);
-      int which(i->first.second.second);
-      item_status current_item;
+      file_path const & from(i->second.get<0>());
+      file_path const & to(i->second.get<1>());
+      bool is_dir(i->second.get<2>());
+      int type(i->first.get<1>());
+      int which(i->first.get<2>());
       item_id current_id;
       std::map<item_id, item_status>::iterator j = out.states->end();
+      bool addednew = false;
+
+      // find where it comes from...
       if (type == added_file || type == added_dir)
         {
           std::map<fpid, item_id>::const_iterator
@@ -1065,6 +1146,8 @@
               p = out.states->insert(make_pair(current_id, item_status(ver)));
               I(p.second);
               j = p.first;
+              addednew = true;
+//              P(F("New item: %1%") % current_id);
             }
           else
             {
@@ -1084,14 +1167,29 @@
           j = out.states->find(current_id);
         }
       I(j != out.states->end());
-      current_item = j->second;
+      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)
         {
-          j->second = item_status(current_item.rename(out.itx->intern(revision),
-                                                      item_id(-1),
-                                                      make_null_component()));
+          current_item = current_item.rename(out.itx->intern(revision),
+                                             item_id(-1),
+                                             make_null_component());
           continue;
         }
+      {
+        int d = -1;
+        std::set<item_status::item_state> s = current_item.current_names();
+        file_path orig;
+        if (s.size() == 1)
+          orig = out.try_get_full_name(*s.begin(), d);
+        if (!(addednew
+              || !(orig == file_path() && d != -1)
+              || to == file_path()))
+          W(F("undeleting %1%") % to);
+      }
       outmap.insert(make_pair(cit.intern(to()), current_id));
 
       file_path pdir;
@@ -1102,56 +1200,18 @@
         compose_path(parts, pdir);
       bool newfile;
       fpid pd = cit.intern(pdir(), newfile);
-
-      // make sure we know where to put it
       if (newfile)
-        {
-          // parent directory implied, did not previously exist
-          std::vector<path_component> p(parts);
-          do
-            {
-              p.pop_back();
-              if (p.size())
-                compose_path(p, pdir);
-              else
-                pdir = file_path();
-              pd = cit.intern(pdir(), newfile);
-            }
-          while (newfile);
-          // found a parent that already exists
-          std::map<fpid, item_id>::const_iterator k = outmap.find(pd);
-          I(k != outmap.end());
-          item_id pi(k->second);
-          while (p.size() != parts.size())
-            {
-              p.push_back(idx(parts, p.size()));
-              compose_path(p, pdir);
-              boost::shared_ptr<item_status::item_data> ver;
-              ver.reset(new item_status::item_data());
-              out.items->push_back(ver);
-              revid r(out.itx->intern(revision));
-              out.states->insert(make_pair(out.items->size()-1,
-                                 item_status(ver).rename(r,
-                                                         pi, p.back())));
-              pi = out.items->size() - 1;
-              pd = cit.intern(pdir());
-              outmap.insert(make_pair(pd, pi));
-            }
-        }
-      file_path recon;
-      split_path(pdir, parts);
-      parts.push_back(new_name);
-      compose_path(parts, recon);
-      I(recon == to);
+        out.ensure_dir_exists(parts, outmap, cit, revision);
 
       std::map<fpid, item_id>::const_iterator k = outmap.find(pd);
       I(k != outmap.end());
-      j->second = item_status(current_item.rename(out.itx->intern(revision),
-                                                  k->second,
-                                                  new_name));
-      std::set<item_status::item_state> n(j->second.current_names());
-      I(n.size() == 1);
-      recon = out.get_full_name(*n.begin());
+
+      // ...and get it moved in.
+      current_item = current_item.rename(out.itx->intern(revision),
+                                         k->second,
+                                         new_name);
+      current_item.is_dir = is_dir;
+      file_path recon = out.get_full_name(current_item);
       I(recon == to);
     }
   return out;
@@ -1185,9 +1245,9 @@
         newstate.states->insert(make_pair(r->first,r->second.copy())), ++r;
       else if (r == other.states->end())
         newstate.states->insert(make_pair(l->first,l->second.copy())), ++l;
-      else if (l->first < r->first)
+      else if (l->first > r->first)
         newstate.states->insert(make_pair(r->first,r->second.copy())), ++r;
-      else if (r->first < l->first)
+      else if (r->first > l->first)
         newstate.states->insert(make_pair(l->first,l->second.copy())), ++l;
       else
         {
@@ -1234,6 +1294,8 @@
       for (std::set<item_status::item_state>::const_iterator
              j = s.begin(); j != s.end(); ++j)
         {
+          if (*j == make_pair(item_id(-1), make_null_component()))
+            continue;
           std::map<item_status::item_state, std::set<item_id> >::iterator
             k = m.find(*j);
           if (k == m.end())
@@ -1263,15 +1325,23 @@
           std::map<item_id, item_status>::const_iterator
             l(states->find(*j)),
             r(other.states->find(*j));
-          I(l != states->end());
-          I(r != other.states->end());
-          std::set<item_status::item_state>
-            left(l->second.current_names()),
-            right(r->second.current_names());
-          I(left.size() == 1);
-          I(right.size() == 1);
-          c.lnames.push_back(get_full_name(*left.begin()));
-          c.rnames.push_back(other.get_full_name(*right.begin()));
+          std::set<item_status::item_state> left, right;
+          if (l != states->end())
+            {
+              left = l->second.current_names();
+              I(left.size() == 1);
+              c.lnames.push_back(get_full_name(*left.begin()));
+            }
+          else
+            c.lnames.push_back(file_path());
+          if (r != other.states->end())
+            {
+              right = r->second.current_names();
+              I(right.size() == 1);
+              c.rnames.push_back(other.get_full_name(*right.begin()));
+            }
+          else
+            c.rnames.push_back(file_path());
         }
       out.push_back(c);
     }
@@ -1293,18 +1363,204 @@
 }
 
 void
-tree_state::get_changes_for_merge(tree_state const & other,
-                               std::set<path_conflict::resolution> const & res,
+tree_state::get_changes_for_merge(tree_state const & merged,
                                   change_set::path_rearrangement & changes)
+                                  const
 {
+  changes.deleted_dirs.clear();
+  changes.deleted_files.clear();
+  changes.renamed_dirs.clear();
+  changes.renamed_files.clear();
+  //
+  changes.added_files.clear();
+
+  map<item_id, item_status>::const_iterator l, r;
+  l = states->begin();
+  r = merged.states->begin();
+  while (l != states->end() || r != merged.states->end())
+    {
+      file_path from, to;
+      bool from_is_dir(false), to_is_dir(false);
+
+      if (l == states->end())
+        {
+          to = merged.get_full_name(r->second);
+          to_is_dir = r->second.is_dir;
+          ++r;
+        }
+      else if (r == merged.states->end())
+        {
+          from = get_full_name(l->second);
+          from_is_dir = l->second.is_dir;
+          ++l;
+        }
+      else if (l->first > r->first)
+        {
+          to = merged.get_full_name(r->second);
+          to_is_dir = r->second.is_dir;
+          ++r;
+        }
+      else if (r->first > l->first)
+        {
+          from = get_full_name(l->second);
+          from_is_dir = l->second.is_dir;
+          ++l;
+        }
+      else
+        {
+          from = get_full_name(l->second);
+          from_is_dir = l->second.is_dir;
+          to = merged.get_full_name(r->second);
+          to_is_dir = r->second.is_dir;
+          ++l, ++r;
+        }
+
+      if (to == from)
+        continue;
+      else if (to == file_path())
+        {
+          if (from_is_dir)
+            changes.deleted_dirs.insert(from);
+          else
+            changes.deleted_files.insert(from);
+        }
+      else if (from == file_path())
+        {
+          if (to_is_dir)
+            ;
+          else
+            changes.added_files.insert(to);
+        }
+      else
+        {
+          if (from_is_dir)
+            changes.renamed_dirs.insert(make_pair(from, to));
+          else
+            changes.renamed_files.insert(make_pair(from, to));
+        }
+    }
 }
 
+tree_state
+tree_state::merge_with_resolution(std::vector<tree_state> const & revs,
+                               std::set<path_conflict::resolution> const & res,
+                                  std::string const & revision)
+{
+  tree_state merged(mash(revs));
+
+  std::set<item_id> resolved;
+  typedef std::vector<path_component> splitpath;
+
+  // we need the names of close-to-root items
+  // before we can resolve their children
+  std::multimap<int, std::pair<item_id, splitpath > > sorted;
+  for (std::set<path_conflict::resolution>::const_iterator i = res.begin();
+       i != res.end(); ++i)
+    {
+      file_path fp(i->second);
+      splitpath sp;
+      split_path(fp, sp);
+      sorted.insert(make_pair(sp.size(), make_pair(i->first, sp)));
+    }
+  typedef int fpid;
+  interner<fpid> cit;
+  map<fpid, item_id> names;
+  int lastlevel = 0;
+  for (std::multimap<int, std::pair<item_id, splitpath > >::const_iterator
+         i = sorted.begin(); i != sorted.end(); ++i)
+    {
+      if (i->first > lastlevel)
+        {
+          // names should contain everything closer to root
+          // than the level we're at now
+          for (std::map<item_id, item_status>::const_iterator
+                 j = merged.states->begin(); j != merged.states->end(); ++j)
+            {
+              if (resolved.find(j->first) == resolved.end())
+                {
+                  std::set<item_status::item_state>
+                    x(j->second.current_names());
+                  if (x.size() != 1)
+                    continue;// not resolved, so not closer
+                  int d;
+                  file_path fp(merged.try_get_full_name(*x.begin(), d));
+                  if (d >= lastlevel || d == -1)
+                    continue;// not reached, or not resolved
+                  resolved.insert(j->first);
+                  fpid f(cit.intern(fp()));
+                  names.insert(make_pair(f, j->first));
+                }
+            }
+          ++lastlevel;
+        }
+      item_id const & id(i->second.first);
+      splitpath sp(i->second.second);
+      unsigned int s = resolved.size();
+      resolved.insert(id);
+      std::map<item_id, item_status>::const_iterator
+        j = merged.states->find(id);
+      I(j != merged.states->end());
+      item_status it = j->second;
+      if (s == resolved.size())
+        {
+          // already resolved this item, this resolution had better match
+          std::set<item_status::item_state> names = it.current_names();
+          I(names.size() == 1);
+          file_path prev = merged.get_full_name(*names.begin());
+          file_path to;
+          compose_path(sp, to);
+          I(to == prev);
+        }
+       else
+        {
+          file_path fp;
+          compose_path(sp, fp);
+          path_component name(sp.back());
+          sp.pop_back();
+          file_path pdir;
+          if (sp.size())
+            compose_path(sp, pdir);
+          bool newfile;
+          fpid pd = cit.intern(pdir(), newfile);
+          if (newfile)
+            merged.ensure_dir_exists(sp, names, cit, revision);
+          std::map<fpid, item_id>::const_iterator k = names.find(pd);
+          I(k != names.end());
+
+          std::map<item_id, item_status>::iterator
+            j = merged.states->find(k->second);
+          I(j != merged.states->end());
+          j->second = item_status(j->second.rename(merged.itx->intern(revision),
+                                                   k->second, name));
+          cit.intern(fp());
+        }
+    }
+  return merged;
+}
+
 file_path
+tree_state::get_full_name(item_status x) const
+{
+  std::set<item_status::item_state> y;
+  y = x.current_names();
+  I(y.size() == 1);
+  return get_full_name(*y.begin());
+}
+
+file_path
 tree_state::get_full_name(item_status::item_state x) const
 {
-// fails if the item has multiple names (only call this on clean trees)
+  int d;
+  file_path out(try_get_full_name(x, d));
+  I(d != -1);
+  return out;
+}
+
+file_path
+tree_state::try_get_full_name(item_status::item_state x, int & d) const
+{
+  d = 0;
   std::vector<path_component> names;
-  file_path out;
   names.push_back(x.second);
   while (x.first != -1)
     {
@@ -1312,11 +1568,16 @@
         i = states->find(x.first);
       I(i != states->end());
       std::set<item_status::item_state> y = i->second.current_names();
-      I(y.size() == 1);
+      if (y.size() != 1)
+        {
+          d = -1;
+          return file_path();
+        }
       x = *y.begin();
       names.push_back(x.second);
     }
   reverse(names.begin(), names.end());
+  file_path out;
   compose_path(names, out);
   return out;
 }
@@ -1329,11 +1590,12 @@
   file_path fp;
   std::string out;
   names.push_back(x.second);
-  do
+  while (x.first != -1)
     {
       std::map<item_id, item_status>::const_iterator
         i = states->find(x.first);
-      I(i != states->end());
+      if (i != states->end());
+      else E(false, F("Missing: %1%") % x.first);
       std::set<item_status::item_state> y = i->second.current_names();
       if (y.size() != 1)
         {
@@ -1343,7 +1605,6 @@
       x = *y.begin();
       names.push_back(x.second);
     }
-  while (x.first != -1);
   reverse(names.begin(), names.end());
   compose_path(names, fp);
   out += fp();
========================================================================
--- pcdv.hh	42bf317c405625ccb402ce51c6ec96b65c187907
+++ pcdv.hh	6dc79305b5e65ce553a85b79f998f0c7da205f2d
@@ -188,10 +188,7 @@
   std::vector<file_path> lnames;
   std::vector<file_path> rnames;
   std::string name;
-  struct resolution
-  {
-    std::vector<std::pair<item_id, std::string> > res;
-  };
+  typedef std::pair<item_id, std::string> resolution;
 };
 
 struct item_status
@@ -201,7 +198,8 @@
   // shared for all versions of this item
   boost::shared_ptr<item_data> versions;
   // shared between all copies of this version of this item
-  boost::shared_ptr<std::vector<revid> > leaves;
+  boost::shared_ptr<std::vector<revid> const > leaves;
+  bool is_dir;
 
   item_status();
   item_status(boost::shared_ptr<item_data> ver);
@@ -225,6 +223,7 @@
   copy() const;
 };
 
+
 // This is a const object type; there are no modifiers.
 // Usage:
 //   for a->b
@@ -241,6 +240,7 @@
 //     x.get_changes_from(b)
 class tree_state
 {
+  typedef int fpid;
   boost::shared_ptr<vector<boost::shared_ptr<item_status::item_data> > > items;
   boost::shared_ptr<std::map<item_id, item_status> > states;
   boost::shared_ptr<interner<revid> > itx;
@@ -257,7 +257,7 @@
   new_tree() {return tree_state();}
 
   static tree_state
-  merge(std::vector<tree_state> const & trees,
+  merge_with_rearrangement(std::vector<tree_state> const & trees,
         std::vector<change_set::path_rearrangement> const & changes,
         std::string revision);
 
@@ -271,15 +271,26 @@
   std::vector<std::pair<item_id, file_path> >
   current() const;
 
-  // get the changes along edge this->merged for merged=merge(this, other)
+  // get the changes along edge this->merged for merged=merge(revs)
+  // note that revs should include *this
   void
-  get_changes_for_merge(tree_state const & other,
+  get_changes_for_merge(tree_state const & merged,
+                        change_set::path_rearrangement & changes) const;
+
+  static tree_state
+  merge_with_resolution(std::vector<tree_state> const & revs,
                         std::set<path_conflict::resolution> const & res,
-                        change_set::path_rearrangement & changes);
+                        std::string const & revision);
 private:
   file_path
   get_full_name(item_status::item_state x) const;
 
+  file_path
+  get_full_name(item_status x) const;
+
+  file_path
+  try_get_full_name(item_status::item_state x, int & d) const;
+
   std::string
   get_ambiguous_full_name(item_status::item_state x) const;
 
@@ -288,6 +299,12 @@
 
   static tree_state
   mash(std::vector<tree_state> const & trees);
+
+  void
+  ensure_dir_exists(std::vector<path_component> const & parts,
+                    std::map<fpid, item_id> & outmap,
+                    interner<fpid> & cit,
+                    std::string const & revision);
 };
 
 void