Issue 4125 - [emscripten] Convert filter classes to C++

compiled/String.h

 #pragma once
 
 #include <cstddef>
 #include <cstring>
 #include <algorithm>
+
+#include <emscripten.h>
 
 #include "debug.h"
 
 inline void String_assert_readonly(bool readOnly);
 
 class String
 {
   friend class DependentString;
   friend class OwnedString;
 
 public:
   typedef char16_t value_type;
   typedef size_t size_type;
 
   // Type flags, stored in the top 2 bits of the mLen member
   static constexpr size_type INVALID = 0xC0000000;
   static constexpr size_type DELETED = 0x80000000;
   static constexpr size_type READ_ONLY = 0x40000000;
   static constexpr size_type READ_WRITE = 0x00000000;
 
   static constexpr size_type FLAGS_MASK = 0xC0000000;
   static constexpr size_type LENGTH_MASK = 0x3FFFFFFF;
 
   static constexpr size_type npos = -1;
 
 protected:
   value_type* mBuf;
   size_type mLen;
 
-  String(value_type* buf, size_type len, size_type flags)
+  explicit String(value_type* buf, size_type len, size_type flags)
       : mBuf(buf), mLen((len & LENGTH_MASK) | flags)
+  {
+  }
+
+  ~String()
   {
   }
 
   void reset(value_type* buf, size_type len, size_type flags)
   {
     mBuf = buf;
     mLen = (len & LENGTH_MASK) | flags;
   }
 

[sergei, 2016/02/17 12:54:53]

What about adding protected destructor or virtual destructor? In that case
nobody will be able to accidentally forget to call the destructor of the derived
class.

[Wladimir Palant, 2016/02/18 16:06:53]

Nice one, I thought that having a protected constructor would already prevent
instantiating the String class - apparently not, I had this in a few places in
the codebase still.

 public:
   size_type length() const
   {
     return mLen & LENGTH_MASK;
   }
 
   bool empty() const
   {
     return !(mLen & LENGTH_MASK);
   }
@@ skipping 36 matching lines @@
   size_type find(value_type c, size_type pos = 0) const
   {
     for (size_type i = pos; i < length(); ++i)
       if (mBuf[i] == c)
         return i;
     return npos;
   }
 
   size_type find(const String& str, size_type pos = 0) const
   {
+    if (pos > LENGTH_MASK || pos + str.length() > length())
+      return npos;
+
     if (!str.length())
       return pos;

[sergei, 2016/02/17 12:54:39]

Strictly speaking, if `pos > this->length()` then it should not find even empty
`str`, returning `npos` in that case seems reasonable, I guess.

[Wladimir Palant, 2016/02/18 16:06:58]

Done.

 
-    if (length() - pos < str.length())

[sergei, 2016/02/17 12:54:42]

We also should check whether `this->length()` is not zero.
If it's zero then `pos < length() - str.length();` (it's below in for-loop) is
likely to be true however the mBuf is likely to be nullptr.

[Wladimir Palant, 2016/02/18 16:06:47]

If length() is 0 then length() - pos will be at most 0 and smaller than
str.length() which is non-zero. So this scenario is already covered.

Btw, I modified the conditions here to use addition rather than subtraction - we
don't want this to go into negative with unsigned numbers.

[sergei, 2016/02/22 12:45:46]

I wanted to have at the beginning of the method the following code

bool isFindable = pos <= length() && str.length() <= length() - pos;
if (!isFindable)
  return npos;

Any integer overflow with unsigned integers in C++ results in unsigned integer
(and it's undefined behavior for signed integers). So, `pos + str.length() >
length()` can be false but it still does not protect from accessing beyond the
size of mBuf, e.g.
length = 10;
pos = npos - 5 (pos > length)
str.length = 10;

pos + str.length = 4 ( 4 <= length)


In addition I have just realized that in our particular case we cannot get
integer overflow because the length is limited by LENGTH_MASK, though we should
verify that `pos <= LENGTH_MASK` (actually, the proposed `isFindable` covers
it).

[Wladimir Palant, 2016/02/23 12:37:21]

Yes, in our case an integer overflow is luckily impossible because we aren't
using the upper two bits of the length. That's exactly why I changed the
comparisons to use addition rather than subtraction, this way it is safe.

[sergei, 2016/02/23 15:07:27]

As a matter of form we still need to check that `pos <= LENGTH_MASK`.

[Wladimir Palant, 2016/02/23 21:34:54]

True, done.

-      return npos;
-
-    for (; pos < length() - str.length(); ++pos)
+    for (; pos + str.length() <= length(); ++pos)
     {
       if (mBuf[pos] == str[0] &&
           std::memcmp(mBuf + pos, str.mBuf, sizeof(value_type) * str.length()) == 0)
       {
         return pos;
       }
     }
 
     return npos;
   }
 
   size_type rfind(value_type c, size_type pos = npos) const
   {
     if (length() == 0)
       return npos;
 
-    if (pos == npos)
+    if (pos >= length())
       pos = length() - 1;

[sergei, 2016/02/17 12:54:54]

It seems safer to use something like `pos = min(pos, length() - 1);` because
`pos` can belong to [length(), npos).

[Wladimir Palant, 2016/02/18 16:06:46]

Done.

 
     for (int i = pos; i >= 0; --i)
       if (mBuf[i] == c)
         return i;
     return npos;
   }
+
+  bool is_invalid() const
+  {
+    return (mLen & FLAGS_MASK) == INVALID;
+  }
+
+  bool is_deleted() const
+  {
+    return (mLen & FLAGS_MASK) == DELETED;
+  }
+
+  void toLower()
+  {
+    size_type len = length();
+    for (size_type i = 0; i < len; ++i)
+    {
+      value_type currChar = mBuf[i];
+
+      // This should be more efficient with a lookup table but I couldn't measure
+      // any performance difference.
+      if (currChar >= u'A' && currChar <= u'Z')
+        mBuf[i] = currChar + u'a' - u'A';
+      else if (currChar >= 128)
+      {
+        // It seems that calling JS is the easiest solution for lowercasing
+        // Unicode characters.
+        mBuf[i] = EM_ASM_INT({
+          return String.fromCharCode($0).toLowerCase().charCodeAt(0);
+        }, currChar);
+      }
+    }
+  }
 };
 
 class DependentString : public String
 {
 public:
-  DependentString()
+  explicit DependentString()
       : String(nullptr, 0, INVALID)
   {
   }
 
-  DependentString(value_type* buf, size_type len)
+  explicit DependentString(value_type* buf, size_type len)
       : String(buf, len, READ_WRITE)
   {
   }
 
-  DependentString(const value_type* buf, size_type len)
+  explicit DependentString(const value_type* buf, size_type len)
       : String(const_cast<value_type*>(buf), len, READ_ONLY)
   {
   }
 
-  DependentString(String& str, size_type pos = 0, size_type len = npos)

[sergei, 2016/02/17 12:54:51]

I would add `explicit` for this particular method.

[Wladimir Palant, 2016/02/18 16:06:51]

Why? I think that passing OwnedString to a function requiring DependentString
and having it converted implicitly is desired.

[sergei, 2016/02/22 12:45:45]

May be it's desired. It seems it's not actually used now.

[Wladimir Palant, 2016/02/23 12:37:26]

It's being used in various getters, e.g. Filter::GetText (the const variant
below actually).

Is your concern that we would end up unintentionally creating a persistent
DependentString instance based on a temporary OwnedString instance?

[sergei, 2016/02/23 15:07:26]

Yes, the variant with const, but this constructor is not used.
No, it's difficult to say what was confusing here. Let's keep it, actually it
looks good and useful.
I guess, I wanted to see where it's used because it can help to identify whether
we really need `DependentString` or the argument can be simply `String&`.

BTW, just wonder, why do we use `EMSCRIPTEN_KEEPALIVE const DependentString`
instead of `EMSCRIPTEN_KEEPALIVE const String&`? I have tried to change it but
could not get all tests passing because it requires to have a good understanding
of what is happening in bindings.{h,js} where I have not carefully looked yet.

[Wladimir Palant, 2016/02/23 21:34:54]

bindings.h currently enforces the return value to be either DependentString or
OwnedString, other string types won't be accepted. Reason is that it needs to
know the calling convention and it needs to know whether the string destructor
should be called. Returning String& is a good idea, it changes the calling
convention however - there is a return value in this case. So bindings.h has to
learn that scenario.

I've done it now, there was unexpected trouble however. With a reference as
result Filter::GetText() will no longer error out if called with invalid
parameters, consequently my hack getting the function name doesn't work. I
realized that the same thing can be done more reliably by filling up the stack
before calling the function.

I also marked these two constructors explicit as nothing is using them
implicitly any more.

+  explicit DependentString(String& str, size_type pos = 0, size_type len = npos)
       : String(
           str.mBuf + std::min(pos, str.length()),
           std::min(len, str.length() - std::min(pos, str.length())),
-          READ_WRITE
+          str.is_readOnly() ? READ_ONLY : READ_WRITE
         )
   {
   }
 
-  DependentString(const String& str, size_type pos = 0, size_type len = npos)
+  explicit DependentString(const String& str, size_type pos = 0,
+      size_type len = npos)
       : String(
           str.mBuf + std::min(pos, str.length()),
           std::min(len, str.length() - std::min(pos, str.length())),
           READ_ONLY
         )
   {
   }
 
   void reset(value_type* buf, size_type len)
   {
     *this = DependentString(buf, len);
   }
 
   void reset(const value_type* buf, size_type len)
   {
     *this = DependentString(buf, len);
   }
 
   void reset(String& str, size_type pos = 0, size_type len = npos)
   {
     *this = DependentString(str, pos, len);
   }
 
   void reset(const String& str, size_type pos = 0, size_type len = npos)
   {
     *this = DependentString(str, pos, len);
   }
 
-  bool is_invalid() const

[sergei, 2016/02/17 12:54:52]

what about moving it into base class String?

[Wladimir Palant, 2016/02/18 16:06:52]

Given that it is only necessary for StringMap - why?

[sergei, 2016/02/22 12:45:49]

Because flag values are defined in `String`, flag value is stored in the member
of `String` and there is `String::is_readOnly` method, it seems `String` class
is a better place for methods which work with flags.

[Wladimir Palant, 2016/02/23 12:37:24]

Done.

-  {
-    return (mLen & FLAGS_MASK) == INVALID;
-  }
-
-  bool is_deleted() const
-  {
-    return (mLen & FLAGS_MASK) == DELETED;

[sergei, 2016/02/17 12:54:49]

How can it actually happen? It seems it is never set to DELETED explicitly and
we don't subtract READ_ONLY from INVALID.

This method is not used actually.

[Wladimir Palant, 2016/02/18 16:06:55]

No, it's not - yet. The reason is that StringMap currently won't remove any
entries. Once we add this functionality we'll need a special value to mark
buckets with deleted entries.

[sergei, 2016/02/22 12:45:50]

Acknowledged.

+  void erase()
+  {
+    *this = DependentString();
+    mLen = DELETED;
   }
 };
 
+inline DependentString operator "" _str(const String::value_type* str,
+    String::size_type len)
+{
+  return DependentString(str, len);
+}
+
+inline void String_assert_readonly(bool readOnly)
+{
+  assert(!readOnly, u"Writing access to a read-only string"_str);
+}
+
 class OwnedString : public String
 {
 private:
-  value_type* allocate(size_type len)
+  void grow(size_type additionalSize)
+  {
+    OwnedString newValue(length() + additionalSize);
+    if (length() > 0)
+      std::memcpy(newValue.mBuf, mBuf, sizeof(value_type) * length());
+    *this = std::move(newValue);
+  }
+
+public:
+  explicit OwnedString(size_type len = 0)
+      : String(nullptr, len, READ_WRITE)
   {
     if (len)
-      return new value_type[len];
+    {
+      mBuf = new value_type[length()];
+      annotate_address(mBuf, "String");
+    }
     else
-      return nullptr;
-  }
-
-  void resize(size_type newLength, bool copy)

[sergei, 2016/02/17 12:54:43]

I'm not sure about `copy` argument, it's called only once with `copy` equal to
`true`.

[Wladimir Palant, 2016/02/18 16:06:49]

Indeed, not any more - removed that parameter.

-  {
-    size_type oldLength = length();
-    value_type* oldBuffer = mBuf;
-
-    reset(nullptr, newLength, READ_WRITE);
-    newLength = length();
-    mBuf = allocate(newLength);
-    annotate_address(mBuf, "String");
-
-    if (copy && oldLength)
-      std::memcpy(mBuf, oldBuffer, sizeof(value_type) * std::min(oldLength, newLength));

[sergei, 2016/02/17 12:54:41]

If either destination or source buffer is nullptr then here is undefined
behaviour.

Here oldBuffer can be nullptr.

[Wladimir Palant, 2016/02/18 16:06:57]

oldLength is non-zero so oldBuffer cannot be nullptr. Destination buffer also
cannot be nullptr given that currently only growing the buffer is supported, not
shrinking it. I made this more clear by renaming the function into grow() and
removing the pointless std::min() here.

[sergei, 2016/02/22 12:45:38]

Acknowledged, sorry, overlooked.

-    if (oldBuffer)
-      delete[] oldBuffer;
-  }
-
-public:
-  OwnedString(size_type len = 0)
-      : String(nullptr, len, READ_WRITE)
-  {
-    mBuf = allocate(length());
-    annotate_address(mBuf, "String");
-  }
-
-  OwnedString(const String& str)
+      mBuf = nullptr;
+  }
+
+  explicit OwnedString(const String& str)
       : OwnedString(str.length())
   {
-    std::memcpy(mBuf, str.mBuf, sizeof(value_type) * length());

[sergei, 2016/02/17 12:54:40]

Here both mBuf and str.mBuf can be nullptr.

[Wladimir Palant, 2016/02/18 16:06:54]

Should be fine as length() will be 0 in that case?

[sergei, 2016/02/22 12:45:48]

According to http://en.cppreference.com/w/cpp/string/byte/memcpy - no,
"If either dest or src is a null pointer, the behavior is undefined, even if
count is zero."

[Wladimir Palant, 2016/02/23 12:37:23]

Done.

+    if (length())
+      std::memcpy(mBuf, str.mBuf, sizeof(value_type) * length());
   }
 
   OwnedString(const OwnedString& str)
       : OwnedString(static_cast<const String&>(str))
   {
   }
 
-  OwnedString(const value_type* str, size_type len)
+  explicit OwnedString(const value_type* str, size_type len)
       : OwnedString(DependentString(str, len))
   {
   }
 
-  OwnedString(OwnedString&& str)
-      : OwnedString(str.length())
-  {
-    mBuf = str.mBuf;
-    str.mBuf = nullptr;
-    str.mLen = READ_WRITE | 0;
-  }
-
-  OwnedString(const char* source, size_type len)
-      : OwnedString(len)
-  {
-    for (size_type i = 0; i < len; i++)
-      mBuf[i] = source[i];
-  }
-
-  ~OwnedString()
-  {
-    if (mBuf)
-      delete[] mBuf;
-  }
-
-  OwnedString& operator=(const String& str)
-  {
-    *this = std::move(OwnedString(str));
-    return *this;
-  }
-
-  OwnedString& operator=(const OwnedString& str)
-  {
-    *this = std::move(OwnedString(str));
-    return *this;
-  }
-
-  OwnedString& operator=(OwnedString&& str)
+  explicit OwnedString(OwnedString&& str)
+      : OwnedString(0)
   {
     mBuf = str.mBuf;
     mLen = str.mLen;
     str.mBuf = nullptr;
     str.mLen = READ_WRITE | 0;
+  }
+
+  ~OwnedString()
+  {
+    if (mBuf)
+      delete[] mBuf;
+  }
+
+  OwnedString& operator=(const String& str)
+  {
+    *this = std::move(OwnedString(str));
+    return *this;
+  }
+
+  OwnedString& operator=(const OwnedString& str)
+  {
+    *this = std::move(OwnedString(str));
+    return *this;
+  }
+
+  OwnedString& operator=(OwnedString&& str)
+  {
+    std::swap(mBuf, str.mBuf);
+    std::swap(mLen, str.mLen);
     return *this;
   }
 
   void append(const value_type* source, size_type sourceLen)
   {
     if (!sourceLen)

[sergei, 2016/02/17 12:54:50]

it would be also good to check that source is not nullptr.

[Wladimir Palant, 2016/02/18 16:06:50]

That would be a bug in the caller - meaning that we should crash, not ignore the
issue. I added an assert() call.

[sergei, 2016/02/22 12:45:39]

Good.

       return;
 
+    assert(source, u"Null buffer passed to OwnedString.append()"_str);
     size_t oldLength = length();
-    resize(oldLength + sourceLen, true);
+    grow(sourceLen);
     std::memcpy(mBuf + oldLength, source, sizeof(value_type) * sourceLen);
   }
 
   void append(const String& str)
   {
     append(str.mBuf, str.length());
   }
 
   void append(value_type c)
   {
     append(&c, 1);
   }
 };
-
-inline DependentString operator "" _str(const String::value_type* str,
-    String::size_type len)
-{
-  return DependentString(str, len);
-}
-
-inline void String_assert_readonly(bool readOnly)
-{
-  assert(!readOnly, u"Writing access to a read-only string"_str);
-}