add list parsing

Change-Id: Id4be03cedd687892b6f4ae45d90afee8e2a4a43c
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 5fa1ac2..62e4261 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -47,6 +47,9 @@
 find_package(spdlog REQUIRED)
 find_package(Boost REQUIRED)
 
+# we don't need filename tracking, and we prefer to use header-only Boost
+add_definitions(-DBOOST_SPIRIT_X3_NO_FILESYSTEM)
+
 set(parser_SRCS
     src/CTree.cpp
     src/CParser.cpp
diff --git a/src/CParser.cpp b/src/CParser.cpp
index 618a721..0762468 100644
--- a/src/CParser.cpp
+++ b/src/CParser.cpp
@@ -5,10 +5,13 @@
  * Written by Václav Kubernát <kubervac@fit.cvut.cz>
  *
 */
+#include <iostream>
 #include "CParser.hpp"
 
 TooManyArgumentsException::~TooManyArgumentsException() = default;
 
+InvalidCommandException::~InvalidCommandException() = default;
+
 CParser::CParser(const CTree& tree)
     : m_tree(tree)
 {
@@ -21,13 +24,16 @@
     ParserContext ctx(m_tree);
     auto it = line.begin();
 
-    auto grammar = x3::with<parser_context_tag>(ctx)[cd];
+    boost::spirit::x3::error_handler<std::string::const_iterator> errorHandler(it, line.end(), std::cerr);
+    auto grammar =
+            x3::with<parser_context_tag>(ctx)[
+            x3::with<x3::error_handler_tag>(std::ref(errorHandler))[cd]
+    ];
+    bool result = x3::phrase_parse(it, line.end(), grammar, space, parsedCommand);
 
-    x3::phrase_parse(it, line.end(), grammar, space, parsedCommand);
-    if (it != line.end()) {
-        throw TooManyArgumentsException(std::string(it, line.end()));
+    if (!result || it != line.end()) {
+        throw InvalidCommandException(std::string(it, line.end()) + " this was left of input");
     }
 
-
     return parsedCommand;
 }
diff --git a/src/CParser.hpp b/src/CParser.hpp
index 96d4979..6db95e1 100644
--- a/src/CParser.hpp
+++ b/src/CParser.hpp
@@ -20,12 +20,19 @@
 using x3::lexeme;
 using ascii::space;
 
+class InvalidCommandException : public std::invalid_argument {
+public:
+    using std::invalid_argument::invalid_argument;
+    ~InvalidCommandException() override;
+};
+
 class TooManyArgumentsException : public std::invalid_argument {
 public:
     using std::invalid_argument::invalid_argument;
     ~TooManyArgumentsException() override;
 };
 
+
 class CParser {
 public:
     CParser(const CTree& tree);
diff --git a/src/CTree.cpp b/src/CTree.cpp
index de16250..cc014dc 100644
--- a/src/CTree.cpp
+++ b/src/CTree.cpp
@@ -6,60 +6,95 @@
  *
 */
 
+#include <iostream>
 #include "CTree.hpp"
 #include "utils.hpp"
 
 InvalidNodeException::~InvalidNodeException() = default;
 
 
-bool TreeNode::operator<(const TreeNode& b) const
-{
-    return this->m_name < b.m_name;
-}
 
 CTree::CTree()
 {
-    m_nodes.emplace("", std::unordered_map<std::string, NODE_TYPE>());
+    m_nodes.emplace("", std::unordered_map<std::string, NodeType>());
 }
 
-const std::unordered_map<std::string, NODE_TYPE>& CTree::children(const std::string& node) const
+const std::unordered_map<std::string, NodeType>& CTree::children(const std::string& name) const
 {
-    return m_nodes.at(node);
+    return m_nodes.at(name);
 }
 
-bool CTree::nodeExists(const std::string& location, const std::string& node) const
+bool CTree::nodeExists(const std::string& location, const std::string& name) const
 {
-    if (node.empty())
+    if (name.empty())
         return true;
     const auto& childrenRef = children(location);
 
-    return childrenRef.find(node) != childrenRef.end();
+    return childrenRef.find(name) != childrenRef.end();
 }
 
-bool CTree::isContainer(const std::string& location, const std::string& node) const
+bool CTree::isContainer(const std::string& location, const std::string& name) const
 {
-    if (!nodeExists(location, node))
+    if (!nodeExists(location, name))
         return false;
-    return children(location).at(node) == TYPE_CONTAINER;
+
+    return children(location).at(name).type() == typeid(schema::container);
 }
 
 void CTree::addContainer(const std::string& location, const std::string& name)
 {
-    m_nodes.at(location).emplace(name, TYPE_CONTAINER);
+    m_nodes.at(location).emplace(name, schema::container{});
 
     //create a new set of children for the new node
     std::string key = joinPaths(location, name);
-    m_nodes.emplace(key, std::unordered_map<std::string, NODE_TYPE>());
+    m_nodes.emplace(key, std::unordered_map<std::string, NodeType>());
 }
 
 
-void CTree::changeNode(const std::string& node)
+bool CTree::listHasKey(const std::string& location, const std::string& name, const std::string& key) const
 {
-    if (node.empty()) {
+    assert(isList(location, name));
+
+    const auto& child = children(location).at(name);
+    const auto& list = boost::get<schema::list>(child);
+    return list.m_keys.find(key) != list.m_keys.end();
+}
+
+const std::set<std::string>& CTree::listKeys(const std::string& location, const std::string& name) const
+{
+    assert(isList(location, name));
+
+    const auto& child = children(location).at(name);
+    const auto& list = boost::get<schema::list>(child);
+    return list.m_keys;
+}
+
+bool CTree::isList(const std::string& location, const std::string& name) const
+{
+    if (!nodeExists(location, name))
+        return false;
+    const auto& child = children(location).at(name);
+    if (child.type() != typeid(schema::list))
+        return false;
+
+    return true;
+}
+
+void CTree::addList(const std::string& location, const std::string& name, const std::set<std::string>& keys)
+{
+    m_nodes.at(location).emplace(name, schema::list{keys});
+
+    m_nodes.emplace(name, std::unordered_map<std::string, NodeType>());
+}
+
+
+void CTree::changeNode(const std::string& name)
+{
+    if (name.empty()) {
         m_curDir = "";
         return;
     }
-    m_curDir += joinPaths(m_curDir, node);
+    m_curDir += joinPaths(m_curDir, name);
 }
 std::string CTree::currentNode() const
 {
diff --git a/src/CTree.hpp b/src/CTree.hpp
index fa99df6..3e95066 100644
--- a/src/CTree.hpp
+++ b/src/CTree.hpp
@@ -8,20 +8,22 @@
 
 #pragma once
 
+#include <boost/variant.hpp>
+#include <set>
 #include <stdexcept>
 #include <unordered_map>
 
-enum NODE_TYPE {
-    TYPE_CONTAINER,
-    TYPE_LIST,
-    TYPE_LIST_ELEMENT
-};
+namespace schema {
+    struct container {
+    };
+    struct list {
+        std::set<std::string> m_keys;
+    };
+}
 
-struct TreeNode {
-    bool operator<(const TreeNode& b) const;
-    std::string m_name;
-    NODE_TYPE m_type;
-};
+
+using NodeType = boost::variant<schema::container, schema::list>;
+
 
 class InvalidNodeException : public std::invalid_argument {
 public:
@@ -38,16 +40,20 @@
 class CTree {
 public:
     CTree();
-    bool nodeExists(const std::string& location, const std::string& node) const;
+    bool nodeExists(const std::string& location, const std::string& name) const;
 
-    bool isContainer(const std::string& location, const std::string& node) const;
-    void addContainer(const std::string& location, const std::string& node);
-    void changeNode(const std::string& node);
+    bool isContainer(const std::string& location, const std::string& name) const;
+    void addContainer(const std::string& location, const std::string& name);
+    const std::set<std::string>& listKeys(const std::string& location, const std::string& name) const;
+    bool listHasKey(const std::string& location, const std::string& name, const std::string& key) const;
+    bool isList(const std::string& location, const std::string& name) const;
+    void addList(const std::string& location, const std::string& name, const std::set<std::string>& keys);
+    void changeNode(const std::string& name);
     std::string currentNode() const;
 
 private:
-    const std::unordered_map<std::string, NODE_TYPE>& children(const std::string& node) const;
+    const std::unordered_map<std::string, NodeType>& children(const std::string& name) const;
 
-    std::unordered_map<std::string, std::unordered_map<std::string, NODE_TYPE>> m_nodes;
+    std::unordered_map<std::string, std::unordered_map<std::string, NodeType>> m_nodes;
     std::string m_curDir;
 };
diff --git a/src/ast.cpp b/src/ast.cpp
index 762c7cc..87f464d 100644
--- a/src/ast.cpp
+++ b/src/ast.cpp
@@ -6,6 +6,9 @@
  *
 */
 #include "ast.hpp"
+
+InvalidKeyException::~InvalidKeyException() = default;
+
 container_::container_(const std::string& name)
     : m_name(name)
 {
@@ -16,6 +19,17 @@
     return this->m_name == b.m_name;
 }
 
+listElement_::listElement_(const std::string& listName, const std::map<std::string, std::string>& keys)
+    : m_listName(listName)
+    , m_keys(keys)
+{
+}
+
+bool listElement_::operator==(const listElement_& b) const
+{
+    return (this->m_listName == b.m_listName && this->m_keys == b.m_keys);
+}
+
 bool path_::operator==(const path_& b) const
 {
     if (this->m_nodes.size() != b.m_nodes.size())
diff --git a/src/ast.hpp b/src/ast.hpp
index 93127d5..e941a8b 100644
--- a/src/ast.hpp
+++ b/src/ast.hpp
@@ -8,9 +8,13 @@
 #pragma once
 #include <boost/spirit/home/x3.hpp>
 #include <boost/spirit/home/x3/support/ast/position_tagged.hpp>
+#include <boost/spirit/home/x3/support/utility/error_reporting.hpp>
 
 #include <boost/fusion/adapted/struct/adapt_struct.hpp>
 #include <boost/fusion/include/adapt_struct.hpp>
+#include <boost/fusion/include/std_pair.hpp>
+#include <boost/variant.hpp>
+#include <map>
 #include <vector>
 
 #include "CTree.hpp"
@@ -24,58 +28,170 @@
 using x3::char_;
 using x3::_attr;
 using x3::lexeme;
+using x3::expect;
 using ascii::space;
+using boost::fusion::operator<<;
+
+
+using keyValue_ = std::pair<std::string, std::string>;
+
+class InvalidKeyException : public std::invalid_argument {
+public:
+    using std::invalid_argument::invalid_argument;
+    ~InvalidKeyException() override;
+};
 
 struct ParserContext {
     ParserContext(const CTree& tree);
     const CTree& m_tree;
     std::string m_curPath;
+    std::string m_errorMsg;
+    std::string m_tmpListName;
+    std::set<std::string> m_tmpListKeys;
+    bool m_errorHandled = false;
 };
 
 struct parser_context_tag;
 
 struct container_ {
-    container_() {}
+    container_() = default;
     container_(const std::string& name);
 
     bool operator==(const container_& b) const;
 
-    char m_first = ' ';
     std::string m_name;
 };
 
-BOOST_FUSION_ADAPT_STRUCT(container_, m_first, m_name)
+BOOST_FUSION_ADAPT_STRUCT(container_, m_name)
+
+struct list_ {
+    std::vector<std::string> m_keys;
+};
+
+struct listElement_ {
+    listElement_() {}
+    listElement_(const std::string& listName, const std::map<std::string, std::string>& keys);
+
+    bool operator==(const listElement_& b) const;
+
+    std::string m_listName;
+    std::map<std::string, std::string> m_keys;
+};
+
+BOOST_FUSION_ADAPT_STRUCT(listElement_, m_listName, m_keys)
 
 struct path_ {
     bool operator==(const path_& b) const;
-    std::vector<container_> m_nodes;
+    std::vector<boost::variant<container_, listElement_>> m_nodes;
 };
 
 BOOST_FUSION_ADAPT_STRUCT(path_, m_nodes)
 
-struct cd_ {
+struct cd_ : x3::position_tagged {
     bool operator==(const cd_& b) const;
     path_ m_path;
 };
 
 BOOST_FUSION_ADAPT_STRUCT(cd_, m_path)
 
+struct keyValue_class {
+    template <typename T, typename Iterator, typename Context>
+    void on_success(Iterator const&, Iterator const&, T& ast, Context const& context)
+    {
+        auto& parserContext = x3::get<parser_context_tag>(context);
+        const CTree& tree = parserContext.m_tree;
+
+        if (parserContext.m_tmpListKeys.find(ast.first) != parserContext.m_tmpListKeys.end()) {
+            _pass(context) = false;
+            parserContext.m_errorMsg = "Key \"" + ast.first + "\" was entered more than once.";
+        } else if (tree.listHasKey(parserContext.m_curPath, parserContext.m_tmpListName, ast.first)) {
+            parserContext.m_tmpListKeys.insert(ast.first);
+        } else {
+            _pass(context) = false;
+            parserContext.m_errorMsg = parserContext.m_tmpListName + " is not indexed by \"" + ast.first + "\".";
+        }
+    }
+};
+struct identifier_class;
+
+struct listPrefix_class {
+    template <typename T, typename Iterator, typename Context>
+    void on_success(Iterator const&, Iterator const&, T& ast, Context const& context)
+    {
+        auto& parserContext = x3::get<parser_context_tag>(context);
+        const CTree& tree = parserContext.m_tree;
+
+        if (tree.isList(parserContext.m_curPath, ast)) {
+            parserContext.m_tmpListName = ast;
+        } else {
+            _pass(context) = false;
+        }
+    }
+};
+
+struct listSuffix_class {
+    template <typename T, typename Iterator, typename Context>
+    void on_success(Iterator const&, Iterator const&, T& ast, Context const& context)
+    {
+        auto& parserContext = x3::get<parser_context_tag>(context);
+        const CTree& tree = parserContext.m_tree;
+
+        const auto& keysNeeded = tree.listKeys(parserContext.m_curPath, parserContext.m_tmpListName);
+        std::set<std::string> keysSupplied;
+        for (const auto& it : ast)
+            keysSupplied.insert(it.first);
+
+        if (keysNeeded != keysSupplied) {
+            parserContext.m_errorMsg = "Not enough keys for " + parserContext.m_tmpListName + ". " +
+                                       "These keys were not supplied:";
+            std::set<std::string> missingKeys;
+            std::set_difference(keysNeeded.begin(), keysNeeded.end(),
+                                keysSupplied.begin(), keysSupplied.end(),
+                                std::inserter(missingKeys, missingKeys.end()));
+
+            for (const auto& it : missingKeys)
+                parserContext.m_errorMsg += " " + it;
+            parserContext.m_errorMsg += ".";
+
+            _pass(context) = false;
+        }
+    }
+};
+struct listElement_class {
+    template <typename T, typename Iterator, typename Context>
+    void on_success(Iterator const&, Iterator const&, T& ast, Context const& context)
+    {
+        auto& parserContext = x3::get<parser_context_tag>(context);
+        parserContext.m_curPath = joinPaths(parserContext.m_curPath, ast.m_listName);
+    }
+
+    template <typename Iterator, typename Exception, typename Context>
+    x3::error_handler_result on_error(Iterator&, Iterator const&, Exception const& ex, Context const& context)
+    {
+        auto& parserContext = x3::get<parser_context_tag>(context);
+        auto& error_handler = x3::get<x3::error_handler_tag>(context).get();
+        if (parserContext.m_errorHandled) // someone already handled our error
+            return x3::error_handler_result::fail;
+
+        parserContext.m_errorHandled = true;
+
+        std::string message = parserContext.m_errorMsg;
+        error_handler(ex.where(), message);
+        return x3::error_handler_result::fail;
+    }
+};
 
 struct container_class {
     template <typename T, typename Iterator, typename Context>
     void on_success(Iterator const&, Iterator const&, T& ast, Context const& context)
     {
-        ast.m_name = ast.m_first + ast.m_name;
         auto& parserContext = x3::get<parser_context_tag>(context);
         const auto& tree = parserContext.m_tree;
 
         if (tree.isContainer(parserContext.m_curPath, ast.m_name)) {
-            if (!parserContext.m_curPath.empty()) {
-                parserContext.m_curPath += '/';
-            }
-            parserContext.m_curPath += ast.m_name;
+            parserContext.m_curPath = joinPaths(parserContext.m_curPath, ast.m_name);
         } else {
-            throw InvalidNodeException("No container with the name \"" + ast.m_name + "\" in \"" + parserContext.m_curPath + "\"");
+            _pass(context) = false;
         }
     }
 };
@@ -92,28 +208,64 @@
     void on_success(Iterator const&, Iterator const&, T&, Context const&)
     {
     }
+
+    template <typename Iterator, typename Exception, typename Context>
+    x3::error_handler_result on_error(Iterator&, Iterator const&, Exception const& x, Context const& context)
+    {
+        auto& parserContext = x3::get<parser_context_tag>(context);
+        auto& error_handler = x3::get<x3::error_handler_tag>(context).get();
+        std::string message = "This isn't a list or a container or nothing.";
+        if (parserContext.m_errorHandled) // someone already handled our error
+            return x3::error_handler_result::fail;
+
+        parserContext.m_errorHandled = true;
+        error_handler(x.where(), message);
+        return x3::error_handler_result::fail;
+    }
 };
 
 
+x3::rule<keyValue_class, keyValue_> const keyValue = "keyValue";
+x3::rule<identifier_class, std::string> const identifier = "identifier";
+x3::rule<listPrefix_class, std::string> const listPrefix = "listPrefix";
+x3::rule<listSuffix_class, std::vector<keyValue_>> const listSuffix = "listSuffix";
+x3::rule<listElement_class, listElement_> const listElement = "listElement";
 x3::rule<container_class, container_> const container = "container";
 x3::rule<path_class, path_> const path = "path";
 x3::rule<cd_class, cd_> const cd = "cd";
 
 
-auto const identifier =
+auto const keyValue_def =
+    lexeme[+alnum >> '=' >> +alnum];
+
+auto const identifier_def =
     lexeme[
         ((alpha | char_("_")) >> *(alnum | char_("_") | char_("-") | char_(".")))
     ];
 
+auto const listPrefix_def =
+    identifier >> '[';
+
+auto const listSuffix_def =
+    +keyValue > ']';
+
+auto const listElement_def =
+   listPrefix > listSuffix;
+
 auto const container_def =
     identifier;
 
 auto const path_def =
-    container % '/';
+    (container | listElement) % '/';
 
 auto const cd_def =
-    lit("cd") >> path >> x3::eoi;
+    lit("cd") > path >> x3::eoi;
 
+BOOST_SPIRIT_DEFINE(keyValue)
+BOOST_SPIRIT_DEFINE(identifier)
+BOOST_SPIRIT_DEFINE(listPrefix)
+BOOST_SPIRIT_DEFINE(listSuffix)
+BOOST_SPIRIT_DEFINE(listElement)
 BOOST_SPIRIT_DEFINE(container)
 BOOST_SPIRIT_DEFINE(path)
 BOOST_SPIRIT_DEFINE(cd)
diff --git a/tests/cd.cpp b/tests/cd.cpp
index 39487a3..376e74c 100644
--- a/tests/cd.cpp
+++ b/tests/cd.cpp
@@ -20,56 +20,120 @@
     tree.addContainer("b", "b2");
     tree.addContainer("a/a2", "a3");
     tree.addContainer("b/b2", "b3");
-
+    tree.addList("", "list", {"number"});
+    tree.addContainer("list", "contInList");
+    tree.addList("", "twoKeyList", {"number", "name"});
     CParser parser(tree);
-    cd_ expected;
-
     std::string input;
 
-    SECTION("basic cd parsing")
+    SECTION("valid input")
     {
-        SECTION("a")
+        cd_ expected;
+
+        SECTION("container")
         {
-            input = "cd a";
-            expected.m_path.m_nodes.push_back(container_("a"));
+            SECTION("a")
+            {
+                input = "cd a";
+                expected.m_path.m_nodes.push_back(container_("a"));
+            }
+
+            SECTION("b")
+            {
+                input = "cd b";
+                expected.m_path.m_nodes.push_back(container_("b"));
+            }
+
+            SECTION("a/a2")
+            {
+                input = "cd a/a2";
+                expected.m_path.m_nodes.push_back(container_("a"));
+                expected.m_path.m_nodes.push_back(container_("a2"));
+            }
+
+            SECTION("b/b2")
+            {
+                input = "cd b/b2";
+                expected.m_path.m_nodes.push_back(container_("b"));
+                expected.m_path.m_nodes.push_back(container_("b2"));
+            }
+
         }
 
-        SECTION("b")
+        SECTION("list elements")
         {
-            input = "cd b";
-            expected.m_path.m_nodes.push_back(container_("b"));
+            SECTION("list[number=1]")
+            {
+                input = "cd list[number=1]";
+                auto keys = std::map<std::string, std::string>{
+                        {"number", "1"}
+                };
+                expected.m_path.m_nodes.push_back(listElement_("list", keys));
+            }
+
+            SECTION("list[number=1]/contInList")
+            {
+                input = "cd list[number=1]/contInList";
+                auto keys = std::map<std::string, std::string>{
+                        {"number", "1"}};
+                expected.m_path.m_nodes.push_back(listElement_("list", keys));
+                expected.m_path.m_nodes.push_back(container_("contInList"));
+            }
+
+            SECTION("twoKeyList[number=4 name=abcd]")
+            {
+                input = "cd twoKeyList[number=4 name=abcd]";
+                auto keys = std::map<std::string, std::string>{
+                        {"number", "4"},
+                        {"name", "abcd"}};
+                expected.m_path.m_nodes.push_back(listElement_("twoKeyList", keys));
+            }
+
         }
-
-
-        SECTION("a/a2")
-        {
-            input = "cd a/a2";
-            expected.m_path.m_nodes.push_back(container_("a"));
-            expected.m_path.m_nodes.push_back(container_("a2"));
-        }
-
-        SECTION("b/b2")
-        {
-            input = "cd b/b2";
-            expected.m_path.m_nodes.push_back(container_("b"));
-            expected.m_path.m_nodes.push_back(container_("b2"));
-        }
-
         cd_ command = parser.parseCommand(input);
         REQUIRE(command == expected);
     }
-
-    SECTION("InvalidNodeException")
+    SECTION("invalid input")
     {
-        SECTION("x")
+        SECTION("invalid identifiers")
         {
-            input = "cd x";
-        }
+            SECTION("nonexistent")
+            {
+                input = "cd nonexistent";
+                REQUIRE_THROWS(parser.parseCommand(input));
+            }
 
-        SECTION("a/x")
-        {
-            input = "cd a/x";
+            SECTION("nonexistent/lol")
+            {
+                input = "cd nonexistent/lol";
+                REQUIRE_THROWS(parser.parseCommand(input));
+            }
         }
-        REQUIRE_THROWS_AS(parser.parseCommand(input), InvalidNodeException);
+        SECTION("invalid list key identifiers")
+        {
+            SECTION("twoKeyList[invalidKey=4]")
+            {
+                input = "cd twoKeyList[invalidKey=4]";
+                REQUIRE_THROWS(parser.parseCommand(input));
+            }
+
+            SECTION("twoKeyList[number=4 number=5]")
+            {
+                input = "cd twoKeyList[number=4 number=5]";
+                REQUIRE_THROWS(parser.parseCommand(input));
+            }
+
+            SECTION("twoKeyList[number=4 name=lol number=7]")
+            {
+                input = "cd twoKeyList[number=4 name=lol number=7]";
+                REQUIRE_THROWS(parser.parseCommand(input));
+            }
+
+            SECTION("twoKeyList[number=4]")
+            {
+                input = "cd twoKeyList[number=4]";
+                REQUIRE_THROWS(parser.parseCommand(input));
+            }
+        }
     }
 }