prevented cycles in DocumentEntity::searchStartAnchor

3 files changed, 67 insertions, 19 deletions

diff --git a/src/core/model/Document.cpp b/src/core/model/Document.cpp
index 1e1620d..1fd429b 100644
--- a/src/core/model/Document.cpp
+++ b/src/core/model/Document.cpp
@@ -466,7 +466,7 @@ static bool matchStartAnchor(Handle<AnnotationClass> desc,
 template <typename Iterator>
 Rooted<Anchor> DocumentEntity::searchStartAnchorInField(
     Handle<AnnotationClass> desc, const std::string &name, Iterator begin,
-    Iterator end)
+    Iterator end, std::unordered_set<const DocumentEntity *> &visited)
 {
 	for (Iterator it = begin; it != end; it++) {
 		Handle<StructureNode> strct = *it;
@@ -481,7 +481,7 @@ Rooted<Anchor> DocumentEntity::searchStartAnchorInField(
 			// search downwards.
 			Rooted<Anchor> a =
 			    strct.cast<StructuredEntity>()->searchStartAnchorDownwards(
-			        desc, name);
+			        desc, name, visited);
 			if (a != nullptr) {
 				return a;
 			}
@@ -491,8 +491,12 @@ Rooted<Anchor> DocumentEntity::searchStartAnchorInField(
 }
 
 Rooted<Anchor> DocumentEntity::searchStartAnchorDownwards(
-    Handle<AnnotationClass> desc, const std::string &name)
+    Handle<AnnotationClass> desc, const std::string &name,
+    std::unordered_set<const DocumentEntity *> &visited)
 {
+	if (!visited.insert(this).second) {
+		return nullptr;
+	}
 	if (fields.empty()) {
 		return nullptr;
 	}
@@ -500,13 +504,17 @@ Rooted<Anchor> DocumentEntity::searchStartAnchorDownwards(
 	NodeVector<StructureNode> children = fields[fields.size() - 1];
 	// search it from back to front.
 	return searchStartAnchorInField(desc, name, children.rbegin(),
-	                                children.rend());
+	                                children.rend(), visited);
 }
 
 Rooted<Anchor> DocumentEntity::searchStartAnchorUpwards(
     Handle<AnnotationClass> desc, const std::string &name,
-    const DocumentEntity *child)
+    const DocumentEntity *child,
+    std::unordered_set<const DocumentEntity *> &visited)
 {
+	if (!visited.insert(this).second) {
+		return nullptr;
+	}
 	if (fields.empty()) {
 		return nullptr;
 	}
@@ -522,7 +530,8 @@ Rooted<Anchor> DocumentEntity::searchStartAnchorUpwards(
 	// to the child.
 	if (it != children.rend()) {
 		it++;
-		return searchStartAnchorInField(desc, name, it, children.rend());
+		return searchStartAnchorInField(desc, name, it, children.rend(),
+		                                visited);
 	}
 	throw OusiaException("Internal error: Child node not found in parent!");
 }
@@ -531,11 +540,13 @@ Rooted<Anchor> DocumentEntity::searchStartAnchor(size_t fieldIdx,
                                                  Handle<AnnotationClass> desc,
                                                  const std::string &name)
 {
+	std::unordered_set<const DocumentEntity *> visited;
+	visited.insert(this);
 	// get the correct field.
 	NodeVector<StructureNode> children = fields[fieldIdx];
 	// search it from back to front.
 	Rooted<Anchor> a = searchStartAnchorInField(desc, name, children.rbegin(),
-	                                            children.rend());
+	                                            children.rend(), visited);
 	// if we found the Anchor, return it.
 	if (a != nullptr) {
 		return a;
@@ -551,11 +562,11 @@ Rooted<Anchor> DocumentEntity::searchStartAnchor(size_t fieldIdx,
 	if (subInst->getParent()->isa(&RttiTypes::StructuredEntity)) {
 		return subInst->getParent()
 		    .cast<StructuredEntity>()
-		    ->searchStartAnchorUpwards(desc, name, this);
+		    ->searchStartAnchorUpwards(desc, name, this, visited);
 	}
 	if (subInst->getParent()->isa(&RttiTypes::AnnotationEntity)) {
 		subInst->getParent().cast<AnnotationEntity>()->searchStartAnchorUpwards(
-		    desc, name, this);
+		    desc, name, this, visited);
 	}
 	return nullptr;
 }
@@ -987,4 +998,4 @@ const Rtti AnnotationEntity =
         .parent(&Node)
         .composedOf({&StructuredEntity, &DocumentPrimitive, &Anchor});
 }
-}
+}
\ No newline at end of file
diff --git a/src/core/model/Document.hpp b/src/core/model/Document.hpp
index 81e2f41..2f82127 100644
--- a/src/core/model/Document.hpp
+++ b/src/core/model/Document.hpp
@@ -157,16 +157,18 @@ private:
 	void invalidateSubInstance();
 
 	template <typename Iterator>
-	Rooted<Anchor> searchStartAnchorInField(Handle<AnnotationClass> desc,
-	                                        const std::string &name,
-	                                        Iterator begin, Iterator end);
+	Rooted<Anchor> searchStartAnchorInField(
+	    Handle<AnnotationClass> desc, const std::string &name, Iterator begin,
+	    Iterator end, std::unordered_set<const DocumentEntity *> &visited);
 
-	Rooted<Anchor> searchStartAnchorDownwards(Handle<AnnotationClass> desc,
-	                                          const std::string &name);
+	Rooted<Anchor> searchStartAnchorDownwards(
+	    Handle<AnnotationClass> desc, const std::string &name,
+	    std::unordered_set<const DocumentEntity *> &visited);
 
-	Rooted<Anchor> searchStartAnchorUpwards(Handle<AnnotationClass> desc,
-	                                        const std::string &name,
-	                                        const DocumentEntity *child);
+	Rooted<Anchor> searchStartAnchorUpwards(
+	    Handle<AnnotationClass> desc, const std::string &name,
+	    const DocumentEntity *child,
+	    std::unordered_set<const DocumentEntity *> &visited);
 
 protected:
 	bool doValidate(Logger &logger) const;
@@ -1090,4 +1092,4 @@ extern const Rtti Anchor;
 }
 }
 
-#endif /* _OUSIA_MODEL_DOCUMENT_HPP_ */
+#endif /* _OUSIA_MODEL_DOCUMENT_HPP_ */
\ No newline at end of file
diff --git a/test/core/model/DocumentTest.cpp b/test/core/model/DocumentTest.cpp
index 9362af8..8ae9475 100644
--- a/test/core/model/DocumentTest.cpp
+++ b/test/core/model/DocumentTest.cpp
@@ -75,6 +75,41 @@ TEST(DocumentEntity, searchStartAnchor)
 	ASSERT_EQ(b, root->searchStartAnchor(0, Alpha, "myAnno"));
 }
 
+
+TEST(DocumentEntity, searchStartAnchorCycles)
+{
+	// create a trivial ontology.
+	Logger logger;
+	Manager mgr{1};
+	Rooted<SystemTypesystem> sys{new SystemTypesystem(mgr)};
+	Rooted<Ontology> ontology{new Ontology(mgr, sys, "trivial")};
+	// we only have one StructuredClass that may have itself as a child.
+	Rooted<StructuredClass> A = ontology->createStructuredClass(
+	    "A", Cardinality::any(), nullptr, false, true);
+	Rooted<FieldDescriptor> A_field = A->createFieldDescriptor(logger).first;
+	A_field->addChild(A);
+	// create an AnnotationClass.
+	Rooted<AnnotationClass> Alpha = ontology->createAnnotationClass("Alpha");
+	// validate this ontology.
+	ASSERT_TRUE(ontology->validate(logger));
+
+	// create a trivial but cyclic document.
+	Rooted<Document> doc{new Document(mgr, "myDoc")};
+	Rooted<StructuredEntity> root = doc->createRootStructuredEntity(A);
+	// add an Anchor.
+	Rooted<Anchor> a = root->createChildAnchor();
+	// create an AnnotationEntity with the Anchor as start.
+	doc->createChildAnnotation(Alpha, a, nullptr, Variant::mapType{}, "myAnno");
+	// add the cyclic reference.
+	root->addStructureNode(root, 0);
+	// We should be able to find the Anchor now if we look for it. There should
+	// be no loops.
+	ASSERT_EQ(a, root->searchStartAnchor(0));
+	ASSERT_EQ(a, root->searchStartAnchor(0, Alpha));
+	ASSERT_EQ(a, root->searchStartAnchor(0, nullptr, "myAnno"));
+	ASSERT_EQ(a, root->searchStartAnchor(0, Alpha, "myAnno"));
+}
+
 TEST(DocumentEntity, searchStartAnchorUpwards)
 {
 	// create a trivial ontology.