Implemented new resolve function

1 files changed, 219 insertions, 132 deletions

diff --git a/src/core/model/Node.hpp b/src/core/model/Node.hpp
index a637b56..97ec16f 100644
--- a/src/core/model/Node.hpp
+++ b/src/core/model/Node.hpp
@@ -16,14 +16,21 @@
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
+/**
+ * @file Node.hpp
+ *
+ * Contains the definition of the Node class, the base class used by all model
+ * classes.
+ *
+ * @author Andreas Stöckel (astoecke@techfak.uni-bielefeld.de)
+ */
+
 #ifndef _OUSIA_NODE_HPP_
 #define _OUSIA_NODE_HPP_
 
-#include <functional>
 #include <map>
 #include <string>
 #include <vector>
-#include <unordered_set>
 
 #include <core/common/Rtti.hpp>
 #include <core/managed/Managed.hpp>
@@ -34,48 +41,45 @@
 namespace ousia {
 
 /**
- * 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.
+ * Structure describing a single result obtained from the resolution function.
  */
-class Node : public Managed {
-public:
+struct ResolutionResult {
 	/**
-	 * 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.
-	 *
-	 * @param managed is the managed 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.
+	 * The actual node that was resolved.
 	 */
-	using Filter = bool (*)(Handle<Managed> managed, void *data);
+	Rooted<Node> node;
 
 	/**
-	 * Hash functional used to convert pairs of nodes and int to hashes which
-	 * can be used within a unordered_set.
+	 * Root node of the subtree in which the node was found. This e.g. points to
+	 * the Domain in which a Structure was defined or the Typesystem in which a
+	 * Type was defined. May be nullptr.
 	 */
-	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);
-		}
-	};
+	Rooted<Node> resolutionRoot;
 
 	/**
-	 * 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.
+	 * Default constructor of the ResolutionResult class.
+	 *
+	 * @param node is a reference pointing at the actually found node.
+	 * @param resolutionRoot is a reference to the root node of the subtree in
+	 * which the node was found.
 	 */
-	using VisitorSet =
-	    std::unordered_set<std::pair<const Node *, int>, VisitorHash>;
+	ResolutionResult(Handle<Node> node, Handle<Node> resolutionRoot)
+	    : node(node), resolutionRoot(resolutionRoot)
+	{
+	}
+};
+
+// Forward declaration
+struct ResolutionState;
 
+/**
+ * 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 Node : public Managed {
 private:
 	/**
 	 * Name of the node. As names are always looked up relative to a node,
@@ -97,29 +101,142 @@ private:
 	 */
 	void path(std::vector<std::string> &p) const;
 
+	/**
+	 * Returns true if the resolution process is just at the beginning (no part
+	 * of the path has been matched yet).
+	 *
+	 * @param state is used internally to manage the resolution process.
+	 */
+	static bool resolutionAtBeginning(ResolutionState &state);
+
+	/**
+	 * Method used internally for resolving nodes with a certain name and type
+	 * within the object graph.
+	 *
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if an matching element was found within this subtree, false
+	 * otherwise.
+	 * @return true if at least one new node has been found that matches the
+	 * criteria given for the resolution.
+	 */
+	bool resolve(ResolutionState &state);
+
+	/**
+	 * Method used internally to check whether the given index has an entry
+	 * which matches the one currently needed to continue the path.
+	 *
+	 * @param index is a reference to the index from which the currently active
+	 * path element should be looked up.
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if at least one new node has been found that matches the
+	 * criteria given for the resolution.
+	 */
+	bool continueResolveIndex(const Index &index, ResolutionState &state);
+
 protected:
 	/**
 	 * 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.
+	 * this function do not need to do anything but call the
+	 * continueResolveComposita() and/or continueResolveReferences() methods on
+	 * any index or list of references and pass the resolution state to these
+	 * methods.
+	 *
+	 * @param state is used internally to manage the resolution process.
+	 */
+	virtual void continueResolve(ResolutionState &state);
+
+	/**
+	 * Tries to advance the resolution process with the compositum pointed at
+	 * by h. If a part of the resolution path has already been matched, only
+	 * decends into the given node if the path can be continued. Otherwise
+	 * always decends into the node to search for potential beginnings of the
+	 * path.
+	 *
+	 * @param h is a handle at a compositum (a node the current node consists of
+	 * or explicitly defines).
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if at least one new node has been found that matches the
+	 * criteria given for the resolution.
+	 */
+	bool continueResolveCompositum(Handle<Node> h, ResolutionState &state);
+
+	/**
+	 * Calls continueResolveCompositum() for each element in the given
+	 * container.
+	 *
+	 * @param container is a container containing compositum nodes for which the
+	 * continueResolveCompositum() method should be called.
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if at least one new node has been found that matches the
+	 * criteria given for the resolution.
+	 */
+	template <class T>
+	bool continueResolveComposita(T &container, ResolutionState &state)
+	{
+		bool res = false;
+		for (auto elem : container) {
+			res = continueResolveCompositum(elem, state) | res;
+		}
+		return res;
+	}
+
+	/**
+	 * Calls continueResolveCompositum() for each element in the given
+	 * container. Uses the given index to speed up the resolution process.
+	 *
+	 * @param container is a container containing compositum nodes for which the
+	 * continueResolveCompositum() method should be called.
+	 * @param index is the Index instance of the given container and is used to
+	 * speed up the resolution process.
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if at least one new node has been found that matches the
+	 * criteria given for the resolution.
+	 */
+	template <class T>
+	bool continueResolveComposita(T &container, const Index &index,
+			ResolutionState &state)
+	{
+		if (continueResolveIndex(index, state)) {
+			return true;
+		} else if (resolutionAtBeginning(state)) {
+			return continueResolveComposita(container, state);
+		}
+		return false;
+	}
+
+	/**
+	 * Tries to search for the requested node in another subtree to which a
+	 * reference exists from this node. 
+	 *
+	 * @param h is a handle pointing at the node in the subtree.
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if at least one new node has been found that matches the
+	 * criteria given for the resolution.
+	 */
+	bool continueResolveReference(Handle<Node> h, ResolutionState &state);
+
+	/**
+	 * Tries to search for the requested node in another subtree to which a
+	 * reference exists from this node. 
 	 *
-	 * @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.
+	 * @param h is a handle pointing at the node in the subtree.
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if at least one new node has been found that matches the
+	 * criteria given for the resolution.
 	 */
-	virtual void doResolve(std::vector<Rooted<Managed>> &res,
-	                       const std::vector<std::string> &path, Filter filter,
-	                       void *filterData, unsigned idx, VisitorSet &visited);
+	template <class T>
+	bool continueResolveReferences(T &container, ResolutionState &state)
+	{
+		if (resolutionAtBeginning(state)) {
+			bool res = false;
+			for (auto elem : container) {
+				res = continueResolveReference(elem, state) | res;
+			}
+			return res;
+		}
+		return false;
+	}
 
 public:
 	/**
@@ -158,12 +275,7 @@ public:
 	/**
 	 * Returns the name of the node.
 	 */
-	std::string getName() const { return name; }
-
-	/**
-	 * Returns a reference to the name of the node.
-	 */
-	const std::string &getNameRef() const { return name; }
+	const std::string &getName() const { return name; }
 
 	/**
 	 * Specifies whether the node has a name, e.g. whether the current name is
@@ -206,94 +318,41 @@ public:
 	std::vector<std::string> path() const;
 
 	/**
-	 * Function which resolves a name path to a list of possible nodes.
-	 *
-	 * @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<Managed>> &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 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<Managed>> 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 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.
-	 */
-	std::vector<Rooted<Managed>> resolve(const std::vector<std::string> &path)
-	{
-		return resolve(path, nullptr, nullptr);
-	}
-
-	/**
-	 * Function which resolves a single name to a list of possible nodes
-	 * starting from this node.
-	 *
-	 * @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.
+	 * @param type specifies the type of the node that should be located.
+	 * @return a vector containing ResolutionResult structures which describe
+	 * the resolved elements.
 	 */
-	std::vector<Rooted<Managed>> resolve(const char *, Filter filter,
-	                                     void *filterData)
-	{
-		return resolve(std::vector<std::string>{name}, filter, filterData);
-	}
+	std::vector<ResolutionResult> resolve(const std::vector<std::string> &path,
+	                                      const RttiBase &type);
 
 	/**
 	 * Function which resolves a single name to a list of possible nodes
 	 * starting from this node.
 	 *
 	 * @param name is the name which should be resolved.
-	 * @return a vector containing all found node references.
+	 * @param type specifies the type of the node that should be located.
+	 * @return a vector containing ResolutionResult structures which describe
+	 * the resolved elements.
 	 */
-	std::vector<Rooted<Managed>> resolve(const std::string &name)
-	{
-		return resolve(std::vector<std::string>{name}, nullptr, nullptr);
-	}
+	std::vector<ResolutionResult> resolve(const std::string &name,
+	                                      const RttiBase &type);
 };
 
-// TODO: Use a different listener here for updating name maps
-
+/**
+ * The NodeVector class is a vector capable of automatically maintaining an
+ * index used for the resolution of node names.
+ *
+ * @tparam T is the type that should be stored in the NodeVector. Must be a
+ * descendant of the Node class.
+ * @tparam Listener is the listener class that should be used to build the
+ * internal index. Should either be Index or a reference to (&Index) in case a
+ * shared index is used.
+ */
 template <class T, class Listener = Index>
 class NodeVector
     : public ManagedGenericList<T, std::vector<Handle<T>>,
@@ -303,9 +362,29 @@ public:
 	                                ListAccessor<Handle<T>>, Listener>;
 	using Base::ManagedGenericList;
 
-	Index& getIndex() { return this->listener;}
+	/**
+	 * Returns the reference to the internal index.
+	 */
+	const Index &getIndex() const { return this->listener; }
+
+	/**
+	 * Returns the reference to the internal index.
+	 */
+	Index &getIndex() { return this->listener; }
+
 };
 
+/**
+ * The NodeMap class is a map class capable of automatically maintaining an
+ * index used for the resolution of node names.
+ *
+ * @tparam K is the key type that should be stored in the NodeMap.
+ * @tparam T is the value type that should be stored in the NodeMap. Must be a
+ * descendant of the Node class.
+ * @tparam Listener is the listener class that should be used to build the
+ * internal index. Should either be Index or a reference to (&Index) in case a
+ * shared index is used.
+ */
 template <class K, class T, class Listener = Index>
 class NodeMap
     : public ManagedGenericMap<K, T, std::map<K, Handle<T>>,
@@ -316,7 +395,15 @@ public:
 	                      MapAccessor<std::pair<K, Handle<T>>>, Listener>;
 	using Base::ManagedGenericMap;
 
-	Index& getIndex() { return this->listener;}
+	/**
+	 * Returns the reference to the internal index.
+	 */
+	const Index &getIndex() const { return this->listener; }
+
+	/**
+	 * Returns the reference to the internal index.
+	 */
+	Index &getIndex() { return this->listener; }
 };
 
 namespace RttiTypes {