Issue 5870 - Implement the new ElemHideEmulation filter type

compiled/filter/ElemHideBase.cpp

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present 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/>.
  */
 
 #include <cstring>
 
 #include "ElemHideBase.h"
 #include "../StringScanner.h"
-
-// the length of a static string array
-#define LENGTH_OF(x) ((sizeof(x) / sizeof(x[0])) - 1)

[sergei, 2018/02/05 14:51:06]

I think we may use constexpr function here, and maybe move it into Utils.h

[hub, 2018/02/07 04:13:37]

No. This has to be a macro because of sizeof() and the use with the argument
that is an array.
Done

[sergei, 2018/02/12 12:53:17]

The following does work
template<typename T, size_t N>
constexpr size_t length_of(T (&)[N])
{
  return N - 1;
}
BTW, I just released that it's a length of string not an array (N - 1 vs N),
what do you think about renaming it to something like get_str_length. In
addition I would replace "static string array" by something like "null
terminated character sequence (string)".

[hub, 2018/02/12 18:14:38]

Done.

[sergei, 2018/02/13 09:12:49]

What about replacing of "static string array" by something like "null
terminated character sequence (string)".

[sergei, 2018/02/13 16:05:59]

It seems only this is left.

[hub, 2018/02/13 16:23:36]

oops.

Done

+#include "../Utils.h"
+
+ABP_NS_USING
 
 namespace
 {
   void NormalizeWhitespace(DependentString& text, String::size_type& domainsEnd,
       String::size_type& selectorStart)
   {
     // For element hiding filters we only want to remove spaces preceding the
     // selector part. The positions we've determined already have to be adjusted
     // accordingly.
 
@@ skipping 12 matching lines @@
         delta++;
       else
         text[pos - delta] = text[pos];
     }
     selectorStart -= delta;
 
     text.reset(text, 0, len - delta);
   }
 
   static constexpr String::value_type ELEM_HIDE_DELIMITER[] = u"##";
-  static constexpr String::size_type ELEM_HIDE_DELIMITER_LEN = LENGTH_OF(ELEM_HIDE_DELIMITER);
+  static constexpr String::size_type ELEM_HIDE_DELIMITER_LEN = str_length_of(ELEM_HIDE_DELIMITER);
 
   static constexpr String::value_type ELEM_HIDE_EMULATION_DELIMITER[] = u"#?#";
-  static constexpr String::size_type ELEM_HIDE_EMULATION_DELIMITER_LEN = LENGTH_OF(ELEM_HIDE_EMULATION_DELIMITER);
-
-  static constexpr String::value_type PROPS_SELECTOR[] = u"[-abp-properties=";
-  static constexpr String::size_type PROPS_SELECTOR_LEN = LENGTH_OF(PROPS_SELECTOR);
-
-  static constexpr String::value_type NEW_PROPS_SELECTOR[] = u":-abp-properties(";

[sergei, 2018/02/05 14:51:05]

I would rather prefer to call it PROPS_SELECTOR and OLD_PROPS_SELECTOR, so later
we can drop OLD_PROPS_SELECTOR.

[hub, 2018/02/07 04:13:36]

Done.

-  static constexpr String::size_type NEW_PROPS_SELECTOR_LEN = LENGTH_OF(NEW_PROPS_SELECTOR);
+  static constexpr String::size_type ELEM_HIDE_EMULATION_DELIMITER_LEN = str_length_of(ELEM_HIDE_EMULATION_DELIMITER);
+
+  static constexpr String::value_type OLD_PROPS_SELECTOR[] = u"[-abp-properties=";
+  static constexpr String::size_type OLD_PROPS_SELECTOR_LEN = str_length_of(OLD_PROPS_SELECTOR);
+
+  static constexpr String::value_type PROPS_SELECTOR[] = u":-abp-properties(";
+  static constexpr String::size_type PROPS_SELECTOR_LEN = str_length_of(PROPS_SELECTOR);
 }
 
 ElemHideBase::ElemHideBase(Type type, const String& text, const ElemHideData& data)
     : ActiveFilter(type, text, false), mData(data)
 {
   if (mData.HasDomains())
     ParseDomains(mData.GetDomainsSource(mText), u',');
 }
 
-Filter::Type ElemHideBase::Parse(DependentString& text, ElemHideData& data)
-{
+Filter::Type ElemHideBase::Parse(DependentString& text, ElemHideData& data, bool& needConversion)
+{
+  needConversion = false;
+
   StringScanner scanner(text);
 
   // Domains part
   bool seenSpaces = false;
   while (!scanner.done())
   {
     String::value_type next = scanner.next();
     if (next == u'#')
     {
       data.mDomainsEnd = scanner.position();
@@ skipping 28 matching lines @@
     return Type::UNKNOWN;
 
   // Selector part
 
   // Selector shouldn't be empty
   seenSpaces |= scanner.skip(u' ');
   if (scanner.done())
     return Type::UNKNOWN;
 
   data.mSelectorStart = scanner.position() + 1;
-  data.mNeedConversion = false;
 
   // We are done validating, now we can normalize whitespace and the domain part
   if (seenSpaces)
     NormalizeWhitespace(text, data.mDomainsEnd, data.mSelectorStart);
   DependentString(text, 0, data.mDomainsEnd).toLower();
 
   // We still need to check the old syntax. It will be converted when
   // we instantiate the filter.
   if (!emulation &&
-      text.find(PROPS_SELECTOR, data.mSelectorStart, PROPS_SELECTOR_LEN) != text.npos)
-  {
-    data.mNeedConversion = true;
+      text.find(OLD_PROPS_SELECTOR, data.mSelectorStart, OLD_PROPS_SELECTOR_LEN) != text.npos)
+  {
+    needConversion = true;
     emulation = !exception;
   }
 
   if (exception)
     return Type::ELEMHIDEEXCEPTION;
 
   if (emulation)
     return Type::ELEMHIDEEMULATION;
 
   return Type::ELEMHIDE;
 }
 
+namespace
+{
+  struct Range
+  {
+    String::size_type start;
+    String::size_type end;
+    String::size_type len() const
+    {
+        return end - start;
+    }
+    String::size_type byte_len() const
+    {
+      return len() * sizeof(String::value_type);
+    }
+  };
+}
+
 // Convert filter from the old syntax to the new.
-OwnedString ElemHideBase::ConvertFilter(const String& text, String::size_type& at)
-{
-  auto selectorPos = text.find(PROPS_SELECTOR, at, PROPS_SELECTOR_LEN);
-  if (selectorPos != text.npos)
-  {
-    auto length = text.length();
-    auto properties = selectorPos + PROPS_SELECTOR_LEN;

[sergei, 2018/02/05 14:51:06]

should it be something like propertiesPos?

[hub, 2018/02/07 04:13:36]

Done.

-    String::value_type quote = 0;
-    bool escape = false;
-    String::size_type removed = 0; // how many chars we remove
-    String::size_type end = properties;
-    String::size_type quote_start = 0;
-    String::size_type quote_end = 0;
-    for (auto index = properties;
-         index < length && end == properties; index++)
-    {
-      if (escape)
-      {
-        escape = false;
-        continue;
-      }
-
-      auto c = text[index];
-      switch (c)
-      {
-      case '\\':

[sergei, 2018/02/05 14:51:05]

should they be u'\\', u'"', etc? Since we keep in mind the possibility to switch
to UTF-8 I also think about some macro like in Windows `_T(x)` (or _TEXT) which
expands to either `Lx` or `x`, perhaps we could have something similar too.
ABP_CHAR and ABP_TEXT?

[hub, 2018/02/07 04:13:36]

yes it should be u'', but with C it works without since we are in the ASCII
realm. Will change it.

-        escape = true;
-        break;
-      case '"':
-      case '\'':
-        if (quote == 0)
-        {
-          quote = c;
-          quote_start = index + 1;
-        }
-        else if (quote == c)
-        {
-          // end of quoted.
-          quote = 0;
-          removed += 2;
-          quote_end = index;
-        }
-        break;
-      case ']':
-        if (quote == 0)
-          end = index + 1; // end of properties (after ])
-        break;
-      default:
-        break;
-      }
-    }

[sergei, 2018/02/05 14:51:05]

It also differs from the regexp in current js implementation
(/\[-abp-properties=(["'])([^"']+)\1\]/) in particular that regexp does not
allow "[-abp-properties='quotedpart1'part2'quotedpart3']", I'm not sure how
flexible we should be here but IMO we should not allow more than is allowed
currently in JS.

[sergei, 2018/02/05 14:51:06]

What if filter is malformed and `end` is equal to zero after the loop? It seems
memcpy below will be pretty dangerous.

[hub, 2018/02/07 04:13:36]

end cannot be equal to zero. It will be at least equal to "properties".

[hub, 2018/02/07 04:13:36]

It's actually worse: the parser doesn't like it at all. The handling of quotes
and escapes is just wrong. I will increase the test coverage and fix it.

-
-    if (quote != 0)
-      quote_end = end - 1;
-    else if (quote_end <= quote_start)
-    {
-      // we likely didn't find a quoted content so we just take it as is.
-      quote_start = properties;
-      quote_end = end - 1;
-    }
-
-    // +1 for the replacement of "##" by "#?#"
-    String::size_type offset = 0;
-
-    String::size_type delimiter = text.find(ELEM_HIDE_DELIMITER, 0,
-                                            ELEM_HIDE_DELIMITER_LEN);
-    OwnedString converted(length + ((delimiter != text.npos) ? 1 : 0) - removed);

[sergei, 2018/02/05 14:51:06]

Since removed cannot be negative (no growth), `text` is originally modifiable
and an old syntax expects quotes, which are removed now, there is no growth, so
what about returning of a DependentString? So, there will no be additional
overhead with constructing of an additional OwnedString.

[hub, 2018/02/07 04:13:36]

I'm not really fond of modifying in place, but we already do that in normalize
and this helps even though the conversion will be still a corner case in the
filter loading.

Will do that, even though this quite complicate things.

-    if (delimiter != text.npos)
-    {
-      if (delimiter >= selectorPos)
-        return OwnedString(text);
-
-      at++;
-      std::memcpy(converted.data(), text.data(),
-                  delimiter * sizeof(String::value_type));
-      offset += delimiter;
-      std::memcpy(converted.data() + offset, ELEM_HIDE_EMULATION_DELIMITER,
-                  ELEM_HIDE_EMULATION_DELIMITER_LEN * sizeof(String::value_type));
-      offset += ELEM_HIDE_EMULATION_DELIMITER_LEN;
-      delimiter += ELEM_HIDE_DELIMITER_LEN;
-      // we have already parsed to past the delimiter.
-      selectorPos -= delimiter;
-    }
-    else
-      delimiter = 0;
-
-
-    std::memcpy(converted.data() + offset, text.data() + delimiter,
-                selectorPos * sizeof(String::value_type));
-    offset += selectorPos;
-
-    std::memcpy(converted.data() + offset, NEW_PROPS_SELECTOR,
-                NEW_PROPS_SELECTOR_LEN * sizeof(String::value_type));
-    offset += NEW_PROPS_SELECTOR_LEN;
-
-    std::memcpy(converted.data() + offset, text.data() + quote_start,
-                (quote_end - quote_start) * sizeof(String::value_type));
-    offset += quote_end - quote_start;
-
-    std::memcpy(converted.data() + offset, u")", sizeof(String::value_type));
-    offset++;
-
-    std::memcpy(converted.data() + offset, text.data() + end,
-                (length - end) * sizeof(String::value_type));
-    offset += (length - end) * sizeof(String::value_type);
-
-    return converted;
-  }
-
-  return OwnedString(text);
+DependentString ElemHideBase::ConvertFilter(String& text, String::size_type& at)
+{
+  Range prefix = {at, text.find(OLD_PROPS_SELECTOR, at, OLD_PROPS_SELECTOR_LEN)};
+  if (prefix.end == text.npos)
+    return DependentString(text);
+
+  auto length = text.length();
+  Range suffix = {at, length};
+  Range properties = { prefix.end + OLD_PROPS_SELECTOR_LEN, 0 };
+  String::value_type quote = 0;
+  for (auto index = properties.start;
+       index < length && (suffix.start == at); index++)
+  {
+    auto c = text[index];
+    switch (c)
+    {
+    case u'"':
+    case u'\'':
+      if (quote == 0)
+      {
+        // syntax error: we already have a quoted section.
+        if (properties.end)
+          return DependentString();
+
+        if (properties.start != index)
+          return DependentString();
+
+        quote = c;
+        properties.start = index + 1;
+      }
+      else if (quote == c)
+      {
+        // end of quoted.
+        quote = 0;
+        properties.end = index;
+      }
+      break;
+    case u']':
+      if (quote == 0)
+      {
+        if (properties.end == 0)
+          return DependentString();
+        if (properties.end + 1 != index)
+          return DependentString();
+        suffix.start = index + 1;
+      }
+      break;
+    default:
+      break;
+    }
+  }
+
+  if (suffix.start == at)

[sergei, 2018/02/27 10:56:53]

Just for reference, I think it (what the whole for-loop above is doing) can be
written in a simpler form, but since it's some sort of interim function it's
fine.

+    return DependentString();
+
+  String::size_type delimiter = text.find(ELEM_HIDE_DELIMITER, 0,
+                                          ELEM_HIDE_DELIMITER_LEN);
+  // +1 for the replacement of "##" by "#?#"
+  if (delimiter != text.npos)
+    at++;
+  auto new_len = at + prefix.len() + PROPS_SELECTOR_LEN + properties.len() + 1 /* ) */ + suffix.len();
+
+  assert2(new_len + 1 == length || (delimiter == text.npos && new_len + 2 == length), u"Inconsistent length in filter conversion."_str);

[sergei, 2018/02/27 10:56:53]

not important just for reference
length == new_len + (delimiter == text.npos ? 2 : 1)
looks shorted and maybe even more logical.

[hub, 2018/02/27 13:32:30]

Acknowledged.

+
+  DependentString converted(text, 0, new_len);
+
+  if (suffix.len())
+  {
+    new_len -= suffix.len();
+    std::memmove(converted.data() + new_len,
+                 text.data() + suffix.start,
+                 suffix.byte_len());
+  }
+  new_len--;
+  // here we need to move the properties before inserting the ')'
+  auto parens = new_len;
+  if (properties.len())
+  {
+    new_len -= properties.len();
+    std::memmove(converted.data() + new_len,
+                 text.data() + properties.start, properties.byte_len());
+  }
+  converted[parens] = u')';
+
+  new_len -= PROPS_SELECTOR_LEN;
+  std::memcpy(converted.data() + new_len,
+              PROPS_SELECTOR,
+              PROPS_SELECTOR_LEN * sizeof(String::value_type));
+  if (prefix.len())
+  {
+    new_len -= prefix.len();
+    std::memmove(converted.data() + new_len,
+                 text.data() + prefix.start, prefix.byte_len());
+  }
+
+  if (delimiter != String::npos)
+  {
+    std::memcpy(converted.data() + delimiter, ELEM_HIDE_EMULATION_DELIMITER,
+                ELEM_HIDE_EMULATION_DELIMITER_LEN * sizeof(String::value_type));
+  }
+
+  return converted;
 }
 
 namespace
 {
   static constexpr String::value_type OPENING_CURLY_REPLACEMENT[] = u"\\7B ";
   static constexpr String::value_type CLOSING_CURLY_REPLACEMENT[] = u"\\7D ";
-  static constexpr String::size_type CURLY_REPLACEMENT_SIZE = LENGTH_OF(OPENING_CURLY_REPLACEMENT);
+  static constexpr String::size_type CURLY_REPLACEMENT_SIZE = str_length_of(OPENING_CURLY_REPLACEMENT);
 
   OwnedString EscapeCurlies(String::size_type replacementCount,
                             const DependentString& str)
   {
     OwnedString result(str.length() + replacementCount * (CURLY_REPLACEMENT_SIZE - 1));
 
     String::value_type* current = result.data();
     for (String::size_type i = 0; i < str.length(); i++)
     {
       switch(str[i])
@@ skipping 43 matching lines @@
       if (item.second && !item.first.empty())
       {
         if (!result.empty())
           result.append(u',');
         result.append(item.first);
       }
     }
   }
   return result;
 }