6
\$\begingroup\$

There is some language where the following are considered comments:

  1. [str] // comment
  2. [str] /* comment */ [str]
  3. [str] # comment
  4. [str] /* comment1 comment2 */ [str]

where [str] is 0 or more occurrences of some string.

I'm reading a file line by line, and need to remove the comments from the whole file (the file is large so I cannot keep the whole content in memory).

I have written a method that receives each line, removes the comments from it, and returns the remaining string.

(Here s_bInComment is a static variable in Parser class with initial value of false)

void Parser::removeComments(std::string &str)
{
    // see if we're still in comment lines, i.e. not reached */
    auto commentEnd = str.find("*/");
    if (s_bInComment && commentEnd == std::string::npos)
    {
        str.clear();
        return;
    }

    std::string result;

    const auto iStrLen = str.length();
    for (std::size_t idx = 0; idx < iStrLen; ++idx)
    {
        if (str[idx] == '/')
        {
            if (idx + 1 < iStrLen)
            {
                if (str[idx + 1] == '/')
                {
                    // we found //
                    // take the part of the string before the comment, if any
                    str = str.substr(0, idx);
                    break;
                }

                if (str[idx + 1] == '*')
                {
                    // see if */ is in the same line
                    commentEnd = str.find("*/");
                    if (commentEnd == std::string::npos)
                    {
                        // multiline comment
                        s_bInComment = true;
                        str = str.substr(0, idx);
                    }
                    else
                    {
                        // remove the comment
                        str = result + str.substr(commentEnd + 2);

                        // recurse on the remaining string
                        removeComments(str);
                    }

                    break;
                }
            }
        }
        else if (str[idx] == '*')
        {
            if (idx + 1 < iStrLen)
            {
                if (str[idx + 1] == '/')
                {
                    // we have found */, comment ended
                    s_bInComment = false;

                    // take the part of the string after the comment, if any
                    str = str.substr(idx + 2);

                    // recurse on the remaining string
                    removeComments(str);

                    break;
                }
            }
        }
        else if (str[idx] == '#')
        {
            // if there's a text before #, it should be accumulated in result
            str = result.size() ? result : std::string();
            break;
        }
        else if (!s_bInComment)
            result += str[idx];
    }
}

I have tested my code with the following input lines:

  1. a /* b */ c
  2. a /* b */
  3. a // b
  4. a /* b c */
  5. // a
  6. a /* b */ c
  7. # a
  8. a # b
  9. a /* a */ b /* b */ c

Please let me know if there's room for improvement in one or other part.

\$\endgroup\$
2
\$\begingroup\$

I believe it's a good example of a problem that you can represent with a state-machine. What you do with the next character depends on the state you're in:

  • if you're outside of a comment, then you copy the character unless it's a / or a #
  • if the last character was a / outside a comment, then test if the new character is a * or a /
  • if you're inside a single line comment, you ignore it unless it's a newline
  • if you're inside a multi-line comment, you ignore it unless it's a star
  • if you've just read a * inside a multi-line comment then you need to check if the new char isn't a /

State-machines aren't always the most elegant way of coding, but they're robust, easy to read and blazingly fast. So how would you implement it in this case?

First, don't read the input line by line. It is probably a mistake since crucial information resides in the previous line, if there's one: you can't know, looking at a line, if a multi-line comment was opened in the previous one. Also, it will force you to perform memory management each time you read a line (you need to check if the output string is big enough and allocate more memory if it isn't), which will slow down your program, whereas looking character by character will allow you greater flexibility (any object exposing iterators on characters is acceptable) and prevent allocations if they aren't needed.

That brings us to the signature:

template <typename InputIt, typename OutputIt>
OutputIt copy_without_comments(InputIt first, InputIt last, OutputIt out)

The OutputIt can be many things: an iterator on an allocated buffer, an iterator constructing a string, an iterator on a stream...

The state machine itself is generally implemented with an enum specifying the possible states:

enum class State : char { SlashOutsideComment, StarInsideComment, SingleLineComment, MultiLineComment, NotAComment };

Then it's only a big switch to know how to handle the next character:

 switch (state) {
            case State::SlashOutsideComment:
                if (*first == '/') state = State::SingleLineComment;
                else if (*first == '*') state = State::MultiLineComment;
                else {
                    state = State::NotAComment;
                    *out++ = '/';
                    *out++ = *first;
                }
                break;
            case State::StarInsideComment:
                if (*first == '/') state = State::NotAComment;
                else state = State::MultiLineComment;
                break;
            case State::NotAComment:
                if (*first == '#') state = State::SingleLineComment;
                else if (*first == '/') state = State::SlashOutsidedComment;
                else *out++ = *first;
                break;
            case State::SingleLineComment:
                if (*first == '\n') {
                    state = State::NotAComment;
                    *out++ = '\n';
                }
                break;
            case State::MultiLineComment:
                if (*first == '*') state = State::StarInsideComment;
        }

Link to test and play with: https://wandbox.org/permlink/iXC7DWaU8Tk8jrf3

\$\endgroup\$
  • \$\begingroup\$ if i'm reading the file character by character, then i'm gonna construct a string, so the allocations will still be done, right? \$\endgroup\$ – user3132457 Mar 21 at 13:29
  • \$\begingroup\$ @user3132457 Well, of course you'll pay for the string if you use it, but not if you don't (for example if you redirect the result to a stream or copy it to a statically allocated buffer). \$\endgroup\$ – papagaga Mar 21 at 18:20
  • \$\begingroup\$ i'm gonna use it. i suppose by statically allocated buffer you mean a char[] of some size allocated beforehand. i don't know the size of each line, so i can't allocate enough i guess. also, after removing the comments i'm removing spaces from beginning and end of the string (with a function) (actually i don't need any spaces, but removing them just from beginning and end is easier and cheaper). where should i do that if i use this state machine comment remover (i made it into a class): wandbox.org/permlink/ZtDvwYoEASE3rnIm. in this class? or a standalone function? \$\endgroup\$ – user3132457 Mar 21 at 18:23
  • \$\begingroup\$ also one question, why do you need the else branch for case CharacterState::SlashOC:? it's never hit i guess? p.s. i was wrong when i said i don't need any spaces. okay, i just don't need them at the beginning and end \$\endgroup\$ – user3132457 Mar 21 at 18:36
  • \$\begingroup\$ updated the code: wandbox.org/permlink/lwphb2NrwmpNlIDp \$\endgroup\$ – user3132457 Mar 21 at 18:43
1
\$\begingroup\$

That's an interesting case. First, I thought that the function should be a function template for a pair of input iterators and an output iterator, as that's an idiomatic approach taken by many STL algorithms and what the function matches this pattern. But given that \n plays a crucial role here, passing iterators to an underlying std::ifstream doesn't make much sense (it consumes words, not lines).

Nevertheless, let me share my thoughts besides.

  • Why does it have to be a static data member s_bInComment? I assume removeComment is static, too? This sounds like it's somewhat decoupled from the rest of the Parser class, which might have some instance-specific state. Maybe it makes things cleaner and more testable if you create a small class only for the removal of comments, which improves encapsulation and circumvents the static variable - non-const, static variables are too global for my taste, and they are generally thread-unsafe.

  • The function is very long, and it contains many nested branches. I think it's common sense that this is not very readable and should be split into smaller functions. If you give them meaningful names, you can even remove some of your comments (e.g. hasPartialEndToken(str) or startsWithGlobalToken(str)).

  • If you care about allocations and C++17 is available, you could change the way this functions passes its result back to the caller, i.e., via a std::vector<std::string_view>. The lifetime of the input argument is controlled by the caller, so it is probably sufficient to not copy the non-comment parts of the string into a result, but instead create a collection of views on the input. As std::string::substr and concatenating strings with operator + are possibly expensive operations, you might keep this option in mind (and of course, only go with it after you made sure that performance/memory footprint is important, you profiled your code and so on...)

  • Minor point, as this is not in your list of tested string: what should happen with something like "a /* b \n c */ d # e", i.e., a multiline comment followed by a until-the-end-of-line comment?

Last, a more general question - why aren't you using <regex>? The API is not famous for its ease of use, but you do a lot of manual work that could be outsourced to the standard library, and developers maintaining such a piece of code wouldn't be surprised to find some regular expressions in it. Here's a small class has the same functionality as the snippet you posted:

class CommentRemover {
    public:
        std::string strip(const std::string& input);

    private:
        bool isInComment = false;
        static const std::regex restOfLine;
        static const std::regex partialInline;
        static const std::regex multiLineBegin;
        static const std::regex multiLineEnd;
};

with the actual std::regex objects being defined as

const std::regex CommentRemover::restOfLine{"(//|#)"};
const std::regex CommentRemover::partialInline{"(/\\*.*?\\*/)"};
const std::regex CommentRemover::multiLineBegin{"(/\\*.*(?!\\*/))"};
const std::regex CommentRemover::multiLineEnd{"(/\\*.*(?!\\*/))"};

and the implementation of the member function looks like

std::string CommentRemover::strip(const std::string& input)
{
    std::smatch match;
    // Save some typing below:
    const auto search = [&match, &input](const std::regex& re){
        return std::regex_search(input, match, re); };

    if (isInComment && search(multiLineEnd)) {
        isInComment = false;
        return strip(match.suffix().str());
    } else if (search(partialInline))
        return match.prefix().str() + strip(match.suffix().str());
    else if (search(restOfLine))
        return match.prefix().str();
    else if (search(multiLineBegin)) {
        isInComment = true;
        return match.prefix().str();
    }

    return input;
}

This is not a prime example for readability, and the regex specifications are admittedly cryptic. But I think it reduces the likelihood of bugs due to less code and no manual looping/indexing. Plus, it allows for concentrating the complexity of the operation into the regex definitions and the if-else if ordering.

\$\endgroup\$
  • \$\begingroup\$ the reason i'm not using regex is that, after removing the comments i run a regex on the string, so if i remove the comments using regex, that'll be 2 regex passes for each string, and i know c++ regex is infamous for its slowness. i know about string_view, but don't have c++17 available. the input "a /* b \n c */ d # e" is supposed to return a \n d (i had a bug and fixed it to return the correct string). and i like the idea to have a comment remover class. i'll update my code respectively and post it again, thanks. \$\endgroup\$ – user3132457 Mar 20 at 17:41
  • \$\begingroup\$ Well, the regex approach I posted will definitely be slow... Besides, make sure to read e.g. this thread before editing your question. \$\endgroup\$ – lubgr Mar 20 at 18:25
0
\$\begingroup\$

You must not use static variables for this task. Doing that makes it impossible to have two of these parsers at the same time.

Test cases 1 and 6 are the same.

You are missing some interesting test cases:

  • /* /* 2*/ 1 */
  • /**/
  • /* // */
  • // /* \n word */
  • /// comment
  • // \\u000A next line?

There's no reason to read the input line by line. That only wastes some memory. And for the /* */ it doesn't matter if there are line breaks nearby or not. Therefore having a character reader instead of a line reader is more appropriate.

\$\endgroup\$

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.