Merge branch 'master' of somweyr.de:ousia

3 files changed, 185 insertions, 65 deletions

diff --git a/src/core/model/Domain.cpp b/src/core/model/Domain.cpp
index d664809..be9aa05 100644
--- a/src/core/model/Domain.cpp
+++ b/src/core/model/Domain.cpp
@@ -16,6 +16,8 @@
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
+#include <set>
+
 #include <core/common/Rtti.hpp>
 #include <core/common/Exceptions.hpp>
 
@@ -60,65 +62,88 @@ static bool pathEquals(const Descriptor &a, const Descriptor &b)
 }
 
 bool Descriptor::continuePath(Handle<StructuredClass> target,
-                              std::vector<Rooted<Node>> &path) const
+                              std::vector<Rooted<Node>> &currentPath,
+                              std::set<std::string> ignoredFields,
+                              bool exploreSuperclass,
+                              bool exploreSubclasses) const
 {
+	// TODO: REMOVE
+	std::string targetName = target->getName();
+	std::string thisName = getName();
+	std::string currentPathName;
+	for (auto &n : currentPath) {
+		currentPathName += ".";
+		currentPathName += n->getName();
+	}
+	// a variable to determine if we already found a solution
 	bool found = false;
+	// the currently optimal path.
+	std::vector<Rooted<Node>> optimum;
 	// use recursive depth-first search from the top to reach the given child
-	if (fieldDescriptors.size() > 0) {
-		for (auto &fd : fieldDescriptors) {
-			for (auto &c : fd->getChildren()) {
-				if (pathEquals(*c, *target)) {
-					// if we have made the connection, stop the search.
-					path.push_back(fd);
-					return true;
-				}
-				// look for transparent intermediate nodes.
-				if (c->transparent) {
-					// copy the path.
-					std::vector<Rooted<Node>> cPath = path;
-					cPath.push_back(fd);
-					cPath.push_back(c);
-					// recursion.
-					if (c->continuePath(target, cPath) &&
-					    (!found || path.size() > cPath.size())) {
-						// look if this path is better than the current optimum.
-						path = std::move(cPath);
-						found = true;
-					}
-				}
-			}
+	for (auto &fd : fieldDescriptors) {
+		if (!(ignoredFields.insert(fd->getName()).second)) {
+			// if we want to ignore that field, we continue.
+			continue;
 		}
-	} else {
-		// if this is a StructuredClass and if it did not formulate own
-		// fieldDescriptors (overriding the parent), we can also use the
-		// (inheritance-wise) parent
-		if (isa(RttiTypes::StructuredClass)) {
-			const StructuredClass *tis =
-			    static_cast<const StructuredClass *>(this);
-			if (!tis->getIsA().isNull()) {
+		for (auto &c : fd->getChildren()) {
+			if (pathEquals(*c, *target)) {
+				// if we have made the connection, stop the search.
+				currentPath.push_back(fd);
+				return true;
+			}
+			// look for transparent intermediate nodes.
+			if (c->transparent) {
 				// copy the path.
-				std::vector<Rooted<Node>> cPath = path;
-				if (tis->getIsA()->continuePath(target, cPath) &&
-				    (found || path.size() > cPath.size())) {
+				std::vector<Rooted<Node>> cPath = currentPath;
+				cPath.push_back(fd);
+				cPath.push_back(c);
+				// recursion.
+				if (c->continuePath(target, cPath) &&
+				    (!found || optimum.size() > cPath.size())) {
 					// look if this path is better than the current optimum.
-					path = std::move(cPath);
+					optimum = std::move(cPath);
 					found = true;
 				}
 			}
 		}
 	}
-	// either way we can try to find the targets parent (inheritance-wise)
-	// instead of the target itself.
-	if (!target->getIsA().isNull()) {
-		// copy the path.
-		std::vector<Rooted<Node>> cPath = path;
-		if (continuePath(target->getIsA(), cPath) &&
-		    (!found || path.size() > cPath.size())) {
-			// look if this path is better than the current optimum.
-			path = std::move(cPath);
-			found = true;
+
+	if (isa(RttiTypes::StructuredClass)) {
+		const StructuredClass *tis = static_cast<const StructuredClass *>(this);
+		/*
+		 * if this is a StructuredClass, we can also use the super class (at
+		 * least for fields that are not overridden)
+		 */
+		if (exploreSuperclass && !tis->getIsA().isNull()) {
+			// copy the path.
+			std::vector<Rooted<Node>> cPath = currentPath;
+			if (tis->getIsA()->continuePath(target, cPath, ignoredFields, true,
+			                                false) &&
+			    (!found || optimum.size() > cPath.size())) {
+				// look if this path is better than the current optimum.
+				optimum = std::move(cPath);
+				found = true;
+			}
+		}
+
+		// we also can call the subclasses.
+		if (exploreSubclasses) {
+			for (auto &c : tis->getSubclasses()) {
+				// copy the path.
+				std::vector<Rooted<Node>> cPath = currentPath;
+				if (c->continuePath(target, cPath, {}, false) &&
+				    (!found || optimum.size() > cPath.size())) {
+					// look if this path is better than the current optimum.
+					optimum = std::move(cPath);
+					found = true;
+				}
+			}
 		}
 	}
+
+	// put the optimum in the given path reference.
+	currentPath = std::move(optimum);
+
 	// return if we found something.
 	return found;
 }
diff --git a/src/core/model/Domain.hpp b/src/core/model/Domain.hpp
index 1f65242..4b26917 100644
--- a/src/core/model/Domain.hpp
+++ b/src/core/model/Domain.hpp
@@ -394,7 +394,10 @@ private:
 	NodeVector<FieldDescriptor> fieldDescriptors;
 
 	bool continuePath(Handle<StructuredClass> target,
-	                  std::vector<Rooted<Node>> &path) const;
+	                  std::vector<Rooted<Node>> &path,
+	                  std::set<std::string> ignoredFields = {},
+	                  bool exploreSuperclass = true,
+	                  bool exploreSubclasses = true) const;
 
 protected:
 	void continueResolve(ResolutionState &state) override;
@@ -558,6 +561,7 @@ class StructuredClass : public Descriptor {
 private:
 	const Cardinality cardinality;
 	Owned<StructuredClass> isa;
+	NodeVector<StructuredClass> subclasses;
 
 public:
 	const bool transparent;
@@ -583,7 +587,9 @@ public:
 	 * @param isa                  references a parent StructuredClass. Please
 	 *                             look for more information on inheritance in
 	 *                             the class documentation above. The default is
-	 *                             a null reference, meaning no parent class.
+	 *                             a null reference, meaning no super class.
+	 *                             The constructor automatically registers this
+	 *                             class as a subclass at the super class.
 	 * @param transparent          specifies whether this StructuredClass is
 	 *                             transparent. For more information on
 	 *                             transparency please refer to the class
@@ -598,9 +604,13 @@ public:
 	    : Descriptor(mgr, std::move(name), domain, attributesDescriptor),
 	      cardinality(cardinality),
 	      isa(acquire(isa)),
+	      subclasses(this),
 	      transparent(transparent),
 	      root(root)
 	{
+		if (!isa.isNull()) {
+			isa->subclasses.push_back(this);
+		}
 	}
 
 	/**
@@ -618,6 +628,24 @@ public:
 	 * hierarchy (!).
 	 */
 	Rooted<StructuredClass> getIsA() const { return isa; }
+
+	/**
+	 * Returns the StructuredClasses that are subclasses of this class. This
+	 * is the inverted version of isa, meaning: each class c that has a isa
+	 * relationship to this class is part of the returned vector.
+	 *
+	 * Note that the order of subclasses is not strictly defined.
+	 *
+	 * You are not allowed to add subclasses directly to the vector. When you
+	 * construct a new StructuredClass with a non-empty isa-handle it will
+	 * automatically register as subclass at the super class.
+	 *
+	 * @return the StructuredClasses that are subclasses of this class.
+	 */
+	const NodeVector<StructuredClass> &getSubclasses() const
+	{
+		return subclasses;
+	}
 };
 
 /**
@@ -637,7 +665,7 @@ public:
 	 *                             be used for later references to this
 	 *                             AnnotationClass.
 	 * @param domain               is the Domain this AnnotationClass belongs
-	 *to.
+	 *                             to.
 	 * @param attributesDescriptor is a StructType that specifies the attribute
 	 *                             keys as well as value domains for this
 	 *                             Descriptor.
diff --git a/test/core/model/DomainTest.cpp b/test/core/model/DomainTest.cpp
index 3b62b48..af00151 100644
--- a/test/core/model/DomainTest.cpp
+++ b/test/core/model/DomainTest.cpp
@@ -104,7 +104,7 @@ TEST(Descriptor, pathTo)
 	std::vector<Rooted<Node>> path = book->pathTo(section);
 	ASSERT_EQ(1U, path.size());
 	ASSERT_TRUE(path[0]->isa(RttiTypes::FieldDescriptor));
-	
+
 	// get the text node.
 	Rooted<StructuredClass> text = getClass("text", domain);
 	// get the path between book and text via paragraph.
@@ -114,7 +114,7 @@ TEST(Descriptor, pathTo)
 	ASSERT_TRUE(path[1]->isa(RttiTypes::StructuredClass));
 	ASSERT_EQ("paragraph", path[1]->getName());
 	ASSERT_TRUE(path[2]->isa(RttiTypes::FieldDescriptor));
-	
+
 	// get the subsection node.
 	Rooted<StructuredClass> subsection = getClass("subsection", domain);
 	// try to get the path between book and subsection.
@@ -125,31 +125,98 @@ TEST(Descriptor, pathTo)
 
 TEST(Descriptor, pathToAdvanced)
 {
-	// Now we build a really nasty domain with lots of transparency
-	// and inheritance
+	/*
+	 * Now we build a really nasty domain with lots of transparency
+	 * and inheritance. The basic idea is to have three paths from start to
+	 * finish, where one is blocked by overriding fields and the longer valid
+	 * one is found first such that it has to be replaced by the shorter one
+	 * during the search.
+	 *
+	 * To achieve that we have the following structure:
+	 * 1.) The start class inherits from A.
+	 * 2.) A has the target as child in the default field, but the default
+	 *     field is overridden in the start class.
+	 * 3.) A has B as child in another field.
+	 * 4.) B is transparent and has no children (but C as subclass)
+	 * 5.) C is a subclass of B, transparent and has
+	 *     the target as child (shortest path).
+	 * 6.) start has D as child in the default field.
+	 * 7.) D is transparent has E as child in the default field.
+	 * 8.) E is transparent and has target as child in the default field
+	 *     (longer path)
+	 *
+	 * So the path start_field , E , E_field should be returned.
+	 */
 	Logger logger;
 	Manager mgr{1};
 	Rooted<SystemTypesystem> sys{new SystemTypesystem(mgr)};
-	// Get the domain.
-	Rooted<Domain> domain {new Domain(mgr, sys, "nasty")};
+	// Construct the domain
+	Rooted<Domain> domain{new Domain(mgr, sys, "nasty")};
 	Cardinality any;
 	any.merge(Range<size_t>::typeRangeFrom(0));
-	
-	// Our root class A
+
+	// Let's create the classes that we need first
 	Rooted<StructuredClass> A{new StructuredClass(
 	    mgr, "A", domain, any, {nullptr}, {nullptr}, false, true)};
 	domain->addStructuredClass(A);
-	// We also create a field for it.
+	Rooted<StructuredClass> start{new StructuredClass(
+	    mgr, "start", domain, any, {nullptr}, A, false, false)};
+	domain->addStructuredClass(start);
+	Rooted<StructuredClass> B{new StructuredClass(
+	    mgr, "B", domain, any, {nullptr}, {nullptr}, true, false)};
+	domain->addStructuredClass(B);
+	Rooted<StructuredClass> C{
+	    new StructuredClass(mgr, "C", domain, any, {nullptr}, B, true, false)};
+	domain->addStructuredClass(C);
+	Rooted<StructuredClass> D{new StructuredClass(
+	    mgr, "D", domain, any, {nullptr}, {nullptr}, true, false)};
+	domain->addStructuredClass(D);
+	Rooted<StructuredClass> E{new StructuredClass(
+	    mgr, "E", domain, any, {nullptr}, {nullptr}, true, false)};
+	domain->addStructuredClass(E);
+	Rooted<StructuredClass> target{
+	    new StructuredClass(mgr, "target", domain, any)};
+	domain->addStructuredClass(target);
+	// We create two fields for A
 	Rooted<FieldDescriptor> A_field{new FieldDescriptor(mgr, A)};
 	A->addFieldDescriptor(A_field);
+	A_field->addChild(target);
+	Rooted<FieldDescriptor> A_field2{new FieldDescriptor(
+	    mgr, A, FieldDescriptor::FieldType::SUBTREE, "second")};
+	A->addFieldDescriptor(A_field2);
+	A_field2->addChild(B);
+	// We create no field for B
+	// One for C
+	Rooted<FieldDescriptor> C_field{new FieldDescriptor(mgr, C)};
+	C->addFieldDescriptor(C_field);
+	C_field->addChild(target);
+	// one for start
+	Rooted<FieldDescriptor> start_field{new FieldDescriptor(mgr, start)};
+	start->addFieldDescriptor(start_field);
+	start_field->addChild(D);
+	// One for D
+	Rooted<FieldDescriptor> D_field{new FieldDescriptor(mgr, D)};
+	D->addFieldDescriptor(D_field);
+	D_field->addChild(E);
+	// One for E
+	Rooted<FieldDescriptor> E_field{new FieldDescriptor(mgr, E)};
+	E->addFieldDescriptor(E_field);
+	E_field->addChild(target);
 	
-	// our first transparent child B
-	Rooted<StructuredClass> B{new StructuredClass(
-	    mgr, "B", domain, any, {nullptr}, {nullptr}, true)};
-	A_field->addChild(B);
-	
-	//TODO: Continue
-}
+	#ifdef MANAGER_GRAPHVIZ_EXPORT
+		// dump the manager state
+		mgr.exportGraphviz("nastyDomain.dot");
+	#endif
 
+	// and now we should be able to find the shortest path as suggested
+	std::vector<Rooted<Node>> path = start->pathTo(target);
+	ASSERT_EQ(3U, path.size());
+	ASSERT_TRUE(path[0]->isa(RttiTypes::FieldDescriptor));
+	ASSERT_EQ("second", path[0]->getName());
+	ASSERT_TRUE(path[1]->isa(RttiTypes::StructuredClass));
+	ASSERT_EQ("B", path[1]->getName());
+	ASSERT_TRUE(path[2]->isa(RttiTypes::FieldDescriptor));
+	ASSERT_EQ("", path[2]->getName());
+}
 }
 }