Remove non-determinism in missing code queue.

4 files changed, 95 insertions, 37 deletions

diff --git a/libsolidity/codegen/Compiler.cpp b/libsolidity/codegen/Compiler.cpp
index d4c94297..1675f659 100644
--- a/libsolidity/codegen/Compiler.cpp
+++ b/libsolidity/codegen/Compiler.cpp
@@ -58,7 +58,7 @@ void Compiler::compileContract(
 		CompilerContext::LocationSetter locationSetterRunTime(m_context, _contract);
 		initializeContext(_contract, _contracts);
 		appendFunctionSelector(_contract);
-		appendFunctionsWithoutCode();
+		appendMissingFunctions();
 	}
 
 	// Swap the runtime context with the creation-time context
@@ -95,7 +95,7 @@ void Compiler::compileClone(
 	m_context << Instruction::DUP1 << runtimeSub << u256(0) << Instruction::CODECOPY;
 	m_context << u256(0) << Instruction::RETURN;
 
-	appendFunctionsWithoutCode();
+	appendMissingFunctions();
 
 	if (m_optimize)
 		m_context.optimise(m_optimizeRuns);
@@ -168,7 +168,7 @@ void Compiler::packIntoContractCreator(ContractDefinition const& _contract, Comp
 	m_context << u256(0) << Instruction::RETURN;
 
 	// note that we have to include the functions again because of absolute jump labels
-	appendFunctionsWithoutCode();
+	appendMissingFunctions();
 }
 
 void Compiler::appendBaseConstructor(FunctionDefinition const& _constructor)
@@ -778,17 +778,13 @@ bool Compiler::visit(PlaceholderStatement const& _placeholderStatement)
 	return true;
 }
 
-void Compiler::appendFunctionsWithoutCode()
+void Compiler::appendMissingFunctions()
 {
-	set<Declaration const*> functions = m_context.functionsWithoutCode();
-	while (!functions.empty())
+	while (Declaration const* function = m_context.nextFunctionToCompile())
 	{
-		for (Declaration const* function: functions)
-		{
-			m_context.setStackOffset(0);
-			function->accept(*this);
-		}
-		functions = m_context.functionsWithoutCode();
+		m_context.setStackOffset(0);
+		function->accept(*this);
+		solAssert(m_context.nextFunctionToCompile() != function, "Compiled the wrong function?");
 	}
 }
 
diff --git a/libsolidity/codegen/Compiler.h b/libsolidity/codegen/Compiler.h
index 68ad904a..69040253 100644
--- a/libsolidity/codegen/Compiler.h
+++ b/libsolidity/codegen/Compiler.h
@@ -107,7 +107,7 @@ private:
 	virtual bool visit(PlaceholderStatement const&) override;
 
 	/// Repeatedly visits all function which are referenced but which are not compiled yet.
-	void appendFunctionsWithoutCode();
+	void appendMissingFunctions();
 
 	/// Appends one layer of function modifier code of the current function, or the function
 	/// body itself if the last modifier was reached.
diff --git a/libsolidity/codegen/CompilerContext.cpp b/libsolidity/codegen/CompilerContext.cpp
index 7810288e..53c2da05 100644
--- a/libsolidity/codegen/CompilerContext.cpp
+++ b/libsolidity/codegen/CompilerContext.cpp
@@ -50,7 +50,7 @@ void CompilerContext::addStateVariable(
 
 void CompilerContext::startFunction(Declaration const& _function)
 {
-	m_functionsWithCode.insert(&_function);
+	m_functionCompilationQueue.startFunction(_function);
 	*this << functionEntryLabel(_function);
 }
 
@@ -81,21 +81,12 @@ bool CompilerContext::isLocalVariable(Declaration const* _declaration) const
 
 eth::AssemblyItem CompilerContext::functionEntryLabel(Declaration const& _declaration)
 {
-	auto res = m_functionEntryLabels.find(&_declaration);
-	if (res == m_functionEntryLabels.end())
-	{
-		eth::AssemblyItem tag(m_asm.newTag());
-		m_functionEntryLabels.insert(make_pair(&_declaration, tag));
-		return tag.tag();
-	}
-	else
-		return res->second.tag();
+	return m_functionCompilationQueue.entryLabel(_declaration, *this);
 }
 
 eth::AssemblyItem CompilerContext::functionEntryLabelIfExists(Declaration const& _declaration) const
 {
-	auto res = m_functionEntryLabels.find(&_declaration);
-	return res == m_functionEntryLabels.end() ? eth::AssemblyItem(eth::UndefinedItem) : res->second.tag();
+	return m_functionCompilationQueue.entryLabelIfExists(_declaration);
 }
 
 eth::AssemblyItem CompilerContext::virtualFunctionEntryLabel(FunctionDefinition const& _function)
@@ -120,13 +111,9 @@ FunctionDefinition const* CompilerContext::nextConstructor(ContractDefinition co
 	return nullptr;
 }
 
-set<Declaration const*> CompilerContext::functionsWithoutCode()
+Declaration const* CompilerContext::nextFunctionToCompile() const
 {
-	set<Declaration const*> functions;
-	for (auto const& it: m_functionEntryLabels)
-		if (m_functionsWithCode.count(it.first) == 0)
-			functions.insert(it.first);
-	return functions;
+	return m_functionCompilationQueue.nextFunctionToCompile();
 }
 
 ModifierDefinition const& CompilerContext::functionModifier(string const& _name) const
@@ -219,5 +206,48 @@ void CompilerContext::updateSourceLocation()
 	m_asm.setSourceLocation(m_visitedNodes.empty() ? SourceLocation() : m_visitedNodes.top()->location());
 }
 
+eth::AssemblyItem CompilerContext::FunctionCompilationQueue::entryLabel(
+	Declaration const& _declaration,
+	CompilerContext& _context
+)
+{
+	auto res = m_entryLabels.find(&_declaration);
+	if (res == m_entryLabels.end())
+	{
+		eth::AssemblyItem tag(_context.newTag());
+		m_entryLabels.insert(make_pair(&_declaration, tag));
+		m_functionsToCompile.push(&_declaration);
+		return tag.tag();
+	}
+	else
+		return res->second.tag();
+
+}
+
+eth::AssemblyItem CompilerContext::FunctionCompilationQueue::entryLabelIfExists(Declaration const& _declaration) const
+{
+	auto res = m_entryLabels.find(&_declaration);
+	return res == m_entryLabels.end() ? eth::AssemblyItem(eth::UndefinedItem) : res->second.tag();
+}
+
+Declaration const* CompilerContext::FunctionCompilationQueue::nextFunctionToCompile() const
+{
+	while (!m_functionsToCompile.empty())
+	{
+		if (m_alreadyCompiledFunctions.count(m_functionsToCompile.front()))
+			m_functionsToCompile.pop();
+		else
+			return m_functionsToCompile.front();
+	}
+	return nullptr;
+}
+
+void CompilerContext::FunctionCompilationQueue::startFunction(Declaration const& _function)
+{
+	if (!m_functionsToCompile.empty() && m_functionsToCompile.front() == &_function)
+		m_functionsToCompile.pop();
+	m_alreadyCompiledFunctions.insert(&_function);
+}
+
 }
 }
diff --git a/libsolidity/codegen/CompilerContext.h b/libsolidity/codegen/CompilerContext.h
index 9368dbcf..5abe59fe 100644
--- a/libsolidity/codegen/CompilerContext.h
+++ b/libsolidity/codegen/CompilerContext.h
@@ -24,6 +24,7 @@
 
 #include <ostream>
 #include <stack>
+#include <queue>
 #include <utility>
 #include <libevmasm/Instruction.h>
 #include <libevmasm/Assembly.h>
@@ -72,8 +73,11 @@ public:
 	eth::AssemblyItem superFunctionEntryLabel(FunctionDefinition const& _function, ContractDefinition const& _base);
 	FunctionDefinition const* nextConstructor(ContractDefinition const& _contract) const;
 
-	/// @returns the set of functions for which we still need to generate code
-	std::set<Declaration const*> functionsWithoutCode();
+	/// @returns the next function in the queue of functions that are still to be compiled
+	/// (i.e. that were referenced during compilation but where we did not yet generate code for).
+	/// Returns nullptr if the queue is empty. Does not remove the function from the queue,
+	/// that will only be done by startFunction below.
+	Declaration const* nextFunctionToCompile() const;
 	/// Resets function specific members, inserts the function entry label and marks the function
 	/// as "having code".
 	void startFunction(Declaration const& _function);
@@ -168,6 +172,38 @@ private:
 	/// Updates source location set in the assembly.
 	void updateSourceLocation();
 
+	/**
+	 * Helper class that manages function labels and ensures that referenced functions are
+	 * compiled in a specific order.
+	 */
+	struct FunctionCompilationQueue
+	{
+		/// @returns the entry label of the given function and creates it if it does not exist yet.
+		/// @param _context compiler context used to create a new tag if needed
+		eth::AssemblyItem entryLabel(Declaration const& _declaration, CompilerContext& _context);
+		/// @returns the entry label of the given function. Might return an AssemblyItem of type
+		/// UndefinedItem if it does not exist yet.
+		eth::AssemblyItem entryLabelIfExists(Declaration const& _declaration) const;
+
+		/// @returns the next function in the queue of functions that are still to be compiled
+		/// (i.e. that were referenced during compilation but where we did not yet generate code for).
+		/// Returns nullptr if the queue is empty. Does not remove the function from the queue,
+		/// that will only be done by startFunction below.
+		Declaration const* nextFunctionToCompile() const;
+		/// Informs the queue that we are about to compile the given function, i.e. removes
+		/// the function from the queue of functions to compile.
+		void startFunction(const Declaration &_function);
+
+		/// Labels pointing to the entry points of functions.
+		std::map<Declaration const*, eth::AssemblyItem> m_entryLabels;
+		/// Set of functions for which we did not yet generate code.
+		std::set<Declaration const*> m_alreadyCompiledFunctions;
+		/// Queue of functions that still need to be compiled (important to be a queue to maintain
+		/// determinism even in the presence of a non-deterministic allocator).
+		/// Mutable because we will throw out some functions earlier than needed.
+		mutable std::queue<Declaration const*> m_functionsToCompile;
+	} m_functionCompilationQueue;
+
 	eth::Assembly m_asm;
 	/// Magic global variables like msg, tx or this, distinguished by type.
 	std::set<Declaration const*> m_magicGlobals;
@@ -177,10 +213,6 @@ private:
 	std::map<Declaration const*, std::pair<u256, unsigned>> m_stateVariables;
 	/// Offsets of local variables on the stack (relative to stack base).
 	std::map<Declaration const*, unsigned> m_localVariables;
-	/// Labels pointing to the entry points of functions.
-	std::map<Declaration const*, eth::AssemblyItem> m_functionEntryLabels;
-	/// Set of functions for which we did not yet generate code.
-	std::set<Declaration const*> m_functionsWithCode;
 	/// List of current inheritance hierarchy from derived to base.
 	std::vector<ContractDefinition const*> m_inheritanceHierarchy;
 	/// Stack of current visited AST nodes, used for location attachment