Merge pull request #5240 from ethereum/limitDispenserSize

[Yul] Limit name length created by dispenser

8 files changed, 97 insertions, 25 deletions

diff --git a/libyul/optimiser/Disambiguator.h b/libyul/optimiser/Disambiguator.h
index e16ebfbf..74a491ab 100644
--- a/libyul/optimiser/Disambiguator.h
+++ b/libyul/optimiser/Disambiguator.h
@@ -47,9 +47,8 @@ public:
 		solidity::assembly::AsmAnalysisInfo const& _analysisInfo,
 		std::set<std::string> const& _externallyUsedIdentifiers = {}
 	):
-		m_info(_analysisInfo), m_externallyUsedIdentifiers(_externallyUsedIdentifiers)
+		m_info(_analysisInfo), m_externallyUsedIdentifiers(_externallyUsedIdentifiers), m_nameDispenser(m_externallyUsedIdentifiers)
 	{
-		m_nameDispenser.m_usedNames = m_externallyUsedIdentifiers;
 	}
 
 protected:
diff --git a/libyul/optimiser/FullInliner.cpp b/libyul/optimiser/FullInliner.cpp
index aa069506..ce71eda5 100644
--- a/libyul/optimiser/FullInliner.cpp
+++ b/libyul/optimiser/FullInliner.cpp
@@ -41,11 +41,10 @@ using namespace dev::yul;
 using namespace dev::solidity;
 
 FullInliner::FullInliner(Block& _ast):
-	m_ast(_ast)
+	m_ast(_ast), m_nameDispenser(_ast)
 {
 	assertThrow(m_ast.statements.size() >= 1, OptimizerException, "");
 	assertThrow(m_ast.statements.front().type() == typeid(Block), OptimizerException, "");
-	m_nameDispenser.m_usedNames = NameCollector(m_ast).names();
 
 	// Determine constants
 	SSAValueTracker tracker;
@@ -157,7 +156,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC
 	// helper function to create a new variable that is supposed to model
 	// an existing variable.
 	auto newVariable = [&](TypedName const& _existingVariable, Expression* _value) {
-		string newName = m_nameDispenser.newName(function.name + "_" + _existingVariable.name);
+		string newName = m_nameDispenser.newName(_existingVariable.name, function.name);
 		variableReplacements[_existingVariable.name] = newName;
 		VariableDeclaration varDecl{_funCall.location, {{_funCall.location, newName, _existingVariable.type}}, {}};
 		if (_value)
@@ -170,7 +169,7 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC
 	for (auto const& var: function.returnVariables)
 		newVariable(var, nullptr);
 
-	Statement newBody = BodyCopier(m_nameDispenser, function.name + "_", variableReplacements)(function.body);
+	Statement newBody = BodyCopier(m_nameDispenser, function.name, variableReplacements)(function.body);
 	newStatements += std::move(boost::get<Block>(newBody).statements);
 
 	boost::apply_visitor(GenericFallbackVisitor<Assignment, VariableDeclaration>{
@@ -203,15 +202,10 @@ vector<Statement> InlineModifier::performInline(Statement& _statement, FunctionC
 	return newStatements;
 }
 
-string InlineModifier::newName(string const& _prefix)
-{
-	return m_nameDispenser.newName(_prefix);
-}
-
 Statement BodyCopier::operator()(VariableDeclaration const& _varDecl)
 {
 	for (auto const& var: _varDecl.variables)
-		m_variableReplacements[var.name] = m_nameDispenser.newName(m_varNamePrefix + var.name);
+		m_variableReplacements[var.name] = m_nameDispenser.newName(var.name, m_varNamePrefix);
 	return ASTCopier::operator()(_varDecl);
 }
 
diff --git a/libyul/optimiser/FullInliner.h b/libyul/optimiser/FullInliner.h
index 513ffc93..cd59ab46 100644
--- a/libyul/optimiser/FullInliner.h
+++ b/libyul/optimiser/FullInliner.h
@@ -116,8 +116,6 @@ private:
 	boost::optional<std::vector<Statement>> tryInlineStatement(Statement& _statement);
 	std::vector<Statement> performInline(Statement& _statement, FunctionCall& _funCall);
 
-	std::string newName(std::string const& _prefix);
-
 	std::string m_currentFunction;
 	FullInliner& m_driver;
 	NameDispenser& m_nameDispenser;
diff --git a/libyul/optimiser/NameDispenser.cpp b/libyul/optimiser/NameDispenser.cpp
index f7385471..d3f10bc2 100644
--- a/libyul/optimiser/NameDispenser.cpp
+++ b/libyul/optimiser/NameDispenser.cpp
@@ -20,18 +20,43 @@
 
 #include <libyul/optimiser/NameDispenser.h>
 
+#include <libyul/optimiser/NameCollector.h>
+
+#include <libsolidity/inlineasm/AsmData.h>
+
 using namespace std;
 using namespace dev;
 using namespace dev::yul;
 
-string NameDispenser::newName(string const& _prefix)
+NameDispenser::NameDispenser(Block const& _ast):
+	NameDispenser(NameCollector(_ast).names())
+{
+}
+
+NameDispenser::NameDispenser(set<string> _usedNames):
+	m_usedNames(std::move(_usedNames))
+{
+}
+
+string NameDispenser::newName(string const& _nameHint, string const& _context)
+{
+	// Shortening rules: Use a suffix of _prefix and a prefix of _context.
+	string prefix = _nameHint;
+
+	if (!_context.empty())
+		prefix = _context.substr(0, 10) + "_" + prefix;
+
+	return newNameInternal(prefix);
+}
+
+string NameDispenser::newNameInternal(string const& _nameHint)
 {
-	string name = _prefix;
 	size_t suffix = 0;
+	string name = _nameHint;
 	while (name.empty() || m_usedNames.count(name))
 	{
 		suffix++;
-		name = _prefix + "_" + to_string(suffix);
+		name = _nameHint + "_" + to_string(suffix);
 	}
 	m_usedNames.insert(name);
 	return name;
diff --git a/libyul/optimiser/NameDispenser.h b/libyul/optimiser/NameDispenser.h
index 64ec318f..5fbf5f8e 100644
--- a/libyul/optimiser/NameDispenser.h
+++ b/libyul/optimiser/NameDispenser.h
@@ -19,6 +19,8 @@
  */
 #pragma once
 
+#include <libyul/ASTDataForward.h>
+
 #include <set>
 #include <string>
 
@@ -27,9 +29,29 @@ namespace dev
 namespace yul
 {
 
-struct NameDispenser
+/**
+ * Optimizer component that can be used to generate new names that
+ * do not conflict with existing names.
+ *
+ * Tries to keep names short and appends decimals to disambiguate.
+ */
+class NameDispenser
 {
-	std::string newName(std::string const& _prefix);
+public:
+	/// Initialize the name dispenser with all the names used in the given AST.
+	explicit NameDispenser(Block const& _ast);
+	/// Initialize the name dispenser with the given used names.
+	explicit NameDispenser(std::set<std::string> _usedNames);
+
+	/// @returns a currently unused name that should be similar to _nameHint
+	/// and prefixed by _context if present.
+	/// If the resulting name would be too long, trims the context at the end
+	/// and the name hint at the start.
+	std::string newName(std::string const& _nameHint, std::string const& _context = {});
+
+private:
+	std::string newNameInternal(std::string const& _nameHint);
+
 	std::set<std::string> m_usedNames;
 };
 
diff --git a/test/libyul/YulOptimizerTest.cpp b/test/libyul/YulOptimizerTest.cpp
index 8e4771c8..a89711a1 100644
--- a/test/libyul/YulOptimizerTest.cpp
+++ b/test/libyul/YulOptimizerTest.cpp
@@ -106,8 +106,7 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 	}
 	else if (m_optimizerStep == "expressionSplitter")
 	{
-		NameDispenser nameDispenser;
-		nameDispenser.m_usedNames = NameCollector(*m_ast).names();
+		NameDispenser nameDispenser(*m_ast);
 		ExpressionSplitter{nameDispenser}(*m_ast);
 	}
 	else if (m_optimizerStep == "functionGrouper")
@@ -130,8 +129,7 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 		disambiguate();
 		(FunctionHoister{})(*m_ast);
 		(FunctionGrouper{})(*m_ast);
-		NameDispenser nameDispenser;
-		nameDispenser.m_usedNames = NameCollector(*m_ast).names();
+		NameDispenser nameDispenser(*m_ast);
 		ExpressionSplitter{nameDispenser}(*m_ast);
 		FullInliner(*m_ast).run();
 		ExpressionJoiner::run(*m_ast);
@@ -155,8 +153,7 @@ bool YulOptimizerTest::run(ostream& _stream, string const& _linePrefix, bool con
 	else if (m_optimizerStep == "fullSimplify")
 	{
 		disambiguate();
-		NameDispenser nameDispenser;
-		nameDispenser.m_usedNames = NameCollector(*m_ast).names();
+		NameDispenser nameDispenser(*m_ast);
 		ExpressionSplitter{nameDispenser}(*m_ast);
 		CommonSubexpressionEliminator{}(*m_ast);
 		ExpressionSimplifier::run(*m_ast);
diff --git a/test/libyul/yulOptimizerTests/disambiguator/long_names.yul b/test/libyul/yulOptimizerTests/disambiguator/long_names.yul
new file mode 100644
index 00000000..933e1e8f
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/disambiguator/long_names.yul
@@ -0,0 +1,12 @@
+// yul
+{ { let aanteuhdaoneudbrgkjiuaothduiathudaoeuh:u256 } { let aanteuhdaoneudbrgkjiuaothduiathudaoeuh:u256 } }
+// ----
+// disambiguator
+// {
+//     {
+//         let aanteuhdaoneudbrgkjiuaothduiathudaoeuh:u256
+//     }
+//     {
+//         let aanteuhdaoneudbrgkjiuaothduiathudaoeuh_1:u256
+//     }
+// }
diff --git a/test/libyul/yulOptimizerTests/fullInliner/long_names.yul b/test/libyul/yulOptimizerTests/fullInliner/long_names.yul
new file mode 100644
index 00000000..644e9126
--- /dev/null
+++ b/test/libyul/yulOptimizerTests/fullInliner/long_names.yul
@@ -0,0 +1,25 @@
+{
+	function verylongfunctionname(verylongvariablename) -> verylongvariablename2 {
+		verylongvariablename2 := add(verylongvariablename, verylongvariablename)
+	}
+	// same long name
+	let verylongvariablename2 := 3
+	mstore(0, verylongfunctionname(verylongvariablename2))
+	mstore(1, verylongvariablename2)
+}
+// ----
+// fullInliner
+// {
+//     {
+//         let verylongvariablename2_1 := 3
+//         let verylongfu_verylongvariablename := verylongvariablename2_1
+//         let verylongfu_verylongvariablename2
+//         verylongfu_verylongvariablename2 := add(verylongfu_verylongvariablename, verylongfu_verylongvariablename)
+//         mstore(0, verylongfu_verylongvariablename2)
+//         mstore(1, verylongvariablename2_1)
+//     }
+//     function verylongfunctionname(verylongvariablename) -> verylongvariablename2
+//     {
+//         verylongvariablename2 := add(verylongvariablename, verylongvariablename)
+//     }
+// }