Warn about unreachable code.

5 files changed, 74 insertions, 11 deletions

diff --git a/libsolidity/analysis/ControlFlowAnalyzer.cpp b/libsolidity/analysis/ControlFlowAnalyzer.cpp
index 3adf6318..b801547f 100644
--- a/libsolidity/analysis/ControlFlowAnalyzer.cpp
+++ b/libsolidity/analysis/ControlFlowAnalyzer.cpp
@@ -18,6 +18,7 @@
 #include <libsolidity/analysis/ControlFlowAnalyzer.h>
 
 #include <liblangutil/SourceLocation.h>
+#include <libdevcore/Algorithms.h>
 #include <boost/range/algorithm/sort.hpp>
 
 using namespace std;
@@ -36,6 +37,7 @@ bool ControlFlowAnalyzer::visit(FunctionDefinition const& _function)
 	{
 		auto const& functionFlow = m_cfg.functionFlow(_function);
 		checkUninitializedAccess(functionFlow.entry, functionFlow.exit);
+		checkUnreachable(functionFlow.entry, functionFlow.exit, functionFlow.revert);
 	}
 	return false;
 }
@@ -145,3 +147,35 @@ void ControlFlowAnalyzer::checkUninitializedAccess(CFGNode const* _entry, CFGNod
 		}
 	}
 }
+
+void ControlFlowAnalyzer::checkUnreachable(CFGNode const* _entry, CFGNode const* _exit, CFGNode const* _revert) const
+{
+	// collect all nodes reachable from the entry point
+	std::set<CFGNode const*> reachable = BreadthFirstSearch<CFGNode>{{_entry}}.run(
+		[](CFGNode const& _node, auto&& _addChild) {
+			for (CFGNode const* exit: _node.exits)
+				_addChild(*exit);
+		}
+	).visited;
+
+	// traverse all paths backwards from exit and revert
+	// and extract (valid) source locations of unreachable nodes into sorted set
+	std::set<SourceLocation> unreachable;
+	BreadthFirstSearch<CFGNode>{{_exit, _revert}}.run(
+		[&](CFGNode const& _node, auto&& _addChild) {
+			if (!reachable.count(&_node) && !_node.location.isEmpty())
+				unreachable.insert(_node.location);
+			for (CFGNode const* entry: _node.entries)
+				_addChild(*entry);
+		}
+	);
+
+	for (auto it = unreachable.begin(); it != unreachable.end();)
+	{
+		SourceLocation location = *it++;
+		// Extend the location, as long as the next location overlaps (unreachable is sorted).
+		for (; it != unreachable.end() && it->start <= location.end; ++it)
+			location.end = std::max(location.end, it->end);
+		m_errorReporter.warning(location, "Unreachable code.");
+	}
+}
diff --git a/libsolidity/analysis/ControlFlowAnalyzer.h b/libsolidity/analysis/ControlFlowAnalyzer.h
index 7761817a..e1585740 100644
--- a/libsolidity/analysis/ControlFlowAnalyzer.h
+++ b/libsolidity/analysis/ControlFlowAnalyzer.h
@@ -38,6 +38,9 @@ public:
 private:
 	/// Checks for uninitialized variable accesses in the control flow between @param _entry and @param _exit.
 	void checkUninitializedAccess(CFGNode const* _entry, CFGNode const* _exit) const;
+	/// Checks for unreachable code, i.e. code ending in @param _exit or @param _revert
+	/// that can not be reached from @param _entry.
+	void checkUnreachable(CFGNode const* _entry, CFGNode const* _exit, CFGNode const* _revert) const;
 
 	CFG const& m_cfg;
 	langutil::ErrorReporter& m_errorReporter;
diff --git a/libsolidity/analysis/ControlFlowBuilder.cpp b/libsolidity/analysis/ControlFlowBuilder.cpp
index 3dab8b16..66664245 100644
--- a/libsolidity/analysis/ControlFlowBuilder.cpp
+++ b/libsolidity/analysis/ControlFlowBuilder.cpp
@@ -18,6 +18,7 @@
 #include <libsolidity/analysis/ControlFlowBuilder.h>
 
 using namespace dev;
+using namespace langutil;
 using namespace solidity;
 using namespace std;
 
@@ -53,6 +54,7 @@ bool ControlFlowBuilder::visit(BinaryOperation const& _operation)
 		case Token::Or:
 		case Token::And:
 		{
+			visitNode(_operation);
 			appendControlFlow(_operation.leftExpression());
 
 			auto nodes = splitFlow<2>();
@@ -62,14 +64,14 @@ bool ControlFlowBuilder::visit(BinaryOperation const& _operation)
 			return false;
 		}
 		default:
-			break;
+			return ASTConstVisitor::visit(_operation);
 	}
-	return ASTConstVisitor::visit(_operation);
 }
 
 bool ControlFlowBuilder::visit(Conditional const& _conditional)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_conditional);
 
 	_conditional.condition().accept(*this);
 
@@ -86,6 +88,7 @@ bool ControlFlowBuilder::visit(Conditional const& _conditional)
 bool ControlFlowBuilder::visit(IfStatement const& _ifStatement)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_ifStatement);
 
 	_ifStatement.condition().accept(*this);
 
@@ -106,6 +109,7 @@ bool ControlFlowBuilder::visit(IfStatement const& _ifStatement)
 bool ControlFlowBuilder::visit(ForStatement const& _forStatement)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_forStatement);
 
 	if (_forStatement.initializationExpression())
 		_forStatement.initializationExpression()->accept(*this);
@@ -139,6 +143,7 @@ bool ControlFlowBuilder::visit(ForStatement const& _forStatement)
 bool ControlFlowBuilder::visit(WhileStatement const& _whileStatement)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_whileStatement);
 
 	if (_whileStatement.isDoWhile())
 	{
@@ -183,28 +188,31 @@ bool ControlFlowBuilder::visit(WhileStatement const& _whileStatement)
 	return false;
 }
 
-bool ControlFlowBuilder::visit(Break const&)
+bool ControlFlowBuilder::visit(Break const& _break)
 {
 	solAssert(!!m_currentNode, "");
 	solAssert(!!m_breakJump, "");
+	visitNode(_break);
 	connect(m_currentNode, m_breakJump);
 	m_currentNode = newLabel();
 	return false;
 }
 
-bool ControlFlowBuilder::visit(Continue const&)
+bool ControlFlowBuilder::visit(Continue const& _continue)
 {
 	solAssert(!!m_currentNode, "");
 	solAssert(!!m_continueJump, "");
+	visitNode(_continue);
 	connect(m_currentNode, m_continueJump);
 	m_currentNode = newLabel();
 	return false;
 }
 
-bool ControlFlowBuilder::visit(Throw const&)
+bool ControlFlowBuilder::visit(Throw const& _throw)
 {
 	solAssert(!!m_currentNode, "");
 	solAssert(!!m_revertNode, "");
+	visitNode(_throw);
 	connect(m_currentNode, m_revertNode);
 	m_currentNode = newLabel();
 	return false;
@@ -232,6 +240,7 @@ bool ControlFlowBuilder::visit(FunctionCall const& _functionCall)
 		{
 			case FunctionType::Kind::Revert:
 				solAssert(!!m_revertNode, "");
+				visitNode(_functionCall);
 				_functionCall.expression().accept(*this);
 				ASTNode::listAccept(_functionCall.arguments(), *this);
 				connect(m_currentNode, m_revertNode);
@@ -241,6 +250,7 @@ bool ControlFlowBuilder::visit(FunctionCall const& _functionCall)
 			case FunctionType::Kind::Assert:
 			{
 				solAssert(!!m_revertNode, "");
+				visitNode(_functionCall);
 				_functionCall.expression().accept(*this);
 				ASTNode::listAccept(_functionCall.arguments(), *this);
 				connect(m_currentNode, m_revertNode);
@@ -314,6 +324,7 @@ bool ControlFlowBuilder::visit(Return const& _return)
 {
 	solAssert(!!m_currentNode, "");
 	solAssert(!!m_returnNode, "");
+	visitNode(_return);
 	if (_return.expression())
 	{
 		appendControlFlow(*_return.expression());
@@ -327,11 +338,12 @@ bool ControlFlowBuilder::visit(Return const& _return)
 	}
 	connect(m_currentNode, m_returnNode);
 	m_currentNode = newLabel();
-	return true;
+	return false;
 }
 
-bool ControlFlowBuilder::visit(FunctionTypeName const&)
+bool ControlFlowBuilder::visit(FunctionTypeName const& _functionTypeName)
 {
+	visitNode(_functionTypeName);
 	// Do not visit the parameters and return values of a function type name.
 	// We do not want to consider them as variable declarations for the control flow graph.
 	return false;
@@ -340,6 +352,7 @@ bool ControlFlowBuilder::visit(FunctionTypeName const&)
 bool ControlFlowBuilder::visit(InlineAssembly const& _inlineAssembly)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_inlineAssembly);
 	for (auto const& ref: _inlineAssembly.annotation().externalReferences)
 	{
 		if (auto variableDeclaration = dynamic_cast<VariableDeclaration const*>(ref.second.declaration))
@@ -355,6 +368,7 @@ bool ControlFlowBuilder::visit(InlineAssembly const& _inlineAssembly)
 bool ControlFlowBuilder::visit(VariableDeclaration const& _variableDeclaration)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_variableDeclaration);
 
 	m_currentNode->variableOccurrences.emplace_back(
 		_variableDeclaration,
@@ -382,6 +396,7 @@ bool ControlFlowBuilder::visit(VariableDeclaration const& _variableDeclaration)
 bool ControlFlowBuilder::visit(VariableDeclarationStatement const& _variableDeclarationStatement)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_variableDeclarationStatement);
 
 	for (auto const& var: _variableDeclarationStatement.declarations())
 		if (var)
@@ -417,6 +432,7 @@ bool ControlFlowBuilder::visit(VariableDeclarationStatement const& _variableDecl
 bool ControlFlowBuilder::visit(Identifier const& _identifier)
 {
 	solAssert(!!m_currentNode, "");
+	visitNode(_identifier);
 
 	if (auto const* variableDeclaration = dynamic_cast<VariableDeclaration const*>(_identifier.annotation().referencedDeclaration))
 		m_currentNode->variableOccurrences.emplace_back(
@@ -430,7 +446,12 @@ bool ControlFlowBuilder::visit(Identifier const& _identifier)
 	return true;
 }
 
-
+bool ControlFlowBuilder::visitNode(ASTNode const& _node)
+{
+	solAssert(!!m_currentNode, "");
+	m_currentNode->location = langutil::SourceLocation::smallestCovering(m_currentNode->location, _node.location());
+	return true;
+}
 
 void ControlFlowBuilder::appendControlFlow(ASTNode const& _node)
 {
diff --git a/libsolidity/analysis/ControlFlowBuilder.h b/libsolidity/analysis/ControlFlowBuilder.h
index f196e5fc..b1748395 100644
--- a/libsolidity/analysis/ControlFlowBuilder.h
+++ b/libsolidity/analysis/ControlFlowBuilder.h
@@ -66,6 +66,11 @@ private:
 	bool visit(VariableDeclarationStatement const& _variableDeclarationStatement) override;
 	bool visit(Identifier const& _identifier) override;
 
+protected:
+	bool visitNode(ASTNode const&) override;
+
+private:
+
 	/// Appends the control flow of @a _node to the current control flow.
 	void appendControlFlow(ASTNode const& _node);
 
@@ -77,9 +82,6 @@ private:
 	/// Creates an arc from @a _from to @a _to.
 	static void connect(CFGNode* _from, CFGNode* _to);
 
-
-private:
-
 	/// Splits the control flow starting at the current node into n paths.
 	/// m_currentNode is set to nullptr and has to be set manually or
 	/// using mergeFlow later.
diff --git a/libsolidity/analysis/ControlFlowGraph.h b/libsolidity/analysis/ControlFlowGraph.h
index cc0113d8..a55b96e8 100644
--- a/libsolidity/analysis/ControlFlowGraph.h
+++ b/libsolidity/analysis/ControlFlowGraph.h
@@ -20,6 +20,7 @@
 #include <libsolidity/ast/AST.h>
 #include <libsolidity/ast/ASTVisitor.h>
 #include <liblangutil/ErrorReporter.h>
+#include <liblangutil/SourceLocation.h>
 
 #include <map>
 #include <memory>
@@ -98,6 +99,8 @@ struct CFGNode
 
 	/// Variable occurrences in the node.
 	std::vector<VariableOccurrence> variableOccurrences;
+	// Source location of this control flow block.
+	langutil::SourceLocation location;
 };
 
 /** Describes the control flow of a function. */