diff options
Diffstat (limited to 'libsolidity/analysis/DeclarationContainer.cpp')
| -rw-r--r-- | libsolidity/analysis/DeclarationContainer.cpp | 63 |
1 files changed, 62 insertions, 1 deletions
diff --git a/libsolidity/analysis/DeclarationContainer.cpp b/libsolidity/analysis/DeclarationContainer.cpp index b33c8568..d41bc7d3 100644 --- a/libsolidity/analysis/DeclarationContainer.cpp +++ b/libsolidity/analysis/DeclarationContainer.cpp @@ -105,7 +105,7 @@ bool DeclarationContainer::registerDeclaration( return true; } -std::vector<Declaration const*> DeclarationContainer::resolveName(ASTString const& _name, bool _recursive) const +vector<Declaration const*> DeclarationContainer::resolveName(ASTString const& _name, bool _recursive) const { solAssert(!_name.empty(), "Attempt to resolve empty name."); auto result = m_declarations.find(_name); @@ -115,3 +115,64 @@ std::vector<Declaration const*> DeclarationContainer::resolveName(ASTString cons return m_enclosingContainer->resolveName(_name, true); return vector<Declaration const*>({}); } + +vector<ASTString> DeclarationContainer::similarNames(ASTString const& _name) const +{ + vector<ASTString> similar; + + for (auto const& declaration: m_declarations) + { + string const& declarationName = declaration.first; + if (DeclarationContainer::areSimilarNames(_name, declarationName)) + similar.push_back(declarationName); + } + + if (m_enclosingContainer) + { + vector<ASTString> enclosingSimilar = m_enclosingContainer->similarNames(_name); + similar.insert(similar.end(), enclosingSimilar.begin(), enclosingSimilar.end()); + } + + return similar; +} + +bool DeclarationContainer::areSimilarNames(ASTString const& _name1, ASTString const& _name2) +{ + if (_name1 == _name2) + return true; + + size_t n1 = _name1.size(), n2 = _name2.size(); + vector<vector<size_t>> dp(n1 + 1, vector<size_t>(n2 + 1)); + + // In this dp formulation of Damerau–Levenshtein distance we are assuming that the strings are 1-based to make base case storage easier. + // So index accesser to _name1 and _name2 have to be adjusted accordingly + for (size_t i1 = 0; i1 <= n1; ++i1) + { + for (size_t i2 = 0; i2 <= n2; ++i2) + { + if (min(i1, i2) == 0) // base case + dp[i1][i2] = max(i1, i2); + else + { + dp[i1][i2] = min(dp[i1-1][i2] + 1, dp[i1][i2-1] + 1); + // Deletion and insertion + if (_name1[i1-1] == _name2[i2-1]) + // Same chars, can skip + dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1]); + else + // Different chars so try substitution + dp[i1][i2] = min(dp[i1][i2], dp[i1-1][i2-1] + 1); + + if (i1 > 1 && i2 > 1 && _name1[i1-1] == _name2[i2-2] && _name1[i1-2] == _name2[i2-1]) + // Try transposing + dp[i1][i2] = min(dp[i1][i2], dp[i1-2][i2-2] + 1); + } + } + } + + size_t distance = dp[n1][n2]; + + // If distance is not greater than MAXIMUM_DISTANCE, and distance is strictly less than length of both names, + // they can be considered similar this is to avoid irrelevant suggestions + return distance <= MAXIMUM_DISTANCE && distance < n1 && distance < n2; +} |