From cb16ee372fa5d189c47176436569291f1f35891e Mon Sep 17 00:00:00 2001 From: Andreas Stöckel Date: Fri, 9 Jan 2015 13:34:27 +0100 Subject: Finished node resolution process --- src/core/model/Node.cpp | 140 ++++++++++++++++++++++++++++++++++-------------- 1 file changed, 100 insertions(+), 40 deletions(-) (limited to 'src/core/model/Node.cpp') diff --git a/src/core/model/Node.cpp b/src/core/model/Node.cpp index 518a74d..d12e92b 100644 --- a/src/core/model/Node.cpp +++ b/src/core/model/Node.cpp @@ -16,6 +16,8 @@ along with this program. If not, see . */ +#include + #include #include @@ -27,13 +29,34 @@ namespace ousia { /* Class SharedResolutionState */ +/** + * Hash functional used to convert pairs of nodes and int to hashes which + * can be used within a unordered_set. + */ +struct VisitorHash { + size_t operator()(const std::pair &p) const + { + const std::hash nodeHash; + const std::hash intHash; + return nodeHash(p.first) + 37 * intHash(p.second); + } +}; + +/** + * 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 index the node has already + * been visited. + */ +using VisitorSet = + std::unordered_set, VisitorHash>; + /** * 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. @@ -48,7 +71,7 @@ public: /** * Tracks all nodes that have already been visited. */ - std::unordered_set visited; + VisitorSet visited; /** * Current resolution result. @@ -79,7 +102,6 @@ public: * resolving Node instances by name. */ class ResolutionState { - private: /** * Constructor of the ResolutionState class. @@ -87,8 +109,7 @@ private: * @param shared is the shared, path independent state. * @param resolutionRoot is the current resolution root node. */ - ResolutionState(SharedResolutionState &shared, - int idx, + ResolutionState(SharedResolutionState &shared, int idx, Node *resolutionRoot) : shared(shared), idx(idx), resolutionRoot(resolutionRoot) { @@ -101,8 +122,12 @@ public: * @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) + ResolutionState(SharedResolutionState &shared, + Node *resolutionRoot = nullptr, bool atStartNode = true) + : shared(shared), + idx(0), + resolutionRoot(resolutionRoot), + atStartNode(atStartNode) { } @@ -123,6 +148,12 @@ public: */ Node *resolutionRoot; + /** + * Set to true if the resolution currently is at the node at which the + * resolution process was started. + */ + bool atStartNode; + /** * Adds a node to the result. * @@ -141,37 +172,42 @@ public: */ bool markVisited(Node *node) { - if (shared.visited.count(node) > 0) { + if (shared.visited.count(std::make_pair(node, idx)) > 0) { return false; } - shared.visited.insert(node); + shared.visited.insert(std::make_pair(node, idx)); return true; } /** - * Returns true if the current node matches the search criteria. + * Returns true if the search reached the end of the given path. * - * @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. + * @return true if the end of the path was reached, false otherwise. */ - bool matches(const RttiBase &type) - { - return idx == static_cast(shared.path.size()) && - type.isa(shared.type); - } + bool atEndOfPath() { return idx == static_cast(shared.path.size()); } - const std::string ¤tName() { - return shared.path[idx]; - } + /** + * Returns true if the given type matches the type given in the query. + * + * @return true if the type matches, false otherwise. + */ + bool typeMatches(const RttiBase &type) { return type.isa(shared.type); } + + const std::string ¤tName() { return shared.path[idx]; } - ResolutionState advance() { + ResolutionState advance() + { return ResolutionState{shared, idx + 1, resolutionRoot}; } - ResolutionState fork(Node *newResolutionRoot) { - return ResolutionState{shared, newResolutionRoot}; + ResolutionState fork(Node *newResolutionRoot) + { + return ResolutionState{shared, newResolutionRoot, false}; } + + bool canFollowReferences() { return idx == 0 && atStartNode; } + + bool canFollowComposita() { return idx == 0; } }; /* Class Node */ @@ -199,19 +235,29 @@ std::vector Node::path() const return res; } -bool Node::resolutionAtBeginning(ResolutionState &state) +bool Node::canFollowComposita(ResolutionState &state) { - return state.idx == 0; + return state.canFollowComposita(); +} + +bool Node::canFollowReferences(ResolutionState &state) +{ + return state.canFollowReferences(); } bool Node::resolve(ResolutionState &state) { // Try to mark this note as visited, do nothing if already has been visited if (state.markVisited(this)) { + std::cout << "visiting " << name << std::endl; + // Add this node to the result if it matches the current description - if (state.matches(type())) { - state.addToResult(this); - return true; + if (state.atEndOfPath()) { + if (state.typeMatches(type())) { + std::cout << "found match!" << std::endl; + state.addToResult(this); + return true; + } } else { continueResolve(state); } @@ -224,7 +270,8 @@ void Node::continueResolve(ResolutionState &state) // Do nothing in the default implementation } -bool Node::continueResolveIndex(const Index &index, ResolutionState &state) { +bool Node::continueResolveIndex(const Index &index, ResolutionState &state) +{ Rooted h = index.resolve(state.currentName()); if (h != nullptr) { ResolutionState advancedState = state.advance(); @@ -235,10 +282,18 @@ bool Node::continueResolveIndex(const Index &index, ResolutionState &state) { bool Node::continueResolveCompositum(Handle h, ResolutionState &state) { + // If the name of the compositum explicitly matches the current name in the + // path, advance the search and try to resolve from this position if (h->getName() == state.currentName()) { ResolutionState advancedState = state.advance(); - return h->resolve(advancedState); - } else if (resolutionAtBeginning(state)) { + if (h->resolve(advancedState)) { + return true; + } + } + + // If the name did not match, but we are at the beginning of the path, + // descend without advancing the state + if (canFollowComposita(state)) { return h->resolve(state); } return false; @@ -246,13 +301,12 @@ bool Node::continueResolveCompositum(Handle h, ResolutionState &state) bool Node::continueResolveReference(Handle h, ResolutionState &state) { - if (resolutionAtBeginning(state)) { + // We can only follow references if we currently are at the beginning of the + // path and this node is the root node + if (canFollowReferences(state)) { + std::cout << "following reference to " << h->getName() << std::endl; ResolutionState forkedState = state.fork(this); - if (h->getName() == state.currentName()) { - ResolutionState advancedState = forkedState.advance(); - return h->resolve(advancedState); - } - return h->resolve(forkedState); + return continueResolveCompositum(h, forkedState); } return false; } @@ -264,8 +318,14 @@ std::vector Node::resolve( SharedResolutionState sharedState(path, type); ResolutionState state(sharedState, this); - // Call the internal resolve function, make sure the length of the given - // path is valid + // Kickstart the resolution process by treating this very node as compositum + std::cout << "------------" << std::endl; + std::cout << "resolving: "; + for (auto s: path) { + std::cout << s << " "; + } + std::cout << " of type " << type.name << std::endl; + if (path.size() > 0) { continueResolveCompositum(this, state); } -- cgit v1.2.3