1 files changed, 231 insertions, 0 deletions
diff --git a/library/cpp/actors/util/rope_ut.cpp b/library/cpp/actors/util/rope_ut.cpp
new file mode 100644
index 0000000000..cabeed9230
--- /dev/null
+++ b/library/cpp/actors/util/rope_ut.cpp
@@ -0,0 +1,231 @@
+#include "rope.h"
+#include <library/cpp/testing/unittest/registar.h>
+#include <util/random/random.h>
+
+class TRopeStringBackend : public IRopeChunkBackend {
+    TString Buffer;
+
+public:
+    TRopeStringBackend(TString buffer)
+        : Buffer(std::move(buffer))
+    {}
+
+    TData GetData() const override {
+        return {Buffer.data(), Buffer.size()};
+    }
+
+    size_t GetCapacity() const override {
+        return Buffer.capacity();
+    }
+};
+
+TRope CreateRope(TString s, size_t sliceSize) {
+    TRope res;
+    for (size_t i = 0; i < s.size(); ) {
+        size_t len = std::min(sliceSize, s.size() - i);
+        if (i % 2) {
+            res.Insert(res.End(), TRope(MakeIntrusive<TRopeStringBackend>(s.substr(i, len))));
+        } else {
+            res.Insert(res.End(), TRope(s.substr(i, len)));
+        }
+        i += len;
+    }
+    return res;
+}
+
+TString RopeToString(const TRope& rope) {
+    TString res;
+    auto iter = rope.Begin();
+    while (iter != rope.End()) {
+        res.append(iter.ContiguousData(), iter.ContiguousSize());
+        iter.AdvanceToNextContiguousBlock();
+    }
+
+    UNIT_ASSERT_VALUES_EQUAL(rope.GetSize(), res.size());
+
+    TString temp = TString::Uninitialized(rope.GetSize());
+    rope.Begin().ExtractPlainDataAndAdvance(temp.Detach(), temp.size());
+    UNIT_ASSERT_VALUES_EQUAL(temp, res);
+
+    return res;
+}
+
+TString Text = "No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.";
+
+Y_UNIT_TEST_SUITE(TRope) {
+
+    Y_UNIT_TEST(Leak) {
+        const size_t begin = 10, end = 20;
+        TRope rope = CreateRope(Text, 10);
+        rope.Erase(rope.Begin() + begin, rope.Begin() + end);
+    }
+
+    Y_UNIT_TEST(BasicRange) {
+        TRope rope = CreateRope(Text, 10);
+        for (size_t begin = 0; begin < Text.size(); ++begin) {
+            for (size_t end = begin; end <= Text.size(); ++end) {
+                TRope::TIterator rBegin = rope.Begin() + begin;
+                TRope::TIterator rEnd = rope.Begin() + end;
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(rBegin, rEnd)), Text.substr(begin, end - begin));
+            }
+        }
+    }
+
+    Y_UNIT_TEST(Erase) {
+        for (size_t begin = 0; begin < Text.size(); ++begin) {
+            for (size_t end = begin; end <= Text.size(); ++end) {
+                TRope rope = CreateRope(Text, 10);
+                rope.Erase(rope.Begin() + begin, rope.Begin() + end);
+                TString text = Text;
+                text.erase(text.begin() + begin, text.begin() + end);
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
+            }
+        }
+    }
+
+    Y_UNIT_TEST(Insert) {
+        TRope rope = CreateRope(Text, 10);
+        for (size_t begin = 0; begin < Text.size(); ++begin) {
+            for (size_t end = begin; end <= Text.size(); ++end) {
+                TRope part = TRope(rope.Begin() + begin, rope.Begin() + end);
+                for (size_t where = 0; where <= Text.size(); ++where) {
+                    TRope x(rope);
+                    x.Insert(x.Begin() + where, TRope(part));
+                    UNIT_ASSERT_VALUES_EQUAL(x.GetSize(), rope.GetSize() + part.GetSize());
+                    TString text = Text;
+                    text.insert(text.begin() + where, Text.begin() + begin, Text.begin() + end);
+                    UNIT_ASSERT_VALUES_EQUAL(RopeToString(x), text);
+                }
+            }
+        }
+    }
+
+    Y_UNIT_TEST(Extract) {
+        for (size_t begin = 0; begin < Text.size(); ++begin) {
+            for (size_t end = begin; end <= Text.size(); ++end) {
+                TRope rope = CreateRope(Text, 10);
+                TRope part = rope.Extract(rope.Begin() + begin, rope.Begin() + end);
+                TString text = Text;
+                text.erase(text.begin() + begin, text.begin() + end);
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), text);
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(part), Text.substr(begin, end - begin));
+            }
+        }
+    }
+
+    Y_UNIT_TEST(EraseFront) {
+        for (size_t pos = 0; pos <= Text.size(); ++pos) {
+            TRope rope = CreateRope(Text, 10);
+            rope.EraseFront(pos);
+            UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(pos));
+        }
+    }
+
+    Y_UNIT_TEST(EraseBack) {
+        for (size_t pos = 0; pos <= Text.size(); ++pos) {
+            TRope rope = CreateRope(Text, 10);
+            rope.EraseBack(pos);
+            UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text.substr(0, Text.size() - pos));
+        }
+    }
+
+    Y_UNIT_TEST(ExtractFront) {
+        for (size_t step = 1; step <= Text.size(); ++step) {
+            TRope rope = CreateRope(Text, 10);
+            TRope out;
+            while (const size_t len = Min(step, rope.GetSize())) {
+                rope.ExtractFront(len, &out);
+                UNIT_ASSERT(rope.GetSize() + out.GetSize() == Text.size());
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(out), Text.substr(0, out.GetSize()));
+            }
+        }
+    }
+
+    Y_UNIT_TEST(ExtractFrontPlain) {
+        for (size_t step = 1; step <= Text.size(); ++step) {
+            TRope rope = CreateRope(Text, 10);
+            TString buffer = Text;
+            auto it = rope.Begin();
+            size_t remain = rope.GetSize();
+            while (const size_t len = Min(step, remain)) {
+                TString data = TString::Uninitialized(len);
+                it.ExtractPlainDataAndAdvance(data.Detach(), data.size());
+                UNIT_ASSERT_VALUES_EQUAL(data, buffer.substr(0, len));
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(TRope(it, rope.End())), buffer.substr(len));
+                buffer = buffer.substr(len);
+                remain -= len;
+            }
+        }
+    }
+
+    Y_UNIT_TEST(FetchFrontPlain) {
+        char s[10];
+        char *data = s;
+        size_t remain = sizeof(s);
+        TRope rope = TRope(TString("HELLO"));
+        UNIT_ASSERT(!rope.FetchFrontPlain(&data, &remain));
+        UNIT_ASSERT(!rope);
+        rope.Insert(rope.End(), TRope(TString("WORLD!!!")));
+        UNIT_ASSERT(rope.FetchFrontPlain(&data, &remain));
+        UNIT_ASSERT(!remain);
+        UNIT_ASSERT(rope.GetSize() == 3);
+        UNIT_ASSERT_VALUES_EQUAL(rope.ConvertToString(), "!!!");
+        UNIT_ASSERT(!strncmp(s, "HELLOWORLD", 10));
+    }
+
+    Y_UNIT_TEST(Glueing) {
+        TRope rope = CreateRope(Text, 10);
+        for (size_t begin = 0; begin <= Text.size(); ++begin) {
+            for (size_t end = begin; end <= Text.size(); ++end) {
+                TString repr = rope.DebugString();
+                TRope temp = rope.Extract(rope.Position(begin), rope.Position(end));
+                rope.Insert(rope.Position(begin), std::move(temp));
+                UNIT_ASSERT_VALUES_EQUAL(repr, rope.DebugString());
+                UNIT_ASSERT_VALUES_EQUAL(RopeToString(rope), Text);
+            }
+        }
+    }
+
+    Y_UNIT_TEST(IterWalk) {
+        TRope rope = CreateRope(Text, 10);
+        for (size_t step1 = 0; step1 <= rope.GetSize(); ++step1) {
+            for (size_t step2 = 0; step2 <= step1; ++step2) {
+                TRope::TConstIterator iter = rope.Begin();
+                iter += step1;
+                iter -= step2;
+                UNIT_ASSERT(iter == rope.Position(step1 - step2));
+            }
+        }
+    }
+
+    Y_UNIT_TEST(Compare) {
+        auto check = [](const TString& x, const TString& y) {
+            const TRope xRope = CreateRope(x, 7);
+            const TRope yRope = CreateRope(y, 11);
+            UNIT_ASSERT_VALUES_EQUAL(xRope == yRope, x == y);
+            UNIT_ASSERT_VALUES_EQUAL(xRope != yRope, x != y);
+            UNIT_ASSERT_VALUES_EQUAL(xRope <  yRope, x <  y);
+            UNIT_ASSERT_VALUES_EQUAL(xRope <= yRope, x <= y);
+            UNIT_ASSERT_VALUES_EQUAL(xRope >  yRope, x >  y);
+            UNIT_ASSERT_VALUES_EQUAL(xRope >= yRope, x >= y);
+        };
+
+        TVector<TString> pool;
+        for (size_t k = 0; k < 10; ++k) {
+            size_t len = RandomNumber<size_t>(100) + 100;
+            TString s = TString::Uninitialized(len);
+            char *p = s.Detach();
+            for (size_t j = 0; j < len; ++j) {
+                *p++ = RandomNumber<unsigned char>();
+            }
+            pool.push_back(std::move(s));
+        }
+
+        for (const TString& x : pool) {
+            for (const TString& y : pool) {
+                check(x, y);
+            }
+        }
+    }
+
+}