# 
# patch "roster3.cc"
#  from [49d706cac36843bc95469bc82a71741d31d78353]
#    to [cfd28a77d3f5bd76b84138ec0fadea0b16c97865]
# 
# patch "roster3.hh"
#  from [53c429f5d8c02cd6f0a6ba8a273b0b7bcc738ba6]
#    to [e48dd575719a83620200e980d527640c38efa31d]
# 
========================================================================
--- roster3.cc	49d706cac36843bc95469bc82a71741d31d78353
+++ roster3.cc	cfd28a77d3f5bd76b84138ec0fadea0b16c97865
@@ -225,3 +225,118 @@
   i->second = val;
 }
 
+namespace 
+{
+  const node_id the_null_node = 0;
+  const node_id first_node = 1;
+  inline bool null_node(node_id n)
+  {
+    return n == the_null_node;
+  }
+  const node_id first_temp_node = widen<node_id, int>(1) << (sizeof(node_id) * 8 - 1);
+  inline bool temp_node(node_id n)
+  {
+    return n & first_temp_node;
+  }
+  
+  struct temp_node_id_source : public node_id_source
+  {
+    temp_node_id_source() : curr(first_temp_node) {}
+    virtual node_id next()
+    {
+      node_id n = curr++;
+      I(temp_node(n));
+      return n;
+    }
+    node_id curr;
+  };
+
+  struct true_node_id_source : public node_id_source
+  {
+    true_node_id_source(app_state & app) : app(app) {}
+    virtual node_id next()
+    {
+      node_id n = app.db.next_node_id();
+      I(!temp_node(n));
+      return n;
+    }
+    app_state & app;
+  };
+
+  // this handles all the stuff in a_new
+  void unify_roster_oneway(roster_t & a, std::set<node_id> & a_new,
+                           roster_t & b, std::set<node_id> & b_new,
+                           std::set<node_id> & new_ids,
+                           node_id_source & nis)
+  {
+    for (std::set<node_id>::const_iterator i = a_new.begin(); i != a_new.end(); ++i)
+      {
+        node_id const aid = *i;
+        split_path sp;
+        // SPEEDUP?: climb out only so far as is necessary to find a shared
+        // id?  possibly faster (since usually will get a hit immediately),
+        // but may not be worth the effort (since it doesn't take that long to
+        // get out in any case)
+        a.get_name(aid, sp);
+        node_id const bid = b.lookup(aid);
+        if (temp_node(bid))
+          {
+            node_id new_nid = nis.next();
+            a.replace_node_id(ls, new_nid);
+            b.replace_node_id(rs, new_nid);
+            new_ids.insert(new_nid);
+            b_new.erase(bid);
+          }
+        else
+          {
+            a.replace_node_id(aid, bid);
+            a.node(bid).birth_revision = b.node(bid).birth_revision;
+          }
+      }
+  }
+
+  // after this, left should == right, and there should be no temporary ids
+  // destroys sets, because that's handy (it has to scan over both, but it can
+  // skip some double-scanning)
+  void
+  unify_rosters(roster_t & left, std::set<node_id> & left_new,
+                roster_t & right, std::set<node_id> & right_new,
+                // these new_souls all come from the given soul source
+                std::set<node_id> & new_ids,
+                node_id_source & nis)
+  {
+    unify_roster_oneway(left, left_new, right, right_new, new_souls, ss);
+    unify_roster_oneway(right, right_new, left, left_new, new_souls, ss);
+  }
+}
+
+void
+make_roster_for_merge(cset const & left_cs, revision_id const & left_rid,
+                      cset const & right_cs, revision_id const & right_rid,
+                      revision_id const & new_rid,
+                      roster_t & result, marking_map & marking, app_state & app)
+{
+  I(!null_id(left_rid) && !null_id(right_rid));
+  roster_t left_r, right_r;
+  marking_map left_marking, right_marking;
+  app.db.get_roster(left_rid, left_r, left_marking);
+  app.db.get_roster(right_rid, right_r, right_marking);
+  temp_node_id_source nis;
+  result = left_r;
+  roster_t from_right_r(right_r);
+  editable_roster from_left_er(result, nis), from_right_er(from_right_r, nis);
+  left_cs.apply_to(from_left_er);
+  right_cs.apply_to(from_right_er);
+  std::set<node_id> new_ids;
+  unify_rosters(result, from_left_er.new_nodes,
+                from_right_r, from_right_er.new_nodes,
+                new_ids, true_node_id_source(app));
+  I(result == new_from_right);
+  for (std::set<node_id>::const_iterator i = new_ids.begin();
+       i != new_ids.end(); ++i)
+    {
+      node_t & n = result.node(*i);
+      n.birth_revision = new_rid;
+      safe_insert(marking, std::make_pair(*i, marking_t(new_rid, n)));
+    }
+}
========================================================================
--- roster3.hh	53c429f5d8c02cd6f0a6ba8a273b0b7bcc738ba6
+++ roster3.hh	e48dd575719a83620200e980d527640c38efa31d
@@ -14,33 +14,9 @@
 #include "paths.hh"
 #include "cset.hh"
 
-const node_id the_null_node = 0;
-const node_id first_node = 1;
-inline bool null_node(node_id n)
-{
-  return n == the_null_node;
-}
-const node_id first_temp_node = widen<node_id, int>(1) << (sizeof(node_id) * 8 - 1);
-inline bool temp_node(node_id n)
-{
-  return n & first_temp_node;
-}
-
 struct node_id_source
 {
   virtual node_id next() = 0;
-}
-
-struct temp_node_id_source : public node_id_source
-{
-  temp_node_id_source() : curr(first_temp_node) {}
-  virtual node_id next()
-  {
-    node_id n = curr++;
-    I(temp_node(n));
-    return n;
-  }
-  node_id curr;
 };
 
 ///////////////////////////////////////////////////////////////////
@@ -99,12 +75,17 @@
   void set_attr(split_path const & pth,
                 attr_name const & name,
                 attr_val const & val);
+  std::map<node_id, node_t> const & all_nodes() const
+  {
+    return nodes;
+  }
 private:
   std::map<node_id, node_t> nodes;
   std::map<node_id, dir_map> children_map;
   node_id root_dir;
 };
 
+// adaptor class to enable cset application on rosters.
 class editable_roster : public editable_tree
 {
 public:
@@ -124,43 +105,58 @@
   virtual node_id create_dir_node()
   {
     node_id nid = r.create_dir_node(nis);
-    new_nodes.insiert(nid);
+    new_nodes.insert(nid);
     return nid;
   }
   virtual node_id create_file_node(file_id const & content)
   {
     node_id nid = r.create_file_node(content, nis);
-    new_nodes.insiert(nid);
+    new_nodes.insert(nid);
     return nid;
   }
   virtual void attach_node(node_id nid, split_path const & dst)
   {
     r.attach_node(nid, dst);
-    touched_nodes.insert(nid);
   }
   virtual void apply_delta(split_path const & pth, 
                            file_id const & old_id, 
                            file_id const & new_id)
   {
     r.apply_delta(pth, old_id, new_id);
-    touched_nodes.insert(r.lookup(pth));
   }
   virtual void clear_attr(split_path const & pth,
                           attr_name const & name)
   {
     r.clear_attr(pth, name);
-    touched_nodes.insert(r.lookup(pth));
   }
   virtual void set_attr(split_path const & pth,
                         attr_name const & name,
                         attr_val const & val)
   {
     r.set_attr(pth, name, val);
-    touched_nodes.insert(r.lookup(pth));
   }
+  std::set<node_id> new_nodes;
 private:
   roster_t & r;
   node_id_source & nis;
-  std::set<node_id> new_nodes;
-  std::set<node_id> touched_nodes;
 };
+
+
+struct marking_t
+{
+  std::set<revision_id> parent_name;
+  std::set<revision_id> file_content;
+  std::map<attr_key, std::set<revision_id> > attrs;
+  marking_t(revision_id const & birth_rid, node_t const & n)
+  {
+    std::set<node_id> singleton;
+    singleton.insert(birth_rid);
+    parent_name = singleton;
+    file_content = singleton;
+    for (std::map<attr_key, attr_value>::const_iterator i = n.attrs.begin();
+         i != n.attrs.end(); ++i)
+      attrs.insert(std::make_pair(i->first, singleton));
+  }
+};
+
+typedef std::map<node_id, marking_t> marking_map;