[corelib] Add explicit overflow checks to int.parse

runtime/lib/integers_patch.dart

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 // Dart core library.
 
 // VM implementation of int.
 
 @patch
 class int {
   @patch
@@ skipping 114 matching lines @@
     while (smallBlockSize >= blockSize) smallBlockSize -= blockSize;
     int result = 0;
     if (smallBlockSize > 0) {
       int blockEnd = start + smallBlockSize;
       _Smi smi = _parseBlock(source, radix, start, blockEnd);
       if (smi == null) return null;
       result = sign * smi;
       start = blockEnd;
     }
     int multiplier = _PARSE_LIMITS[tableIndex + 1];
+    int positiveOverflowLimit = _int64OverflowLimits[tableIndex];
+    int negativeOverflowLimit = _int64OverflowLimits[tableIndex + 1];

[Lasse Reichstein Nielsen, 2017/07/27 23:40:18]

Only read these if they are needed (which goes well with the separate loop
suggested below).

[alexmarkov, 2017/07/28 17:29:02]

Done (see the newer CL).

     int blockEnd = start + blockSize;
     do {
       _Smi smi = _parseBlock(source, radix, start, blockEnd);
       if (smi == null) return null;
+      if (_limitIntsTo64Bits) {
+        if (result >= positiveOverflowLimit) {
+          if ((result > positiveOverflowLimit) ||
+              (smi > (_maxInt64 - positiveOverflowLimit * multiplier))) {
+            return null;
+          }
+        } else if (result <= negativeOverflowLimit) {
+          if ((result < negativeOverflowLimit) ||
+              (smi > (negativeOverflowLimit * multiplier - _minInt64))) {
+            return null;
+          }
+        }
+      }

[Lasse Reichstein Nielsen, 2017/07/27 23:40:18]

This increases the inner loop size significantly if the condition is not
optimized away by the compiler.

Can you check how much this affects performance when the flag isn't set?

Maybe have an entire different loop for the limit-to-64-bits case.
Heck, maybe have an entire different method and algorithm since we know that
there are at most two/three smis in 64 bits.
(I'm also considering splitting the parsing into different loops for base <= 10
and base > 10, instead of having the radix check in every call to _parseBlock.

[alexmarkov, 2017/07/28 17:29:02]

Optimizer should be able to remove "if (_limitIntsTo64Bits)" entirely, because
_limitIntsTo64Bits is a compile-time constant. I did performance measurements on
micro-benchmark on my linux desktop and didn't notice any performance difference
in default mode (if --limit-ints-to-64-bits is not enabled). I'll double check
by looking into the optimized code for this method to ensure that the check for
_limitIntsTo64Bits is completely eliminated.

[alexmarkov, 2017/07/28 18:25:56]

As I expected, both JIT and AOT optimizers are able to remove the code "if
(_limitIntsTo64Bits) { ... }" entirely.

       result = (result * multiplier) + (sign * smi);
       start = blockEnd;
       blockEnd = start + blockSize;
     } while (blockEnd <= end);
     return result;
   }
 
   // Parse block of digits into a Smi.
   static _Smi _parseBlock(String source, int radix, int start, int end) {
     _Smi result = 0;
@@ skipping 50 matching lines @@
     6, 481890304, 12, 232218265089212416,
     6, 594823321, 12, 353814783205469041,
     6, 729000000, 12, 531441000000000000, //    radix: 30
     6, 887503681, 12, 787662783788549761,
     6, 1073741824, 12, 1152921504606846976,
     5, 39135393, 12, 1667889514952984961,
     5, 45435424, 12, 2386420683693101056,
     5, 52521875, 12, 3379220508056640625, //    radix: 35
     5, 60466176, 11, 131621703842267136,
   ];
+
+  // Flag indicating if integers are limited by 64 bits
+  // (--limit-ints-to-64-bits mode is enabled).

[Lasse Reichstein Nielsen, 2017/07/27 23:40:18]

Use doc-comments ("///"). It might make some editors show the documentation when
hovering, and it can't hurt.

[alexmarkov, 2017/07/28 17:29:02]

Done.

+  static const _limitIntsTo64Bits = ((1 << 64) == 0);
+
+  static const _maxInt64 = 0x7fffffffffffffff;
+  static const _minInt64 = -_maxInt64 - 1;

[Lasse Reichstein Nielsen, 2017/07/27 23:40:17]

In the "limit integers to 64-bit mode", you should find a way to accept the
expression `-0x8000000000000000`, even if it requires special-casing the unary
minus+integer literal case.

[alexmarkov, 2017/07/28 17:29:02]

It's a known problem and will be addressed separately. Unfortunately, for now
literals like -0x8000000000000000 or -9223372036854775808 do not work in
--limit-ints-to-64-bits mode. I'll correct this constant after such literals are
supported.

+
+  // In the --limit-ints-to-64-bits mode calculation of the expression
+  //   result = (result * multiplier) + (sign * smi);
+  // in _parseRadix() may overflow 64-bit integers. In such case, int.parse()
+  // should stop with an error. It is safe to do this calculation until partial
+  // result reaches or exceeds limits in this table.
+  // For each multiplier from _PARSE_LIMITS[tableIndex + 1] the
+  // positive limit is at tableIndex, the negative limit is at tableIndex + 1.
+  static const _int64OverflowLimits = const [

[zra, 2017/07/27 21:22:38]

Is there any way to populate this table lazily?

[alexmarkov, 2017/07/27 23:37:32]

Done.

[Lasse Reichstein Nielsen, 2017/07/27 23:40:17]

Don't make it const, then it's evaluated the first time it's accessed.
That might slow down all accesses, though, depending on the implementation (I
have no idea how it's actually implemented, but that's the effect of static
variables in C++ - an extra "is initialized" check on each access).

[alexmarkov, 2017/07/28 17:29:02]

Done.

+    _maxInt64 ~/ 1073741824,
+    _minInt64 ~/ 1073741824,
+    _maxInt64 ~/ 4611686018427387904,
+    _minInt64 ~/ 4611686018427387904,
+    _maxInt64 ~/ 387420489,
+    _minInt64 ~/ 387420489,
+    _maxInt64 ~/ 4052555153018976267,
+    _minInt64 ~/ 4052555153018976267,
+    _maxInt64 ~/ 1073741824,
+    _minInt64 ~/ 1073741824,
+    _maxInt64 ~/ 1152921504606846976,
+    _minInt64 ~/ 1152921504606846976,
+    _maxInt64 ~/ 244140625,
+    _minInt64 ~/ 244140625,
+    _maxInt64 ~/ 1490116119384765625,
+    _minInt64 ~/ 1490116119384765625,
+    _maxInt64 ~/ 362797056,
+    _minInt64 ~/ 362797056,
+    _maxInt64 ~/ 789730223053602816,
+    _minInt64 ~/ 789730223053602816,
+    _maxInt64 ~/ 282475249,
+    _minInt64 ~/ 282475249,
+    _maxInt64 ~/ 3909821048582988049,
+    _minInt64 ~/ 3909821048582988049,
+    _maxInt64 ~/ 1073741824,
+    _minInt64 ~/ 1073741824,
+    _maxInt64 ~/ 1152921504606846976,
+    _minInt64 ~/ 1152921504606846976,
+    _maxInt64 ~/ 387420489,
+    _minInt64 ~/ 387420489,
+    _maxInt64 ~/ 1350851717672992089,
+    _minInt64 ~/ 1350851717672992089,
+    _maxInt64 ~/ 1000000000,
+    _minInt64 ~/ 1000000000,
+    _maxInt64 ~/ 1000000000000000000,
+    _minInt64 ~/ 1000000000000000000,
+    _maxInt64 ~/ 214358881,
+    _minInt64 ~/ 214358881,
+    _maxInt64 ~/ 505447028499293771,
+    _minInt64 ~/ 505447028499293771,
+    _maxInt64 ~/ 429981696,
+    _minInt64 ~/ 429981696,
+    _maxInt64 ~/ 2218611106740436992,
+    _minInt64 ~/ 2218611106740436992,
+    _maxInt64 ~/ 815730721,
+    _minInt64 ~/ 815730721,
+    _maxInt64 ~/ 665416609183179841,
+    _minInt64 ~/ 665416609183179841,
+    _maxInt64 ~/ 105413504,
+    _minInt64 ~/ 105413504,
+    _maxInt64 ~/ 2177953337809371136,
+    _minInt64 ~/ 2177953337809371136,
+    _maxInt64 ~/ 170859375,
+    _minInt64 ~/ 170859375,
+    _maxInt64 ~/ 437893890380859375,
+    _minInt64 ~/ 437893890380859375,
+    _maxInt64 ~/ 268435456,
+    _minInt64 ~/ 268435456,
+    _maxInt64 ~/ 1152921504606846976,
+    _minInt64 ~/ 1152921504606846976,
+    _maxInt64 ~/ 410338673,
+    _minInt64 ~/ 410338673,
+    _maxInt64 ~/ 2862423051509815793,
+    _minInt64 ~/ 2862423051509815793,
+    _maxInt64 ~/ 612220032,
+    _minInt64 ~/ 612220032,
+    _maxInt64 ~/ 374813367582081024,
+    _minInt64 ~/ 374813367582081024,
+    _maxInt64 ~/ 893871739,
+    _minInt64 ~/ 893871739,
+    _maxInt64 ~/ 799006685782884121,
+    _minInt64 ~/ 799006685782884121,
+    _maxInt64 ~/ 64000000,
+    _minInt64 ~/ 64000000,
+    _maxInt64 ~/ 1638400000000000000,
+    _minInt64 ~/ 1638400000000000000,
+    _maxInt64 ~/ 85766121,
+    _minInt64 ~/ 85766121,
+    _maxInt64 ~/ 3243919932521508681,
+    _minInt64 ~/ 3243919932521508681,
+    _maxInt64 ~/ 113379904,
+    _minInt64 ~/ 113379904,
+    _maxInt64 ~/ 282810057883082752,
+    _minInt64 ~/ 282810057883082752,
+    _maxInt64 ~/ 148035889,
+    _minInt64 ~/ 148035889,
+    _maxInt64 ~/ 504036361936467383,
+    _minInt64 ~/ 504036361936467383,
+    _maxInt64 ~/ 191102976,
+    _minInt64 ~/ 191102976,
+    _maxInt64 ~/ 876488338465357824,
+    _minInt64 ~/ 876488338465357824,
+    _maxInt64 ~/ 244140625,
+    _minInt64 ~/ 244140625,
+    _maxInt64 ~/ 1490116119384765625,
+    _minInt64 ~/ 1490116119384765625,
+    _maxInt64 ~/ 308915776,
+    _minInt64 ~/ 308915776,
+    _maxInt64 ~/ 2481152873203736576,
+    _minInt64 ~/ 2481152873203736576,
+    _maxInt64 ~/ 387420489,
+    _minInt64 ~/ 387420489,
+    _maxInt64 ~/ 4052555153018976267,
+    _minInt64 ~/ 4052555153018976267,
+    _maxInt64 ~/ 481890304,
+    _minInt64 ~/ 481890304,
+    _maxInt64 ~/ 232218265089212416,
+    _minInt64 ~/ 232218265089212416,
+    _maxInt64 ~/ 594823321,
+    _minInt64 ~/ 594823321,
+    _maxInt64 ~/ 353814783205469041,
+    _minInt64 ~/ 353814783205469041,
+    _maxInt64 ~/ 729000000,
+    _minInt64 ~/ 729000000,
+    _maxInt64 ~/ 531441000000000000,
+    _minInt64 ~/ 531441000000000000,
+    _maxInt64 ~/ 887503681,
+    _minInt64 ~/ 887503681,
+    _maxInt64 ~/ 787662783788549761,
+    _minInt64 ~/ 787662783788549761,
+    _maxInt64 ~/ 1073741824,
+    _minInt64 ~/ 1073741824,
+    _maxInt64 ~/ 1152921504606846976,
+    _minInt64 ~/ 1152921504606846976,
+    _maxInt64 ~/ 39135393,
+    _minInt64 ~/ 39135393,
+    _maxInt64 ~/ 1667889514952984961,
+    _minInt64 ~/ 1667889514952984961,
+    _maxInt64 ~/ 45435424,
+    _minInt64 ~/ 45435424,
+    _maxInt64 ~/ 2386420683693101056,
+    _minInt64 ~/ 2386420683693101056,
+    _maxInt64 ~/ 52521875,
+    _minInt64 ~/ 52521875,
+    _maxInt64 ~/ 3379220508056640625,
+    _minInt64 ~/ 3379220508056640625,
+    _maxInt64 ~/ 60466176,
+    _minInt64 ~/ 60466176,
+    _maxInt64 ~/ 131621703842267136,
+    _minInt64 ~/ 131621703842267136,
+  ];
 }