[pseudo] A basic implementation of compiling cxx grammar at build time.

[hokein]

Summary

The main idea is to compile the cxx grammar at build time, and construct
the core pieces (Grammar, LRTable) of the pseudoparse based on the compiled
data sources.

This is a tiny implementation, which is good for start:

• defines how the public API should look like;
• integrates the cxx grammar compilation workflow with the cmake system.
• onlynonterminal symbols of the C++ grammar are compiled, anything else are still doing the real compilation work at runtime, we can opt-in more bits in the future;
• splits the monolithic clangPsuedo library for better layering;

[hokein]

This is a revised version of D125231, based on our discussion. It has a narrow scope: only nonterminals of the grammar are compiled; and it mainly focuses on interfaces;

[sammccall]

Few initial comments...

clang-tools-extra/pseudo/gen/Main.cpp

9

missing description

clang-tools-extra/pseudo/include/clang-pseudo/cxx/cxx.h

35 ↗

(On Diff #429636)

enum class? I suspect having to cast these explicitly is worth it if using them is rare.

Otherwise we'll end up with rules in the same namespace as symbols, later.

37 ↗

(On Diff #429636)

we've got {cxx, Cxx} in filenames.
We should be consistent, and per LLVM style I think CXX is correct?

clang-tools-extra/pseudo/lib/CMakeLists.txt

6–7

We do have a layering relationship here, and a requirement to keep the "grammar" dependencies small - should we move it into a subdirectory?

21

why is this not in cxx/CMakeLists.txt?

clang-tools-extra/pseudo/lib/cxx/cxx.cpp

1 ↗

(On Diff #429636)

nit: interfaces

[sammccall]

clang-tools-extra/pseudo/CMakeLists.txt

3

I think these variables shared across CMakeLists.txt files generally add more confusion than value, it doesn't seem to be needed here - can we use relative paths instead?

clang-tools-extra/pseudo/gen/cxx_gen.cmake

1 ↗

(On Diff #429636)

why is this a textually included *.cmake file that adds rules, instead of a CMakeLists.txt file or a *.cmake file that provides functions?

clang-tools-extra/pseudo/include/CMakeLists.txt

2

it seems to me the build rules for files that end up in the include/ directory should go here?

[hokein]

Address comments:

• split to a grammar subdirectory
• remove cxx_gen.cmake, move it to include/CMakeLists.txt
• rename cxx -> CXX

[hokein]

format fix

clang-tools-extra/pseudo/CMakeLists.txt

3

removed

clang-tools-extra/pseudo/include/CMakeLists.txt

2

sounds a good idea, move the cxx_gen.cmake to this file.

clang-tools-extra/pseudo/lib/CMakeLists.txt

6–7

split it to a grammar subdirectory.

[sammccall]

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

18

this is worth a try, but I think (some versions of?) MSVC don't like long string literals.

Stackoverflow says 2k per "chunk" ("one" "two" "three") and 64k total.
Integer arrays can be larger...

So let's start with simple readable options, and make them progressively uglier if we hit limits.

23

static Grammar &G = *Grammar::parseBNF(...).release();
to avoid destruction

29

similarly &Table = *new LRTable(buildSLR(...));

clang-tools-extra/pseudo/lib/grammar/CMakeLists.txt

4

a comment why we want minimal deps here?

[hokein]

rebase, and emit string chunks rather than a long raw string literal (to make msvc happy)

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

18

ah, good point. And you're right -- the previous version raw string literal doesn't compile with MSVC v19 <source>(397): error C2026: string too big, trailing characters truncated. Changing to string chunks seems to work.

[smeenai]

This breaks cross-compilation, because we're building pseudo-gen for the target but then trying to run it on the build machine. You'll need to do something like TableGen does (see https://github.com/llvm/llvm-project/blob/main/llvm/cmake/modules/CrossCompile.cmake and the uses of build_native_tool). That being said, I'm trying to figure out why our builds are attempting to build this in the first place, since as far as I can tell nothing external depends on it yet.

EDIT: Ah, it's because we're building an umbrella target (clang-libraries), so the library targets introduced here will be naturally folded into it (because of add_clang_library). Could we please get cross-compilation fixed here, and revert if it'll take a while?

[sammccall]

I'll see if I can fix it quickly, else will revert (there are a couple of fixes stacked on top already, so revert isn't quite clean)

[smeenai]

In D125667#3537655, @sammccall wrote:

I'll see if I can fix it quickly, else will revert (there are a couple of fixes stacked on top already, so revert isn't quite clean)

Thank you! I'll have some time to look at this a bit later myself as well, and it should hopefully be a quick fix, so we can try to avoid the revert :)

[smeenai]

In D125667#3537678, @smeenai wrote:

In D125667#3537655, @sammccall wrote:

I'll see if I can fix it quickly, else will revert (there are a couple of fixes stacked on top already, so revert isn't quite clean)

Thank you! I'll have some time to look at this a bit later myself as well, and it should hopefully be a quick fix, so we can try to avoid the revert :)

D126397

clang-tools-extra/pseudo/CMakeLists.txt

 include_directories(include)
 include_directories(${CMAKE_CURRENT_BINARY_DIR}/include)
+add_subdirectory(include)
+add_subdirectory(gen)
 add_subdirectory(lib)
 add_subdirectory(tool)
 add_subdirectory(fuzzer)
 add_subdirectory(benchmarks)
 if(CLANG_INCLUDE_TESTS)
   add_subdirectory(unittests)
   add_subdirectory(test)
 endif()

clang-tools-extra/pseudo/gen/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS Support)
+
+add_clang_executable(pseudo-gen
+  Main.cpp
+  )
+
+target_link_libraries(pseudo-gen
+  PRIVATE
+  clangPseudoGrammar
+  )

clang-tools-extra/pseudo/gen/Main.cpp

+//===--- Main.cpp - Compile BNF grammar -----------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This is a tool to compile a BNF grammar, it is used by the build system to
+// generate a necessary data bits to statically construct core pieces (Grammar,
+// LRTable etc) of the LR parser.
+//
+//===----------------------------------------------------------------------===//
+
+#include "clang-pseudo/Grammar.h"
+#include "llvm/ADT/StringExtras.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/FormatVariadic.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include <algorithm>
+
+using llvm::cl::desc;
+using llvm::cl::init;
+using llvm::cl::opt;
+using llvm::cl::values;
+
+namespace {
+enum EmitType {
+  EmitSymbolList,
+  EmitGrammarContent,
+};
+
+opt<std::string> Grammar("grammar", desc("Parse a BNF grammar file."),
+                         init(""));
+opt<EmitType>
+    Emit(desc("which information to emit:"),
+         values(clEnumValN(EmitSymbolList, "emit-symbol-list",
+                           "Print nonterminal symbols (default)"),
+                clEnumValN(EmitGrammarContent, "emit-grammar-content",
+                           "Print the BNF grammar content as a string")));
+std::string readOrDie(llvm::StringRef Path) {
+  llvm::ErrorOr<std::unique_ptr<llvm::MemoryBuffer>> Text =
+      llvm::MemoryBuffer::getFile(Path);
+  if (std::error_code EC = Text.getError()) {
+    llvm::errs() << "Error: can't read grammar file '" << Path
+                 << "': " << EC.message() << "\n";
+    ::exit(1);
+  }
+  return Text.get()->getBuffer().str();
+}
+} // namespace
+
+int main(int argc, char *argv[]) {
+  llvm::cl::ParseCommandLineOptions(argc, argv, "");
+  if (!Grammar.getNumOccurrences()) {
+    llvm::errs() << "Grammar file must be provided!\n";
+    return 1;
+  }
+
+  std::string GrammarText = readOrDie(Grammar);
+  std::vector<std::string> Diags;
+  auto G = clang::pseudo::Grammar::parseBNF(GrammarText, Diags);
+
+  if (!Diags.empty()) {
+    llvm::errs() << llvm::join(Diags, "\n");
+    return 1;
+  }
+  switch (Emit) {
+
+  case EmitSymbolList:
+    for (clang::pseudo::SymbolID ID = 0; ID < G->table().Nonterminals.size();
+         ++ID) {
+      std::string Name = G->symbolName(ID).str();
+      // translation-unit -> translation_unit
+      std::replace(Name.begin(), Name.end(), '-', '_');
+      llvm::outs() << (llvm::formatv("NONTERMINAL({0}, {1})\n", Name, ID));
+    }
+    break;
+  case EmitGrammarContent:
+    for (llvm::StringRef Line : llvm::split(GrammarText, '\n')) {
+      llvm::outs() << '"';
+      llvm::outs().write_escaped((Line + "\n").str());
+      llvm::outs() << "\"\n";
+    }
+    break;
+  }
+
+  return 0;
+}

clang-tools-extra/pseudo/include/CMakeLists.txt

+# The cxx.bnf grammar file
+set(cxx_bnf ${CMAKE_CURRENT_SOURCE_DIR}/../lib/cxx.bnf)
+
+# Generate inc files.
+set(cxx_symbols_inc ${CMAKE_CURRENT_BINARY_DIR}/CXXSymbols.inc)
+add_custom_command(OUTPUT ${cxx_symbols_inc}
+   COMMAND "${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/pseudo-gen"
+     --grammar ${cxx_bnf}
+     --emit-symbol-list
+     > ${cxx_symbols_inc}
+   COMMENT "Generating nonterminal symbol file for cxx grammar..."
+   DEPENDS pseudo-gen
+   VERBATIM)
+
+set(cxx_bnf_inc ${CMAKE_CURRENT_BINARY_DIR}/CXXBNF.inc)
+add_custom_command(OUTPUT ${cxx_bnf_inc}
+   COMMAND "${CMAKE_RUNTIME_OUTPUT_DIRECTORY}/pseudo-gen"
+     --grammar ${cxx_bnf}
+     --emit-grammar-content
+     > ${cxx_bnf_inc}
+   COMMENT "Generating bnf string file for cxx grammar..."
+   DEPENDS pseudo-gen
+   VERBATIM)
+
+# add_custom_command does not create a new target, we need to deine a target
+# explicitly, so that other targets can depend on it.
+add_custom_target(cxx_gen
+    DEPENDS ${cxx_symbols_inc} ${cxx_bnf_inc}
+    VERBATIM)

clang-tools-extra/pseudo/include/clang-pseudo/cxx/CXX.h

+//===--- CXX.h - Public interfaces for the C++ grammar -----------*- C++-*-===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines public interfaces for the C++ grammar
+//  (pseudo/lib/cxx.bnf). It provides a fast way to access core building pieces
+//  of the LR parser, e.g. Grammar, LRTable, rather than parsing the grammar
+//  file at the runtime.
+//
+//  We do a compilation of the C++ BNF grammar at build time, and generate
+//  critical data sources. The implementation of the interfaces are based on the
+//  generated data sources.
+//
+//  FIXME: not everything is fully compiled yet. The implementation of the
+//  interfaces are still parsing the grammar file at the runtime.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef CLANG_PSEUDO_CXX_CXX_H
+#define CLANG_PSEUDO_CXX_CXX_H
+
+#include "clang-pseudo/Grammar.h"
+
+namespace clang {
+namespace pseudo {
+class LRTable;
+
+namespace cxx {
+// Symbol represents nonterminal symbols in the C++ grammar.
+// It provides a simple uniform way to access a particular nonterminal.
+enum class Symbol : SymbolID {
+#define NONTERMINAL(X, Y) X = Y,
+#include "CXXSymbols.inc"
+#undef NONTERMINAL
+};
+
+// Returns the C++ grammar.
+const Grammar &getGrammar();
+// Returns the corresponding LRTable for the C++ grammar.
+const LRTable &getLRTable();
+
+} // namespace cxx
+
+} // namespace pseudo
+} // namespace clang
+
+#endif // CLANG_PSEUDO_CXX_CXX_H

clang-tools-extra/pseudo/lib/CMakeLists.txt

+add_subdirectory(cxx)
+add_subdirectory(grammar)
+
 set(LLVM_LINK_COMPONENTS Support)
 
 add_clang_library(clangPseudo
   Bracket.cpp
   DirectiveTree.cpp
   Forest.cpp
   GLR.cpp
-  Grammar.cpp
-  GrammarBNF.cpp
   Lex.cpp
-  LRGraph.cpp
-  LRTable.cpp
-  LRTableBuild.cpp
   Token.cpp
 
   LINK_LIBS
   clangBasic
   clangLex
+  clangPseudoGrammar
   )

clang-tools-extra/pseudo/lib/cxx/CMakeLists.txt

+add_clang_library(clangPseudoCXX
+  CXX.cpp
+
+  DEPENDS
+  cxx_gen
+
+  LINK_LIBS
+  clangPseudoGrammar
+  )

clang-tools-extra/pseudo/lib/cxx/CXX.cpp

+//===--- CXX.cpp - Define public interfaces for C++ grammar ---------------===//
+//
+// 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/cxx/CXX.h"
+#include "clang-pseudo/LRTable.h"
+
+namespace clang {
+namespace pseudo {
+namespace cxx {
+
+static const char *CXXBNF =
+#include "CXXBNF.inc"
+    ;
+
+const Grammar &getGrammar() {
+  static std::vector<std::string> Diags;
+  static Grammar *G = Grammar::parseBNF(CXXBNF, Diags).release();
+  assert(Diags.empty());
+  return *G;
+}
+
+const LRTable &getLRTable() {
+  static LRTable *Table = new LRTable(LRTable::buildSLR(getGrammar()));
+  return *Table;
+}
+
+} // namespace cxx
+} // namespace pseudo
+} // namespace clang

clang-tools-extra/pseudo/lib/grammar/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS Support)
+
+# This library intents to keep as minimal dependencies as possible, it is a base
+# library of the cxx generator, to avoid creating long dep paths in the build
+# graph.
+add_clang_library(clangPseudoGrammar
+  Grammar.cpp
+  GrammarBNF.cpp
+  LRGraph.cpp
+  LRTable.cpp
+  LRTableBuild.cpp
+
+  # FIXME: can we get rid of the clangBasic dependency? We need it for the
+  # clang::tok::getTokenName and clang::tok::getPunctuatorSpelling functions, we
+  # could consider remimplement these functions.
+  LINK_LIBS
+  clangBasic
+  )