/** Reference Counted Array.
    See_Also: http://dpaste.dzfl.pl/817283c163f5
 */
module nxt.rcstring;

import core.memory : GC;
// import core.stdc.stdlib;
// import core.stdc.string;
// import std.algorithm;

/** Reference Counted (RC) version of string.
 */
alias RCString = RCXString!(immutable char);

/** Reference Counted Array.
    Configured with character type `E`, maximum length for the small string optimization,
    and the allocation function, which must have the same semantics as `realloc`.

    See_Also: https://github.com/burner/std.rcstring
*/
struct RCXString(E = immutable char, size_t maxSmallSize = 23, alias realloc = GC.realloc)
{
    pure nothrow:

    // Preconditions
    static assert(is(E == immutable), "Only immutable characters supported for now.");
    static assert(E.alignof <= 4, "Character type must be 32-bit aligned at most.");
    static assert(E.min == 0, "Character type must be unsigned.");
    static assert((maxSmallSize + 1) * E.sizeof % size_t.sizeof == 0,
                  "maxSmallSize + 1 must be a multiple of size_t.sizeof.");
    static assert((maxSmallSize + 1) * E.sizeof >= 3 * size_t.sizeof,
                  "maxSmallSize + 1 must be >= size_t.sizeof * 3.");
    static assert(maxSmallSize < E.max, "maxSmallSize must be less than E.max");

    enum maxSmallLength = maxSmallSize;

private:
    // import std.utf;
    import core.lifetime : emplace;
    import std.traits: isSomeChar, Unqual;

    version(unittest) import std.stdio;

    alias ME = Unqual!E; // mutable E

    enum isString = isSomeChar!E;

    // Simple reference-counted buffer. The reference count itself is a E. Layout is a size_t (the capacity)
    // followed by the reference count followed by the payload.
    struct RCBuffer
    {
        size_t capacity;
        uint refCount;

        // Data starts right after the refcount, no padding because of the static assert above
        ME* mptr() @nogc { return cast(ME*) (&refCount + 1); }
        E* ptr() @nogc { return cast(E*) mptr; }

        // Create a new buffer given capacity and initializes payload. Capacity must be large enough.
        static RCBuffer* make(size_t capacity, const(ME)[] content)
        {
            assert(capacity >= content.length);
            auto result = cast(RCBuffer*) realloc(null, size_t.sizeof + uint.sizeof + capacity * E.sizeof);
            result || assert(0);
            result.capacity = capacity;
            result.refCount = 1;
            result.mptr[0 .. content.length] = content;
            return result;
        }

        // Resize the buffer. It is assumed the reference count is 1.
        static void resize(ref RCBuffer* p, size_t capacity)
        {
            assert(p.refCount == 1);
            p = cast(RCBuffer*) realloc(p, size_t.sizeof + uint.sizeof + capacity * E.sizeof);
            p || assert(0);
            p.capacity = capacity;
        }

        unittest
        {
            auto p = make(101, null);
            assert(p.refCount == 1);
            assert(p.capacity == 101);
            resize(p, 203);
            assert(p.refCount == 1);
            assert(p.capacity == 203);
            realloc(p, 0);
        }
    }

    // Hosts a large string
    struct Large
    {
        // <layout>
        union
        {
            immutable RCBuffer* buf;
            RCBuffer* mbuf;
        }
        union
        {
            E* ptr;
            ME* mptr;
        }
        static if ((maxSmallSize + 1) * E.sizeof == 3 * size_t.sizeof)
        {
            /* The small buffer and the large buffer overlap. This means the large buffer must give up its last byte
             * as a discriminator.
             */
            size_t _length;
            enum maxLarge = size_t.max >> (8 * E.sizeof);
            version(BigEndian)
            {
                // Use the LSB to store the marker
                size_t length() const @safe @nogc { return _length >> 8 * E.sizeof; }
                void length(size_t s) @safe @nogc { _length = Marker.isRefCounted | (s << (8 * E.sizeof)); }
            }
            else version(LittleEndian)
            {
                // Use the MSB to store the marker
                private enum size_t mask = size_t(E.max) << (8 * (size_t.sizeof - E.sizeof));
                size_t length() const @safe @nogc { return _length & ~mask; }
                void length(size_t s) @safe @nogc { assert(s <= maxLarge); _length = s | mask; }
            }
            else
            {
                static assert(0, "Unspecified endianness.");
            }
        }
        else
        {
            // No tricks needed, store the size plainly
            size_t _length;
            size_t length() const @safe @nogc
            {
                return _length;
            }
            void length(size_t s) @safe @nogc
            {
                _length = s;
            }
        }
        // </layout>

        // Get length
        alias opDollar = length;

        // Initializes a Large given capacity and content. Capacity must be at least as large as content's size.
        this(size_t capacity, const(ME)[] content)
        {
            assert(capacity >= content.length);
            mbuf = RCBuffer.make(capacity, content);
            mptr = mbuf.mptr;
            length = content.length;
        }

        // Initializes a Large from a string by copying it.
        this(const(ME)[] s)
        {
            this(s.length, s);
        }

        static if (isString) unittest
        {
            const(ME)[] s1 = "hello, world";
            auto lrg1 = Large(s1);
            assert(lrg1.length == 12);
            immutable lrg2 = immutable Large(s1);
            assert(lrg2.length == 12);
            const lrg3 = const Large(s1);
            assert(lrg3.length == 12);
        }

        // Initializes a Large from a static string by referring to it.
        this(immutable(ME)[] s)
        {
            assert(buf is null);
            ptr = s.ptr;
            length = s.length;
        }

        static if (isString) unittest
        {
            immutable ME[] s = "abcdef";
            auto lrg1 = Large(s);
            assert(lrg1.length == 6);
            assert(lrg1.buf is null);
        }

        // Decrements the reference count and frees buf if it goes down to zero.
        void decRef() nothrow
        {
            if (!mbuf) return;
            if (mbuf.refCount == 1) realloc(mbuf, 0);
            else --mbuf.refCount;
        }

        auto opSlice() inout return
        {
            assert(ptr);
            return ptr[0 .. length];
        }

        // Makes sure there's room for at least newCap Chars.
        void reserve(size_t newCap)
        {
            if (mbuf && mbuf.refCount == 1 && mbuf.capacity >= newCap) return;
            immutable size = this.length;
            version(assert) scope(exit) assert(size == this.length);
            if (!mbuf)
            {
                // Migrate from static string to allocated string
                mbuf = RCBuffer.make(newCap, ptr[0 .. size]);
                ptr = mbuf.ptr;
                return;
            }
            if (mbuf.refCount > 1)
            {
                // Split this guy making its buffer unique
                --mbuf.refCount;
                mbuf = RCBuffer.make(newCap, ptr[0 .. size]);
                ptr = mbuf.ptr;
                // size stays untouched
            }
            else
            {
                immutable offset = ptr - mbuf.ptr;
                // If offset is too large, it's worth decRef()ing and then allocating a new buffer
                if (offset * 2 >= newCap)
                {
                    auto newBuf = RCBuffer.make(newCap, ptr[0 .. size]);
                    decRef;
                    mbuf = newBuf;
                    ptr = mbuf.ptr;
                }
                else
                {
                    RCBuffer.resize(mbuf, newCap);
                    ptr = mbuf.ptr + offset;
                }
            }
        }

        unittest
        {
            Large obj;
            obj.reserve(1);
            assert(obj.mbuf !is null);
            assert(obj.mbuf.capacity >= 1);
            obj.reserve(1000);
            assert(obj.mbuf.capacity >= 1000);
            obj.reserve(10000);
            assert(obj.mbuf.capacity >= 10000);
        }
    }

    // <layout>
    union
    {
        Large large;
        struct
        {
            union
            {
                E[maxSmallSize] small;
                ME[maxSmallSize] msmall;
            }
            ME smallLength;
        }
        size_t[(maxSmallSize + 1) / size_t.sizeof] ancillary; // used internally
    }
    // </layout>

    hash_t toHash() const @trusted
    {
        import core.internal.hash : hashOf;
        return this.asSlice.hashOf;
    }

    static if (isString) unittest
    {
        assert(RCXString("a").toHash ==
               RCXString("a").toHash);
        assert(RCXString("a").toHash !=
               RCXString("b").toHash);
        assert(RCXString("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa").toHash ==
               RCXString("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa").toHash);
        assert(RCXString("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa").toHash !=
               RCXString("bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb").toHash);
    }

    static if (isString) unittest
    {
        RCXString x;
        assert(x.smallLength == 0);
        assert(x.length == 0);
        x.large.length = 133;
        assert(x.smallLength == E.max);
        assert(x.large.length == 133);
        x.large.length = 0x0088_8888_8888_8888;
        assert(x.large.length == 0x0088_8888_8888_8888);
        assert(x.smallLength == E.max);
    }

    // is this string small?
    bool isSmall() const @safe @nogc
    {
        return smallLength <= maxSmallSize;
    }

    // release all memory associated with this
    private void decRef() @nogc
    {
        if (!isSmall) large.decRef;
    }

    // Return a slice with the string's contents
    // Not public because it leaks the internals
    auto asSlice() inout @nogc
    {
        immutable s = smallLength;
        if (s <= maxSmallSize) return small.ptr[0 .. s];
        return large[];
    }

public:

    /// Returns the length of the string
    size_t length() const @nogc
    {
        immutable s = smallLength;
        return s <= maxSmallSize ? s : large.length;
    }
    /// Ditto
    alias opDollar = length;

    static if (isString) unittest
    {
        auto s1 = RCXString("123456789_");
        assert(s1.length == 10);
        s1 ~= RCXString("123456789_123456789_123456789_123456789_12345");
        assert(s1.length == 55);
    }

    /// Needed for correct printing in other modules
    static if (isString)
    {
        string toArray() const @trusted
        {
            return this.asSlice;
        }
    }

    /** Construct a `RCXString` from a slice `s`.

        If the slice is immutable, assumes the slice is a literal or
        GC-allocated and does NOT copy it internally.

        Warning: Subsequently deallocating `s` will cause the `RCXString`
        to dangle. If the slice has `const` or mutable characters, creates
        and manages a copy internally.
     */
    this(C)(C[] s)
        if (is(Unqual!C == ME))
    {
        // Contents is immutable, we may assume it won't go away ever
        if (s.length <= maxSmallSize)
        {
            // fits in small
            small[0 .. s.length] = s[]; // so copy it
            smallLength = cast(E)s.length;
        }
        else
        {
            emplace(&large, s);
        }
    }

    // Test construction from immutable(ME)[], const(ME)[], and ME[]
    static if (isString) unittest
    {
        immutable(E)[] a = "123456789_";
        auto s1 = RCXString(a);
        assert(s1 == a);
        assert(s1.asSlice !is a, "Small strings must be copied");
        a = "123456789_123456789_123456789_123456789_";
        auto s2 = RCXString(a);
        assert(s2 == a);
        assert(s2.asSlice is a, "Large immutable strings shall not be copied");

        const(char)[] b = "123456789_";
        auto s3 = RCXString(b);
        assert(s3 == b);
        assert(s3.isSmall, "Small strings must be copied");
        b = "123456789_123456789_123456789_123456789_";
        auto s4 = RCXString(b);
        assert(s4 == b);
        assert(s4.asSlice !is b, "Large non-immutable strings shall be copied");

        char[] c = "123456789_".dup;
        auto s5 = RCXString(c);
        assert(s5 == c);
        assert(s5.isSmall, "Small strings must be copied");
        c = "123456789_123456789_123456789_123456789_".dup;
        auto s6 = RCXString(c);
        assert(s6 == c);
        assert(s6.asSlice !is c, "Large non-immutable strings shall be copied");
    }

    static if (isString) unittest
    {
        const(ME)[] s = "123456789_123456789_123456789_123456789_";
        auto s1 = RCXString(s);
        assert(s1.large.mbuf);
        auto s2 = s1;
        assert(s1.large.mbuf is s2.large.mbuf);
        assert(s1.large.mbuf.refCount == 2);
        s1 = s ~ "123";
        assert(s1.large.mbuf.refCount == 1);
        assert(s2.large.mbuf.refCount == 1);
        assert(s2 == s);
        assert(s1 == s ~ "123");
        const s3 = s1;
        assert(s1.large.mbuf.refCount == 2);
        immutable s4 = s1;
        //immutable s5 = s3;
        assert(s1.large.mbuf.refCount == 3);
    }

    // Postblit
    this(this) @nogc
    {
        if (!isSmall && large.mbuf) ++large.mbuf.refCount;
    }

    // Dtor decrements refcount and may deallocate
    ~this() @nogc
    {
        decRef;
    }

    // Assigns another string
    void opAssign(immutable(ME)[] s)
    {
        decRef;
        // Contents is immutable, we may assume it won't go away ever
        emplace(&this, s);
    }

    static if (isString) unittest
    {
        immutable(ME)[] s = "123456789_";
        RCXString rcs;
        rcs = s;
        assert(rcs.isSmall);
        s = "123456789_123456789_123456789_123456789_";
        rcs = s;
        assert(!rcs.isSmall);
        assert(rcs.large.mbuf is null);
    }

    // Assigns another string
    void opAssign(const(ME)[] s)
    {
        if (capacity >= s.length)
        {
            // Noice, there's room
            if (s.length <= maxSmallSize)
            {
                // Fits in small
                msmall[0 .. s.length] = s[];
                smallLength = cast(E) s.length;
            }
            else
            {
                // Large it is
                assert(!isSmall);
                large.mptr[0 .. s.length] = s;
                large.length = s.length;
            }
        }
        else
        {
            // Tear down and rebuild
            decRef;
            emplace(&this, s);
        }
    }

    static if (isString) unittest
    {
        const(ME)[] s = "123456789_123456789_123456789_123456789_";
        RCXString s1;
        s1 = s;
        assert(!s1.isSmall && s1.large.buf !is null);
        auto p = s1.ptr;
        s1 = s;
        assert(s1.ptr is p, "Wasteful reallocation");
        RCXString s2;
        s2 = s1;
        assert(s1.large.mbuf is s2.large.mbuf);
        assert(s1.large.mbuf.refCount == 2);
        s1 = "123456789_123456789_123456789_123456789_123456789_";
        assert(s1.large.mbuf !is s2.large.mbuf);
        assert(s1.large.mbuf is null);
        assert(s2.large.mbuf.refCount == 1);
        assert(s1 == "123456789_123456789_123456789_123456789_123456789_");
        assert(s2 == "123456789_123456789_123456789_123456789_");
    }

    bool opEquals(const(ME)[] s) const @nogc
    {
        if (isSmall) return s.length == smallLength && small[0 .. s.length] == s;
        return large[] == s;
    }

    bool opEquals(in RCXString s) const
    {
        return this == s.asSlice;
    }

    static if (isString) unittest
    {
        const s1 = RCXString("123456789_123456789_123456789_123456789_123456789_");
        RCXString s2 = s1[0 .. 10];
        auto s3 = RCXString("123456789_");
        assert(s2 == s3);
    }

    /** Returns the maximum number of character this string can store without
        requesting more memory.
     */
    size_t capacity() const @nogc
    {
        /** This is subtle: if large.mbuf is null (i.e. the string had been constructed from a literal), then the
            capacity is maxSmallSize because that's what we can store without a memory (re)allocation. Same if refCount is
            greater than 1 - we can't reuse the memory.
        */
        return isSmall || !large.mbuf || large.mbuf.refCount > 1 ? maxSmallSize : large.mbuf.capacity;
    }

    static if (isString) unittest
    {
        auto s = RCXString("abc");
        assert(s.capacity == maxSmallSize);
        s = "123456789_123456789_123456789_123456789_123456789_";
        assert(s.capacity == maxSmallSize);
        const char[] lit = "123456789_123456789_123456789_123456789_123456789_";
        s = lit;
        assert(s.capacity >= 50);
    }

    void reserve(size_t capacity)
    {
        if (isSmall)
        {
            if (capacity <= maxSmallSize)
            {
                // stays small
                return;
            }
            // small to large
            immutable length = smallLength;
            auto newLayout = Large(capacity, small.ptr[0 .. length]);
            large = newLayout;
        }
        else
        {
            // large to large
            if (large.mbuf && large.mbuf.capacity >= capacity) return;
            large.reserve(capacity);
        }
    }

    static if (isString) unittest
    {
        RCXString s1;
        s1.reserve(1);
        assert(s1.capacity >= 1);
        s1.reserve(1023);
        assert(s1.capacity >= 1023);
        s1.reserve(10230);
        assert(s1.capacity >= 10230);
    }

    /** Appends `s` to `this`.
     */
    void opOpAssign(string s : "~")(const(ME)[] s)
    {
        immutable length = this.length;
        immutable newLen = length + s.length;
        if (isSmall)
        {
            if (newLen <= maxSmallSize)
            {
                // stays small
                msmall[length .. newLen] = s;
                smallLength = cast(E) newLen;
            }
            else
            {
                // small to large
                auto newLayout = Large(newLen, small.ptr[0 .. length]);
                newLayout.mptr[length .. newLen][] = s;
                newLayout.length = newLen;
                large = newLayout;
                assert(!isSmall);
                assert(this.length == newLen);
            }
        }
        else
        {
            // large to large
            large.reserve(newLen);
            large.mptr[length .. newLen][] = s;
            large.length = newLen;
        }
    }

    static if (isString) unittest
    {
        auto s1 = RCXString("123456789_123456789_123456789_123456789_");
        s1 ~= s1;
        assert(s1 == "123456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789_");
        foreach (i; 0 .. 70) s1.popFront();
        assert(s1 == "123456789_");
        s1 ~= "abc";
        assert(s1 == "123456789_abc");
    }

    /// Ditto
    void opOpAssign(string s : "~")(const auto ref RCXString s)
    {
        this ~= s.asSlice;
    }

    static if (isString) unittest
    {
        RCXString s1;
        s1 = "hello";
        assert(s1 == "hello");
        s1 ~= ", world! ";
        assert(s1 == "hello, world! ");
        s1 ~= s1;
        assert(s1 == "hello, world! hello, world! ");
        s1 ~= s1;
        assert(s1 == "hello, world! hello, world! hello, world! hello, world! ");
        auto s2 = RCXString("yah! ");
        assert(s2 == "yah! ");
        s2 ~= s1;
        assert(s2 == "yah! hello, world! hello, world! hello, world! hello, world! ");
        s2 = "123456789_123456789_123456789_123456789_";
        s2 ~= s2;
        assert(s2 == "123456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789_");
        auto s3 = s2;
        assert(s3.large.mbuf.refCount == 2);
        s2 ~= "123456789_";
        assert(s2.large.mbuf.refCount == 1);
        assert(s3.large.mbuf.refCount == 1);
        assert(s3 == "123456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789_");

        s2 = "123456789_123456789_123456789_123456789_";
        const s4 = RCXString(", world");
        s2 ~= s4;
        assert(s2 == "123456789_123456789_123456789_123456789_, world");
        s2 ~= const RCXString("!!!");
        assert(s2 == "123456789_123456789_123456789_123456789_, world!!!");
    }

    /// Returns `true` iff `this` is empty
    bool empty() const @nogc
    {
        return !length;
    }

    static if (isString)
    {
        private dchar unsafeDecode(const(ME)* p) const @nogc
        {
            byte c = *p;
            dchar res = c & 0b0111_1111;
            if (c >= 0) return res;
            assert(c < 0b1111_1000);
            dchar cover = 0b1000_0000;
            c <<= 1;
            assert(c < 0);
            do
            {
                ++p;
                assert((*p >> 6) == 0b10);
                cover <<= 5;
                res = (res << 6) ^ *p ^ cover ^ 0b1000_0000;
                c <<= 1;
            } while(c < 0);
            return res;
        }
    }

    /// Returns the first code point of `this`.
    auto front() const @nogc
    {
        assert(!empty);
        // TODO make safe
        static if (isString)
        {
            return unsafeDecode(ptr);
        }
        else
        {
            return ptr[0];
        }
    }

    /// Returns the last code point of `this`.
    static if (isString)
    {
        dchar back() const @nogc
        {
            assert(!empty);
            auto p = ptr + length - 1;
            if (*p < 0b1000_0000) return *p;
            // TODO make safe
            do
            {
                --p;
            } while (!(*p & 0b0100_0000));
            return unsafeDecode(p);
        }
    }
    else
    {
        E back() const @nogc
        {
            return ptr[length - 1];
        }
    }

    /// Returns the `n`th code unit in `this`.
    E opIndex(size_t n) const @nogc
    {
        assert(n < length);
        return ptr[n];
    }

    static if (isString) unittest
    {
        auto s1 = RCXString("hello");
        assert(s1.front == 'h');
        assert(s1[1] == 'e');
        assert(s1.back == 'o');
        assert(s1[$ - 1] == 'o');
        s1 = RCXString("Ü");
        assert(s1.length == 2);
        assert(s1.front == 'Ü');
        assert(s1.back == 'Ü');
    }

    /// Discards the first code point
    void popFront() @nogc
    {
        assert(!empty && ptr);
        uint toPop = 1;
        auto b = *ptr;
        if (b >= 0b1000_0000)
        {
            toPop = (b | 0b0010_0000) != b ? 2
                : (b | 0b0001_0000) != b ? 3
                : 4;
        }
        if (isSmall)
        {
            // Must shuffle in place
            // TODO make faster
            foreach (i; 0 .. length - toPop)
            {
                msmall[i] = small[i + toPop];
            }
            smallLength -= toPop;
        }
        else
        {
            large.ptr += toPop;
            large.length = large.length - toPop;
        }
    }

    static if (isString) unittest
    {
        auto s1 = RCXString("123456789_");
        auto s2 = s1;
        s1.popFront();
        assert(s1 == "23456789_");
        assert(s2 == "123456789_");
        s1 = RCXString("123456789_123456789_123456789_123456789_");
        s2 = s1;
        s1.popFront();
        assert(s1 == "23456789_123456789_123456789_123456789_");
        assert(s2 == "123456789_123456789_123456789_123456789_");
        s1 = "öü";
        s2 = s1;
        s1.popFront();
        assert(s1 == "ü");
        assert(s2 == "öü");
    }

    /// Discards the last code point
    void popBack() @nogc
    {
        assert(!empty && ptr);
        auto p = ptr + length - 1;
        if (*p < 0b1000_0000)
        {
            // hot path
            if (isSmall) --smallLength;
            else large.length = large.length - 1;
            return;
        }
        // TODO make safe
        auto p1 = p;
        do
        {
            --p;
        } while (!(*p & 0b0100_0000));
        immutable diff = p1 - p + 1;
        assert(diff > 1 && diff <= length);
        if (isSmall) smallLength -= diff;
        else large.length = large.length - diff;
    }

    static if (isString) unittest
    {
        auto s1 = RCXString("123456789_");
        auto s2 = s1;
        s1.popBack;
        assert(s1 == "123456789");
        assert(s2 == "123456789_");
        s1 = RCXString("123456789_123456789_123456789_123456789_");
        s2 = s1;
        s1.popBack;
        assert(s1 == "123456789_123456789_123456789_123456789");
        assert(s2 == "123456789_123456789_123456789_123456789_");
        s1 = "öü";
        s2 = s1;
        s1.popBack;
        assert(s1 == "ö");
        assert(s2 == "öü");
    }

    /// Returns a slice to the entire string or a portion of it.
    auto opSlice() inout @nogc
    {
        return this;
    }

    /// Ditto
    auto opSlice(size_t b, size_t e) inout
    {
        assert(b <= e && e <= length);
        auto ptr = this.ptr;
        auto sz = e - b;
        if (sz <= maxSmallSize)
        {
            // result is small
            RCXString result = void;
            result.msmall[0 .. sz] = ptr[b .. e];
            result.smallLength = cast(E) sz;
            return result;
        }
        assert(!isSmall);
        RCXString result = this;
        result.large.ptr += b;
        result.large.length = e - b;
        return result;
    }

    static if (isString) unittest
    {
        immutable s = RCXString("123456789_123456789_123456789_123456789");
        RCXString s1 = s[0 .. 38];
        assert(!s1.isSmall && s1.large.buf is null);
    }

    // Unsafe! Returns a pointer to the beginning of the payload.
    auto ptr() inout @nogc
    {
        return isSmall ? small.ptr : large.ptr;
    }

    static if (isString) unittest
    {
        auto s1 = RCXString("hello");
        auto s2 = s1[1 .. $ - 1];
        assert(s2 == "ell");
        s1 = "123456789_123456789_123456789_123456789_";
        s2 = s1[1 .. $ - 1];
        assert(s2 == "23456789_123456789_123456789_123456789");
    }

    /// Returns the concatenation of `this` with `s`.
    RCXString opBinary(string s = "~")(const auto ref RCXString s) const
    {
        return this ~ s.asSlice;
    }

    /// Ditto
    RCXString opBinary(string s = "~")(const(ME)[] s) const
    {
        immutable length = this.length;
        auto resultLen = length + s.length;
        RCXString result = void;
        if (resultLen <= maxSmallSize)
        {
            // noice
            result.msmall.ptr[0 .. length] = ptr[0 .. length];
            result.msmall.ptr[length .. resultLen] = s[];
            result.smallLength = cast(E) resultLen;
            return result;
        }
        emplace(&result.large, resultLen, this.asSlice);
        result ~= s;
        return result;
    }

    /// Returns the concatenation of `s` with `this`.
    RCXString opBinaryRight(string s = "~")(const(E)[] s) const
    {
        immutable length = this.length, resultLen = length + s.length;
        RCXString result = void;
        if (resultLen <= maxSmallSize)
        {
            // noice
            result.msmall.ptr[0 .. s.length] = s[];
            result.msmall.ptr[s.length .. resultLen] = small.ptr[0 .. length];
            result.smallLength = cast(E) resultLen;
            return result;
        }
        emplace(&result.large, resultLen, s);
        result ~= this;
        return result;
    }

    static if (isString) unittest
    {
        auto s1 = RCXString("hello");
        auto s2 = s1 ~ ", world!";
        assert(s2 == "hello, world!");
        s1 = "123456789_123456789_123456789_123456789_";
        s2 = s1 ~ "abcdefghi_";
        assert(s2 == "123456789_123456789_123456789_123456789_abcdefghi_");
        s2 = s1 ~ s1;
        assert(s2 == "123456789_123456789_123456789_123456789_123456789_123456789_123456789_123456789_");
        s2 = "abcdefghi_" ~ s1;
        assert(s2 == "abcdefghi_123456789_123456789_123456789_123456789_");
    }
}

unittest
{
    alias RCI = RCXString!(immutable uint);
    RCI x;
}

/// verify UTF-8 storage
unittest
{
    string s = "åäö";
    RCString rcs = s;
    assert(rcs.length == 6);
    import std.algorithm : count;
    assert(rcs.count == 3);
    assert(rcs.front == 'å');
    rcs.popFront();
    assert(rcs.front == 'ä');
    rcs.popFront();
    assert(rcs.front == 'ö');
    rcs.popFront();
    assert(rcs.empty);
}

version = profile;

/// shows performance increase for SSO over built-in string
version(profile) unittest
{
    enum maxSmallSize = 23;
    alias S = RCXString!(immutable char, maxSmallSize);

    import std.datetime: StopWatch, Duration;
    import std.conv : to;
    import std.stdio;

    enum n = 2^^21;

    StopWatch sw;

    sw.reset;
    sw.start;
    char[maxSmallSize] ss;
    foreach (i; 0 .. n)
    {
        auto x = S(ss);
    }
    sw.stop;
    auto timeRCString = sw.peek().msecs;
    writeln("> RCString took ", sw.peek().to!Duration);

    sw.reset;
    sw.start;
    foreach (i; 0 .. n)
    {
        string x = ss.idup;
    }
    sw.stop;
    auto timeString = sw.peek().msecs;
    writeln("> Builtin string took ", sw.peek().to!Duration);

    writeln("> Speedup: ", timeString/timeRCString);
}