diff options
Diffstat (limited to 'src/core/model/Node.hpp')
| -rw-r--r-- | src/core/model/Node.hpp | 351 |
1 files changed, 219 insertions, 132 deletions
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 { |