3
\$\begingroup\$

I am writing a parser. To build up the tree, I need to find the correct type for my node based on text from my language input file. Right now, I have a map from a string (the node name) to a factory function which returns the correct type. Is there any way I can make this more simple/idiomatic when calling make shared?

Anything else I can do more idiomatically or with a better architecture is appreciated too.

abstract_node.hpp

#pragma once

#include <memory>
#include <vector>
#include <utility>

namespace ql::parser {
    class AbstractNode : protected std::enable_shared_from_this<AbstractNode> {
    public:
        typedef std::vector<std::shared_ptr<AbstractNode>> ChildrenRef;
        typedef std::weak_ptr<AbstractNode> ParentRef;
    protected:
        ChildrenRef m_Children;
        ParentRef m_Parent;
    public:
        explicit AbstractNode(ParentRef parent) : m_Parent(std::move(parent)) {}

        void addChild(std::shared_ptr<AbstractNode> const& node);
    };
}

abstract_node_with_descriptor.hpp

#pragma once

#include <parser/node/parse_node.hpp>

namespace ql::parser {
    class ParseWithDescriptorNode : public ParseNode {
    protected:
        std::string_view m_InnerBody;
    public:
        ParseWithDescriptorNode(std::string&& body, std::string_view const& innerBody, std::vector<std::string>&& tokens, ParentRef const& parent)
                : ParseNode(std::move(body), std::move(tokens), parent), m_InnerBody(innerBody) {
        }
    };
}

parser.hpp

#pragma once

#include <boost/program_options/variables_map.hpp>

#include <parser/node/master_node.hpp>
#include <parser/node/structure/parse_with_descriptor_node.hpp>

namespace po = boost::program_options;

namespace ql::parser {
    class Parser {
    private:
        using NodeFactory = std::function<std::shared_ptr<ParseWithDescriptorNode>(std::string&&, std::string_view const&, std::vector<std::string>&&,
                                                                                   AbstractNode::ParentRef)>;

        std::map<std::string, NodeFactory> m_NamesToNodes;

        template<typename TNode>
        void registerNode(std::string_view nodeName) {
            // TODO use forwarding?
            m_NamesToNodes.emplace(nodeName, [](auto&& block, auto const& body, auto&& tokens, auto parent) {
                auto node = std::make_shared<TNode>(std::forward<decltype(block)>(block), body, std::forward<decltype(tokens)>(tokens), parent);
                node->parse();
                return node;
            });
        }

        std::shared_ptr<AbstractNode> getNode(std::string const& nodeName,
                                              std::string&& blockWithInfo, std::string_view const& innerBlock, std::vector<std::string>&& tokens,
                                              AbstractNode::ParentRef parent);

        void recurseNodes(std::string_view code, std::weak_ptr<AbstractNode> const& parent, int depth = 0);

    public:
        Parser();

        std::shared_ptr<MasterNode> parse(po::variables_map& options);

        std::shared_ptr<MasterNode> getNodes(std::string code);
    };
}

parser.cpp

#include "parser.hpp"

#include <utility>
#include <iomanip>
#include <iostream>

#include <boost/algorithm/string/split.hpp>
#include <boost/algorithm/string/trim_all.hpp>
#include <boost/range/algorithm_ext/erase.hpp>
#include <boost/algorithm/string/predicate.hpp>
#include <boost/program_options/variables_map.hpp>
#include <boost/algorithm/string/classification.hpp>

#include <util/read.hpp>
#include <util/terminal_color.hpp>
#include <parser/node/structure/package_node.hpp>
#include <parser/node/structure/def_func_node.hpp>
#include <parser/node/structure/impl_func_node.hpp>

namespace ql::parser {
    Parser::Parser() {
        registerNode<PackageNode>("pckg");
        registerNode<DefineFunctionNode>("def");
        registerNode<ImplementFunctionNode>("impl");
        registerNode<ParseWithDescriptorNode>("default");
    }

    std::shared_ptr<MasterNode> Parser::parse(po::variables_map& options) {
        auto sources = options["input"].as<std::vector<std::string>>();
        std::string sourceFileName = sources[0];
        std::cout << sourceFileName << std::endl;
        auto src = util::readAllText(sourceFileName);
        auto node = getNodes(src.value());
        return node;
    }

    std::shared_ptr<AbstractNode> Parser::getNode(std::string const& nodeName,
                                                  std::string&& blockWithInfo, std::string_view const& innerBlock, std::vector<std::string>&& tokens,
                                                  AbstractNode::ParentRef parent) {
        // Check if we have a generator function that can make this requested node, or else use default
        auto it = m_NamesToNodes.find(nodeName);
        NodeFactory& nodeFactoryFunc = it == m_NamesToNodes.end() ? m_NamesToNodes["default"] : it->second;
        // Give ownership of copied code slice to this node. View of inner block still references original memory since we move it instead of copying
        auto node = nodeFactoryFunc(std::move(blockWithInfo), innerBlock, std::move(tokens), std::move(parent));
        return node;
    }

    std::shared_ptr<MasterNode> Parser::getNodes(std::string code) {
        auto parent = std::make_shared<MasterNode>();
        boost::remove_erase_if(code, boost::is_any_of("\n\r"));
        recurseNodes(code, parent);
        return parent;
    }

    void Parser::recurseNodes(std::string_view code, std::weak_ptr<AbstractNode> const& parent, int depth) {
        auto level = 0;
        auto blockInfoStart = 0ul, blockStart = 0ul;
        for (auto i = 0ul; i < code.size(); i++) {
            char c = code[i];
            if (c == '{') {
                if (level++ == 0) {
                    blockStart = i + 1ul;
                }
            } else if (c == '}') {
                if (--level == 0) {
                    auto blockInfoSize = i - blockInfoStart + 1ul;
                    std::string blockWithInfo(code.substr(blockInfoStart, blockInfoSize));

                    // Split by tabs and spaces into tokens, which we use to find what type of node to create
                    std::vector<std::string> tokens;
                    auto deliminator = boost::is_any_of("\t ");
                    boost::split(tokens, blockWithInfo, deliminator, boost::token_compress_on);
                    // Remove first and last blank tokens if they exist
                    boost::trim_all_if(tokens, [](auto const& token) { return token.empty(); });

                    std::string const& nodeName = tokens[0ul]; // TODO do more checks as opposed to just taking first
                    std::cout << KGRN << std::setw(7) << nodeName << RST << " → " << blockWithInfo << FBLU("#") << std::endl;

                    // Find inner block
                    auto blockContentStart = blockStart, blockContentSize = i - blockContentStart;
                    std::string_view blockContents = std::string_view(blockWithInfo).substr(blockContentStart - blockInfoStart, blockContentSize);
                    std::cout << blockContents << FRED("$") << std::endl;
                    auto child = getNode(nodeName, std::move(blockWithInfo), blockContents, std::move(tokens), parent);
                    // Add children to parent node, parent node is owning via a shared pointer
                    parent.lock()->addChild(child);

                    // Recurse on the inner contents of the block so that each node added is for one block only
                    recurseNodes(code.substr(blockContentStart, blockContentSize), child, depth + 1);
                    blockInfoStart = i + 1;
                }
            }
        }
    }
}
\$\endgroup\$
0

2 Answers 2

Reset to default
2
\$\begingroup\$

AbstractNode must have a virtual destructor (if we have child classes, we'll be deleting them from a pointer to the base class).

It doesn't look like we require shared ownership of nodes, so we don't need to use std::shared_ptr. The parent node owns its children, and children have a non-owning pointer to the parent.

We can therefore use unique_ptr for storing the children, and a raw pointer to refer to the parent. This makes the code quite a bit simpler.

For "sink" arguments (function arguments that we want to copy and store internally), it's best to take them by value. The current code requires r-value references, which would force the user to do a copy themselves outside the class if they don't want to move something, which is very awkward.

So we should be doing:

    ParseWithDescriptorNode(std::string body, std::string_view innerBody, std::vector<std::string> tokens, ParentRef parent)
            : ParseNode(std::move(body), std::move(tokens), std::move(parent)), m_InnerBody(std::move(innerBody)) {
    }

(There's no point moving the string_view, but it's consistent, and there's no real downside).

Since we specify exact types here:

    using NodeFactory = std::function<std::shared_ptr<ParseWithDescriptorNode>(std::string&&, std::string_view const&, std::vector<std::string>&&, AbstractNode::ParentRef)>;

It's kinda weird to use a generic lambda here:

        m_NamesToNodes.emplace(nodeName, [](auto&& block, auto const& body, auto&& tokens, auto parent) {
            auto node = std::make_shared<TNode>(std::forward<decltype(block)>(block), body, std::forward<decltype(tokens)>(tokens), parent);
            node->parse();
            return node;
        });

I guess the generic lambda is to get perfect forwarding working, but it's a bit confusing.

As above, the specification of std::string&& and std::vector<std::string>&& unnecessarily require r-value references, which isn't ideal.

    std::string_view m_InnerBody;

We need to be careful about keeping a string_view around as a class member. It looks like this will refer to a local variable in recurseNodes, which will go out of scope and become invalid well before the Node's lifetime ends. There are two things we could do to improve things:

Do everything we need to do with the string data in the constructor (i.e. call parse() in the constructor, instead of as a separate step).

Store indices instead (since an index remains valid and usable independent of the lifetime of the string).

(Unlike the other answer) I personally like the use of auto for declaring local variables. It makes declarations instantly recognizable and uniform, and puts the focus on the semantics of the object (value, &, const&), instead unnecessarily repeating the type.

We can improve things a bit though:

  • Use auto consistently for every local variable.
  • Put constness after the auto, so auto is always the first word.
  • Put the type on the right-hand side of the declaration if necessary.
  • Never declare multiple variables in one line using commas.

e.g.

    auto sources = options["input"].as<std::vector<std::string>>();
    auto const& firstFile = sources.front();
    ...
        auto c = char{ code[i] };
    ...
                auto blockWithInfo = std::string(code.substr(blockInfoStart, blockInfoSize));

Using boost is fine, but it may be worth writing our own split function using std::string_view. It looks like we could do all the parsing without any string copies at all.

\$\endgroup\$
3
\$\begingroup\$

Maintainability
You may be the only programmer on this project, but if you work on larger projects other people may have to maintain the code. Code like this:

namespace po = boost::program_options;

makes the code much harder to maintain. That is especially true when that code is in a header file such as parser.hpp. The previous code is the equivalent of putting

using namespace std;

into a header file. How is someone that has to maintain the code going to find it? In 3 years even you may not remember this was done.

Portability
While

#pragma once

is widely supported, it has never been added to the C++ programming standard. Therefore there may actually be compilers that don't implement it. To ensure a header file is only included once it may be better to use

#ifndef H_HEADER_NAME
#define H_HEADER_NAME

/* contents of header */

#endif /* H_HEADER_NAME */

because this will always be portable.

Abuse of auto
C++ is a typed language, not a scripting language. The auto type declaration is very useful, especially in ranged loops, however, declaring almost every variable in a function as auto is an abuse of the feature. for maintainers of the code it might be better if most of the type declarations in void Parser::recurseNodes(std::string_view code, std::weak_ptr<AbstractNode> const& parent, int depth) used explicit type declarations rather than auto.

\$\endgroup\$
4
  • \$\begingroup\$ @Zeta 1) Is there anything else you don't like in the answer. 2) I can remove the iterator section completely, but I'm not going to refactor the code. The entire function is a key portion of a recursive descent parser and some of the data types in the function aren't clear. \$\endgroup\$ Commented Sep 14, 2019 at 20:21
  • \$\begingroup\$ @Zeta done, no more iterator section. \$\endgroup\$ Commented Sep 14, 2019 at 20:49
  • 1
    \$\begingroup\$ Hey, thanks for your comments. I do see now how I abused the auto keyword. My original intention was to use it only where you can interpret the type based on what is being assigned. An example would be like the result of make_shared<Type> since it can be easily seen there. Or with 0ul, type is unsigned long. I guess CLion has spoiled me there. I used the namespace using since it is what is demonstrated in the Boost docu, I was just trying to make it less verbose. \$\endgroup\$ Commented Sep 14, 2019 at 22:28
  • 1
    \$\begingroup\$ Also, namespace po = boost::program_options is a bit different from using namespace std because in the latter all functions/stuff is opened up to the global namespace, which could cause more potential collisions versus just po. I guess the idea was that many code editors now have a click to follow, so people could easily see that it maps to boost::program_options. \$\endgroup\$ Commented Sep 14, 2019 at 22:30

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.