# 
# add_file "cset.cc"
# 
# add_file "cset.hh"
# 
# patch "Makefile.am"
#  from [8aefb7ba1e9e19ac619b8828bbcdd8106ee3e7fa]
#    to [4fd07091c0eb1958cfbafbbd3ad1b8bdc22a776d]
# 
# patch "cset.cc"
#  from []
#    to [49d2b2d080bd074f229d4c15e34ffa86303b0234]
# 
# patch "cset.hh"
#  from []
#    to [6a2ab00c024533f530ae9aa3106fc84a47fb06e0]
# 
========================================================================
--- Makefile.am	8aefb7ba1e9e19ac619b8828bbcdd8106ee3e7fa
+++ Makefile.am	4fd07091c0eb1958cfbafbbd3ad1b8bdc22a776d
@@ -31,6 +31,7 @@
          rcs_import.cc rcs_import.hh					\
          revision.cc revision.hh					\
 	 change_set.cc change_set.hh					\
+	 cset.cc cset.hh						\
          mt_version.cc mt_version.hh					\
          automate.cc automate.hh					\
          database_check.cc database_check.hh				\
========================================================================
--- cset.cc	
+++ cset.cc	49d2b2d080bd074f229d4c15e34ffa86303b0234
@@ -0,0 +1,142 @@
+// copyright (C) 2005 nathaniel smith <address@hidden>
+// copyright (C) 2005 graydon hoare <address@hidden>
+// all rights reserved.
+// licensed to the public under the terms of the GNU GPL (>= 2)
+// see the file COPYING for details
+
+#include "cset.hh"
+#include "sanity.hh"
+
+using std::set;
+using std::map;
+using std::pair;
+
+struct
+detach
+{
+  detach(split_path const & src) 
+    : src_path(src), 
+      reattach(false) 
+  {}
+  
+  detach(split_path const & src, 
+	 split_path const & dst) 
+    : src_path(src), 
+      reattach(true), 
+      dst_path(dst) 
+  {}
+  
+  split_path src_path;
+  bool reattach;
+  split_path dst_path;
+
+  bool operator<(struct detach const & other) const
+  {
+    // We sort detach operations bottom-up by src path
+    return src_path > other.src_path;
+  }
+};
+
+struct
+attach
+{
+  attach(node_id n, 
+	 split_path const & p) 
+    : node(n), path(p)
+  {}
+
+  node_id node;
+  split_path path;
+
+  bool operator<(struct attach const & other) const
+  {
+    // We sort attach operations top-down by path
+    return path < other.path;
+  }
+};
+
+
+void 
+cset::apply_to(editable_tree & t)
+{
+  set<detach> detaches;
+  set<attach> attaches;
+  set<node_id> drops;
+
+
+  // FIXME -- normalize:
+  //
+  //   add_file address@hidden + apply_delta id1->id2
+  //   clear_attr foo:bar + set_attr foo:bar=baz
+  //
+  // possibly more?
+
+
+  // Decompose all additions into a set of pending attachments to be
+  // executed top-down. We might as well do this first, to be sure we
+  // can form the new nodes -- such as in a filesystem -- before we do
+  // anything else potentially destructive. This should all be
+  // happening in a temp directory anyways.
+
+  for (set<split_path>::const_iterator i = dirs_added.begin();
+       i != dirs_added.end(); ++i)
+    attaches.insert(attach(t.create_dir_node(), *i));
+
+  for (map<split_path, file_id>::const_iterator i = files_added.begin();
+       i != files_added.end(); ++i)
+    attaches.insert(attach(t.create_file_node(i->second), i->first));
+
+
+  // Decompose all path deletion and the first-half of renamings on
+  // existing paths into the set of pending detaches, to be executed
+  // bottom-up.
+
+  for (set<split_path>::const_iterator i = nodes_deleted.begin();
+       i != nodes_deleted.end(); ++i)    
+    detaches.insert(detach(*i));
+  
+  for (map<split_path, split_path>::const_iterator i = nodes_renamed.begin();
+       i != nodes_renamed.end(); ++i)
+    detaches.insert(detach(i->first, i->second));
+
+
+  // Execute all the detaches, rescheduling the results of each detach
+  // for either attaching or dropping.
+
+  for (set<detach>::const_iterator i = detaches.begin(); 
+       i != detaches.end(); ++i)
+    {
+      node_id n = t.detach_node(i->src_path);
+      if (i->reattach)
+	attaches.insert(attach(n, i->dst_path));
+      else
+	drops.insert(n);
+    }
+
+
+  // Execute all the attaches.
+
+  for (set<attach>::const_iterator i = attaches.begin(); i != attaches.end(); ++i)
+    t.attach_node(i->node, i->path);
+
+
+  // Execute all the drops.
+
+  for (set<node_id>::const_iterator i = drops.begin(); i != drops.end(); ++i)
+    t.drop_detached_node (*i);
+
+
+  // Execute all the in-place edits
+  for (map<split_path, pair<file_id, file_id> >::const_iterator i = deltas_applied.begin();
+       i != deltas_applied.end(); ++i)
+    t.apply_delta(i->first, i->second.first, i->second.second);
+
+  for (map<split_path, attr_name>::const_iterator i = attrs_cleared.begin();
+       i != attrs_cleared.end(); ++i)
+    t.clear_attr(i->first, i->second);
+
+  for (map<pair<split_path, attr_name>, attr_val>::const_iterator i = attrs_set.begin();
+       i != attrs_set.end(); ++i)
+    t.set_attr(i->first.first, i->first.second, i->second);
+}
+
========================================================================
--- cset.hh	
+++ cset.hh	6a2ab00c024533f530ae9aa3106fc84a47fb06e0
@@ -0,0 +1,80 @@
+#ifndef __CSET_HH__
+#define __CSET_HH__
+
+// copyright (C) 2005 nathaniel smith <address@hidden>
+// copyright (C) 2005 graydon hoare <address@hidden>
+// all rights reserved.
+// licensed to the public under the terms of the GNU GPL (>= 2)
+// see the file COPYING for details
+
+#include <map>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "numeric_vocab.hh"
+#include "paths.hh"
+#include "vocab.hh"
+
+typedef std::string attr_name;
+typedef std::string attr_val;
+typedef std::map<attr_name, attr_val> attr_map;
+
+typedef std::vector<path_component> split_path;
+
+// Virtual interface to a tree-of-files which you can edit
+// destructively; this may be the filesystem or an in-memory
+// representation (a roster / mfest).
+
+typedef u64 node_id;
+
+struct editable_tree
+{
+  // Detaching existing nodes (for renaming or deleting)
+  virtual node_id detach_node(split_path const & src) = 0;
+  virtual void drop_detached_node(node_id n) = 0;
+
+  // Attaching new nodes (via creation or as the tail end of renaming)
+  virtual node_id create_dir_node() = 0;
+  virtual node_id create_file_node(file_id const & content) = 0;
+  virtual void attach_node(node_id n, split_path const & dst) = 0;
+
+  // Modifying elements in-place
+  virtual void apply_delta(split_path const & pth, 
+			   file_id const & old_id, 
+			   file_id const & new_new) = 0;
+  virtual void clear_attr(split_path const & pth,
+			  attr_name const & name) = 0;
+  virtual void set_attr(split_path const & pth,
+			attr_name const & name,
+			attr_val const & val) = 0;
+
+  virtual ~editable_tree() {}
+};
+
+
+// In-memory representation of a change set. 
+
+struct cset 
+{
+  // Deletions.
+  std::set<split_path> nodes_deleted;
+
+  // Additions.
+  std::set<split_path> dirs_added;
+  std::map<split_path, file_id> files_added;
+
+  // Pure renames.
+  std::map<split_path, split_path> nodes_renamed;
+
+  // Pure deltas.
+  std::map<split_path, std::pair<file_id, file_id> > deltas_applied;
+
+  // Attribute changes.
+  std::map<split_path, attr_name> attrs_cleared;
+  std::map<std::pair<split_path, attr_name>, attr_val> attrs_set;
+
+  void apply_to(editable_tree & t);
+};
+
+#endif // __CSET_HH__