Added methods for checking a property for acyclicity (or however this is supposed to be called)

2 files changed, 118 insertions, 5 deletions

diff --git a/src/core/model/Node.cpp b/src/core/model/Node.cpp
index dbc85e2..3b5f38c 100644
--- a/src/core/model/Node.cpp
+++ b/src/core/model/Node.cpp
@@ -361,26 +361,92 @@ bool Node::checkDuplicate(Handle<Node> elem,
 	const std::string &name = elem->getName();
 	if (!names.emplace(name).second) {
 		logger.error(std::string("Element with name \"") + name +
-		             std::string("\" defined multiple times in parent ") +
-		             type().name + std::string(" \"") +
-		             Utils::join(path(), ".") + std::string("\""), *elem);
+		                 std::string("\" defined multiple times in parent ") +
+		                 type().name + std::string(" \"") +
+		                 Utils::join(path(), ".") + std::string("\""),
+		             *elem);
 		return false;
 	}
 	return true;
 }
 
+bool Node::checkIsAcyclic(std::vector<const Node *> &path,
+                          std::unordered_set<const Node *> &visited,
+                          NodeReferenceCallback callback) const
+{
+	// Add this node to the path
+	path.push_back(this);
+
+	// A cycle was found, abort, shorten the path to the actual cycle
+	if (visited.count(this)) {
+		return false;
+	}
+	visited.insert(this);
+
+	// Continue allong the path
+	const Node *node = callback(this);
+	if (node != nullptr) {
+		if (!node->checkIsAcyclic(path, visited, callback)) {
+			return false;
+		}
+	}
+
+	// Remove this node from the path
+	path.pop_back();
+	return true;
+}
+
 bool Node::doValidate(Logger &logger) const { return true; }
 
 bool Node::validateName(Logger &logger) const
 {
 	if (!Utils::isIdentifier(name)) {
 		logger.error(type().name + std::string(" name \"") + name +
-		             std::string("\" is not a valid identifier"), this);
+		                 std::string("\" is not a valid identifier"),
+		             this);
 		return false;
 	}
 	return true;
 }
 
+bool Node::validateIsAcyclic(const std::string &name,
+                             NodeReferenceCallback callback,
+                             Logger &logger) const
+{
+	std::vector<const Node *> path;
+	std::unordered_set<const Node *> visited;
+
+	if (!checkIsAcyclic(path, visited, callback)) {
+		logger.error(std::string("Attribute \"") + name + ("\" is cyclic."),
+		             this);
+		logger.note("The following nodes are included in the cycle: ",
+		            SourceLocation{}, MessageMode::NO_CONTEXT);
+		for (const Node *node : path) {
+			const std::string &name = node->getName();
+			const std::string &typeName = node->type().name;
+			if (name.empty()) {
+				logger.note(std::string("Node of internal type ") + typeName +
+				                std::string(" declared here:"),
+				            node);
+			} else {
+				logger.note(std::string("Node \"") + name +
+				                std::string("\" of internal type ") + typeName +
+				                std::string(" declared here:"),
+				            node);
+			}
+		}
+		return false;
+	}
+	return true;
+}
+
+bool Node::validateParentIsAcyclic(Logger &logger) const
+{
+	return validateIsAcyclic("parent", [](const Node *thisRef) -> const Node *
+	                                   { return thisRef->parent.get(); },
+	                         logger);
+}
+
 void Node::invalidate()
 {
 	// Only perform the invalidation if necessary
diff --git a/src/core/model/Node.hpp b/src/core/model/Node.hpp
index 60d22e0..036bcae 100644
--- a/src/core/model/Node.hpp
+++ b/src/core/model/Node.hpp
@@ -31,8 +31,8 @@
 #include <cstdint>
 #include <map>
 #include <set>
-#include <unordered_set>
 #include <string>
+#include <unordered_set>
 #include <vector>
 
 #include <core/common/Location.hpp>
@@ -155,6 +155,7 @@ private:
 	 * vector.
 	 *
 	 * @param p is the list the path should be constructed in.
+	 * @param root is a node at which building the path should be aborted.
 	 */
 	void path(std::vector<std::string> &p, Handle<Node> root) const;
 
@@ -215,6 +216,30 @@ private:
 	                    std::unordered_set<std::string> &names,
 	                    Logger &logger) const;
 
+	/**
+	 * Callback function used to access a Node reference stored inside another
+	 * Node.
+	 *
+	 * @param thisRef is the Node of which the reference should be returned.
+	 * @return the value of the reference.
+	 */
+	using NodeReferenceCallback = const Node* (const Node* thisRef);
+
+	/**
+	 * Checks whether the a certain property is acyclic.
+	 *
+	 * @param path is a path containing the cycle. If no cycle is found, the
+	 * path will be empty.
+	 * @param visited a set of visited nodes used for cycle detection.
+	 * @param callback is the callback that is used to access the underlying
+	 * property that should be checked for acyclicity.
+	 * @return true if the node is acyclic regarding this property, false if
+	 * a cycle was detected. The cycle is stored in the "path".
+	 */
+	bool checkIsAcyclic(std::vector<const Node *> &path,
+	                    std::unordered_set<const Node *> &visited,
+	                    NodeReferenceCallback callback) const;
+
 protected:
 	/**
 	 * Sets the parent node.
@@ -365,6 +390,28 @@ protected:
 	bool validateName(Logger &logger) const;
 
 	/**
+	 * Makes sure the property accessed by the callback is not cyclic.
+	 *
+	 * @param name is the name of the property. The passed name is used to build
+	 * a nice error message.
+	 * @param callback is the callback that is used to access the property.
+	 * @param logger is the logger instance to which an error message containing
+	 * the cycle is logged.
+	 * @return true if the parent reference is acyclic, false otherwise.
+	 */
+	bool validateIsAcyclic(const std::string &name,
+	                       NodeReferenceCallback callback, Logger &logger) const;
+
+	/**
+	 * Makes sure the "parent" reference is not cyclic.
+	 *
+	 * @param logger is the logger instance to which an error message containing
+	 * the cycle is logged.
+	 * @return true if the parent reference is acyclic, false otherwise.
+	 */
+	bool validateParentIsAcyclic(Logger &logger) const;
+
+	/**
 	 * Helper function that can be used to forward the validation process to
 	 * child nodes.
 	 *