/** Lightweight versions of polymorphism packed inside one single
    word/pointer.

    Most significant bits are used to store type information.

    These higher bits are normally unused on 64-bit systems (tested on
    Linux). 16 higher bits are, on Linux, either 1 (kernel-space) or 0 (user-space).

    See_Also: http://forum.dlang.org/post/sybuoliqhhefcovxjfjv@forum.dlang.org

    TODO: Ask forum.dlang.org: Is it safe to assume that `typeBits` most significant bits of a
    pointer are zero? If not put them in least significant part.

    TODO: What todo with the fact that the GC will fail to scan WordVariant?
    Can the GC be tweaked to mask out the type bits before scanning?

    TODO: Enable support for `is null` instead of `isNull`?

    TODO: Use `enforce()` instead of `assert()` in WordVariant:initialize()

    TODO: Move to Phobos std.variant
*/
module nxt.variant_ex;

/** A variant of `Types` packed into a word (`size_t`).
 *
 * Suitable for use in tree-data containers, such as radix trees (tries), where
 * hybrid value (sparsely packed sub-tree) and pointer (to dense sub-tree)
 * packing of sub-nodes is needed.
 */
struct WordVariant(Types...)
{
    import nxt.traits_ex : allSame, sizesOf;
    static assert(allSame!(sizesOf!(Types)), "Types must have equal size");
    static assert(this.sizeof == (void*).sizeof, "Size must be same as word (pointer)");

    alias S = size_t; // TODO: templatize?

    import nxt.typecons_ex : makeEnumFromSymbolNames;
    alias Ix = makeEnumFromSymbolNames!(`ix_`, ``, true, false, Types);
    static assert(Ix.undefined == 0);

    import nxt.bit_traits : bitsNeeded;
    enum typeBits = bitsNeeded!(1 + Types.length); // number of bits needed to represent variant type, plus one for undefined state
    enum typeShift = 8*S.sizeof - typeBits;
    enum typeMask = cast(S)(2^^typeBits - 1) << typeShift;

    import std.meta : staticIndexOf;
    enum indexOf(T) = staticIndexOf!(T, Types); // TODO: cast to ubyte if Types.length is <= 256

    /// Is `true` iff a `T` can be stored.
    enum canStore(T) = indexOf!T >= 0;

    pure:

    @property string toString() const @trusted // TODO: pure nothrow
    {
        import std.traits : isPointer;
        import std.conv : to;
        final switch (typeIndex) // typeIndex starts at 0 (undefined)
        {
        case 0: return "null";
            foreach (const i, T; Types)
            {
            case i + 1:
                // TODO: improve this to look more like D-code:
                static if (isPointer!T)
                    return T.stringof ~ `@` ~ as!T.to!string; // TODO: ~ `:` ~ (*as!T).to!string;
                else
                    return T.stringof ~ `@` ~ as!T.to!string;
            }
        }
    }

    nothrow:

    extern (D) auto toHash() const
    {
        import core.internal.hash : hashOf;
        return _raw.hashOf;
    }

    @nogc:

    /// Construction from `value`.
    this(T)(T value) if (canStore!T) { initialize(value); }
    /// ditto
    this(typeof(null) value) { _raw = S.init; }
    /// Construction from sub-variant `value`.
    this(SubTypes...)(WordVariant!(SubTypes) value) { initializeFromSub(value); }

    /// Assignment from `that`.
    auto ref opAssign(typeof(this) value) { _raw = value._raw; return this; }
    /// ditto
    auto ref opAssign(T)(T that) if (canStore!T) { initialize(that); return this; }
    /// ditto
    auto ref opAssign(typeof(null) that) { _raw = S.init; return this; }
    /// Assignment from sub-variant `value`.
    auto ref opAssign(SubTypes...)(WordVariant!(SubTypes) value) { initializeFromSub(value); return this; }

pragma(inline):

    /** Reference to peek of type `T`. */
    static private struct Ref(T)
    {
        S _raw;
        const bool defined;
        pragma(inline):
        bool opCast(T : bool)() const { return defined; }
        inout(T) opUnary(string op : `*`)() @trusted inout
        {
            auto data = (_raw & ~typeMask); // mask away type bits
            return *(cast(typeof(return)*)&data);
        }
    }

    @property inout(Ref!T) peek(T)() inout @trusted if (canStore!T)
    {
        if (!ofType!T)
            return typeof(return).init;
        return typeof(return)(_raw, true);
    }

    bool opEquals(WordVariant that) const
    {
        return _raw == that._raw;
    }

    bool opEquals(T)(T that) const
    {
        auto x = peek!T; // if `this` contains pointer of to instance of type `T`
        return x && *x == that; // and is equal to it
    }

    bool isNull() const
    {
        return _raw == S.init;
    }

    bool opCast(T : bool)() const
    {
        return !isNull;
    }

    private void initialize(T)(T that) @trusted
    {
        const thatRaw = (*(cast(S*)(&that)));
        assert(!(thatRaw & typeMask), `Top-most bits of parameter is already occupied`); // TODO: use enforce instead?
        _raw = (thatRaw | // data in lower part
                (cast(S)(indexOf!T + 1) << typeShift)); // use higher bits for type information
    }

    private void initializeFromSub(SubTypes...)(WordVariant!(SubTypes) that) @trusted
    {
        import std.meta : staticIndexOf;
        final switch (that.typeIndex)
        {
        case 0:
            this._raw = 0;      // propagate `undefined`/`null`
            foreach (const i, SubType; SubTypes)
            {
                static assert(staticIndexOf!(SubType, Types) != -1,
                              "Subtype " ~ SubType.stringof ~ " must be part of the supertypes " ~ Types.stringof);
            case i + 1:
                this._raw = (that.rawValue | // raw value
                             (cast(S)(indexOf!SubType + 1) << typeShift)); // super type index
                break;
            }
        }
    }

    private bool ofType(T)() const if (canStore!T)
    {
        return (!isNull &&
                typeIndex == indexOf!T + 1);
    }

    inout(T) as(T)() inout @trusted if (canStore!T)
    {
        // only in debug mode because it's meant to be called in conjunction with `typeIndex`
        assert(ofType!T);
        inout x = rawValue;
        return *(cast(typeof(return)*)(cast(void*)&x)); // reinterpret
    }

    /** Get zero-offset index as `Ix` of current variant type. */
    Ix typeIx() const
    {
        return cast(typeof(return))typeIndex;
    }

    /** Get zero-offset index of current variant type. */
    private auto typeIndex() const
    {
        return ((_raw & typeMask) >> typeShift);
    }

    private S rawValue() const
    {
        return _raw & ~typeMask;
    }

    private S _raw;             // raw untyped word

}

/* TODO: activate to figure out what makes Sample instance consume RAM */
version(debugMemoryUsage)
{
	struct S {}
	struct T {}
	alias Sample = WordVariant!(S, T);
}

///
pure nothrow unittest
{
    import std.meta : AliasSeq;

    alias SubType = WordVariant!(byte*, short*);
    alias SuperType = WordVariant!(bool*, byte*, short*, long*);

    byte* byteValue = cast(byte*)(0x11);
    short* shortValue = cast(short*)(0x22);

    SubType sub = byteValue;
    assert(sub.typeIndex == 1);
    assert(sub.peek!(byte*));
    assert(*(sub.peek!(byte*)) == byteValue);

    SuperType sup = sub;
    assert(sup.typeIndex == 2);
    assert(sup.peek!(byte*));
    assert(*(sup.peek!(byte*)) == byteValue);

    sub = shortValue;
    assert(sub.typeIndex == 2);
    assert(sub.peek!(short*));
    assert(*(sub.peek!(short*)) == shortValue);

    sup = sub;
    assert(sup.typeIndex == 3);
    assert(sup.peek!(short*));
    assert(*(sup.peek!(short*)) == shortValue);
}

///
pure nothrow unittest
{
    import std.meta : AliasSeq;

    alias Types = AliasSeq!(byte*, short*, int*, long*,
                            ubyte*, ushort*, uint*, ulong*,
                            float*, double*, real*,
                            char*, wchar*, dchar*);

    alias V = WordVariant!Types;
    V v;

    try
    {
        assert(v.toString == "null");
    }
    catch (Exception e) {}

    assert(v.isNull);
    v = null;
    assert(v.isNull);
    assert(!v);

    foreach (Tp; Types)
    {
        alias T = typeof(*Tp.init);

        static assert(!__traits(compiles, { T[] a; v = &a; }));
        static assert(!__traits(compiles, { v.peek!(T[]*); }));

        // assignment from stack pointer
        T a = 73;
        T a_ = 73;

        v = &a;
        assert(v);
        assert(!v.isNull);
        assert(v.typeIndex != 0);
        assert(v.ofType!Tp);

        assert(v == &a);
        assert(v != &a_);
        assert(v);

        foreach (Up; Types)
        {
            alias U = typeof(*Up.init);
            static if (is(T == U))
            {
                assert(v.peek!Up);
                assert(*(v.peek!Up) == &a);
                assert(v.as!Up == &a);
            }
            else
                assert(!v.peek!Up);
        }

        // assignment from heap pointer
        T* b = new T;
        T* b_ = new T;
        *b = 73;
        *b_ = 73;
        v = b;
        assert(v == b);
        assert(v != b_);
        assert(v);
        foreach (Up; Types)
        {
            alias U = typeof(*Up.init);
            static if (is(T == U))
            {
                assert(v.peek!Up);
                assert(*(v.peek!Up) == b);
            }
            else
                assert(!v.peek!Up);
        }

    }
}

/** A typed pointer to a variant of `Types`, packed into a word (`size_t`).
 *
 * See_Also: `std.bitmanip.taggedPointer`.
 */
struct VariantPointerTo(Types...)
{
    static assert(this.sizeof == (void*).sizeof, "Size must be same as word (pointer)");

    alias S = size_t; // TODO: templatize?

    import nxt.bit_traits : bitsNeeded;
    enum typeBits = bitsNeeded!(Types.length); // number of bits needed to represent variant type
    enum typeShift = 8*S.sizeof - typeBits;
    enum typeMask = cast(S)(2^^typeBits - 1) << typeShift;

    import std.meta : staticIndexOf;
    enum indexOf(T) = staticIndexOf!(T, Types); // TODO: cast to ubyte if Types.length is <= 256

    /// Is `true` iff a pointer to a `T` can be stored.
    enum canStorePointerTo(T) = indexOf!T >= 0;

    pure:

    @property string toString() const @trusted // TODO: pure
    {
        import std.conv : to;
        final switch (typeIndex)
        {
            foreach (const i, T; Types)
            {
            case i: return T.stringof ~ `@` ~ ptr.to!string;
            }
        }
    }

    nothrow:

    extern (D) auto toHash() const
    {
        import core.internal.hash : hashOf;
        return _raw.hashOf;
    }

    @nogc:

    /// Construction from `value`.
    this(T)(T* value)
    if (canStorePointerTo!T)
    {
        init(value);
    }
    /// ditto
    this(typeof(null) value) { /* null is the default */ }

    /// Assignment from `that`.
    auto ref opAssign(T)(T* that)
    if (canStorePointerTo!T)
    {
        init(that);
        return this;
    }
    /// ditto
    auto ref opAssign(typeof(null) that)
    {
        _raw = S.init;
        return this;
    }

    @property inout(void)* ptr() inout @trusted
    {
        return cast(void*)(_raw & ~typeMask);
    }

    @property inout(T)* peek(T)() inout @trusted if (canStorePointerTo!T)
    {
        static if (is(T == void))
            static assert(canStorePointerTo!T, `Cannot store a ` ~ T.stringof ~ ` in a ` ~ name);
        if (!pointsTo!T)
            return null;
        return cast(inout T*)ptr;
    }

    bool opEquals(T)(T* that) const @trusted
    {
        auto x = peek!T; // if `this` contains pointer of to instance of type `T`
        return (x &&
                x == that); // and is equal to it
    }

    bool isNull() const
    {
        return ptr is null;
    }

    bool opCast(T : bool)() const
    {
        return ptr !is null;
    }

    private void init(T)(T* that)
    {
        const thatRaw = cast(S)that;
        assert(!(thatRaw & typeMask), `Top-most bits of pointer are already occupied`); // TODO: use enforce instead?
        _raw = (thatRaw | // pointer in lower part
                (cast(S)(indexOf!T) << typeShift)); // use higher bits for type information
    }

    /** Get zero-offset index of current variant type. */
    private auto typeIndex() const
    {
        return (_raw & typeMask) >> typeShift;
    }

    private bool pointsTo(T)() const if (canStorePointerTo!T)
    {
        return typeIndex == indexOf!T;
    }

    private S _raw;             // raw untyped word

}

///
pure nothrow unittest
{
    import std.meta : AliasSeq;

    alias Types = AliasSeq!(byte, short, int, long,
                            ubyte, ushort, uint, ulong,
                            float, double, real,
                            char, wchar, dchar);

    alias V = VariantPointerTo!Types;

    V v;
    assert(v.isNull);
    v = null;
    assert(v.isNull);
    assert(!v);

    foreach (T; Types)
    {
        static assert(!__traits(compiles, { T[] a; v = &a; }));
        static assert(!__traits(compiles, { v.peek!(T[]*); }));

        // assignment from stack pointer
        T a = 73;
        T a_ = 73;
        v = &a;
        assert(v == &a);
        assert(v != &a_);
        assert(v);
        foreach (U; Types)
        {
            static if (is(T == U))
            {
                assert(v.peek!U);
                assert(*(v.peek!U) == a);
            }
            else
                assert(!v.peek!U);
        }

        // assignment from heap pointer
        T* b = new T;
        T* b_ = new T;
        *b = 73;
        *b_ = 73;
        v = b;
        assert(v == b);
        assert(v != b_);
        assert(v);
        foreach (U; Types)
        {
            static if (is(T == U))
            {
                assert(v.peek!U);
                assert(*(v.peek!U) == *b);
            }
            else
                assert(!v.peek!U);
        }

    }
}