reify.d

import std;

/**
Reified type. Currently stores the plain name (not the mangled name).
*/
struct Id
{
    enum Kind : ubyte { _type, _alias };
    // state {
    Kind kind;
    string name;
    string[] bases;
    // }

    // Use reify (defined below) to create objects of type Id.
    this(Kind kind, string name, string[] bases = null)
    {
        this.kind = kind;
        this.name = name;
        this.bases = bases;
    }

    // Comparison for equality relies on strings being interned.
    bool opEquals(const Id rhs) const
    {
        if (kind != rhs.kind) return false;
        assert((name.ptr != rhs.name.ptr) || (name == rhs.name), "Internal error: strings not interned.");
        return name.ptr == rhs.name.ptr;
    }

    // Comparison for ordering makes bases "greater".
    int opCmp(const Id rhs) const {
        if (this == rhs) return 0;
        int result = (bases.length < rhs.bases.length) - (rhs.bases.length < bases.length);
        if (result == 0)
            // They are not equal and have the same depth, can't be related
            return 0;
        const(string)[] haystack;
        string needle;
        if (result > 0)
        {
            // this could be a base of rhs, search this among rhs's bases
            haystack = rhs.bases;
            needle = name;
        }
        else
        {
            // rhs could be a base of this, search for rhs among this's bases
            haystack = bases;
            needle = rhs.name;
        }
        foreach (s; haystack)
            if (s == needle)
                return result;
        return 0;
    }

    // kinda crappy just for demo purposes, will redo
    Id addConst()()
    {
        assert(kind == Kind._type);
        return Id(kind, "const(" ~ name ~ ")");
    }
}

/**
Remove all type qualifiers from `id`.
*/
Id unqual(Id id)()
{
    assert(id.kind == Id.Kind._type);
    return reify!(Unqual!(dereify!id));
}

///
unittest
{
    alias T = dereify!(reify!(int).addConst());
    static assert(is(T == const int));
    alias U = dereify!(unqual!(reify!T));
    static assert(is(U == int));
}

/**
Reification: given a type, alias, or expression, returns an object associated with it.
*/
auto reify(T)()
{
    string[] bases;
    static if (is(T == class)) {
        alias Super = BaseClassesTuple!T;
        // Save the base classes as well
        static foreach (C; Super)
            bases ~= C.stringof;
    }
    return Id(Id.Kind._type, T.stringof, bases);
}

/// ditto
auto reify(alias T)()
{
    return Id(Id.Kind._alias, T.stringof);
}

/**
Reification of a collevtion of items: given zero or more types, aliases, or expressions, returns an
array of `Id`s associated with them.
*/
Id[] reifyArray(T...)()
{
    Id[] result;
    result.length = T.length;
    static foreach (i, X; T)
        result[i] = reify!X;
    return result;
}

/**
Dereification: given one ore more `Id` object, yields the type associated with it.
*/
template dereify(Id id) {
    static if (id.kind == Id.Kind._type)
        mixin("alias dereify = " ~ id.name ~ ";");
    else
        mixin("enum dereify = " ~ id.name ~ ";");
}

/// ditto
template dereify(Id[] ids) {
    // TODO: replace recursive implementation with iterative.
    static if (ids.length == 0)
        alias dereify = AliasSeq!();
    else static if (ids.length == 1)
        alias dereify = AliasSeq!(dereify!(ids[0]));
    else
        alias dereify = AliasSeq!(dereify!(ids[0 .. $ / 2]), dereify!(ids[$ / 2 .. $]));
}

unittest
{
    enum a = reify!int;
    static assert(a.name == "int");
    enum b = reify!42;
    static assert(b.name == "42");
    static assert(reify!(1+1).name == "2");
    static assert(is(dereify!a == int));
    static assert(dereify!b == 42);
    static assert(dereify!(reify!"hello") == "hello");
}

////////////////////////////////////////////////////////////////////////////////
// A few samples taken from std.meta
////////////////////////////////////////////////////////////////////////////////

enum staticIndexOf(Args...) = {
    auto id = reify!(Args[0]);
    auto ids = reifyArray!(Args[1 .. $]);
    auto tail = ids.find(id).length;
    return tail == 0 ? -1 : ids.length - tail;
}();

@safe unittest
{
    static assert(staticIndexOf!( byte, byte, short, int, long) ==  0);
    static assert(staticIndexOf!(short, byte, short, int, long) ==  1);
    static assert(staticIndexOf!(  int, byte, short, int, long) ==  2);
    static assert(staticIndexOf!( long, byte, short, int, long) ==  3);
    static assert(staticIndexOf!( char, byte, short, int, long) == -1);
    static assert(staticIndexOf!(   -1, byte, short, int, long) == -1);
    static assert(staticIndexOf!(void) == -1);

    static assert(staticIndexOf!("abc", "abc", "def", "ghi", "jkl") ==  0);
    static assert(staticIndexOf!("def", "abc", "def", "ghi", "jkl") ==  1);
    static assert(staticIndexOf!("ghi", "abc", "def", "ghi", "jkl") ==  2);
    static assert(staticIndexOf!("jkl", "abc", "def", "ghi", "jkl") ==  3);
    static assert(staticIndexOf!("mno", "abc", "def", "ghi", "jkl") == -1);
    static assert(staticIndexOf!( void, "abc", "def", "ghi", "jkl") == -1);
    static assert(staticIndexOf!(42) == -1);

    static assert(staticIndexOf!(void, 0, "void", void) == 2);
    static assert(staticIndexOf!("void", 0, void, "void") == 2);
}

alias Erase(Args...) = dereify!({
    auto id = reify!(Args[0]);
    auto ids = reifyArray!(Args[1 .. $]);
    // TODO: do something more efficient.
    auto p = ids.findSplit([id]);
    return p[0] ~ p[2];
}());

@safe unittest
{
    alias T = Erase!(int, short, int, int, 4);
    static assert(T.stringof == "tuple((short), (int), 4)");
    alias U = Erase!(1, real, 3, 1, 4, 1, 5, 9);
    static assert(U.stringof == "tuple((real), 3, 4, 1, 5, 9)");
}

alias EraseAll(Args...) = dereify!({
    auto id = reify!(Args[0]);
    auto ids = reifyArray!(Args[1 .. $]);
    return ids.remove!(x => x == id);
}());

@safe unittest
{
    alias T = EraseAll!(int, short, int, int, 4);
    static assert(T.stringof == "tuple((short), 4)");
    alias U = EraseAll!(1, real, 3, 1, 4, 1, 5, 9);
    static assert(U.stringof == "tuple((real), 3, 4, 5, 9)");
}

alias NoDuplicates(Args...) = dereify!({
    auto ids = reifyArray!Args;
    size_t newLength = ids.length;
    for (size_t i = 0; i < newLength; ++i) {
        newLength = 1 + i + ids[i + 1 .. $].remove!(x => x == ids[i]).length;
    }
    return ids[0 .. newLength];
}());

@safe unittest
{
    alias Types = AliasSeq!(int, long, long, int, float);
    alias TL = NoDuplicates!Types;
    static assert(is(TL == AliasSeq!(int, long, float)));
}

@safe unittest
{
    alias LongList = Repeat!(1500, int);
    static assert(NoDuplicates!LongList.length == 1);
    alias a = NoDuplicates!(AliasSeq!(1, Repeat!(1000, 3)));
    alias b = NoDuplicates!(AliasSeq!(1, Repeat!(10, 3)));
    static assert(a.length == b.length);
    static assert(NoDuplicates!(aliasSeqOf!(iota(7)), aliasSeqOf!(iota(7))) == aliasSeqOf!(iota(7)));
    static assert(NoDuplicates!(aliasSeqOf!(iota(8)), aliasSeqOf!(iota(8))) == aliasSeqOf!(iota(8)));
}

alias Replace(Args...) = dereify!({
    auto find = reify!(Args[0]);
    auto replace = reify!(Args[1]);
    auto range = reifyArray!(Args[2 .. $]);
    for (size_t i = 0; i < range.length; ++i) {
        if (range[i] == find) {
            range[i] = replace;
            break;
        }
    }
    return range;
}());

///
@safe unittest
{
    alias Types = AliasSeq!(int, long, long, int, float);
    alias TL = Replace!(long, char, Types);
    static assert(is(TL == AliasSeq!(int, char, long, int, float)));
}

alias ReplaceAll(Args...) = dereify!({
    auto find = reify!(Args[0]);
    auto replace = reify!(Args[1]);
    auto range = reifyArray!(Args[2 .. $]);
    for (size_t i = 0; i < range.length; ++i) {
        if (range[i] == find) {
            range[i] = replace;
        }
    }
    return range;
}());

@safe unittest
{
    alias Types = AliasSeq!(int, long, long, int, float);
    alias TL = ReplaceAll!(long, char, Types);
    static assert(is(TL == AliasSeq!(int, char, char, int, float)));
}

alias Reverse(Args...) = dereify!({
    auto ids = reifyArray!Args;
    reverse(ids);
    return ids;
}());

@safe unittest
{
    alias Types = AliasSeq!(int, long, long, int, float, byte, ubyte, short, ushort, uint);
    alias TL = Reverse!(Types);
    static assert(is(TL == AliasSeq!(uint, ushort, short, ubyte, byte, float, int, long, long, int)));
}

alias DerivedToFront(Args...) = dereify!({
    auto ids = reifyArray!Args;
    ids.sort;
    return ids;
}());

class A { }
class B : A { }
class C : B { }
alias Types = AliasSeq!(A, C, B);

@safe unittest
{
    static assert(reify!B != reify!A);
    static assert(reify!B < reify!A);
    static assert(reify!C < reify!B);
    static assert(reify!C < reify!A);
    alias TL = DerivedToFront!(Types);
    static assert(is(TL == AliasSeq!(C, B, A)));
}

alias staticMap(alias F, Args...) = dereify!({
    static immutable ids = reifyArray!Args;
    Id[] result;
    result.length = Args.length;
    static foreach (i; 0 .. Args.length)
        result[i] = reify!(F!(dereify!(ids[i])));
    return result;
}());

///
@safe unittest
{
    import std.traits : Unqual;
    alias TL = staticMap!(Unqual, int, const int, immutable int, uint, ubyte, byte, short, ushort);
    static assert(is(TL == AliasSeq!(int, int, int, uint, ubyte, byte, short, ushort)));
}

@safe unittest
{
    import std.traits : Unqual;

    // empty
    alias Empty = staticMap!(Unqual);
    static assert(Empty.length == 0);

    // single
    alias Single = staticMap!(Unqual, const int);
    static assert(is(Single == AliasSeq!int));

    alias T = staticMap!(Unqual, int, const int, immutable int, uint, ubyte, byte, short, ushort, long);
    static assert(is(T == AliasSeq!(int, int, int, uint, ubyte, byte, short, ushort, long)));
}

// regression test for https://issues.dlang.org/show_bug.cgi?id=21088
@system unittest // typeid opEquals is @system
{
    enum getTypeId(T) = typeid(T);
    // TODO: see why this doesn't work.
    //alias A = staticMap!(getTypeId, int);
    //assert(A == typeid(int));
}

enum allSatisfy(alias F, Args...) = {
    static immutable ids = reifyArray!Args;
    static foreach (i; 0 .. Args.length)
        if (!F!(dereify!(ids[i])))
            return false;
    return true;
}();

@safe unittest
{
    import std.traits : isIntegral;
    static assert(!allSatisfy!(isIntegral, int, double));
    static assert( allSatisfy!(isIntegral, int, long));
}

enum anySatisfy(alias F, Ts...) = {
    static immutable ids = reifyArray!Ts;
    static foreach (i; 0 .. Ts.length)
        if (F!(dereify!(ids[i])))
            return true;
    return false;
}();

///
@safe unittest
{
    import std.traits : isIntegral;
    static assert(!anySatisfy!(isIntegral, string, double));
    static assert( anySatisfy!(isIntegral, int, double));
}

alias Filter(alias F, Args...) = dereify!({
    static immutable ids = reifyArray!Args;
    Id[] result;
    static foreach (i; 0 .. Args.length)
    {{
        enum id = ids[i];
        if (F!(dereify!id))
            result ~= id;
    }}
    return result;
}());

@safe unittest
{
    import std.traits : isNarrowString, isUnsigned;

    alias Types1 = AliasSeq!(string, wstring, dchar[], char[], dstring, int);
    alias TL1 = Filter!(isNarrowString, Types1);
    static assert(is(TL1 == AliasSeq!(string, wstring, char[])));

    alias Types2 = AliasSeq!(int, byte, ubyte, dstring, dchar, uint, ulong);
    alias TL2 = Filter!(isUnsigned, Types2);
    static assert(is(TL2 == AliasSeq!(ubyte, uint, ulong)));
}

@safe unittest
{
    import std.traits : isPointer;
    static assert(is(Filter!(isPointer, int, void*, char[], int*) == AliasSeq!(void*, int*)));
    static assert(is(Filter!isPointer == AliasSeq!()));
}

// Had to hoist this outside the unittest because dereify uses stringof
static struct S {}

@safe unittest
{
    enum Yes(T) = true;
    static assert(is(Filter!(Yes, const(int), const(S)) == AliasSeq!(const(int), const(S))));
}

alias Repeat(size_t n, Args...) = dereify!({
    static immutable ids = reifyArray!Args;
    return ids.cycle.take(n * Args.length).array;
}());

@safe unittest
{
    alias ImInt0 = Repeat!(0, int);
    static assert(is(ImInt0 == AliasSeq!()));

    alias ImInt1 = Repeat!(1, immutable(int));
    static assert(is(ImInt1 == AliasSeq!(immutable(int))));

    alias Real3 = Repeat!(3, real);
    static assert(is(Real3 == AliasSeq!(real, real, real)));

    alias Real12 = Repeat!(4, Real3);
    static assert(is(Real12 == AliasSeq!(real, real, real, real, real, real,
        real, real, real, real, real, real)));

    alias Composite = AliasSeq!(uint, int);
    alias Composite2 = Repeat!(2, Composite);
    static assert(is(Composite2 == AliasSeq!(uint, int, uint, int)));

    alias ImInt10 = Repeat!(10, int);
    static assert(is(ImInt10 == AliasSeq!(int, int, int, int, int, int, int, int, int, int)));
}

///
@safe unittest
{
    auto staticArray(T, size_t n)(Repeat!(n, T) elems)
    {
        T[n] a = [elems];
        return a;
    }

    auto a = staticArray!(long, 3)(3, 1, 4);
    assert(is(typeof(a) == long[3]));
    assert(a == [3, 1, 4]);
}