1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357
|
//===--- DirectiveTree.cpp - Find and strip preprocessor directives -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#include "clang-pseudo/DirectiveTree.h"
#include "clang/Basic/IdentifierTable.h"
#include "clang/Basic/TokenKinds.h"
#include "llvm/Support/FormatVariadic.h"
#include <optional>
#include <variant>
namespace clang {
namespace pseudo {
namespace {
class DirectiveParser {
public:
explicit DirectiveParser(const TokenStream &Code)
: Code(Code), Tok(&Code.front()) {}
void parse(DirectiveTree *Result) { parse(Result, /*TopLevel=*/true); }
private:
// Roles that a directive might take within a conditional block.
enum class Cond { None, If, Else, End };
static Cond classifyDirective(tok::PPKeywordKind K) {
switch (K) {
case clang::tok::pp_if:
case clang::tok::pp_ifdef:
case clang::tok::pp_ifndef:
return Cond::If;
case clang::tok::pp_elif:
case clang::tok::pp_elifdef:
case clang::tok::pp_elifndef:
case clang::tok::pp_else:
return Cond::Else;
case clang::tok::pp_endif:
return Cond::End;
default:
return Cond::None;
}
}
// Parses tokens starting at Tok into Tree.
// If we reach an End or Else directive that ends Tree, returns it.
// If TopLevel is true, then we do not expect End and always return
// std::nullopt.
std::optional<DirectiveTree::Directive> parse(DirectiveTree *Tree,
bool TopLevel) {
auto StartsDirective =
[&, AllowDirectiveAt((const Token *)nullptr)]() mutable {
if (Tok->flag(LexFlags::StartsPPLine)) {
// If we considered a comment at the start of a PP-line, it doesn't
// start a directive but the directive can still start after it.
if (Tok->Kind == tok::comment)
AllowDirectiveAt = Tok + 1;
return Tok->Kind == tok::hash;
}
return Tok->Kind == tok::hash && AllowDirectiveAt == Tok;
};
// Each iteration adds one chunk (or returns, if we see #endif).
while (Tok->Kind != tok::eof) {
// If there's no directive here, we have a code chunk.
if (!StartsDirective()) {
const Token *Start = Tok;
do
++Tok;
while (Tok->Kind != tok::eof && !StartsDirective());
Tree->Chunks.push_back(DirectiveTree::Code{
Token::Range{Code.index(*Start), Code.index(*Tok)}});
continue;
}
// We have some kind of directive.
DirectiveTree::Directive Directive;
parseDirective(&Directive);
Cond Kind = classifyDirective(Directive.Kind);
if (Kind == Cond::If) {
// #if or similar, starting a nested conditional block.
DirectiveTree::Conditional Conditional;
Conditional.Branches.emplace_back();
Conditional.Branches.back().first = std::move(Directive);
parseConditional(&Conditional);
Tree->Chunks.push_back(std::move(Conditional));
} else if ((Kind == Cond::Else || Kind == Cond::End) && !TopLevel) {
// #endif or similar, ending this PStructure scope.
// (#endif is unexpected at the top level, treat as simple directive).
return std::move(Directive);
} else {
// #define or similar, a simple directive at the current scope.
Tree->Chunks.push_back(std::move(Directive));
}
}
return std::nullopt;
}
// Parse the rest of a conditional section, after seeing the If directive.
// Returns after consuming the End directive.
void parseConditional(DirectiveTree::Conditional *C) {
assert(C->Branches.size() == 1 &&
C->Branches.front().second.Chunks.empty() &&
"Should be ready to parse first branch body");
while (Tok->Kind != tok::eof) {
auto Terminator = parse(&C->Branches.back().second, /*TopLevel=*/false);
if (!Terminator) {
assert(Tok->Kind == tok::eof && "gave up parsing before eof?");
C->End.Tokens = Token::Range::emptyAt(Code.index(*Tok));
return;
}
if (classifyDirective(Terminator->Kind) == Cond::End) {
C->End = std::move(*Terminator);
return;
}
assert(classifyDirective(Terminator->Kind) == Cond::Else &&
"ended branch unexpectedly");
C->Branches.emplace_back();
C->Branches.back().first = std::move(*Terminator);
}
}
// Parse a directive. Tok is the hash.
void parseDirective(DirectiveTree::Directive *D) {
assert(Tok->Kind == tok::hash);
// Directive spans from the hash until the end of line or file.
const Token *Begin = Tok++;
while (Tok->Kind != tok::eof && !Tok->flag(LexFlags::StartsPPLine))
++Tok;
ArrayRef<Token> Tokens{Begin, Tok};
D->Tokens = {Code.index(*Tokens.begin()), Code.index(*Tokens.end())};
// Directive name is the first non-comment token after the hash.
Tokens = Tokens.drop_front().drop_while(
[](const Token &T) { return T.Kind == tok::comment; });
if (!Tokens.empty())
D->Kind = PPKeywords.get(Tokens.front().text()).getPPKeywordID();
}
const TokenStream &Code;
const Token *Tok;
clang::IdentifierTable PPKeywords;
};
struct Dumper {
llvm::raw_ostream &OS;
unsigned Indent = 0;
Dumper(llvm::raw_ostream& OS) : OS(OS) {}
void operator()(const DirectiveTree& Tree) {
for (const auto& Chunk : Tree.Chunks)
std::visit(*this, Chunk);
}
void operator()(const DirectiveTree::Conditional &Conditional) {
for (unsigned I = 0; I < Conditional.Branches.size(); ++I) {
const auto &Branch = Conditional.Branches[I];
(*this)(Branch.first, Conditional.Taken == I);
Indent += 2;
(*this)(Branch.second);
Indent -= 2;
}
(*this)(Conditional.End);
}
void operator()(const DirectiveTree::Directive &Directive,
bool Taken = false) {
OS.indent(Indent) << llvm::formatv(
"#{0} ({1} tokens){2}\n", tok::getPPKeywordSpelling(Directive.Kind),
Directive.Tokens.size(), Taken ? " TAKEN" : "");
}
void operator()(const DirectiveTree::Code &Code) {
OS.indent(Indent) << llvm::formatv("code ({0} tokens)\n",
Code.Tokens.size());
}
};
} // namespace
DirectiveTree DirectiveTree::parse(const TokenStream &Code) {
DirectiveTree Result;
DirectiveParser(Code).parse(&Result);
return Result;
}
// Define operator<< in terms of dump() functions above.
#define OSTREAM_DUMP(Type) \
llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, const Type &T) { \
Dumper{OS}(T); \
return OS; \
}
OSTREAM_DUMP(DirectiveTree)
OSTREAM_DUMP(DirectiveTree::Directive)
OSTREAM_DUMP(DirectiveTree::Conditional)
OSTREAM_DUMP(DirectiveTree::Code)
#undef OSTREAM_DUMP
namespace {
// Makes choices about conditional branches.
//
// Generally it tries to maximize the amount of useful code we see.
//
// Caveat: each conditional is evaluated independently. Consider this code:
// #ifdef WINDOWS
// bool isWindows = true;
// #endif
// #ifndef WINDOWS
// bool isWindows = false;
// #endif
// We take both branches and define isWindows twice. We could track more state
// in order to produce a consistent view, but this is complex.
class BranchChooser {
public:
BranchChooser(const TokenStream &Code) : Code(Code) {}
// Describes code seen by making particular branch choices. Higher is better.
struct Score {
int Tokens = 0; // excluding comments and directives
int Directives = 0;
int Errors = 0; // #error directives
bool operator>(const Score &Other) const {
// Seeing errors is bad, other things are good.
return std::make_tuple(-Errors, Tokens, Directives) >
std::make_tuple(-Other.Errors, Other.Tokens, Other.Directives);
}
Score &operator+=(const Score &Other) {
Tokens += Other.Tokens;
Directives += Other.Directives;
Errors += Other.Errors;
return *this;
}
};
Score operator()(DirectiveTree::Code &C) {
Score S;
for (const Token &T : Code.tokens(C.Tokens))
if (T.Kind != tok::comment)
++S.Tokens;
return S;
}
Score operator()(DirectiveTree::Directive &D) {
Score S;
S.Directives = 1;
S.Errors = D.Kind == tok::pp_error;
return S;
}
Score operator()(DirectiveTree::Conditional &C) {
Score Best;
bool MayTakeTrivial = true;
bool TookTrivial = false;
for (unsigned I = 0; I < C.Branches.size(); ++I) {
// Walk the branch to make its nested choices in any case.
Score BranchScore = walk(C.Branches[I].second);
// If we already took an #if 1, don't consider any other branches.
if (TookTrivial)
continue;
// Is this a trivial #if 0 or #if 1?
if (auto TriviallyTaken = isTakenWhenReached(C.Branches[I].first)) {
if (!*TriviallyTaken)
continue; // Don't consider #if 0 even if it scores well.
if (MayTakeTrivial)
TookTrivial = true;
} else {
// After a nontrivial condition, #elif 1 isn't guaranteed taken.
MayTakeTrivial = false;
}
// Is this the best branch so far? (Including if it's #if 1).
if (TookTrivial || !C.Taken || BranchScore > Best) {
Best = BranchScore;
C.Taken = I;
}
}
return Best;
}
Score walk(DirectiveTree &M) {
Score S;
for (auto &C : M.Chunks)
S += std::visit(*this, C);
return S;
}
private:
// Return true if the directive starts an always-taken conditional branch,
// false if the branch is never taken, and std::nullopt otherwise.
std::optional<bool> isTakenWhenReached(const DirectiveTree::Directive &Dir) {
switch (Dir.Kind) {
case clang::tok::pp_if:
case clang::tok::pp_elif:
break; // handled below
case clang::tok::pp_else:
return true;
default: // #ifdef etc
return std::nullopt;
}
const auto &Tokens = Code.tokens(Dir.Tokens);
assert(!Tokens.empty() && Tokens.front().Kind == tok::hash);
const Token &Name = Tokens.front().nextNC();
const Token &Value = Name.nextNC();
// Does the condition consist of exactly one token?
if (&Value >= Tokens.end() || &Value.nextNC() < Tokens.end())
return std::nullopt;
return llvm::StringSwitch<std::optional<bool>>(Value.text())
.Cases("true", "1", true)
.Cases("false", "0", false)
.Default(std::nullopt);
}
const TokenStream &Code;
};
} // namespace
void chooseConditionalBranches(DirectiveTree &Tree, const TokenStream &Code) {
BranchChooser{Code}.walk(Tree);
}
namespace {
class Preprocessor {
const TokenStream &In;
TokenStream &Out;
public:
Preprocessor(const TokenStream &In, TokenStream &Out) : In(In), Out(Out) {}
~Preprocessor() { Out.finalize(); }
void walk(const DirectiveTree &T) {
for (const auto &C : T.Chunks)
std::visit(*this, C);
}
void operator()(const DirectiveTree::Code &C) {
for (const auto &Tok : In.tokens(C.Tokens))
Out.push(Tok);
}
void operator()(const DirectiveTree::Directive &) {}
void operator()(const DirectiveTree::Conditional &C) {
if (C.Taken)
walk(C.Branches[*C.Taken].second);
}
};
} // namespace
TokenStream DirectiveTree::stripDirectives(const TokenStream &In) const {
TokenStream Out;
Preprocessor(In, Out).walk(*this);
return Out;
}
} // namespace pseudo
} // namespace clang
|