Merge WebKit at r67178 : Initial merge by git.

Change-Id: I57e01163b6866cb029cdadf405a0394a3918bc18

1 files changed, 323 insertions, 0 deletions

diff --git a/WebKit/chromium/tests/PODIntervalTreeTest.cpp b/WebKit/chromium/tests/PODIntervalTreeTest.cpp
new file mode 100644
index 0000000..3a8a245
--- /dev/null
+++ b/WebKit/chromium/tests/PODIntervalTreeTest.cpp
@@ -0,0 +1,323 @@
+/*
+ * Copyright (C) 2010 Google Inc. All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1.  Redistributions of source code must retain the above copyright
+ *     notice, this list of conditions and the following disclaimer.
+ * 2.  Redistributions in binary form must reproduce the above copyright
+ *     notice, this list of conditions and the following disclaimer in the
+ *     documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
+ * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+ * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
+ * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+ * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
+ * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+// Tests for the interval tree class.
+
+#include "config.h"
+
+#include "PODIntervalTree.h"
+
+#include "Logging.h"
+#include "TreeTestHelpers.h"
+#include <gtest/gtest.h>
+#include <wtf/Vector.h>
+#include <wtf/text/WTFString.h>
+
+namespace WebCore {
+
+using TreeTestHelpers::generateSeed;
+using TreeTestHelpers::initRandom;
+using TreeTestHelpers::nextRandom;
+
+inline String valueToString(const float& value)
+{
+    return String::number(value);
+}
+
+inline String valueToString(void* const& value)
+{
+    return String::format("0x%p", value);
+}
+
+TEST(PODIntervalTreeTest, TestInsertion)
+{
+    PODIntervalTree<float> tree;
+    tree.add(PODInterval<float>(2, 4));
+    ASSERT_TRUE(tree.checkInvariants());
+}
+
+TEST(PODIntervalTreeTest, TestInsertionAndQuery)
+{
+    PODIntervalTree<float> tree;
+    tree.add(PODInterval<float>(2, 4));
+    ASSERT_TRUE(tree.checkInvariants());
+    Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(1, 3));
+    EXPECT_EQ(1U, result.size());
+    EXPECT_EQ(2, result[0].low());
+    EXPECT_EQ(4, result[0].high());
+}
+
+TEST(PODIntervalTreeTest, TestQueryAgainstZeroSizeInterval)
+{
+    PODIntervalTree<float> tree;
+    tree.add(PODInterval<float>(1, 2.5));
+    tree.add(PODInterval<float>(3.5, 5));
+    tree.add(PODInterval<float>(2, 4));
+    ASSERT_TRUE(tree.checkInvariants());
+    Vector<PODInterval<float> > result = tree.allOverlaps(PODInterval<float>(3, 3));
+    EXPECT_EQ(1U, result.size());
+    EXPECT_EQ(2, result[0].low());
+    EXPECT_EQ(4, result[0].high());
+}
+
+TEST(PODIntervalTreeTest, TestDuplicateElementInsertion)
+{
+    PODIntervalTree<float, int*> tree;
+    int tmp1 = 1;
+    int tmp2 = 2;
+    typedef PODIntervalTree<float, int*>::IntervalType IntervalType;
+    IntervalType interval1(1, 3, &tmp1);
+    IntervalType interval2(1, 3, &tmp2);
+    tree.add(interval1);
+    tree.add(interval2);
+    ASSERT_TRUE(tree.checkInvariants());
+    EXPECT_TRUE(tree.contains(interval1));
+    EXPECT_TRUE(tree.contains(interval2));
+    EXPECT_TRUE(tree.remove(interval1));
+    EXPECT_TRUE(tree.contains(interval2));
+    EXPECT_FALSE(tree.contains(interval1));
+    EXPECT_TRUE(tree.remove(interval2));
+    EXPECT_EQ(0, tree.size());
+}
+
+namespace {
+
+struct UserData1 {
+public:
+    UserData1()
+        : a(0), b(1) { }
+
+    float a;
+    int b;
+};
+
+inline String valueToString(const UserData1& value)
+{
+    return String("[UserData1 a=") + String::number(value.a) + " b=" + String::number(value.b) + "]";
+}
+
+} // anonymous namespace
+
+TEST(PODIntervalTreeTest, TestInsertionOfComplexUserData)
+{
+    PODIntervalTree<float, UserData1> tree;
+    UserData1 data1;
+    data1.a = 5;
+    data1.b = 6;
+    tree.add(tree.createInterval(2, 4, data1));
+    ASSERT_TRUE(tree.checkInvariants());
+}
+
+TEST(PODIntervalTreeTest, TestQueryingOfComplexUserData)
+{
+    PODIntervalTree<float, UserData1> tree;
+    UserData1 data1;
+    data1.a = 5;
+    data1.b = 6;
+    tree.add(tree.createInterval(2, 4, data1));
+    ASSERT_TRUE(tree.checkInvariants());
+    Vector<PODInterval<float, UserData1> > overlaps = tree.allOverlaps(tree.createInterval(3, 5, data1));
+    EXPECT_EQ(1U, overlaps.size());
+    EXPECT_EQ(5, overlaps[0].data().a);
+    EXPECT_EQ(6, overlaps[0].data().b);
+}
+
+namespace {
+
+class EndpointType1 {
+public:
+    explicit EndpointType1(int value)
+        : m_value(value) { }
+
+    int value() const { return m_value; }
+
+    bool operator<(const EndpointType1& other) const { return m_value < other.m_value; }
+    bool operator==(const EndpointType1& other) const { return m_value == other.m_value; }
+
+private:
+    int m_value;
+    // These operators should not be called by the interval tree.
+    bool operator>(const EndpointType1& other);
+    bool operator<=(const EndpointType1& other);
+    bool operator>=(const EndpointType1& other);
+    bool operator!=(const EndpointType1& other);
+};
+
+inline String valueToString(const EndpointType1& value)
+{
+    return String("[EndpointType1 value=") + String::number(value.value()) + "]";
+}
+
+} // anonymous namespace
+
+TEST(PODIntervalTreeTest, TestTreeDoesNotRequireMostOperators)
+{
+    PODIntervalTree<EndpointType1> tree;
+    tree.add(tree.createInterval(EndpointType1(1), EndpointType1(2)));
+    ASSERT_TRUE(tree.checkInvariants());
+}
+
+// Uncomment to debug a failure of the insertion and deletion test.
+// #define DEBUG_INSERTION_AND_DELETION_TEST
+
+namespace {
+
+void InsertionAndDeletionTest(int32_t seed, int treeSize)
+{
+    initRandom(seed);
+    int maximumValue = treeSize;
+    // Build the tree
+    PODIntervalTree<int> tree;
+    Vector<PODInterval<int> > addedElements;
+    Vector<PODInterval<int> > removedElements;
+    for (int i = 0; i < treeSize; i++) {
+        int left = nextRandom(maximumValue);
+        int length = nextRandom(maximumValue);
+        PODInterval<int> interval(left, left + length);
+        tree.add(interval);
+#ifdef DEBUG_INSERTION_AND_DELETION_TEST
+        LOG_ERROR("*** Adding element %s", valueToString(interval).ascii().data());
+#endif
+        addedElements.append(interval);
+    }
+    // Churn the tree's contents.
+    // First remove half of the elements in random order.
+    for (int i = 0; i < treeSize / 2; i++) {
+        int index = nextRandom(addedElements.size());
+#ifdef DEBUG_INSERTION_AND_DELETION_TEST
+        LOG_ERROR("*** Removing element %s", valueToString(addedElements[index]).ascii().data());
+#endif
+        ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
+        tree.remove(addedElements[index]);
+        removedElements.append(addedElements[index]);
+        addedElements.remove(index);
+        ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
+    }
+    // Now randomly add or remove elements.
+    for (int i = 0; i < 2 * treeSize; i++) {
+        bool add = false;
+        if (!addedElements.size())
+            add = true;
+        else if (!removedElements.size())
+            add = false;
+        else
+            add = (nextRandom(2) == 1);
+        if (add) {
+            int index = nextRandom(removedElements.size());
+#ifdef DEBUG_INSERTION_AND_DELETION_TEST
+            LOG_ERROR("*** Adding element %s", valueToString(removedElements[index]).ascii().data());
+#endif
+            tree.add(removedElements[index]);
+            addedElements.append(removedElements[index]);
+            removedElements.remove(index);
+        } else {
+            int index = nextRandom(addedElements.size());
+#ifdef DEBUG_INSERTION_AND_DELETION_TEST
+            LOG_ERROR("*** Removing element %s", valueToString(addedElements[index]).ascii().data());
+#endif
+            ASSERT_TRUE(tree.contains(addedElements[index])) << "Test failed for seed " << seed;
+            ASSERT_TRUE(tree.remove(addedElements[index])) << "Test failed for seed " << seed;
+            removedElements.append(addedElements[index]);
+            addedElements.remove(index);
+        }
+        ASSERT_TRUE(tree.checkInvariants()) << "Test failed for seed " << seed;
+    }
+}
+
+} // anonymous namespace
+
+TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest1)
+{
+    InsertionAndDeletionTest(13972, 100);
+}
+
+TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest2)
+{
+    InsertionAndDeletionTest(1283382113, 10);
+}
+
+TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest3)
+{
+    // This is the sequence of insertions and deletions that triggered
+    // the failure in RandomDeletionAndInsertionRegressionTest2.
+    PODIntervalTree<int> tree;
+    tree.add(tree.createInterval(0, 5));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(4, 5));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(8, 9));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(1, 4));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(3, 5));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(4, 12));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(0, 2));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(0, 2));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(9, 13));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(0, 1));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.remove(tree.createInterval(0, 2));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.remove(tree.createInterval(9, 13));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.remove(tree.createInterval(0, 2));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.remove(tree.createInterval(0, 1));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.remove(tree.createInterval(4, 5));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.remove(tree.createInterval(4, 12));
+    ASSERT_TRUE(tree.checkInvariants());
+}
+
+TEST(PODIntervalTreeTest, RandomDeletionAndInsertionRegressionTest4)
+{
+    // Even further reduced test case for RandomDeletionAndInsertionRegressionTest3.
+    PODIntervalTree<int> tree;
+    tree.add(tree.createInterval(0, 5));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(8, 9));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(1, 4));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(3, 5));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.add(tree.createInterval(4, 12));
+    ASSERT_TRUE(tree.checkInvariants());
+    tree.remove(tree.createInterval(4, 12));
+    ASSERT_TRUE(tree.checkInvariants());
+}
+
+TEST(PODIntervalTreeTest, TestRandomDeletionAndInsertion)
+{
+    InsertionAndDeletionTest(generateSeed(), 1000);
+}
+
+} // namespace WebCore