2 files changed, 118 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 4b35fd4..966060f 100644
--- a/src/core/model/Domain.hpp
+++ b/src/core/model/Domain.hpp
@@ -334,19 +334,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; }
 
@@ -387,6 +389,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;
 
@@ -434,10 +439,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;
@@ -598,7 +633,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());
 	}
@@ -620,7 +655,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.