diff options
| -rw-r--r-- | CMakeLists.txt | 1 | ||||
| -rw-r--r-- | src/core/parser/ParserState.cpp | 79 | ||||
| -rw-r--r-- | src/core/parser/ParserState.hpp | 91 | ||||
| -rw-r--r-- | test/core/parser/ParserStateTest.cpp | 77 |
4 files changed, 247 insertions, 1 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt index 04af853..94c89dc 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -259,6 +259,7 @@ IF(TEST) test/core/model/TypesystemTest test/core/parser/ParserScopeTest test/core/parser/ParserStackTest + test/core/parser/ParserStateTest test/core/resource/ResourceLocatorTest test/core/resource/ResourceRequestTest # test/core/script/FunctionTest diff --git a/src/core/parser/ParserState.cpp b/src/core/parser/ParserState.cpp index b0b02d2..9d3aa7e 100644 --- a/src/core/parser/ParserState.cpp +++ b/src/core/parser/ParserState.cpp @@ -25,10 +25,12 @@ namespace ousia { ParserState::ParserState() : elementHandler(nullptr), childHandler(nullptr) {} ParserState::ParserState(ParserStateSet parents, Arguments arguments, + RttiSet createdNodeTypes, HandlerConstructor elementHandler, HandlerConstructor childHandler) : parents(parents), arguments(arguments), + createdNodeTypes(createdNodeTypes), elementHandler(elementHandler), childHandler(childHandler) { @@ -65,6 +67,18 @@ ParserStateBuilder &ParserStateBuilder::arguments(const Arguments &arguments) return *this; } +ParserStateBuilder &ParserStateBuilder::createdNodeType(const Rtti *type) +{ + state.createdNodeTypes = RttiSet{type}; + return *this; +} + +ParserStateBuilder &ParserStateBuilder::createdNodeTypes(const RttiSet &types) +{ + state.createdNodeTypes = types; + return *this; +} + ParserStateBuilder &ParserStateBuilder::elementHandler( HandlerConstructor elementHandler) { @@ -81,6 +95,71 @@ ParserStateBuilder &ParserStateBuilder::childHandler( const ParserState &ParserStateBuilder::build() const { return state; } +/* Class ParserStateDeductor */ + +ParserStateDeductor::ParserStateDeductor( + std::vector<const Rtti *> signature, + std::vector<const ParserState *> states) + : tbl(signature.size()), + signature(std::move(signature)), + states(std::move(states)) +{ +} + +bool ParserStateDeductor::isActive(size_t d, const ParserState *s) +{ + // Lookup the "active" state of (d, s), if it was not already set + // (e.second is true) we'll have to calculate it + auto e = tbl[d].emplace(s, false); + bool &res = e.first->second; + if (!e.second) { + return res; + } + + // Check whether this node is generative (may have produced the Node + // described by the current Signature element) + bool isGenerative = signature[d]->isOneOf(s->createdNodeTypes); + + if (isGenerative && d == 0) { + // End of recursion -- the last signature element is reached and the + // node was generative + res = true; + } else { + // Try repetition of this node + if (isGenerative && isActive(d - 1, s)) { + res = true; + } else { + // Check whether any of the parent nodes were active -- either for + // the previous element (if this one is generative) or for the + // current element (assuming this node was not generative) + for (const ParserState *parent : s->parents) { + if ((isGenerative && isActive(d - 1, parent)) || + isActive(d, parent)) { + res = true; + break; + } + } + } + } + + return res; +} + +std::vector<const ParserState *> ParserStateDeductor::deduce() +{ + std::vector<const ParserState *> res; + if (!signature.empty()) { + const size_t D = signature.size(); + for (auto s : states) { + if (signature[D - 1]->isOneOf(s->createdNodeTypes) && + isActive(D - 1, s)) { + res.push_back(s); + } + } + } + return res; +} + /* Constant initializations */ namespace ParserStates { diff --git a/src/core/parser/ParserState.hpp b/src/core/parser/ParserState.hpp index 81e118d..43b8035 100644 --- a/src/core/parser/ParserState.hpp +++ b/src/core/parser/ParserState.hpp @@ -65,6 +65,13 @@ struct ParserState { Arguments arguments; /** + * Set containing the types of the nodes that may be created in this + * ParserState. This information is needed for Parsers to reconstruct the + * current ParserState from a given ParserScope when a file is included. + */ + RttiSet createdNodeTypes; + + /** * Pointer at a function which creates a new concrete Handler instance for * the elements described by this state. May be nullptr in which case no * handler instance is created. @@ -90,6 +97,10 @@ struct ParserState { * @param parents is a vector containing all possible parent states. * @param arguments is a descriptor of arguments that should be passed to * the handler. + * @param createdNodeTypes is a set containing the types of the nodes tha + * may be created in this ParserState. This information is needed for + * Parsers to reconstruct the current ParserState from a given ParserScope + * when a file is included. * @param elementHandler is a pointer at a function which creates a new * concrete Handler instance for the elements described by this state. May * be nullptr in which case no handler instance is created. @@ -99,6 +110,7 @@ struct ParserState { * allowed. */ ParserState(ParserStateSet parents, Arguments arguments = Arguments{}, + RttiSet createdNodeTypes = RttiSet{}, HandlerConstructor elementHandler = nullptr, HandlerConstructor childHandler = nullptr); @@ -164,6 +176,26 @@ public: ParserStateBuilder &arguments(const Arguments &arguments); /** + * Sets the Node types this state may produce to the given Rtti descriptor. + * + * @param type is the Rtti descriptor of the Type that may be produced by + * this state. + * @return a reference at this ParserStateBuilder instance for method + * chaining. + */ + ParserStateBuilder &createdNodeType(const Rtti *type); + + /** + * Sets the Node types this state may produce to the given Rtti descriptors. + * + * @param types is a set of Rtti descriptors of the Types that may be + * produced by this state. + * @return a reference at this ParserStateBuilder instance for method + * chaining. + */ + ParserStateBuilder &createdNodeTypes(const RttiSet &types); + + /** * Sets the constructor for the element handler. The constructor creates a * new concrete Handler instance for the elements described by this state. * May be nullptr in which case no handler instance is created (this is @@ -199,6 +231,64 @@ public: }; /** + * Class used to deduce the ParserState a Parser is currently in based on the + * types of the Nodes that currently are on the ParserStack. Uses dynamic + * programming in order to solve this problem. + */ +class ParserStateDeductor { +public: + /** + * Type containing the dynamic programming table. + */ + using Table = std::vector<std::unordered_map<const ParserState *, bool>>; + +private: + /** + * Dynamic programming table. + */ + Table tbl; + + /** + * Signature given in the constructor. + */ + const std::vector<const Rtti *> signature; + + /** + * List of states that should be checked for being active. + */ + const std::vector<const ParserState *> states; + + /** + * Used internally to check whether the given parser stack s may have been + * active for signature element d. + * + * @param d is the signature element. + * @param s is the parser state. + * @return true if the the given ParserState may have been active. + */ + bool isActive(size_t d, const ParserState *s); + +public: + /** + * Constructor of the ParserStateDeductor class. + * + * @param signature a Node type signature describing the types of the nodes + * which currently reside on e.g. the ParserScope stack. + * @param states is a list of states that should be checked. + */ + ParserStateDeductor(std::vector<const Rtti *> signature, + std::vector<const ParserState *> states); + + /** + * Selects all active states from the given states. Only considers those + * states that may have produced the last signature element. + * + * @return a list of states that may actually have been active. + */ + std::vector<const ParserState *> deduce(); +}; + +/** * The ParserStates namespace contains all the global state constants used * in the ParserStack class. */ @@ -213,7 +303,6 @@ extern const ParserState All; */ extern const ParserState None; } - } #endif /* _OUSIA_PARSER_STATE_HPP_ */ diff --git a/test/core/parser/ParserStateTest.cpp b/test/core/parser/ParserStateTest.cpp new file mode 100644 index 0000000..91d8dcd --- /dev/null +++ b/test/core/parser/ParserStateTest.cpp @@ -0,0 +1,77 @@ +/* + Ousía + Copyright (C) 2014, 2015 Benjamin Paaßen, Andreas Stöckel + + This program is free software: you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program. If not, see <http://www.gnu.org/licenses/>. +*/ + +#include <gtest/gtest.h> + +#include <core/common/Rtti.hpp> +#include <core/parser/ParserState.hpp> + +namespace ousia { + +static const Rtti t1; +static const Rtti t2; +static const Rtti t3; +static const Rtti t4; +static const Rtti t5; + +static const ParserState s1 = ParserStateBuilder().createdNodeType(&t1); +static const ParserState s2a = + ParserStateBuilder().parent(&s1).createdNodeType(&t2); +static const ParserState s2b = + ParserStateBuilder().parent(&s1).createdNodeType(&t2); +static const ParserState s3 = + ParserStateBuilder().parents({&s2a, &s1}).createdNodeType(&t3); +static const ParserState s4 = + ParserStateBuilder().parent(&s3).createdNodeType(&t4); +static const ParserState s5 = + ParserStateBuilder().parent(&s2b).createdNodeType(&t5); + +TEST(ParserStateDeductor, deduce) +{ + using Result = std::vector<const ParserState *>; + using Signature = std::vector<const Rtti *>; + std::vector<const ParserState *> states{&s1, &s2a, &s2b, &s3, &s4, &s5}; + + // Should not crash on empty signature + ASSERT_EQ(Result{}, ParserStateDeductor(Signature{}, states).deduce()); + + // Try repeating signature elements + ASSERT_EQ(Result({&s1}), + ParserStateDeductor(Signature({&t1}), states).deduce()); + ASSERT_EQ(Result({&s1}), + ParserStateDeductor(Signature({&t1, &t1}), states).deduce()); + ASSERT_EQ(Result({&s1}), + ParserStateDeductor(Signature({&t1, &t1, &t1}), states).deduce()); + + // Go to another state + ASSERT_EQ(Result({&s2a, &s2b}), + ParserStateDeductor(Signature({&t1, &t1, &t2}), states).deduce()); + ASSERT_EQ(Result({&s4}), + ParserStateDeductor(Signature({&t1, &t3, &t4}), states).deduce()); + + // Skip one state + ASSERT_EQ(Result({&s4}), + ParserStateDeductor(Signature({&t2, &t4}), states).deduce()); + + // Impossible signature + ASSERT_EQ(Result({}), + ParserStateDeductor(Signature({&t4, &t5}), states).deduce()); + +} +} + |