dmd.intrange source code

1 /**
2  * Implement $(LINK2 https://digitalmars.com/articles/b62.html, Value Range Propagation).
3  *
4  * Copyright:   Copyright (C) 1999-2023 by The D Language Foundation, All Rights Reserved
5  * Authors:     $(LINK2 https://www.digitalmars.com, Walter Bright)
6  * License:     $(LINK2 https://www.boost.org/LICENSE_1_0.txt, Boost License 1.0)
7  * Source:      $(LINK2 https://github.com/dlang/dmd/blob/master/src/dmd/intrange.d, _intrange.d)
8  * Documentation:  https://dlang.org/phobos/dmd_intrange.html
9  * Coverage:    https://codecov.io/gh/dlang/dmd/src/master/src/dmd/intrange.d
10  */
11 
12 module dmd.intrange;
13 
14 import core.stdc.stdio;
15 
16 import dmd.astenums;
17 import dmd.mtype;
18 import dmd.expression;
19 import dmd.globals;
20 
21 private uinteger_t copySign(uinteger_t x, bool sign) @safe
22 {
23     // return sign ? -x : x;
24     return (x - cast(uinteger_t)sign) ^ -cast(uinteger_t)sign;
25 }
26 
27 struct SignExtendedNumber
28 {
29     uinteger_t value;
30     bool negative;
31 
32     static SignExtendedNumber fromInteger(uinteger_t value_) @safe
33     {
34         return SignExtendedNumber(value_, value_ >> 63);
35     }
36 
37     static SignExtendedNumber extreme(bool minimum) @safe
38     {
39         return SignExtendedNumber(minimum - 1, minimum);
40     }
41 
42     static SignExtendedNumber max() @safe
43     {
44         return SignExtendedNumber(ulong.max, false);
45     }
46 
47     static SignExtendedNumber min() @safe
48     {
49         return SignExtendedNumber(0, true);
50     }
51 
52     bool isMinimum() const @safe
53     {
54         return negative && value == 0;
55     }
56 
57     bool opEquals(const ref SignExtendedNumber a) const @safe
58     {
59         return value == a.value && negative == a.negative;
60     }
61 
62     int opCmp(const ref SignExtendedNumber a) const @safe
63     {
64         if (negative != a.negative)
65         {
66             if (negative)
67                 return -1;
68             else
69                 return 1;
70         }
71         if (value < a.value)
72             return -1;
73         else if (value > a.value)
74             return 1;
75         else
76             return 0;
77     }
78 
79     SignExtendedNumber opUnary(string op : "++")()
80     {
81         if (value != ulong.max)
82             ++value;
83         else if (negative)
84         {
85             value = 0;
86             negative = false;
87         }
88         return this;
89     }
90 
91     SignExtendedNumber opUnary(string op : "~")() const
92     {
93         if (~value == 0)
94             return SignExtendedNumber(~value);
95         else
96             return SignExtendedNumber(~value, !negative);
97     }
98 
99     SignExtendedNumber opUnary(string op : "-")() const
100     {
101         if (value == 0)
102             return SignExtendedNumber(-cast(ulong)negative);
103         else
104             return SignExtendedNumber(-value, !negative);
105     }
106 
107     SignExtendedNumber opBinary(string op : "&")(SignExtendedNumber rhs) const
108     {
109         return SignExtendedNumber(value & rhs.value);
110     }
111 
112     SignExtendedNumber opBinary(string op : "|")(SignExtendedNumber rhs)
113     {
114         return SignExtendedNumber(value | rhs.value);
115     }
116 
117     SignExtendedNumber opBinary(string op : "^")(SignExtendedNumber rhs)
118     {
119         return SignExtendedNumber(value ^ rhs.value);
120     }
121 
122     SignExtendedNumber opBinary(string op : "+")(SignExtendedNumber rhs)
123     {
124         uinteger_t sum = value + rhs.value;
125         bool carry = sum < value && sum < rhs.value;
126         if (negative != rhs.negative)
127             return SignExtendedNumber(sum, !carry);
128         else if (negative)
129             return SignExtendedNumber(carry ? sum : 0, true);
130         else
131             return SignExtendedNumber(carry ? ulong.max : sum, false);
132     }
133 
134 
135     SignExtendedNumber opBinary(string op : "-")(SignExtendedNumber rhs)
136     {
137         if (rhs.isMinimum())
138             return negative ? SignExtendedNumber(value, false) : max();
139         else
140             return this + (-rhs);
141     }
142 
143     SignExtendedNumber opBinary(string op : "*")(SignExtendedNumber rhs)
144     {
145         // perform *saturated* multiplication, otherwise we may get bogus ranges
146         //  like 0x10 * 0x10 == 0x100 == 0.
147 
148         /* Special handling for zeros:
149             INT65_MIN * 0 = 0
150             INT65_MIN * + = INT65_MIN
151             INT65_MIN * - = INT65_MAX
152             0 * anything = 0
153         */
154         if (value == 0)
155         {
156             if (!negative)
157                 return this;
158             else if (rhs.negative)
159                 return max();
160             else
161                 return rhs.value == 0 ? rhs : this;
162         }
163         else if (rhs.value == 0)
164             return rhs * this; // don't duplicate the symmetric case.
165 
166         SignExtendedNumber rv;
167         // these are != 0 now surely.
168         uinteger_t tAbs = copySign(value, negative);
169         uinteger_t aAbs = copySign(rhs.value, rhs.negative);
170         rv.negative = negative != rhs.negative;
171         if (ulong.max / tAbs < aAbs)
172             rv.value = rv.negative - 1;
173         else
174             rv.value = copySign(tAbs * aAbs, rv.negative);
175         return rv;
176     }
177 
178     SignExtendedNumber opBinary(string op : "/")(SignExtendedNumber rhs)
179     {
180         /* special handling for zeros:
181             INT65_MIN / INT65_MIN = 1
182             anything / INT65_MIN = 0
183             + / 0 = INT65_MAX  (eh?)
184             - / 0 = INT65_MIN  (eh?)
185         */
186         if (rhs.value == 0)
187         {
188             if (rhs.negative)
189                 return SignExtendedNumber(value == 0 && negative);
190             else
191                 return extreme(negative);
192         }
193 
194         uinteger_t aAbs = copySign(rhs.value, rhs.negative);
195         uinteger_t rvVal;
196 
197         if (!isMinimum())
198             rvVal = copySign(value, negative) / aAbs;
199         // Special handling for INT65_MIN
200         //  if the denominator is not a power of 2, it is same as ulong.max / x.
201         else if (aAbs & (aAbs - 1))
202             rvVal = ulong.max / aAbs;
203         // otherwise, it's the same as reversing the bits of x.
204         else
205         {
206             if (aAbs == 1)
207                 return extreme(!rhs.negative);
208             rvVal = 1UL << 63;
209             aAbs >>= 1;
210             if (aAbs & 0xAAAAAAAAAAAAAAAAUL) rvVal >>= 1;
211             if (aAbs & 0xCCCCCCCCCCCCCCCCUL) rvVal >>= 2;
212             if (aAbs & 0xF0F0F0F0F0F0F0F0UL) rvVal >>= 4;
213             if (aAbs & 0xFF00FF00FF00FF00UL) rvVal >>= 8;
214             if (aAbs & 0xFFFF0000FFFF0000UL) rvVal >>= 16;
215             if (aAbs & 0xFFFFFFFF00000000UL) rvVal >>= 32;
216         }
217         bool rvNeg = negative != rhs.negative;
218         rvVal = copySign(rvVal, rvNeg);
219 
220         return SignExtendedNumber(rvVal, rvVal != 0 && rvNeg);
221     }
222 
223     SignExtendedNumber opBinary(string op : "%")(SignExtendedNumber rhs)
224     {
225         if (rhs.value == 0)
226             return !rhs.negative ? rhs : isMinimum() ? SignExtendedNumber(0) : this;
227 
228         uinteger_t aAbs = copySign(rhs.value, rhs.negative);
229         uinteger_t rvVal;
230 
231         // a % b == sgn(a) * abs(a) % abs(b).
232         if (!isMinimum())
233             rvVal = copySign(value, negative) % aAbs;
234         // Special handling for INT65_MIN
235         //  if the denominator is not a power of 2, it is same as ulong.max % x + 1.
236         else if (aAbs & (aAbs - 1))
237             rvVal = ulong.max % aAbs + 1;
238         //  otherwise, the modulus is trivially zero.
239         else
240             rvVal = 0;
241 
242         rvVal = copySign(rvVal, negative);
243         return SignExtendedNumber(rvVal, rvVal != 0 && negative);
244     }
245 
246     SignExtendedNumber opBinary(string op : "<<")(SignExtendedNumber rhs)
247     {
248         // assume left-shift the shift-amount is always unsigned. Thus negative
249         //  shifts will give huge result.
250         if (value == 0)
251             return this;
252         else if (rhs.negative)
253             return extreme(negative);
254 
255         uinteger_t v = copySign(value, negative);
256 
257         // compute base-2 log of 'v' to determine the maximum allowed bits to shift.
258         // Ref: https://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
259 
260         // Why is this a size_t? Looks like a bug.
261         size_t r, s;
262 
263         r = (v > 0xFFFFFFFFUL) << 5; v >>= r;
264         s = (v > 0xFFFFUL    ) << 4; v >>= s; r |= s;
265         s = (v > 0xFFUL      ) << 3; v >>= s; r |= s;
266         s = (v > 0xFUL       ) << 2; v >>= s; r |= s;
267         s = (v > 0x3UL       ) << 1; v >>= s; r |= s;
268                                                r |= (v >> 1);
269 
270         uinteger_t allowableShift = 63 - r;
271         if (rhs.value > allowableShift)
272             return extreme(negative);
273         else
274             return SignExtendedNumber(value << rhs.value, negative);
275     }
276 
277     SignExtendedNumber opBinary(string op : ">>")(SignExtendedNumber rhs)
278     {
279         if (rhs.negative || rhs.value > 63)
280             return negative ? SignExtendedNumber(-1, true) : SignExtendedNumber(0);
281         else if (isMinimum())
282             return rhs.value == 0 ? this : SignExtendedNumber(-1UL << (64 - rhs.value), true);
283 
284         uinteger_t x = value ^ -cast(int)negative;
285         x >>= rhs.value;
286         return SignExtendedNumber(x ^ -cast(int)negative, negative);
287     }
288 
289     SignExtendedNumber opBinary(string op : "^^")(SignExtendedNumber rhs)
290     {
291         // Not yet implemented
292         assert(0);
293     }
294 }
295 
296 struct IntRange
297 {
298     SignExtendedNumber imin, imax;
299 
300     this(IntRange another) @safe
301     {
302         imin = another.imin;
303         imax = another.imax;
304     }
305 
306     this(SignExtendedNumber a) @safe
307     {
308         imin = a;
309         imax = a;
310     }
311 
312     this(SignExtendedNumber lower, SignExtendedNumber upper) @safe
313     {
314         imin = lower;
315         imax = upper;
316     }
317 
318     static IntRange fromType(Type type)
319     {
320         return fromType(type, type.isunsigned());
321     }
322 
323     static IntRange fromType(Type type, bool isUnsigned)
324     {
325         if (!type.isintegral() || type.toBasetype().ty == Tvector)
326             return widest();
327 
328         uinteger_t mask = type.sizemask();
329         auto lower = SignExtendedNumber(0);
330         auto upper = SignExtendedNumber(mask);
331         if (type.toBasetype().ty == Tdchar)
332             upper.value = 0x10FFFFUL;
333         else if (!isUnsigned)
334         {
335             lower.value = ~(mask >> 1);
336             lower.negative = true;
337             upper.value = (mask >> 1);
338         }
339         return IntRange(lower, upper);
340     }
341 
342     static IntRange fromNumbers2(SignExtendedNumber* numbers)
343     {
344         if (numbers[0] < numbers[1])
345             return IntRange(numbers[0], numbers[1]);
346         else
347             return IntRange(numbers[1], numbers[0]);
348     }
349 
350     static IntRange fromNumbers4(SignExtendedNumber* numbers)
351     {
352         IntRange ab = fromNumbers2(numbers);
353         IntRange cd = fromNumbers2(numbers + 2);
354         if (cd.imin < ab.imin)
355             ab.imin = cd.imin;
356         if (cd.imax > ab.imax)
357             ab.imax = cd.imax;
358         return ab;
359     }
360 
361     static IntRange widest() @safe
362     {
363         return IntRange(SignExtendedNumber.min(), SignExtendedNumber.max());
364     }
365 
366     IntRange castSigned(uinteger_t mask) @safe
367     {
368         // .... 0x1e7f ] [0x1e80 .. 0x1f7f] [0x1f80 .. 0x7f] [0x80 .. 0x17f] [0x180 ....
369         //
370         // regular signed type. We use a technique similar to the unsigned version,
371         //  but the chunk has to be offset by 1/2 of the range.
372         uinteger_t halfChunkMask = mask >> 1;
373         uinteger_t minHalfChunk = imin.value & ~halfChunkMask;
374         uinteger_t maxHalfChunk = imax.value & ~halfChunkMask;
375         int minHalfChunkNegativity = imin.negative; // 1 = neg, 0 = nonneg, -1 = chunk containing ::max
376         int maxHalfChunkNegativity = imax.negative;
377         if (minHalfChunk & mask)
378         {
379             minHalfChunk += halfChunkMask + 1;
380             if (minHalfChunk == 0)
381                 --minHalfChunkNegativity;
382         }
383         if (maxHalfChunk & mask)
384         {
385             maxHalfChunk += halfChunkMask + 1;
386             if (maxHalfChunk == 0)
387                 --maxHalfChunkNegativity;
388         }
389         if (minHalfChunk == maxHalfChunk && minHalfChunkNegativity == maxHalfChunkNegativity)
390         {
391             imin.value &= mask;
392             imax.value &= mask;
393             // sign extend if necessary.
394             imin.negative = (imin.value & ~halfChunkMask) != 0;
395             imax.negative = (imax.value & ~halfChunkMask) != 0;
396             halfChunkMask += 1;
397             imin.value = (imin.value ^ halfChunkMask) - halfChunkMask;
398             imax.value = (imax.value ^ halfChunkMask) - halfChunkMask;
399         }
400         else
401         {
402             imin = SignExtendedNumber(~halfChunkMask, true);
403             imax = SignExtendedNumber(halfChunkMask, false);
404         }
405         return this;
406     }
407 
408     IntRange castUnsigned(uinteger_t mask) @safe
409     {
410         // .... 0x1eff ] [0x1f00 .. 0x1fff] [0 .. 0xff] [0x100 .. 0x1ff] [0x200 ....
411         //
412         // regular unsigned type. We just need to see if ir steps across the
413         //  boundary of validRange. If yes, ir will represent the whole validRange,
414         //  otherwise, we just take the modulus.
415         // e.g. [0x105, 0x107] & 0xff == [5, 7]
416         //      [0x105, 0x207] & 0xff == [0, 0xff]
417         uinteger_t minChunk = imin.value & ~mask;
418         uinteger_t maxChunk = imax.value & ~mask;
419         if (minChunk == maxChunk && imin.negative == imax.negative)
420         {
421             imin.value &= mask;
422             imax.value &= mask;
423         }
424         else
425         {
426             imin.value = 0;
427             imax.value = mask;
428         }
429         imin.negative = imax.negative = false;
430         return this;
431     }
432 
433     IntRange castDchar() @safe
434     {
435         // special case for dchar. Casting to dchar means "I'll ignore all
436         //  invalid characters."
437         castUnsigned(0xFFFFFFFFUL);
438         if (imin.value > 0x10FFFFUL) // ??
439             imin.value = 0x10FFFFUL; // ??
440         if (imax.value > 0x10FFFFUL)
441             imax.value = 0x10FFFFUL;
442         return this;
443     }
444 
445     IntRange _cast(Type type)
446     {
447         if (!type.isintegral() || type.toBasetype().ty == Tvector)
448             return this;
449         else if (!type.isunsigned())
450             return castSigned(type.sizemask());
451         else if (type.toBasetype().ty == Tdchar)
452             return castDchar();
453         else
454             return castUnsigned(type.sizemask());
455     }
456 
457     IntRange castUnsigned(Type type)
458     {
459         if (!type.isintegral() || type.toBasetype().ty == Tvector)
460             return castUnsigned(ulong.max);
461         else if (type.toBasetype().ty == Tdchar)
462             return castDchar();
463         else
464             return castUnsigned(type.sizemask());
465     }
466 
467     bool contains(IntRange a) @safe
468     {
469         return imin <= a.imin && imax >= a.imax;
470     }
471 
472     bool containsZero() const @safe
473     {
474         return (imin.negative && !imax.negative)
475             || (!imin.negative && imin.value == 0);
476     }
477 
478     IntRange absNeg() const @safe
479     {
480         if (imax.negative)
481             return this;
482         else if (!imin.negative)
483             return IntRange(-imax, -imin);
484         else
485         {
486             SignExtendedNumber imaxAbsNeg = -imax;
487             return IntRange(imaxAbsNeg < imin ? imaxAbsNeg : imin,
488                             SignExtendedNumber(0));
489         }
490     }
491 
492     IntRange unionWith(const ref IntRange other) const @safe
493     {
494         return IntRange(imin < other.imin ? imin : other.imin,
495                         imax > other.imax ? imax : other.imax);
496     }
497 
498     void unionOrAssign(IntRange other, ref bool union_) @safe
499     {
500         if (!union_ || imin > other.imin)
501             imin = other.imin;
502         if (!union_ || imax < other.imax)
503             imax = other.imax;
504         union_ = true;
505     }
506 
507     ref const(IntRange) dump(const(char)* funcName, Expression e) const return
508     {
509         printf("[(%c)%#018llx, (%c)%#018llx] @ %s ::: %s\n",
510                imin.negative?'-':'+', cast(ulong)imin.value,
511                imax.negative?'-':'+', cast(ulong)imax.value,
512                funcName, e.toChars());
513         return this;
514     }
515 
516     void splitBySign(ref IntRange negRange, ref bool hasNegRange, ref IntRange nonNegRange, ref bool hasNonNegRange) const @safe
517     {
518         hasNegRange = imin.negative;
519         if (hasNegRange)
520         {
521             negRange.imin = imin;
522             negRange.imax = imax.negative ? imax : SignExtendedNumber(-1, true);
523         }
524         hasNonNegRange = !imax.negative;
525         if (hasNonNegRange)
526         {
527             nonNegRange.imin = imin.negative ? SignExtendedNumber(0) : imin;
528             nonNegRange.imax = imax;
529         }
530     }
531 
532     IntRange opUnary(string op:"~")() const
533     {
534         return IntRange(~imax, ~imin);
535     }
536 
537     IntRange opUnary(string op : "-")()
538     {
539         return IntRange(-imax, -imin);
540     }
541 
542     // Credits to Timon Gehr for the algorithms for &, |
543     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
544     IntRange opBinary(string op : "&")(IntRange rhs) const
545     {
546         // unsigned or identical sign bits
547         if ((imin.negative ^ imax.negative) != 1 && (rhs.imin.negative ^ rhs.imax.negative) != 1)
548         {
549             return IntRange(minAnd(this, rhs), maxAnd(this, rhs));
550         }
551 
552         IntRange l = IntRange(this);
553         IntRange r = IntRange(rhs);
554 
555         // both intervals span [-1,0]
556         if ((imin.negative ^ imax.negative) == 1 && (rhs.imin.negative ^ rhs.imax.negative) == 1)
557         {
558             // cannot be larger than either l.max or r.max, set the other one to -1
559             SignExtendedNumber max = l.imax.value > r.imax.value ? l.imax : r.imax;
560 
561             // only negative numbers for minimum
562             l.imax.value = -1;
563             l.imax.negative = true;
564             r.imax.value = -1;
565             r.imax.negative = true;
566 
567             return IntRange(minAnd(l, r), max);
568         }
569         else
570         {
571             // only one interval spans [-1,0]
572             if ((l.imin.negative ^ l.imax.negative) == 1)
573             {
574                 swap(l, r); // r spans [-1,0]
575             }
576 
577             auto minAndNeg = minAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
578             auto minAndPos = minAnd(l, IntRange(SignExtendedNumber(0), r.imax));
579             auto maxAndNeg = maxAnd(l, IntRange(r.imin, SignExtendedNumber(-1)));
580             auto maxAndPos = maxAnd(l, IntRange(SignExtendedNumber(0), r.imax));
581 
582             auto min = minAndNeg < minAndPos ? minAndNeg : minAndPos;
583             auto max = maxAndNeg > maxAndPos ? maxAndNeg : maxAndPos;
584 
585             auto range = IntRange(min, max);
586             return range;
587         }
588     }
589 
590     // Credits to Timon Gehr for the algorithms for &, |
591     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
592     IntRange opBinary(string op : "|")(IntRange rhs) const
593     {
594         // unsigned or identical sign bits:
595         if ((imin.negative ^ imax.negative) == 0 && (rhs.imin.negative ^ rhs.imax.negative) == 0)
596         {
597             return IntRange(minOr(this, rhs), maxOr(this, rhs));
598         }
599 
600         IntRange l = IntRange(this);
601         IntRange r = IntRange(rhs);
602 
603         // both intervals span [-1,0]
604         if ((imin.negative ^ imax.negative) == 1 && (rhs.imin.negative ^ rhs.imax.negative) == 1)
605         {
606             // cannot be smaller than either l.min or r.min, set the other one to 0
607             SignExtendedNumber min = l.imin.value < r.imin.value ? l.imin : r.imin;
608 
609             // only negative numbers for minimum
610             l.imin.value = 0;
611             l.imin.negative = false;
612             r.imin.value = 0;
613             r.imin.negative = false;
614 
615             return IntRange(min, maxOr(l, r));
616         }
617         else
618         {
619             // only one interval spans [-1,0]
620             if ((imin.negative ^ imax.negative) == 1)
621             {
622                 swap(l, r); // r spans [-1,0]
623             }
624 
625             auto minOrNeg = minOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
626             auto minOrPos = minOr(l, IntRange(SignExtendedNumber(0), r.imax));
627             auto maxOrNeg = maxOr(l, IntRange(r.imin, SignExtendedNumber(-1)));
628             auto maxOrPos = maxOr(l, IntRange(SignExtendedNumber(0), r.imax));
629 
630             auto min = minOrNeg < minOrPos ? minOrNeg : minOrPos;
631             auto max = maxOrNeg > maxOrPos ? maxOrNeg : maxOrPos;
632 
633             auto range = IntRange(min, max);
634             return range;
635         }
636     }
637 
638     IntRange opBinary(string op : "^")(IntRange rhs) const
639     {
640         return this & ~rhs | ~this & rhs;
641     }
642 
643     IntRange opBinary(string op : "+")(IntRange rhs)
644     {
645         return IntRange(imin + rhs.imin, imax + rhs.imax);
646     }
647 
648     IntRange opBinary(string op : "-")(IntRange rhs)
649     {
650         return IntRange(imin - rhs.imax, imax - rhs.imin);
651     }
652 
653     IntRange opBinary(string op : "*")(IntRange rhs)
654     {
655         // [a,b] * [c,d] = [min (ac, ad, bc, bd), max (ac, ad, bc, bd)]
656         SignExtendedNumber[4] bdy;
657         bdy[0] = imin * rhs.imin;
658         bdy[1] = imin * rhs.imax;
659         bdy[2] = imax * rhs.imin;
660         bdy[3] = imax * rhs.imax;
661         return IntRange.fromNumbers4(bdy.ptr);
662     }
663 
664     IntRange opBinary(string op : "/")(IntRange rhs)
665     {
666         // Handle divide by 0
667         if (rhs.imax.value == 0 && rhs.imin.value == 0)
668             return widest();
669 
670         // Don't treat the whole range as divide by 0 if only one end of a range is 0.
671         // Issue 15289
672         if (rhs.imax.value == 0)
673         {
674             rhs.imax.value--;
675         }
676         else if(rhs.imin.value == 0)
677         {
678             rhs.imin.value++;
679         }
680 
681         if (!imin.negative && !imax.negative && !rhs.imin.negative && !rhs.imax.negative)
682         {
683             return IntRange(imin / rhs.imax, imax / rhs.imin);
684         }
685         else
686         {
687             // [a,b] / [c,d] = [min (a/c, a/d, b/c, b/d), max (a/c, a/d, b/c, b/d)]
688             SignExtendedNumber[4] bdy;
689             bdy[0] = imin / rhs.imin;
690             bdy[1] = imin / rhs.imax;
691             bdy[2] = imax / rhs.imin;
692             bdy[3] = imax / rhs.imax;
693 
694             return IntRange.fromNumbers4(bdy.ptr);
695         }
696     }
697 
698     IntRange opBinary(string op : "%")(IntRange rhs)
699     {
700         IntRange irNum = this;
701         IntRange irDen = rhs.absNeg();
702 
703         /*
704          due to the rules of D (C)'s % operator, we need to consider the cases
705          separately in different range of signs.
706 
707              case 1. [500, 1700] % [7, 23] (numerator is always positive)
708                  = [0, 22]
709              case 2. [-500, 1700] % [7, 23] (numerator can be negative)
710                  = [-22, 22]
711              case 3. [-1700, -500] % [7, 23] (numerator is always negative)
712                  = [-22, 0]
713 
714          the number 22 is the maximum absolute value in the denomator's range. We
715          don't care about divide by zero.
716          */
717 
718         irDen.imin = irDen.imin + SignExtendedNumber(1);
719         irDen.imax = -irDen.imin;
720 
721         if (!irNum.imin.negative)
722         {
723             irNum.imin.value = 0;
724         }
725         else if (irNum.imin < irDen.imin)
726         {
727             irNum.imin = irDen.imin;
728         }
729 
730         if (irNum.imax.negative)
731         {
732             irNum.imax.negative = false;
733             irNum.imax.value = 0;
734         }
735         else if (irNum.imax > irDen.imax)
736         {
737             irNum.imax = irDen.imax;
738         }
739 
740         return irNum;
741     }
742 
743     IntRange opBinary(string op : "<<")(IntRange rhs)
744     {
745         if (rhs.imin.negative)
746         {
747             rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
748         }
749 
750         SignExtendedNumber lower = imin << (imin.negative ? rhs.imax : rhs.imin);
751         SignExtendedNumber upper = imax << (imax.negative ? rhs.imin : rhs.imax);
752 
753         return IntRange(lower, upper);
754     }
755 
756     IntRange opBinary(string op : ">>")(IntRange rhs)
757     {
758         if (rhs.imin.negative)
759         {
760             rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
761         }
762 
763         SignExtendedNumber lower = imin >> (imin.negative ? rhs.imin : rhs.imax);
764         SignExtendedNumber upper = imax >> (imax.negative ? rhs.imax : rhs.imin);
765 
766         return IntRange(lower, upper);
767     }
768 
769     IntRange opBinary(string op : ">>>")(IntRange rhs)
770     {
771         if (rhs.imin.negative)
772         {
773             rhs = IntRange(SignExtendedNumber(0), SignExtendedNumber(64));
774         }
775 
776         return IntRange(imin >> rhs.imax, imax >> rhs.imin);
777     }
778 
779     IntRange opBinary(string op : "^^")(IntRange rhs)
780     {
781         // Not yet implemented
782         assert(0);
783     }
784 
785 private:
786     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
787     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
788     static SignExtendedNumber maxOr(const IntRange lhs, const IntRange rhs) @safe
789     {
790         uinteger_t x = 0;
791         auto sign = false;
792         auto xor = lhs.imax.value ^ rhs.imax.value;
793         auto and = lhs.imax.value & rhs.imax.value;
794         auto lhsc = IntRange(lhs);
795         auto rhsc = IntRange(rhs);
796 
797         // Sign bit not part of the .value so we need an extra iteration
798         if (lhsc.imax.negative ^ rhsc.imax.negative)
799         {
800             sign = true;
801             if (lhsc.imax.negative)
802             {
803                 if (!lhsc.imin.negative)
804                 {
805                     lhsc.imin.value = 0;
806                 }
807                 if (!rhsc.imin.negative)
808                 {
809                     rhsc.imin.value = 0;
810                 }
811             }
812         }
813         else if (lhsc.imin.negative & rhsc.imin.negative)
814         {
815             sign = true;
816         }
817         else if (lhsc.imax.negative & rhsc.imax.negative)
818         {
819             return SignExtendedNumber(-1, false);
820         }
821 
822         for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
823         {
824             if (xor & d)
825             {
826                 x |= d;
827                 if (lhsc.imax.value & d)
828                 {
829                     if (~lhsc.imin.value & d)
830                     {
831                         lhsc.imin.value = 0;
832                     }
833                 }
834                 else
835                 {
836                     if (~rhsc.imin.value & d)
837                     {
838                         rhsc.imin.value = 0;
839                     }
840                 }
841             }
842             else if (lhsc.imin.value & rhsc.imin.value & d)
843             {
844                 x |= d;
845             }
846             else if (and & d)
847             {
848                 x |= (d << 1) - 1;
849                 break;
850             }
851         }
852 
853         auto range = SignExtendedNumber(x, sign);
854         return range;
855     }
856 
857     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
858     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
859     static SignExtendedNumber minOr(const IntRange lhs, const IntRange rhs) @safe
860     {
861         return ~maxAnd(~lhs, ~rhs);
862     }
863 
864     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
865     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
866     static SignExtendedNumber maxAnd(const IntRange lhs, const IntRange rhs) @safe
867     {
868         uinteger_t x = 0;
869         bool sign = false;
870         auto lhsc = IntRange(lhs);
871         auto rhsc = IntRange(rhs);
872 
873         if (lhsc.imax.negative & rhsc.imax.negative)
874         {
875             sign = true;
876         }
877 
878         for (uinteger_t d = 1LU << (8 * uinteger_t.sizeof - 1); d; d >>= 1)
879         {
880             if (lhsc.imax.value & rhsc.imax.value & d)
881             {
882                 x |= d;
883                 if (~lhsc.imin.value & d)
884                 {
885                     lhsc.imin.value = 0;
886                 }
887                 if (~rhsc.imin.value & d)
888                 {
889                     rhsc.imin.value = 0;
890                 }
891             }
892             else if (~lhsc.imin.value & d && lhsc.imax.value & d)
893             {
894                 lhsc.imax.value |= d - 1;
895             }
896             else if (~rhsc.imin.value & d && rhsc.imax.value & d)
897             {
898                 rhsc.imax.value |= d - 1;
899             }
900         }
901 
902         auto range = SignExtendedNumber(x, sign);
903         return range;
904     }
905 
906     // Credits to Timon Gehr maxOr, minOr, maxAnd, minAnd
907     // https://github.com/tgehr/d-compiler/blob/master/vrange.d
908     static SignExtendedNumber minAnd(const IntRange lhs, const IntRange rhs) @safe
909     {
910         return ~maxOr(~lhs, ~rhs);
911     }
912 
913     static swap(ref IntRange a, ref IntRange b)
914     {
915         auto aux = a;
916         a = b;
917         b = aux;
918     }
919 }