4
\$\begingroup\$

My concern is mainly the correctness of the algorithm for tokenizing purposes. The code compiles as it is called as a member function in my program. The code does pass my small amount of unit tests for parsing inputs (61 unit tests, all pass). But, I'm slightly stressed out about this part of code, and also paranoid. I could use a pair of foreign mk.I eyeballs looking at my code. This is part of a bigger project and ideally the tokenizing should be bugfree

please take a look and give thoughts. :'(

BACKGROUND & problem parameters objectives of my tokenizer:

  • cannot use stringstreams, run out of programmemory
  • input cppstrings will not have newline or any such limiter at the end(will be chucked out before inputting into tokenize_input_refactored() ), IT will be as though the input cppstring was gotten with getline()
  • separate cppstrings into tokens based on single spacebar (delimiter), or the end of the string in regular way ("M4 255" is tokenized into "M4", "255")
  • if there's no delimiter, take the entire cppstring as token
  • backToBack delimiters is immediately invalid input, like " " twoSpacebars in row (or more spacebars in row)
  • cannot begin or end with spacebar(delimiter), immediately invalid input
  • too large string ( 31 or more true chars) is illegal input
  • empty string is illegal input

  • the "garbage strings" that are pushed into the vector "illegalcommand" are later on used for comparison with known words for parsing purposes. Just to be sure that command won't be parsed as valid. (tokens amount as well as tokens themselves are checked against expected values)

Possible solution as C++ member-function:

tokensVec is just an empty vector datamember of Gcodeparser object. It will be cleared empty after each round of tokenizing (or parsing, the same same effect).

bool GcodeParser::tokenize_input_refactored(const std::string & rawInput) {

    /*find delimiter == singleSpacebar*/
    auto res = rawInput.find(delimiter);

    /*find if there was twoOrMoreDelimiters backToBack "  " twospacebars */
    string backToBackDelim;
    backToBackDelim += delimiter;
    backToBackDelim += delimiter;
    auto res2 = rawInput.find(backToBackDelim);

    int searchInd = 0;
    int pos = 0;
    int size = rawInput.length();
    bool returnableResult = false;

    /*if the input was too large => reject as illegal*/
    if (size > maxCharAmount) {
        tokensVec.push_back("INVALID_COMMAND!");
        return false;
    }
    /*check if empty string*/
    if (size == 0) {
        tokensVec.push_back("INVALID_COMMAND!");
        return false;
    }

    /*found 2delim backtoback*/
    if (res2 != string::npos) {
        tokensVec.push_back("INVALID_COMMAND!");
        return false;
    }

    /*input ended in delimiter or started with delimiter*/
    if (rawInput[0] == delimiter || rawInput[size-1] == delimiter) {
        tokensVec.push_back("INVALID_COMMAND!");
        return false;
    }

    /*delimiter wasnt found => take complete word into vec for later parsing*/
    if (res == string::npos) {
        tokensVec.push_back(rawInput);
        return true;
    }
    else {
        while (pos != string::npos) {
            pos = rawInput.find(delimiter, searchInd);
            if (pos != string::npos) {
                tokensVec.push_back(rawInput.substr(searchInd, pos - searchInd));
                searchInd = pos + 1;
            }
        }
        /*take the last valid token*/
        tokensVec.push_back( rawInput.substr(searchInd, size - searchInd) );
        return true;
    }
}
\$\endgroup\$
  • \$\begingroup\$ If your main concern is correctness, you should really include your unit tests as part of the review. Without that, it's hard to know which aspects are already well covered and which aspects have gaps. \$\endgroup\$ – Toby Speight Oct 2 '18 at 7:48
2
\$\begingroup\$

Well, it seems to do what you want. But, we can do better.

Review:

  1. Avoid dynamic allocation where possible.

    string backToBackDelim;
    backToBackDelim += delimiter;
    backToBackDelim += delimiter;
    auto res2 = rawInput.find(backToBackDelim)
    

    becomes

    const char backToBackDelim[] = {delimiter, delimiter};
    auto res2 = rawInput.find(backToBackDelim, 0, 2)
    
  2. Don't pass std::string by constant reference unless you depend on the terminator. Pass a view by value instead, specifically C++17 std::string_view. It is more flexible and tends to be more efficient.

  3. An empty line directly after the prototype is curious. Either remove it, or move the opening brace { for the function there.

  4. Define your variables in the smallest scope you can, and invest in good names. What is res / res2, and why do you initialize it all the way up there, and only use it the once down here?
    You know what, eliminate it completely, it's bloat.

  5. Choosing good names should also be applied to the function itself. Yours seems to be a placeholder.

  6. Consider marking things const to ease comprehension. No Need to search for possible sites of modification then. That is, if having that extra-variable actually pays for itself with clarity.

  7. You have a bunch of conditions under which you error out. The curious Thing is that you manually duplicated the handling block. Consider merging the conditions so you only need it once.

  8. Don't use else if control-flow doesn't resume after the code-block anyway. Less indentation is better.

  9. You know .substr() will adjust the second argument, if provided, to not leave the string? So, don't try so hard in your last call.

Re-Design:

Mull over your spec. And now try to simplify it. Doing so leads to a simpler, more efficient design, which is optimized for legal input:

  1. Too large or empty => illegal.
  2. Tokenize.
  3. Empty token => illegal.

Rewrite:

bool GcodeParser::tokenize_input_refactored(std::string_view s) {
    // Consider adding here: tokensVec.clear();
    if (auto pos = size(s); pos && pos <= maxCharAmount) {
        while ((pos = s.find(delimiter))) {
            tokensVec.push_back(s.substr(0, pos));
            if (pos == std::string_view::npos)
                return true;
            s = s.substr(pos + 1);
        }
        tokensVec.clear();
    }
    tokensVec.push_back("INVALID_COMMAND!");
    return false;
}
\$\endgroup\$
  • \$\begingroup\$ I forgot to say it was for ISO C++ 11. Code is intended for embedded c++ microcontroller. I would say that, I prefer using kind of verbose style with local variables usage, because it makes it easier for me to understand what the code does. I think that I will combine the error cases probably together, since my teacher doesn't like "copy-paste code". \$\endgroup\$ – Late347 Oct 2 '18 at 4:49
  • \$\begingroup\$ With regards to tokensVec.clear(), it cannot be done immediately after the tokenizing, because separate parser functions will run on the tokens. And after the last parsing is done, then the tokens will be cleared (or I suppose I could take your advice and clear in the beginning before tokenizing anything) \$\endgroup\$ – Late347 Oct 2 '18 at 4:50
  • \$\begingroup\$ It will probably take about 30minutes or so decipher the terse refactored tokenizing version, I'll take another look at it in a while. I have the terrible case of man flu at the moment, and my eyes are watering and my nostrils are just completely blocked :'( \$\endgroup\$ – Late347 Oct 2 '18 at 4:53
  • \$\begingroup\$ thank you for reviewing the code, in any case! I realy appreciate this. \$\endgroup\$ – Late347 Oct 2 '18 at 4:53
  • \$\begingroup\$ Well, if you are restricted to C++11, then may I suggest looking at boost's string_view here and maybe adopting that? Otherwise, yes, you will have to slightly modify my approach to using a second position. \$\endgroup\$ – Deduplicator Oct 2 '18 at 12:55
1
\$\begingroup\$

As far as I can see, this looks correct for the behavior you've stated. A few possible improvements:

Efficiency:

  • It would be better to check for failure conditions in a different order: string size, first or last is delimiter, presence of double-delimiter, and only if those all pass then find single-delimiter.
  • You re-search the string for the first occurrence of delimiter in the while loop instead of using the already calculated one. You could rewrite the else block to:

    while (res != string::npos) {
        tokensVec.push_back(rawInput.substr(previous, res - previous));
        previous = res + 1;
        res = rawInput.find(delimiter, previous);
    }
    tokensVec.push_back(rawInput.substr(previous, size - previous));
    

Style:

  • There are a few too many variables, and the naming isn't very clear. searchInd and pos can be condensed to a single one (previous, in the above snippet), returnableResult isn't used, and res2 doesn't need to be a variable.
  • Use full names, especially when it's only slightly longer.
  • The lack of indentation at the top level and the use of /* */ for single-line comments is atypical; I wouldn't recommend it unless that's an existing coding style used by your team / company.

Misc:

  • Different failure messages for different failure conditions may be useful, depending on where that output is used.
\$\endgroup\$
  • \$\begingroup\$ Hmm... I was left wondering if your proposed change would work e.g. inputstr == "M4 255". Then, you can see that res variable will then contain the index of the found delimiter, so that res == 2 even before the else branch and before first loop iteration. Then you go into the while loop first iteration. Then, search for delimiter will fail, because only one delimiter existed, and then next == size. Then, an attempt is made to push back a substring that starts from the first delimiter, (instead of the zeroeth index) so, it looks like it misses the first token??? I will take another look later.. \$\endgroup\$ – Late347 Oct 2 '18 at 0:24
  • \$\begingroup\$ Whoops! You're right, I was editing too quick there and mixed versions. Corrected now. \$\endgroup\$ – Errorsatz Oct 2 '18 at 1:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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