Index: src/Common/InternedString.cc
===================================================================
--- src/Common/InternedString.cc	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
+++ src/Common/InternedString.cc	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
@@ -0,0 +1,24 @@
+//
+// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
+//
+// The contents of this file are covered under the licence agreement in the
+// file "LICENCE" distributed with Cforall.
+//
+// InternedString.cc --
+//
+// Author           : Aaron B. Moss
+// Created On       : Thu Jun 14 11:15:00 2018
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Thu Jun 14 11:15:00 2018
+// Update Count     : 1
+//
+
+#include "InternedString.h"
+
+std::unordered_set< std::string > interned_string::canonical;
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //
Index: src/Common/InternedString.h
===================================================================
--- src/Common/InternedString.h	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
+++ src/Common/InternedString.h	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
@@ -0,0 +1,78 @@
+//
+// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
+//
+// The contents of this file are covered under the licence agreement in the
+// file "LICENCE" distributed with Cforall.
+//
+// InternedString.h --
+//
+// Author           : Aaron B. Moss
+// Created On       : Thu Jun 14 11:15:00 2018
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Thu Jun 14 11:15:00 2018
+// Update Count     : 1
+//
+
+#pragma once
+
+#include <functional>
+#include <string>
+#include <unordered_set>
+#include <utility>
+
+/// Keeps canonical copies of a std::string for quicker comparisons
+class interned_string {
+	/// Shared map of canonical string representations
+	static std::unordered_set< std::string > canonical;
+
+	/// Canonical representation of empty string
+	static const std::string* empty_string() {
+		static const std::string* mt = [](){
+			return &*canonical.emplace( "" ).first;
+		}();
+		return mt;
+	}
+
+	/// Canonicalize string
+	template<typename S>
+	static const std::string* intern( S&& s ) {
+		return &*canonical.emplace( std::forward<S>(s) ).first;
+	}
+
+	/// Pointer to stored string
+	const std::string* s;
+	
+public:
+	interned_string() : s{empty_string()} {}
+	interned_string(const char* cs) : s{intern(cs)} {}
+	interned_string(const std::string& ss) : s{intern(ss)} {}
+	/// Invalid string
+	interned_string(std::nullptr_t) : s{nullptr} {}
+
+	operator const std::string& () const { return *s; }
+	const std::string& str() const { return (const std::string&)*this; }
+
+	bool operator== (const interned_string& o) const { return s == o.s; }
+	bool operator!= (const interned_string& o) const { return s != o.s; }
+
+	/// Check for invalid string
+	explicit operator bool () { return s != nullptr; }
+};
+
+inline std::ostream& operator<< (std::ostream& out, const interned_string& s) {
+	return out << (const std::string&)s;
+}
+
+namespace std {
+	template<> struct hash<interned_string> {
+		std::size_t operator() (const interned_string& s) const {
+			return std::hash<const std::string*>{}( &(const std::string&)s );
+		}
+	};
+}
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //
Index: src/Common/PersistentDisjointSet.h
===================================================================
--- src/Common/PersistentDisjointSet.h	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
+++ src/Common/PersistentDisjointSet.h	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
@@ -0,0 +1,439 @@
+//
+// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
+//
+// The contents of this file are covered under the licence agreement in the
+// file "LICENCE" distributed with Cforall.
+//
+// PersistentDisjointSet.h --
+//
+// Author           : Aaron B. Moss
+// Created On       : Wed Jun 13 16:31:00 2018
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Wed Jun 13 16:31:00 2018
+// Update Count     : 1
+//
+
+#pragma once
+
+#include <cassert>
+#include <functional>
+#include <unordered_map>
+#include <utility>
+
+#include "GC.h"
+
+/// Persistent disjoint-set data structure based on the persistent array in 
+/// Conchon & Filliatre "A Persistent Union-Find Data Structure". Path 
+/// compression is not performed (to lower cost of persistent rollback). 
+/// Auxilliary lists are kept for efficient retrieval of class members.
+/// Find root should still operate in O(log k), for k the size of an 
+/// equivalence class.
+
+template<typename Elm, typename Hash = std::hash<Elm>, typename Eq = std::equal_to<Elm>>
+class PersistentDisjointSet : public GC_Object {
+public:
+	/// Type of this class
+	using Self = PersistentDisjointSet<Elm, Hash, Eq>;
+
+	/// Types of version nodes
+	enum Mode { 
+		BASE,    ///< Root node of version tree
+		ADD,     ///< Add key to set
+		REM,     ///< Reverse add operation
+		ADDTO,   ///< Merge one class root under another
+		REMFROM  ///< Reverse addTo operation
+	};
+
+private:
+	/// Type of node height
+	using Height = unsigned char;
+
+	/// Disjoint-set node
+	struct Node {
+		Elm parent;     ///< Parent node in equivalence class
+		Elm next;       ///< Next node in equivalence class
+		Height height;  ///< Tree height of the node
+
+		template<typename E>
+		Node(E&& e) : parent(e), next(std::forward<E>(e)), height(0) {}
+
+		template<typename E, typename F>
+		Node(E&& p, F&& n, Height h) 
+			: parent(std::forward<E>(p)), next(std::forward<F>(n)), height(h) {}
+	};
+
+	/// Type of class map
+	using Base = std::unordered_map<Elm, Node, Hash, Eq>;
+
+	/// Node inserted into underlying map as new equivalence class
+	struct Add {
+		Self* base;  ///< Modified map
+		Elm root;    ///< Element added
+
+		template<typename E>
+		Add(Self* b, E&& r) : base(b), root(std::forward<E>(r)) {}
+	};
+
+	/// Two classes merged
+	struct AddTo {
+		Self* base;       ///< Modified map
+		Elm root;         ///< Root node
+		Elm child;        ///< Child node, formerly root of own class
+		bool new_height;  ///< Did the root node's height change?
+
+		template<typename R, typename C>
+		AddTo(Self* b, R&& r, C&& c, bool h) 
+			: base(b), root(std::forward<R>(r)), child(std::forward<C>(c)), new_height(h) {}
+	};
+
+	/// Underlying storage
+	union Data {
+		char none;
+		Base base;
+		Add add;
+		AddTo add_to;
+
+		Data() : none('\0') {}
+		~Data() {}
+	} data;
+
+	/// Type of version node
+	mutable Mode mode;
+
+	/// get mutable reference as T
+	template<typename T>
+	T& as() { return reinterpret_cast<T&>(data); }
+
+	/// get const reference as T
+	template<typename T>
+	const T& as() const { return reinterpret_cast<const T&>(data); }
+
+	/// get rvalue reference as T
+	template<typename T>
+	T&& take_as() { return std::move(as<T>()); }
+
+	/// initialize as T
+	template<typename T, typename... Args>
+	void init( Args&&... args ) {
+		new( &as<T>() ) T { std::forward<Args>(args)... };
+	}
+
+	/// reset according to current mode
+	void reset() {
+		switch( mode ) {
+			case BASE:                as<Base>().~Base();   break;
+			case ADD: case REM:       as<Add>().~Add();     break;
+			case ADDTO: case REMFROM: as<AddTo>().~AddTo(); break;
+			default: assertf(false, "invalid mode");
+		}
+	}
+
+	PersistentDisjointSet( Mode m, Base&& b ) : data(), mode(m) {
+		assertf(m == BASE, "invalid mode");
+		init<Base>(std::move(b));
+	}
+
+	template<typename R>
+	PersistentDisjointSet( Mode m, const Self* b, R&& r ) : data(), mode(m) {
+		assertf(m == ADD || m == REM, "invalid mode");
+		init<Add>(b, std::forward<R>(r));
+	}
+
+	template<typename R, typename C>
+	PersistentDisjointSet( Mode m, const Self* b, R&& r, C&& c, bool h ) : data(), mode(m) {
+		assertf(m == ADDTO || m == REMFROM, "invalid mode");
+		init<AddTo>(b, std::forward<R>(r), std::forward<C>(c), h);
+	}
+
+	/// Adds (also removes) graph edges.
+	/// * `from.parent` updated to `new_root`, 
+	/// * `from.next` and `to.next` swapped (splices or un-splices class lists)
+	/// * `to.height` adjusted by change
+	template<typename R>
+	static void addEdge( Node& from, Node& to, R&& new_root, Height change ) {
+		from.parent = std::forward<R>(new_root);
+		std::swap(from.next, to.next);
+		to.height += change;
+	}
+
+protected:
+	void trace( const GC& gc ) const {
+		switch( mode ) {
+			case BASE: {
+				for (const auto& entry : as<Base>()) {
+					gc << entry.first;
+				}
+				return;
+			}
+			case ADD: case REM: {
+				const Add& self = as<Add>();
+				gc << self.base << self.root;
+				return;
+			}
+			case ADDTO: case REMFROM: {
+				const AddTo& self = as<AddTo>();
+				gc << self.base << self.root << self.child;
+				return;
+			}
+			default: assertf(false, "invalid mode");
+		}
+	}
+
+public:
+	using size_type = std::size_t;
+
+	using iterator = typename Base::const_iterator;
+
+	PersistentDisjointSet() : data(), mode(BASE) { init<Base>(); }
+
+	PersistentDisjointSet( const Self& o ) = delete;
+
+	Self& operator= ( const Self& o ) = delete;
+
+	~PersistentDisjointSet() { reset(); }
+
+	/// reroot persistent data structure at current node
+	void reroot() const {
+		if ( mode == BASE ) return;
+
+		// reroot base
+		Self* mut_this = const_cast<Self*>(this);
+		Self* base = ( mode == ADD || mode == REM ) ? 
+			mut_this->as<Add>().base : 
+			mut_this->as<AddTo>().base;
+		base->reroot();
+		assertf(base->mode == BASE, "reroot results in base");
+
+		// take map out of base
+		Base base_map = base->take_as<Base>();
+		base->reset();
+
+		// switch base to inverse of self and mutate base map
+		switch ( mode ) {
+			case ADD: {
+				Add& self = mut_this->as<Add>();
+
+				base->init<Add>( mut_this, self.root );
+				base->mode = REM;
+
+				base_map.emplace( self.root, Node{ std::move(self.root) } );
+			} break;
+			case REM: {
+				Add& self = mut_this->as<Add>();
+
+				base->init<Add>( mut_this, self.root );
+				base->mode = ADD;
+
+				base_map.erase( self.root );
+			} break;
+			case ADDTO: {
+				AddTo& self = mut_this->as<AddTo>();
+
+				base->init<AddTo>( mut_this, self.root, self.child, self.new_height );
+				base->mode = REMFROM;
+
+				auto child_it = base_map.find( self.child );
+				auto root_it = base_map.find( self.root );
+				assertf(child_it != base_map.end() && root_it != base_map.end(), 
+					"nodes must exist in base");
+				Node& child = child_it->second;
+				Node& root = root_it->second;
+
+				addEdge( child, root, std::move(self.root), Height(self.new_height) );
+			} break;
+			case REMFROM: {
+				AddTo& self = mut_this->as<AddTo>();
+
+				base->init<AddTo>( mut_this, self.root, self.child, self.new_height );
+				base->mode = ADDTO;
+
+				auto child_it = base_map.find( self.child );
+				auto root_it = base_map.find( self.root );
+				assertf(child_it != base_map.end() && root_it != base_map.end(), 
+					"nodes must exist in base");
+				Node& child = child_it->second;
+				Node& root = root_it->second;
+
+				addEdge( child, root, std::move(self.child), Height(-1 * self.new_height) );
+			} break;
+			default: assertf(false, "invalid mode");
+		}
+
+		// set base map into self
+		mut_this->reset();
+		mut_this->init<Base>( std::move(base_map) );
+		mode = BASE;
+	}
+
+private:
+	/// Gets the base after rerooting at the current node 
+	const Base& rerooted() const {
+		reroot();
+		return as<Base>();
+	}
+
+public:
+	/// true if the set of sets is empty
+	bool empty() const { return rerooted().empty(); }
+
+	/// Get number of entries in the map
+	size_type size() const { return rerooted().size(); }
+
+	/// Get begin iterator for map; may be invalidated by calls to non-iteration functions 
+	/// or functions on other maps in the same chain
+	iterator begin() const { return rerooted().begin(); }
+
+	/// Get end iterator for map; may be invalidated by calls to non-iteration functions 
+	/// or functions on other maps in the same chain
+	iterator end() const { return rerooted().end(); }
+
+	/// Check if value is present
+	size_type count(Elm i) const { return rerooted().count( i ); }
+
+	/// Finds root for element i, assertfs i is present
+	Elm find(Elm i) const {
+		const Base& self = rerooted();
+		
+		auto it = self.find( i );
+		while (true) {
+			assertf(it != self.end(), "find target not present");
+
+			if ( it->first == it->second.parent ) return it->first;
+
+			it = self.find( it->second.parent );
+		}
+	}
+
+	/// Finds root for element i, or default if i is not present
+	template<typename E>
+	Elm find_or_default(Elm i, E&& d) const {
+		const Base& self = rerooted();
+
+		auto it = self.find( i );
+		if ( it == self.end() ) return d;
+
+		while ( it->first != it->second.parent ) {
+			it = self.find( it->second.parent );
+
+			assertf(it != self.end(), "find target not present");
+		}
+		return it->first;
+	}
+
+	/// Adds fresh class including only one item; returns updated map
+	template<typename E>
+	Self* add(E&& i) {
+		reroot();
+		
+		// transfer map to new node
+		Self* ret = new Self{ BASE, take_as<Base>() };
+		reset();
+
+		// set self to REM node
+		init<Add>( ret, i );
+		mode = REM;
+		
+		// add element in returned map
+		Base& base_map = ret->as<Base>();
+		bool added = base_map.emplace( i, Node{ std::forward<E>(i) } ).second;
+		assertf(added, "added element already present in map");
+
+		return ret;
+	}
+
+	/// Merges two classes given by their roots; returns updated map.
+	/// If two classes have same height, `i` is new root.
+	Self* merge(Elm i, Elm j) {
+		reroot();
+
+		// transfer map to new node
+		Self* ret = new Self{ BASE, take_as<Base>() };
+		reset();
+
+		// find set nodes
+		Base& base_map = ret->as<Base>();
+		auto it = base_map.find( i );
+		auto jt = base_map.find( j );
+		assertf(it != base_map.end() && jt != base_map.end(), "nodes must exist in base");
+		Node& in = it->second;
+		Node& jn = jt->second;
+
+		// update returned map and set self to appropriate REMFROM node
+		if ( in.height < jn.height ) {
+			addEdge( in, jn, j, 0 );
+			init<AddTo>( ret, j, i, false );
+		} else if ( jn.height < in.height ) {
+			addEdge( jn, in, i, 0 );
+			init<AddTo>( ret, i, j, false );
+		} else /* if ( jn.height == in.height ) */ {
+			addEdge( jn, in, i, 1 );
+			init<AddTo>( ret, i, j, true );
+		}
+		mode = REMFROM;
+
+		return ret;
+	}
+
+	/// Reports all members of a class to `out`; none if i does not exist in map
+	template<typename OutputIterator>
+	void find_class(Elm i, OutputIterator&& out) const {
+		const Base& self = rerooted();
+
+		// skip empty classes
+		if ( ! self.count( i ) ) return;
+
+		Elm crnt = i;
+		do {
+			*out++ = crnt;
+			auto it = self.find( crnt );
+			assertf( it != self.end(), "current node must exist in base" );
+			crnt = it->second.next;
+		} while ( crnt != i );
+	}
+
+	/// Get version node type
+	Mode get_mode() const { return mode; }
+
+	/// Get next version up the revision tree (self if base node)
+	const Self* get_base() const {
+		switch ( mode ) {
+			case BASE:                return this;
+			case ADD: case REM:       return as<Add>().base;
+			case ADDTO: case REMFROM: return as<AddTo>().base;
+			default: assertf(false, "invalid mode");
+		}
+	}
+
+	/// Get root of new class formed/removed/split (undefined if called on base)
+	Elm get_root() const {
+		switch ( mode ) {
+			case ADD: case REM:       return as<Add>().root;
+			case ADDTO: case REMFROM: return as<AddTo>().root;
+			default: assertf(false, "invalid mode for get_root()");
+		}
+	}
+
+	/// Get child root of new class formed/split (undefined if called on base or add/remove node)
+	Elm get_child() const {
+		switch ( mode ) {
+			case ADDTO: case REMFROM: return as<AddTo>().child;
+			default: assertf(false, "invalid mode for get_child()");
+		}
+	}
+
+	/// Gets acted-upon key for new class (root unless for add/remove node, child for add to/remove 
+	/// from node, undefined otherwise)
+	Elm get_key() const {
+		switch ( mode ) {
+			case ADD: case REM:       return as<Add>().root;
+			case ADDTO: case REMFROM: return as<AddTo>().child;
+			default: assertf(false, "invalid mode for get_key()");
+		}
+	}
+};
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //
Index: src/Common/PersistentMap.h
===================================================================
--- src/Common/PersistentMap.h	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
+++ src/Common/PersistentMap.h	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
@@ -0,0 +1,428 @@
+//
+// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
+//
+// The contents of this file are covered under the licence agreement in the
+// file "LICENCE" distributed with Cforall.
+//
+// PersistentMap.h --
+//
+// Author           : Aaron B. Moss
+// Created On       : Wed Jun 13 16:31:00 2018
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Wed Jun 13 16:31:00 2018
+// Update Count     : 1
+//
+
+#pragma once
+
+#include <cassert>
+#include <cstddef>
+#include <functional>
+#include <unordered_map>
+#include <utility>
+
+#include "GC.h"
+
+/// Wraps a hash table in a persistent data structure, using a technique based 
+/// on the persistent array in Conchon & Filliatre "A Persistent Union-Find 
+/// Data Structure"
+
+template<typename Key, typename Val, 
+         typename Hash = std::hash<Key>, typename Eq = std::equal_to<Key>>
+class PersistentMap : public GC_Object {
+public:
+	/// Type of this class
+	using Self = PersistentMap<Key, Val, Hash, Eq>;
+
+	/// Types of version nodes
+	enum Mode { 
+		BASE,  ///< Root node of version tree
+		REM,   ///< Key removal node
+		INS,   ///< Key update node
+		UPD    ///< Key update node
+	};
+
+private:
+	/// Type of underlying hash table
+	using Base = std::unordered_map<Key, Val, Hash, Eq>;
+	
+	/// Node inserted into underlying map
+	struct Ins {
+		Self* base;  ///< Modified map
+		Key key;     ///< Key inserted
+		Val val;     ///< Value stored
+
+		template<typename K, typename V>
+		Ins(Self* b, K&& k, V&& v) : base(b), key(std::forward<K>(k)), val(std::forward<V>(v)) {}
+	};
+
+	/// Node removed from underlying map
+	struct Rem {
+		Self* base;  ///< Modified map
+		Key key;     ///< Key removed
+
+		template<typename K>
+		Rem(Self* b, K&& k) : base(b), key(std::forward<K>(k)) {}
+	};
+
+	/// Underlying storage
+	union Data {
+		char def;
+		Base base;
+		Ins ins;
+		Rem rem;
+
+		Data() : def('\0') {}
+		~Data() {}
+	} data;
+
+	// Mode of node
+	mutable Mode mode;
+
+	/// get mutable reference as T
+	template<typename T>
+	T& as() { return reinterpret_cast<T&>(data); }
+
+	/// get const reference as T
+	template<typename T>
+	const T& as() const { return reinterpret_cast<const T&>(data); }
+
+	/// get rvalue reference as T
+	template<typename T>
+	T&& take_as() { return std::move(as<T>()); }
+
+	/// initialize as T
+	template<typename T, typename... Args>
+	void init( Args&&... args ) {
+		new( &as<T>() ) T { std::forward<Args>(args)... };
+	}
+
+	/// reset as current mode
+	void reset() {
+		switch( mode ) {
+			case BASE:          as<Base>().~Base(); break;
+			case REM:           as<Rem>().~Rem();   break;
+			case INS: case UPD: as<Ins>().~Ins();   break;
+			default: assertf(false, "invalid mode");
+		}
+	}
+
+	/// reset as base
+	void reset_as_base() { 
+		assertf( mode == BASE, "can only reset_as_base() on BASE" );
+		as<Base>().~Base();
+	}
+
+	PersistentMap( Mode m, Base&& b ) : data(), mode(m) {
+		assertf(m == BASE, "invalid mode");
+		init<Base>(std::move(b));
+	}
+
+	template<typename K, typename V>
+	PersistentMap( Mode m, const Self* o, K&& k, V&& v ) : data(), mode(m) {
+		assertf(m == INS || m == UPD, "invalid mode");
+		init<Ins>(o, std::forward<K>(k), std::forward<V>(v));
+	}
+
+	template<typename K>
+	PersistentMap( Mode m, const Self* o, K&& k ) : data(), mode(m) {
+		assertf(m == REM, "invalid mode");
+		init<Rem>(o, std::forward<K>(k));
+	}
+
+protected:
+	void trace(const GC& gc) const {
+		switch( mode ) {
+			case BASE: {
+				for (const auto& entry : as<Base>()) {
+					gc << entry.first << entry.second;
+				}
+				return;
+			}
+			case REM: {
+				const Rem& self = as<Rem>();
+				gc << self.base << self.key;
+				return;
+			}
+			case INS: case UPD: {
+				const Ins& self = as<Ins>();
+				gc << self.base << self.key << self.val;
+				return;
+			}
+			default: assertf(false, "invalid mode");
+		}
+	}
+
+public:
+	using size_type = std::size_t;
+
+	using iterator = typename Base::const_iterator;
+
+	PersistentMap() : data(), mode(BASE) { init<Base>(); }
+
+	PersistentMap( const Self& o ) = delete;
+
+	Self& operator= ( const Self& o ) = delete;
+
+	~PersistentMap() { reset(); }
+
+	/// reroot persistent map at current node
+	void reroot() const {
+		// recursive base case
+		if ( mode == BASE ) return;
+		
+		// reroot base
+		Self* mut_this = const_cast<Self*>(this);
+		Self* base = ( mode == REM ) ? mut_this->as<Rem>().base : mut_this->as<Ins>().base;
+		base->reroot();
+		assertf(base->mode == BASE, "reroot results in base");
+
+		// take map out of base
+		Base base_map = base->take_as<Base>();
+		base->reset_as_base();
+
+		// switch base to inverse of self and mutate base map
+		switch ( mode ) {
+			case REM: {
+				Rem& self = mut_this->as<Rem>();
+				auto it = base_map.find( self.key );
+				assertf( it != base_map.end(), "removed node must exist in base");
+
+				base->init<Ins>( mut_this, std::move(self.key), std::move(it->second) );
+				base->mode = INS;
+
+				base_map.erase( it );
+				break;
+			}
+			case INS: {
+				Ins& self = mut_this->as<Ins>();
+
+				base->init<Rem>( mut_this, self.key );
+				base->mode = REM;
+
+				base_map.emplace( std::move(self.key), std::move(self.val) );
+				break;
+			}
+			case UPD: {
+				Ins& self = mut_this->as<Ins>();
+				auto it = base_map.find( self.key );
+				assertf( it != base_map.end(), "updated node must exist in base");
+
+				base->init<Ins>( mut_this, std::move(self.key), std::move(it->second) );
+				base->mode = UPD;
+
+				it->second = std::move(self.val);
+				break;
+			}
+			default: assertf(false, "invalid mode");
+		}
+
+		// set base map into self
+		mut_this->reset();
+		mut_this->init<Base>( std::move(base_map) );
+		mode = BASE;
+	}
+
+private:
+	/// Gets the base after rerooting at the current node
+	const Base& rerooted() const {
+		reroot();
+		return as<Base>();
+	}
+
+public:
+	/// true iff the map is empty
+	bool empty() const { return rerooted().empty(); }
+
+	/// Get number of entries in map
+	size_type size() const { return rerooted().size(); }
+
+	/// Get begin iterator for map; may be invalidated by calls to non-iteration functions 
+	/// or functions on other maps in the same chain
+	iterator begin() const { return rerooted().begin(); }
+
+	/// Get end iterator for map; may be invalidated by calls to non-iteration functions 
+	/// or functions on other maps in the same chain
+	iterator end() const { return rerooted().end(); }
+
+	/// Get underlying map iterator for value
+	iterator find(const Key& k) const { return rerooted().find( k ); }
+
+	/// Check if value is present
+	size_type count(const Key& k) const { return rerooted().count( k ); }
+
+	/// Get value; undefined behavior if not present
+	const Val& get(const Key& k) const {
+		const Base& self = rerooted();
+		auto it = self.find( k );
+		assertf(it != self.end(), "get target not present");
+		return it->second;
+	}
+
+	/// Get value; returns default if not present
+	template<typename V>
+	Val get_or_default(const Key& k, V&& d) const {
+		const Base& self = rerooted();
+		auto it = self.find( k );
+		if ( it == self.end() ) return d;
+		else return it->second;
+	}
+
+	/// Set value, storing new map in output variable
+	template<typename K, typename V>
+	Self* set(K&& k, V&& v) {
+		reroot();
+		assertf(mode == BASE, "reroot results in base");
+
+		// transfer map to new node
+		Self* ret = new Self{ BASE, take_as<Base>() };
+		reset_as_base();
+		Base& base_map = ret->as<Base>();
+
+		// check if this is update or insert
+		auto it = base_map.find( k );
+		if ( it == base_map.end() ) {
+			// set self to REM node and insert into base
+			init<Rem>( ret, k );
+			mode = REM;
+
+			base_map.emplace_hint( it, std::forward<K>(k), std::forward<V>(v) );
+		} else {
+			// set self to UPD node and modify base
+			init<Ins>( ret, std::forward<K>(k), std::move(it->second) );
+			mode = UPD;
+
+			it->second = std::forward<V>(v);
+		}
+
+		return ret;
+	}
+
+	/// Remove value, storing new map in output variable; does nothing if key not in map
+	Self* erase(const Key& k) {
+		reroot();
+		assertf(mode == BASE, "reroot results in base");
+
+		// exit early if key does not exist in map
+		if ( ! as<Base>().count( k ) ) return this;
+
+		// transfer map to new node
+		Self* ret = new Self{ BASE, take_as<Base>() };
+		reset_as_base();
+		Base& base_map = ret->as<Base>();
+
+		// set self to INS node and remove from base
+		init<Ins>( ret, k, base_map[k] );
+		mode = INS;
+		
+		base_map.erase( k );
+
+		return ret;
+	}
+
+	/// smart reference for indexing interface
+	class Entry {
+	friend PersistentMap;
+		Self* base;
+		const Key& key;
+
+	public:
+		Entry(Self* b, const Key& k) : base(b), key(k) {}
+
+		/// Gets the underlying map instance
+		Self* get_base() const { return base; }
+
+		/// Gets the key
+		const Key& get_key() const { return key; }
+
+		/// Checks if the key exists in the map
+		bool exists() const { return base->count(key); }
+
+		/// Gets the value for the key (if it exists)
+		const Val& get() const { return base->get(key); }
+
+		/// Cast version of get
+		operator const Val& () const { return base->get(key); }
+
+		/// Sets the value into the key; returns entry pointing to new set
+		template<typename V>
+		Entry& set(V&& v) {
+			base = base->set(key, std::forward<V>(v));
+			return *this;
+		}
+
+		/// Assignment version of set
+		template<typename V>
+		Entry& operator= (V&& v) {
+			base = base->set(key, std::forward<V>(v));
+			return *this;
+		}
+
+		/// Gets value or initializes to new value from args
+		template<typename... Args>
+		Entry& get_or(Args&&... args) {
+			base = base->get_or(key, std::forward<Args>(args)...);
+			return *this;
+		}
+	};
+
+	/// Gets smart reference to slot with given key
+	Entry operator[] (const Key& k) { return { this, k }; }
+
+	/// Gets Entry for key, initializing from args if not present
+	template<typename... Args>
+	Entry get_or_insert(const Key& k, Args&&... args) {
+		Base& base_map = rerooted();
+
+		// check already present
+		if ( base_map.count(k) ) return { this, k };
+
+		// otherwise insert based on parameters
+		base_map.emplace( k, Val{ std::forward<Args>(args)... } );
+		Self* ret = new Self{ BASE, std::move(base_map) };
+
+		// update self to point to new base
+		reset_as_base();
+		init<Rem>( ret, k );
+		mode = REM;
+
+		// return entry for new base
+		return { ret, k };
+	}
+
+	/// Get version node type
+	Mode get_mode() const { return mode; }
+
+	/// Get next version up the revision tree (self if base node)
+	const Self* get_base() const {
+		switch ( mode ) {
+			case BASE:          return this;
+			case REM:           return as<Rem>().base;
+			case INS: case UPD: return as<Ins>().base;
+			default: assertf(false, "invalid mode");
+		}
+	}
+
+	/// Get key of revision node (undefined if called on base)
+	const Key& get_key() const {
+		switch ( mode ) {
+			case REM:           return as<Rem>().key;
+			case INS: case UPD: return as<Ins>().key;
+			default: assertf(false, "invalid mode for get_key()");
+		}
+	}
+
+	/// Get value of insert/update revision node (undefined otherwise)
+	const Val& get_val() const {
+		switch ( mode ) {
+			case INS: case UPD: return as<Ins>().val;
+			default: assertf(false, "invalid mode for get_val()");
+		}
+	}
+};
+
+// Local Variables: //
+// tab-width: 4 //
+// mode: c++ //
+// compile-command: "make install" //
+// End: //
Index: src/Common/module.mk
===================================================================
--- src/Common/module.mk	(revision cdc4d434eaa8d5b4aeaf69a97a56f029f675cd09)
+++ src/Common/module.mk	(revision 982f95dc68c7956ead7dd0e4005088eaab1e2ad9)
@@ -10,7 +10,7 @@
 ## Author           : Richard C. Bilson
 ## Created On       : Mon Jun  1 17:49:17 2015
-## Last Modified By : Peter A. Buhr
-## Last Modified On : Tue Sep 27 11:06:38 2016
-## Update Count     : 4
+## Last Modified By : Aaron B. Moss
+## Last Modified On : Thu Jun 14 11:15:00 2018
+## Update Count     : 5
 ###############################################################################
 
@@ -20,3 +20,4 @@
        Common/GC.cc \
        Common/Assert.cc \
+       Common/InternedString.cc \
        Common/Heap.cc
