module variant;
// By Reiner Pope

version (Tango)
    import tango.core.Tuple : IndexOf, Unique;
else
    import std.typetuple : IndexOf, Unique = NoDuplicates;

/** Simple Discriminated Unions for D. (Lacking support for recursive types and _extensible_ pattern matching.)

    This module presents an implementation of type-safe discriminated unions for D, employing meta-programming
    to implement pattern-matching.

    The base data-structure is the Variant struct, which takes a list of types:
         alias Variant!(int, char[], Foo) MyVariant; // MyVariant is a type which can be assigned ints, char[]s, or Foo's.

    Pattern matching can be done with a Match!() or a MatchStrict!() statement, both of which have the same prototype: 
       they expect the variable as a first parameter, followed by a list of cases.

    A case is created using the Case!() template:
       first parameter expresses the pattern, which can be of two forms:
            "type name"                 eg    "int n"
            "{type1|type2|...} name"    eg    "{int|float|char[]} f"
       second parameter is the code to be executed with this newly-declared variable. It should be D code, which makes sense
          when injected (via mixin) to the calling scope.*/

public:
template Case(char[] pattern, char[] code)
{
    static if (pattern[0] == '{')
    {
        alias MakeCaseList!(findNewPatterns(pattern), code).List Case;
    }
    else
        alias CaseImpl!(pattern, code) Case;
}

template Match(alias Variant, Cases...)
{
    const char[] Match = MatchImpl!(Variant, false, Cases);
}

template MatchStrict(alias Variant, Cases...)
{
    const char[] MatchStrict = MatchImpl!(Variant, true, Cases);
}

struct Variant(T...)
{
    ulong _variant_type;
    alias T Types;
    union { T _variant_data; }
   
    public:
    mixin(makeOpAssigns!(0, T));
}


private:
template CaseImpl(char[] pattern, char[] code)
{
    const bool IsCase = true;
    const char[] Pattern = pattern;
    const char[] Code = code;

    const int SeparatorIndex = findLastWhitespace(pattern);

    static assert(SeparatorIndex != -2, "Pattern must have no newlines");
    static assert(SeparatorIndex > 0, "Pattern must be of the form 'type name'");

    const char[] TypeName = pattern[0..SeparatorIndex];
    const char[] VariableName = pattern[SeparatorIndex..$];

    mixin("alias " ~ TypeName ~ " Type;");

    char[] GenerateCode(ulong[] indices)
    {
        assert(indices.length > 0, "Unreachable case statement: " ~ pattern);
        char[] genCode = "// pattern: " ~ pattern ~ \n;

        // Generate the 'case 5:' statements
        foreach (i; indices)
            genCode ~= \t "case " ~ itoa(i) ~ ":\n";

	genCode ~= pattern ~ ";\n";

        // Instantiate the variable:
        if (indices.length == 1)
            genCode ~= VariableName ~ " = _variant_data[" ~ itoa(indices[0]) ~ "];\n";
   	else
	{
	    genCode ~= "switch (_variant_type) {\n";
            foreach (i; indices)
		genCode ~= "case " ~ itoa(i) ~ ": " ~ VariableName ~ " = _variant_data[" ~ itoa(i) ~ "]; break;\n";
	    genCode ~= "}\n";
	}

	genCode ~= code ~ \n "break;" \n \n;
        return genCode;
    }
}

template MakeCaseList(PatternsThenCode...)
{
    static if (PatternsThenCode[0].length == 0)
        alias Tuple!() List;
    else
        alias Tuple!(Case!(PatternsThenCode[0][0], PatternsThenCode[1]), 
              MakeCaseList!(PatternsThenCode[0].slice(1), PatternsThenCode[1]).List) List;
}

template Tuple(T...)
{
    alias T Tuple;
}

char[][] slice(char[][] list, size_t index1, size_t index2 = size_t.max)
{
    if (index2 == size_t.max) return list[index1..$];
    return list[index1..index2];
}

char[][] findNewPatterns(char[] pattern)
{
    char[][] types;
    char[] name;
    size_t beginIndex = 1;
    foreach (size_t i, char c; pattern)
    {
        if (c == '|' || c == '}')
        {
            assert(i > beginIndex, "Multi-pattern format is {type1|type2|type3|type4} name");
            types ~= pattern[beginIndex .. i];
            beginIndex = i + 1;
        }
        if (c == '}')
            name = pattern[i + 1..$];
    }
    
    char[][] retVal;
    foreach (char[] type; types)
    {
        retVal ~= type ~ name;
    }
    return retVal;
}

int findLastWhitespace(char[] pattern)
{
    int index = -1;
    for (int i = pattern.length - 1; i >= 0; i--)
    {
        if (pattern[i] == '\t' || pattern[i] == ' ' && index == -1)
            index = i;
    }
    return index;
}

const ulong[] EmptyIndexList = [];

template MatchImpl(alias Variant, bool Strict, Cases...)
{
    const char[] MatchImpl = "with (" ~ Variant.stringof ~ ") {" \n
                            "switch (_variant_type) {" \n ~
                                GenerateCases!(typeof(Variant), Strict, EmptyIndexList, Cases).Code ~ \n
                                "default: break;" \n
                            "} \n"
                         "}";
}

template TypeIndices(Type1, T...)
{
    static if (IndexOf!(Type1, T) >= 0)
        const ulong[] TypeIndices = [cast(ulong)IndexOf!(Type1, T)];
    else
        const ulong[] TypeIndices = DerivedIndices!(Type1, 0, T);
}

template GenerateCases(VType, bool Strict, IndicesThenCases...)
{
    // Lets grab our parameters again
    const ulong[] usedIndices = IndicesThenCases[0];
    alias IndicesThenCases[1..$] Cases;

    static if (Cases.length == 0)
    {
        static assert(!Strict || (usedIndices.length == VType.Types.length), "Not all cases expressed in match statement");
        const char[] Code = "";
    }
    else
    {
        static assert(Cases[0].IsCase, "Match statement must be composed of Case!() statements");
        alias Cases[0] TheFirstCase;   // A workaround for bug #1215
        alias TheFirstCase.Type TheType;
        const ulong[] indices = TypeIndices!(TheType, VType.Types);
        const ulong[] uniqueIndices = removeOnesUsedFrom(indices, usedIndices);

        const char[] Code = Cases[0].GenerateCode(uniqueIndices) ~ 
                 GenerateCases!(VType, Strict, getConcat(usedIndices, uniqueIndices), Cases[1..$]).Code;
    }
}


// A workaround for bug #1216
ulong[] getConcat(ulong[] a, ulong[] b)
{
    return a ~ b;
}

ulong[] removeOnesUsedFrom(ulong[] indices, ulong[] others)
{
    ulong[] retVal = [];
    foreach (k; indices)
    {
        bool found = false;
        foreach (j; others)
        {
            if (j == k) found = true;
            break;
        }
        if (!found) retVal ~= k;
    }
    return retVal;
}

template DerivedIndices(Type1, ulong index = 0, T...)
{
    static if (index == T.length)
    {
        const ulong[] DerivedIndices = [];
    }
    else
    {
        static if (is(T[index] : Type1))
        {
            const ulong[] DerivedIndices = index ~ DerivedIndices!(Type1, index+1, T);
        }
        else
        {
            const ulong[] DerivedIndices = DerivedIndices!(Type1, index+1, T);
        }
    }
}



template makeOpAssigns(ulong index, T...)
{
/*   This code here would be preferable, but because of overriding rules with index, it doesn't work at the moment.
    static if (index < T.length)
    {
        pragma(msg, itoa(index));
        typeof(*this) opAssign(T[index] value)
        {
            _variant_data[index] = value;
            _variant_type = index;
            return *this;
        }
        mixin makeOpAssigns!(index + 1, T);
    }
*/

    static if (index == T.length)
        const char[] makeOpAssigns = "";
    else
    {
        const char[] makeOpAssigns = "    typeof(*this) opAssign(" ~ T[index].stringof ~ 
              " value) { _variant_data[" ~ itoa(index) ~ "] = value; _variant_type = " 
              ~ itoa(index) ~ "; return *this; }\n"
              ~ makeOpAssigns!(index + 1, T);
    }
}

template GenerateList(ulong index, T...)
{
    static if (T.length == 0)
        const char[] GenerateList = "";
    else
        const char[] GenerateList = T[0].stringof ~ " _variant_data[" ~ itoa(index) ~ "]; " ~ GenerateList!(index + 1, T[1..$]);
}

char[] itoa(ulong x)
{
    char[] s="";
    do {
        s = cast(char)('0' + (x%10)) ~ s;
        x /= 10;
    } while (x>0);
    return s;
}