Finished node resolution process

2 files changed, 116 insertions, 43 deletions

diff --git a/src/core/model/Node.cpp b/src/core/model/Node.cpp
index 518a74d..d12e92b 100644
--- a/src/core/model/Node.cpp
+++ b/src/core/model/Node.cpp
@@ -16,6 +16,8 @@
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
+#include <iostream>
+
 #include <functional>
 #include <unordered_set>
 
@@ -28,12 +30,33 @@ namespace ousia {
 /* Class SharedResolutionState */
 
 /**
+ * Hash functional used to convert pairs of nodes and int to hashes which
+ * can be used within a unordered_set.
+ */
+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);
+	}
+};
+
+/**
+ * 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 index the node has already
+ * been visited.
+ */
+using VisitorSet =
+    std::unordered_set<std::pair<const Node *, int>, VisitorHash>;
+
+/**
  * The SharedResolutionState structure represents the state that is shared
  * between all resolution paths. A reference to a per-resolution-global
  * SharedResolutionState instance is stored in the ResolutionState class.
  */
 class SharedResolutionState {
-
 public:
 	/**
 	 * Actual path (name pattern) that was requested for resolution.
@@ -48,7 +71,7 @@ public:
 	/**
 	 * Tracks all nodes that have already been visited.
 	 */
-	std::unordered_set<Node *> visited;
+	VisitorSet visited;
 
 	/**
 	 * Current resolution result.
@@ -79,7 +102,6 @@ public:
  * resolving Node instances by name.
  */
 class ResolutionState {
-
 private:
 	/**
 	 * Constructor of the ResolutionState class.
@@ -87,8 +109,7 @@ private:
 	 * @param shared is the shared, path independent state.
 	 * @param resolutionRoot is the current resolution root node.
 	 */
-	ResolutionState(SharedResolutionState &shared,
-					int idx,
+	ResolutionState(SharedResolutionState &shared, int idx,
 	                Node *resolutionRoot)
 	    : shared(shared), idx(idx), resolutionRoot(resolutionRoot)
 	{
@@ -101,8 +122,12 @@ public:
 	 * @param shared is the shared, path independent state.
 	 * @param resolutionRoot is the current resolution root node.
 	 */
-	ResolutionState(SharedResolutionState &shared, Node *resolutionRoot = nullptr)
-	    : shared(shared), idx(0), resolutionRoot(resolutionRoot)
+	ResolutionState(SharedResolutionState &shared,
+	                Node *resolutionRoot = nullptr, bool atStartNode = true)
+	    : shared(shared),
+	      idx(0),
+	      resolutionRoot(resolutionRoot),
+	      atStartNode(atStartNode)
 	{
 	}
 
@@ -124,6 +149,12 @@ public:
 	Node *resolutionRoot;
 
 	/**
+	 * Set to true if the resolution currently is at the node at which the
+	 * resolution process was started.
+	 */
+	bool atStartNode;
+
+	/**
 	 * Adds a node to the result.
 	 *
 	 * @param node is the node that has been found.
@@ -141,37 +172,42 @@ public:
 	 */
 	bool markVisited(Node *node)
 	{
-		if (shared.visited.count(node) > 0) {
+		if (shared.visited.count(std::make_pair(node, idx)) > 0) {
 			return false;
 		}
-		shared.visited.insert(node);
+		shared.visited.insert(std::make_pair(node, idx));
 		return true;
 	}
 
 	/**
-	 * Returns true if the current node matches the search criteria.
+	 * Returns true if the search reached the end of the given path.
 	 *
-	 * @param type is the type of the current node.
-	 * @return true if the state indicates that the path has been completely
-	 * matched and that the given type matches the queried type.
+	 * @return true if the end of the path was reached, false otherwise.
 	 */
-	bool matches(const RttiBase &type)
-	{
-		return idx == static_cast<int>(shared.path.size()) &&
-		       type.isa(shared.type);
-	}
+	bool atEndOfPath() { return idx == static_cast<int>(shared.path.size()); }
 
-	const std::string &currentName() {
-		return shared.path[idx];
-	}
+	/**
+	 * Returns true if the given type matches the type given in the query.
+	 *
+	 * @return true if the type matches, false otherwise.
+	 */
+	bool typeMatches(const RttiBase &type) { return type.isa(shared.type); }
+
+	const std::string &currentName() { return shared.path[idx]; }
 
-	ResolutionState advance() {
+	ResolutionState advance()
+	{
 		return ResolutionState{shared, idx + 1, resolutionRoot};
 	}
 
-	ResolutionState fork(Node *newResolutionRoot) {
-		return ResolutionState{shared, newResolutionRoot};
+	ResolutionState fork(Node *newResolutionRoot)
+	{
+		return ResolutionState{shared, newResolutionRoot, false};
 	}
+
+	bool canFollowReferences() { return idx == 0 && atStartNode; }
+
+	bool canFollowComposita() { return idx == 0; }
 };
 
 /* Class Node */
@@ -199,19 +235,29 @@ std::vector<std::string> Node::path() const
 	return res;
 }
 
-bool Node::resolutionAtBeginning(ResolutionState &state)
+bool Node::canFollowComposita(ResolutionState &state)
 {
-	return state.idx == 0;
+	return state.canFollowComposita();
+}
+
+bool Node::canFollowReferences(ResolutionState &state)
+{
+	return state.canFollowReferences();
 }
 
 bool Node::resolve(ResolutionState &state)
 {
 	// Try to mark this note as visited, do nothing if already has been visited
 	if (state.markVisited(this)) {
+		std::cout << "visiting " << name << std::endl;
+
 		// Add this node to the result if it matches the current description
-		if (state.matches(type())) {
-			state.addToResult(this);
-			return true;
+		if (state.atEndOfPath()) {
+			if (state.typeMatches(type())) {
+				std::cout << "found match!" << std::endl;
+				state.addToResult(this);
+				return true;
+			}
 		} else {
 			continueResolve(state);
 		}
@@ -224,7 +270,8 @@ void Node::continueResolve(ResolutionState &state)
 	// Do nothing in the default implementation
 }
 
-bool Node::continueResolveIndex(const Index &index, ResolutionState &state) {
+bool Node::continueResolveIndex(const Index &index, ResolutionState &state)
+{
 	Rooted<Node> h = index.resolve(state.currentName());
 	if (h != nullptr) {
 		ResolutionState advancedState = state.advance();
@@ -235,10 +282,18 @@ bool Node::continueResolveIndex(const Index &index, ResolutionState &state) {
 
 bool Node::continueResolveCompositum(Handle<Node> h, ResolutionState &state)
 {
+	// If the name of the compositum explicitly matches the current name in the
+	// path, advance the search and try to resolve from this position
 	if (h->getName() == state.currentName()) {
 		ResolutionState advancedState = state.advance();
-		return h->resolve(advancedState);
-	} else if (resolutionAtBeginning(state)) {
+		if (h->resolve(advancedState)) {
+			return true;
+		}
+	}
+
+	// If the name did not match, but we are at the beginning of the path,
+	// descend without advancing the state
+	if (canFollowComposita(state)) {
 		return h->resolve(state);
 	}
 	return false;
@@ -246,13 +301,12 @@ bool Node::continueResolveCompositum(Handle<Node> h, ResolutionState &state)
 
 bool Node::continueResolveReference(Handle<Node> h, ResolutionState &state)
 {
-	if (resolutionAtBeginning(state)) {
+	// We can only follow references if we currently are at the beginning of the
+	// path and this node is the root node
+	if (canFollowReferences(state)) {
+		std::cout << "following reference to " << h->getName() << std::endl;
 		ResolutionState forkedState = state.fork(this);
-		if (h->getName() == state.currentName()) {
-			ResolutionState advancedState = forkedState.advance();
-			return h->resolve(advancedState);
-		}
-		return h->resolve(forkedState);
+		return continueResolveCompositum(h, forkedState);
 	}
 	return false;
 }
@@ -264,8 +318,14 @@ std::vector<ResolutionResult> Node::resolve(
 	SharedResolutionState sharedState(path, type);
 	ResolutionState state(sharedState, this);
 
-	// Call the internal resolve function, make sure the length of the given
-	// path is valid
+	// Kickstart the resolution process by treating this very node as compositum
+	std::cout << "------------" << std::endl;
+	std::cout << "resolving: ";
+	for (auto s: path) {
+		std::cout << s << " ";
+	}
+	std::cout << " of type " << type.name << std::endl;
+
 	if (path.size() > 0) {
 		continueResolveCompositum(this, state);
 	}
diff --git a/src/core/model/Node.hpp b/src/core/model/Node.hpp
index 97ec16f..c9c2808 100644
--- a/src/core/model/Node.hpp
+++ b/src/core/model/Node.hpp
@@ -106,8 +106,20 @@ private:
 	 * of the path has been matched yet).
 	 *
 	 * @param state is used internally to manage the resolution process.
+	 * @return true if the resolution is at the beginning, false otherwise.
 	 */
-	static bool resolutionAtBeginning(ResolutionState &state);
+	static bool canFollowComposita(ResolutionState &state);
+
+	/**
+	 * Returns true if following references is currently allowed in the
+	 * resolution process. This is the case if the resolution is currently at
+	 * the beginning (no part of the path has been matched yet) and this node
+	 * is the current resolution root node.
+	 *
+	 * @param state is used internally to manage the resolution process.
+	 * @return true if references can be followed, false otherwise.
+	 */
+	static bool canFollowReferences(ResolutionState &state);
 
 	/**
 	 * Method used internally for resolving nodes with a certain name and type
@@ -199,7 +211,8 @@ protected:
 	{
 		if (continueResolveIndex(index, state)) {
 			return true;
-		} else if (resolutionAtBeginning(state)) {
+		}
+		if (canFollowComposita(state)) {
 			return continueResolveComposita(container, state);
 		}
 		return false;
@@ -228,7 +241,7 @@ protected:
 	template <class T>
 	bool continueResolveReferences(T &container, ResolutionState &state)
 	{
-		if (resolutionAtBeginning(state)) {
+		if (canFollowReferences(state)) {
 			bool res = false;
 			for (auto elem : container) {
 				res = continueResolveReference(elem, state) | res;