# 
# patch "ChangeLog"
#  from [3b086fd325fc76dd74d1c9d07add50380ff1b09c]
#    to [b057c2543646fc3da2fa4a0f6ad90194f3b52a94]
# 
# patch "commands.cc"
#  from [de80ee6b0dbe35414038363b3bbf5c184da3801f]
#    to [c37e80febb5d27822b14f8fb0ebb0a509e5efb79]
# 
# patch "pcdv.cc"
#  from [3013fda6802159117186282ee281185ae301b64a]
#    to [ec5439e5a58d5895d73ce163d6c8ac96ce7d908e]
# 
# patch "pcdv.hh"
#  from [30c19d348e8315aa42fec1f521ea514c45da2839]
#    to [42bf317c405625ccb402ce51c6ec96b65c187907]
# 
===============================================
--- ChangeLog	3b086fd325fc76dd74d1c9d07add50380ff1b09c
+++ ChangeLog	b057c2543646fc3da2fa4a0f6ad90194f3b52a94
@@ -1,3 +1,9 @@
+2005-08-02  Timothy Brownawell  <address@hidden>
+
+	* pcdv.{cc,hh}: Add history-aware filetree merge.
+		TODO: write get_changes_for_merge, add tests.
+	* commands.cc: Call it from the pcdv driver.
+
 2005-07-29  Timothy Brownawell  <address@hidden>
 
 	* commands.cc (pcdv): Try to make pcdv driver more efficient.
===============================================
--- commands.cc	de80ee6b0dbe35414038363b3bbf5c184da3801f
+++ commands.cc	c37e80febb5d27822b14f8fb0ebb0a509e5efb79
@@ -52,6 +52,8 @@
 #include "options.hh"
 #include "globish.hh"
 
+#include "pcdv.hh"
+
 //
 // this file defines the task-oriented "top level" commands which can be
 // issued as part of a monotone command line. the command line can only
@@ -3907,6 +3909,9 @@
            i != rs.edges.end(); ++i)
         {
           revision_id oldrev(edge_old_revision(i));
+          if (!(oldrev == revision_id()))
+            ++child_count;
+
           {
             std::pair<int, vector<revision_id> > p(1, vector<revision_id>());
             p.second.push_back(oldrev);
@@ -3933,23 +3938,27 @@
           if (fileids.find(oldrev) != fileids.end())
             continue;
           // this is the beginning of time
-          if (edge_changes(i).rearrangement.has_added_file(p))
-            continue;
+//          if (edge_changes(i).rearrangement.has_added_file(p))
+//            continue;
           std::map<file_path, file_path> const &
               renames(edge_changes(i).rearrangement.renamed_files);
           std::map<file_path, file_path>::const_iterator j = renames.begin();
           while (j != renames.end() && !(j->second == p))
             ++j;
           file_path const & mfp((j == renames.end())?fp:j->first);
-          
-          manifest_map m;
-          app.db.get_manifest(edge_old_manifest(i), m);
-          manifest_map::const_iterator mi = m.find(mfp);
-          I(mi != m.end());
-          file_id ident = manifest_entry_id(mi);
-          fileids.insert(make_pair(oldrev, make_pair(ident, mfp)));
-          todo.push_back(make_pair(oldrev, mfp));
-          ++child_count;
+          if (!(mfp == file_path()
+              || edge_changes(i).rearrangement.has_added_file(p)))
+          {
+            manifest_map m;
+            app.db.get_manifest(edge_old_manifest(i), m);
+            manifest_map::const_iterator mi = m.find(mfp);
+            I(mi != m.end());
+            file_id ident = manifest_entry_id(mi);
+            fileids.insert(make_pair(oldrev, make_pair(ident, mfp)));
+            todo.push_back(make_pair(oldrev, mfp));
+          }
+          else if (!(oldrev == revision_id()))
+            todo.push_back(make_pair(oldrev, file_path()));
         }
       if (!child_count)
         roots.push_back(todo.front().first);
@@ -3985,19 +3994,48 @@
   std::deque<revision_id> roots;
   for (vector<revision_id>::const_iterator i = rootvect.begin();
        i != rootvect.end(); ++i)
-    roots.push_back(*i);
+    {
+      roots.push_back(*i);
+      P(F("Roots: %1%") % *i);
+    }
 
   ticker count("Revs in weave", "R", 1);
   ticker lines("Lines in weave", "L", 1);
   ticker unique("Unique lines", "U", 1);
 
   map<revision_id, file_state> files;
-  file_state empty;
+  file_state empty(file_state::new_file());
   file_state p(empty);
+  std::map<revision_id, tree_state> trees;
+  tree_state emptytree(tree_state::new_tree());
   bool found_right = false;
   bool found_left = false;
   while (!roots.empty() && !(found_right && found_left))
     {
+      revision_set rs;
+      app.db.get_revision(roots.front(), rs);
+      std::vector<tree_state> treevec;
+      std::vector<change_set::path_rearrangement> revec;
+      for (edge_map::const_iterator i = rs.edges.begin();
+           i != rs.edges.end(); ++i)
+        {
+          tree_state from(emptytree);
+          if (edge_old_revision(i) == revision_id())
+            from = emptytree;
+          else
+            {
+              std::map<revision_id, tree_state>::iterator
+                j = trees.find(edge_old_revision(i));
+              I(j != trees.end());
+              from = j->second;
+            }
+          treevec.push_back(from);
+          revec.push_back(edge_changes(i).rearrangement);
+        }
+      tree_state newtree(tree_state::merge(treevec, revec,
+                                           roots.front().inner()()));
+      trees.insert(make_pair(roots.front(), newtree));
+
       std::map<revision_id, std::pair<file_id, file_path> >::const_iterator
           i(fileids.find(roots.front()));
       if (i != fileids.end())
@@ -4046,7 +4084,10 @@
               if (--children[*i].first == 0
                   && left.inner()() != i->inner()()
                   && right.inner()() != i->inner()())
-                files.erase(*i);
+                {
+                  files.erase(*i);
+                  trees.erase(*i);
+                }
             }
         }
 
@@ -4070,6 +4111,14 @@
   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	3013fda6802159117186282ee281185ae301b64a
+++ pcdv.cc	ec5439e5a58d5895d73ce163d6c8ac96ce7d908e
@@ -7,6 +7,13 @@
 
 #include <iostream>
 
+/////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////
+//////////////// History-aware file merge (pcdv) ////////////////////
+/////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////
+
+
 // This stuff is to provide data for size optimization.
 unsigned int biggest_living_status=0;
 unsigned int sum_living_status=0;
@@ -244,6 +251,14 @@
   return *this;
 }
 
+living_status
+living_status::copy() const
+{
+  living_status out(*this);
+  out.leaves.reset(new std::vector<revid>(*leaves));
+  return out;
+}
+
 living_status const
 living_status::new_version(vector<revid> const & _leaves) const
 {
@@ -323,12 +338,16 @@
     todo.push_back(*i);
   while (todo.size())
     {
+      unsigned int s = ref.size();
       ref.insert(todo.front());
-      line_data::const_iterator i = overrides->find(todo.front());
-      I(i != overrides->end());
-      for (vector<revid>::const_iterator j = i->second.begin();
-           j != i->second.end(); ++j)
-        todo.push_back(*j);
+      if (s != ref.size())
+        {
+          line_data::const_iterator i = overrides->find(todo.front());
+          I(i != overrides->end());
+          for (vector<revid>::const_iterator j = i->second.begin();
+               j != i->second.end(); ++j)
+            todo.push_back(*j);
+        }
       todo.pop_front();
     }
   newworking = ref;
@@ -475,13 +494,13 @@
   while (l != states->end() || r != other.states->end())
     {
       if (l == states->end())
-        newstate.states->insert(*(r++));
+        newstate.states->insert(make_pair(r->first,r->second.copy())), ++r;
       else if (r == other.states->end())
-        newstate.states->insert(*(l++));
+        newstate.states->insert(make_pair(l->first,l->second.copy())), ++l;
       else if (l->first < r->first)
-        newstate.states->insert(*(r++));
+        newstate.states->insert(make_pair(r->first,r->second.copy())), ++r;
       else if (r->first < l->first)
-        newstate.states->insert(*(l++));
+        newstate.states->insert(make_pair(l->first,l->second.copy())), ++l;
       else
         {
           newstate.states->insert(make_pair(l->first,
@@ -743,12 +762,605 @@
   return out;
 }
 
+/////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////
+////////////////// History-aware directory merge ////////////////////
+/////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////
 
-/////////////////////////////////////////////////////////////////
-///////////////////////// Tests /////////////////////////////////
-/////////////////////////////////////////////////////////////////
+item_status::item_status():
+             versions(new item_data()),
+             leaves(new vector<revid>())
+{
+  versions->insert(make_pair(revid(-1),
+                             make_pair(make_pair(item_id(-1),
+                                                 make_null_component()),
+                                       vector<revid>())));
+  leaves->push_back(revid(-1));
+}
 
+item_status::item_status(boost::shared_ptr<item_data> ver):
+             versions(ver),
+             leaves(new vector<revid>())
+{
+  leaves->push_back(revid(-1));
+  versions->insert(make_pair(revid(-1),
+                             make_pair(make_pair(item_id(-1),
+                                                 make_null_component()),
+                                       vector<revid>())));
+}
 
+item_status::item_status(item_status const & x):
+               versions(x.versions),
+               leaves(x.leaves)
+{}
+
+item_status::~item_status()
+{}
+
+item_status
+item_status::copy() const
+{
+  item_status out(*this);
+  out.leaves.reset(new std::vector<revid>(*leaves));
+  return out;
+}
+
+item_status const
+item_status::new_version(vector<revid> const & _leaves) const
+{
+  I(leaves->size());
+  item_status out(*this);
+  out.leaves.reset(new vector<revid>(_leaves));
+  return out;
+}
+
+item_status
+item_status::merge(item_status const & other) const
+{
+  I(versions == other.versions);
+  set<revid> leafset, done;
+  std::deque<revid> todo;
+  for (vector<revid>::const_iterator i = leaves->begin();
+       i != leaves->end(); ++i)
+    leafset.insert(*i);
+  for (vector<revid>::const_iterator i = other.leaves->begin();
+       i != other.leaves->end(); ++i)
+    leafset.insert(*i);
+  for (set<revid>::const_iterator i = leafset.begin();
+       i != leafset.end(); ++i)
+    todo.push_back(*i);
+  while (todo.size())
+    {
+      item_data::const_iterator i = versions->find(todo.front());
+      I(i != versions->end());
+      for (vector<revid>::const_iterator j = i->second.second.begin();
+           j != i->second.second.end(); ++j)
+        {
+          if (done.find(*j) != done.end())
+            continue;
+          set<revid>::iterator l = leafset.find(*j);
+          if (l != leafset.end())
+            {
+              leafset.erase(l);
+              continue;
+            }
+          done.insert(*j);
+          todo.push_back(*j);
+        }
+      todo.pop_front();
+    }
+  I(leafset.size());
+
+  vector<revid> newleaves;
+  newleaves.reserve(leafset.size());
+  for (set<revid>::const_iterator i = leafset.begin();
+       i != leafset.end(); ++i)
+    newleaves.push_back(*i);
+  if (newleaves == *leaves)
+    return *this;
+  if (newleaves == *other.leaves)
+    return other;
+  return new_version(newleaves);
+}
+
+std::set<item_status::item_state>
+item_status::current_names() const
+{
+  I(leaves->size());
+  std::set<item_state> out;
+  for (vector<revid>::const_iterator i = leaves->begin();
+       i != leaves->end(); ++i)
+    {
+      item_data::const_iterator j = versions->find(*i);
+      I(j != versions->end());
+      out.insert(j->second.first);
+    }
+  return out;
+}
+
+item_status
+item_status::rename(revid rev, item_id new_parent, path_component new_name) const
+{
+  item_state newstate(make_pair(new_parent, new_name));
+  vector<revid> newleaves, badleaves;
+  for (vector<revid>::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
+        badleaves.push_back(*i);
+    }
+  if (badleaves.empty())
+    return *this;
+
+  newleaves.push_back(rev);
+  versions->insert(make_pair(rev, make_pair(newstate, badleaves)));
+  return new_version(newleaves);
+}
+
+
+
+tree_state::tree_state(boost::shared_ptr<vector<boost::shared_ptr<
+                                            item_status::item_data> > > _items,
+                       boost::shared_ptr<interner<revid> > _itx):
+            items(_items),
+            states(new std::map<item_id, item_status>()),
+            itx(_itx)
+{}
+
+tree_state::tree_state():
+            items(new vector<boost::shared_ptr<item_status::item_data> >()),
+            states(new std::map<item_id, item_status>()),
+            itx(new interner<revid>())
+{}
+
+tree_state::~tree_state()
+{}
+
+const int deleted_dir(1);
+const int deleted_file(2);
+const int renamed_dir(3);
+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;
+
+void
+process_rearrangement(change_set::path_rearrangement const & changes,
+                      orderer & todo, int num)
+{
+  for (std::set<file_path>::const_iterator i = changes.deleted_dirs.begin();
+       i != changes.deleted_dirs.end(); ++i)
+    {
+      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())));
+    }
+  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())));
+    }
+  for (std::map<file_path, file_path>::const_iterator
+         i = changes.renamed_dirs.begin();
+       i != changes.renamed_dirs.end(); ++i)
+    {
+      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)));
+    }
+  for (std::map<file_path, file_path>::const_iterator
+         i = changes.renamed_files.begin();
+       i != changes.renamed_files.end(); ++i)
+    {
+      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)));
+    }
+  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)));
+    }
+
+}
+
+tree_state
+tree_state::merge(std::vector<tree_state> const & trees,
+                  std::vector<change_set::path_rearrangement> const & changes,
+                  std::string revision)
+{
+  // shortest first, then in order of:
+  // 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
+  {
+    int n;
+    std::vector<change_set::path_rearrangement>::const_iterator i;
+    for (i = changes.begin(), n = 0; i != changes.end(); ++i, ++n)
+      {
+        process_rearrangement(*i, todo, n);
+      }
+  }
+  interner<fpid> cit;
+  tree_state out(mash(trees));
+  fpid rootid = cit.intern(file_path()());
+  outmap.insert(make_pair(rootid, -1));
+
+  // populate outmap with any unchanged entries
+  {
+    std::vector<change_set::path_rearrangement>::const_iterator x;
+    std::vector<tree_state>::const_iterator i;
+    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));
+
+            // does it stay put?
+            bool deldir = (x->deleted_dirs.find(j->second)
+                           != x->deleted_dirs.end());
+            bool delfile = (x->deleted_files.find(j->second)
+                            != x->deleted_files.end());
+            bool mvdir = (x->renamed_dirs.find(j->second)
+                          != x->renamed_dirs.end());
+            bool mvfile = (x->renamed_files.find(j->second)
+                           != x->renamed_files.end());
+            if (!deldir && !delfile && !mvdir && !mvfile)
+              outmap.insert(make_pair(myid, j->first));
+          }
+      }
+  }
+
+  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;
+      item_id current_id;
+      std::map<item_id, item_status>::iterator j = out.states->end();
+      if (type == added_file || type == added_dir)
+        {
+          std::map<fpid, item_id>::const_iterator
+            k = outmap.find(cit.intern(to()));
+          if (k == outmap.end())
+            {
+              boost::shared_ptr<item_status::item_data> ver;
+              ver.reset(new item_status::item_data());
+              out.items->push_back(ver);
+              current_id = out.items->size() - 1;
+              std::pair<std::map<item_id, item_status>::iterator, bool> p;
+              p = out.states->insert(make_pair(current_id, item_status(ver)));
+              I(p.second);
+              j = p.first;
+            }
+          else
+            {
+              current_id = k->second;
+              j = out.states->find(current_id);
+            }
+        }
+      else
+        {
+          bool newfile;
+          fpid f = cit.intern(from(), newfile);
+          I(!newfile);
+          std::map<fpid, item_id>::const_iterator
+            k = idx(premaps, which).find(f);
+          I(k != idx(premaps, which).end());
+          current_id = k->second;
+          j = out.states->find(current_id);
+        }
+      I(j != out.states->end());
+      current_item = j->second;
+      if (type == deleted_file || type == deleted_dir)
+        {
+          j->second = item_status(current_item.rename(out.itx->intern(revision),
+                                                      item_id(-1),
+                                                      make_null_component()));
+          continue;
+        }
+      outmap.insert(make_pair(cit.intern(to()), current_id));
+
+      file_path pdir;
+      std::vector<path_component> parts;
+      path_component new_name;
+      split_path(to, parts, new_name);
+      if (parts.size())
+        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);
+
+      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());
+      I(recon == to);
+    }
+  return out;
+}
+
+tree_state
+tree_state::mash(std::vector<tree_state> const & trees)
+{
+  I(!trees.empty());
+  tree_state out(idx(trees, 0));
+  for (std::vector<tree_state>::const_iterator i = ++trees.begin();
+       i != trees.end(); ++i)
+    out = out.mash(*i);
+  if (trees.size() == 1)
+    out.states.reset(new map<item_id, item_status>(*out.states));
+  I(out.states != idx(trees, 0).states);
+  return out;
+}
+
+tree_state
+tree_state::mash(tree_state const & other) const
+{
+  I(items == other.items);
+  tree_state newstate(items, itx);
+  map<item_id, item_status>::const_iterator l, r;
+  l = states->begin();
+  r = other.states->begin();
+  while (l != states->end() || r != other.states->end())
+    {
+      if (l == states->end())
+        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)
+        newstate.states->insert(make_pair(r->first,r->second.copy())), ++r;
+      else if (r->first < l->first)
+        newstate.states->insert(make_pair(l->first,l->second.copy())), ++l;
+      else
+        {
+          newstate.states->insert(make_pair(l->first,
+                                            l->second.merge(r->second)));
+          ++l, ++r;
+        }
+    }
+  return newstate;
+}
+
+std::vector<path_conflict>
+tree_state::conflict(tree_state const & other) const
+{
+  tree_state merged(mash(other));
+  std::vector<path_conflict> out;
+  std::map<item_status::item_state, std::set<item_id> > m;
+
+  // splits, merge(mv a b, mv a c)
+  for (std::map<item_id, item_status>::const_iterator
+         i = merged.states->begin();
+       i != merged.states->end(); ++i)
+    {
+      std::set<item_status::item_state> s = i->second.current_names();
+      if (s.size() != 1)
+        {
+          path_conflict c;
+          c.type = path_conflict::split;
+          c.items.push_back(i->first);
+          std::map<item_id, item_status>::const_iterator
+            j(states->find(i->first)),
+            k(other.states->find(i->first));
+          I(j != states->end());
+          I(k != other.states->end());
+          std::set<item_status::item_state>
+            left(j->second.current_names()),
+            right(k->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()));
+          out.push_back(c);
+        }
+      for (std::set<item_status::item_state>::const_iterator
+             j = s.begin(); j != s.end(); ++j)
+        {
+          std::map<item_status::item_state, std::set<item_id> >::iterator
+            k = m.find(*j);
+          if (k == m.end())
+            {
+              std::set<item_id> ns;
+              ns.insert(i->first);
+              m.insert(make_pair(*j, ns));
+            }
+          else
+            k->second.insert(i->first);
+        }
+    }
+
+  // collisions, merge(mv a c, mv b c)
+  for (std::map<item_status::item_state, std::set<item_id> >::const_iterator
+         i = m.begin(); i != m.end(); ++i)
+    {
+      if (i->second.size() == 1)
+        continue;
+      path_conflict c;
+      c.type = path_conflict::collision;
+      c.name = merged.get_ambiguous_full_name(i->first);
+      for (std::set<item_id>::const_iterator j = i->second.begin();
+           j != i->second.end(); ++j)
+        {
+          c.items.push_back(*j);
+          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()));
+        }
+      out.push_back(c);
+    }
+  return out;
+}
+
+std::vector<std::pair<item_id, file_path> >
+tree_state::current() const
+{
+  std::vector<std::pair<item_id, file_path> > out;
+  for (std::map<item_id, item_status>::const_iterator i = states->begin();
+       i != states->end(); ++i)
+    {
+      std::set<item_status::item_state> s = i->second.current_names();
+      I(s.size() == 1);
+      out.push_back(make_pair(i->first, get_full_name(*s.begin())));
+    }
+  return out;
+}
+
+void
+tree_state::get_changes_for_merge(tree_state const & other,
+                               std::set<path_conflict::resolution> const & res,
+                                  change_set::path_rearrangement & changes)
+{
+}
+
+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)
+  std::vector<path_component> names;
+  file_path out;
+  names.push_back(x.second);
+  while (x.first != -1)
+    {
+      std::map<item_id, item_status>::const_iterator
+        i = states->find(x.first);
+      I(i != states->end());
+      std::set<item_status::item_state> y = i->second.current_names();
+      I(y.size() == 1);
+      x = *y.begin();
+      names.push_back(x.second);
+    }
+  reverse(names.begin(), names.end());
+  compose_path(names, out);
+  return out;
+}
+
+std::string
+tree_state::get_ambiguous_full_name(item_status::item_state x) const
+{
+// fails if the item has multiple names (only call this on clean trees)
+  std::vector<path_component> names;
+  file_path fp;
+  std::string out;
+  names.push_back(x.second);
+  do
+    {
+      std::map<item_id, item_status>::const_iterator
+        i = states->find(x.first);
+      I(i != states->end());
+      std::set<item_status::item_state> y = i->second.current_names();
+      if (y.size() != 1)
+        {
+          out = (F("<id:%1%>/") % x.first).str();
+          break;
+        }
+      x = *y.begin();
+      names.push_back(x.second);
+    }
+  while (x.first != -1);
+  reverse(names.begin(), names.end());
+  compose_path(names, fp);
+  out += fp();
+  return out;
+}
+
+
+
+
+
+/////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////
+/////////////////////////// Tests ///////////////////////////////////
+/////////////////////////////////////////////////////////////////////
+/////////////////////////////////////////////////////////////////////
+
+
 vector<string>
 vectorize(string x)
 {
@@ -959,3 +1571,9 @@
   test_living_status();
   test_file_state();
 }
+
+
+void
+dirmerge_test()
+{
+}
===============================================
--- pcdv.hh	30c19d348e8315aa42fec1f521ea514c45da2839
+++ pcdv.hh	42bf317c405625ccb402ce51c6ec96b65c187907
@@ -10,6 +10,8 @@
 #include <boost/scoped_ptr.hpp>
 
 #include "interner.hh"
+#include "change_set.hh"
+#include "path_component.hh"
 
 using std::vector;
 using std::string;
@@ -18,6 +20,7 @@
 using std::make_pair;
 using std::set;
 
+// pcdv (history-aware merge) for files (line state is {alive, dead} binary)
 
 struct merge_section
 {
@@ -74,6 +77,9 @@
 
   ~living_status();
 
+  living_status
+  copy() const;
+
   living_status const
   new_version(vector<revid> const & _leaves) const;
 
@@ -116,6 +122,8 @@
   weave_line(line_contents const & l, revid const & v, int n);
 };
 
+void test_file_state();//for friend decl.
+
 //a.mash(b).resolve(c) -> "a and b were merged, with result c"
 //a.mash(b).conflict() -> "merge a and b"
 //a.resolve(b) -> "b is a child of a"
@@ -128,17 +136,22 @@
                               interner<revid> > > itx;
   boost::shared_ptr<map<line_id, living_status> > states;
 
+private:
+  file_state();
   file_state(boost::shared_ptr<vector<weave_line> > _weave,
              boost::shared_ptr<std::pair<interner<line_contents>,
                                          interner<revid> > > _itx);
-  file_state();
   file_state(vector<string> const & initial, string rev,
              boost::shared_ptr<vector<weave_line> > _weave,
              boost::shared_ptr<std::pair<interner<line_contents>,
                                          interner<revid> > > _itx);
+public:
 
   ~file_state();
 
+  static file_state
+  new_file() {return file_state();}
+
   // combine line states between two versions of a file
   file_state
   mash(file_state const & other) const;
@@ -154,9 +167,130 @@
   // add a descendent of this version to the weave, and return it
   file_state
   resolve(vector<string> const & result, string revision) const;
+
+  friend void test_file_state();
 };
 
 void
 pcdv_test();
 
+
+// history-aware directory merge (line state is a (parent+string))
+// multiple lines (files/directories) cannot have the same state (filename)
+
+typedef int item_id;
+
+struct path_conflict
+{
+  enum what {split, collision};
+  what type;
+  std::vector<item_id> items;
+  std::vector<file_path> lnames;
+  std::vector<file_path> rnames;
+  std::string name;
+  struct resolution
+  {
+    std::vector<std::pair<item_id, std::string> > res;
+  };
+};
+
+struct item_status
+{
+  typedef std::pair<item_id, path_component> item_state;
+  typedef std::map<revid, std::pair<item_state, vector<revid> > > item_data;
+  // 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;
+
+  item_status();
+  item_status(boost::shared_ptr<item_data> ver);
+  item_status(item_status const & x);
+
+  ~item_status();
+
+  item_status const
+  new_version(vector<revid> const & _leaves) const;
+
+  item_status
+  merge(item_status const & other) const;
+
+  std::set<item_state>
+  current_names() const;
+
+  item_status
+  rename(revid rev, item_id new_parent, path_component new_name) const;
+
+  item_status
+  copy() const;
+};
+
+// This is a const object type; there are no modifiers.
+// Usage:
+//   for a->b
+//     a.rearrange(<changes>, 'b')
+//   for (a, b)->c (merge in history)
+//     x = a.rearrange(<changes>, 'c')
+//     y = b.rearrange(<changes>, 'c')
+//     x.mash(y)
+//   for merge(a, b)
+//     x = a.mash(b)
+//     <conflict> = x.get_conflicts()
+//     x.resolve(<conflict_resolution>)
+//     x.get_changes_from(a)
+//     x.get_changes_from(b)
+class tree_state
+{
+  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;
+
+  tree_state(boost::shared_ptr<vector<boost::shared_ptr<
+                                        item_status::item_data> > > _items,
+             boost::shared_ptr<interner<revid> > _itx);
+  tree_state();
+public:
+
+  ~tree_state();
+
+  static tree_state
+  new_tree() {return tree_state();}
+
+  static tree_state
+  merge(std::vector<tree_state> const & trees,
+        std::vector<change_set::path_rearrangement> const & changes,
+        std::string revision);
+
+  std::vector<path_conflict>
+  conflict(tree_state const & other) const;
+  
+  bool
+  is_clean()
+  {return conflict(*this).empty();}
+
+  std::vector<std::pair<item_id, file_path> >
+  current() const;
+
+  // get the changes along edge this->merged for merged=merge(this, other)
+  void
+  get_changes_for_merge(tree_state const & other,
+                        std::set<path_conflict::resolution> const & res,
+                        change_set::path_rearrangement & changes);
+private:
+  file_path
+  get_full_name(item_status::item_state x) const;
+
+  std::string
+  get_ambiguous_full_name(item_status::item_state x) const;
+
+  tree_state
+  mash(tree_state const & other) const;
+
+  static tree_state
+  mash(std::vector<tree_state> const & trees);
+};
+
+void
+dirmerge_test();
+
 #endif