Merge pull request #5793 from ethereum/switchLiteralSameValue

[Yul] Require equal types for switch cases and detect duplicates by number value.

16 files changed, 166 insertions, 30 deletions

diff --git a/docs/yul.rst b/docs/yul.rst
index 31555742..627e6e7c 100644
--- a/docs/yul.rst
+++ b/docs/yul.rst
@@ -130,9 +130,10 @@ Restrictions on the Grammar
 ---------------------------
 
 Switches must have at least one case (including the default case).
-If all possible values of the expression is covered, the default case should
-not be allowed (i.e. a switch with a ``bool`` expression and having both a
-true and false case should not allow a default case).
+If all possible values of the expression are covered, a default case should
+not be allowed (i.e. a switch with a ``bool`` expression that has both a
+true and a false case should not allow a default case). All case values need to
+have the same type.
 
 Every expression evaluates to zero or more values. Identifiers and Literals
 evaluate to exactly
diff --git a/libyul/AsmAnalysis.cpp b/libyul/AsmAnalysis.cpp
index 6a7b2b61..a5552c51 100644
--- a/libyul/AsmAnalysis.cpp
+++ b/libyul/AsmAnalysis.cpp
@@ -24,6 +24,7 @@
 #include <libyul/AsmScopeFiller.h>
 #include <libyul/AsmScope.h>
 #include <libyul/AsmAnalysisInfo.h>
+#include <libyul/Utilities.h>
 
 #include <liblangutil/ErrorReporter.h>
 
@@ -390,7 +391,29 @@ bool AsmAnalyzer::operator()(Switch const& _switch)
 	if (!expectExpression(*_switch.expression))
 		success = false;
 
-	set<tuple<LiteralKind, YulString>> cases;
+	if (m_dialect->flavour == AsmFlavour::Yul)
+	{
+		YulString caseType;
+		bool mismatchingTypes = false;
+		for (auto const& _case: _switch.cases)
+			if (_case.value)
+			{
+				if (caseType.empty())
+					caseType = _case.value->type;
+				else if (caseType != _case.value->type)
+				{
+					mismatchingTypes = true;
+					break;
+				}
+			}
+		if (mismatchingTypes)
+			m_errorReporter.typeError(
+				_switch.location,
+				"Switch cases have non-matching types."
+			);
+	}
+
+	set<Literal const*, Less<Literal*>> cases;
 	for (auto const& _case: _switch.cases)
 	{
 		if (_case.value)
@@ -404,12 +427,11 @@ bool AsmAnalyzer::operator()(Switch const& _switch)
 			m_stackHeight--;
 
 			/// Note: the parser ensures there is only one default case
-			auto val = make_tuple(_case.value->kind, _case.value->value);
-			if (!cases.insert(val).second)
+			if (!cases.insert(_case.value.get()).second)
 			{
 				m_errorReporter.declarationError(
 					_case.location,
-					"Duplicate case defined"
+					"Duplicate case defined."
 				);
 				success = false;
 			}
diff --git a/libyul/CMakeLists.txt b/libyul/CMakeLists.txt
index 52c4ac8e..ad9812bd 100644
--- a/libyul/CMakeLists.txt
+++ b/libyul/CMakeLists.txt
@@ -20,6 +20,8 @@ add_library(yul
 	Object.h
 	ObjectParser.cpp
 	ObjectParser.h
+	Utilities.cpp
+	Utilities.h
 	YulString.h
 	backends/evm/AbstractAssembly.h
 	backends/evm/EVMAssembly.cpp
@@ -68,6 +70,8 @@ add_library(yul
 	optimiser/NameCollector.h
 	optimiser/NameDispenser.cpp
 	optimiser/NameDispenser.h
+	optimiser/OptimizerUtilities.cpp
+	optimiser/OptimizerUtilities.h
 	optimiser/RedundantAssignEliminator.cpp
 	optimiser/RedundantAssignEliminator.h
 	optimiser/Rematerialiser.cpp
@@ -90,8 +94,6 @@ add_library(yul
 	optimiser/SyntacticalEquality.h
 	optimiser/UnusedPruner.cpp
 	optimiser/UnusedPruner.h
-	optimiser/Utilities.cpp
-	optimiser/Utilities.h
 	optimiser/VarDeclInitializer.cpp
 	optimiser/VarDeclInitializer.h
 )
diff --git a/libyul/Utilities.cpp b/libyul/Utilities.cpp
new file mode 100644
index 00000000..e5f4e517
--- /dev/null
+++ b/libyul/Utilities.cpp
@@ -0,0 +1,50 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Some useful snippets for the optimiser.
+ */
+
+#include <libyul/Utilities.h>
+
+#include <libyul/AsmData.h>
+#include <libyul/Exceptions.h>
+
+#include <libdevcore/CommonData.h>
+
+using namespace std;
+using namespace dev;
+using namespace yul;
+
+u256 yul::valueOfNumberLiteral(Literal const& _literal)
+{
+	assertThrow(_literal.kind == LiteralKind::Number, OptimizerException, "");
+	std::string const& literalString = _literal.value.str();
+	assertThrow(isValidDecimal(literalString) || isValidHex(literalString), OptimizerException, "");
+	return u256(literalString);
+}
+
+template<>
+bool Less<Literal>::operator()(Literal const& _lhs, Literal const& _rhs) const
+{
+	if (std::make_tuple(_lhs.kind, _lhs.type) != std::make_tuple(_rhs.kind, _rhs.type))
+		return std::make_tuple(_lhs.kind, _lhs.type) < std::make_tuple(_rhs.kind, _rhs.type);
+
+	if (_lhs.kind == LiteralKind::Number)
+		return valueOfNumberLiteral(_lhs) < valueOfNumberLiteral(_rhs);
+	else
+		return _lhs.value < _rhs.value;
+}
diff --git a/libyul/Utilities.h b/libyul/Utilities.h
new file mode 100644
index 00000000..288bc6ee
--- /dev/null
+++ b/libyul/Utilities.h
@@ -0,0 +1,59 @@
+/*
+	This file is part of solidity.
+
+	solidity is free software: you can redistribute it and/or modify
+	it under the terms of the GNU General Public License as published by
+	the Free Software Foundation, either version 3 of the License, or
+	(at your option) any later version.
+
+	solidity is distributed in the hope that it will be useful,
+	but WITHOUT ANY WARRANTY; without even the implied warranty of
+	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+	GNU General Public License for more details.
+
+	You should have received a copy of the GNU General Public License
+	along with solidity.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * Small useful snippets for the optimiser.
+ */
+
+#pragma once
+
+#include <libdevcore/Common.h>
+#include <libyul/AsmDataForward.h>
+
+namespace yul
+{
+
+dev::u256 valueOfNumberLiteral(Literal const& _literal);
+
+/**
+ * Linear order on Yul AST nodes.
+ *
+ * Defines a linear order on Yul AST nodes to be used in maps and sets.
+ * Note: the order is total and deterministic, but independent of the semantics, e.g.
+ * it is not guaranteed that the false Literal is "less" than the true Literal.
+ */
+template<typename T>
+struct Less
+{
+	bool operator()(T const& _lhs, T const& _rhs) const;
+};
+
+template<typename T>
+struct Less<T*>
+{
+	bool operator()(T const* _lhs, T const* _rhs) const
+	{
+		if (_lhs && _rhs)
+			return Less<T>{}(*_lhs, *_rhs);
+		else
+			return _lhs < _rhs;
+	}
+};
+
+template<> bool Less<Literal>::operator()(Literal const& _lhs, Literal const& _rhs) const;
+extern template struct Less<Literal>;
+
+}
diff --git a/libyul/optimiser/ExpressionJoiner.cpp b/libyul/optimiser/ExpressionJoiner.cpp
index de2b5d53..02ac4e45 100644
--- a/libyul/optimiser/ExpressionJoiner.cpp
+++ b/libyul/optimiser/ExpressionJoiner.cpp
@@ -22,7 +22,7 @@
 #include <libyul/optimiser/ExpressionJoiner.h>
 
 #include <libyul/optimiser/NameCollector.h>
-#include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/OptimizerUtilities.h>
 #include <libyul/Exceptions.h>
 #include <libyul/AsmData.h>
 
diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp
index 1f267f96..dd969faf 100644
--- a/libyul/optimiser/FullInliner.cpp
+++ b/libyul/optimiser/FullInliner.cpp
@@ -23,7 +23,7 @@
 #include <libyul/optimiser/ASTCopier.h>
 #include <libyul/optimiser/ASTWalker.h>
 #include <libyul/optimiser/NameCollector.h>
-#include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/OptimizerUtilities.h>
 #include <libyul/optimiser/Metrics.h>
 #include <libyul/optimiser/SSAValueTracker.h>
 #include <libyul/Exceptions.h>
diff --git a/libyul/optimiser/FunctionHoister.cpp b/libyul/optimiser/FunctionHoister.cpp
index bd1c781b..4863b94d 100644
--- a/libyul/optimiser/FunctionHoister.cpp
+++ b/libyul/optimiser/FunctionHoister.cpp
@@ -21,7 +21,7 @@
  */
 
 #include <libyul/optimiser/FunctionHoister.h>
-#include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/OptimizerUtilities.h>
 #include <libyul/AsmData.h>
 
 #include <libdevcore/CommonData.h>
diff --git a/libyul/optimiser/InlinableExpressionFunctionFinder.cpp b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
index 662cdf25..f57faa7c 100644
--- a/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
+++ b/libyul/optimiser/InlinableExpressionFunctionFinder.cpp
@@ -20,7 +20,7 @@
 
 #include <libyul/optimiser/InlinableExpressionFunctionFinder.h>
 
-#include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/OptimizerUtilities.h>
 #include <libyul/AsmData.h>
 
 using namespace std;
diff --git a/libyul/optimiser/Utilities.cpp b/libyul/optimiser/OptimizerUtilities.cpp
index b3b580d5..f9571a4c 100644
--- a/libyul/optimiser/Utilities.cpp
+++ b/libyul/optimiser/OptimizerUtilities.cpp
@@ -1,4 +1,4 @@
-/*(
+/*
 	This file is part of solidity.
 
 	solidity is free software: you can redistribute it and/or modify
@@ -18,10 +18,9 @@
  * Some useful snippets for the optimiser.
  */
 
-#include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/OptimizerUtilities.h>
 
 #include <libyul/AsmData.h>
-#include <libyul/Exceptions.h>
 
 #include <libdevcore/CommonData.h>
 
@@ -38,11 +37,3 @@ void yul::removeEmptyBlocks(Block& _block)
 	};
 	boost::range::remove_erase_if(_block.statements, isEmptyBlock);
 }
-
-u256 yul::valueOfNumberLiteral(Literal const& _literal)
-{
-	assertThrow(_literal.kind == LiteralKind::Number, OptimizerException, "");
-	std::string const& literalString = _literal.value.str();
-	assertThrow(isValidDecimal(literalString) || isValidHex(literalString), OptimizerException, "");
-	return u256(literalString);
-}
diff --git a/libyul/optimiser/Utilities.h b/libyul/optimiser/OptimizerUtilities.h
index 1cfff62b..449a1bc0 100644
--- a/libyul/optimiser/Utilities.h
+++ b/libyul/optimiser/OptimizerUtilities.h
@@ -29,6 +29,4 @@ namespace yul
 /// Removes statements that are just empty blocks (non-recursive).
 void removeEmptyBlocks(Block& _block);
 
-dev::u256 valueOfNumberLiteral(Literal const& _literal);
-
 }
diff --git a/libyul/optimiser/SimplificationRules.cpp b/libyul/optimiser/SimplificationRules.cpp
index da9c7d9d..037dad97 100644
--- a/libyul/optimiser/SimplificationRules.cpp
+++ b/libyul/optimiser/SimplificationRules.cpp
@@ -20,11 +20,11 @@
 
 #include <libyul/optimiser/SimplificationRules.h>
 
-#include <libyul/optimiser/Utilities.h>
 #include <libyul/optimiser/ASTCopier.h>
 #include <libyul/optimiser/Semantics.h>
 #include <libyul/optimiser/SyntacticalEquality.h>
 #include <libyul/AsmData.h>
+#include <libyul/Utilities.h>
 
 #include <libevmasm/RuleList.h>
 
diff --git a/libyul/optimiser/StructuralSimplifier.cpp b/libyul/optimiser/StructuralSimplifier.cpp
index bdf4cb2a..8d7dcd57 100644
--- a/libyul/optimiser/StructuralSimplifier.cpp
+++ b/libyul/optimiser/StructuralSimplifier.cpp
@@ -16,8 +16,8 @@
 */
 #include <libyul/optimiser/StructuralSimplifier.h>
 #include <libyul/optimiser/Semantics.h>
-#include <libyul/optimiser/Utilities.h>
 #include <libyul/AsmData.h>
+#include <libyul/Utilities.h>
 #include <libdevcore/CommonData.h>
 #include <libdevcore/Visitor.h>
 
diff --git a/libyul/optimiser/UnusedPruner.cpp b/libyul/optimiser/UnusedPruner.cpp
index 53c412e3..365b255c 100644
--- a/libyul/optimiser/UnusedPruner.cpp
+++ b/libyul/optimiser/UnusedPruner.cpp
@@ -22,7 +22,7 @@
 
 #include <libyul/optimiser/NameCollector.h>
 #include <libyul/optimiser/Semantics.h>
-#include <libyul/optimiser/Utilities.h>
+#include <libyul/optimiser/OptimizerUtilities.h>
 #include <libyul/Exceptions.h>
 #include <libyul/AsmData.h>
 
diff --git a/test/libsolidity/InlineAssembly.cpp b/test/libsolidity/InlineAssembly.cpp
index b6986041..92e4dcf6 100644
--- a/test/libsolidity/InlineAssembly.cpp
+++ b/test/libsolidity/InlineAssembly.cpp
@@ -316,7 +316,7 @@ BOOST_AUTO_TEST_CASE(switch_no_cases)
 
 BOOST_AUTO_TEST_CASE(switch_duplicate_case)
 {
-	CHECK_PARSE_ERROR("{ switch 42 case 1 {} case 1 {} default {} }", DeclarationError, "Duplicate case defined");
+	CHECK_PARSE_ERROR("{ switch 42 case 1 {} case 1 {} default {} }", DeclarationError, "Duplicate case defined.");
 }
 
 BOOST_AUTO_TEST_CASE(switch_invalid_expression)
diff --git a/test/libyul/Parser.cpp b/test/libyul/Parser.cpp
index 897f18ae..84f5c14b 100644
--- a/test/libyul/Parser.cpp
+++ b/test/libyul/Parser.cpp
@@ -304,6 +304,19 @@ BOOST_AUTO_TEST_CASE(if_statement_invalid)
 	BOOST_CHECK(successParse("{ if 42:u256 { } }"));
 }
 
+BOOST_AUTO_TEST_CASE(switch_case_types)
+{
+	CHECK_ERROR("{ switch 0:u256 case 0:u256 {} case 1:u32 {} }", TypeError, "Switch cases have non-matching types.");
+	// The following should be an error in the future, but this is not yet detected.
+	BOOST_CHECK(successParse("{ switch 0:u256 case 0:u32 {} case 1:u32 {} }"));
+}
+
+BOOST_AUTO_TEST_CASE(switch_duplicate_case)
+{
+	CHECK_ERROR("{ switch 0:u256 case 0:u256 {} case 0x0:u256 {} }", DeclarationError, "Duplicate case defined.");
+	BOOST_CHECK(successParse("{ switch 0:u256 case 42:u256 {} case 0x42:u256 {} }"));
+}
+
 BOOST_AUTO_TEST_CASE(builtins_parser)
 {
 	struct SimpleDialect: public Dialect