From 1765901ff35db93ba79ce67473ffb1abcf7165d6 Mon Sep 17 00:00:00 2001
From: Benjamin Paassen <bpaassen@techfak.uni-bielefeld.de>
Date: Wed, 18 Feb 2015 11:42:30 +0100
Subject: detected and counteracted cycles in gatherFieldDescriptors and
 gatherSubclasses. Also added unit tests for those cyclic cases.

---
 src/core/model/Domain.cpp | 37 +++++++++++++++++++++++++++----------
 src/core/model/Domain.hpp |  1 +
 2 files changed, 28 insertions(+), 10 deletions(-)

(limited to 'src/core/model')

diff --git a/src/core/model/Domain.cpp b/src/core/model/Domain.cpp
index ca8f889..8255401 100644
--- a/src/core/model/Domain.cpp
+++ b/src/core/model/Domain.cpp
@@ -324,21 +324,31 @@ bool FieldDescriptor::doValidate(Logger &logger) const
 	return valid;
 }
 
-static void gatherSubclasses(NodeVector<StructuredClass> &res,
-                             Handle<StructuredClass> strct)
+static void gatherSubclasses(
+    std::unordered_set<const StructuredClass *>& visited,
+    NodeVector<StructuredClass> &res, Handle<StructuredClass> strct)
 {
+	// this check is to prevent cycles.
+	if (!visited.insert(strct.get()).second) {
+		return;
+	}
 	for (auto sub : strct->getSubclasses()) {
+		// this check is to prevent cycles.
+		if(visited.count(sub.get())){
+			continue;
+		}
 		res.push_back(sub);
-		gatherSubclasses(res, sub);
+		gatherSubclasses(visited, res, sub);
 	}
 }
 
 NodeVector<StructuredClass> FieldDescriptor::getChildrenWithSubclasses() const
 {
+	std::unordered_set<const StructuredClass *> visited;
 	NodeVector<StructuredClass> res;
 	for (auto c : children) {
 		res.push_back(c);
-		gatherSubclasses(res, c);
+		gatherSubclasses(visited, res, c);
 	}
 	return res;
 }
@@ -566,8 +576,9 @@ bool Descriptor::addAndSortFieldDescriptor(Handle<FieldDescriptor> fd,
 	if (fds.find(fd) == fds.end()) {
 		invalidate();
 		// check if the previous field is a tree field already.
-		if (!fds.empty() && !fieldDescriptors.empty() &&
-		    fds.back()->getFieldType() == FieldDescriptor::FieldType::TREE &&
+		if (!fieldDescriptors.empty() &&
+		    fieldDescriptors.back()->getFieldType() ==
+		        FieldDescriptor::FieldType::TREE &&
 		    fd->getFieldType() != FieldDescriptor::FieldType::TREE) {
 			// if so we add the new field before the TREE field.
 			fieldDescriptors.insert(fieldDescriptors.end() - 1, fd);
@@ -776,8 +787,13 @@ void StructuredClass::removeSubclass(Handle<StructuredClass> sc, Logger &logger)
 
 Rooted<FieldDescriptor> StructuredClass::gatherFieldDescriptors(
     NodeVector<FieldDescriptor> &current,
+    std::unordered_set<const StructuredClass *> &visited,
     std::set<std::string> &overriddenFields, bool hasTREE) const
 {
+	// this check is to prevent cycles of inheritance to mess up this function.
+	if (!visited.insert(this).second) {
+		return nullptr;
+	}
 	Rooted<FieldDescriptor> mainField;
 	NodeVector<FieldDescriptor> tmp;
 	// first gather the non-overridden fields.
@@ -798,8 +814,8 @@ Rooted<FieldDescriptor> StructuredClass::gatherFieldDescriptors(
 
 	if (superclass != nullptr) {
 		Rooted<FieldDescriptor> super_main_field =
-		    superclass->gatherFieldDescriptors(current, overriddenFields,
-		                                       hasTREE);
+		    superclass->gatherFieldDescriptors(current, visited,
+		                                       overriddenFields, hasTREE);
 		if (!hasTREE) {
 			mainField = super_main_field;
 		}
@@ -814,9 +830,10 @@ NodeVector<FieldDescriptor> StructuredClass::getFieldDescriptors() const
 {
 	// in this case we return a NodeVector of Rooted entries without owner.
 	NodeVector<FieldDescriptor> vec;
+	std::unordered_set<const StructuredClass *> visited;
 	std::set<std::string> overriddenFields;
 	Rooted<FieldDescriptor> mainField =
-	    gatherFieldDescriptors(vec, overriddenFields, false);
+	    gatherFieldDescriptors(vec, visited, overriddenFields, false);
 	if (mainField != nullptr) {
 		vec.push_back(mainField);
 	}
@@ -961,4 +978,4 @@ const Rtti Domain = RttiBuilder<ousia::Domain>("Domain")
                         .parent(&RootNode)
                         .composedOf({&StructuredClass, &AnnotationClass});
 }
-}
+}
\ No newline at end of file
diff --git a/src/core/model/Domain.hpp b/src/core/model/Domain.hpp
index 476a38c..b3fc6c2 100644
--- a/src/core/model/Domain.hpp
+++ b/src/core/model/Domain.hpp
@@ -808,6 +808,7 @@ private:
 	 */
 	Rooted<FieldDescriptor> gatherFieldDescriptors(
 	    NodeVector<FieldDescriptor> &current,
+	    std::unordered_set<const StructuredClass *> &visited,
 	    std::set<std::string> &overriddenFields, bool hasTREE) const;
 
 protected:
-- 
cgit v1.2.3