Node.cpp and Node.hpp now containts the new Node base class (which always is a named node). Node instances implement the complex logic for being resolved with a path of names relative to another node

3 files changed, 216 insertions, 855 deletions

diff --git a/CMakeLists.txt b/CMakeLists.txt
index 73e2fb8..58fa742 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -97,6 +97,7 @@ ADD_DEFINITIONS(
 # ousia_script library (containing the bindings needed for script engines)
 ADD_LIBRARY(ousia_core
 	src/core/dom/Managed
+	src/core/dom/Node
 	src/core/script/Function
 	src/core/script/Object
 	src/core/script/ScriptEngine
diff --git a/src/core/dom/Node.cpp b/src/core/dom/Node.cpp
index cdf8137..df5bfcb 100644
--- a/src/core/dom/Node.cpp
+++ b/src/core/dom/Node.cpp
@@ -16,349 +16,76 @@
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
-#include <cassert>
-#include <queue>
-
 #include "Node.hpp"
 
 namespace ousia {
 namespace dom {
 
-/* Class NodeDescriptor */
+/* Class Node */
 
-int NodeDescriptor::refInCount() const
+void Node::path(std::vector<std::string> &p) const
 {
-	int res = 0;
-	for (const auto &e : refIn) {
-		res += e.second;
+	if (!isRoot()) {
+		parent->path(p);
 	}
-	return res + rootRefCount;
+	p.push_back(name);
 }
 
-int NodeDescriptor::refOutCount() const
+std::vector<std::string> Node::path() const
 {
-	int res = 0;
-	for (const auto &e : refOut) {
-		res += e.second;
-	}
+	std::vector<std::string> res;
+	path(res);
 	return res;
 }
 
-int NodeDescriptor::refInCount(Node *n) const
-{
-	if (n == nullptr) {
-		return rootRefCount;
-	}
-
-	const auto it = refIn.find(n);
-	if (it != refIn.cend()) {
-		return it->second;
-	}
-	return 0;
-}
-
-int NodeDescriptor::refOutCount(Node *n) const
-{
-	const auto it = refOut.find(n);
-	if (it != refOut.cend()) {
-		return it->second;
-	}
-	return 0;
-}
-
-void NodeDescriptor::incrNodeDegree(RefDir dir, Node *n)
+void Node::doResolve(std::vector<Rooted<Node>> &res,
+                     const std::vector<std::string> &path, Filter filter,
+                     void *filterData, unsigned idx, VisitorSet &visited)
 {
-	// If the given node is null it refers to an input rooted reference
-	if (n == nullptr) {
-		rootRefCount++;
-		return;
-	}
-
-	// Fetch a reference to either the input or the output reference map
-	auto &m = dir == RefDir::in ? refIn : refOut;
-
-	// Insert a new entry or increment the corresponding reference counter
-	auto it = m.find(n);
-	if (it == m.end()) {
-		m.emplace(std::make_pair(n, 1));
-	} else {
-		it->second++;
-	}
+	// Do nothing in the default implementation
 }
 
-bool NodeDescriptor::decrNodeDegree(RefDir dir, Node *n, bool all)
+int Node::resolve(std::vector<Rooted<Node>> &res,
+                   const std::vector<std::string> &path, Filter filter,
+                   void *filterData, unsigned idx, VisitorSet &visited,
+                   const std::string *alias)
 {
-	// If the given node is null it refers to an input rooted reference
-	if (n == nullptr) {
-		if (rootRefCount > 0) {
-			if (all) {
-				rootRefCount = 0;
-			} else {
-				rootRefCount--;
+	// Abort if this node was already visited for this path index
+	std::pair<const Node *, int> recKey = std::make_pair(this, idx);
+	if (visited.find(recKey) != visited.end()) {
+		return res.size();
+	}
+	visited.insert(recKey);
+
+	// Check whether the we can continue the path
+	if (path[idx] == name || (alias && *alias == name)) {
+		// If we have reached the end of the path and the node is successfully
+		// tested by the filter function, add it to the result. Otherwise
+		// continue searching along the path
+		if (idx + 1 == path.size()) {
+			if (!filter || filter(this, filterData)) {
+				res.push_back(this);
 			}
-			return true;
+		} else {
+			doResolve(res, path, filter, filterData, idx + 1, visited);
 		}
-		return false;
 	}
 
-	// Fetch a reference to either the input or the output reference map
-	auto &m = dir == RefDir::in ? refIn : refOut;
+	// Restart the search from here in order to find all possible nodes that can
+	// be matched to the given path
+	doResolve(res, path, filter, filterData, 0, visited);
 
-	// Decrement corresponding reference counter, delete the entry if the
-	// reference counter reaches zero
-	auto it = m.find(n);
-	if (it != m.end()) {
-		it->second--;
-		if (it->second == 0 || all) {
-			m.erase(it);
-		}
-		return true;
-	}
-	return false;
+	return res.size();
 }
 
-/* Class NodeManager */
-
-/**
- * The ScopedIncrement class is used by the NodeManager to safely increment a
- * variable when a scope is entered and to decrement it when the scope is left.
- */
-class ScopedIncrement {
-private:
-	/**
-	 * Reference to the variable that should be incremented.
-	 */
-	int &i;
-
-public:
-	/**
-	 * Constructor of ScopedIncrement. Increments the given variable.
-	 *
-	 * @param i is the variable that should be incremented.
-	 */
-	ScopedIncrement(int &i) : i(i) { i++; }
-
-	/**
-	 * Destructor of ScopedIncrement. Decrements the referenced variable.
-	 */
-	~ScopedIncrement() { i--; }
-};
-
-NodeManager::~NodeManager()
+std::vector<Rooted<Node>> Node::resolve(const std::vector<std::string> &path,
+                                        Filter filter = nullptr,
+                                        void *filterData = nullptr)
 {
-	// Perform a final sweep
-	sweep();
-
-	// All nodes should have been deleted!
-	assert(nodes.empty());
-
-	// Free all nodes managed by the node manager (we'll get here if assertions
-	// are disabled)
-	if (!nodes.empty()) {
-		ScopedIncrement incr{deletionRecursionDepth};
-		for (auto &e : nodes) {
-			delete e.first;
-		}
-	}
-}
-
-NodeDescriptor *NodeManager::getDescriptor(Node *n)
-{
-	if (n) {
-		auto it = nodes.find(n);
-		if (it != nodes.end()) {
-			return &(it->second);
-		}
-	}
-	return nullptr;
-}
-
-void NodeManager::registerNode(Node *n)
-{
-	nodes.emplace(std::make_pair(n, NodeDescriptor{}));
-}
-
-void NodeManager::addRef(Node *tar, Node *src)
-{
-	// Fetch the node descriptors for the two nodes
-	NodeDescriptor *dTar = getDescriptor(tar);
-	NodeDescriptor *dSrc = getDescriptor(src);
-
-	// Store the tar <- src reference
-	assert(dTar);
-	dTar->incrNodeDegree(RefDir::in, src);
-	if (src) {
-		// Store the src -> tar reference
-		assert(dSrc);
-		dSrc->incrNodeDegree(RefDir::out, tar);
-	} else {
-		// We have just added a root reference, remove the element from the
-		// list of marked nodes
-		marked.erase(tar);
-	}
-}
-
-void NodeManager::deleteRef(Node *tar, Node *src, bool all)
-{
-	// Fetch the node descriptors for the two nodes
-	NodeDescriptor *dTar = getDescriptor(tar);
-	NodeDescriptor *dSrc = getDescriptor(src);
-
-	// Decrement the output degree of the source node first
-	if (dSrc) {
-		dSrc->decrNodeDegree(RefDir::out, tar, all);
-	}
-
-	// Decrement the input degree of the input node
-	if (dTar && dTar->decrNodeDegree(RefDir::in, src, all)) {
-		// If the node has a zero in degree, it can be safely deleted, otherwise
-		// if it has no root reference, add it to the "marked" set which is
-		// subject to tracing garbage collection
-		if (dTar->refInCount() == 0) {
-			deleteNode(tar, dTar);
-		} else if (dTar->rootRefCount == 0) {
-			// Insert the node into the list of nodes to be inspected by garbage
-			// collection
-			marked.insert(tar);
-		}
-	}
-
-	// Call the tracing garbage collector if the marked size is larger than the
-	// actual value
-	if (marked.size() >= threshold) {
-		sweep();
-	}
-}
-
-void NodeManager::deleteNode(Node *n, NodeDescriptor *descr)
-{
-	// Abort if the node already is on the "deleted" list
-	if (deleted.find(n) != deleted.end()) {
-		return;
-	}
-
-	// Increment the recursion depth counter. The "deleteRef" function called
-	// below
-	// may descend further into this function and the actual deletion should be
-	// done in a single step.
-	{
-		ScopedIncrement incr{deletionRecursionDepth};
-
-		// Add the node to the "deleted" set
-		deleted.insert(n);
-
-		// Remove all output references of this node
-		while (!descr->refOut.empty()) {
-			deleteRef(descr->refOut.begin()->first, n, true);
-		}
-
-		// Remove the node from the "marked" set
-		marked.erase(n);
-	}
-
-	purgeDeleted();
-}
-
-void NodeManager::purgeDeleted()
-{
-	// Perform the actual deletion if the recursion level is zero
-	if (deletionRecursionDepth == 0 && !deleted.empty()) {
-		// Increment the recursion depth so this function does not get called
-		// again while deleting nodes
-		ScopedIncrement incr{deletionRecursionDepth};
-
-		// Deleting nodes might add new nodes to the deleted list, thus the
-		// iterator would get invalid and we have to use this awkward
-		// construction
-		while (!deleted.empty()) {
-			auto it = deleted.begin();
-			Node *n = *it;
-			deleted.erase(it);
-			marked.erase(n);
-			nodes.erase(n);
-			delete n;
-		}
-	}
-}
-
-void NodeManager::sweep()
-{
-	// Only execute sweep on the highest recursion level
-	if (deletionRecursionDepth > 0) {
-		return;
-	}
-
-	// Set containing nodes which are reachable from a rooted node
-	std::unordered_set<Node *> reachable;
-
-	// Deletion of nodes may cause other nodes to be added to the "marked" list
-	// so we repeat this process until nodes are no longer deleted
-	while (!marked.empty()) {
-		// Repeat until all nodes in the "marked" list have been visited
-		while (!marked.empty()) {
-			// Increment the deletionRecursionDepth counter to prevent deletion
-			// of nodes while sweep is running
-			ScopedIncrement incr{deletionRecursionDepth};
-
-			// Fetch the next node in the "marked" list and remove it
-			Node *curNode = *(marked.begin());
-
-			// Perform a breadth-first search starting from the current node
-			bool isReachable = false;
-			std::unordered_set<Node *> visited{{curNode}};
-			std::queue<Node *> queue{{curNode}};
-			while (!queue.empty() && !isReachable) {
-				// Pop the next element from the queue, remove the element from
-				// the marked list as we obviously have evaluated it
-				curNode = queue.front();
-				queue.pop();
-				marked.erase(curNode);
-
-				// Fetch the node descriptor
-				NodeDescriptor *descr = getDescriptor(curNode);
-				if (!descr) {
-					continue;
-				}
-
-				// If this node is rooted, the complete visited subgraph is
-				// rooted
-				if (descr->rootRefCount > 0) {
-					isReachable = true;
-					break;
-				}
-
-				// Iterate over all nodes leading to the current one
-				for (auto &src : descr->refIn) {
-					Node *srcNode = src.first;
-
-					// Abort if the node already in the reachable list,
-					// otherwise add the node to the queue if it was not visited
-					if (reachable.find(srcNode) != reachable.end()) {
-						isReachable = true;
-						break;
-					} else if (visited.find(srcNode) == visited.end()) {
-						visited.insert(srcNode);
-						queue.push(srcNode);
-					}
-				}
-			}
-
-			// Insert the nodes into the list of to be deleted nodes or
-			// reachable nodes depending on the "isReachable" flag
-			if (isReachable) {
-				for (auto n : visited) {
-					reachable.insert(n);
-				}
-			} else {
-				for (auto n : visited) {
-					deleteNode(n, getDescriptor(n));
-				}
-			}
-		}
-
-		// Now purge all nodes marked for deletion
-		purgeDeleted();
-	}
+	std::vector<Rooted<Node>> res;
+	VisitorSet visited;
+	resolve(res, path, filter, filterData, 0, visited, nullptr);
+	return res;
 }
 }
 }
diff --git a/src/core/dom/Node.hpp b/src/core/dom/Node.hpp
index 10572e7..571eedd 100644
--- a/src/core/dom/Node.hpp
+++ b/src/core/dom/Node.hpp
@@ -19,632 +19,265 @@
 #ifndef _OUSIA_DOM_NODE_HPP_
 #define _OUSIA_DOM_NODE_HPP_
 
-#include <iostream>
-#include <map>
-#include <type_traits>
-#include <unordered_map>
+#include <string>
+#include <vector>
+#include <functional>
 #include <unordered_set>
 
+#include "Managed.hpp"
+
 namespace ousia {
 namespace dom {
 
-class Node;
-
-template <class T>
-class Handle;
-
-template <class T>
-class Rooted;
-
-template <class T>
-class Owned;
-
-/**
- * Enum used for specifying the Reference direction.
- */
-enum class RefDir { in, out };
-
 /**
- * The NodeDescriptor class is used by the NodeManager for reference counting
- * and garbage collection. It describes the node reference multi graph with
- * adjacency lists.
+ * The Node class builds the base class for any Node within the DOM graph. A
+ * node may either be a descriptive node (such as a domain description etc.)
+ * or a document element. Each node is identified by acharacteristic name and
+ * a parent element. Note that the node name is not required to be unique. Nodes
+ * without parent are considered root nodes.
  */
-class NodeDescriptor {
+class Node : public Managed {
 public:
 	/**
-	 * Contains the number of references to rooted handles. A node whith at
-	 * least one rooted reference is considered reachable.
-	 */
-	int rootRefCount;
-
-	/**
-	 * Map containing all references pointing at this node. The map key
-	 * describes the node which points at this node, the map value contains the
-	 * reference count from this node.
-	 */
-	std::map<Node *, int> refIn;
-
-	/**
-	 * Map containing all references pointing from this node at other nodes. The
-	 * map key describes the target node and the map value the reference count.
-	 */
-	std::map<Node *, int> refOut;
-
-	/**
-	 * Default constructor of the NodeDescriptor class.
-	 */
-	NodeDescriptor() : rootRefCount(0){};
-
-	/**
-	 * Returns the total input degree of this node. The root references are also
-	 * counted as incomming references and thus added to the result.
+	 * The Filter function is used when resolving names to Node instances. The
+	 * filter tests whether the given node meets the requirements for inclusion
+	 * in the result list.
 	 *
-	 * @return the input degree of this node, including the root references.
+	 * @param node is the node which should be tested.
+	 * @param data is user-defined data passed to the filter.
+	 * @return true if the node should be included in the result set, false
+	 * otherwise.
 	 */
-	int refInCount() const;
+	using Filter = bool (*)(Handle<Node> node, void *data);
 
 	/**
-	 * Returns the total output degree of this node.
-	 *
-	 * @return the output degree of this node.
+	 * Hash functional used to convert pairs of nodes and int to hashes which
+	 * can be used within a unordered_set.
 	 */
-	int refOutCount() const;
+	struct VisitorHash {
+		size_t operator()(const std::pair<const Node *, int> &p) const
+		{
+			const std::hash<const Node *> nodeHash;
+			const std::hash<int> intHash;
+			return nodeHash(p.first) + 37 * intHash(p.second);
+		}
+	};
 
 	/**
-	 * Returns the input degree for the given node.
-	 *
-	 * @param n is the node for which the input degree should be returned,
-	 * nullptr if the number of root references is returned.
-	 * @return the input degree of the node or the rootRefCount if nullptr is
-	 * given as node. If the node is not found, zero is returned.
+	 * Alias for the VisitorSet class which represents all nodes which have been
+	 * visited in the name resolution process. The map stores pairs of node
+	 * pointers and integers, indicating for which path start id the node has
+	 * already been visited.
 	 */
-	int refInCount(Node *n) const;
+	using VisitorSet =
+	    std::unordered_set<std::pair<const Node *, int>, VisitorHash>;
 
+private:
 	/**
-	 * Returns the output degree for the given node.
-	 *
-	 * @param n is the node for which the output degree should be returned.
-	 * @return the output degree of the node. If the node is not found, zero is
-	 * returned.
+	 * Name of the node. As names are always looked up relative to a node,
+	 * names are not required to be unique.
 	 */
-	int refOutCount(Node *n) const;
+	std::string name;
 
 	/**
-	 * Increments the input or output degree for the given node.
-	 *
-	 * @param dir is "in", increments the input degree, otherwise increments the
-	 * output degree.
-	 * @param n is the node for which the input or output degree should be
-	 * incremented. If the given node is null, the rootRefCount is incremented,
-	 * independent of the in parameter.
+	 * Reference to a parent node instace.
 	 */
-	void incrNodeDegree(RefDir dir, Node *n);
+	Owned<Node> parent;
 
 	/**
-	 * Decrements the input or output degree for the given node.
+	 * Private version of the "path" function used to construct the path. Calls
+	 * the path function of the parent node and adds the own name to the given
+	 * vector.
 	 *
-	 * @param dir is "in", decrements the input degree, otherwise decrements the
-	 * output degree.
-	 * @param n is the node for which the input or output degree should be
-	 * decremented. If the given node is null, the rootRefCount is decremented,
-	 * independent of the in parameter.
-	 * @param all specifies whether the node degree of the reference to this
-	 * node should be set to zero, no matter what the actual degree is. This
-	 * is set to true, when the given node is deleted and all references to it
-	 * should be purged, no matter what.
-	 * @return true if the node degree was sucessfully decremented.
+	 * @param p is the list the path should be constructed in.
 	 */
-	bool decrNodeDegree(RefDir dir, Node *n, bool all = false);
-};
+	void path(std::vector<std::string> &p) const;
 
-/**
- * Default sweep threshold used in the node manager. If the number of nodes
- * marked for sweeping reaches this threshold a garbage collection sweep is
- * performed.
- */
-constexpr size_t NODE_MANAGER_SWEEP_THRESHOLD = 128;
-
-class NodeManager {
 protected:
 	/**
-	 * Threshold that defines the minimum number of entries in the "marked"
-	 * set until "sweep" is called.
-	 */
-	const size_t threshold;
-
-	/**
-	 * Map used to store the node descriptors for all managed nodes. Every node
-	 * that has at least one root, in or out reference has an entry in this map.
-	 */
-	std::unordered_map<Node *, NodeDescriptor> nodes;
-
-	/**
-	 * Set containing the nodes marked for sweeping.
-	 */
-	std::unordered_set<Node *> marked;
-
-	/**
-	 * Set containing nodes marked for deletion.
-	 */
-	std::unordered_set<Node *> deleted;
-
-	/**
-	 * Recursion depth while performing deletion. This variable is needed
-	 * because the deletion of a node may cause further nodes to be deleted.
-	 * Yet the actual deletion should only be performed at the uppermost
-	 * recursion level.
-	 */
-	int deletionRecursionDepth = 0;
-
-	/**
-	 * Returns the node descriptor for the given node from the nodes map.
-	 * Creates it if it does not exist and the "create" parameter is set to
-	 * true.
-	 */
-	NodeDescriptor *getDescriptor(Node *n);
-
-	/**
-	 * Purges the nodes in the "deleted" set.
-	 */
-	void purgeDeleted();
-
-	/**
-	 * Function used internally to delete a node and clean up all references in
-	 * the node manager still pointing at it.
-	 *
-	 * @param n is the node that should be deleted.
-	 * @param
-	 */
-	void deleteNode(Node *n, NodeDescriptor *descr);
-
-	/**
-	 * Internal version of the deleteRef function with an additional "all"
-	 * parameter. Removes a reference to the given target node from the source
-	 * node.
-	 *
-	 * @param tar is the target node for which the reference from the given
-	 * source node should be removed.
-	 * @param src is the source node from which the target node was referenced
-	 * or nullptr if the target node is referenced from the local scope.
-	 * @param all specifies whether all (src, tar) references should be deleted,
-	 * independent of the actual cardinality. This is set to true, when the
-	 * given node is deleted and all references to it should be purged, no
-	 * matter what.
-	 */
-	void deleteRef(Node *tar, Node *src, bool all);
-
-public:
-	NodeManager() : threshold(NODE_MANAGER_SWEEP_THRESHOLD) {}
-
-	NodeManager(size_t threshold) : threshold(threshold) {}
-
-	/**
-	 * Deletes all nodes which are managed by this class.
-	 */
-	~NodeManager();
-
-	/**
-	 * Registers a node for being used with the NodeManager.
+	 * Function which should be overwritten by derived classes in order to
+	 * resolve node names to a list of possible nodes. The implementations of
+	 * this function do not need to do anything but call the "resovle" function
+	 * of any child instance of NamedNode.
 	 *
-	 * @param n is the node which is registered for being used with the
-	 * NodeManager.
-	 */
-	void registerNode(Node *n);
-
-	/**
-	 * Stores a reference to the given target node from the given source node.
-	 * If the source pointer is set to nullptr, this means that the target node
-	 * is rooted (semantic: it is reachable from the current scope) and should
-	 * not be collected.
-	 *
-	 * @param tar is the target node to which the reference from src should be
-	 * stored.
-	 * @param src is the source node from which the target node is referenced or
-	 * nullptr if the target node is referenced from the local scope.
-	 */
-	void addRef(Node *tar, Node *src);
-
-	/**
-	 * Removes a reference to the given target node from the source node.
-	 *
-	 * @param tar is the target node for which the reference from the given
-	 * source node should be removed.
-	 * @param src is the source node from which the target node was referenced
-	 * or nullptr if the target node is referenced from the local scope.
-	 */
-	void deleteRef(Node *tar, Node *src) { deleteRef(tar, src, false); }
-
-	/**
-	 * Performs garbage collection.
-	 */
-	void sweep();
-};
-
-/**
- * The Node class builds the main class in the DOM graph. The Node class
- * instances are managed by a NodeManager which performs garbage collection of
- * the Node instances. Do not pass raw Node pointers around, always wrap them
- * inside a Rooted or Owned class.
- */
-class Node {
-protected:
-	NodeManager &mgr;
-
-public:
-	Node(NodeManager &mgr) : mgr(mgr) { mgr.registerNode(this); };
-
-	virtual ~Node(){};
-
-	NodeManager &getManager() { return mgr; }
-
-	template <class T>
-	Owned<T> acquire(const Handle<T> &h)
-	{
-		return Owned<T>{h, this};
-	}
-
-	template <class T>
-	Owned<T> acquire(Handle<T> &&h)
-	{
-		return Owned<T>{h, this};
-	}
-
-	template <class T>
-	Owned<T> acquire(T *t)
-	{
-		return Owned<T>{t, this};
-	}
-};
-
-template <class T>
-class Handle {
-protected:
-	friend class Rooted<T>;
-	friend class Owned<T>;
-
-	static_assert(std::is_base_of<Node, T>::value, "T must be a Node");
-
-	/**
-	 * Reference to the represented node.
-	 */
-	T *ptr;
+	 * @param res is the result list containing all possible nodes matching the
+	 * name specified in the path.
+	 * @param path is a list specifying a path of node names which is meant to
+	 * specify a certain named node.
+	 * @param idx is the current index in the path.
+	 * @param visited is a map which is used to prevent unwanted recursion.
+	 * @param filter is a callback function which may check whether a certain
+	 * node should be in the result set. If nullptr is given, all nodes matching
+	 * the path are included. The filter function can be used to restrict the
+	 * type of matched functions.
+	 * @param filterData is user-defined data that should be passed to the
+	 * filter.
+	 */
+	virtual void doResolve(std::vector<Rooted<Node>> &res,
+	                       const std::vector<std::string> &path, Filter filter,
+	                       void *filterData, unsigned idx, VisitorSet &visited);
 
 public:
 	/**
-	 * Constructor of the base Owned class.
+	 * Initializes the node with empty name and parent.
 	 *
-	 * @param ptr is the pointer to the node the Owned should represent.
+	 * @param mgr is a reference to the Manager instace the node belongs to.
 	 */
-	Handle(T *ptr) : ptr(ptr) {}
+	Node(Manager &mgr) : Managed(mgr) {}
 
 	/**
-	 * Copies the given Handle to this Handle instance.
+	 * Constructs a new node with the given name and the given parent element.
 	 *
-	 * @param h is the Handle that should be asigned to this instance.
-	 */
-	Handle(const Handle<T> &h) : ptr(h.get()) {}
-
-	/**
-	 * Copies the given Handle for a derived class to this Handle instance.
-	 *
-	 * @param h is the Handle that should be asigned to this instance.
-	 */
-	template <class T2>
-	Handle(const Handle<T2> &h)
-	    : ptr(h.get())
-	{
-	}
-
-	/**
-	 * Returns the underlying pointer.
-	 */
-	T *get() const { return ptr; }
-
-	/**
-	 * Provides access to the underlying node.
-	 */
-	T *operator->() { return ptr; }
-
-	/**
-	 * Provides access to the underlying node.
-	 */
-	T &operator*() { return *ptr; }
-
-	/**
-	 * Comparison operator between base Owned and base Owned.
-	 */
-	bool operator==(const Handle &h) const { return ptr == h.ptr; }
-
-	/**
-	 * Comparison operator between base Owned and pointer.
-	 */
-	friend bool operator==(const Handle &h, const Node *n)
-	{
-		return h.ptr == n;
-	}
-
-	/**
-	 * Comparison operator between base Owned and pointer.
-	 */
-	friend bool operator==(const Node *n, const Handle &h)
-	{
-		return h.ptr == n;
-	}
-
-	/**
-	 * Returns true if the handle is the null pointer.
-	 */
-	bool isNull() const { return ptr == nullptr; }
-
-	/**
-	 * Returns true if the handle is the null pointer.
+	 * @param mgr is a reference to the Manager instace the node belongs to.
+	 * @param name is the name of the Node.
+	 * @param parent is a handle pointing at the parent node.
 	 */
-	bool operator!() const { return isNull(); }
-};
-
-/**
- * Null represents a null handle.
- */
-static const Handle<Node> Null{nullptr};
-
-/**
- * A Rooted represents a directed, garbage collected pointer at a Node
- * instance. The lifetime of the represented node is guaranteed to be at least
- * as long as the lifetime of the Rooted instance.
- */
-template <class T>
-class Rooted : public Handle<T> {
-private:
-	void addRef()
+	Node(Manager &mgr, std::string name, Handle<Node> parent = Null)
+	    : Managed(mgr), name(name), parent(acquire(parent))
 	{
-		if (Handle<T>::ptr) {
-			Handle<T>::ptr->getManager().addRef(Handle<T>::ptr, nullptr);
-		}
-	}
-
-	void deleteRef()
-	{
-		if (Handle<T>::ptr) {
-			Handle<T>::ptr->getManager().deleteRef(Handle<T>::ptr, nullptr);
-		}
 	}
 
-public:
-	/**
-	 * Creates an empty Owned.
-	 */
-	Rooted() : Handle<T>(nullptr){};
-
 	/**
-	 * Copies the given Rooted to this Rooted instance. Both handles
-	 * are indistinguishable after the operation.
+	 * Sets the name of the node to the given name. Note: The name set here may
+	 * be invalid (contain spaces, colons or other special characters). However,
+	 * in this case the node will not be reachable as reference from a input
+	 * document. This behaviour allows for gracefully degradation in error
+	 * cases.
 	 *
-	 * @param h is the Owned that should be asigned to this instance.
+	 * @param name is the name that should be assigned to the node.
 	 */
-	Rooted(const Rooted<T> &h) : Handle<T>(h.ptr) { addRef(); }
+	void setName(std::string name) { this->name = std::move(name); }
 
 	/**
-	 * Move constructor. Moves the given rvalue Rooted to this instance.
-	 *
-	 * @param h is the Rooted to be moved to this instance.
-	 */
-	Rooted(Rooted<T> &&h) : Handle<T>(h.ptr) { h.ptr = nullptr; }
-
-	/**
-	 * Constructor of the Owned class.
-	 *
-	 * @param ptr is the node the Owned should represent.
-	 */
-	Rooted(T *ptr) : Handle<T>(ptr) { addRef(); }
-
-	/**
-	 * Constructor of the Owned class.
-	 *
-	 * @param h is another Owned whose Node should be used.
+	 * Returns the name of the node.
 	 */
-	template <class T2>
-	Rooted(const Handle<T2> &h)
-	    : Handle<T>(h.get())
-	{
-		addRef();
-	}
+	std::string getName() const { return name; }
 
 	/**
-	 * Assignment operator. Assigns the given Owned to this Owned instance.
-	 * Both handles are indistinguishable after the operation.
+	 * Specifies whether the node has a name, e.g. whether the current name is
+	 * not empty.
 	 *
-	 * @param h is the Owned that should be asigned to this instance.
+	 * @return true if the name of this node is not empty, false otherwise.
 	 */
-	Rooted<T> &operator=(const Rooted<T> &h)
-	{
-		deleteRef();
-		this->ptr = h.ptr;
-		addRef();
-		return *this;
-	}
+	bool hasName() const { return !name.empty(); }
 
 	/**
-	 * Move assignment operator. Moves the given rvalue Owned into this
-	 * instance.
+	 * Sets the parent node.
 	 *
-	 * @param h is the Owned to be moved to this instance.
+	 * @param parent is a Handle to the parent node.
 	 */
-	Rooted<T> &operator=(Rooted<T> &&h)
-	{
-		deleteRef();
-		this->ptr = h.ptr;
-		h.ptr = nullptr;
-		return *this;
-	}
+	void setParent(Handle<Node> parent) { this->parent = acquire(parent); }
 
 	/**
-	 * Assignment operator. Assigns the given Owned to this Owned instance.
-	 * Both handles are indistinguishable after the operation.
+	 * Returns a handle to the parent node of the Node instance.
 	 *
-	 * @param h is the Owned that should be asigned to this instance.
+	 * @return a handle to the root node.
 	 */
-	template <class T2>
-	Rooted<T> &operator=(const Handle<T2> &h)
-	{
-		deleteRef();
-		this->ptr = h.get();
-		addRef();
-		return *this;
-	}
+	Rooted<Node> getParent() const { return parent; }
 
 	/**
-	 * Move assignment operator. Moves the given rvalue Owned into this
-	 * instance.
+	 * Returns true, if the node does not have a parent. Root nodes may either
+	 * be the root element of the complete DOM tree
 	 *
-	 * @param h is the Owned to be moved to this instance.
-	 */
-	Rooted<T> &operator=(Handle<T> &&h)
-	{
-		deleteRef();
-		this->ptr = h.ptr;
-		h.ptr = nullptr;
-		return *this;
-	}
-
-	/**
-	 * Destructor of the Rooted class, deletes all refrences the class is
-	 * still holding.
-	 */
-	~Rooted() { deleteRef(); }
-};
-
-/**
- * The Owned class represents a directed, garbage collected pointer at a Node
- * instance. The lifetime of the represented node is guaranteed to be at last
- * as long as the lifetime of the Node instance which owns this reference.
- */
-template <class T>
-class Owned : public Handle<T> {
-private:
-	Node *owner;
-
-	void addRef()
-	{
-		if (Handle<T>::ptr && owner) {
-			owner->getManager().addRef(Handle<T>::ptr, owner);
-		}
-	}
-
-	void deleteRef()
-	{
-		if (Handle<T>::ptr && owner) {
-			owner->getManager().deleteRef(Handle<T>::ptr, owner);
-		}
-	}
-
-public:
-	/**
-	 * Creates an empty Owned.
+	 * @return true if the node is a root node (has no parent) or false if the
+	 * node is no root node (has a parent).
 	 */
-	Owned() : Handle<T>(nullptr), owner(nullptr){};
+	bool isRoot() const { return parent.isNull(); }
 
 	/**
-	 * Copies the given Owned to this Owned instance. Both handles are
-	 * indistinguishable after the operation. Note that especially the Owned
-	 * owner is copied.
+	 * Returns the vector containing the complete path to this node (including
+	 * the name of the parent nodes).
 	 *
-	 * @param h is the Owned that should be asigned to this instance.
+	 * @return a vector containing the path (starting with the root node) to
+	 * this node as a list of names.
 	 */
-	Owned(const Owned<T> &h) : Handle<T>(h.get()), owner(h.getOwner())
-	{
-		addRef();
-	}
+	std::vector<std::string> path() const;
 
 	/**
-	 * Copies the given Owned of another derived type to this Owned instance.
-	 * Both handles are indistinguishable after the operation (except for the
-	 * type). Note that especially the Owned owner is copied.
+	 * Function which resolves a name path to a list of possible nodes.
 	 *
-	 * @param h is the Owned that should be asigned to this instance.
-	 */
-	template <class T2>
-	Owned(const Owned<T2> &h)
-	    : Handle<T>(h.get()), owner(h.getOwner())
-	{
-		addRef();
-	}
-
-	/**
-	 * Move constructor. Moves the given rvalue Owned to this instance.
+	 * @param res is the result list containing all possible nodes matching the
+	 * name specified in the path.
+	 * @param path is a list specifying a path of node names which is meant to
+	 * specify a certain named node.
+	 * @param filter is a callback function which may check whether a certain
+	 * node should be in the result set. If nullptr is given, all nodes matching
+	 * the path are included. The filter function can be used to restrict the
+	 * type of matched functions.
+	 * @param filterData is user-defined data that should be passed to the
+	 * filter.
+	 * @param idx is the current index in the path.
+	 * @param visited is a map which is used to prevent unwanted recursion.
+	 * @param alias is a pointer at a string which contains an alternative name
+	 * for this node. If nullptr is given, not such alternative name is
+	 * provided.
+	 * @return the number of elements in the result list.
+	 */
+	int resolve(std::vector<Rooted<Node>> &res,
+	            const std::vector<std::string> &path, Filter filter,
+	            void *filterData, unsigned idx, VisitorSet &visited,
+	            const std::string *alias);
+
+	/**
+	 * Function which resolves a name path to a list of possible nodes starting
+	 * from this node.
 	 *
-	 * @param h is the Owned to be moved to this instance.
-	 */
-	Owned(Owned<T> &&h) : Handle<T>(h.get()), owner(h.getOwner())
-	{
-		h.ptr = nullptr;
-	}
-
-	/**
-	 * Assignment operator. Assigns the given Owned to this Owned instance.
-	 * Both handles are indistinguishable after the operation. Note that
-	 * especially the Owned owner is copied.
+	 * @param path is a list specifying a path of node names meant to specify a
+	 * certain named node.
+	 * @param filter is a callback function which may check whether a certain
+	 * node should be in the result set. If nullptr is given, all nodes matching
+	 * the path are included. The filter function can e.g. be used to restrict
+	 * the type of matched functions.
+	 * @param filterData is user-defined data that should be passed to the
+	 * filter.
+	 * @return a vector containing all found node references.
+	 */
+	std::vector<Rooted<Node>> resolve(const std::vector<std::string> &path,
+	                                  Filter filter, void *filterData);
+
+	/**
+	 * Function which resolves a name path to a list of possible nodes starting
+	 * from this node.
 	 *
-	 * @param h is the Owned that should be asigned to this instance.
+	 * @param path is a list specifying a path of node names meant to specify a
+	 * certain named node.
+	 * @return a vector containing all found node references.
 	 */
-	Owned<T> &operator=(const Owned<T> &h)
+	std::vector<Rooted<Node>> resolve(const std::vector<std::string> &path)
 	{
-		deleteRef();
-		this->ptr = h.ptr;
-		this->owner = h.getOwner();
-		addRef();
-		return *this;
+		return resolve(path, nullptr, nullptr);
 	}
 
 	/**
-	 * Move assignment operator. Moves the given rvalue Owned into this
-	 * instance.
+	 * Function which resolves a single name to a list of possible nodes
+	 * starting from this node.
 	 *
-	 * @param h is the Owned to be moved to this instance.
-	 */
-	Owned<T> &operator=(Owned<T> &&h)
+	 * @param name is the name which should be resolved.
+	 * @param filter is a callback function which may check whether a certain
+	 * node should be in the result set. If nullptr is given, all nodes matching
+	 * the path are included. The filter function can e.g. be used to restrict
+	 * the type of matched functions.
+	 * @param filterData is user-defined data that should be passed to the
+	 * filter.
+	 * @return a vector containing all found node references.
+	 */
+	std::vector<Rooted<Node>> resolve(const char *, Filter filter,
+	                                  void *filterData)
 	{
-		deleteRef();
-		this->ptr = h.ptr;
-		this->owner = h.getOwner();
-		h.ptr = nullptr;
-		return *this;
+		return resolve(std::vector<std::string>{name}, filter, filterData);
 	}
 
 	/**
-	 * Constructor of the Owned class.
+	 * Function which resolves a single name to a list of possible nodes
+	 * starting from this node.
 	 *
-	 * @param ptr is the node the Owned should represent.
-	 * @param owner is the node which owns this Owned instance. The ptr node
-	 * is guaranteed to live at least as long as the owner.
+	 * @param name is the name which should be resolved.
+	 * @return a vector containing all found node references.
 	 */
-	Owned(T *ptr, Node *owner) : Handle<T>(ptr), owner(owner) { addRef(); }
-
-	/**
-	 * Constructor of the Owned class.
-	 *
-	 * @param h is another Owned whose Node should be used.
-	 * @param owner is the node which owns this Owned instance. The ptr node
-	 * is guaranteed to live at least as long as the owner.
-	 */
-	template <class T2>
-	Owned(const Handle<T2> &h, Node *owner)
-	    : Handle<T>(h.get()), owner(owner)
+	std::vector<Rooted<Node>> resolve(const std::string &name)
 	{
-		addRef();
+		return resolve(std::vector<std::string>{name}, nullptr, nullptr);
 	}
-
-	/**
-	 * Destructor of the Owned class, deletes all refrences the class is still
-	 * holding.
-	 */
-	~Owned() { deleteRef(); }
-
-	/**
-	 * Returns the reference to the owner of the Owned.
-	 *
-	 * @return the Owned owner.
-	 */
-	Node *getOwner() const { return owner; }
 };
 }
 }