StringView.split() should use an iterator design pattern instead of allocating a...
authordbates@webkit.org <dbates@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 24 Jan 2017 17:44:50 +0000 (17:44 +0000)
committerdbates@webkit.org <dbates@webkit.org@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Tue, 24 Jan 2017 17:44:50 +0000 (17:44 +0000)
https://bugs.webkit.org/show_bug.cgi?id=163225

Reviewed by Darin Adler.

Source/WebCore:

Update code to use the new iterator-style StringView.split().

* platform/URLParser.cpp:

Source/WTF:

Implement StringView.split() using an iterator design.

Using an iterator design avoids the need to allocate a Vector of StringView objects,
which is space-inefficient and error prone as the returned Vector may outlive the
lifetime of the underlying string associated with the split (as StringView is a non-
owning reference to a string).

StringView.split() now returns a StringView::SplitResult object that implements begin()/end()
to support iterating over StringView substrings delimited by the specified separator
character. For example, to iterate over the 'c'-separated substrings of a StringView v,
you can write:

for (StringView substring : v.split('c'))
    // Do something with substring.

* wtf/text/StringView.cpp:
(WTF::StringView::SplitResult::Iterator::findNextSubstring): Advances the iterator to point to the
next substring.
(WTF::StringView::split): Modified to return a SplitResult::Iterator object instead of a Vector<StringView>.
* wtf/text/StringView.h:
(WTF::StringView::SplitResult::SplitResult):
(WTF::StringView::SplitResult::Iterator::Iterator):
(WTF::StringView::SplitResult::Iterator::operator*):
(WTF::StringView::SplitResult::Iterator::operator==):
(WTF::StringView::SplitResult::Iterator::operator!=):
Implements the iterator interface.

Tools:

Add unit tests for StringView.split().

* TestWebKitAPI/Tests/WTF/StringView.cpp:
(TestWebKitAPI::stringViewFromLiteral): Moved to the top of the file so that it can be
used in the StringView.split() unit tests.
(TestWebKitAPI::stringViewFromUTF8): Ditto.
(TestWebKitAPI::vectorFromSplitResult): Convenience function to convert a StringView::SplitResult
object to a Vector of String objects.
(TestWebKitAPI::TEST): Added the following tests:
    - WTF.StringViewSplitEmptyAndNullStrings
    - WTF.StringViewSplitBasic
    - WTF.StringViewSplitWithConsecutiveSeparators

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@211087 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/text/StringView.cpp
Source/WTF/wtf/text/StringView.h
Source/WebCore/ChangeLog
Source/WebCore/platform/URLParser.cpp
Tools/ChangeLog
Tools/TestWebKitAPI/Tests/WTF/StringView.cpp

index 4b6592f..cf66ba6 100644 (file)
@@ -1,3 +1,37 @@
+2017-01-24  Daniel Bates  <dabates@apple.com>
+
+        StringView.split() should use an iterator design pattern instead of allocating a Vector
+        https://bugs.webkit.org/show_bug.cgi?id=163225
+
+        Reviewed by Darin Adler.
+
+        Implement StringView.split() using an iterator design.
+
+        Using an iterator design avoids the need to allocate a Vector of StringView objects,
+        which is space-inefficient and error prone as the returned Vector may outlive the
+        lifetime of the underlying string associated with the split (as StringView is a non-
+        owning reference to a string).
+
+        StringView.split() now returns a StringView::SplitResult object that implements begin()/end()
+        to support iterating over StringView substrings delimited by the specified separator
+        character. For example, to iterate over the 'c'-separated substrings of a StringView v,
+        you can write:
+
+        for (StringView substring : v.split('c'))
+            // Do something with substring.
+
+        * wtf/text/StringView.cpp:
+        (WTF::StringView::SplitResult::Iterator::findNextSubstring): Advances the iterator to point to the
+        next substring.
+        (WTF::StringView::split): Modified to return a SplitResult::Iterator object instead of a Vector<StringView>.
+        * wtf/text/StringView.h:
+        (WTF::StringView::SplitResult::SplitResult):
+        (WTF::StringView::SplitResult::Iterator::Iterator):
+        (WTF::StringView::SplitResult::Iterator::operator*):
+        (WTF::StringView::SplitResult::Iterator::operator==):
+        (WTF::StringView::SplitResult::Iterator::operator!=):
+        Implements the iterator interface.
+
 2017-01-20  Joseph Pecoraro  <pecoraro@apple.com>
 
         Remove outdated ENABLE(CSP_NEXT) build flag
index d78562e..5807997 100644 (file)
@@ -1,6 +1,6 @@
 /*
 
-Copyright (C) 2014, 2016 Apple Inc. All rights reserved.
+Copyright (C) 2014-2017 Apple Inc. All rights reserved.
 
 Redistribution and use in source and binary forms, with or without
 modification, are permitted provided that the following conditions
@@ -94,6 +94,28 @@ size_t StringView::find(StringView matchString, unsigned start) const
     return findCommon(*this, matchString, start);
 }
 
+void StringView::SplitResult::Iterator::findNextSubstring()
+{
+    for (size_t separatorPosition; (separatorPosition = m_result.m_string.find(m_result.m_separator, m_position)) != notFound; ++m_position) {
+        if (separatorPosition > m_position) {
+            m_length = separatorPosition - m_position;
+            return;
+        }
+    }
+    m_length = m_result.m_string.length() - m_position;
+}
+
+auto StringView::SplitResult::Iterator::operator++() -> Iterator&
+{
+    ASSERT(m_position < m_result.m_string.length());
+    m_position += m_length;
+    if (m_position < m_result.m_string.length()) {
+        ++m_position;
+        findNextSubstring();
+    }
+    return *this;
+}
+
 class StringView::GraphemeClusters::Iterator::Impl {
 public:
     Impl(const StringView& stringView, std::optional<NonSharedCharacterBreakIterator>&& iterator, unsigned index)
@@ -142,21 +164,6 @@ private:
     unsigned m_indexEnd;
 };
 
-Vector<StringView> StringView::split(UChar separator)
-{
-    Vector<StringView> result;
-    unsigned startPos = 0;
-    size_t endPos;
-    while ((endPos = find(separator, startPos)) != notFound) {
-        if (startPos != endPos)
-            result.append(substring(startPos, endPos - startPos));
-        startPos = endPos + 1;
-    }
-    if (startPos != length())
-        result.append(substring(startPos));
-    return result;
-}
-
 StringView::GraphemeClusters::Iterator::Iterator(const StringView& stringView, unsigned index)
     : m_impl(std::make_unique<Impl>(stringView, stringView.isNull() ? std::nullopt : std::optional<NonSharedCharacterBreakIterator>(NonSharedCharacterBreakIterator(stringView)), index))
 {
index 2cc25cd..ef209f9 100644 (file)
@@ -1,5 +1,5 @@
 /*
- * Copyright (C) 2014-2016 Apple Inc. All rights reserved.
+ * Copyright (C) 2014-2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
@@ -117,7 +117,9 @@ public:
     StringView substring(unsigned start, unsigned length = std::numeric_limits<unsigned>::max()) const;
     StringView left(unsigned len) const { return substring(0, len); }
     StringView right(unsigned len) const { return substring(length() - len, len); }
-    WTF_EXPORT_STRING_API Vector<StringView> split(UChar);
+
+    class SplitResult;
+    SplitResult split(UChar) const;
 
     size_t find(UChar, unsigned start = 0) const;
     size_t find(CharacterMatchFunction, unsigned start = 0) const;
@@ -613,6 +615,19 @@ inline bool equalIgnoringASCIICase(StringView a, const char* b)
     return equalIgnoringASCIICaseCommon(a, b);
 }
 
+class StringView::SplitResult {
+public:
+    explicit SplitResult(StringView, UChar separator);
+
+    class Iterator;
+    Iterator begin() const;
+    Iterator end() const;
+
+private:
+    StringView m_string;
+    UChar m_separator;
+};
+
 class StringView::GraphemeClusters {
 public:
     explicit GraphemeClusters(const StringView&);
@@ -649,6 +664,29 @@ private:
     StringView m_stringView;
 };
 
+class StringView::SplitResult::Iterator {
+public:
+    StringView operator*() const;
+
+    WTF_EXPORT_PRIVATE Iterator& operator++();
+
+    bool operator==(const Iterator&) const;
+    bool operator!=(const Iterator&) const;
+
+private:
+    enum PositionTag { AtEnd };
+    Iterator(const SplitResult&);
+    Iterator(const SplitResult&, PositionTag);
+
+    WTF_EXPORT_PRIVATE void findNextSubstring();
+
+    friend SplitResult;
+
+    const SplitResult& m_result;
+    unsigned m_position { 0 };
+    unsigned m_length;
+};
+
 class StringView::GraphemeClusters::Iterator {
 public:
     WTF_EXPORT_PRIVATE Iterator() = delete;
@@ -839,6 +877,56 @@ inline auto StringView::CodeUnits::end() const -> Iterator
     return Iterator(m_stringView, m_stringView.length());
 }
 
+inline auto StringView::split(UChar separator) const -> SplitResult
+{
+    return SplitResult { *this, separator };
+}
+
+inline StringView::SplitResult::SplitResult(StringView stringView, UChar separator)
+    : m_string { stringView }
+    , m_separator { separator }
+{
+}
+
+inline auto StringView::SplitResult::begin() const -> Iterator
+{
+    return Iterator { *this };
+}
+
+inline auto StringView::SplitResult::end() const -> Iterator
+{
+    return Iterator { *this, Iterator::AtEnd };
+}
+
+inline StringView::SplitResult::Iterator::Iterator(const SplitResult& result)
+    : m_result { result }
+{
+    findNextSubstring();
+}
+
+inline StringView::SplitResult::Iterator::Iterator(const SplitResult& result, PositionTag)
+    : m_result { result }
+    , m_position { result.m_string.length() }
+{
+}
+
+inline StringView StringView::SplitResult::Iterator::operator*() const
+{
+    ASSERT(m_position < m_result.m_string.length());
+    return m_result.m_string.substring(m_position, m_length);
+}
+
+inline bool StringView::SplitResult::Iterator::operator==(const Iterator& other) const
+{
+    ASSERT(&m_result == &other.m_result);
+    return m_position == other.m_position;
+}
+
+inline bool StringView::SplitResult::Iterator::operator!=(const Iterator& other) const
+{
+    return !(*this == other);
+}
+
 template<unsigned length> inline bool equalLettersIgnoringASCIICase(StringView string, const char (&lowercaseLetters)[length])
 {
     return equalLettersIgnoringASCIICaseCommon(string, lowercaseLetters);
index 94df461..3a9a180 100644 (file)
@@ -1,3 +1,14 @@
+2017-01-24  Daniel Bates  <dabates@apple.com>
+
+        StringView.split() should use an iterator design pattern instead of allocating a Vector
+        https://bugs.webkit.org/show_bug.cgi?id=163225
+
+        Reviewed by Darin Adler.
+
+        Update code to use the new iterator-style StringView.split().
+
+        * platform/URLParser.cpp:
+
 2017-01-24  Joseph Pecoraro  <pecoraro@apple.com>
 
         Remove always true openGLMultisamplingEnabled setting
index 7a5aea9..f6a9aa2 100644 (file)
@@ -2721,10 +2721,8 @@ std::optional<String> URLParser::formURLDecode(StringView input)
 
 auto URLParser::parseURLEncodedForm(StringView input) -> URLEncodedForm
 {
-    Vector<StringView> sequences = input.split('&');
-
     URLEncodedForm output;
-    for (auto& bytes : sequences) {
+    for (StringView bytes : input.split('&')) {
         auto valueStart = bytes.find('=');
         if (valueStart == notFound) {
             if (auto name = formURLDecode(bytes))
index 36520dc..d46a5ed 100644 (file)
@@ -1,3 +1,23 @@
+2017-01-24  Daniel Bates  <dabates@apple.com>
+
+        StringView.split() should use an iterator design pattern instead of allocating a Vector
+        https://bugs.webkit.org/show_bug.cgi?id=163225
+
+        Reviewed by Darin Adler.
+
+        Add unit tests for StringView.split().
+
+        * TestWebKitAPI/Tests/WTF/StringView.cpp:
+        (TestWebKitAPI::stringViewFromLiteral): Moved to the top of the file so that it can be
+        used in the StringView.split() unit tests.
+        (TestWebKitAPI::stringViewFromUTF8): Ditto.
+        (TestWebKitAPI::vectorFromSplitResult): Convenience function to convert a StringView::SplitResult
+        object to a Vector of String objects.
+        (TestWebKitAPI::TEST): Added the following tests:
+            - WTF.StringViewSplitEmptyAndNullStrings
+            - WTF.StringViewSplitBasic
+            - WTF.StringViewSplitWithConsecutiveSeparators
+
 2017-01-23  Anders Carlsson  <andersca@apple.com>
 
         The Score Esports crashes on launch
index 34503f4..9359283 100644 (file)
 
 namespace TestWebKitAPI {
 
+StringView stringViewFromLiteral(const char* characters)
+{
+    return StringView(reinterpret_cast<const LChar*>(characters), strlen(characters));
+}
+
+StringView stringViewFromUTF8(String &ref, const char* characters)
+{
+    ref = String::fromUTF8(characters);
+    return ref;
+}
+
 TEST(WTF, StringViewEmptyVsNull)
 {
     StringView nullView;
@@ -214,6 +225,79 @@ TEST(WTF, StringViewIterators)
         StringView(b.characters16() + 3, 3)}));
 }
 
+static Vector<String> vectorFromSplitResult(const StringView::SplitResult& substrings)
+{
+    Vector<String> result;
+    for (StringView substring : substrings)
+        result.append(substring.toString());
+    return result;
+}
+
+TEST(WTF, StringViewSplitEmptyAndNullStrings)
+{
+    StringView a = emptyString();
+    auto splitResult = a.split('b');
+    EXPECT_TRUE(splitResult.begin() == splitResult.end());
+
+    a = { String { } };
+    splitResult = a.split('b');
+    EXPECT_TRUE(splitResult.begin() == splitResult.end());
+
+    a = { };
+    splitResult = a.split('b');
+    EXPECT_TRUE(splitResult.begin() == splitResult.end());
+}
+
+TEST(WTF, StringViewSplitBasic)
+{
+    String referenceHolder;
+    StringView a = stringViewFromUTF8(referenceHolder, "This is a sentence.");
+
+    // Simple
+    Vector<String> actual = vectorFromSplitResult(a.split('T'));
+    Vector<String> expected({ "his is a sentence." });
+    ASSERT_EQ(expected.size(), actual.size());
+    for (size_t i = 0; i < actual.size(); ++i)
+        EXPECT_STREQ(expected[i].utf8().data(), actual[i].utf8().data()) << "Vectors differ at index " << i;
+
+    actual = vectorFromSplitResult(a.split('.'));
+    expected = { "This is a sentence" };
+    ASSERT_EQ(expected.size(), actual.size());
+    for (size_t i = 0; i < actual.size(); ++i)
+        EXPECT_STREQ(expected[i].utf8().data(), actual[i].utf8().data()) << "Vectors differ at index " << i;
+
+    actual = vectorFromSplitResult(a.split('a'));
+    expected = { "This is ", " sentence." };
+    ASSERT_EQ(expected.size(), actual.size());
+    for (size_t i = 0; i < actual.size(); ++i)
+        EXPECT_STREQ(expected[i].utf8().data(), actual[i].utf8().data()) << "Vectors differ at index " << i;
+
+    actual = vectorFromSplitResult(a.split(' '));
+    expected = { "This", "is", "a", "sentence." };
+    ASSERT_EQ(expected.size(), actual.size());
+    for (size_t i = 0; i < actual.size(); ++i)
+        EXPECT_STREQ(expected[i].utf8().data(), actual[i].utf8().data()) << "Vectors differ at index " << i;
+
+    // Non-existent separator
+    actual = vectorFromSplitResult(a.split('z'));
+    expected = { "This is a sentence." };
+    ASSERT_EQ(expected.size(), actual.size());
+    for (size_t i = 0; i < actual.size(); ++i)
+        EXPECT_STREQ(expected[i].utf8().data(), actual[i].utf8().data()) << "Vectors differ at index " << i;
+}
+
+TEST(WTF, StringViewSplitWithConsecutiveSeparators)
+{
+    String referenceHolder;
+    StringView a = stringViewFromUTF8(referenceHolder, "This     is  a       sentence.");
+
+    Vector<String> actual = vectorFromSplitResult(a.split(' '));
+    Vector<String> expected({ "This", "is", "a", "sentence." });
+    ASSERT_EQ(expected.size(), actual.size());
+    for (size_t i = 0; i < actual.size(); ++i)
+        EXPECT_STREQ(expected[i].utf8().data(), actual[i].utf8().data()) << "Vectors differ at index " << i;
+}
+
 TEST(WTF, StringViewEqualIgnoringASCIICaseBasic)
 {
     RefPtr<StringImpl> a = StringImpl::createFromLiteral("aBcDeFG");
@@ -304,17 +388,6 @@ TEST(WTF, StringViewEqualIgnoringASCIICaseWithLatin1Characters)
     ASSERT_FALSE(equalIgnoringASCIICase(stringViewD, e));
 }
 
-StringView stringViewFromLiteral(const char* characters)
-{
-    return StringView(reinterpret_cast<const LChar*>(characters), strlen(characters));
-}
-
-StringView stringViewFromUTF8(String &ref, const char* characters)
-{
-    ref = String::fromUTF8(characters);
-    return ref;
-}
-
 TEST(WTF, StringViewFindIgnoringASCIICaseBasic)
 {
     String referenceAHolder;