1/**
2This module contains compiler support for switch...case statements
3
4Copyright: Copyright Digital Mars 2000 - 2019.
5License: Distributed under the
6     $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
7   (See accompanying file LICENSE)
8Source: $(DRUNTIMESRC core/internal/_switch_.d)
9*/
10module core.internal.switch_;
11
12/**
13Support for switch statements switching on strings.
14Params:
15    caseLabels = sorted array of strings generated by compiler. Note the
16        strings are sorted by length first, and then lexicographically.
17    condition = string to look up in table
18Returns:
19    index of match in caseLabels, a negative integer if not found
20*/
21int __switch(T, caseLabels...)(/*in*/ const scope T[] condition) pure nothrow @safe @nogc
22{
23    // This closes recursion for other cases.
24    static if (caseLabels.length == 0)
25    {
26        return int.min;
27    }
28    else static if (caseLabels.length == 1)
29    {
30        return __cmp(condition, caseLabels[0]) == 0 ? 0 : int.min;
31    }
32    // To be adjusted after measurements
33    // Compile-time inlined binary search.
34    else static if (caseLabels.length < 7)
35    {
36        int r = void;
37        enum mid = cast(int)caseLabels.length / 2;
38        if (condition.length == caseLabels[mid].length)
39        {
40            r = __cmp(condition, caseLabels[mid]);
41            if (r == 0) return mid;
42        }
43        else
44        {
45            // Equivalent to (but faster than) condition.length > caseLabels[$ / 2].length ? 1 : -1
46            r = ((condition.length > caseLabels[mid].length) << 1) - 1;
47        }
48
49        if (r < 0)
50        {
51            // Search the left side
52            return __switch!(T, caseLabels[0 .. mid])(condition);
53        }
54        else
55        {
56            // Search the right side
57            return __switch!(T, caseLabels[mid + 1 .. $])(condition) + mid + 1;
58        }
59    }
60    else
61    {
62        // Need immutable array to be accessible in pure code, but case labels are
63        // currently coerced to the switch condition type (e.g. const(char)[]).
64        pure @trusted nothrow @nogc asImmutable(scope const(T[])[] items)
65        {
66            assert(__ctfe); // only @safe for CTFE
67            immutable T[][caseLabels.length] result = cast(immutable)(items[]);
68            return result;
69        }
70        static immutable T[][caseLabels.length] cases = asImmutable([caseLabels]);
71
72        // Run-time binary search in a static array of labels.
73        return __switchSearch!T(cases[], condition);
74    }
75}
76
77// binary search in sorted string cases, also see `__switch`.
78private int __switchSearch(T)(/*in*/ const scope T[][] cases, /*in*/ const scope T[] condition) pure nothrow @safe @nogc
79{
80    size_t low = 0;
81    size_t high = cases.length;
82
83    do
84    {
85        auto mid = (low + high) / 2;
86        int r = void;
87        if (condition.length == cases[mid].length)
88        {
89            r = __cmp(condition, cases[mid]);
90            if (r == 0) return cast(int) mid;
91        }
92        else
93        {
94            // Generates better code than "expr ? 1 : -1" on dmd and gdc, same with ldc
95            r = ((condition.length > cases[mid].length) << 1) - 1;
96        }
97
98        if (r > 0) low = mid + 1;
99        else high = mid;
100    }
101    while (low < high);
102
103    // Not found
104    return -1;
105}
106
107@system unittest
108{
109    static void testSwitch(T)()
110    {
111        switch (cast(T[]) "c")
112        {
113             case "coo":
114             default:
115                 break;
116        }
117
118        static int bug5381(immutable(T)[] s)
119        {
120            switch (s)
121            {
122                case "unittest":        return 1;
123                case "D_Version2":      return 2;
124                case "nonenone":        return 3;
125                case "none":            return 4;
126                case "all":             return 5;
127                default:                return 6;
128            }
129        }
130
131        int rc = bug5381("unittest");
132        assert(rc == 1);
133
134        rc = bug5381("D_Version2");
135        assert(rc == 2);
136
137        rc = bug5381("nonenone");
138        assert(rc == 3);
139
140        rc = bug5381("none");
141        assert(rc == 4);
142
143        rc = bug5381("all");
144        assert(rc == 5);
145
146        rc = bug5381("nonerandom");
147        assert(rc == 6);
148
149        static int binarySearch(immutable(T)[] s)
150        {
151            switch (s)
152            {
153                static foreach (i; 0 .. 16)
154                case i.stringof: return i;
155                default: return -1;
156            }
157        }
158        static foreach (i; 0 .. 16)
159            assert(binarySearch(i.stringof) == i);
160        assert(binarySearch("") == -1);
161        assert(binarySearch("sth.") == -1);
162        assert(binarySearch(null) == -1);
163
164        static int bug16739(immutable(T)[] s)
165        {
166            switch (s)
167            {
168                case "\u0100": return 1;
169                case "a": return 2;
170                default: return 3;
171            }
172        }
173        assert(bug16739("\u0100") == 1);
174        assert(bug16739("a") == 2);
175        assert(bug16739("foo") == 3);
176    }
177    testSwitch!char;
178    testSwitch!wchar;
179    testSwitch!dchar;
180}
181
182/**
183Compiler lowers final switch default case to this (which is a runtime error)
184Old implementation is in core/exception.d
185*/
186void __switch_error()(string file = __FILE__, size_t line = __LINE__)
187{
188    import core.exception : __switch_errorT;
189    __switch_errorT(file, line);
190}
191