Merge pull request #3793 from ethereum/rationalNumberLimit

Rational number limit

11 files changed, 297 insertions, 20 deletions

diff --git a/Changelog.md b/Changelog.md
index 91048cd5..9d1c835d 100644
--- a/Changelog.md
+++ b/Changelog.md
@@ -43,6 +43,7 @@ Bugfixes:
  * Type System: Improve error message when attempting to shift by a fractional amount.
  * Type System: Make external library functions accessible.
  * Type System: Prevent encoding of weird types.
+ * Type System: Restrict rational numbers to 4096 bits.
  * Static Analyzer: Fix non-deterministic order of unused variable warnings.
  * Static Analyzer: Invalid arithmetic with constant expressions causes errors.
 
diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp
index 68b12777..51739cb0 100644
--- a/libsolidity/ast/Types.cpp
+++ b/libsolidity/ast/Types.cpp
@@ -44,6 +44,85 @@ using namespace std;
 using namespace dev;
 using namespace dev::solidity;
 
+namespace
+{
+
+unsigned int mostSignificantBit(bigint const& _number)
+{
+#if BOOST_VERSION < 105500
+	solAssert(_number > 0, "");
+	bigint number = _number;
+	unsigned int result = 0;
+	while (number != 0)
+	{
+		number >>= 1;
+		++result;
+	}
+	return --result;
+#else
+	return boost::multiprecision::msb(_number);
+#endif
+}
+
+/// Check whether (_base ** _exp) fits into 4096 bits.
+bool fitsPrecisionExp(bigint const& _base, bigint const& _exp)
+{
+	if (_base == 0)
+		return true;
+
+	solAssert(_base > 0, "");
+
+	size_t const bitsMax = 4096;
+
+	unsigned mostSignificantBaseBit = mostSignificantBit(_base);
+	if (mostSignificantBaseBit == 0) // _base == 1
+		return true;
+	if (mostSignificantBaseBit > bitsMax) // _base >= 2 ^ 4096
+		return false;
+
+	bigint bitsNeeded = _exp * (mostSignificantBaseBit + 1);
+
+	return bitsNeeded <= bitsMax;
+}
+
+/// Checks whether _mantissa * (X ** _exp) fits into 4096 bits,
+/// where X is given indirectly via _log2OfBase = log2(X).
+bool fitsPrecisionBaseX(
+	bigint const& _mantissa,
+	double _log2OfBase,
+	uint32_t _exp
+)
+{
+	if (_mantissa == 0)
+		return true;
+
+	solAssert(_mantissa > 0, "");
+
+	size_t const bitsMax = 4096;
+
+	unsigned mostSignificantMantissaBit = mostSignificantBit(_mantissa);
+	if (mostSignificantMantissaBit > bitsMax) // _mantissa >= 2 ^ 4096
+		return false;
+
+	bigint bitsNeeded = mostSignificantMantissaBit + bigint(floor(double(_exp) * _log2OfBase)) + 1;
+	return bitsNeeded <= bitsMax;
+}
+
+/// Checks whether _mantissa * (10 ** _expBase10) fits into 4096 bits.
+bool fitsPrecisionBase10(bigint const& _mantissa, uint32_t _expBase10)
+{
+	double const log2Of10AwayFromZero = 3.3219280948873624;
+	return fitsPrecisionBaseX(_mantissa, log2Of10AwayFromZero, _expBase10);
+}
+
+/// Checks whether _mantissa * (2 ** _expBase10) fits into 4096 bits.
+bool fitsPrecisionBase2(bigint const& _mantissa, uint32_t _expBase2)
+{
+	return fitsPrecisionBaseX(_mantissa, 1.0, _expBase2);
+}
+
+}
+
 void StorageOffsets::computeOffsets(TypePointers const& _types)
 {
 	bigint slotOffset = 0;
@@ -689,31 +768,39 @@ tuple<bool, rational> RationalNumberType::isValidLiteral(Literal const& _literal
 		}
 		else if (expPoint != _literal.value().end())
 		{
-			// parse the exponent
+			// Parse base and exponent. Checks numeric limit.
 			bigint exp = bigint(string(expPoint + 1, _literal.value().end()));
 
 			if (exp > numeric_limits<int32_t>::max() || exp < numeric_limits<int32_t>::min())
 				return make_tuple(false, rational(0));
 
-			// parse the base
+			uint32_t expAbs = bigint(abs(exp)).convert_to<uint32_t>();
+
+
 			tuple<bool, rational> base = parseRational(string(_literal.value().begin(), expPoint));
+
 			if (!get<0>(base))
 				return make_tuple(false, rational(0));
 			value = get<1>(base);
 
 			if (exp < 0)
 			{
-				exp *= -1;
+				if (!fitsPrecisionBase10(abs(value.denominator()), expAbs))
+					return make_tuple(false, rational(0));
 				value /= boost::multiprecision::pow(
 					bigint(10),
-					exp.convert_to<int32_t>()
+					expAbs
 				);
 			}
-			else
+			else if (exp > 0)
+			{
+				if (!fitsPrecisionBase10(abs(value.numerator()), expAbs))
+					return make_tuple(false, rational(0));
 				value *= boost::multiprecision::pow(
 					bigint(10),
-					exp.convert_to<int32_t>()
+					expAbs
 				);
+			}
 		}
 		else
 		{
@@ -912,16 +999,49 @@ TypePointer RationalNumberType::binaryOperatorResult(Token::Value _operator, Typ
 			using boost::multiprecision::pow;
 			if (other.isFractional())
 				return TypePointer();
-			else if (abs(other.m_value) > numeric_limits<uint32_t>::max())
-				return TypePointer(); // This will need too much memory to represent.
-			uint32_t exponent = abs(other.m_value).numerator().convert_to<uint32_t>();
-			bigint numerator = pow(m_value.numerator(), exponent);
-			bigint denominator = pow(m_value.denominator(), exponent);
-			if (other.m_value >= 0)
-				value = rational(numerator, denominator);
+			solAssert(other.m_value.denominator() == 1, "");
+			bigint const& exp = other.m_value.numerator();
+
+			// x ** 0 = 1
+			// for 0, 1 and -1 the size of the exponent doesn't have to be restricted
+			if (exp == 0)
+				value = 1;
+			else if (m_value.numerator() == 0 || m_value == 1)
+				value = m_value;
+			else if (m_value == -1)
+			{
+				bigint isOdd = abs(exp) & bigint(1);
+				value = 1 - 2 * isOdd.convert_to<int>();
+			}
 			else
-				// invert
-				value = rational(denominator, numerator);
+			{
+				if (abs(exp) > numeric_limits<uint32_t>::max())
+					return TypePointer(); // This will need too much memory to represent.
+
+				uint32_t absExp = bigint(abs(exp)).convert_to<uint32_t>();
+
+				// Limit size to 4096 bits
+				if (!fitsPrecisionExp(abs(m_value.numerator()), absExp) || !fitsPrecisionExp(abs(m_value.denominator()), absExp))
+					return TypePointer();
+
+				static auto const optimizedPow = [](bigint const& _base, uint32_t _exponent) -> bigint {
+					if (_base == 1)
+						return 1;
+					else if (_base == -1)
+						return 1 - 2 * int(_exponent & 1);
+					else
+						return pow(_base, _exponent);
+				};
+
+				bigint numerator = optimizedPow(m_value.numerator(), absExp);
+				bigint denominator = optimizedPow(m_value.denominator(), absExp);
+
+				if (exp >= 0)
+					value = rational(numerator, denominator);
+				else
+					// invert
+					value = rational(denominator, numerator);
+			}
 			break;
 		}
 		case Token::SHL:
@@ -933,28 +1053,48 @@ TypePointer RationalNumberType::binaryOperatorResult(Token::Value _operator, Typ
 				return TypePointer();
 			else if (other.m_value > numeric_limits<uint32_t>::max())
 				return TypePointer();
-			uint32_t exponent = other.m_value.numerator().convert_to<uint32_t>();
-			value = m_value.numerator() * pow(bigint(2), exponent);
+			if (m_value.numerator() == 0)
+				value = 0;
+			else
+			{
+				uint32_t exponent = other.m_value.numerator().convert_to<uint32_t>();
+				if (!fitsPrecisionBase2(abs(m_value.numerator()), exponent))
+					return TypePointer();
+				value = m_value.numerator() * pow(bigint(2), exponent);
+			}
 			break;
 		}
 		// NOTE: we're using >> (SAR) to denote right shifting. The type of the LValue
 		//       determines the resulting type and the type of shift (SAR or SHR).
 		case Token::SAR:
 		{
-			using boost::multiprecision::pow;
+			namespace mp = boost::multiprecision;
 			if (fractional)
 				return TypePointer();
 			else if (other.m_value < 0)
 				return TypePointer();
 			else if (other.m_value > numeric_limits<uint32_t>::max())
 				return TypePointer();
-			uint32_t exponent = other.m_value.numerator().convert_to<uint32_t>();
-			value = rational(m_value.numerator() / pow(bigint(2), exponent), 1);
+			if (m_value.numerator() == 0)
+				value = 0;
+			else
+			{
+				uint32_t exponent = other.m_value.numerator().convert_to<uint32_t>();
+				if (exponent > mostSignificantBit(mp::abs(m_value.numerator())))
+					value = 0;
+				else
+					value = rational(m_value.numerator() / mp::pow(bigint(2), exponent), 1);
+			}
 			break;
 		}
 		default:
 			return TypePointer();
 		}
+
+		// verify that numerator and denominator fit into 4096 bit after every operation
+		if (value.numerator() != 0 && max(mostSignificantBit(abs(value.numerator())), mostSignificantBit(abs(value.denominator()))) > 4096)
+			return TypePointer();
+
 		return make_shared<RationalNumberType>(value);
 	}
 }
diff --git a/test/libsolidity/SolidityEndToEndTest.cpp b/test/libsolidity/SolidityEndToEndTest.cpp
index cbeca215..8440449c 100644
--- a/test/libsolidity/SolidityEndToEndTest.cpp
+++ b/test/libsolidity/SolidityEndToEndTest.cpp
@@ -102,6 +102,29 @@ BOOST_AUTO_TEST_CASE(exp_operator_const_signed)
 	ABI_CHECK(callContractFunction("f()", bytes()), toBigEndian(u256(-8)));
 }
 
+BOOST_AUTO_TEST_CASE(exp_zero)
+{
+	char const* sourceCode = R"(
+		contract test {
+			function f(uint a) returns(uint d) { return a ** 0; }
+		}
+	)";
+	compileAndRun(sourceCode);
+	testContractAgainstCppOnRange("f(uint256)", [](u256 const&) -> u256 { return u256(1); }, 0, 16);
+}
+
+BOOST_AUTO_TEST_CASE(exp_zero_literal)
+{
+	char const* sourceCode = R"(
+		contract test {
+			function f() returns(uint d) { return 0 ** 0; }
+		}
+	)";
+	compileAndRun(sourceCode);
+	ABI_CHECK(callContractFunction("f()", bytes()), toBigEndian(u256(1)));
+}
+
+
 BOOST_AUTO_TEST_CASE(conditional_expression_true_literal)
 {
 	char const* sourceCode = R"(
diff --git a/test/libsolidity/syntaxTests/types/rational_number_array_index_limit.sol b/test/libsolidity/syntaxTests/types/rational_number_array_index_limit.sol
new file mode 100644
index 00000000..45ede998
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_array_index_limit.sol
@@ -0,0 +1,5 @@
+contract c {
+    uint[2**253] data;
+}
+// ----
+// Warning: (17-34): Variable covers a large part of storage and thus makes collisions likely. Either use mappings or dynamic arrays and allow their size to be increased only in small quantities per transaction.
diff --git a/test/libsolidity/syntaxTests/types/rational_number_bitshift_limit.sol b/test/libsolidity/syntaxTests/types/rational_number_bitshift_limit.sol
new file mode 100644
index 00000000..94981aa0
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_bitshift_limit.sol
@@ -0,0 +1,13 @@
+contract c {
+    function f() public pure {
+        int a;
+        a = 1 << 4095; // shift is fine, but result too large
+        a = 1 << 4096; // too large
+        a = (1E1233) << 2; // too large
+    }
+}
+// ----
+// TypeError: (71-80): Type int_const 5221...(1225 digits omitted)...5168 is not implicitly convertible to expected type int256.
+// TypeError: (133-142): Operator << not compatible with types int_const 1 and int_const 4096
+// TypeError: (169-182): Operator << not compatible with types int_const 1000...(1226 digits omitted)...0000 and int_const 2
+// TypeError: (169-182): Type int_const 1000...(1226 digits omitted)...0000 is not implicitly convertible to expected type int256.
diff --git a/test/libsolidity/syntaxTests/types/rational_number_div_limit.sol b/test/libsolidity/syntaxTests/types/rational_number_div_limit.sol
new file mode 100644
index 00000000..1b0b5f94
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_div_limit.sol
@@ -0,0 +1,9 @@
+contract c {
+    function f() public pure {
+        int a;
+        a = 1/(2<<4094)/(2<<4094);
+    }
+}
+// ----
+// TypeError: (71-92): Operator / not compatible with types rational_const 1 / 5221...(1225 digits omitted)...5168 and int_const 5221...(1225 digits omitted)...5168
+// TypeError: (71-92): Type rational_const 1 / 5221...(1225 digits omitted)...5168 is not implicitly convertible to expected type int256. Try converting to type ufixed8x80 or use an explicit conversion.
diff --git a/test/libsolidity/syntaxTests/types/rational_number_exp_limit.sol b/test/libsolidity/syntaxTests/types/rational_number_exp_limit.sol
new file mode 100644
index 00000000..6785f580
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_exp_limit.sol
@@ -0,0 +1,50 @@
+contract c {
+    function f() public pure {
+        int a;
+        a = 4 ** 4 ** 2 ** 4 ** 4 ** 4 ** 4;
+        a = -4 ** 4 ** 2 ** 4 ** 4 ** 4 ** 4 ** 4;
+        a = 4 ** (-(2 ** 4 ** 4 ** 4 ** 4 ** 4));
+        a = 0 ** 1E1233; // fine
+        a = 1 ** 1E1233; // fine
+        a = -1 ** 1E1233; // fine
+        a = 2 ** 1E1233;
+        a = -2 ** 1E1233;
+        a = 2 ** -1E1233;
+        a = -2 ** -1E1233;
+        a = 1E1233 ** 2;
+        a = -1E1233 ** 2;
+        a = 1E1233 ** -2;
+        a = -1E1233 ** -2;
+        a = 1E1233 ** 1E1233;
+        a = 1E1233 ** -1E1233;
+        a = -1E1233 ** 1E1233;
+        a = -1E1233 ** -1E1233;
+    }
+}
+// ----
+// TypeError: (71-102): Operator ** not compatible with types int_const 1797...(301 digits omitted)...7216 and int_const 4
+// TypeError: (71-102): Type int_const 1797...(301 digits omitted)...7216 is not implicitly convertible to expected type int256.
+// TypeError: (116-148): Operator ** not compatible with types int_const 1797...(301 digits omitted)...7216 and int_const 4
+// TypeError: (116-153): Operator ** not compatible with types int_const 1797...(301 digits omitted)...7216 and int_const 4
+// TypeError: (116-153): Type int_const 1797...(301 digits omitted)...7216 is not implicitly convertible to expected type int256.
+// TypeError: (167-203): Operator ** not compatible with types int_const 4 and int_const -179...(302 digits omitted)...7216
+// TypeError: (317-328): Operator ** not compatible with types int_const 2 and int_const 1000...(1226 digits omitted)...0000
+// TypeError: (342-354): Operator ** not compatible with types int_const -2 and int_const 1000...(1226 digits omitted)...0000
+// TypeError: (368-380): Operator ** not compatible with types int_const 2 and int_const -100...(1227 digits omitted)...0000
+// TypeError: (394-407): Operator ** not compatible with types int_const -2 and int_const -100...(1227 digits omitted)...0000
+// TypeError: (421-432): Operator ** not compatible with types int_const 1000...(1226 digits omitted)...0000 and int_const 2
+// TypeError: (421-432): Type int_const 1000...(1226 digits omitted)...0000 is not implicitly convertible to expected type int256.
+// TypeError: (446-458): Operator ** not compatible with types int_const -100...(1227 digits omitted)...0000 and int_const 2
+// TypeError: (446-458): Type int_const -100...(1227 digits omitted)...0000 is not implicitly convertible to expected type int256.
+// TypeError: (472-484): Operator ** not compatible with types int_const 1000...(1226 digits omitted)...0000 and int_const -2
+// TypeError: (472-484): Type int_const 1000...(1226 digits omitted)...0000 is not implicitly convertible to expected type int256.
+// TypeError: (498-511): Operator ** not compatible with types int_const -100...(1227 digits omitted)...0000 and int_const -2
+// TypeError: (498-511): Type int_const -100...(1227 digits omitted)...0000 is not implicitly convertible to expected type int256.
+// TypeError: (525-541): Operator ** not compatible with types int_const 1000...(1226 digits omitted)...0000 and int_const 1000...(1226 digits omitted)...0000
+// TypeError: (525-541): Type int_const 1000...(1226 digits omitted)...0000 is not implicitly convertible to expected type int256.
+// TypeError: (555-572): Operator ** not compatible with types int_const 1000...(1226 digits omitted)...0000 and int_const -100...(1227 digits omitted)...0000
+// TypeError: (555-572): Type int_const 1000...(1226 digits omitted)...0000 is not implicitly convertible to expected type int256.
+// TypeError: (586-603): Operator ** not compatible with types int_const -100...(1227 digits omitted)...0000 and int_const 1000...(1226 digits omitted)...0000
+// TypeError: (586-603): Type int_const -100...(1227 digits omitted)...0000 is not implicitly convertible to expected type int256.
+// TypeError: (617-635): Operator ** not compatible with types int_const -100...(1227 digits omitted)...0000 and int_const -100...(1227 digits omitted)...0000
+// TypeError: (617-635): Type int_const -100...(1227 digits omitted)...0000 is not implicitly convertible to expected type int256.
diff --git a/test/libsolidity/syntaxTests/types/rational_number_literal_limit_1.sol b/test/libsolidity/syntaxTests/types/rational_number_literal_limit_1.sol
new file mode 100644
index 00000000..233857a3
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_literal_limit_1.sol
@@ -0,0 +1,9 @@
+contract c {
+    function bignum() public {
+        uint256 a;
+        a = 1e1233 / 1e1233; // 1e1233 is still fine
+        a = 1e1234; // 1e1234 is too big
+    }
+}
+// ----
+// TypeError: (128-134): Invalid literal value.
diff --git a/test/libsolidity/syntaxTests/types/rational_number_literal_limit_2.sol b/test/libsolidity/syntaxTests/types/rational_number_literal_limit_2.sol
new file mode 100644
index 00000000..16673924
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_literal_limit_2.sol
@@ -0,0 +1,9 @@
+contract c {
+    function bignum() public {
+        uint a;
+        a = 134562324532464234452335168163516E1200 / 134562324532464234452335168163516E1200; // still fine
+        a = 1345623245324642344523351681635168E1200; // too large
+    }
+}
+// ----
+// TypeError: (179-218): Invalid literal value.
diff --git a/test/libsolidity/syntaxTests/types/rational_number_literal_limit_3.sol b/test/libsolidity/syntaxTests/types/rational_number_literal_limit_3.sol
new file mode 100644
index 00000000..5a696171
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_literal_limit_3.sol
@@ -0,0 +1,9 @@
+contract c {
+    function bignum() public {
+        uint a;
+        a = 134562324532464.234452335168163517E1200 / 134562324532464.234452335168163517E1200; // still fine
+        a = 134562324532464.2344523351681635177E1200; // too large
+    }
+}
+// ----
+// TypeError: (181-221): Invalid literal value.
diff --git a/test/libsolidity/syntaxTests/types/rational_number_mul_limit.sol b/test/libsolidity/syntaxTests/types/rational_number_mul_limit.sol
new file mode 100644
index 00000000..bbed94b5
--- /dev/null
+++ b/test/libsolidity/syntaxTests/types/rational_number_mul_limit.sol
@@ -0,0 +1,9 @@
+contract c {
+    function f() public pure {
+        int a;
+        a = (1<<4095)*(1<<4095);
+    }
+}
+// ----
+// TypeError: (71-90): Operator * not compatible with types int_const 5221...(1225 digits omitted)...5168 and int_const 5221...(1225 digits omitted)...5168
+// TypeError: (71-90): Type int_const 5221...(1225 digits omitted)...5168 is not implicitly convertible to expected type int256.