switch_.d

/**
This module contains compiler support for switch...case statements

Copyright: Copyright Digital Mars 2000 - 2019.
License: Distributed under the
     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
   (See accompanying file LICENSE)
Source: $(DRUNTIMESRC core/internal/_switch_.d)
*/
module core.internal.switch_;

/**
Support for switch statements switching on strings.
Params:
    caseLabels = sorted array of strings generated by compiler. Note the
        strings are sorted by length first, and then lexicographically.
    condition = string to look up in table
Returns:
    index of match in caseLabels, a negative integer if not found
*/
int __switch(T, caseLabels...)(/*in*/ const scope T[] condition) pure nothrow @safe @nogc
{
    // This closes recursion for other cases.
    static if (caseLabels.length == 0)
    {
        return int.min;
    }
    else static if (caseLabels.length == 1)
    {
        return __cmp(condition, caseLabels[0]) == 0 ? 0 : int.min;
    }
    // To be adjusted after measurements
    // Compile-time inlined binary search.
    else static if (caseLabels.length < 7)
    {
        int r = void;
        enum mid = cast(int)caseLabels.length / 2;
        if (condition.length == caseLabels[mid].length)
        {
            r = __cmp(condition, caseLabels[mid]);
            if (r == 0) return mid;
        }
        else
        {
            // Equivalent to (but faster than) condition.length > caseLabels[$ / 2].length ? 1 : -1
            r = ((condition.length > caseLabels[mid].length) << 1) - 1;
        }

        if (r < 0)
        {
            // Search the left side
            return __switch!(T, caseLabels[0 .. mid])(condition);
        }
        else
        {
            // Search the right side
            return __switch!(T, caseLabels[mid + 1 .. $])(condition) + mid + 1;
        }
    }
    else
    {
        // Need immutable array to be accessible in pure code, but case labels are
        // currently coerced to the switch condition type (e.g. const(char)[]).
        static immutable T[][caseLabels.length] cases = {
            auto res = new immutable(T)[][](caseLabels.length);
            foreach (i, s; caseLabels)
                res[i] = s.idup;
            return res;
        }();

        // Run-time binary search in a static array of labels.
        return __switchSearch!T(cases[], condition);
    }
}

// binary search in sorted string cases, also see `__switch`.
private int __switchSearch(T)(/*in*/ const scope T[][] cases, /*in*/ const scope T[] condition) pure nothrow @safe @nogc
{
    size_t low = 0;
    size_t high = cases.length;

    do
    {
        auto mid = (low + high) / 2;
        int r = void;
        if (condition.length == cases[mid].length)
        {
            r = __cmp(condition, cases[mid]);
            if (r == 0) return cast(int) mid;
        }
        else
        {
            // Generates better code than "expr ? 1 : -1" on dmd and gdc, same with ldc
            r = ((condition.length > cases[mid].length) << 1) - 1;
        }

        if (r > 0) low = mid + 1;
        else high = mid;
    }
    while (low < high);

    // Not found
    return -1;
}

@system unittest
{
    static void testSwitch(T)()
    {
        switch (cast(T[]) "c")
        {
             case "coo":
             default:
                 break;
        }

        static int bug5381(immutable(T)[] s)
        {
            switch (s)
            {
                case "unittest":        return 1;
                case "D_Version2":      return 2;
                case "nonenone":        return 3;
                case "none":            return 4;
                case "all":             return 5;
                default:                return 6;
            }
        }

        int rc = bug5381("unittest");
        assert(rc == 1);

        rc = bug5381("D_Version2");
        assert(rc == 2);

        rc = bug5381("nonenone");
        assert(rc == 3);

        rc = bug5381("none");
        assert(rc == 4);

        rc = bug5381("all");
        assert(rc == 5);

        rc = bug5381("nonerandom");
        assert(rc == 6);

        static int binarySearch(immutable(T)[] s)
        {
            switch (s)
            {
                static foreach (i; 0 .. 16)
                case i.stringof: return i;
                default: return -1;
            }
        }
        static foreach (i; 0 .. 16)
            assert(binarySearch(i.stringof) == i);
        assert(binarySearch("") == -1);
        assert(binarySearch("sth.") == -1);
        assert(binarySearch(null) == -1);

        static int bug16739(immutable(T)[] s)
        {
            switch (s)
            {
                case "\u0100": return 1;
                case "a": return 2;
                default: return 3;
            }
        }
        assert(bug16739("\u0100") == 1);
        assert(bug16739("a") == 2);
        assert(bug16739("foo") == 3);
    }
    testSwitch!char;
    testSwitch!wchar;
    testSwitch!dchar;
}

/**
Compiler lowers final switch default case to this (which is a runtime error)
Old implementation is in core/exception.d
*/
void __switch_error()(string file = __FILE__, size_t line = __LINE__)
{
    import core.exception : __switch_errorT;
    __switch_errorT(file, line);
}