diff options
| -rw-r--r-- | src/core/model/Node.cpp | 265 | ||||
| -rw-r--r-- | src/core/model/Node.hpp | 351 | ||||
| -rw-r--r-- | test/core/model/NodeTest.cpp | 42 |
3 files changed, 464 insertions, 194 deletions
diff --git a/src/core/model/Node.cpp b/src/core/model/Node.cpp index e149596..518a74d 100644 --- a/src/core/model/Node.cpp +++ b/src/core/model/Node.cpp @@ -16,23 +16,171 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ +#include <functional> +#include <unordered_set> + #include <core/common/Exceptions.hpp> #include "Node.hpp" namespace ousia { -/* Class Node */ +/* Class SharedResolutionState */ -void Node::setName(std::string name) -{ - // Call the name change event +/** + * The SharedResolutionState structure represents the state that is shared + * between all resolution paths. A reference to a per-resolution-global + * SharedResolutionState instance is stored in the ResolutionState class. + */ +class SharedResolutionState { + +public: + /** + * Actual path (name pattern) that was requested for resolution. + */ + const std::vector<std::string> &path; + + /** + * Type of the node that was requested for resolution. + */ + const RttiBase &type; + + /** + * Tracks all nodes that have already been visited. + */ + std::unordered_set<Node *> visited; + + /** + * Current resolution result. + */ + std::vector<ResolutionResult> result; + + static std::vector<int> buildPrefixTable( + const std::vector<std::string> &path); + + /** + * Constructor of the SharedResolutionState class. + * + * @param path is a const reference to the actual path that should be + * resolved. + * @param type is the type of the node that should be resolved. + */ + SharedResolutionState(const std::vector<std::string> &path, + const RttiBase &type) + : path(path), type(type) + { + } +}; + +/* Class ResolutionState */ + +/** + * The ResolutionState class represents a single resolution path used when + * resolving Node instances by name. + */ +class ResolutionState { + +private: + /** + * Constructor of the ResolutionState class. + * + * @param shared is the shared, path independent state. + * @param resolutionRoot is the current resolution root node. + */ + ResolutionState(SharedResolutionState &shared, + int idx, + Node *resolutionRoot) + : shared(shared), idx(idx), resolutionRoot(resolutionRoot) + { + } + +public: + /** + * Constructor of the ResolutionState class. + * + * @param shared is the shared, path independent state. + * @param resolutionRoot is the current resolution root node. + */ + ResolutionState(SharedResolutionState &shared, Node *resolutionRoot = nullptr) + : shared(shared), idx(0), resolutionRoot(resolutionRoot) + { + } + + /** + * Reference at the resolution state that is shared between the various + * resolution paths. + */ + SharedResolutionState &shared; + + /** + * Current index within the given path. + */ + int idx; + + /** + * Current resolution root node or nullptr if no resolution root node has + * been set yet. + */ + Node *resolutionRoot; + + /** + * Adds a node to the result. + * + * @param node is the node that has been found. + */ + void addToResult(Node *node) { - NameChangeEvent ev{this->name, name}; - triggerEvent(ev); + shared.result.emplace_back(ResolutionResult{node, resolutionRoot}); } - // Set the new name + /** + * Marks the given node as visited. Returns false if the given node has + * already been visited. + * + * @param node is the node that should be marked as visited. + */ + bool markVisited(Node *node) + { + if (shared.visited.count(node) > 0) { + return false; + } + shared.visited.insert(node); + return true; + } + + /** + * Returns true if the current node matches the search criteria. + * + * @param type is the type of the current node. + * @return true if the state indicates that the path has been completely + * matched and that the given type matches the queried type. + */ + bool matches(const RttiBase &type) + { + return idx == static_cast<int>(shared.path.size()) && + type.isa(shared.type); + } + + const std::string ¤tName() { + return shared.path[idx]; + } + + ResolutionState advance() { + return ResolutionState{shared, idx + 1, resolutionRoot}; + } + + ResolutionState fork(Node *newResolutionRoot) { + return ResolutionState{shared, newResolutionRoot}; + } +}; + +/* Class Node */ + +void Node::setName(std::string name) +{ + // Call the name change event and (afterwards!) set the new name + NameChangeEvent ev{this->name, name}; + triggerEvent(ev); this->name = std::move(name); } @@ -51,57 +199,90 @@ std::vector<std::string> Node::path() const return res; } -void Node::doResolve(std::vector<Rooted<Managed>> &res, - const std::vector<std::string> &path, Filter filter, - void *filterData, unsigned idx, VisitorSet &visited) +bool Node::resolutionAtBeginning(ResolutionState &state) +{ + return state.idx == 0; +} + +bool Node::resolve(ResolutionState &state) +{ + // Try to mark this note as visited, do nothing if already has been visited + if (state.markVisited(this)) { + // Add this node to the result if it matches the current description + if (state.matches(type())) { + state.addToResult(this); + return true; + } else { + continueResolve(state); + } + } + return false; +} + +void Node::continueResolve(ResolutionState &state) { // Do nothing in the default implementation } -int Node::resolve(std::vector<Rooted<Managed>> &res, - const std::vector<std::string> &path, Filter filter, - void *filterData, unsigned idx, VisitorSet &visited, - const std::string *alias) +bool Node::continueResolveIndex(const Index &index, ResolutionState &state) { + Rooted<Node> h = index.resolve(state.currentName()); + if (h != nullptr) { + ResolutionState advancedState = state.advance(); + return h->resolve(advancedState); + } + return false; +} + +bool Node::continueResolveCompositum(Handle<Node> h, ResolutionState &state) { - // Abort if this node was already visited for this path index - std::pair<const Node *, int> recKey = std::make_pair(this, idx); - if (visited.find(recKey) != visited.end()) { - return res.size(); + if (h->getName() == state.currentName()) { + ResolutionState advancedState = state.advance(); + return h->resolve(advancedState); + } else if (resolutionAtBeginning(state)) { + return h->resolve(state); } - visited.insert(recKey); - - // Check whether the we can continue the path - if (path[idx] == name || (alias && *alias == name)) { - // If we have reached the end of the path and the node is successfully - // tested by the filter function, add it to the result. Otherwise - // continue searching along the path - if (idx + 1 == path.size()) { - if (!filter || filter(this, filterData)) { - res.push_back(this); - } - } else { - doResolve(res, path, filter, filterData, idx + 1, visited); + return false; +} + +bool Node::continueResolveReference(Handle<Node> h, ResolutionState &state) +{ + if (resolutionAtBeginning(state)) { + ResolutionState forkedState = state.fork(this); + if (h->getName() == state.currentName()) { + ResolutionState advancedState = forkedState.advance(); + return h->resolve(advancedState); } + return h->resolve(forkedState); } + return false; +} - // Restart the search from here in order to find all possible nodes that can - // be matched to the given path - doResolve(res, path, filter, filterData, 0, visited); +std::vector<ResolutionResult> Node::resolve( + const std::vector<std::string> &path, const RttiBase &type) +{ + // Create the state variables + SharedResolutionState sharedState(path, type); + ResolutionState state(sharedState, this); - return res.size(); + // Call the internal resolve function, make sure the length of the given + // path is valid + if (path.size() > 0) { + continueResolveCompositum(this, state); + } + + // Return the results + return sharedState.result; } -std::vector<Rooted<Managed>> Node::resolve(const std::vector<std::string> &path, - Filter filter = nullptr, - void *filterData = nullptr) +std::vector<ResolutionResult> Node::resolve(const std::string &name, + const RttiBase &type) { - std::vector<Rooted<Managed>> res; - VisitorSet visited; - resolve(res, path, filter, filterData, 0, visited, nullptr); - return res; + // Place the name in a vector and call the corresponding resolve function + return resolve(std::vector<std::string>{name}, type); } /* RTTI type registrations */ const Rtti<Node> RttiTypes::Node{"Node"}; } + diff --git a/src/core/model/Node.hpp b/src/core/model/Node.hpp index a637b56..97ec16f 100644 --- a/src/core/model/Node.hpp +++ b/src/core/model/Node.hpp @@ -16,14 +16,21 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ +/** + * @file Node.hpp + * + * Contains the definition of the Node class, the base class used by all model + * classes. + * + * @author Andreas Stöckel (astoecke@techfak.uni-bielefeld.de) + */ + #ifndef _OUSIA_NODE_HPP_ #define _OUSIA_NODE_HPP_ -#include <functional> #include <map> #include <string> #include <vector> -#include <unordered_set> #include <core/common/Rtti.hpp> #include <core/managed/Managed.hpp> @@ -34,48 +41,45 @@ namespace ousia { /** - * The Node class builds the base class for any Node within the DOM graph. A - * node may either be a descriptive node (such as a domain description etc.) - * or a document element. Each node is identified by acharacteristic name and - * a parent element. Note that the node name is not required to be unique. Nodes - * without parent are considered root nodes. + * Structure describing a single result obtained from the resolution function. */ -class Node : public Managed { -public: +struct ResolutionResult { /** - * The Filter function is used when resolving names to Node instances. The - * filter tests whether the given node meets the requirements for inclusion - * in the result list. - * - * @param managed is the managed which should be tested. - * @param data is user-defined data passed to the filter. - * @return true if the node should be included in the result set, false - * otherwise. + * The actual node that was resolved. */ - using Filter = bool (*)(Handle<Managed> managed, void *data); + Rooted<Node> node; /** - * Hash functional used to convert pairs of nodes and int to hashes which - * can be used within a unordered_set. + * Root node of the subtree in which the node was found. This e.g. points to + * the Domain in which a Structure was defined or the Typesystem in which a + * Type was defined. May be nullptr. */ - struct VisitorHash { - size_t operator()(const std::pair<const Node *, int> &p) const - { - const std::hash<const Node *> nodeHash; - const std::hash<int> intHash; - return nodeHash(p.first) + 37 * intHash(p.second); - } - }; + Rooted<Node> resolutionRoot; /** - * Alias for the VisitorSet class which represents all nodes which have been - * visited in the name resolution process. The map stores pairs of node - * pointers and integers, indicating for which path start id the node has - * already been visited. + * Default constructor of the ResolutionResult class. + * + * @param node is a reference pointing at the actually found node. + * @param resolutionRoot is a reference to the root node of the subtree in + * which the node was found. */ - using VisitorSet = - std::unordered_set<std::pair<const Node *, int>, VisitorHash>; + ResolutionResult(Handle<Node> node, Handle<Node> resolutionRoot) + : node(node), resolutionRoot(resolutionRoot) + { + } +}; + +// Forward declaration +struct ResolutionState; +/** + * The Node class builds the base class for any Node within the DOM graph. A + * node may either be a descriptive node (such as a domain description etc.) + * or a document element. Each node is identified by acharacteristic name and + * a parent element. Note that the node name is not required to be unique. Nodes + * without parent are considered root nodes. + */ +class Node : public Managed { private: /** * Name of the node. As names are always looked up relative to a node, @@ -97,29 +101,142 @@ private: */ void path(std::vector<std::string> &p) const; + /** + * Returns true if the resolution process is just at the beginning (no part + * of the path has been matched yet). + * + * @param state is used internally to manage the resolution process. + */ + static bool resolutionAtBeginning(ResolutionState &state); + + /** + * Method used internally for resolving nodes with a certain name and type + * within the object graph. + * + * @param state is used internally to manage the resolution process. + * @return true if an matching element was found within this subtree, false + * otherwise. + * @return true if at least one new node has been found that matches the + * criteria given for the resolution. + */ + bool resolve(ResolutionState &state); + + /** + * Method used internally to check whether the given index has an entry + * which matches the one currently needed to continue the path. + * + * @param index is a reference to the index from which the currently active + * path element should be looked up. + * @param state is used internally to manage the resolution process. + * @return true if at least one new node has been found that matches the + * criteria given for the resolution. + */ + bool continueResolveIndex(const Index &index, ResolutionState &state); + protected: /** * Function which should be overwritten by derived classes in order to * resolve node names to a list of possible nodes. The implementations of - * this function do not need to do anything but call the "resovle" function - * of any child instance of NamedNode. + * this function do not need to do anything but call the + * continueResolveComposita() and/or continueResolveReferences() methods on + * any index or list of references and pass the resolution state to these + * methods. + * + * @param state is used internally to manage the resolution process. + */ + virtual void continueResolve(ResolutionState &state); + + /** + * Tries to advance the resolution process with the compositum pointed at + * by h. If a part of the resolution path has already been matched, only + * decends into the given node if the path can be continued. Otherwise + * always decends into the node to search for potential beginnings of the + * path. + * + * @param h is a handle at a compositum (a node the current node consists of + * or explicitly defines). + * @param state is used internally to manage the resolution process. + * @return true if at least one new node has been found that matches the + * criteria given for the resolution. + */ + bool continueResolveCompositum(Handle<Node> h, ResolutionState &state); + + /** + * Calls continueResolveCompositum() for each element in the given + * container. + * + * @param container is a container containing compositum nodes for which the + * continueResolveCompositum() method should be called. + * @param state is used internally to manage the resolution process. + * @return true if at least one new node has been found that matches the + * criteria given for the resolution. + */ + template <class T> + bool continueResolveComposita(T &container, ResolutionState &state) + { + bool res = false; + for (auto elem : container) { + res = continueResolveCompositum(elem, state) | res; + } + return res; + } + + /** + * Calls continueResolveCompositum() for each element in the given + * container. Uses the given index to speed up the resolution process. + * + * @param container is a container containing compositum nodes for which the + * continueResolveCompositum() method should be called. + * @param index is the Index instance of the given container and is used to + * speed up the resolution process. + * @param state is used internally to manage the resolution process. + * @return true if at least one new node has been found that matches the + * criteria given for the resolution. + */ + template <class T> + bool continueResolveComposita(T &container, const Index &index, + ResolutionState &state) + { + if (continueResolveIndex(index, state)) { + return true; + } else if (resolutionAtBeginning(state)) { + return continueResolveComposita(container, state); + } + return false; + } + + /** + * Tries to search for the requested node in another subtree to which a + * reference exists from this node. + * + * @param h is a handle pointing at the node in the subtree. + * @param state is used internally to manage the resolution process. + * @return true if at least one new node has been found that matches the + * criteria given for the resolution. + */ + bool continueResolveReference(Handle<Node> h, ResolutionState &state); + + /** + * Tries to search for the requested node in another subtree to which a + * reference exists from this node. * - * @param res is the result list containing all possible nodes matching the - * name specified in the path. - * @param path is a list specifying a path of node names which is meant to - * specify a certain named node. - * @param idx is the current index in the path. - * @param visited is a map which is used to prevent unwanted recursion. - * @param filter is a callback function which may check whether a certain - * node should be in the result set. If nullptr is given, all nodes matching - * the path are included. The filter function can be used to restrict the - * type of matched functions. - * @param filterData is user-defined data that should be passed to the - * filter. + * @param h is a handle pointing at the node in the subtree. + * @param state is used internally to manage the resolution process. + * @return true if at least one new node has been found that matches the + * criteria given for the resolution. */ - virtual void doResolve(std::vector<Rooted<Managed>> &res, - const std::vector<std::string> &path, Filter filter, - void *filterData, unsigned idx, VisitorSet &visited); + template <class T> + bool continueResolveReferences(T &container, ResolutionState &state) + { + if (resolutionAtBeginning(state)) { + bool res = false; + for (auto elem : container) { + res = continueResolveReference(elem, state) | res; + } + return res; + } + return false; + } public: /** @@ -158,12 +275,7 @@ public: /** * Returns the name of the node. */ - std::string getName() const { return name; } - - /** - * Returns a reference to the name of the node. - */ - const std::string &getNameRef() const { return name; } + const std::string &getName() const { return name; } /** * Specifies whether the node has a name, e.g. whether the current name is @@ -206,94 +318,41 @@ public: std::vector<std::string> path() const; /** - * Function which resolves a name path to a list of possible nodes. - * - * @param res is the result list containing all possible nodes matching the - * name specified in the path. - * @param path is a list specifying a path of node names which is meant to - * specify a certain named node. - * @param filter is a callback function which may check whether a certain - * node should be in the result set. If nullptr is given, all nodes matching - * the path are included. The filter function can be used to restrict the - * type of matched functions. - * @param filterData is user-defined data that should be passed to the - * filter. - * @param idx is the current index in the path. - * @param visited is a map which is used to prevent unwanted recursion. - * @param alias is a pointer at a string which contains an alternative name - * for this node. If nullptr is given, not such alternative name is - * provided. - * @return the number of elements in the result list. - */ - int resolve(std::vector<Rooted<Managed>> &res, - const std::vector<std::string> &path, Filter filter, - void *filterData, unsigned idx, VisitorSet &visited, - const std::string *alias); - - /** - * Function which resolves a name path to a list of possible nodes starting - * from this node. - * - * @param path is a list specifying a path of node names meant to specify a - * certain named node. - * @param filter is a callback function which may check whether a certain - * node should be in the result set. If nullptr is given, all nodes matching - * the path are included. The filter function can e.g. be used to restrict - * the type of matched functions. - * @param filterData is user-defined data that should be passed to the - * filter. - * @return a vector containing all found node references. - */ - std::vector<Rooted<Managed>> resolve(const std::vector<std::string> &path, - Filter filter, void *filterData); - - /** * Function which resolves a name path to a list of possible nodes starting * from this node. * * @param path is a list specifying a path of node names meant to specify a * certain named node. - * @return a vector containing all found node references. - */ - std::vector<Rooted<Managed>> resolve(const std::vector<std::string> &path) - { - return resolve(path, nullptr, nullptr); - } - - /** - * Function which resolves a single name to a list of possible nodes - * starting from this node. - * - * @param name is the name which should be resolved. - * @param filter is a callback function which may check whether a certain - * node should be in the result set. If nullptr is given, all nodes matching - * the path are included. The filter function can e.g. be used to restrict - * the type of matched functions. - * @param filterData is user-defined data that should be passed to the - * filter. - * @return a vector containing all found node references. + * @param type specifies the type of the node that should be located. + * @return a vector containing ResolutionResult structures which describe + * the resolved elements. */ - std::vector<Rooted<Managed>> resolve(const char *, Filter filter, - void *filterData) - { - return resolve(std::vector<std::string>{name}, filter, filterData); - } + std::vector<ResolutionResult> resolve(const std::vector<std::string> &path, + const RttiBase &type); /** * Function which resolves a single name to a list of possible nodes * starting from this node. * * @param name is the name which should be resolved. - * @return a vector containing all found node references. + * @param type specifies the type of the node that should be located. + * @return a vector containing ResolutionResult structures which describe + * the resolved elements. */ - std::vector<Rooted<Managed>> resolve(const std::string &name) - { - return resolve(std::vector<std::string>{name}, nullptr, nullptr); - } + std::vector<ResolutionResult> resolve(const std::string &name, + const RttiBase &type); }; -// TODO: Use a different listener here for updating name maps - +/** + * The NodeVector class is a vector capable of automatically maintaining an + * index used for the resolution of node names. + * + * @tparam T is the type that should be stored in the NodeVector. Must be a + * descendant of the Node class. + * @tparam Listener is the listener class that should be used to build the + * internal index. Should either be Index or a reference to (&Index) in case a + * shared index is used. + */ template <class T, class Listener = Index> class NodeVector : public ManagedGenericList<T, std::vector<Handle<T>>, @@ -303,9 +362,29 @@ public: ListAccessor<Handle<T>>, Listener>; using Base::ManagedGenericList; - Index& getIndex() { return this->listener;} + /** + * Returns the reference to the internal index. + */ + const Index &getIndex() const { return this->listener; } + + /** + * Returns the reference to the internal index. + */ + Index &getIndex() { return this->listener; } + }; +/** + * The NodeMap class is a map class capable of automatically maintaining an + * index used for the resolution of node names. + * + * @tparam K is the key type that should be stored in the NodeMap. + * @tparam T is the value type that should be stored in the NodeMap. Must be a + * descendant of the Node class. + * @tparam Listener is the listener class that should be used to build the + * internal index. Should either be Index or a reference to (&Index) in case a + * shared index is used. + */ template <class K, class T, class Listener = Index> class NodeMap : public ManagedGenericMap<K, T, std::map<K, Handle<T>>, @@ -316,7 +395,15 @@ public: MapAccessor<std::pair<K, Handle<T>>>, Listener>; using Base::ManagedGenericMap; - Index& getIndex() { return this->listener;} + /** + * Returns the reference to the internal index. + */ + const Index &getIndex() const { return this->listener; } + + /** + * Returns the reference to the internal index. + */ + Index &getIndex() { return this->listener; } }; namespace RttiTypes { diff --git a/test/core/model/NodeTest.cpp b/test/core/model/NodeTest.cpp index 1c58e2c..334a311 100644 --- a/test/core/model/NodeTest.cpp +++ b/test/core/model/NodeTest.cpp @@ -22,20 +22,15 @@ #include <core/model/Node.hpp> namespace ousia { -namespace dom { class TestNode : public Node { private: std::vector<Owned<Node>> children; protected: - void doResolve(std::vector<Rooted<Managed>> &res, - const std::vector<std::string> &path, Filter filter, - void *filterData, unsigned idx, VisitorSet &visited) override + void continueResolve(ResolutionState &state) override { - for (auto &n : children) { - n->resolve(res, path, filter, filterData, idx, visited, nullptr); - } + continueResolveComposita(children, state); } public: @@ -49,6 +44,11 @@ public: } }; +namespace RttiTypes { +const Rtti<ousia::TestNode> TestNode = + RttiBuilder("TestNode").parent(RttiTypes::Node).composedOf(&TestNode); +} + TEST(Node, isRoot) { Manager mgr; @@ -72,19 +72,21 @@ TEST(Node, simpleResolve) Rooted<TestNode> child1 = root->addChild(new TestNode(mgr, "child1")); Rooted<TestNode> child11 = child1->addChild(new TestNode(mgr, "child11")); - std::vector<Rooted<Managed>> res; - res = root->resolve(std::vector<std::string>{"root", "child1", "child11"}); - ASSERT_EQ(1, res.size()); - ASSERT_TRUE(child11 == *(res.begin())); - - res = root->resolve(std::vector<std::string>{"child1", "child11"}); - ASSERT_EQ(1, res.size()); - ASSERT_TRUE(child11 == *(res.begin())); - - res = root->resolve(std::vector<std::string>{"child11"}); - ASSERT_EQ(1, res.size()); - ASSERT_TRUE(child11 == *(res.begin())); + std::vector<ResolutionResult> res; + res = root->resolve(std::vector<std::string>{"root", "child1", "child11"}, + RttiTypes::TestNode); + ASSERT_EQ(1U, res.size()); + ASSERT_TRUE(child11 == res[0].node); + + res = root->resolve(std::vector<std::string>{"child1", "child11"}, + RttiTypes::TestNode); + ASSERT_EQ(1U, res.size()); + ASSERT_TRUE(child11 == res[0].node); + + res = + root->resolve(std::vector<std::string>{"child11"}, RttiTypes::TestNode); + ASSERT_EQ(1U, res.size()); + ASSERT_TRUE(child11 == res[0].node); } } -} |