diff options
19 files changed, 220 insertions, 155 deletions
diff --git a/Changelog.md b/Changelog.md index e208437e..7e653ebf 100644 --- a/Changelog.md +++ b/Changelog.md @@ -22,6 +22,7 @@ Bugfixes: * Commandline interface: Support ``--evm-version constantinople`` properly. * DocString Parser: Fix error message for empty descriptions. * Standard JSON: Support ``constantinople`` as ``evmVersion`` properly. + * Type Checker: Fix detection of recursive structs. * Type System: Improve error message when attempting to shift by a fractional amount. * Type System: Make external library functions accessible. * Type System: Prevent encoding of weird types. diff --git a/libdevcore/Algorithms.h b/libdevcore/Algorithms.h new file mode 100644 index 00000000..b2540668 --- /dev/null +++ b/libdevcore/Algorithms.h @@ -0,0 +1,76 @@ +/* + 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/>. +*/ +#pragma once + + +#include <functional> +#include <set> + +namespace dev +{ + +/** + * Detector for cycles in directed graphs. It returns the first + * vertex on the path towards a cycle or a nullptr if there is + * no reachable cycle starting from a given vertex. + */ +template <typename V> +class CycleDetector +{ +public: + /// Initializes the cycle detector + /// @param _visit function that is given the current vertex + /// and is supposed to call @a run on all + /// adjacent vertices. + explicit CycleDetector(std::function<void(V const&, CycleDetector&)> _visit): + m_visit(std::move(_visit)) + { } + + /// Recursively perform cycle detection starting + /// (or continuing) with @param _vertex + /// @returns the first vertex on the path towards a cycle from @a _vertex + /// or nullptr if no cycle is reachable from @a _vertex. + V const* run(V const& _vertex) + { + if (m_firstCycleVertex) + return m_firstCycleVertex; + if (m_processed.count(&_vertex)) + return nullptr; + else if (m_processing.count(&_vertex)) + return m_firstCycleVertex = &_vertex; + m_processing.insert(&_vertex); + + m_depth++; + m_visit(_vertex, *this); + m_depth--; + if (m_firstCycleVertex && m_depth == 1) + m_firstCycleVertex = &_vertex; + + m_processing.erase(&_vertex); + m_processed.insert(&_vertex); + return m_firstCycleVertex; + } + +private: + std::function<void(V const&, CycleDetector&)> m_visit; + std::set<V const*> m_processing; + std::set<V const*> m_processed; + size_t m_depth = 0; + V const* m_firstCycleVertex = nullptr; +}; + +} diff --git a/libsolidity/analysis/PostTypeChecker.cpp b/libsolidity/analysis/PostTypeChecker.cpp index fbc72e52..19d0b708 100644 --- a/libsolidity/analysis/PostTypeChecker.cpp +++ b/libsolidity/analysis/PostTypeChecker.cpp @@ -21,6 +21,8 @@ #include <libsolidity/interface/ErrorReporter.h> #include <libsolidity/interface/Version.h> +#include <libdevcore/Algorithms.h> + #include <boost/range/adaptor/map.hpp> #include <memory> @@ -47,7 +49,7 @@ void PostTypeChecker::endVisit(ContractDefinition const&) { solAssert(!m_currentConstVariable, ""); for (auto declaration: m_constVariables) - if (auto identifier = findCycle(declaration)) + if (auto identifier = findCycle(*declaration)) m_errorReporter.typeError( declaration->location(), "The value of the constant " + declaration->name() + @@ -87,20 +89,24 @@ bool PostTypeChecker::visit(Identifier const& _identifier) return true; } -VariableDeclaration const* PostTypeChecker::findCycle( - VariableDeclaration const* _startingFrom, - set<VariableDeclaration const*> const& _seen -) +VariableDeclaration const* PostTypeChecker::findCycle(VariableDeclaration const& _startingFrom) { - if (_seen.count(_startingFrom)) - return _startingFrom; - else if (m_constVariableDependencies.count(_startingFrom)) + auto visitor = [&](VariableDeclaration const& _variable, CycleDetector<VariableDeclaration>& _cycleDetector) { - set<VariableDeclaration const*> seen(_seen); - seen.insert(_startingFrom); - for (auto v: m_constVariableDependencies[_startingFrom]) - if (findCycle(v, seen)) - return v; - } - return nullptr; + // Iterating through the dependencies needs to be deterministic and thus cannot + // depend on the memory layout. + // Because of that, we sort by AST node id. + vector<VariableDeclaration const*> dependencies( + m_constVariableDependencies[&_variable].begin(), + m_constVariableDependencies[&_variable].end() + ); + sort(dependencies.begin(), dependencies.end(), [](VariableDeclaration const* _a, VariableDeclaration const* _b) -> bool + { + return _a->id() < _b->id(); + }); + for (auto v: dependencies) + if (_cycleDetector.run(*v)) + return; + }; + return CycleDetector<VariableDeclaration>(visitor).run(_startingFrom); } diff --git a/libsolidity/analysis/PostTypeChecker.h b/libsolidity/analysis/PostTypeChecker.h index bafc1ae6..4f9dac6e 100644 --- a/libsolidity/analysis/PostTypeChecker.h +++ b/libsolidity/analysis/PostTypeChecker.h @@ -55,10 +55,7 @@ private: virtual bool visit(Identifier const& _identifier) override; - VariableDeclaration const* findCycle( - VariableDeclaration const* _startingFrom, - std::set<VariableDeclaration const*> const& _seen = std::set<VariableDeclaration const*>{} - ); + VariableDeclaration const* findCycle(VariableDeclaration const& _startingFrom); ErrorReporter& m_errorReporter; diff --git a/libsolidity/ast/Types.cpp b/libsolidity/ast/Types.cpp index 42fd1c3d..ac1d3b01 100644 --- a/libsolidity/ast/Types.cpp +++ b/libsolidity/ast/Types.cpp @@ -28,6 +28,7 @@ #include <libdevcore/CommonData.h> #include <libdevcore/SHA3.h> #include <libdevcore/UTF8.h> +#include <libdevcore/Algorithms.h> #include <boost/algorithm/string/join.hpp> #include <boost/algorithm/string/replace.hpp> @@ -1971,25 +1972,19 @@ bool StructType::recursive() const { if (!m_recursive.is_initialized()) { - set<StructDefinition const*> structsSeen; - function<bool(StructType const*)> check = [&](StructType const* t) -> bool + auto visitor = [&](StructDefinition const& _struct, CycleDetector<StructDefinition>& _cycleDetector) { - StructDefinition const* str = &t->structDefinition(); - if (structsSeen.count(str)) - return true; - structsSeen.insert(str); - for (ASTPointer<VariableDeclaration> const& variable: str->members()) + for (ASTPointer<VariableDeclaration> const& variable: _struct.members()) { Type const* memberType = variable->annotation().type.get(); while (dynamic_cast<ArrayType const*>(memberType)) memberType = dynamic_cast<ArrayType const*>(memberType)->baseType().get(); if (StructType const* innerStruct = dynamic_cast<StructType const*>(memberType)) - if (check(innerStruct)) - return true; + if (_cycleDetector.run(innerStruct->structDefinition())) + return; } - return false; }; - m_recursive = check(this); + m_recursive = (CycleDetector<StructDefinition>(visitor).run(structDefinition()) != nullptr); } return *m_recursive; } diff --git a/test/libsolidity/SolidityNameAndTypeResolution.cpp b/test/libsolidity/SolidityNameAndTypeResolution.cpp index b6596327..fcee0df3 100644 --- a/test/libsolidity/SolidityNameAndTypeResolution.cpp +++ b/test/libsolidity/SolidityNameAndTypeResolution.cpp @@ -92,61 +92,6 @@ BOOST_AUTO_TEST_CASE(reference_to_later_declaration) CHECK_SUCCESS(text); } -BOOST_AUTO_TEST_CASE(struct_definition_directly_recursive) -{ - char const* text = R"( - contract test { - struct MyStructName { - address addr; - MyStructName x; - } - } - )"; - CHECK_ERROR(text, TypeError, "Recursive struct definition."); -} - -BOOST_AUTO_TEST_CASE(struct_definition_indirectly_recursive) -{ - char const* text = R"( - contract test { - struct MyStructName1 { - address addr; - uint256 count; - MyStructName2 x; - } - struct MyStructName2 { - MyStructName1 x; - } - } - )"; - CHECK_ERROR(text, TypeError, "Recursive struct definition."); -} - -BOOST_AUTO_TEST_CASE(struct_definition_not_really_recursive) -{ - char const* text = R"( - contract test { - struct s1 { uint a; } - struct s2 { s1 x; s1 y; } - } - )"; - CHECK_SUCCESS(text); -} - -BOOST_AUTO_TEST_CASE(struct_definition_recursion_via_mapping) -{ - char const* text = R"( - contract test { - struct MyStructName1 { - address addr; - uint256 count; - mapping(uint => MyStructName1) x; - } - } - )"; - CHECK_SUCCESS(text); -} - BOOST_AUTO_TEST_CASE(type_inference_smoke_test) { char const* text = R"( @@ -6222,44 +6167,6 @@ BOOST_AUTO_TEST_CASE(read_returned_struct) )"; CHECK_WARNING(text, "Experimental features"); } - -BOOST_AUTO_TEST_CASE(return_recursive_structs) -{ - char const* text = R"( - contract C { - struct S { uint a; S[] sub; } - function f() returns (uint, S) { - } - } - )"; - CHECK_ERROR(text, TypeError, "Internal or recursive type is not allowed for public or external functions."); -} - -BOOST_AUTO_TEST_CASE(return_recursive_structs2) -{ - char const* text = R"( - contract C { - struct S { uint a; S[2][] sub; } - function f() returns (uint, S) { - } - } - )"; - CHECK_ERROR(text, TypeError, "Internal or recursive type is not allowed for public or external functions."); -} - -BOOST_AUTO_TEST_CASE(return_recursive_structs3) -{ - char const* text = R"( - contract C { - struct S { uint a; S[][][] sub; } - struct T { S s; } - function f() returns (uint x, T t) { - } - } - )"; - CHECK_ERROR(text, TypeError, "Internal or recursive type is not allowed for public or external functions."); -} - BOOST_AUTO_TEST_CASE(address_checksum_type_deduction) { char const* text = R"( @@ -6382,38 +6289,6 @@ BOOST_AUTO_TEST_CASE(address_methods) CHECK_SUCCESS(text); } -BOOST_AUTO_TEST_CASE(cyclic_dependency_for_constants) -{ - char const* text = R"( - contract C { - uint constant a = a; - } - )"; - CHECK_ERROR(text, TypeError, "cyclic dependency via a"); - text = R"( - contract C { - uint constant a = b * c; - uint constant b = 7; - uint constant c = b + uint(keccak256(d)); - uint constant d = 2 + a; - } - )"; - CHECK_ERROR_ALLOW_MULTI(text, TypeError, (std::vector<std::string>{ - "a has a cyclic dependency via c", - "c has a cyclic dependency via d", - "d has a cyclic dependency via a" - })); - text = R"( - contract C { - uint constant a = b * c; - uint constant b = 7; - uint constant c = 4 + uint(keccak256(d)); - uint constant d = 2 + b; - } - )"; - CHECK_SUCCESS(text); -} - BOOST_AUTO_TEST_CASE(interface) { char const* text = R"( diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_1.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_1.sol new file mode 100644 index 00000000..2b6aa088 --- /dev/null +++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_1.sol @@ -0,0 +1,5 @@ +contract C { + uint constant a = a; +} +// ---- +// TypeError: The value of the constant a has a cyclic dependency via a. diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_2.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_2.sol new file mode 100644 index 00000000..461979f8 --- /dev/null +++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_2.sol @@ -0,0 +1,10 @@ +contract C { + uint constant a = b * c; + uint constant b = 7; + uint constant c = b + uint(keccak256(d)); + uint constant d = 2 + a; +} +// ---- +// TypeError: The value of the constant a has a cyclic dependency via c. +// TypeError: The value of the constant c has a cyclic dependency via d. +// TypeError: The value of the constant d has a cyclic dependency via a. diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_3.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_3.sol new file mode 100644 index 00000000..f63be05e --- /dev/null +++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_3.sol @@ -0,0 +1,11 @@ +contract C { + uint constant x = a; + uint constant a = b * c; + uint constant b = c; + uint constant c = b; +} +// ---- +// TypeError: The value of the constant x has a cyclic dependency via a. +// TypeError: The value of the constant a has a cyclic dependency via b. +// TypeError: The value of the constant b has a cyclic dependency via c. +// TypeError: The value of the constant c has a cyclic dependency via b. diff --git a/test/libsolidity/syntaxTests/constants/cyclic_dependency_4.sol b/test/libsolidity/syntaxTests/constants/cyclic_dependency_4.sol new file mode 100644 index 00000000..f01cb98e --- /dev/null +++ b/test/libsolidity/syntaxTests/constants/cyclic_dependency_4.sol @@ -0,0 +1,6 @@ +contract C { + uint constant a = b * c; + uint constant b = 7; + uint constant c = 4 + uint(keccak256(d)); + uint constant d = 2 + b; +}
\ No newline at end of file diff --git a/test/libsolidity/syntaxTests/structs/recursion/multi_struct_composition.sol b/test/libsolidity/syntaxTests/structs/recursion/multi_struct_composition.sol new file mode 100644 index 00000000..9a1c22f1 --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/multi_struct_composition.sol @@ -0,0 +1,15 @@ +pragma experimental ABIEncoderV2; + +contract C { + struct T { U u; V v; } + + struct U { W w; } + + struct V { W w; } + + struct W { uint x; } + + function f(T) public pure { } +} +// ---- +// Warning: Experimental features are turned on. Do not use experimental features on live deployments. diff --git a/test/libsolidity/syntaxTests/structs/recursion/parallel_structs.sol b/test/libsolidity/syntaxTests/structs/recursion/parallel_structs.sol new file mode 100644 index 00000000..d4ad088d --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/parallel_structs.sol @@ -0,0 +1,15 @@ +pragma experimental ABIEncoderV2; + +contract TestContract +{ + struct SubStruct { + uint256 id; + } + struct TestStruct { + SubStruct subStruct1; + SubStruct subStruct2; + } + function addTestStruct(TestStruct) public pure {} +} +// ---- +// Warning: Experimental features are turned on. Do not use experimental features on live deployments. diff --git a/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs.sol b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs.sol new file mode 100644 index 00000000..c02a8aa4 --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs.sol @@ -0,0 +1,7 @@ +contract C { + struct S { uint a; S[] sub; } + function f() public pure returns (uint, S) { + } +} +// ---- +// TypeError: Internal or recursive type is not allowed for public or external functions. diff --git a/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs2.sol b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs2.sol new file mode 100644 index 00000000..e9488cf4 --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs2.sol @@ -0,0 +1,7 @@ +contract C { + struct S { uint a; S[2][] sub; } + function f() public pure returns (uint, S) { + } +} +// ---- +// TypeError: Internal or recursive type is not allowed for public or external functions. diff --git a/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs3.sol b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs3.sol new file mode 100644 index 00000000..6728baec --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/return_recursive_structs3.sol @@ -0,0 +1,8 @@ +contract C { + struct S { uint a; S[][][] sub; } + struct T { S s; } + function f() public pure returns (uint x, T t) { + } +} +// ---- +// TypeError: Internal or recursive type is not allowed for public or external functions. diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive.sol new file mode 100644 index 00000000..cac2e23f --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_directly_recursive.sol @@ -0,0 +1,8 @@ +contract Test { + struct MyStructName { + address addr; + MyStructName x; + } +} +// ---- +// TypeError: Recursive struct definition. diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive.sol new file mode 100644 index 00000000..11fc6307 --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_indirectly_recursive.sol @@ -0,0 +1,12 @@ +contract Test { + struct MyStructName1 { + address addr; + uint256 count; + MyStructName2 x; + } + struct MyStructName2 { + MyStructName1 x; + } +} +// ---- +// TypeError: Recursive struct definition. diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive.sol new file mode 100644 index 00000000..6ec4ee01 --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_not_really_recursive.sol @@ -0,0 +1,4 @@ +contract Test { + struct S1 { uint a; } + struct S2 { S1 x; S1 y; } +} diff --git a/test/libsolidity/syntaxTests/structs/recursion/struct_definition_recursion_via_mapping.sol b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_recursion_via_mapping.sol new file mode 100644 index 00000000..926981b3 --- /dev/null +++ b/test/libsolidity/syntaxTests/structs/recursion/struct_definition_recursion_via_mapping.sol @@ -0,0 +1,7 @@ +contract Test { + struct MyStructName1 { + address addr; + uint256 count; + mapping(uint => MyStructName1) x; + } +} |