libphobos/libdruntime/core/internal/switch_.d

   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 */
  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`.
  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 {
 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 */
 186 void __switch_error()(string file = __FILE__, size_t line = __LINE__)
 187 {
 188     import core.exception : __switch_errorT;
 189     __switch_errorT(file, line);
 190 }