| 1 |
//===-- ClangPseudo.cpp - Clang pseudoparser tool -------------------------===// |
| 2 |
// |
| 3 |
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 |
// See https://llvm.org/LICENSE.txt for license information. |
| 5 |
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 |
// |
| 7 |
//===----------------------------------------------------------------------===// |
| 8 |
|
| 9 |
#include "clang-pseudo/Bracket.h" |
| 10 |
#include "clang-pseudo/DirectiveTree.h" |
| 11 |
#include "clang-pseudo/Disambiguate.h" |
| 12 |
#include "clang-pseudo/Forest.h" |
| 13 |
#include "clang-pseudo/GLR.h" |
| 14 |
#include "clang-pseudo/Language.h" |
| 15 |
#include "clang-pseudo/Token.h" |
| 16 |
#include "clang-pseudo/cli/CLI.h" |
| 17 |
#include "clang-pseudo/grammar/Grammar.h" |
| 18 |
#include "clang-pseudo/grammar/LRGraph.h" |
| 19 |
#include "clang-pseudo/grammar/LRTable.h" |
| 20 |
#include "clang/Basic/LangOptions.h" |
| 21 |
#include "llvm/ADT/STLExtras.h" |
| 22 |
#include "llvm/ADT/STLFunctionalExtras.h" |
| 23 |
#include "llvm/Support/CommandLine.h" |
| 24 |
#include "llvm/Support/FormatVariadic.h" |
| 25 |
#include "llvm/Support/MemoryBuffer.h" |
| 26 |
#include "llvm/Support/Signals.h" |
| 27 |
#include <optional> |
| 28 |
|
| 29 |
using clang::pseudo::ForestNode; |
| 30 |
using clang::pseudo::Token; |
| 31 |
using clang::pseudo::TokenStream; |
| 32 |
using llvm::cl::desc; |
| 33 |
using llvm::cl::init; |
| 34 |
using llvm::cl::opt; |
| 35 |
|
| 36 |
static opt<bool> PrintGrammar("print-grammar", desc("Print the grammar")); |
| 37 |
static opt<bool> PrintGraph("print-graph", |
| 38 |
desc("Print the LR graph for the grammar")); |
| 39 |
static opt<bool> PrintTable("print-table", |
| 40 |
desc("Print the LR table for the grammar")); |
| 41 |
static opt<std::string> Source("source", desc("Source file")); |
| 42 |
static opt<bool> PrintSource("print-source", desc("Print token stream")); |
| 43 |
static opt<bool> PrintTokens("print-tokens", desc("Print detailed token info")); |
| 44 |
static opt<bool> |
| 45 |
PrintDirectiveTree("print-directive-tree", |
| 46 |
desc("Print directive structure of source code")); |
| 47 |
static opt<bool> |
| 48 |
StripDirectives("strip-directives", |
| 49 |
desc("Strip directives and select conditional sections")); |
| 50 |
static opt<bool> Disambiguate("disambiguate", |
| 51 |
desc("Choose best tree from parse forest")); |
| 52 |
static opt<bool> PrintStatistics("print-statistics", desc("Print GLR parser statistics")); |
| 53 |
static opt<bool> PrintForest("print-forest", desc("Print parse forest")); |
| 54 |
static opt<bool> ForestAbbrev("forest-abbrev", desc("Abbreviate parse forest"), |
| 55 |
init(true)); |
| 56 |
static opt<std::string> HTMLForest("html-forest", |
| 57 |
desc("output file for HTML forest")); |
| 58 |
static opt<std::string> StartSymbol("start-symbol", |
| 59 |
desc("Specify the start symbol to parse"), |
| 60 |
init("translation-unit")); |
| 61 |
|
| 62 |
static std::string readOrDie(llvm::StringRef Path) { |
| 63 |
llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text = |
| 64 |
llvm::MemoryBuffer::getFile(Path); |
| 65 |
if (std::error_code EC = Text.getError()) { |
| 66 |
llvm::errs() << "Error: can't read file '" << Path |
| 67 |
<< "': " << EC.message() << "\n"; |
| 68 |
::exit(1); |
| 69 |
} |
| 70 |
return Text.get()->getBuffer().str(); |
| 71 |
} |
| 72 |
|
| 73 |
namespace clang { |
| 74 |
namespace pseudo { |
| 75 |
// Defined in HTMLForest.cpp |
| 76 |
void writeHTMLForest(llvm::raw_ostream &OS, const Grammar &, |
| 77 |
const ForestNode &Root, const Disambiguation &, |
| 78 |
const TokenStream &); |
| 79 |
namespace { |
| 80 |
|
| 81 |
struct NodeStats { |
| 82 |
unsigned Total = 0; |
| 83 |
std::vector<std::pair<SymbolID, unsigned>> BySymbol; |
| 84 |
|
| 85 |
NodeStats(const ForestNode &Root, |
| 86 |
llvm::function_ref<bool(const ForestNode &)> Filter) { |
| 87 |
llvm::DenseMap<SymbolID, unsigned> Map; |
| 88 |
for (const ForestNode &N : Root.descendants()) |
| 89 |
if (Filter(N)) { |
| 90 |
++Total; |
| 91 |
++Map[N.symbol()]; |
| 92 |
} |
| 93 |
BySymbol = {Map.begin(), Map.end()}; |
| 94 |
// Sort by count descending, then symbol ascending. |
| 95 |
llvm::sort(BySymbol, [](const auto &L, const auto &R) { |
| 96 |
return std::tie(R.second, L.first) < std::tie(L.second, R.first); |
| 97 |
}); |
| 98 |
} |
| 99 |
}; |
| 100 |
|
| 101 |
} // namespace |
| 102 |
} // namespace pseudo |
| 103 |
} // namespace clang |
| 104 |
|
| 105 |
int main(int argc, char *argv[]) { |
| 106 |
llvm::cl::ParseCommandLineOptions(argc, argv, ""); |
| 107 |
llvm::sys::PrintStackTraceOnErrorSignal(argv[0]); |
| 108 |
|
| 109 |
clang::LangOptions LangOpts = clang::pseudo::genericLangOpts(); |
| 110 |
std::string SourceText; |
| 111 |
std::optional<clang::pseudo::TokenStream> RawStream; |
| 112 |
std::optional<TokenStream> PreprocessedStream; |
| 113 |
std::optional<clang::pseudo::TokenStream> ParseableStream; |
| 114 |
if (Source.getNumOccurrences()) { |
| 115 |
SourceText = readOrDie(Source); |
| 116 |
RawStream = clang::pseudo::lex(SourceText, LangOpts); |
| 117 |
TokenStream *Stream = &*RawStream; |
| 118 |
|
| 119 |
auto DirectiveStructure = clang::pseudo::DirectiveTree::parse(*RawStream); |
| 120 |
clang::pseudo::chooseConditionalBranches(DirectiveStructure, *RawStream); |
| 121 |
|
| 122 |
std::optional<TokenStream> Preprocessed; |
| 123 |
if (StripDirectives) { |
| 124 |
Preprocessed = DirectiveStructure.stripDirectives(*Stream); |
| 125 |
Stream = &*Preprocessed; |
| 126 |
} |
| 127 |
|
| 128 |
if (PrintSource) |
| 129 |
Stream->print(llvm::outs()); |
| 130 |
if (PrintTokens) |
| 131 |
llvm::outs() << *Stream; |
| 132 |
if (PrintDirectiveTree) |
| 133 |
llvm::outs() << DirectiveStructure; |
| 134 |
|
| 135 |
ParseableStream = clang::pseudo::stripComments(cook(*Stream, LangOpts)); |
| 136 |
pairBrackets(*ParseableStream); |
| 137 |
} |
| 138 |
|
| 139 |
const auto &Lang = clang::pseudo::getLanguageFromFlags(); |
| 140 |
if (PrintGrammar) |
| 141 |
llvm::outs() << Lang.G.dump(); |
| 142 |
if (PrintGraph) |
| 143 |
llvm::outs() << clang::pseudo::LRGraph::buildLR0(Lang.G).dumpForTests( |
| 144 |
Lang.G); |
| 145 |
|
| 146 |
if (PrintTable) |
| 147 |
llvm::outs() << Lang.Table.dumpForTests(Lang.G); |
| 148 |
if (PrintStatistics) |
| 149 |
llvm::outs() << Lang.Table.dumpStatistics(); |
| 150 |
|
| 151 |
if (ParseableStream) { |
| 152 |
clang::pseudo::ForestArena Arena; |
| 153 |
clang::pseudo::GSS GSS; |
| 154 |
std::optional<clang::pseudo::SymbolID> StartSymID = |
| 155 |
Lang.G.findNonterminal(StartSymbol); |
| 156 |
if (!StartSymID) { |
| 157 |
llvm::errs() << llvm::formatv( |
| 158 |
"The start symbol {0} doesn't exit in the grammar!\n", StartSymbol); |
| 159 |
return 2; |
| 160 |
} |
| 161 |
auto &Root = |
| 162 |
glrParse(clang::pseudo::ParseParams{*ParseableStream, Arena, GSS}, |
| 163 |
*StartSymID, Lang); |
| 164 |
// If we're disambiguating, we'll print at the end instead. |
| 165 |
if (PrintForest && !Disambiguate) |
| 166 |
llvm::outs() << Root.dumpRecursive(Lang.G, /*Abbreviated=*/ForestAbbrev); |
| 167 |
clang::pseudo::Disambiguation Disambig; |
| 168 |
if (Disambiguate) |
| 169 |
Disambig = clang::pseudo::disambiguate(&Root, {}); |
| 170 |
|
| 171 |
if (HTMLForest.getNumOccurrences()) { |
| 172 |
std::error_code EC; |
| 173 |
llvm::raw_fd_ostream HTMLOut(HTMLForest, EC); |
| 174 |
if (EC) { |
| 175 |
llvm::errs() << "Couldn't write " << HTMLForest << ": " << EC.message() |
| 176 |
<< "\n"; |
| 177 |
return 2; |
| 178 |
} |
| 179 |
clang::pseudo::writeHTMLForest(HTMLOut, Lang.G, Root, Disambig, |
| 180 |
*ParseableStream); |
| 181 |
} |
| 182 |
|
| 183 |
if (PrintStatistics) { |
| 184 |
llvm::outs() << "Forest bytes: " << Arena.bytes() |
| 185 |
<< " nodes: " << Arena.nodeCount() << "\n"; |
| 186 |
llvm::outs() << "GSS bytes: " << GSS.bytes() |
| 187 |
<< " nodes: " << GSS.nodesCreated() << "\n"; |
| 188 |
|
| 189 |
for (auto &P : {std::make_pair("Ambiguous", ForestNode::Ambiguous), |
| 190 |
std::make_pair("Opaque", ForestNode::Opaque)}) { |
| 191 |
clang::pseudo::NodeStats Stats( |
| 192 |
Root, [&](const auto &N) { return N.kind() == P.second; }); |
| 193 |
llvm::outs() << "\n" << Stats.Total << " " << P.first << " nodes:\n"; |
| 194 |
for (const auto &S : Stats.BySymbol) |
| 195 |
llvm::outs() << llvm::formatv(" {0,3} {1}\n", S.second, |
| 196 |
Lang.G.symbolName(S.first)); |
| 197 |
} |
| 198 |
|
| 199 |
// Metrics for how imprecise parsing was. |
| 200 |
// These are rough but aim to be: |
| 201 |
// - linear: if we eliminate half the errors the metric should halve |
| 202 |
// - length-independent |
| 203 |
unsigned UnparsedTokens = 0; // Tokens covered by Opaque. (not unique) |
| 204 |
unsigned Misparses = 0; // Sum of alternatives-1 |
| 205 |
llvm::DenseSet<const ForestNode *> Visited; |
| 206 |
auto DFS = [&](const ForestNode &N, Token::Index End, auto &DFS) -> void { |
| 207 |
if (N.kind() == ForestNode::Opaque) { |
| 208 |
UnparsedTokens += End - N.startTokenIndex(); |
| 209 |
} else if (N.kind() == ForestNode::Ambiguous) { |
| 210 |
Misparses += N.alternatives().size() - 1; |
| 211 |
for (const auto *C : N.alternatives()) |
| 212 |
if (Visited.insert(C).second) |
| 213 |
DFS(*C, End, DFS); |
| 214 |
} else if (N.kind() == ForestNode::Sequence) { |
| 215 |
for (unsigned I = 0, E = N.children().size(); I < E; ++I) |
| 216 |
if (Visited.insert(N.children()[I]).second) |
| 217 |
DFS(*N.children()[I], |
| 218 |
I + 1 == N.children().size() |
| 219 |
? End |
| 220 |
: N.children()[I + 1]->startTokenIndex(), |
| 221 |
DFS); |
| 222 |
} |
| 223 |
}; |
| 224 |
unsigned Len = ParseableStream->tokens().size(); |
| 225 |
DFS(Root, Len, DFS); |
| 226 |
llvm::outs() << "\n"; |
| 227 |
llvm::outs() << llvm::formatv("Ambiguity: {0} misparses/token\n", |
| 228 |
double(Misparses) / Len); |
| 229 |
llvm::outs() << llvm::formatv("Unparsed: {0}%\n", |
| 230 |
100.0 * UnparsedTokens / Len); |
| 231 |
} |
| 232 |
|
| 233 |
if (Disambiguate && PrintForest) { |
| 234 |
ForestNode *DisambigRoot = &Root; |
| 235 |
removeAmbiguities(DisambigRoot, Disambig); |
| 236 |
llvm::outs() << "Disambiguated tree:\n"; |
| 237 |
llvm::outs() << DisambigRoot->dumpRecursive(Lang.G, |
| 238 |
/*Abbreviated=*/ForestAbbrev); |
| 239 |
} |
| 240 |
} |
| 241 |
|
| 242 |
return 0; |
| 243 |
} |