4
\$\begingroup\$

In my answer to string_view tokenizer function template I suggested that a flexible tokeniser would yield a Range that could be iterated over. This is my implementation of such a tokeniser.

#include <concepts>
#include <cstddef>
#include <functional>
#include <iterator>
#include <ranges>
#include <string_view>
#include <utility>

namespace parser
{
    template<typename T>
    using search_func = std::function<typename T::size_type(T)>;

    template<typename StringView>
    class token_iter
    {
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = StringView;
        using reference = value_type const&;
        using pointer = value_type const*;
        using difference_type = std::ptrdiff_t;

        using token_search = search_func<value_type>;

    private:
        value_type input = {};

        token_search find_start = {};
        token_search find_end = {};

        value_type current_token = {};

    public:
        token_iter(token_search find_start, token_search find_end,
                   value_type input = {})
            : input{input},
              find_start{find_start},
              find_end{find_end},
              current_token{get_next()}
        {}
        token_iter() = default;
        ~token_iter() = default;

        token_iter(token_iter const&) = default;
        token_iter(token_iter&&) = default;
        token_iter& operator=(token_iter const&) = default;
        token_iter& operator=(token_iter&&) = default;

        reference& operator*()
        {
            return current_token;
        }

        pointer operator->()
        {
            return &current_token;
        }

        token_iter& operator++()
        {
            current_token = get_next();
            return *this;
        }

        token_iter operator++(int)
        {
            auto const it = *this;
            ++*this;
            return it;
        }

        // it's undefined to compare iterators into different strings
        bool operator==(token_iter const& other) const
        {
            return current_token.empty() ? other.current_token.empty()
                :  current_token.begin() == other.current_token.begin();
        }

    private:
        value_type get_next()
        {
            auto start = find_start(input);
            if (start > input.size()) {
                // not found
                return {};
            }
            input = input.substr(start);
            auto end = find_end(input);
            if (end > input.size()) {
                return std::exchange(input, {});
            }

            auto token = input.substr(0, end);
            input = input.substr(end);
            return token;
        }
    };


    template<typename CharT, typename Traits>
    auto as_string_view(std::basic_string_view<CharT, Traits> s)
    {
        return s;
    }

    template<typename CharT, typename Traits>
    auto as_string_view(std::basic_string<CharT, Traits> const& s)
    {
        return std::basic_string_view<CharT, Traits>{s};
    }

    template<typename CharT, typename Traits = std::char_traits<CharT>>
    auto as_string_view(CharT const* s)
    {
        return std::basic_string_view<CharT, Traits>{s};
    }


    template<typename StringView>
    auto tokenize(search_func<StringView> find_start, search_func<StringView> find_end,
                  StringView input)
    {
        auto iter = token_iter{find_start, find_end, StringView(input)};
        decltype(iter) sentinel = {};
        return std::ranges::subrange{iter, sentinel};
    }

    auto tokenize(auto delim_chars, auto input)
    {
        auto delim_chars_view = as_string_view(delim_chars);
        auto input_view = as_string_view(input);
        using StringView = decltype(input_view);

        search_func<StringView> find_start =
            [delim_chars_view](auto in) {
                return in.find_first_not_of(delim_chars_view);
            };
        search_func<StringView> find_end =
            [delim_chars_view](auto in) {
                return in.find_first_of(delim_chars_view);
            };
        return tokenize(find_start, find_end, input_view);
    }
}

I wrote these unit tests (slightly cluttered by the demand of EXPECT_EQ to have arguments of the same type):

#include <gtest/gtest.h>

using parser::tokenize;

TEST(Tokenize, EmptyInput)
{
    EXPECT_TRUE(tokenize(" ", "").empty());
}

TEST(Tokenize, WhitespaceInput)
{
    EXPECT_TRUE(tokenize(" ", "    ").empty());
    EXPECT_TRUE(tokenize(" \n\t", "  \n  \t  ").empty());
}

TEST(Tokenize, OneWord)
{
    auto results = tokenize(" ", "  One  ");
    auto expected = std::vector<std::string_view>{"One"};
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);

    results = tokenize("-", "--One--");
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);

    results = tokenize(" ", "One");
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);
}

TEST(Tokenize, TwoWords)
{
    auto results = tokenize(" \n\t", "  One\nTwo  ");
    auto expected = std::vector<std::string_view>{"One", "Two"};
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);

    results = tokenize(" \n\t", "One\nTwo");
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);
}


static auto shell_token_start(std::string_view in)
{
    return in.find_first_not_of(" \t\n");
}
static auto shell_token_end(std::string_view in)
{
    bool in_single_quote = false;
    bool in_double_quote = false;
    std::size_t i;
    for (i = 0; i < in.size();  ++i) {
        auto const c = in[i];
        if (in_single_quote) {
            if (c == '\'') {
                in_single_quote = false;
            }
            continue;
        }
        // Backslash is escape in unquoted and double-quoted, but not
        // single-quoted
        if (c == '\\') {
            ++i; continue;      // skip next character
        }
        if (in_double_quote) {
            if (c == '"') {
                in_double_quote = false;
            }
            continue;
        }
        switch (c) {
        case '\'': in_single_quote = true; continue;
        case '"': in_double_quote = true; continue;
        case ' ':
        case '\n':
        case '\t': return i;
        default: continue;
        }
    }
    return in.npos;
}
static auto shell_tokenize(std::string_view input)
{
    return tokenize<std::string_view>(shell_token_start, shell_token_end, input);
}

TEST(TokenizeShell, TwoWords)
{
    auto results = shell_tokenize(R"('a b c'  \ "\"1 2\"")");
    auto expected = std::vector<std::string_view>{R"('a b c')", R"(\ "\"1 2\"")"};
    EXPECT_EQ(std::vector(results.begin(), results.end()), expected);
}

A practical use: find the most frequent words of a book, without creating thousands of std::string objects:

#include <boost/iostreams/device/mapped_file.hpp>
#include <iostream>
#include <map>
#include <ranges>
#include <vector>

int main()
{
    auto source = boost::iostreams::mapped_file_source{"moby-dick.txt"};
    std::clog << "Input contains " << source.size() << " bytes.\n";
    auto input = std::string_view{source.data(), source.size()};
    std::unordered_map<std::string_view,std::size_t> histogram;
    for (auto word: parser::tokenize(" \n.,\";:-[]#?!", input)) {
        ++histogram[word];
    }
    std::clog << "Input contains " << histogram.size() << " distinct words.\n";
    std::vector<std::pair<std::string_view, std::size_t>> ranked(histogram.begin(), histogram.end());
    std::ranges::sort(ranked, std::greater{}, &decltype(ranked)::value_type::second);
    for (auto [val, count]: ranked | std::views::take(50)) {
        std::cout << count << ' ' << val << '\n';
    }
}
\$\endgroup\$

1 Answer 1

2
\$\begingroup\$

tokenize() makes copies unnecessarily

Remember that auto on its own will never deduce a reference. That means tokenize() takes its parameters by value, and that can cause undesired copies to be made in some cases. Consider:

std::string delim_chars = …;
std::string input = …;
auto tokens = tokenize(delim_chars, input);

To avoid this, make it take parameters by const reference:

auto tokenize(const auto& delim_chars, const auto& input)
{
    …
}

That is maybe a bit silly if you want to pass in std::string_views which are better passed by value, but since it's a template anyway, the compiler will very likely be able to optimize out the reference.

Avoid unnecessary default constructors and operators

There is no need to explicitly default the destructor and the copy and move constructors and assignment operators. Prefer not declaring them; the compiler will do the right thing based on the types of member variables, and this way there is less chance of making errors yourself.

Consider tokenizing streams

The reason for the suggestion of making a tokenizer that returns a range is so you don't need to tokenize all of the input up front into a container. This saves memory, and possibly CPU time if you didn't need to tokenize everything. However, your tokenizer still assumes that all of the input is available in memory. What if you want to tokenize say, lines in a file? Instead of requiring the whole file to be loaded into memory first, it would be nice if you could stream the file into the tokenizer.

There are several approaches to this. You could make tokenizer() take a std::istream as a parameter, or you could somehow add a way (perhaps via a callback function) to either push new data into the tokenizer, or have the tokenizer pull more data when necessary.

\$\endgroup\$
9
  • 1
    \$\begingroup\$ "There are several approaches to this." I wonder about using a coroutine type for asynchronously tokenizing the content of a file. Could it be done in some way? \$\endgroup\$
    – digito_evo
    May 28, 2023 at 15:20
  • 1
    \$\begingroup\$ Yes, the tokenizer could be a generator that itself co_awaits to get new data. \$\endgroup\$
    – G. Sliepen
    May 28, 2023 at 18:13
  • \$\begingroup\$ I respectfully think the advice on “unnecessary” constructors is mistaken. First, there is a non-default constructor for token_iter declared, which would prevent the other constructors from being silently created. Second, my own preference is to always declare them explicitly if I need them, even if it does mean a few lines of boilerplate. It really comes down to coding style. \$\endgroup\$
    – Davislor
    May 28, 2023 at 19:10
  • 1
    \$\begingroup\$ An approach that’d work well for files on a local drive is to map the input file to memory. In practice, though, a tokenizer is often going to need to work on data that comes over a slow network, and I agree that it’d be very useful for it to able to generate the tokens lazily. \$\endgroup\$
    – Davislor
    May 28, 2023 at 19:16
  • 1
    \$\begingroup\$ There are a few classic approaches—polling the token to see if reading it would block, running the tokenizer in a background thread that can do blocking I/O, coroutines as you mentioned—but the problem for this design is that you can only return a string_view of a string in memory that will outlive the view. Otherwise, it will turn into a dangling reference. You can’t return views of a std::string that you append data to, either, since that could move it in memory. You’re back to either creating thousands of string objects, or buffering the entire input to memory so you can take views. \$\endgroup\$
    – Davislor
    May 28, 2023 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.