1 | // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors |
2 | // Licensed under the MIT License: |
3 | // |
4 | // Permission is hereby granted, free of charge, to any person obtaining a copy |
5 | // of this software and associated documentation files (the "Software"), to deal |
6 | // in the Software without restriction, including without limitation the rights |
7 | // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell |
8 | // copies of the Software, and to permit persons to whom the Software is |
9 | // furnished to do so, subject to the following conditions: |
10 | // |
11 | // The above copyright notice and this permission notice shall be included in |
12 | // all copies or substantial portions of the Software. |
13 | // |
14 | // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
15 | // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
16 | // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
17 | // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
18 | // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, |
19 | // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN |
20 | // THE SOFTWARE. |
21 | |
22 | // This file contains types which are intended to help detect incorrect usage at compile |
23 | // time, but should then be optimized down to basic primitives (usually, integers) by the |
24 | // compiler. |
25 | |
26 | #pragma once |
27 | |
28 | #if defined(__GNUC__) && !KJ_HEADER_WARNINGS |
29 | #pragma GCC system_header |
30 | #endif |
31 | |
32 | #include "common.h" |
33 | #include <inttypes.h> |
34 | |
35 | namespace kj { |
36 | |
37 | // ======================================================================================= |
38 | // IDs |
39 | |
40 | template <typename UnderlyingType, typename Label> |
41 | struct Id { |
42 | // A type-safe numeric ID. `UnderlyingType` is the underlying integer representation. `Label` |
43 | // distinguishes this Id from other Id types. Sample usage: |
44 | // |
45 | // class Foo; |
46 | // typedef Id<uint, Foo> FooId; |
47 | // |
48 | // class Bar; |
49 | // typedef Id<uint, Bar> BarId; |
50 | // |
51 | // You can now use the FooId and BarId types without any possibility of accidentally using a |
52 | // FooId when you really wanted a BarId or vice-versa. |
53 | |
54 | UnderlyingType value; |
55 | |
56 | inline constexpr Id(): value(0) {} |
57 | inline constexpr explicit Id(int value): value(value) {} |
58 | |
59 | inline constexpr bool operator==(const Id& other) const { return value == other.value; } |
60 | inline constexpr bool operator!=(const Id& other) const { return value != other.value; } |
61 | inline constexpr bool operator<=(const Id& other) const { return value <= other.value; } |
62 | inline constexpr bool operator>=(const Id& other) const { return value >= other.value; } |
63 | inline constexpr bool operator< (const Id& other) const { return value < other.value; } |
64 | inline constexpr bool operator> (const Id& other) const { return value > other.value; } |
65 | }; |
66 | |
67 | // ======================================================================================= |
68 | // Quantity and UnitRatio -- implement unit analysis via the type system |
69 | |
70 | struct Unsafe_ {}; |
71 | constexpr Unsafe_ unsafe = Unsafe_(); |
72 | // Use as a parameter to constructors that are unsafe to indicate that you really do mean it. |
73 | |
74 | template <uint64_t maxN, typename T> |
75 | class Bounded; |
76 | template <uint value> |
77 | class BoundedConst; |
78 | |
79 | template <typename T> constexpr bool isIntegral() { return false; } |
80 | template <> constexpr bool isIntegral<char>() { return true; } |
81 | template <> constexpr bool isIntegral<signed char>() { return true; } |
82 | template <> constexpr bool isIntegral<short>() { return true; } |
83 | template <> constexpr bool isIntegral<int>() { return true; } |
84 | template <> constexpr bool isIntegral<long>() { return true; } |
85 | template <> constexpr bool isIntegral<long long>() { return true; } |
86 | template <> constexpr bool isIntegral<unsigned char>() { return true; } |
87 | template <> constexpr bool isIntegral<unsigned short>() { return true; } |
88 | template <> constexpr bool isIntegral<unsigned int>() { return true; } |
89 | template <> constexpr bool isIntegral<unsigned long>() { return true; } |
90 | template <> constexpr bool isIntegral<unsigned long long>() { return true; } |
91 | |
92 | template <typename T> |
93 | struct IsIntegralOrBounded_ { static constexpr bool value = isIntegral<T>(); }; |
94 | template <uint64_t m, typename T> |
95 | struct IsIntegralOrBounded_<Bounded<m, T>> { static constexpr bool value = true; }; |
96 | template <uint v> |
97 | struct IsIntegralOrBounded_<BoundedConst<v>> { static constexpr bool value = true; }; |
98 | |
99 | template <typename T> |
100 | inline constexpr bool isIntegralOrBounded() { return IsIntegralOrBounded_<T>::value; } |
101 | |
102 | template <typename Number, typename Unit1, typename Unit2> |
103 | class UnitRatio { |
104 | // A multiplier used to convert Quantities of one unit to Quantities of another unit. See |
105 | // Quantity, below. |
106 | // |
107 | // Construct this type by dividing one Quantity by another of a different unit. Use this type |
108 | // by multiplying it by a Quantity, or dividing a Quantity by it. |
109 | |
110 | static_assert(isIntegralOrBounded<Number>(), |
111 | "Underlying type for UnitRatio must be integer." ); |
112 | |
113 | public: |
114 | inline UnitRatio() {} |
115 | |
116 | constexpr UnitRatio(Number unit1PerUnit2, decltype(unsafe)): unit1PerUnit2(unit1PerUnit2) {} |
117 | // This constructor was intended to be private, but GCC complains about it being private in a |
118 | // bunch of places that don't appear to even call it, so I made it public. Oh well. |
119 | |
120 | template <typename OtherNumber> |
121 | inline constexpr UnitRatio(const UnitRatio<OtherNumber, Unit1, Unit2>& other) |
122 | : unit1PerUnit2(other.unit1PerUnit2) {} |
123 | |
124 | template <typename OtherNumber> |
125 | inline constexpr UnitRatio<decltype(Number()+OtherNumber()), Unit1, Unit2> |
126 | operator+(UnitRatio<OtherNumber, Unit1, Unit2> other) const { |
127 | return UnitRatio<decltype(Number()+OtherNumber()), Unit1, Unit2>( |
128 | unit1PerUnit2 + other.unit1PerUnit2, unsafe); |
129 | } |
130 | template <typename OtherNumber> |
131 | inline constexpr UnitRatio<decltype(Number()-OtherNumber()), Unit1, Unit2> |
132 | operator-(UnitRatio<OtherNumber, Unit1, Unit2> other) const { |
133 | return UnitRatio<decltype(Number()-OtherNumber()), Unit1, Unit2>( |
134 | unit1PerUnit2 - other.unit1PerUnit2, unsafe); |
135 | } |
136 | |
137 | template <typename OtherNumber, typename Unit3> |
138 | inline constexpr UnitRatio<decltype(Number()*OtherNumber()), Unit3, Unit2> |
139 | operator*(UnitRatio<OtherNumber, Unit3, Unit1> other) const { |
140 | // U1 / U2 * U3 / U1 = U3 / U2 |
141 | return UnitRatio<decltype(Number()*OtherNumber()), Unit3, Unit2>( |
142 | unit1PerUnit2 * other.unit1PerUnit2, unsafe); |
143 | } |
144 | template <typename OtherNumber, typename Unit3> |
145 | inline constexpr UnitRatio<decltype(Number()*OtherNumber()), Unit1, Unit3> |
146 | operator*(UnitRatio<OtherNumber, Unit2, Unit3> other) const { |
147 | // U1 / U2 * U2 / U3 = U1 / U3 |
148 | return UnitRatio<decltype(Number()*OtherNumber()), Unit1, Unit3>( |
149 | unit1PerUnit2 * other.unit1PerUnit2, unsafe); |
150 | } |
151 | |
152 | template <typename OtherNumber, typename Unit3> |
153 | inline constexpr UnitRatio<decltype(Number()*OtherNumber()), Unit3, Unit2> |
154 | operator/(UnitRatio<OtherNumber, Unit1, Unit3> other) const { |
155 | // (U1 / U2) / (U1 / U3) = U3 / U2 |
156 | return UnitRatio<decltype(Number()*OtherNumber()), Unit3, Unit2>( |
157 | unit1PerUnit2 / other.unit1PerUnit2, unsafe); |
158 | } |
159 | template <typename OtherNumber, typename Unit3> |
160 | inline constexpr UnitRatio<decltype(Number()*OtherNumber()), Unit1, Unit3> |
161 | operator/(UnitRatio<OtherNumber, Unit3, Unit2> other) const { |
162 | // (U1 / U2) / (U3 / U2) = U1 / U3 |
163 | return UnitRatio<decltype(Number()*OtherNumber()), Unit1, Unit3>( |
164 | unit1PerUnit2 / other.unit1PerUnit2, unsafe); |
165 | } |
166 | |
167 | template <typename OtherNumber> |
168 | inline decltype(Number() / OtherNumber()) |
169 | operator/(UnitRatio<OtherNumber, Unit1, Unit2> other) const { |
170 | return unit1PerUnit2 / other.unit1PerUnit2; |
171 | } |
172 | |
173 | inline bool operator==(UnitRatio other) const { return unit1PerUnit2 == other.unit1PerUnit2; } |
174 | inline bool operator!=(UnitRatio other) const { return unit1PerUnit2 != other.unit1PerUnit2; } |
175 | |
176 | private: |
177 | Number unit1PerUnit2; |
178 | |
179 | template <typename OtherNumber, typename OtherUnit> |
180 | friend class Quantity; |
181 | template <typename OtherNumber, typename OtherUnit1, typename OtherUnit2> |
182 | friend class UnitRatio; |
183 | |
184 | template <typename N1, typename N2, typename U1, typename U2, typename> |
185 | friend inline constexpr UnitRatio<decltype(N1() * N2()), U1, U2> |
186 | operator*(N1, UnitRatio<N2, U1, U2>); |
187 | }; |
188 | |
189 | template <typename N1, typename N2, typename U1, typename U2, |
190 | typename = EnableIf<isIntegralOrBounded<N1>() && isIntegralOrBounded<N2>()>> |
191 | inline constexpr UnitRatio<decltype(N1() * N2()), U1, U2> |
192 | operator*(N1 n, UnitRatio<N2, U1, U2> r) { |
193 | return UnitRatio<decltype(N1() * N2()), U1, U2>(n * r.unit1PerUnit2, unsafe); |
194 | } |
195 | |
196 | template <typename Number, typename Unit> |
197 | class Quantity { |
198 | // A type-safe numeric quantity, specified in terms of some unit. Two Quantities cannot be used |
199 | // in arithmetic unless they use the same unit. The `Unit` type parameter is only used to prevent |
200 | // accidental mixing of units; this type is never instantiated and can very well be incomplete. |
201 | // `Number` is the underlying primitive numeric type. |
202 | // |
203 | // Quantities support most basic arithmetic operators, intelligently handling units, and |
204 | // automatically casting the underlying type in the same way that the compiler would. |
205 | // |
206 | // To convert a primitive number to a Quantity, multiply it by unit<Quantity<N, U>>(). |
207 | // To convert a Quantity to a primitive number, divide it by unit<Quantity<N, U>>(). |
208 | // To convert a Quantity of one unit to another unit, multiply or divide by a UnitRatio. |
209 | // |
210 | // The Quantity class is not well-suited to hardcore physics as it does not allow multiplying |
211 | // one quantity by another. For example, multiplying meters by meters won't get you square |
212 | // meters; it will get you a compiler error. It would be interesting to see if template |
213 | // metaprogramming could properly deal with such things but this isn't needed for the present |
214 | // use case. |
215 | // |
216 | // Sample usage: |
217 | // |
218 | // class SecondsLabel; |
219 | // typedef Quantity<double, SecondsLabel> Seconds; |
220 | // constexpr Seconds SECONDS = unit<Seconds>(); |
221 | // |
222 | // class MinutesLabel; |
223 | // typedef Quantity<double, MinutesLabel> Minutes; |
224 | // constexpr Minutes MINUTES = unit<Minutes>(); |
225 | // |
226 | // constexpr UnitRatio<double, SecondsLabel, MinutesLabel> SECONDS_PER_MINUTE = |
227 | // 60 * SECONDS / MINUTES; |
228 | // |
229 | // void waitFor(Seconds seconds) { |
230 | // sleep(seconds / SECONDS); |
231 | // } |
232 | // void waitFor(Minutes minutes) { |
233 | // waitFor(minutes * SECONDS_PER_MINUTE); |
234 | // } |
235 | // |
236 | // void waitThreeMinutes() { |
237 | // waitFor(3 * MINUTES); |
238 | // } |
239 | |
240 | static_assert(isIntegralOrBounded<Number>(), |
241 | "Underlying type for Quantity must be integer." ); |
242 | |
243 | public: |
244 | inline constexpr Quantity() = default; |
245 | |
246 | inline constexpr Quantity(MaxValue_): value(maxValue) {} |
247 | inline constexpr Quantity(MinValue_): value(minValue) {} |
248 | // Allow initialization from maxValue and minValue. |
249 | // TODO(msvc): decltype(maxValue) and decltype(minValue) deduce unknown-type for these function |
250 | // parameters, causing the compiler to complain of a duplicate constructor definition, so we |
251 | // specify MaxValue_ and MinValue_ types explicitly. |
252 | |
253 | inline constexpr Quantity(Number value, decltype(unsafe)): value(value) {} |
254 | // This constructor was intended to be private, but GCC complains about it being private in a |
255 | // bunch of places that don't appear to even call it, so I made it public. Oh well. |
256 | |
257 | template <typename OtherNumber> |
258 | inline constexpr Quantity(const Quantity<OtherNumber, Unit>& other) |
259 | : value(other.value) {} |
260 | |
261 | template <typename OtherNumber> |
262 | inline Quantity& operator=(const Quantity<OtherNumber, Unit>& other) { |
263 | value = other.value; |
264 | return *this; |
265 | } |
266 | |
267 | template <typename OtherNumber> |
268 | inline constexpr Quantity<decltype(Number() + OtherNumber()), Unit> |
269 | operator+(const Quantity<OtherNumber, Unit>& other) const { |
270 | return Quantity<decltype(Number() + OtherNumber()), Unit>(value + other.value, unsafe); |
271 | } |
272 | template <typename OtherNumber> |
273 | inline constexpr Quantity<decltype(Number() - OtherNumber()), Unit> |
274 | operator-(const Quantity<OtherNumber, Unit>& other) const { |
275 | return Quantity<decltype(Number() - OtherNumber()), Unit>(value - other.value, unsafe); |
276 | } |
277 | template <typename OtherNumber, typename = EnableIf<isIntegralOrBounded<OtherNumber>()>> |
278 | inline constexpr Quantity<decltype(Number() * OtherNumber()), Unit> |
279 | operator*(OtherNumber other) const { |
280 | return Quantity<decltype(Number() * other), Unit>(value * other, unsafe); |
281 | } |
282 | template <typename OtherNumber, typename = EnableIf<isIntegralOrBounded<OtherNumber>()>> |
283 | inline constexpr Quantity<decltype(Number() / OtherNumber()), Unit> |
284 | operator/(OtherNumber other) const { |
285 | return Quantity<decltype(Number() / other), Unit>(value / other, unsafe); |
286 | } |
287 | template <typename OtherNumber> |
288 | inline constexpr decltype(Number() / OtherNumber()) |
289 | operator/(const Quantity<OtherNumber, Unit>& other) const { |
290 | return value / other.value; |
291 | } |
292 | template <typename OtherNumber> |
293 | inline constexpr Quantity<decltype(Number() % OtherNumber()), Unit> |
294 | operator%(const Quantity<OtherNumber, Unit>& other) const { |
295 | return Quantity<decltype(Number() % OtherNumber()), Unit>(value % other.value, unsafe); |
296 | } |
297 | |
298 | template <typename OtherNumber, typename OtherUnit> |
299 | inline constexpr Quantity<decltype(Number() * OtherNumber()), OtherUnit> |
300 | operator*(UnitRatio<OtherNumber, OtherUnit, Unit> ratio) const { |
301 | return Quantity<decltype(Number() * OtherNumber()), OtherUnit>( |
302 | value * ratio.unit1PerUnit2, unsafe); |
303 | } |
304 | template <typename OtherNumber, typename OtherUnit> |
305 | inline constexpr Quantity<decltype(Number() / OtherNumber()), OtherUnit> |
306 | operator/(UnitRatio<OtherNumber, Unit, OtherUnit> ratio) const { |
307 | return Quantity<decltype(Number() / OtherNumber()), OtherUnit>( |
308 | value / ratio.unit1PerUnit2, unsafe); |
309 | } |
310 | template <typename OtherNumber, typename OtherUnit> |
311 | inline constexpr Quantity<decltype(Number() % OtherNumber()), Unit> |
312 | operator%(UnitRatio<OtherNumber, Unit, OtherUnit> ratio) const { |
313 | return Quantity<decltype(Number() % OtherNumber()), Unit>( |
314 | value % ratio.unit1PerUnit2, unsafe); |
315 | } |
316 | template <typename OtherNumber, typename OtherUnit> |
317 | inline constexpr UnitRatio<decltype(Number() / OtherNumber()), Unit, OtherUnit> |
318 | operator/(Quantity<OtherNumber, OtherUnit> other) const { |
319 | return UnitRatio<decltype(Number() / OtherNumber()), Unit, OtherUnit>( |
320 | value / other.value, unsafe); |
321 | } |
322 | |
323 | template <typename OtherNumber> |
324 | inline constexpr bool operator==(const Quantity<OtherNumber, Unit>& other) const { |
325 | return value == other.value; |
326 | } |
327 | template <typename OtherNumber> |
328 | inline constexpr bool operator!=(const Quantity<OtherNumber, Unit>& other) const { |
329 | return value != other.value; |
330 | } |
331 | template <typename OtherNumber> |
332 | inline constexpr bool operator<=(const Quantity<OtherNumber, Unit>& other) const { |
333 | return value <= other.value; |
334 | } |
335 | template <typename OtherNumber> |
336 | inline constexpr bool operator>=(const Quantity<OtherNumber, Unit>& other) const { |
337 | return value >= other.value; |
338 | } |
339 | template <typename OtherNumber> |
340 | inline constexpr bool operator<(const Quantity<OtherNumber, Unit>& other) const { |
341 | return value < other.value; |
342 | } |
343 | template <typename OtherNumber> |
344 | inline constexpr bool operator>(const Quantity<OtherNumber, Unit>& other) const { |
345 | return value > other.value; |
346 | } |
347 | |
348 | template <typename OtherNumber> |
349 | inline Quantity& operator+=(const Quantity<OtherNumber, Unit>& other) { |
350 | value += other.value; |
351 | return *this; |
352 | } |
353 | template <typename OtherNumber> |
354 | inline Quantity& operator-=(const Quantity<OtherNumber, Unit>& other) { |
355 | value -= other.value; |
356 | return *this; |
357 | } |
358 | template <typename OtherNumber> |
359 | inline Quantity& operator*=(OtherNumber other) { |
360 | value *= other; |
361 | return *this; |
362 | } |
363 | template <typename OtherNumber> |
364 | inline Quantity& operator/=(OtherNumber other) { |
365 | value /= other.value; |
366 | return *this; |
367 | } |
368 | |
369 | private: |
370 | Number value; |
371 | |
372 | template <typename OtherNumber, typename OtherUnit> |
373 | friend class Quantity; |
374 | |
375 | template <typename Number1, typename Number2, typename Unit2> |
376 | friend inline constexpr auto operator*(Number1 a, Quantity<Number2, Unit2> b) |
377 | -> Quantity<decltype(Number1() * Number2()), Unit2>; |
378 | }; |
379 | |
380 | template <typename T> struct Unit_ { |
381 | static inline constexpr T get() { return T(1); } |
382 | }; |
383 | template <typename T, typename U> |
384 | struct Unit_<Quantity<T, U>> { |
385 | static inline constexpr Quantity<decltype(Unit_<T>::get()), U> get() { |
386 | return Quantity<decltype(Unit_<T>::get()), U>(Unit_<T>::get(), unsafe); |
387 | } |
388 | }; |
389 | |
390 | template <typename T> |
391 | inline constexpr auto unit() -> decltype(Unit_<T>::get()) { return Unit_<T>::get(); } |
392 | // unit<Quantity<T, U>>() returns a Quantity of value 1. It also, intentionally, works on basic |
393 | // numeric types. |
394 | |
395 | template <typename Number1, typename Number2, typename Unit> |
396 | inline constexpr auto operator*(Number1 a, Quantity<Number2, Unit> b) |
397 | -> Quantity<decltype(Number1() * Number2()), Unit> { |
398 | return Quantity<decltype(Number1() * Number2()), Unit>(a * b.value, unsafe); |
399 | } |
400 | |
401 | template <typename Number1, typename Number2, typename Unit, typename Unit2> |
402 | inline constexpr auto operator*(UnitRatio<Number1, Unit2, Unit> ratio, |
403 | Quantity<Number2, Unit> measure) |
404 | -> decltype(measure * ratio) { |
405 | return measure * ratio; |
406 | } |
407 | |
408 | // ======================================================================================= |
409 | // Absolute measures |
410 | |
411 | template <typename T, typename Label> |
412 | class Absolute { |
413 | // Wraps some other value -- typically a Quantity -- but represents a value measured based on |
414 | // some absolute origin. For example, if `Duration` is a type representing a time duration, |
415 | // Absolute<Duration, UnixEpoch> might be a calendar date. |
416 | // |
417 | // Since Absolute represents measurements relative to some arbitrary origin, the only sensible |
418 | // arithmetic to perform on them is addition and subtraction. |
419 | |
420 | // TODO(someday): Do the same automatic expansion of integer width that Quantity does? Doesn't |
421 | // matter for our time use case, where we always use 64-bit anyway. Note that fixing this |
422 | // would implicitly allow things like multiplying an Absolute by a UnitRatio to change its |
423 | // units, which is actually totally logical and kind of neat. |
424 | |
425 | public: |
426 | inline constexpr Absolute operator+(const T& other) const { return Absolute(value + other); } |
427 | inline constexpr Absolute operator-(const T& other) const { return Absolute(value - other); } |
428 | inline constexpr T operator-(const Absolute& other) const { return value - other.value; } |
429 | |
430 | inline Absolute& operator+=(const T& other) { value += other; return *this; } |
431 | inline Absolute& operator-=(const T& other) { value -= other; return *this; } |
432 | |
433 | inline constexpr bool operator==(const Absolute& other) const { return value == other.value; } |
434 | inline constexpr bool operator!=(const Absolute& other) const { return value != other.value; } |
435 | inline constexpr bool operator<=(const Absolute& other) const { return value <= other.value; } |
436 | inline constexpr bool operator>=(const Absolute& other) const { return value >= other.value; } |
437 | inline constexpr bool operator< (const Absolute& other) const { return value < other.value; } |
438 | inline constexpr bool operator> (const Absolute& other) const { return value > other.value; } |
439 | |
440 | private: |
441 | T value; |
442 | |
443 | explicit constexpr Absolute(T value): value(value) {} |
444 | |
445 | template <typename U> |
446 | friend inline constexpr U origin(); |
447 | }; |
448 | |
449 | template <typename T, typename Label> |
450 | inline constexpr Absolute<T, Label> operator+(const T& a, const Absolute<T, Label>& b) { |
451 | return b + a; |
452 | } |
453 | |
454 | template <typename T> struct UnitOf_ { typedef T Type; }; |
455 | template <typename T, typename Label> struct UnitOf_<Absolute<T, Label>> { typedef T Type; }; |
456 | template <typename T> |
457 | using UnitOf = typename UnitOf_<T>::Type; |
458 | // UnitOf<Absolute<T, U>> is T. UnitOf<AnythingElse> is AnythingElse. |
459 | |
460 | template <typename T> |
461 | inline constexpr T origin() { return T(0 * unit<UnitOf<T>>()); } |
462 | // origin<Absolute<T, U>>() returns an Absolute of value 0. It also, intentionally, works on basic |
463 | // numeric types. |
464 | |
465 | // ======================================================================================= |
466 | // Overflow avoidance |
467 | |
468 | template <uint64_t n, uint accum = 0> |
469 | struct BitCount_ { |
470 | static constexpr uint value = BitCount_<(n >> 1), accum + 1>::value; |
471 | }; |
472 | template <uint accum> |
473 | struct BitCount_<0, accum> { |
474 | static constexpr uint value = accum; |
475 | }; |
476 | |
477 | template <uint64_t n> |
478 | inline constexpr uint bitCount() { return BitCount_<n>::value; } |
479 | // Number of bits required to represent the number `n`. |
480 | |
481 | template <uint bitCountBitCount> struct AtLeastUInt_ { |
482 | static_assert(bitCountBitCount < 7, "don't know how to represent integers over 64 bits" ); |
483 | }; |
484 | template <> struct AtLeastUInt_<0> { typedef uint8_t Type; }; |
485 | template <> struct AtLeastUInt_<1> { typedef uint8_t Type; }; |
486 | template <> struct AtLeastUInt_<2> { typedef uint8_t Type; }; |
487 | template <> struct AtLeastUInt_<3> { typedef uint8_t Type; }; |
488 | template <> struct AtLeastUInt_<4> { typedef uint16_t Type; }; |
489 | template <> struct AtLeastUInt_<5> { typedef uint32_t Type; }; |
490 | template <> struct AtLeastUInt_<6> { typedef uint64_t Type; }; |
491 | |
492 | template <uint bits> |
493 | using AtLeastUInt = typename AtLeastUInt_<bitCount<max(bits, 1) - 1>()>::Type; |
494 | // AtLeastUInt<n> is an unsigned integer of at least n bits. E.g. AtLeastUInt<12> is uint16_t. |
495 | |
496 | // ------------------------------------------------------------------- |
497 | |
498 | template <uint value> |
499 | class BoundedConst { |
500 | // A constant integer value on which we can do bit size analysis. |
501 | |
502 | public: |
503 | BoundedConst() = default; |
504 | |
505 | inline constexpr uint unwrap() const { return value; } |
506 | |
507 | #define OP(op, check) \ |
508 | template <uint other> \ |
509 | inline constexpr BoundedConst<(value op other)> \ |
510 | operator op(BoundedConst<other>) const { \ |
511 | static_assert(check, "overflow in BoundedConst arithmetic"); \ |
512 | return BoundedConst<(value op other)>(); \ |
513 | } |
514 | #define COMPARE_OP(op) \ |
515 | template <uint other> \ |
516 | inline constexpr bool operator op(BoundedConst<other>) const { \ |
517 | return value op other; \ |
518 | } |
519 | |
520 | OP(+, value + other >= value) |
521 | OP(-, value - other <= value) |
522 | OP(*, value * other / other == value) |
523 | OP(/, true) // div by zero already errors out; no other division ever overflows |
524 | OP(%, true) // mod by zero already errors out; no other modulus ever overflows |
525 | OP(<<, value << other >= value) |
526 | OP(>>, true) // right shift can't overflow |
527 | OP(&, true) // bitwise ops can't overflow |
528 | OP(|, true) // bitwise ops can't overflow |
529 | |
530 | COMPARE_OP(==) |
531 | COMPARE_OP(!=) |
532 | COMPARE_OP(< ) |
533 | COMPARE_OP(> ) |
534 | COMPARE_OP(<=) |
535 | COMPARE_OP(>=) |
536 | #undef OP |
537 | #undef COMPARE_OP |
538 | }; |
539 | |
540 | template <uint64_t m, typename T> |
541 | struct Unit_<Bounded<m, T>> { |
542 | static inline constexpr BoundedConst<1> get() { return BoundedConst<1>(); } |
543 | }; |
544 | |
545 | template <uint value> |
546 | struct Unit_<BoundedConst<value>> { |
547 | static inline constexpr BoundedConst<1> get() { return BoundedConst<1>(); } |
548 | }; |
549 | |
550 | template <uint value> |
551 | inline constexpr BoundedConst<value> bounded() { |
552 | return BoundedConst<value>(); |
553 | } |
554 | |
555 | template <uint64_t a, uint64_t b> |
556 | static constexpr uint64_t boundedAdd() { |
557 | static_assert(a + b >= a, "possible overflow detected" ); |
558 | return a + b; |
559 | } |
560 | template <uint64_t a, uint64_t b> |
561 | static constexpr uint64_t boundedSub() { |
562 | static_assert(a - b <= a, "possible underflow detected" ); |
563 | return a - b; |
564 | } |
565 | template <uint64_t a, uint64_t b> |
566 | static constexpr uint64_t boundedMul() { |
567 | static_assert(a * b / b == a, "possible overflow detected" ); |
568 | return a * b; |
569 | } |
570 | template <uint64_t a, uint64_t b> |
571 | static constexpr uint64_t boundedLShift() { |
572 | static_assert(a << b >= a, "possible overflow detected" ); |
573 | return a << b; |
574 | } |
575 | |
576 | template <uint a, uint b> |
577 | inline constexpr BoundedConst<kj::min(a, b)> min(BoundedConst<a>, BoundedConst<b>) { |
578 | return bounded<kj::min(a, b)>(); |
579 | } |
580 | template <uint a, uint b> |
581 | inline constexpr BoundedConst<kj::max(a, b)> max(BoundedConst<a>, BoundedConst<b>) { |
582 | return bounded<kj::max(a, b)>(); |
583 | } |
584 | // We need to override min() and max() between constants because the ternary operator in the |
585 | // default implementation would complain. |
586 | |
587 | // ------------------------------------------------------------------- |
588 | |
589 | template <uint64_t maxN, typename T> |
590 | class Bounded { |
591 | public: |
592 | static_assert(maxN <= T(kj::maxValue), "possible overflow detected" ); |
593 | |
594 | Bounded() = default; |
595 | |
596 | Bounded(const Bounded& other) = default; |
597 | template <typename OtherInt, typename = EnableIf<isIntegral<OtherInt>()>> |
598 | inline constexpr Bounded(OtherInt value): value(value) { |
599 | static_assert(OtherInt(maxValue) <= maxN, "possible overflow detected" ); |
600 | } |
601 | template <uint64_t otherMax, typename OtherT> |
602 | inline constexpr Bounded(const Bounded<otherMax, OtherT>& other) |
603 | : value(other.value) { |
604 | static_assert(otherMax <= maxN, "possible overflow detected" ); |
605 | } |
606 | template <uint otherValue> |
607 | inline constexpr Bounded(BoundedConst<otherValue>) |
608 | : value(otherValue) { |
609 | static_assert(otherValue <= maxN, "overflow detected" ); |
610 | } |
611 | |
612 | Bounded& operator=(const Bounded& other) = default; |
613 | template <typename OtherInt, typename = EnableIf<isIntegral<OtherInt>()>> |
614 | Bounded& operator=(OtherInt other) { |
615 | static_assert(OtherInt(maxValue) <= maxN, "possible overflow detected" ); |
616 | value = other; |
617 | return *this; |
618 | } |
619 | template <uint64_t otherMax, typename OtherT> |
620 | inline Bounded& operator=(const Bounded<otherMax, OtherT>& other) { |
621 | static_assert(otherMax <= maxN, "possible overflow detected" ); |
622 | value = other.value; |
623 | return *this; |
624 | } |
625 | template <uint otherValue> |
626 | inline Bounded& operator=(BoundedConst<otherValue>) { |
627 | static_assert(otherValue <= maxN, "overflow detected" ); |
628 | value = otherValue; |
629 | return *this; |
630 | } |
631 | |
632 | inline constexpr T unwrap() const { return value; } |
633 | |
634 | #define OP(op, newMax) \ |
635 | template <uint64_t otherMax, typename otherT> \ |
636 | inline constexpr Bounded<newMax, decltype(T() op otherT())> \ |
637 | operator op(const Bounded<otherMax, otherT>& other) const { \ |
638 | return Bounded<newMax, decltype(T() op otherT())>(value op other.value, unsafe); \ |
639 | } |
640 | #define COMPARE_OP(op) \ |
641 | template <uint64_t otherMax, typename OtherT> \ |
642 | inline constexpr bool operator op(const Bounded<otherMax, OtherT>& other) const { \ |
643 | return value op other.value; \ |
644 | } |
645 | |
646 | OP(+, (boundedAdd<maxN, otherMax>())) |
647 | OP(*, (boundedMul<maxN, otherMax>())) |
648 | OP(/, maxN) |
649 | OP(%, otherMax - 1) |
650 | |
651 | // operator- is intentionally omitted because we mostly use this with unsigned types, and |
652 | // subtraction requires proof that subtrahend is not greater than the minuend. |
653 | |
654 | COMPARE_OP(==) |
655 | COMPARE_OP(!=) |
656 | COMPARE_OP(< ) |
657 | COMPARE_OP(> ) |
658 | COMPARE_OP(<=) |
659 | COMPARE_OP(>=) |
660 | |
661 | #undef OP |
662 | #undef COMPARE_OP |
663 | |
664 | template <uint64_t newMax, typename ErrorFunc> |
665 | inline Bounded<newMax, T> assertMax(ErrorFunc&& func) const { |
666 | // Assert that the number is no more than `newMax`. Otherwise, call `func`. |
667 | static_assert(newMax < maxN, "this bounded size assertion is redundant" ); |
668 | if (KJ_UNLIKELY(value > newMax)) func(); |
669 | return Bounded<newMax, T>(value, unsafe); |
670 | } |
671 | |
672 | template <uint64_t otherMax, typename OtherT, typename ErrorFunc> |
673 | inline Bounded<maxN, decltype(T() - OtherT())> subtractChecked( |
674 | const Bounded<otherMax, OtherT>& other, ErrorFunc&& func) const { |
675 | // Subtract a number, calling func() if the result would underflow. |
676 | if (KJ_UNLIKELY(value < other.value)) func(); |
677 | return Bounded<maxN, decltype(T() - OtherT())>(value - other.value, unsafe); |
678 | } |
679 | |
680 | template <uint otherValue, typename ErrorFunc> |
681 | inline Bounded<maxN - otherValue, T> subtractChecked( |
682 | BoundedConst<otherValue>, ErrorFunc&& func) const { |
683 | // Subtract a number, calling func() if the result would underflow. |
684 | static_assert(otherValue <= maxN, "underflow detected" ); |
685 | if (KJ_UNLIKELY(value < otherValue)) func(); |
686 | return Bounded<maxN - otherValue, T>(value - otherValue, unsafe); |
687 | } |
688 | |
689 | template <uint64_t otherMax, typename OtherT> |
690 | inline Maybe<Bounded<maxN, decltype(T() - OtherT())>> trySubtract( |
691 | const Bounded<otherMax, OtherT>& other) const { |
692 | // Subtract a number, calling func() if the result would underflow. |
693 | if (value < other.value) { |
694 | return nullptr; |
695 | } else { |
696 | return Bounded<maxN, decltype(T() - OtherT())>(value - other.value, unsafe); |
697 | } |
698 | } |
699 | |
700 | template <uint otherValue> |
701 | inline Maybe<Bounded<maxN - otherValue, T>> trySubtract(BoundedConst<otherValue>) const { |
702 | // Subtract a number, calling func() if the result would underflow. |
703 | if (value < otherValue) { |
704 | return nullptr; |
705 | } else { |
706 | return Bounded<maxN - otherValue, T>(value - otherValue, unsafe); |
707 | } |
708 | } |
709 | |
710 | inline constexpr Bounded(T value, decltype(unsafe)): value(value) {} |
711 | template <uint64_t otherMax, typename OtherT> |
712 | inline constexpr Bounded(Bounded<otherMax, OtherT> value, decltype(unsafe)) |
713 | : value(value.value) {} |
714 | // Mainly for internal use. |
715 | // |
716 | // Only use these as a last resort, with ample commentary on why you think it's safe. |
717 | |
718 | private: |
719 | T value; |
720 | |
721 | template <uint64_t, typename> |
722 | friend class Bounded; |
723 | }; |
724 | |
725 | template <typename Number> |
726 | inline constexpr Bounded<Number(kj::maxValue), Number> bounded(Number value) { |
727 | return Bounded<Number(kj::maxValue), Number>(value, unsafe); |
728 | } |
729 | |
730 | inline constexpr Bounded<1, uint8_t> bounded(bool value) { |
731 | return Bounded<1, uint8_t>(value, unsafe); |
732 | } |
733 | |
734 | template <uint bits, typename Number> |
735 | inline constexpr Bounded<maxValueForBits<bits>(), Number> assumeBits(Number value) { |
736 | return Bounded<maxValueForBits<bits>(), Number>(value, unsafe); |
737 | } |
738 | |
739 | template <uint bits, uint64_t maxN, typename T> |
740 | inline constexpr Bounded<maxValueForBits<bits>(), T> assumeBits(Bounded<maxN, T> value) { |
741 | return Bounded<maxValueForBits<bits>(), T>(value, unsafe); |
742 | } |
743 | |
744 | template <uint bits, typename Number, typename Unit> |
745 | inline constexpr auto assumeBits(Quantity<Number, Unit> value) |
746 | -> Quantity<decltype(assumeBits<bits>(value / unit<Quantity<Number, Unit>>())), Unit> { |
747 | return Quantity<decltype(assumeBits<bits>(value / unit<Quantity<Number, Unit>>())), Unit>( |
748 | assumeBits<bits>(value / unit<Quantity<Number, Unit>>()), unsafe); |
749 | } |
750 | |
751 | template <uint64_t maxN, typename Number> |
752 | inline constexpr Bounded<maxN, Number> assumeMax(Number value) { |
753 | return Bounded<maxN, Number>(value, unsafe); |
754 | } |
755 | |
756 | template <uint64_t newMaxN, uint64_t maxN, typename T> |
757 | inline constexpr Bounded<newMaxN, T> assumeMax(Bounded<maxN, T> value) { |
758 | return Bounded<newMaxN, T>(value, unsafe); |
759 | } |
760 | |
761 | template <uint64_t maxN, typename Number, typename Unit> |
762 | inline constexpr auto assumeMax(Quantity<Number, Unit> value) |
763 | -> Quantity<decltype(assumeMax<maxN>(value / unit<Quantity<Number, Unit>>())), Unit> { |
764 | return Quantity<decltype(assumeMax<maxN>(value / unit<Quantity<Number, Unit>>())), Unit>( |
765 | assumeMax<maxN>(value / unit<Quantity<Number, Unit>>()), unsafe); |
766 | } |
767 | |
768 | template <uint maxN, typename Number> |
769 | inline constexpr Bounded<maxN, Number> assumeMax(BoundedConst<maxN>, Number value) { |
770 | return assumeMax<maxN>(value); |
771 | } |
772 | |
773 | template <uint newMaxN, uint64_t maxN, typename T> |
774 | inline constexpr Bounded<newMaxN, T> assumeMax(BoundedConst<maxN>, Bounded<maxN, T> value) { |
775 | return assumeMax<maxN>(value); |
776 | } |
777 | |
778 | template <uint maxN, typename Number, typename Unit> |
779 | inline constexpr auto assumeMax(Quantity<BoundedConst<maxN>, Unit>, Quantity<Number, Unit> value) |
780 | -> decltype(assumeMax<maxN>(value)) { |
781 | return assumeMax<maxN>(value); |
782 | } |
783 | |
784 | template <uint64_t newMax, uint64_t maxN, typename T, typename ErrorFunc> |
785 | inline Bounded<newMax, T> assertMax(Bounded<maxN, T> value, ErrorFunc&& errorFunc) { |
786 | // Assert that the bounded value is less than or equal to the given maximum, calling errorFunc() |
787 | // if not. |
788 | static_assert(newMax < maxN, "this bounded size assertion is redundant" ); |
789 | return value.template assertMax<newMax>(kj::fwd<ErrorFunc>(errorFunc)); |
790 | } |
791 | |
792 | template <uint64_t newMax, uint64_t maxN, typename T, typename Unit, typename ErrorFunc> |
793 | inline Quantity<Bounded<newMax, T>, Unit> assertMax( |
794 | Quantity<Bounded<maxN, T>, Unit> value, ErrorFunc&& errorFunc) { |
795 | // Assert that the bounded value is less than or equal to the given maximum, calling errorFunc() |
796 | // if not. |
797 | static_assert(newMax < maxN, "this bounded size assertion is redundant" ); |
798 | return (value / unit<decltype(value)>()).template assertMax<newMax>( |
799 | kj::fwd<ErrorFunc>(errorFunc)) * unit<decltype(value)>(); |
800 | } |
801 | |
802 | template <uint newMax, uint64_t maxN, typename T, typename ErrorFunc> |
803 | inline Bounded<newMax, T> assertMax( |
804 | BoundedConst<newMax>, Bounded<maxN, T> value, ErrorFunc&& errorFunc) { |
805 | return assertMax<newMax>(value, kj::mv(errorFunc)); |
806 | } |
807 | |
808 | template <uint newMax, uint64_t maxN, typename T, typename Unit, typename ErrorFunc> |
809 | inline Quantity<Bounded<newMax, T>, Unit> assertMax( |
810 | Quantity<BoundedConst<newMax>, Unit>, |
811 | Quantity<Bounded<maxN, T>, Unit> value, ErrorFunc&& errorFunc) { |
812 | return assertMax<newMax>(value, kj::mv(errorFunc)); |
813 | } |
814 | |
815 | template <uint64_t newBits, uint64_t maxN, typename T, typename ErrorFunc = ThrowOverflow> |
816 | inline Bounded<maxValueForBits<newBits>(), T> assertMaxBits( |
817 | Bounded<maxN, T> value, ErrorFunc&& errorFunc = ErrorFunc()) { |
818 | // Assert that the bounded value requires no more than the given number of bits, calling |
819 | // errorFunc() if not. |
820 | return assertMax<maxValueForBits<newBits>()>(value, kj::fwd<ErrorFunc>(errorFunc)); |
821 | } |
822 | |
823 | template <uint64_t newBits, uint64_t maxN, typename T, typename Unit, |
824 | typename ErrorFunc = ThrowOverflow> |
825 | inline Quantity<Bounded<maxValueForBits<newBits>(), T>, Unit> assertMaxBits( |
826 | Quantity<Bounded<maxN, T>, Unit> value, ErrorFunc&& errorFunc = ErrorFunc()) { |
827 | // Assert that the bounded value requires no more than the given number of bits, calling |
828 | // errorFunc() if not. |
829 | return assertMax<maxValueForBits<newBits>()>(value, kj::fwd<ErrorFunc>(errorFunc)); |
830 | } |
831 | |
832 | template <typename newT, uint64_t maxN, typename T> |
833 | inline constexpr Bounded<maxN, newT> upgradeBound(Bounded<maxN, T> value) { |
834 | return value; |
835 | } |
836 | |
837 | template <typename newT, uint64_t maxN, typename T, typename Unit> |
838 | inline constexpr Quantity<Bounded<maxN, newT>, Unit> upgradeBound( |
839 | Quantity<Bounded<maxN, T>, Unit> value) { |
840 | return value; |
841 | } |
842 | |
843 | template <uint64_t maxN, typename T, typename Other, typename ErrorFunc> |
844 | inline auto subtractChecked(Bounded<maxN, T> value, Other other, ErrorFunc&& errorFunc) |
845 | -> decltype(value.subtractChecked(other, kj::fwd<ErrorFunc>(errorFunc))) { |
846 | return value.subtractChecked(other, kj::fwd<ErrorFunc>(errorFunc)); |
847 | } |
848 | |
849 | template <typename T, typename U, typename Unit, typename ErrorFunc> |
850 | inline auto subtractChecked(Quantity<T, Unit> value, Quantity<U, Unit> other, ErrorFunc&& errorFunc) |
851 | -> Quantity<decltype(subtractChecked(T(), U(), kj::fwd<ErrorFunc>(errorFunc))), Unit> { |
852 | return subtractChecked(value / unit<Quantity<T, Unit>>(), |
853 | other / unit<Quantity<U, Unit>>(), |
854 | kj::fwd<ErrorFunc>(errorFunc)) |
855 | * unit<Quantity<T, Unit>>(); |
856 | } |
857 | |
858 | template <uint64_t maxN, typename T, typename Other> |
859 | inline auto trySubtract(Bounded<maxN, T> value, Other other) |
860 | -> decltype(value.trySubtract(other)) { |
861 | return value.trySubtract(other); |
862 | } |
863 | |
864 | template <typename T, typename U, typename Unit> |
865 | inline auto trySubtract(Quantity<T, Unit> value, Quantity<U, Unit> other) |
866 | -> Maybe<Quantity<decltype(subtractChecked(T(), U(), int())), Unit>> { |
867 | return trySubtract(value / unit<Quantity<T, Unit>>(), |
868 | other / unit<Quantity<U, Unit>>()) |
869 | .map([](decltype(subtractChecked(T(), U(), int())) x) { |
870 | return x * unit<Quantity<T, Unit>>(); |
871 | }); |
872 | } |
873 | |
874 | template <uint64_t aN, uint64_t bN, typename A, typename B> |
875 | inline constexpr Bounded<kj::min(aN, bN), WiderType<A, B>> |
876 | min(Bounded<aN, A> a, Bounded<bN, B> b) { |
877 | return Bounded<kj::min(aN, bN), WiderType<A, B>>(kj::min(a.unwrap(), b.unwrap()), unsafe); |
878 | } |
879 | template <uint64_t aN, uint64_t bN, typename A, typename B> |
880 | inline constexpr Bounded<kj::max(aN, bN), WiderType<A, B>> |
881 | max(Bounded<aN, A> a, Bounded<bN, B> b) { |
882 | return Bounded<kj::max(aN, bN), WiderType<A, B>>(kj::max(a.unwrap(), b.unwrap()), unsafe); |
883 | } |
884 | // We need to override min() and max() because: |
885 | // 1) WiderType<> might not choose the correct bounds. |
886 | // 2) One of the two sides of the ternary operator in the default implementation would fail to |
887 | // typecheck even though it is OK in practice. |
888 | |
889 | // ------------------------------------------------------------------- |
890 | // Operators between Bounded and BoundedConst |
891 | |
892 | #define OP(op, newMax) \ |
893 | template <uint64_t maxN, uint cvalue, typename T> \ |
894 | inline constexpr Bounded<(newMax), decltype(T() op uint())> operator op( \ |
895 | Bounded<maxN, T> value, BoundedConst<cvalue>) { \ |
896 | return Bounded<(newMax), decltype(T() op uint())>(value.unwrap() op cvalue, unsafe); \ |
897 | } |
898 | |
899 | #define REVERSE_OP(op, newMax) \ |
900 | template <uint64_t maxN, uint cvalue, typename T> \ |
901 | inline constexpr Bounded<(newMax), decltype(uint() op T())> operator op( \ |
902 | BoundedConst<cvalue>, Bounded<maxN, T> value) { \ |
903 | return Bounded<(newMax), decltype(uint() op T())>(cvalue op value.unwrap(), unsafe); \ |
904 | } |
905 | |
906 | #define COMPARE_OP(op) \ |
907 | template <uint64_t maxN, uint cvalue, typename T> \ |
908 | inline constexpr bool operator op(Bounded<maxN, T> value, BoundedConst<cvalue>) { \ |
909 | return value.unwrap() op cvalue; \ |
910 | } \ |
911 | template <uint64_t maxN, uint cvalue, typename T> \ |
912 | inline constexpr bool operator op(BoundedConst<cvalue>, Bounded<maxN, T> value) { \ |
913 | return cvalue op value.unwrap(); \ |
914 | } |
915 | |
916 | OP(+, (boundedAdd<maxN, cvalue>())) |
917 | REVERSE_OP(+, (boundedAdd<maxN, cvalue>())) |
918 | |
919 | OP(*, (boundedMul<maxN, cvalue>())) |
920 | REVERSE_OP(*, (boundedAdd<maxN, cvalue>())) |
921 | |
922 | OP(/, maxN / cvalue) |
923 | REVERSE_OP(/, cvalue) // denominator could be 1 |
924 | |
925 | OP(%, cvalue - 1) |
926 | REVERSE_OP(%, maxN - 1) |
927 | |
928 | OP(<<, (boundedLShift<maxN, cvalue>())) |
929 | REVERSE_OP(<<, (boundedLShift<cvalue, maxN>())) |
930 | |
931 | OP(>>, maxN >> cvalue) |
932 | REVERSE_OP(>>, cvalue >> maxN) |
933 | |
934 | OP(&, maxValueForBits<bitCount<maxN>()>() & cvalue) |
935 | REVERSE_OP(&, maxValueForBits<bitCount<maxN>()>() & cvalue) |
936 | |
937 | OP(|, maxN | cvalue) |
938 | REVERSE_OP(|, maxN | cvalue) |
939 | |
940 | COMPARE_OP(==) |
941 | COMPARE_OP(!=) |
942 | COMPARE_OP(< ) |
943 | COMPARE_OP(> ) |
944 | COMPARE_OP(<=) |
945 | COMPARE_OP(>=) |
946 | |
947 | #undef OP |
948 | #undef REVERSE_OP |
949 | #undef COMPARE_OP |
950 | |
951 | template <uint64_t maxN, uint cvalue, typename T> |
952 | inline constexpr Bounded<cvalue, decltype(uint() - T())> |
953 | operator-(BoundedConst<cvalue>, Bounded<maxN, T> value) { |
954 | // We allow subtraction of a variable from a constant only if the constant is greater than or |
955 | // equal to the maximum possible value of the variable. Since the variable could be zero, the |
956 | // result can be as large as the constant. |
957 | // |
958 | // We do not allow subtraction of a constant from a variable because there's never a guarantee it |
959 | // won't underflow (unless the constant is zero, which is silly). |
960 | static_assert(cvalue >= maxN, "possible underflow detected" ); |
961 | return Bounded<cvalue, decltype(uint() - T())>(cvalue - value.unwrap(), unsafe); |
962 | } |
963 | |
964 | template <uint64_t aN, uint b, typename A> |
965 | inline constexpr Bounded<kj::min(aN, b), A> min(Bounded<aN, A> a, BoundedConst<b>) { |
966 | return Bounded<kj::min(aN, b), A>(kj::min(b, a.unwrap()), unsafe); |
967 | } |
968 | template <uint64_t aN, uint b, typename A> |
969 | inline constexpr Bounded<kj::min(aN, b), A> min(BoundedConst<b>, Bounded<aN, A> a) { |
970 | return Bounded<kj::min(aN, b), A>(kj::min(a.unwrap(), b), unsafe); |
971 | } |
972 | template <uint64_t aN, uint b, typename A> |
973 | inline constexpr Bounded<kj::max(aN, b), A> max(Bounded<aN, A> a, BoundedConst<b>) { |
974 | return Bounded<kj::max(aN, b), A>(kj::max(b, a.unwrap()), unsafe); |
975 | } |
976 | template <uint64_t aN, uint b, typename A> |
977 | inline constexpr Bounded<kj::max(aN, b), A> max(BoundedConst<b>, Bounded<aN, A> a) { |
978 | return Bounded<kj::max(aN, b), A>(kj::max(a.unwrap(), b), unsafe); |
979 | } |
980 | // We need to override min() between a Bounded and a constant since: |
981 | // 1) WiderType<> might choose BoundedConst over a 1-byte Bounded, which is wrong. |
982 | // 2) To clamp the bounds of the output type. |
983 | // 3) Same ternary operator typechecking issues. |
984 | |
985 | // ------------------------------------------------------------------- |
986 | |
987 | template <uint64_t maxN, typename T> |
988 | class SafeUnwrapper { |
989 | public: |
990 | inline explicit constexpr SafeUnwrapper(Bounded<maxN, T> value): value(value.unwrap()) {} |
991 | |
992 | template <typename U, typename = EnableIf<isIntegral<U>()>> |
993 | inline constexpr operator U() const { |
994 | static_assert(maxN <= U(maxValue), "possible truncation detected" ); |
995 | return value; |
996 | } |
997 | |
998 | inline constexpr operator bool() const { |
999 | static_assert(maxN <= 1, "possible truncation detected" ); |
1000 | return value; |
1001 | } |
1002 | |
1003 | private: |
1004 | T value; |
1005 | }; |
1006 | |
1007 | template <uint64_t maxN, typename T> |
1008 | inline constexpr SafeUnwrapper<maxN, T> unbound(Bounded<maxN, T> bounded) { |
1009 | // Unwraps the bounded value, returning a value that can be implicitly cast to any integer type. |
1010 | // If this implicit cast could truncate, a compile-time error will be raised. |
1011 | return SafeUnwrapper<maxN, T>(bounded); |
1012 | } |
1013 | |
1014 | template <uint64_t value> |
1015 | class SafeConstUnwrapper { |
1016 | public: |
1017 | template <typename T, typename = EnableIf<isIntegral<T>()>> |
1018 | inline constexpr operator T() const { |
1019 | static_assert(value <= T(maxValue), "this operation will truncate" ); |
1020 | return value; |
1021 | } |
1022 | |
1023 | inline constexpr operator bool() const { |
1024 | static_assert(value <= 1, "this operation will truncate" ); |
1025 | return value; |
1026 | } |
1027 | }; |
1028 | |
1029 | template <uint value> |
1030 | inline constexpr SafeConstUnwrapper<value> unbound(BoundedConst<value>) { |
1031 | return SafeConstUnwrapper<value>(); |
1032 | } |
1033 | |
1034 | template <typename T, typename U> |
1035 | inline constexpr T unboundAs(U value) { |
1036 | return unbound(value); |
1037 | } |
1038 | |
1039 | template <uint64_t requestedMax, uint64_t maxN, typename T> |
1040 | inline constexpr T unboundMax(Bounded<maxN, T> value) { |
1041 | // Explicitly ungaurd expecting a value that is at most `maxN`. |
1042 | static_assert(maxN <= requestedMax, "possible overflow detected" ); |
1043 | return value.unwrap(); |
1044 | } |
1045 | |
1046 | template <uint64_t requestedMax, uint value> |
1047 | inline constexpr uint unboundMax(BoundedConst<value>) { |
1048 | // Explicitly ungaurd expecting a value that is at most `maxN`. |
1049 | static_assert(value <= requestedMax, "overflow detected" ); |
1050 | return value; |
1051 | } |
1052 | |
1053 | template <uint bits, typename T> |
1054 | inline constexpr auto unboundMaxBits(T value) -> |
1055 | decltype(unboundMax<maxValueForBits<bits>()>(value)) { |
1056 | // Explicitly ungaurd expecting a value that fits into `bits` bits. |
1057 | return unboundMax<maxValueForBits<bits>()>(value); |
1058 | } |
1059 | |
1060 | #define OP(op) \ |
1061 | template <uint64_t maxN, typename T, typename U> \ |
1062 | inline constexpr auto operator op(T a, SafeUnwrapper<maxN, U> b) -> decltype(a op (T)b) { \ |
1063 | return a op (AtLeastUInt<sizeof(T)*8>)b; \ |
1064 | } \ |
1065 | template <uint64_t maxN, typename T, typename U> \ |
1066 | inline constexpr auto operator op(SafeUnwrapper<maxN, U> b, T a) -> decltype((T)b op a) { \ |
1067 | return (AtLeastUInt<sizeof(T)*8>)b op a; \ |
1068 | } \ |
1069 | template <uint64_t value, typename T> \ |
1070 | inline constexpr auto operator op(T a, SafeConstUnwrapper<value> b) -> decltype(a op (T)b) { \ |
1071 | return a op (AtLeastUInt<sizeof(T)*8>)b; \ |
1072 | } \ |
1073 | template <uint64_t value, typename T> \ |
1074 | inline constexpr auto operator op(SafeConstUnwrapper<value> b, T a) -> decltype((T)b op a) { \ |
1075 | return (AtLeastUInt<sizeof(T)*8>)b op a; \ |
1076 | } |
1077 | |
1078 | OP(+) |
1079 | OP(-) |
1080 | OP(*) |
1081 | OP(/) |
1082 | OP(%) |
1083 | OP(<<) |
1084 | OP(>>) |
1085 | OP(&) |
1086 | OP(|) |
1087 | OP(==) |
1088 | OP(!=) |
1089 | OP(<=) |
1090 | OP(>=) |
1091 | OP(<) |
1092 | OP(>) |
1093 | |
1094 | #undef OP |
1095 | |
1096 | // ------------------------------------------------------------------- |
1097 | |
1098 | template <uint64_t maxN, typename T> |
1099 | class Range<Bounded<maxN, T>> { |
1100 | public: |
1101 | inline constexpr Range(Bounded<maxN, T> begin, Bounded<maxN, T> end) |
1102 | : inner(unbound(begin), unbound(end)) {} |
1103 | inline explicit constexpr Range(Bounded<maxN, T> end) |
1104 | : inner(unbound(end)) {} |
1105 | |
1106 | class Iterator { |
1107 | public: |
1108 | Iterator() = default; |
1109 | inline explicit Iterator(typename Range<T>::Iterator inner): inner(inner) {} |
1110 | |
1111 | inline Bounded<maxN, T> operator* () const { return Bounded<maxN, T>(*inner, unsafe); } |
1112 | inline Iterator& operator++() { ++inner; return *this; } |
1113 | |
1114 | inline bool operator==(const Iterator& other) const { return inner == other.inner; } |
1115 | inline bool operator!=(const Iterator& other) const { return inner != other.inner; } |
1116 | |
1117 | private: |
1118 | typename Range<T>::Iterator inner; |
1119 | }; |
1120 | |
1121 | inline Iterator begin() const { return Iterator(inner.begin()); } |
1122 | inline Iterator end() const { return Iterator(inner.end()); } |
1123 | |
1124 | private: |
1125 | Range<T> inner; |
1126 | }; |
1127 | |
1128 | template <typename T, typename U> |
1129 | class Range<Quantity<T, U>> { |
1130 | public: |
1131 | inline constexpr Range(Quantity<T, U> begin, Quantity<T, U> end) |
1132 | : inner(begin / unit<Quantity<T, U>>(), end / unit<Quantity<T, U>>()) {} |
1133 | inline explicit constexpr Range(Quantity<T, U> end) |
1134 | : inner(end / unit<Quantity<T, U>>()) {} |
1135 | |
1136 | class Iterator { |
1137 | public: |
1138 | Iterator() = default; |
1139 | inline explicit Iterator(typename Range<T>::Iterator inner): inner(inner) {} |
1140 | |
1141 | inline Quantity<T, U> operator* () const { return *inner * unit<Quantity<T, U>>(); } |
1142 | inline Iterator& operator++() { ++inner; return *this; } |
1143 | |
1144 | inline bool operator==(const Iterator& other) const { return inner == other.inner; } |
1145 | inline bool operator!=(const Iterator& other) const { return inner != other.inner; } |
1146 | |
1147 | private: |
1148 | typename Range<T>::Iterator inner; |
1149 | }; |
1150 | |
1151 | inline Iterator begin() const { return Iterator(inner.begin()); } |
1152 | inline Iterator end() const { return Iterator(inner.end()); } |
1153 | |
1154 | private: |
1155 | Range<T> inner; |
1156 | }; |
1157 | |
1158 | template <uint value> |
1159 | inline constexpr Range<Bounded<value, uint>> zeroTo(BoundedConst<value> end) { |
1160 | return Range<Bounded<value, uint>>(end); |
1161 | } |
1162 | |
1163 | template <uint value, typename Unit> |
1164 | inline constexpr Range<Quantity<Bounded<value, uint>, Unit>> |
1165 | zeroTo(Quantity<BoundedConst<value>, Unit> end) { |
1166 | return Range<Quantity<Bounded<value, uint>, Unit>>(end); |
1167 | } |
1168 | |
1169 | } // namespace kj |
1170 | |