Skip to content

Commit 0d7836f

Browse files
rebnridgwaydanmar
rebnridgway
authored and
danmar
committed
Calculate token scopes in advance rather than as the tokenlist is iterated (#1882)
* Added scopeinfo member to token class Moved ScopeInfo2 declaration here as well because that's where it needs to be now. * Added scopeinfo accessors and declaration to class * Add new method for calculating scopes This replaces the methods in the TemplateSimplifier which calculate the current scope as the token list is iterated. The old method required checking if the scope had changed for every token multiple times (for multiple iterations), which was surprisingly costly. Calculating scopes in advance like this decreases runtime on a worst-case file by around thirty percent. ScopeInfo objects are disposed of when the TemplateSimplification is done as they are not used later. * Add calculateScopes method to header * Removed code that calculated current scope This has been replaced by code that calculates the scopes up front and stores them with each token, which is much faster. * Fixed compile errors from extra parentheses * Added missing code to fix memory leak * Added code to actually clean up ScopeInfo structs * Tidy up a dodgy for loop * Convert argument to const ref * Calculate missing scopes As the templatesimplificator expands templates and does multiple passes it needs to make sure all scopes are calculated. * Remove copying the scope to the next token This is now done properly when scopes are calculated. * Remove call to calculateScopes This is now done by the TemplateSimplifier. * Recalculate scopes for every pass of simplifyTemplates * Add code to calculate extra scopes as they are added I thought that this might be useful for calculating scopes when Tokens are created, but as there are several ways of creating Tokens that don't guarantee that they are placed in a list it is easier to just calculate scopes when you know you have a list and when you know you're adding to a list. * Fix several bugs and poorly designed code Remove the global scopes collection, and clean them up instead by iterating through the tokenlist to find them. This means scopes can be calculated by functions in the Token class as well as in the Tokenizer class without leaking the scope object. Fix a couple of bugs in the calculateScopes method and make it more efficient. * Remove unnecessary calls to calculateScopes * Move brace to correct position Calculating scopes during insertToken only needs to happen if we created a new Token. * Handle 'using namespace' declarations separately This fixes a bug caused by a statement matching 'struct B < 0 > ;' * Fix argument name mismatch * Actually use newScopeInfo when inserting Token * Switch to using shared_ptr to hold scopeInfos This means ScopeInfo2 objects get properly cleaned up when they are no longer needed. * Change ScopeInfo member to be a shared_ptr * Update code to use shared_ptr * Add missing include for shared_ptr * Remove unnecessary cleanup code This has been replaced by shared_ptr for ScopeInfo2 objects
1 parent d1d622b commit 0d7836f

5 files changed

Lines changed: 220 additions & 126 deletions

File tree

‎lib/templatesimplifier.cpp‎

Lines changed: 9 additions & 120 deletions
Original file line numberDiff line numberDiff line change
@@ -632,106 +632,10 @@ bool TemplateSimplifier::removeTemplate(Token *tok)
632632
return false;
633633
}
634634

635-
/// TODO: This is copy pasted from Tokenizer. We should reuse this code.
636-
namespace {
637-
struct ScopeInfo2 {
638-
ScopeInfo2(const std::string &name_, const Token *bodyEnd_) : name(name_), bodyEnd(bodyEnd_) {}
639-
const std::string name;
640-
const Token * const bodyEnd;
641-
std::set<std::string> usingNamespaces;
642-
};
643-
}
644-
static std::string getScopeName(const std::list<ScopeInfo2> &scopeInfo)
645-
{
646-
std::string ret;
647-
for (const ScopeInfo2 &i : scopeInfo) {
648-
if (!i.name.empty())
649-
ret += (ret.empty() ? "" : " :: ") + i.name;
650-
}
651-
return ret;
652-
}
653-
654-
static void setScopeInfo(Token *tok, std::list<ScopeInfo2> *scopeInfo, bool all = false)
655-
{
656-
while (tok->str() == "}" && !scopeInfo->empty() && tok == scopeInfo->back().bodyEnd)
657-
scopeInfo->pop_back();
658-
if (!Token::Match(tok, "namespace|class|struct|union %name% {|:|::")) {
659-
// check for using namespace
660-
if (Token::Match(tok, "using namespace %name% ;|::")) {
661-
const Token * tok1 = tok->tokAt(2);
662-
std::string nameSpace;
663-
while (tok1 && tok1->str() != ";") {
664-
if (!nameSpace.empty())
665-
nameSpace += " ";
666-
nameSpace += tok1->str();
667-
tok1 = tok1->next();
668-
}
669-
scopeInfo->back().usingNamespaces.insert(nameSpace);
670-
}
671-
// check for member function
672-
else if (tok->str() == "{") {
673-
bool added = false;
674-
Token *tok1 = tok;
675-
while (Token::Match(tok1->previous(), "const|volatile|final|override|&|&&|noexcept"))
676-
tok1 = tok1->previous();
677-
if (tok1 && tok1->previous() && tok1->strAt(-1) == ")") {
678-
tok1 = tok1->linkAt(-1);
679-
if (Token::Match(tok1->previous(), "throw|noexcept")) {
680-
tok1 = tok1->previous();
681-
while (Token::Match(tok1->previous(), "const|volatile|final|override|&|&&|noexcept"))
682-
tok1 = tok1->previous();
683-
if (tok1->strAt(-1) != ")")
684-
return;
685-
} else if (Token::Match(tok->tokAt(-2), ":|, %name%")) {
686-
tok1 = tok1->tokAt(-2);
687-
if (tok1->strAt(-1) != ")")
688-
return;
689-
}
690-
if (tok1->strAt(-1) == ">")
691-
tok1 = tok1->previous()->findOpeningBracket();
692-
if (tok1 && Token::Match(tok1->tokAt(-3), "%name% :: %name%")) {
693-
tok1 = tok1->tokAt(-2);
694-
std::string scope = tok1->strAt(-1);
695-
while (Token::Match(tok1->tokAt(-2), ":: %name%")) {
696-
scope = tok1->strAt(-3) + " :: " + scope;
697-
tok1 = tok1->tokAt(-2);
698-
}
699-
scopeInfo->emplace_back(scope, tok->link());
700-
added = true;
701-
}
702-
}
703-
704-
if (all && !added)
705-
scopeInfo->emplace_back("", tok->link());
706-
}
707-
return;
708-
}
709-
710-
tok = tok->next();
711-
std::string classname = tok->str();
712-
while (Token::Match(tok, "%name% :: %name%")) {
713-
tok = tok->tokAt(2);
714-
classname += " :: " + tok->str();
715-
}
716-
tok = tok->next();
717-
if (tok && tok->str() == ":") {
718-
while (tok && !Token::Match(tok, ";|{"))
719-
tok = tok->next();
720-
}
721-
if (tok && tok->str() == "{") {
722-
scopeInfo->emplace_back(classname,tok->link());
723-
}
724-
}
725-
726635
bool TemplateSimplifier::getTemplateDeclarations()
727636
{
728637
bool codeWithTemplates = false;
729-
std::list<ScopeInfo2> scopeInfo;
730638
for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
731-
if (Token::Match(tok, "{|}|namespace|class|struct|union")) {
732-
setScopeInfo(tok, &scopeInfo);
733-
continue;
734-
}
735639
if (!Token::simpleMatch(tok, "template <"))
736640
continue;
737641
// ignore template template parameter
@@ -756,7 +660,7 @@ bool TemplateSimplifier::getTemplateDeclarations()
756660
else if (Token::Match(tok2, "{|=|;")) {
757661
const int namepos = getTemplateNamePosition(parmEnd);
758662
if (namepos > 0) {
759-
TokenAndName decl(tok, getScopeName(scopeInfo), parmEnd->tokAt(namepos), parmEnd);
663+
TokenAndName decl(tok, tok->scopeInfo()->name, parmEnd->tokAt(namepos), parmEnd);
760664
if (decl.isForwardDeclaration()) {
761665
// Declaration => add to mTemplateForwardDeclarations
762666
mTemplateForwardDeclarations.emplace_back(decl);
@@ -793,18 +697,9 @@ void TemplateSimplifier::getTemplateInstantiations()
793697
functionNameMap.insert(std::make_pair(decl.name, &decl));
794698
}
795699

796-
std::list<ScopeInfo2> scopeList;
797700
const Token *skip = nullptr;
798701

799-
scopeList.emplace_back("", nullptr);
800-
801702
for (Token *tok = mTokenList.front(); tok; tok = tok->next()) {
802-
if (Token::Match(tok, "{|}|namespace|class|struct|union") ||
803-
Token::Match(tok, "using namespace %name% ;|::")) {
804-
setScopeInfo(tok, &scopeList);
805-
continue;
806-
}
807-
808703
// template definition.. skip it
809704
if (Token::simpleMatch(tok, "template <")) {
810705
tok = tok->next()->findClosingBracket();
@@ -855,7 +750,7 @@ void TemplateSimplifier::getTemplateInstantiations()
855750
} else if (Token::Match(tok->previous(), "(|{|}|;|=|>|<<|:|.|*|&|return|<|, %name% ::|<|(") ||
856751
Token::Match(tok->previous(), "%type% %name% ::|<") ||
857752
Token::Match(tok->tokAt(-2), "[,:] private|protected|public %name% ::|<")) {
858-
std::string scopeName = getScopeName(scopeList);
753+
std::string scopeName = tok->scopeInfo()->name;
859754
std::string qualification;
860755
Token * qualificationTok = tok;
861756
while (Token::Match(tok, "%name% :: %name%")) {
@@ -951,7 +846,7 @@ void TemplateSimplifier::getTemplateInstantiations()
951846
for (; tok2 && tok2 != tok; tok2 = tok2->previous()) {
952847
if (Token::Match(tok2, ",|< %name% <") &&
953848
(tok2->strAt(3) == ">" || templateParameters(tok2->tokAt(2)))) {
954-
addInstantiation(tok2->next(), getScopeName(scopeList));
849+
addInstantiation(tok2->next(), tok->scopeInfo()->name);
955850
} else if (Token::Match(tok2->next(), "class|struct"))
956851
tok2->deleteNext();
957852
}
@@ -970,7 +865,7 @@ void TemplateSimplifier::getTemplateInstantiations()
970865
} else {
971866
// full name doesn't match so try with using namespaces if available
972867
bool found = false;
973-
for (const auto & nameSpace : scopeList.back().usingNamespaces) {
868+
for (const auto & nameSpace : tok->scopeInfo()->usingNamespaces) {
974869
std::string fullNameSpace = scopeName + (scopeName.empty()?"":" :: ") +
975870
nameSpace + (qualification.empty()?"":" :: ") + qualification;
976871
std::string newFullName = fullNameSpace + " :: " + tok->str();
@@ -997,7 +892,7 @@ void TemplateSimplifier::getTemplateInstantiations()
997892
if (!qualification.empty())
998893
addInstantiation(tok, qualification);
999894
else
1000-
addInstantiation(tok, getScopeName(scopeList));
895+
addInstantiation(tok, tok->scopeInfo()->name);
1001896
break;
1002897
}
1003898
const std::string::size_type pos = scopeName.rfind(" :: ");
@@ -1538,7 +1433,6 @@ void TemplateSimplifier::expandTemplate(
15381433
const std::string &newName,
15391434
bool copy)
15401435
{
1541-
std::list<ScopeInfo2> scopeInfo;
15421436
bool inTemplateDefinition = false;
15431437
const Token *startOfTemplateDeclaration = nullptr;
15441438
const Token *endOfTemplateDefinition = nullptr;
@@ -1753,10 +1647,6 @@ void TemplateSimplifier::expandTemplate(
17531647
}
17541648

17551649
for (Token *tok3 = mTokenList.front(); tok3; tok3 = tok3 ? tok3->next() : nullptr) {
1756-
if (Token::Match(tok3, "{|}|namespace|class|struct|union")) {
1757-
setScopeInfo(tok3, &scopeInfo);
1758-
continue;
1759-
}
17601650
if (inTemplateDefinition) {
17611651
if (!endOfTemplateDefinition) {
17621652
if (isVariable) {
@@ -2936,13 +2826,8 @@ void TemplateSimplifier::replaceTemplateUsage(
29362826
const std::list<std::string> &typeStringsUsedInTemplateInstantiation,
29372827
const std::string &newName)
29382828
{
2939-
std::list<ScopeInfo2> scopeInfo;
29402829
std::list< std::pair<Token *, Token *> > removeTokens;
29412830
for (Token *nameTok = mTokenList.front(); nameTok; nameTok = nameTok->next()) {
2942-
if (Token::Match(nameTok, "{|}|namespace|class|struct|union")) {
2943-
setScopeInfo(nameTok, &scopeInfo);
2944-
continue;
2945-
}
29462831
if (!Token::Match(nameTok, "%name% <") ||
29472832
Token::Match(nameTok, "template|const_cast|dynamic_cast|reinterpret_cast|static_cast"))
29482833
continue;
@@ -3370,6 +3255,10 @@ void TemplateSimplifier::simplifyTemplates(
33703255
unsigned int passCount = 0;
33713256
const unsigned int passCountMax = 10;
33723257
for (; passCount < passCountMax; ++passCount) {
3258+
// Recalculate scopes from scratch every pass, in case a scope is missing or incorrect
3259+
for (auto tok = mTokenizer->list.front(); tok; tok = tok->next()) tok->scopeInfo(nullptr);
3260+
mTokenizer->calculateScopes();
3261+
33733262
if (passCount) {
33743263
// it may take more than one pass to simplify type aliases
33753264
bool usingChanged = false;

‎lib/token.cpp‎

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -990,6 +990,84 @@ void Token::insertToken(const std::string &tokenStr, const std::string &original
990990
this->next(newToken);
991991
newToken->previous(this);
992992
}
993+
994+
// If the token we're inserting from has a scope, the new token needs one too
995+
if (mImpl->mScopeInfo) {
996+
// If it's a brace, we need to open a new scope
997+
if (tokenStr == "{") {
998+
std::string nextScopeNameAddition = "";
999+
// This might be the opening of a member function
1000+
Token *tok1 = newToken;
1001+
while (Token::Match(tok1->previous(), "const|volatile|final|override|&|&&|noexcept"))
1002+
tok1 = tok1->previous();
1003+
if (tok1 && tok1->previous() && tok1->strAt(-1) == ")") {
1004+
tok1 = tok1->linkAt(-1);
1005+
if (Token::Match(tok1->previous(), "throw|noexcept")) {
1006+
tok1 = tok1->previous();
1007+
while (Token::Match(tok1->previous(), "const|volatile|final|override|&|&&|noexcept"))
1008+
tok1 = tok1->previous();
1009+
if (tok1->strAt(-1) != ")")
1010+
return;
1011+
} else if (Token::Match(newToken->tokAt(-2), ":|, %name%")) {
1012+
tok1 = tok1->tokAt(-2);
1013+
if (tok1->strAt(-1) != ")")
1014+
return;
1015+
}
1016+
if (tok1->strAt(-1) == ">")
1017+
tok1 = tok1->previous()->findOpeningBracket();
1018+
if (tok1 && Token::Match(tok1->tokAt(-3), "%name% :: %name%")) {
1019+
tok1 = tok1->tokAt(-2);
1020+
std::string scope = tok1->strAt(-1);
1021+
while (Token::Match(tok1->tokAt(-2), ":: %name%")) {
1022+
scope = tok1->strAt(-3) + " :: " + scope;
1023+
tok1 = tok1->tokAt(-2);
1024+
}
1025+
1026+
if (nextScopeNameAddition.length() > 0) nextScopeNameAddition += " :: ";
1027+
nextScopeNameAddition += scope;
1028+
}
1029+
}
1030+
1031+
// Or it might be a namespace/class/struct
1032+
if (Token::Match(newToken->previous(), "%name%|>")) {
1033+
Token* nameTok = newToken->previous();
1034+
while (nameTok && !Token::Match(nameTok, "namespace|class|struct|union %name% {|::|:|<")) {
1035+
nameTok = nameTok->previous();
1036+
}
1037+
if (nameTok) {
1038+
for (nameTok = nameTok->next(); nameTok && !Token::Match(nameTok, "{|:|<"); nameTok = nameTok->next()) {
1039+
nextScopeNameAddition.append(nameTok->str());
1040+
nextScopeNameAddition.append(" ");
1041+
}
1042+
if (nextScopeNameAddition.length() > 0) nextScopeNameAddition = nextScopeNameAddition.substr(0, nextScopeNameAddition.length() - 1);
1043+
}
1044+
}
1045+
1046+
// New scope is opening, record it here
1047+
std::shared_ptr<ScopeInfo2> newScopeInfo = std::make_shared<ScopeInfo2>(mImpl->mScopeInfo->name, nullptr, mImpl->mScopeInfo->usingNamespaces);
1048+
1049+
if (newScopeInfo->name != "") newScopeInfo->name.append(" :: ");
1050+
newScopeInfo->name.append(nextScopeNameAddition);
1051+
1052+
newToken->scopeInfo(newScopeInfo);
1053+
1054+
// If it's a closing brace, we need to find where the scope opened and take the scope before
1055+
} else if (tokenStr == "}") {
1056+
Token* matchingTok = newToken->previous();
1057+
int depth = 0;
1058+
while (matchingTok && (depth != 0 || !Token::simpleMatch(matchingTok, "{"))) {
1059+
if (Token::simpleMatch(matchingTok, "}")) depth++;
1060+
if (Token::simpleMatch(matchingTok, "{")) depth--;
1061+
matchingTok = matchingTok->previous();
1062+
}
1063+
if (matchingTok && matchingTok->previous()) {
1064+
newToken->mImpl->mScopeInfo = matchingTok->previous()->scopeInfo();
1065+
}
1066+
// Otherwise we can just take the previous scope
1067+
} else {
1068+
newToken->mImpl->mScopeInfo = mImpl->mScopeInfo;
1069+
}
1070+
}
9931071
}
9941072
}
9951073

@@ -1846,6 +1924,13 @@ std::string Token::typeStr(const Token* tok)
18461924
return r.first->stringifyList(r.second, false);
18471925
}
18481926

1927+
void Token::scopeInfo(std::shared_ptr<ScopeInfo2> newScopeInfo) {
1928+
mImpl->mScopeInfo = newScopeInfo;
1929+
}
1930+
std::shared_ptr<ScopeInfo2> Token::scopeInfo() const {
1931+
return mImpl->mScopeInfo;
1932+
}
1933+
18491934
TokenImpl::~TokenImpl()
18501935
{
18511936
delete mOriginalName;

‎lib/token.h‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@
3030
#include <cstddef>
3131
#include <functional>
3232
#include <list>
33+
#include <memory>
3334
#include <ostream>
3435
#include <string>
3536
#include <vector>
@@ -50,6 +51,17 @@ struct TokensFrontBack {
5051
Token *back;
5152
};
5253

54+
struct ScopeInfo2 {
55+
ScopeInfo2(const std::string &name_, const Token *bodyEnd_, const std::set<std::string> &usingNamespaces_ = std::set<std::string>())
56+
: name(name_),
57+
bodyEnd(bodyEnd_),
58+
usingNamespaces(usingNamespaces_)
59+
{}
60+
std::string name;
61+
const Token * const bodyEnd;
62+
std::set<std::string> usingNamespaces;
63+
};
64+
5365
struct TokenImpl {
5466
unsigned int mVarId;
5567
unsigned int mFileIndex;
@@ -97,6 +109,8 @@ struct TokenImpl {
97109
// Pointer to a template in the template simplifier
98110
std::set<TemplateSimplifier::TokenAndName*> mTemplateSimplifierPointers;
99111

112+
std::shared_ptr<ScopeInfo2> mScopeInfo;
113+
100114
TokenImpl()
101115
: mVarId(0)
102116
, mFileIndex(0)
@@ -114,6 +128,7 @@ struct TokenImpl {
114128
, mValues(nullptr)
115129
, mBits(0)
116130
, mTemplateSimplifierPointers()
131+
, mScopeInfo(nullptr)
117132
{}
118133

119134
~TokenImpl();
@@ -1168,6 +1183,10 @@ class CPPCHECKLIB Token {
11681183
void printAst(bool verbose, bool xml, std::ostream &out) const;
11691184

11701185
void printValueFlow(bool xml, std::ostream &out) const;
1186+
1187+
void scopeInfo(std::shared_ptr<ScopeInfo2> newScopeInfo);
1188+
1189+
std::shared_ptr<ScopeInfo2> scopeInfo() const;
11711190
};
11721191

11731192
/// @}

0 commit comments

Comments
 (0)