1 /**
2 This module contains compiler support for switch...case statements
3
4 Copyright: Copyright Digital Mars 2000 - 2019.
5 License: Distributed under the
6 $(LINK2 http://www.boost.org/LICENSE_1_0.txt, Boost Software License 1.0).
7 (See accompanying file LICENSE)
8 Source: $(DRUNTIMESRC core/internal/_switch_.d)
9 */
10 module core.internal.switch_;
11
12 /**
13 Support for switch statements switching on strings.
14 Params:
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
18 Returns:
19 index of match in caseLabels, a negative integer if not found
20 */
__switch(T,caseLabels...)21 int __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`.
__switchSearch(T)78 private 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 {
testSwitch(T)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 /**
183 Compiler lowers final switch default case to this (which is a runtime error)
184 Old implementation is in core/exception.d
185 */
__switch_error()186 void __switch_error()(string file = __FILE__, size_t line = __LINE__)
187 {
188 import core.exception : __switch_errorT;
189 __switch_errorT(file, line);
190 }
191