Merge branch 'master' of somweyr.de:ousia

3 files changed, 160 insertions, 8 deletions

diff --git a/src/core/model/Domain.cpp b/src/core/model/Domain.cpp
index 17b1d2d..1fb057e 100644
--- a/src/core/model/Domain.cpp
+++ b/src/core/model/Domain.cpp
@@ -17,6 +17,7 @@
 */
 
 #include <core/common/Rtti.hpp>
+#include <core/common/Exceptions.hpp>
 
 #include "Domain.hpp"
 
@@ -38,6 +39,79 @@ void Descriptor::continueResolve(ResolutionState &state)
 	                         state);
 }
 
+std::vector<Rooted<Node>> Descriptor::pathTo(
+    Handle<StructuredClass> target) const
+{
+	std::vector<Rooted<Node>> path;
+	continuePath(target, path);
+	return path;
+}
+
+static bool pathEquals(const Descriptor& a, const Descriptor& b)
+{
+	// We assume that two Descriptors are equal if their names and domain names
+	// are equal.
+	if (a.getName() != b.getName()) {
+		return false;
+	}
+	Handle<Domain> aDom = a.getParent().cast<Domain>();
+	Handle<Domain> bDom = b.getParent().cast<Domain>();
+	return aDom->getName() == bDom->getName();
+}
+
+//TODO: isa-handling.
+bool Descriptor::continuePath(Handle<StructuredClass> target,
+                              std::vector<Rooted<Node>> &path) const
+{
+	// look if our current node is reachable using the parent references
+	for (auto &pfd : target->getParents()) {
+		Handle<Descriptor> p = pfd->getParent().cast<Descriptor>();
+		if (pathEquals(*this, *p)) {
+			// if we have made the connection, stop the search.
+			path.push_back(pfd);
+			return true;
+		}
+		// look for transparent intermediate nodes.
+		if (!p->isa(RttiTypes::StructuredClass)) {
+			continue;
+		}
+		Handle<StructuredClass> pc = p.cast<StructuredClass>();
+		if (pc->transparent) {
+			// recursion
+			std::vector<Rooted<Node>> cPath = path;
+			if (continuePath(pc, cPath)) {
+				path = std::move(cPath);
+				path.push_back(pc);
+				path.push_back(pfd);
+				return true;
+			}
+		}
+	}
+	// use recursive depth-first search from the top to reach the given child
+	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)) {
+					path = std::move(cPath);
+					return true;
+				}
+			}
+		}
+	}
+	return false;
+}
+
 /* Class Domain */
 
 void Domain::continueResolve(ResolutionState &state)
diff --git a/src/core/model/Domain.hpp b/src/core/model/Domain.hpp
index 23a55f3..755ff52 100644
--- a/src/core/model/Domain.hpp
+++ b/src/core/model/Domain.hpp
@@ -336,19 +336,21 @@ public:
 	 * this field.
 	 */
 	const NodeVector<StructuredClass> &getChildren() const { return children; }
-	
+
 	/**
 	 * Adds a StructuredClass whose instances shall be allowed as children in
 	 * the StructureTree of instances of this field.
 	 */
-	void addChild(Handle<StructuredClass> c){ children.push_back(c);}
-	
-	
+	void addChild(Handle<StructuredClass> c) { children.push_back(c); }
+
 	/**
 	 * Adds multiple StructuredClasses whose instances shall be allowed as
 	 * children in the StructureTree of instances of this field.
 	 */
-	void addChildren(const std::vector<Handle<StructuredClass>> &cs){ children.insert(children.end(), cs.begin(), cs.end());}
+	void addChildren(const std::vector<Handle<StructuredClass>> &cs)
+	{
+		children.insert(children.end(), cs.begin(), cs.end());
+	}
 
 	FieldType getFieldType() const { return fieldType; }
 
@@ -391,6 +393,9 @@ private:
 	Owned<StructType> attributesDescriptor;
 	NodeVector<FieldDescriptor> fieldDescriptors;
 
+	bool continuePath(Handle<StructuredClass> target,
+	                  std::vector<Rooted<Node>> &path) const;
+
 protected:
 	void continueResolve(ResolutionState &state) override;
 
@@ -438,10 +443,40 @@ public:
 	/**
 	 * Adds multiple FieldDescriptors to this Descriptor.
 	 */
-	void addFieldDescriptors(const std::vector<Handle<FieldDescriptor>>& fds)
+	void addFieldDescriptors(const std::vector<Handle<FieldDescriptor>> &fds)
 	{
 		fieldDescriptors.insert(fieldDescriptors.end(), fds.begin(), fds.end());
 	}
+
+	/**
+	 * This tries to construct the shortest possible path of this Descriptor
+	 * to the given child Descriptor. As an example consider the book domain
+	 * from above.
+	 *
+	 * First consider the call book->pathTo(chapter). This is an easy example:
+	 * Our path just contains a reference to the default field of book, because
+	 * a chapter may be directly added to the main field of book.
+	 *
+	 * Second consider the call book->pathTo(text). This is somewhat more
+	 * complicated, but it is still a valid request, because we can construct
+	 * the path: {book_main_field, paragraph, paragraph_main_field}.
+	 * This is only valid because paragraph is transparent.
+	 *
+	 * What about the call book->pathTo(section)? This will lead to an empty
+	 * return path (= invalid). We could, of course, in principle construct
+	 * a path between book and section (via chapter), but chapter is not
+	 * transparent. Therefore that path is not allowed.
+	 *
+	 * @param childDescriptor is a supposedly valid child Descriptor of this
+	 *                        Descriptor.
+	 * @return                either a path of FieldDescriptors and
+	 *                        StructuredClasses between this Descriptor and
+	 *                        the input StructuredClass or an empty vector if
+	 *                        no such path can be constructed.
+	 *
+	 */
+	std::vector<Rooted<Node>> pathTo(
+	    Handle<StructuredClass> childDescriptor) const;
 };
 
 typedef RangeSet<size_t> Cardinality;
@@ -608,7 +643,7 @@ public:
 	 * Adds multiple FieldDescriptors that should allow an instance of this
 	 * StructuredClass as a child in the Structure Tree.
 	 */
-	void addParents(const std::vector<Handle<FieldDescriptor>>& ps)
+	void addParents(const std::vector<Handle<FieldDescriptor>> &ps)
 	{
 		parents.insert(parents.end(), ps.begin(), ps.end());
 	}
@@ -630,7 +665,8 @@ public:
 	 * @param name                 is a name for this AnnotationClass that will
 	 *                             be used for later references to this
 	 *                             AnnotationClass.
-	 * @param domain               is the Domain this AnnotationClass belongs to.
+	 * @param domain               is the Domain this AnnotationClass belongs
+	 *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 317223d..d22c845 100644
--- a/test/core/model/DomainTest.cpp
+++ b/test/core/model/DomainTest.cpp
@@ -80,5 +80,47 @@ TEST(Domain, testDomainResolving)
 	ASSERT_EQ(1U, res.size());
 	assert_path(res[0], typeOf<StructuredClass>(), {"book", "paragraph"});
 }
+
+Rooted<StructuredClass> getClass(const std::string name, Handle<Domain> dom)
+{
+	std::vector<ResolutionResult> res =
+	    dom->resolve(name, RttiTypes::StructuredClass);
+	return res[0].node.cast<StructuredClass>();
+}
+
+TEST(Descriptor, pathTo)
+{
+	// Start with some easy examples from the book domain.
+	Logger logger;
+	Manager mgr{1};
+	Rooted<SystemTypesystem> sys{new SystemTypesystem(mgr)};
+	// Get the domain.
+	Rooted<Domain> domain = constructBookDomain(mgr, sys, logger);
+
+	// get the book node and the section node.
+	Rooted<StructuredClass> book = getClass("book", domain);
+	Rooted<StructuredClass> section = getClass("section", domain);
+	// get the path in between.
+	std::vector<Rooted<Node>> path = book->pathTo(section);
+	ASSERT_EQ(1, 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.
+	path = book->pathTo(text);
+	ASSERT_EQ(3, path.size());
+	ASSERT_TRUE(path[0]->isa(RttiTypes::FieldDescriptor));
+	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.
+	path = book->pathTo(subsection);
+	// this should be impossible.
+	ASSERT_EQ(0, path.size());
+}
 }
 }