Structural gas estimator.

5 files changed, 224 insertions, 3 deletions

diff --git a/ASTPrinter.cpp b/ASTPrinter.cpp
index 713059d3..f21ec5e3 100644
--- a/ASTPrinter.cpp
+++ b/ASTPrinter.cpp
@@ -30,8 +30,10 @@ namespace dev
 namespace solidity
 {
 
-ASTPrinter::ASTPrinter(ASTNode const& _ast, string const& _source):
-	m_indentation(0), m_source(_source), m_ast(&_ast)
+ASTPrinter::ASTPrinter(ASTNode const& _ast,
+	string const& _source,
+	StructuralGasEstimator::ASTGasConsumption const& _gasCosts
+): m_indentation(0), m_source(_source), m_ast(&_ast), m_gasCosts(_gasCosts)
 {
 }
 
@@ -503,6 +505,8 @@ void ASTPrinter::endVisit(Literal const&)
 
 void ASTPrinter::printSourcePart(ASTNode const& _node)
 {
+	if (m_gasCosts.count(&_node))
+		*m_ostream << getIndentation() << "   Gas costs: " << m_gasCosts.at(&_node) << endl;
 	if (!m_source.empty())
 	{
 		SourceLocation const& location(_node.getLocation());
diff --git a/ASTPrinter.h b/ASTPrinter.h
index 9494bf8c..dabf6470 100644
--- a/ASTPrinter.h
+++ b/ASTPrinter.h
@@ -24,6 +24,7 @@
 
 #include <ostream>
 #include <libsolidity/ASTVisitor.h>
+#include <libsolidity/StructuralGasEstimator.h>
 
 namespace dev
 {
@@ -38,7 +39,11 @@ class ASTPrinter: public ASTConstVisitor
 public:
 	/// Create a printer for the given abstract syntax tree. If the source is specified,
 	/// the corresponding parts of the source are printed with each node.
-	ASTPrinter(ASTNode const& _ast, std::string const& _source = std::string());
+	ASTPrinter(
+		ASTNode const& _ast,
+		std::string const& _source = std::string(),
+		StructuralGasEstimator::ASTGasConsumption const& _gasCosts = {}
+	);
 	/// Output the string representation of the AST to _stream.
 	void print(std::ostream& _stream);
 
@@ -128,6 +133,7 @@ private:
 	int m_indentation;
 	std::string m_source;
 	ASTNode const* m_ast;
+	StructuralGasEstimator::ASTGasConsumption m_gasCosts;
 	std::ostream* m_ostream;
 };
 
diff --git a/ASTVisitor.h b/ASTVisitor.h
index ec22bd44..fbda5079 100644
--- a/ASTVisitor.h
+++ b/ASTVisitor.h
@@ -23,6 +23,8 @@
 #pragma once
 
 #include <string>
+#include <functional>
+#include <vector>
 #include <libsolidity/AST.h>
 
 namespace dev
@@ -218,5 +220,47 @@ protected:
 	virtual void endVisitNode(ASTNode const&) { }
 };
 
+/**
+ * Utility class that visits the AST in depth-first order and calls a function on each node and each edge.
+ * Child nodes are only visited if the node callback of the parent returns true.
+ * The node callback of a parent is called before any edge or node callback involving the children.
+ * The edge callbacks of all children are called before the edge callback of the parent.
+ * This way, the node callback can be used as an initializing callback and the edge callbacks can be
+ * used to compute a "reduce" function.
+ */
+class ASTReduce: public ASTConstVisitor
+{
+public:
+	/**
+	 * Constructs a new ASTReduce object with the given callback functions.
+	 * @param _onNode called for each node, before its child edges and nodes, should return true to descend deeper
+	 * @param _onEdge called for each edge with (parent, child)
+	 */
+	ASTReduce(
+		std::function<bool(ASTNode const&)> _onNode,
+		std::function<void(ASTNode const&, ASTNode const&)> _onEdge
+	): m_onNode(_onNode), m_onEdge(_onEdge)
+	{
+	}
+
+protected:
+	bool visitNode(ASTNode const& _node) override
+	{
+		m_parents.push_back(&_node);
+		return m_onNode(_node);
+	}
+	void endVisitNode(ASTNode const& _node) override
+	{
+		m_parents.pop_back();
+		if (!m_parents.empty())
+			m_onEdge(*m_parents.back(), _node);
+	}
+
+private:
+	std::vector<ASTNode const*> m_parents;
+	std::function<bool(ASTNode const&)> m_onNode;
+	std::function<void(ASTNode const&, ASTNode const&)> m_onEdge;
+};
+
 }
 }
diff --git a/StructuralGasEstimator.cpp b/StructuralGasEstimator.cpp
new file mode 100644
index 00000000..2cf8c2a8
--- /dev/null
+++ b/StructuralGasEstimator.cpp
@@ -0,0 +1,108 @@
+/*
+	This file is part of cpp-ethereum.
+
+	cpp-ethereum 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.
+
+	cpp-ethereum 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 cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * @author Christian <c@ethdev.com>
+ * @date 2015
+ * Gas consumption estimator working alongside the AST.
+ */
+
+#include "StructuralGasEstimator.h"
+#include <map>
+#include <functional>
+#include <libsolidity/AST.h>
+#include <libsolidity/ASTVisitor.h>
+
+using namespace std;
+using namespace dev;
+using namespace dev::eth;
+using namespace dev::solidity;
+
+map<ASTNode const*, GasMeter::GasConsumption[2]> StructuralGasEstimator::performEstimation(
+	AssemblyItems const& _items,
+	vector<ASTNode const*> const& _ast
+)
+{
+	map<SourceLocation, GasMeter::GasConsumption> particularCosts;
+	GasMeter meter;
+
+	for (auto const& item: _items)
+		particularCosts[item.getLocation()] += meter.estimateMax(item);
+
+	map<ASTNode const*, GasMeter::GasConsumption[2]> gasCosts;
+	auto onNode = [&](ASTNode const& _node)
+	{
+		gasCosts[&_node][0] = gasCosts[&_node][1] = particularCosts[_node.getLocation()];
+		return true;
+	};
+	auto onEdge = [&](ASTNode const& _parent, ASTNode const& _child)
+	{
+		gasCosts[&_parent][1] += gasCosts[&_child][1];
+	};
+	ASTReduce folder(onNode, onEdge);
+	for (ASTNode const* ast: _ast)
+		ast->accept(folder);
+
+	return gasCosts;
+}
+
+map<ASTNode const*, GasMeter::GasConsumption> StructuralGasEstimator::breakToStatementLevel(
+	map<ASTNode const*, GasMeter::GasConsumption[2]> const& _gasCosts,
+	vector<ASTNode const*> const& _roots
+)
+{
+	// first pass: statementDepth[node] is the distance from the deepend statement to node
+	// in direction of the tree root (or undefined if not possible)
+	map<ASTNode const*, int> statementDepth;
+	auto onNodeFirstPass = [&](ASTNode const& _node)
+	{
+		if (dynamic_cast<Statement const*>(&_node))
+			statementDepth[&_node] = 0;
+		return true;
+	};
+	auto onEdgeFirstPass = [&](ASTNode const& _parent, ASTNode const& _child)
+	{
+		if (statementDepth.count(&_child))
+			statementDepth[&_parent] = max(statementDepth[&_parent], statementDepth[&_child] + 1);
+	};
+	ASTReduce firstPass(onNodeFirstPass, onEdgeFirstPass);
+	for (ASTNode const* node: _roots)
+		node->accept(firstPass);
+
+	// we use the location of a node if
+	//  - its statement depth is 0 or
+	//  - its statement depth is undefined but the parent's statement depth is at least 1
+	map<ASTNode const*, GasMeter::GasConsumption> gasCosts;
+	auto onNodeSecondPass = [&](ASTNode const& _node)
+	{
+		return statementDepth.count(&_node);
+	};
+	auto onEdgeSecondPass = [&](ASTNode const& _parent, ASTNode const& _child)
+	{
+		bool useNode = false;
+		if (statementDepth.count(&_child))
+			useNode = statementDepth[&_child] == 0;
+		else
+			useNode = statementDepth.count(&_parent) && statementDepth.at(&_parent) > 0;
+		if (useNode)
+			gasCosts[&_child] = _gasCosts.at(&_child)[1];
+	};
+	ASTReduce secondPass(onNodeSecondPass, onEdgeSecondPass);
+	for (ASTNode const* node: _roots)
+		node->accept(secondPass);
+	// gasCosts should only contain non-overlapping locations
+	return gasCosts;
+}
diff --git a/StructuralGasEstimator.h b/StructuralGasEstimator.h
new file mode 100644
index 00000000..b9e97643
--- /dev/null
+++ b/StructuralGasEstimator.h
@@ -0,0 +1,59 @@
+/*
+	This file is part of cpp-ethereum.
+
+	cpp-ethereum 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.
+
+	cpp-ethereum 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 cpp-ethereum.  If not, see <http://www.gnu.org/licenses/>.
+*/
+/**
+ * @author Christian <c@ethdev.com>
+ * @date 2015
+ * Gas consumption estimator working alongside the AST.
+ */
+
+#pragma once
+
+#include <vector>
+#include <map>
+#include <libsolidity/ASTForward.h>
+#include <libevmasm/GasMeter.h>
+#include <libevmasm/Assembly.h>
+
+namespace dev
+{
+namespace solidity
+{
+
+class StructuralGasEstimator
+{
+public:
+	using ASTGasConsumption = std::map<ASTNode const*, eth::GasMeter::GasConsumption>;
+
+	/// Estimates the gas consumption for every assembly item in the given assembly and stores
+	/// it by source location.
+	/// @returns a mapping from each AST node to a pair of its particular and syntactically accumulated gas costs.
+	std::map<ASTNode const*, eth::GasMeter::GasConsumption[2]> performEstimation(
+		eth::AssemblyItems const& _items,
+		std::vector<ASTNode const*> const& _ast
+	);
+	/// @returns a mapping from nodes with non-overlapping source locations to gas consumptions such that
+	/// the following source locations are part of the mapping:
+	/// 1. source locations of statements that do not contain other statements
+	/// 2. maximal source locations that do not overlap locations coming from the first rule
+	ASTGasConsumption breakToStatementLevel(
+		std::map<ASTNode const*, eth::GasMeter::GasConsumption[2]> const& _gasCosts,
+		std::vector<ASTNode const*> const& _roots
+	);
+};
+
+}
+}