summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/core/model/Domain.cpp50
-rw-r--r--src/core/model/Domain.hpp18
-rw-r--r--test/core/model/DomainTest.cpp36
3 files changed, 58 insertions, 46 deletions
diff --git a/src/core/model/Domain.cpp b/src/core/model/Domain.cpp
index 25b2528..619454c 100644
--- a/src/core/model/Domain.cpp
+++ b/src/core/model/Domain.cpp
@@ -212,7 +212,7 @@ bool Descriptor::doValidate(Logger &logger) const
struct PathState {
std::shared_ptr<PathState> pred;
Node *node;
- int length;
+ size_t length;
PathState(std::shared_ptr<PathState> pred, Node *node)
: pred(pred), node(node)
@@ -234,10 +234,12 @@ static void constructPath(std::shared_ptr<PathState> state,
vec.push_back(state->node);
}
-template <typename F>
static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
- F finished)
+ Handle<Node> target, bool &success)
{
+ success = false;
+ // shortest path.
+ NodeVector<Node> shortest;
// state queue for breadth-first search.
std::queue<std::shared_ptr<PathState>> states;
{
@@ -245,11 +247,16 @@ static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
NodeVector<FieldDescriptor> fields = start->getFieldDescriptors();
for (auto fd : fields) {
- states.push(std::make_shared<PathState>(nullptr, fd.get()));
+ if (fd == target) {
+ // if we have found the target directly, return without search.
+ success = true;
+ return shortest;
+ }
+ if (fd->getFieldType() == FieldDescriptor::FieldType::TREE) {
+ states.push(std::make_shared<PathState>(nullptr, fd.get()));
+ }
}
}
- // shortest path.
- NodeVector<Node> shortest;
// set of visited nodes.
std::unordered_set<const Node *> visited;
while (!states.empty()) {
@@ -270,15 +277,18 @@ static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
const StructuredClass *strct =
static_cast<const StructuredClass *>(current->node);
- // continue the search path via all fields.
+ // look through 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)) {
+ if (fd == target) {
fin = true;
continue;
}
- states.push(std::make_shared<PathState>(current, fd.get()));
+ // only continue in the TREE field.
+ if (fd->getFieldType() == FieldDescriptor::FieldType::TREE) {
+ states.push(std::make_shared<PathState>(current, fd.get()));
+ }
}
/*
@@ -290,7 +300,7 @@ static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
NodeVector<StructuredClass> subs = strct->getSubclasses();
for (auto sub : subs) {
// if we found our target, break off the search in this branch.
- if (finished(sub)) {
+ if (sub == target) {
fin = true;
current = current->pred;
continue;
@@ -308,7 +318,7 @@ static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
// 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)) {
+ if (c == target) {
fin = true;
continue;
}
@@ -320,6 +330,7 @@ static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
}
// check if we are finished.
if (fin) {
+ success = true;
// if so we look if we found a shorter path than the current minimum
if (shortest.empty() || current->length < shortest.size()) {
NodeVector<Node> newPath;
@@ -332,7 +343,7 @@ static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
constructPath(current, newPath);
logger.error(
std::string("Can not unambigously create a path from \"") +
- start->getName() + "\".");
+ start->getName() + "\" to \"" + target->getName() + "\".");
logger.note("Dismissed the path:", SourceLocation{},
MessageMode::NO_CONTEXT);
for (auto n : newPath) {
@@ -347,15 +358,18 @@ static NodeVector<Node> pathTo(const Descriptor *start, Logger &logger,
NodeVector<Node> Descriptor::pathTo(Handle<StructuredClass> target,
Logger &logger) const
{
- return ousia::pathTo(this, logger,
- [target](Handle<Node> n) { return n == target; });
+ bool success = false;
+ return ousia::pathTo(this, logger, target, success);
}
-NodeVector<Node> Descriptor::pathTo(Handle<FieldDescriptor> field,
- Logger &logger) const
+std::pair<NodeVector<Node>, bool> Descriptor::pathTo(
+ Handle<FieldDescriptor> field, Logger &logger) const
+{
+ bool success = false;
+ NodeVector<Node> path = ousia::pathTo(this, logger, field, success);
+ return std::make_pair(path, success);
+}
{
- 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 abe7a52..91d635e 100644
--- a/src/core/model/Domain.hpp
+++ b/src/core/model/Domain.hpp
@@ -593,19 +593,25 @@ public:
Logger &logger) const;
/**
* This tries to construct the shortest possible path of this Descriptor
- * to the given FieldDescriptor.
+ * to the given FieldDescriptor. Note that this method has the problem that
+ * an empty return path does NOT strictly imply that no such path could
+ * be constructed: We also return an empty vector if the given
+ * FieldDescriptor is a direct child. Therefore we also return a bool value
+ * indicating that the path is valid or not.
+ *
*
* 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.
+ * @return returns a tuple containing a path of FieldDescriptors and
+ * StructuredClasses between this Descriptor and the input
+ * FieldDescriptor and a bool value indicating if the
+ * construction was successful.
*/
- NodeVector<Node> pathTo(Handle<FieldDescriptor> field,
- Logger &logger) const;
+ std::pair<NodeVector<Node>, bool> pathTo(Handle<FieldDescriptor> field,
+ Logger &logger) const;
};
/*
* TODO: We should discuss Cardinalities one more time. Is it smart to define
diff --git a/test/core/model/DomainTest.cpp b/test/core/model/DomainTest.cpp
index 0097900..672b2d1 100644
--- a/test/core/model/DomainTest.cpp
+++ b/test/core/model/DomainTest.cpp
@@ -123,7 +123,9 @@ TEST(Descriptor, pathTo)
ASSERT_EQ(0U, path.size());
// try to construct the path between section and the text field.
- path = section->pathTo(text->getFieldDescriptor(), logger);
+ auto res = section->pathTo(text->getFieldDescriptor(), logger);
+ ASSERT_TRUE(res.second);
+ path = res.first;
ASSERT_EQ(4U, path.size());
ASSERT_TRUE(path[0]->isa(&RttiTypes::FieldDescriptor));
ASSERT_TRUE(path[1]->isa(&RttiTypes::StructuredClass));
@@ -144,15 +146,13 @@ TEST(Descriptor, pathToAdvanced)
*
* 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
+ * 2.) A has B as child in the default field.
+ * 3.) B is transparent and has no children (but C as subclass)
+ * 4.) 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
+ * 5.) A has D as child in the default field.
+ * 6.) D is transparent has E as child in the default field.
+ * 7.) E is transparent and has target as child in the default field
* (longer path)
*
* So the path A_second_field, C, C_field should be returned.
@@ -185,30 +185,22 @@ TEST(Descriptor, pathToAdvanced)
Rooted<StructuredClass> target{
new StructuredClass(mgr, "target", domain, Cardinality::any())};
- // We create two fields for A
+ // We create a field for A
Rooted<FieldDescriptor> A_field = A->createFieldDescriptor(logger);
+ A_field->addChild(B);
+ A_field->addChild(D);
- A_field->addChild(target);
- Rooted<FieldDescriptor> A_field2 = A->createFieldDescriptor(
- logger, FieldDescriptor::FieldType::SUBTREE, "second", false);
-
- A_field2->addChild(B);
// We create no field for B
// One for C
Rooted<FieldDescriptor> C_field = C->createFieldDescriptor(logger);
-
C_field->addChild(target);
- // one for start
- Rooted<FieldDescriptor> start_field = start->createFieldDescriptor(logger);
- start_field->addChild(D);
// One for D
Rooted<FieldDescriptor> D_field = D->createFieldDescriptor(logger);
-
D_field->addChild(E);
+
// One for E
Rooted<FieldDescriptor> E_field = E->createFieldDescriptor(logger);
-
E_field->addChild(target);
ASSERT_TRUE(domain->validate(logger));
@@ -222,7 +214,7 @@ TEST(Descriptor, pathToAdvanced)
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());
+ ASSERT_EQ("", path[0]->getName());
ASSERT_TRUE(path[1]->isa(&RttiTypes::StructuredClass));
ASSERT_EQ("C", path[1]->getName());
ASSERT_TRUE(path[2]->isa(&RttiTypes::FieldDescriptor));
generated by cgit v1.2.3 (git 2.39.1) at 2025-05-01 06:30:50 +0000