Issue #1234 - Remove 'CString' from PluginFilter.*

src/plugin/TokenSequence.h

+/*
+ * This file is part of Adblock Plus <https://adblockplus.org/>,
+ * Copyright (C) 2006-2015 Eyeo GmbH
+ *
+ * Adblock Plus is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 3 as
+ * published by the Free Software Foundation.
+ *
+ * Adblock Plus is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
+ */
+
+template<class T> class TokenSequenceConstIterator; // forward declaration
+
+/**
+ * A sequence of delimited tokens contained within a given string.
+ */
+template<class T>
+class TokenSequence
+{
+  typedef TokenSequenceConstIterator<T> ConstIterator;

[sergei, 2016/01/25 14:13:52]

I would like to have it as a public member and name it as `const_iterator`. It
might does not fully support iterator API, but it's still good to have it
STL-like.

[Eric, 2016/01/26 15:54:19]

When our style guide at https://adblockplus.org/en/coding-style has a specific
exemption for this, I'll gladly change it.

[sergei, 2016/01/26 22:34:58]

I thought that it's natural to adhere to common iterator interface. Why do
`cbegin` and `cend` start from lower letter and have "c"? I really don't want
them to be renamed, but it would be definitely better to have public
`const_iterator`.

+  friend class ConstIterator;
+  const T delimiters;
+  const T value;
+
+  /**
+   * Default constructor is deleted
+   */
+  TokenSequence(); // = delete
+
+public:
+  TokenSequence(const T& value, const T& delimiters)
+    : value(value), delimiters(delimiters)
+  {
+    if (delimiters.empty())
+    {
+      // If we don't have delimiter characters, the 'first_first_*' functions will have undefined behavior.
+      throw std::runtime_error("Must have at least one delimiter character");
+    }
+  }
+
+  ConstIterator cbegin() const
+  {
+    return ConstIterator(*this, ConstIterator::BeginMarker());
+  }
+
+  ConstIterator cend() const
+  {
+    return ConstIterator(*this, ConstIterator::EndMarker());
+  }
+};
+
+/**
+ * Iterator class for TokenSequence<T>
+ *
+ * All constructors are private, only available to TokenSequence<T> through a friend declaration.
+ *
+ * Invariant
+ *   if posFirstCharInToken == npos
+ *     iterator is "end()"
+ *   else
+ *     0 <= posFirstCharInToken < posFirstCharNotInToken <= length of underlying container string
+ *     first token position = posFirstCharInToken
+ *     token length = posFirstCharNotInToken - posFirstCharInToken
+ */
+template<class T>
+class TokenSequenceConstIterator
+{
+  typedef TokenSequence<T> Container;
+  friend class Container;
+  const Container& sequence;

[sergei, 2016/01/25 14:13:54]

I'm pretty sure it generates a warning something like "The compiler cannot
generate copy ctr and assignment operator."
Could you explicitly make this class "uncopyable"?

[Eric, 2016/01/26 15:54:20]

I am completely sure it does not generate a warning, because I've compiled the
code.
I would worry about this more if I were writing a proper library class. As it
is, I've now got multiple changes that depend on this code and I am resistant to
making changes that don't involve defects or other major problems.

[sergei, 2016/01/26 22:34:57]

OK, our warning level does not generate a warning here, but it does not mean
that we should not write a clean code.
I think that these classes are quite generic and deserve a proper
implementation. If it's so specific, why is it a template class and why is it
not mentioned in the comments that it's not something which can be safely widely
used?
It's not clear what are these multiple changes that depend on this code. Anyway,
it shouldn't be a reason that allows to commit dirty code.

+  size_t posFirstCharInToken;

[sergei, 2016/01/25 14:13:54]

Wouldn't it better to name it as `tokenFirstCharPos[ition]` because it's a
position of the first character of the token in the container.

[Eric, 2016/01/26 15:54:20]

It's "position of the first character in the token". It's generally better to
put what kind of thing it is first in the name if you're dealing with an
inadequate type system. (Positions in strings should be their own type, IMO, but
they're not.)

[sergei, 2016/01/26 22:34:57]

Let's say there is a string "aaa bbb ccc", after tokenization using space as a
delimiter we get three tokens: "aaa", "bbb" and "ccc". The "position of the
first character in token" is apparently always 1 (or zero if we are using
zero-based numbering), however the position of the first character of each token
in the container is different, for "aaa" it's 1, for "bbb" it's 5 and for "ccc"
it's 9.
I don't have a strong opinion regarding position of "pos" but the rest of the
name is confusing.

+  size_t posFirstCharNotInToken;

[sergei, 2016/01/25 14:13:53]

And this one is a position of the next delimiter, so something like
`nextDelimiterPos`.

[Eric, 2016/01/26 15:54:21]

Your suggested name is not as precise as the current one.

These two variables are the endpoints of a half-closed, half-open interval of
positions that define a token, and their names reflect exactly that.

[sergei, 2016/01/26 22:34:58]

That's clear that it's a right-open interval, BTW, you can explain it in the
comments. You are right, the first character of not token is a delimiter or
nothing (can be unknown character) but in my opinion during the reading of the
code it's easier to consider the end of the string as a delimiter than read a
little bit complicated variable name. It would be already better to name it
`posNotTokenFirstChar`.

+
+  class BeginMarker {};
+  class EndMarker {};
+
+  /**
+   * Default constructor is deleted
+   */
+  TokenSequenceConstIterator(); // = delete
+
+  /**
+   * Constructor for cbegin()
+   */
+  TokenSequenceConstIterator(const TokenSequence<T>& sequence, BeginMarker)
+    : sequence(sequence)
+  {
+    Advance(0);
+  }
+
+  /**
+   * Constructor for cend()
+   */
+  TokenSequenceConstIterator(const TokenSequence<T>& sequence, EndMarker)
+    : sequence(sequence), posFirstCharInToken(T::npos)

[sergei, 2016/01/25 14:13:54]

I feel myself uncomfortable when not all members without default constructor are
initialized.

[Eric, 2016/01/26 15:54:20]

If you would like a comment about why 'posFirstCharNotInToken' is not
initialized, I can add one. It's a deliberate choice. The current code
initializes to a valid iterator state; that's all that matters.

[sergei, 2016/01/26 22:34:57]

Don't forget about readability and maintainability. When I see that the member
field is not initialized the first thing I think is that there is a bug and I
need to check the implementation of the whole class. 
Here comparing `posFirstCharInToken` against `npos` might always tell us whether
we may or not use other fields, but in general when I need to modify the class
(e.g. add some method), again I need to very cautiously check that it will be in
a consistent state and to do it I need dive into details of all algorithms with
all their edge-cases.

Off-topic: do you cross a street driving car on red light when there is nobody?
Basically, it's safe and you achieve the goal, that's all that matters, isn't
it?

+  {
+  }
+
+  /**
+   * Find the next token beginning at or after the given position
+   */
+  void Advance(size_t posStart)

[sergei, 2016/01/25 14:13:54]

Wouldn't it be better to rename it to something like `FindNextToken` because
`Advance` refers rather to a sequence of calls of `iterator::operator++` in
context of iterators.

[Eric, 2016/01/26 15:54:19]

It's better to name functions "what they do" than "how they work". In this case,
"Advance" is named relative to the constructor and 'operator++', meaning
"advance to the next token".

[sergei, 2016/01/26 22:34:57]

"advance to the next token" actually means `find next token`, does not it?
In general `Advance` is fine for me.

+  {
+    posFirstCharInToken = sequence.value.find_first_not_of(sequence.delimiters, posStart);

[sergei, 2016/01/25 14:13:53]

That line "eats" all delimiters and skips empty tokens, that's very important
moment. It should be reflected at least in the comment for `TokenSequence`, it
also could be good to have it commented here.

[Eric, 2016/01/26 15:54:19]

From my point of view, it's completely conventional to collapse multiple
whitespace delimiter characters into a single delimiter. Please don't use this
class with "comma" as a delimiter.

If this were a general purpose class, I'd worry about this more.

[sergei, 2016/01/26 22:34:57]

Why not to use it with comma as a delimiter and how will one be able to
understand it in a year?
BTW, the actual limitation I see here, it won't work when a delimiter character
consists from several elements (several bytes for UTF-8 or it's a surrogate pair
for UTF-16). I have not commented it before and I don't think we should pay
attention to it, because if we ever need such functionality we will pay
attention to each method which works with the string.

+    if (posFirstCharInToken == T::npos)
+    {
+      // If we've become an "end()" iterator, we're done.
+      return;
+    }
+    posFirstCharNotInToken = sequence.value.find_first_of(sequence.delimiters, posFirstCharInToken + 1);
+    if (posFirstCharNotInToken == T::npos)
+    {
+      posFirstCharNotInToken = sequence.value.length();
+    }
+  }
+
+public:
+  bool operator==(const TokenSequenceConstIterator& other) const
+  {
+    if (&sequence != &other.sequence)
+    {
+      return false; // iterators to different sequences cannot be equal
+    }
+    // Iterators with the same initial token position will also have the same final final position
+    // "end()" iterators use "npos" as their position
+    return posFirstCharInToken == other.posFirstCharInToken;
+  }
+
+  bool operator!=(const TokenSequenceConstIterator& other) const
+  {
+    return !operator==(other);
+  }
+
+  void operator++()

[sergei, 2016/01/25 14:13:53]

It seems we are not using it, but it can be very convenient to return `*this`
from the prefix increment operator.

[Eric, 2016/01/26 15:54:20]

Right. We're not using it. So no need for a return value.

Again: this is not a general purpose library function. If it ever does, that's
the time to add such things.

+  {
+    if (posFirstCharInToken == T::npos)
+    {
+      return; // Incrementing "end()" yields "end()"

[sergei, 2016/01/25 14:13:52]

Should we throw an exception here instead?

[Eric, 2016/01/26 15:54:20]

In fact, the way that this code is used in 'for' loops, this statement is never
actually reached in any code we'll use. The presence of this test is purely
defensive.

And to answer the question directly, no, because that would not be the
documented behavior, which is that incrementing "end()" yields "end()".
Thankfully, this is not a library function, so we don't need to debate what
interface would be better for general purpose use.

[sergei, 2016/01/26 22:34:58]

It defensive but it protects silently, if we are trying to increase it then
there is likely a bug and it would be better to be notified about it. I would
personally use assert, but in this project we are extensively using pure
exceptions for such cases.
IMO, incrementing of undereferenceable iterator is an error because it's not
expected in C++.

+    }
+    if (posFirstCharNotInToken >= sequence.value.length())
+    {
+      // We are already at the end of the sequence. No need to search more.
+      posFirstCharInToken = T::npos;

[sergei, 2016/01/25 14:13:53]

I'm not sure that we actually need to make an assignment here, actually
`posFirstCharNotInToken` cannot be bigger than `sequence.value.length()`, but I
don't object against `>=` in the clause above.

[Eric, 2016/01/26 15:54:19]

The very simple answer is that we're incrementing from a non-"end()" iterator to
the "end()" iterator, and there's a single canonical value for "end()". That's
valuable because it makes 'operator==' much less complicated.

If we didn't have this statement, loops on the iterator would never terminate.

The class invariant is that if a token is present, both 'posFirstCharNotInToken'
and 'posFirstCharInToken' be string positions. See line 161 below for why. The
design decision here is that these position tests go in the state-change
functions. Access and predicate functions therefore do not perform such tests.

Lines 117-120 above are a related test. Those fix up the 'npos' return value
into a proper length.

Using ">=" is slightly clearer to me than using "==". It's never the case that
this test is reached with a positive value greater than then length.

[sergei, 2016/01/26 22:34:58]

Sorry, I have overlooked it, I have wrongly read `posFirstCharInToken` as
`posFirstCharNotInToken`. Anyway, now I think that this assignment should be
inside `Advance` method.

+      return;

[sergei, 2016/01/25 14:13:54]

Should we rather throw an exception?

[Eric, 2016/01/26 15:54:20]

Never. Incrementing to "end()" is not an error.

+    }
+    Advance(posFirstCharNotInToken + 1);
+  }
+
+  T operator*() const
+  {
+    if (posFirstCharInToken == T::npos)
+    {
+      throw std::runtime_error("Cannot dereference end() iterator");
+    }
+    return sequence.value.substr(posFirstCharInToken, posFirstCharNotInToken - posFirstCharInToken);
+  }
+};