4
\$\begingroup\$

This is the next iteration of the Natural language text fast tokenizer code review. Special thanks goes to G. Sliepen, Toby Speight and uli who conducted previous reviews and to Matthieu M. and Adrian McCarthy who participated with important findings.

Functional specification

Implement a class for fast text tokenization handling some natural language specifics below:

  1. Consider ‘ ‘ (space) as a delimiter, keeping a way to extend the list of delimiters later; the delimiters couldn’t be a part of other constructs.
  2. Extract stable collocations like “i.e.”, “etc.”, “…” as a single lexem.
  3. In case word contains “inword” characters like ‘-‘ and ‘’’ (examples: semi-column, half-, cat’s) return the whole construct as a whole lexem.
  4. Threat all other non-alphanumeric characters as separate lexems.
  5. Return sequences of numbers (integers without signs) as a single lexem. Consider out of scope paired quotes and other lexical parsing level issues. Performance is critical, since the amount of data is huge. The function should be thread-safe.

Changes

  1. The code has been reworked according to all code review points.

Reservations

  1. Methods implementation inside of the class definition done only to the sake of brevity; production code will have them implemented separately.
  2. I am not sure that using value_type = std::string_view; is correct in TokenRange::Iterator; most likely I should store a nested struct for data and lexem and it should be a type of value_type, but I pretend like lexem is the value to be stored and data is some proxy of TokenRange::data which makes the iterator safer in case of TokenRange changes. At the end of the day, both TokenRange::data and TokenRange:: Iterator::data are just proxies to the original std::string / std::string_view passed to TokenRange.

The code

Here is the updated code for the code review; could you please take a look and suggest further ways to improve or confirm that this is ready to go code?

Fully functional demo.

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstring>
#include <functional>
#include <iostream>
#include <limits>
#include <locale>
#include <numeric>
#include <random>
#include <ranges>
#include <vector>

namespace fast {
    template <typename Fn>
    class CharacterClass
    {
        std::array<char, std::numeric_limits<char>::max() + 1> cache = {};

    public:
        explicit CharacterClass(Fn fn, const std::locale& locale = {})
        {
            set_locale(fn, locale);
        }

        void set_locale(Fn fn, const std::locale& locale)
        {
            auto const func = [&locale, &fn](char c) { return fn(c, locale); };
            std::ranges::copy(std::views::iota(0u, cache.size())
                | std::views::transform(func),
                cache.begin());
        }

        bool operator()(char c) const { return cache[c]; }
    };

    CharacterClass isalpha(std::isalpha<char>);
    CharacterClass isdigit(std::isdigit<char>);
    CharacterClass isalnum(std::isalnum<char>);
}

class TokenRange {
    std::string_view data;
public:
    class Iterator {
        const std::string_view delimiters = " ";
        const std::vector<std::string_view> stable_lexems = { "...", "i.e.", "etc.", "etc..."  };
        const std::string_view inword_symbols = "-\'";

        std::string_view data;
        std::string_view lexem;
    public:
        using iterator_category = std::input_iterator_tag;
        using value_type = std::string_view;
        using difference_type = std::ptrdiff_t;

        Iterator() {}
        Iterator(std::string_view data) : data(data) { extract_lexem(); }
        std::string_view operator*() const { return lexem; }
        Iterator& operator++();
        Iterator operator++(int);
        friend bool operator==(const Iterator& it1, const Iterator& it2) { return it1.lexem == it2.lexem; }
        friend bool operator!=(const Iterator& it1, const Iterator& it2) { return it1.lexem != it2.lexem; }
        Iterator& operator=(const Iterator& it) { data = it.data; lexem = it.lexem; return *this;  }
    private:
        void extract_lexem();
        void skip_delimiters();
        bool check_for_stable_lexems();
    };

    TokenRange(std::string_view data) : data(data) {}

    Iterator begin() const {
        return Iterator(data);
    }

    Iterator end() const {
        return {};
    }
};

void TokenRange::Iterator::skip_delimiters()
{
    while (!data.empty() && std::ranges::contains(delimiters, data.front())) {
        data.remove_prefix(1);
    }
}

bool TokenRange::Iterator::check_for_stable_lexems()
{
    auto it = std::ranges::max_element(stable_lexems, std::less<size_t>(),
        [&](auto stable_lexem) {
            return data.starts_with(stable_lexem) ? stable_lexem.size() : 0;
         }
    );

    if (it != stable_lexems.end() && data.starts_with(it->data()) ) {
        lexem = data.substr(0, it->size());
        data = data.substr(it->size());
        return true;
    }

    return false;
}

void TokenRange::Iterator::extract_lexem()
{
    skip_delimiters();

    if (check_for_stable_lexems()) {
        return;
    }

    std::size_t index = 0;
    while (index < data.size()) 
    {
        if (std::ranges::contains(delimiters, data[index])) {
            break;
        }

        if (!fast::isalnum(data[index])) {
            if (index == 0) {
                ++index;
            }
            break;
        }

        const bool is_next_char_inword_symbol = (index+1) < data.size() ? std::ranges::contains(inword_symbols, data[index+1]) : false;
        if (is_next_char_inword_symbol) {
            ++index;
        }

        ++index;
    }

    lexem = data.substr(0, index);
    data = data.substr(index);
}

TokenRange::Iterator& TokenRange::Iterator::operator++()
{
    extract_lexem();
    return *this;
}

TokenRange::Iterator TokenRange::Iterator::operator++(int)
{
    Iterator temp(data);
    extract_lexem();
    return temp;
}

int main()
{
    {
        std::string sample = "Let's consider, this cats' semi-simple sample, i.e. test data with ints: 100 and 0x20u, etc. For ... some testing...";

        for (auto token : TokenRange(sample)) {
            std::cout << token << " | ";
        }
    }

#define TEST_SUITE
#ifdef TEST_SUITE
    struct {
        std::string input;
        std::vector<std::string> expected;
    } samples[] = {
        { "", {} },
        { " ", {} },
        { "  ", {} },
        { "etc.", { "etc." } },
        { "etc.i.e.", { "etc.", "i.e."} },
        { "...etc...", { "...", "etc..."} },
        { "......", { "...", "..."  } },
        { "....", { "...", "."  } },
        { ".,:", { ".", ",", ":"}},
        { "cat\'s cats\' 'cats'", { "cat\'s", "cats\'", "\'", "cats\'"}},
        { "semi-semi-column", { "semi-semi-column" } },
        { "Let's consider, this cats' semi-simple sample, i.e. test data with ints: 100 and 0x20u, etc. For ... some testing...",
        { "Let\'s", "consider", ",", "this", "cats\'", "semi-simple", "sample", ",", "i.e.", "test", "data", "with", "ints", ":", "100", "and", "0x20u", ",", "etc.", "For", "...", "some", "testing", "..." } },
    };

    for (auto& sample : samples) {
        assert(std::ranges::equal(TokenRange(sample.input), sample.expected));
    }
#endif // TEST_SUITE
}

Some final thoughts

I started with 48 lines of very simple (in terms of used language techniques) code which fit a C-style function and ended up with two sophisticated classes (well, at least one of them) of 110 lines of code whose behaviour is not so obvious and transparent for a newbie developer or another person in support.

The code was improved and some subtle defects were fixed, but all this could have been done in scope of the original function and would led even to reducing its size.

I have some personal profits:

  1. I learned a lot about ranges, concepts and compiler warnings for them.
  2. I learned a technique to distribute work between ‘operator++()’ and ‘operator*()’ in iterators.
  3. I got the prove that std::string_view and some other tools used here in no meaning slower that traditional C-style pointers.
  4. I got another confirmation that “working” code without unit tests doesn’t go.

So, all this comes as experience and I am thankful for all people involved here.

On the other hand, if we consider the task “as is”, here are my thoughts.

Profits

  1. Now the code supports (at least preliminary and partially) new language technique, namely, std::ranges.
  2. The API became much safer without char * and friendlier to the user with support of iterators and ranges.

Drawbacks

  1. The code became longer and harder to maintain. This especially comes with this state machine data / lexem.
  2. It is very hard to prove that code is still correct not only terms of tokenizing, but even in terms of usage C++ for iterators; many things done as “well, this works” and require very detailed reading of standard on iterators, ranges, concepts, requires’, etc. to make sure that this code fits all these requirements. So, this again increases requirements to personnel who will develop and support the code, while the original technical specification never required this.
  3. The code no more portable to C language fast, if needed. I remember that I myself asked in the first post to use std::ranges, but I meant to use some functions which could be easily replaced back with C-style functions, not to implement this object as std::range itself.

This is always a design choice which way to go, to solve the specific task in existing code or to improve it with continuous refactoring. In my personal view, the main programmer’s mistake is to solve a wrong task and if initial functional specification told “Implement a function” and programmer started with expensive refactoring to iterators, ranges, etc. I would consider this as overengineering and spending effort aimlessly. If instead of fixing some lines of code in function they would develop two classes, I would consider this a mistake, since technical requirements never asked to implement something different and the client could be constrained with function usage (although, I would agree that code review title could give such a freedom). And the key point is that after first turn of code review I agreed with the proposal, so accepting the design decision is on me and I am totally responsible here. So, I am considering my choice in retrospective to learn.

And please, don’t get me wrong, I am very thankful to G. Sliepen who suggested this way and helped me learn a lot in practice and I am not saying that he suggested a wrong design decision; I believe, his circumstances and goals was slightly different, namely to show on this simple example how to develop good nowadays C+ software and he succeeded here. My only concern if this specific small task is a good candidate for this since it mixes two questions: good language style and a very specific task. My point is that the technique is great, but it is arguable that this particular task benefits from it taking into account the drawbacks.

To be precise in wording:

  1. Should the proposed style be used instead of old one? Yes, in most of the cases.
  2. Should the developer given the original task start this refactoring instead of fixing defects in the function? I am not sure, totally depends on the context and how it will be used

So, to put in a nutshell, I am still in twenty minds about this refactoring for this specific task, although I consider it “must learn to use when needed”.

Please, don’t consider this as concerns, complains or disagreements, this is just thoughts to share. Thank you all, who helped me here!

\$\endgroup\$

1 Answer 1

4
\$\begingroup\$

Enable compiler warnings and fix them

When developing code, always enable rather strict compiler warnings (for example, using -Wall -W -pedantic for Clang and GCC, but you could go even stricter at the risk of getting false positives). Whenever the compiler warns about something, don't ignore it but fix it. Both Clang and GCC complain about this:

In member function 'TokenRange::Iterator TokenRange::Iterator::operator++(int)':
warning: implicitly-declared 'constexpr TokenRange::Iterator::Iterator(const TokenRange::Iterator&)'
         is deprecated [-Wdeprecated-copy]
note: because 'TokenRange::Iterator' has user-provided
      'TokenRange::Iterator& TokenRange::Iterator::operator=(const TokenRange::Iterator&)'

So this means, at some future point in time, the copy constructor will not be generated automatically anymore because you provided a custom assignment operator. So a possible fix is to just add a copy constructor as well.

Even better would be to not need to add copy and assignment operators, as at first glance it should not be necessary at all: the compiler should be able to automatically generate default functions that copy the std::string_views. The problem, as you found out yourself, is because of the const variables delimiters, stable_lexems and inword_symbols. Make them static instead.

About your final thoughts

It's great that you yourself realize that all this effort has made you learn a great deal, and that the code has improved because of it! You are also right about it being hard to get the iterator version correct, and it indeed requires quite a bit more code. Ideally, you would just want to write something as close as possible to the first revision, and still get the benefit of using it in a range-for loop. Since C++23 you can, by using std::generator<>. Your code would then look like:

std::generator<std::string_view> tokenize(std::string_view data) {
    …
    while (/* not done yet */) {
        …
        std::string_view token = …;
        co_yield token;
        …
    }
}

I did not mention this before since this is a very recent addition to the language, and you thus also need a very recent compiler.

What should you use in your actual project? That's indeed up to you. Sometimes a quick and dirty hack is all you need. In larger projects, refactoring the code to make it more generic and more standards compliant will pay off though. If you don't know when to do what, consider applying the YAGNI principle.

When and how to decompose functions

There is this pervasive notion that more lines of code is bad. There is some truth to that: more lines means more possibilities of bugs, more to maintain, and more to document. However, the real problem is actually complex code. If you have one function of 100 lines of complex code, or ten simple functions of only 20 lines each, then despite the latter being 200 lines of code, it will actually have less chance of bugs, easier to maintain, and more self-documenting.

Of course, you should only decompose when it makes sense: if you can cleanly move some lines of code into a separate function, and that function then does something clear and simple (and thus can be given a clear and simple name), and it makes the original function less complex. Even skip_delimiters(), despite being just a few lines of code, is a great example of this.

It's hard to say what the right number of functions is, or what the maximum size of a function should be, that depends on the nature of the code of course. However, I can tell you that most people, including myself, don't decompose as much as they should.

The helper member functions you are creating should be private. They don't change the public API nor the ABI, so this is very safe to do. If you really want to avoid complicating your class declaration, you could consider instead to make them out-of-class functions, and then pass references to any member variables you want to modify. For example:

static void skip_delimiters(std::string_view& data, std::string_view delimiters) {
{
    while (!data.empty() && std::ranges::contains(delimiters, data.front())) {
        data.remove_prefix(1);
    }
}

void TokenRange::Iterator::extract_lexem()
{
    skip_delimiters(data, delimiters);
    …
}

There might also be some other ways to approach this problem.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Thank you for your help here. Since the final changes are trivial, let's stay with this version. Here is the answer to your concern about not working = default for the assignment, the reason is these const members of the class which can't be assigned by default. But the funny things comes after it. If I remove const keywords, I can default the copy constructor and after that warning says: "Not used operator=() has been removed". But if I remove it manually from code, std::ramges::equal(...) doesn't compile. Funny. \$\endgroup\$ Feb 15 at 18:12
  • \$\begingroup\$ Unfortunately, VS2022 haven't reported these issues on /W4 level and I am still in two minds of using /WALL on a daily basis because of warnings on this level for C+ Standard Library functions in VS2022 (like this and the same in <atomic> header) and lots of Spectre mitigation warnings for my code I am not concerned with for the moment. At the same time it reported a mistake with std::array<char,... instead of needed std::array<bool,... in the CharacterClass (I can suppress, of course). \$\endgroup\$ Feb 15 at 18:20
  • \$\begingroup\$ One additional request, I will be thankful, if you add a section to cover my questions on functional decomposition/function extraction raised as comments under your answer in the Rev.3 \$\endgroup\$ Feb 15 at 18:22

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.