summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/core/model/Domain.cpp187
-rw-r--r--src/core/model/Domain.hpp39
-rw-r--r--src/plugins/xml/XmlParser.cpp6
-rw-r--r--test/core/model/DomainTest.cpp22
4 files changed, 185 insertions, 69 deletions
diff --git a/src/core/model/Domain.cpp b/src/core/model/Domain.cpp
index 228348d..25b2528 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 <memory>
+#include <queue>
#include <set>
#include <core/common/RttiBuilder.hpp>
@@ -207,80 +209,153 @@ bool Descriptor::doValidate(Logger &logger) const
return valid & continueValidationCheckDuplicates(fds, logger);
}
-NodeVector<Node> Descriptor::pathTo(Handle<StructuredClass> target) const
+struct PathState {
+ std::shared_ptr<PathState> pred;
+ Node *node;
+ int length;
+
+ PathState(std::shared_ptr<PathState> pred, Node *node)
+ : pred(pred), node(node)
+ {
+ if (pred == nullptr) {
+ length = 1;
+ } else {
+ length = pred->length + 1;
+ }
+ }
+};
+
+static void constructPath(std::shared_ptr<PathState> state,
+ NodeVector<Node> &vec)
{
- NodeVector<Node> path;
- continuePath(target, path, true);
- return std::move(path);
+ if (state->pred != nullptr) {
+ constructPath(state->pred, vec);
+ }
+ vec.push_back(state->node);
}
-bool Descriptor::continuePath(Handle<StructuredClass> target,
- NodeVector<Node> &currentPath, bool start) const
+template <typename F>
+static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
+ F finished)
{
- // check if we are at the target already
- if (this == target) {
- return true;
+ // state queue for breadth-first search.
+ std::queue<std::shared_ptr<PathState>> states;
+ {
+ // initially put every field descriptor on the queue.
+ NodeVector<FieldDescriptor> fields = start->getFieldDescriptors();
+
+ for (auto fd : fields) {
+ states.push(std::make_shared<PathState>(nullptr, fd.get()));
+ }
}
- // a variable to determine if we already found a solution
- bool found = false;
- // the currently optimal path.
- NodeVector<Node> optimum;
- // use recursive depth-first search from the top to reach the given child
- // get the list of effective FieldDescriptors.
- NodeVector<FieldDescriptor> fields = getFieldDescriptors();
+ // shortest path.
+ NodeVector<Node> shortest;
+ // set of visited nodes.
+ std::unordered_set<const Node *> visited;
+ while (!states.empty()) {
+ std::shared_ptr<PathState> current = states.front();
+ states.pop();
+ // do not proceed if this node was already visited.
+ if (!visited.insert(current->node).second) {
+ continue;
+ }
+ // also do not proceed if we can't get better than the current shortest
+ // path anymore.
+ if (!shortest.empty() && current->length > shortest.size()) {
+ continue;
+ }
+
+ bool fin = false;
+ if (current->node->isa(&RttiTypes::StructuredClass)) {
+ const StructuredClass *strct =
+ static_cast<const StructuredClass *>(current->node);
+
+ // continue the search path via all fields.
+ NodeVector<FieldDescriptor> fields = strct->getFieldDescriptors();
+ for (auto fd : fields) {
+ // if we found our target, break off the search in this branch.
+ if (finished(fd)) {
+ fin = true;
+ continue;
+ }
+ states.push(std::make_shared<PathState>(current, fd.get()));
+ }
- Rooted<Node> thisHandle{const_cast<Descriptor *>(this)};
+ /*
+ * Furthermore we have to consider that all subclasses of this
+ * StructuredClass are allowed in place of this StructuredClass as
+ * well, so we continue the search for them as well.
+ */
- for (auto &fd : fields) {
- for (auto &c : fd->getChildren()) {
- // check if a child is the target node.
- if (c == target) {
- // if we have made the connection, stop the search.
- if (!start) {
- currentPath.push_back(thisHandle);
+ NodeVector<StructuredClass> subs = strct->getSubclasses();
+ for (auto sub : subs) {
+ // if we found our target, break off the search in this branch.
+ if (finished(sub)) {
+ fin = true;
+ current = current->pred;
+ continue;
+ }
+ // We only continue our path via transparent classes.
+ if (sub->isTransparent()) {
+ states.push(
+ std::make_shared<PathState>(current->pred, sub.get()));
}
- currentPath.push_back(fd);
- return true;
}
- // look for transparent intermediate nodes.
- if (c->isTransparent()) {
- // copy the path.
- NodeVector<Node> cPath = currentPath;
- if (!start) {
- cPath.push_back(thisHandle);
+ } else {
+ // otherwise this is a FieldDescriptor.
+ const FieldDescriptor *field =
+ static_cast<const FieldDescriptor *>(current->node);
+ // and we proceed by visiting all permitted children.
+ for (auto c : field->getChildren()) {
+ // if we found our target, break off the search in this branch.
+ if (finished(c)) {
+ fin = true;
+ continue;
}
- cPath.push_back(fd);
- // recursion.
- 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;
+ // We only allow to continue our path via transparent children.
+ if (c->isTransparent()) {
+ states.push(std::make_shared<PathState>(current, c.get()));
}
}
}
- }
-
- if (isa(&RttiTypes::StructuredClass)) {
- const StructuredClass *tis = static_cast<const StructuredClass *>(this);
- // if this is a StructuredClass we also can call the subclasses.
- for (auto &c : tis->getSubclasses()) {
- // copy the path.
- NodeVector<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;
+ // check if we are finished.
+ if (fin) {
+ // if so we look if we found a shorter path than the current minimum
+ if (shortest.empty() || current->length < shortest.size()) {
+ NodeVector<Node> newPath;
+ constructPath(current, newPath);
+ shortest = newPath;
+ } else if (current->length == shortest.size()) {
+ // if the length is the same the result is ambigous and we log
+ // an error.
+ NodeVector<Node> newPath;
+ constructPath(current, newPath);
+ logger.error(
+ std::string("Can not unambigously create a path from \"") +
+ start->getName() + "\".");
+ logger.note("Dismissed the path:", SourceLocation{},
+ MessageMode::NO_CONTEXT);
+ for (auto n : newPath) {
+ logger.note(n->getName());
+ }
}
}
}
+ return shortest;
+}
- // put the optimum in the given path reference.
- currentPath = std::move(optimum);
+NodeVector<Node> Descriptor::pathTo(Handle<StructuredClass> target,
+ Logger &logger) const
+{
+ return ousia::pathTo(this, logger,
+ [target](Handle<Node> n) { return n == target; });
+}
- // return if we found something.
- return found;
+NodeVector<Node> Descriptor::pathTo(Handle<FieldDescriptor> field,
+ Logger &logger) const
+{
+ return ousia::pathTo(this, logger,
+ [field](Handle<Node> n) { return n == field; });
}
static ssize_t getFieldDescriptorIndex(const NodeVector<FieldDescriptor> &fds,
diff --git a/src/core/model/Domain.hpp b/src/core/model/Domain.hpp
index 57e5602..ae5ba1d 100644
--- a/src/core/model/Domain.hpp
+++ b/src/core/model/Domain.hpp
@@ -404,9 +404,6 @@ private:
Owned<StructType> attributesDescriptor;
NodeVector<FieldDescriptor> fieldDescriptors;
- bool continuePath(Handle<StructuredClass> target, NodeVector<Node> &path,
- bool start) const;
-
void addAndSortFieldDescriptor(Handle<FieldDescriptor> fd, Logger &logger);
protected:
@@ -581,6 +578,9 @@ public:
* a path between book and section (via chapter), but chapter is not
* transparent. Therefore that path is not allowed.
*
+ * Implicitly this does a breadth-first search on the graph of
+ * StructuredClasses that are transparent. It also takes care of cycles.
+ *
* @param childDescriptor is a supposedly valid child Descriptor of this
* Descriptor.
* @return either a path of FieldDescriptors and
@@ -589,7 +589,38 @@ public:
* no such path can be constructed.
*
*/
- NodeVector<Node> pathTo(Handle<StructuredClass> childDescriptor) const;
+ NodeVector<Node> pathTo(Handle<StructuredClass> childDescriptor,
+ Logger &logger) const;
+ /**
+ * This tries to construct the shortest possible path of this Descriptor
+ * to the given FieldDescriptor.
+ *
+ * Implicitly this does a breadth-first search on the graph of
+ * StructuredClasses that are transparent. It also takes care of cycles.
+ *
+ * @param field is a FieldDescriptor that may be allowed as child of this
+ * Descriptor.
+ * @return either a path of FieldDescriptors and StructuredClasses
+ * between this Descriptor and the input FieldDescriptor or an
+ * empty vector if no such path can be constructed.
+ */
+ NodeVector<Node> pathTo(Handle<FieldDescriptor> field,
+ Logger &logger) const;
+ /**
+ * This tries to construct the shortest possible path of this Descriptor
+ * to the given FieldDescriptor.
+ *
+ * Implicitly this does a breadth-first search on the graph of
+ * StructuredClasses that are transparent. It also takes care of cycles.
+ *
+ * @param fieldName is the name of a FieldDescriptor that may be allowed as
+ * child of this Descriptor.
+ * @return either a path of FieldDescriptors and StructuredClasses
+ * between this Descriptor and a FieldDescriptor with the
+ * given name or an empty vector if no such path can be
+ * constructed.
+ */
+ NodeVector<Node> pathTo(const std::string &fieldName, Logger &logger) const;
};
/*
* TODO: We should discuss Cardinalities one more time. Is it smart to define
diff --git a/src/plugins/xml/XmlParser.cpp b/src/plugins/xml/XmlParser.cpp
index c51ca8c..63d9df5 100644
--- a/src/plugins/xml/XmlParser.cpp
+++ b/src/plugins/xml/XmlParser.cpp
@@ -131,8 +131,8 @@ public:
preamble(parentNode, fieldName, parent, inField);
// try to find a FieldDescriptor for the given tag if we are not in a
- // field already.
- // TODO: Consider fields of transparent classes
+ // field already. This does _not_ try to construct transparent paths
+ // in between.
if (!inField && parent != nullptr &&
parent->getDescriptor()->hasField(name())) {
Rooted<DocumentField> field{new DocumentField(
@@ -166,7 +166,7 @@ public:
strct, args, name);
} else {
// calculate a path if transparent entities are needed in between.
- auto path = parent->getDescriptor()->pathTo(strct);
+ auto path = parent->getDescriptor()->pathTo(strct, logger());
if (path.empty()) {
throw LoggableException(
std::string("An instance of \"") + strct->getName() +
diff --git a/test/core/model/DomainTest.cpp b/test/core/model/DomainTest.cpp
index 2e20c3b..0097900 100644
--- a/test/core/model/DomainTest.cpp
+++ b/test/core/model/DomainTest.cpp
@@ -91,7 +91,7 @@ Rooted<StructuredClass> getClass(const std::string name, Handle<Domain> dom)
TEST(Descriptor, pathTo)
{
// Start with some easy examples from the book domain.
- Logger logger;
+ TerminalLogger logger{std::cout};
Manager mgr{1};
Rooted<SystemTypesystem> sys{new SystemTypesystem(mgr)};
// Get the domain.
@@ -101,14 +101,14 @@ TEST(Descriptor, pathTo)
Rooted<StructuredClass> book = getClass("book", domain);
Rooted<StructuredClass> section = getClass("section", domain);
// get the path in between.
- NodeVector<Node> path = book->pathTo(section);
+ NodeVector<Node> path = book->pathTo(section, logger);
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.
- path = book->pathTo(text);
+ path = book->pathTo(text, logger);
ASSERT_EQ(3U, path.size());
ASSERT_TRUE(path[0]->isa(&RttiTypes::FieldDescriptor));
ASSERT_TRUE(path[1]->isa(&RttiTypes::StructuredClass));
@@ -118,9 +118,19 @@ TEST(Descriptor, pathTo)
// get the subsection node.
Rooted<StructuredClass> subsection = getClass("subsection", domain);
// try to get the path between book and subsection.
- path = book->pathTo(subsection);
+ path = book->pathTo(subsection, logger);
// this should be impossible.
ASSERT_EQ(0U, path.size());
+
+ // try to construct the path between section and the text field.
+ path = section->pathTo(text->getFieldDescriptor(), logger);
+ ASSERT_EQ(4U, 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));
+ ASSERT_TRUE(path[3]->isa(&RttiTypes::StructuredClass));
+ ASSERT_EQ("text", path[3]->getName());
}
TEST(Descriptor, pathToAdvanced)
@@ -148,7 +158,7 @@ TEST(Descriptor, pathToAdvanced)
* So the path A_second_field, C, C_field should be returned.
*/
Manager mgr{1};
- Logger logger;
+ TerminalLogger logger{std::cout};
Rooted<SystemTypesystem> sys{new SystemTypesystem(mgr)};
// Construct the domain
Rooted<Domain> domain{new Domain(mgr, sys, "nasty")};
@@ -209,7 +219,7 @@ TEST(Descriptor, pathToAdvanced)
#endif
// and now we should be able to find the shortest path as suggested
- NodeVector<Node> path = start->pathTo(target);
+ NodeVector<Node> path = start->pathTo(target, logger);
ASSERT_EQ(3U, path.size());
ASSERT_TRUE(path[0]->isa(&RttiTypes::FieldDescriptor));
ASSERT_EQ("second", path[0]->getName());
generated by cgit v1.2.3 (git 2.39.1) at 2025-04-30 22:06:56 +0000