// Part of the Carbon Language project, under the Apache License v2.0 with LLVM // Exceptions. See /LICENSE for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception #ifndef CARBON_TOOLCHAIN_LEX_TOKENIZED_BUFFER_H_ #define CARBON_TOOLCHAIN_LEX_TOKENIZED_BUFFER_H_ #include #include "common/check.h" #include "common/ostream.h" #include "llvm/ADT/APInt.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/StringRef.h" #include "llvm/ADT/iterator_range.h" #include "llvm/Support/Allocator.h" #include "llvm/Support/raw_ostream.h" #include "toolchain/base/index_base.h" #include "toolchain/base/mem_usage.h" #include "toolchain/base/shared_value_stores.h" #include "toolchain/diagnostics/emitter.h" #include "toolchain/lex/source_loc.h" #include "toolchain/lex/token_index.h" #include "toolchain/lex/token_info.h" #include "toolchain/lex/token_kind.h" #include "toolchain/source/source_buffer.h" namespace Carbon::Lex { class TokenizedBuffer; struct LineInfo { explicit LineInfo(int32_t start) : start(start), indent(0) {} // Zero-based byte offset of the start of the line within the source buffer // provided. int32_t start; // The byte offset from the start of the line of the first non-whitespace // character. int32_t indent; }; // A lightweight handle to a lexed `LineInfo` in a `TokenizedBuffer`. // // `LineIndex` objects are designed to be passed by value, not reference or // pointer. They are also designed to be small and efficient to store in data // structures. // // Each `LineIndex` object refers to a specific line in the source code that was // lexed. They can be compared directly to establish that they refer to the // same line or the relative position of different lines within the source. // // All other APIs to query a `LineIndex` are on the `TokenizedBuffer`. struct LineIndex : public IndexBase { static constexpr llvm::StringLiteral Label = "line"; static const LineIndex None; using IndexBase::IndexBase; }; inline constexpr LineIndex LineIndex::None(NoneIndex); // A comment, which can be a block of lines. These are tracked separately from // tokens because they don't affect parse; if they were part of tokens, we'd // need more general special-casing within token logic. // // Note that `CommentInfo` is used for an API to expose the comment. struct CommentData { // Zero-based byte offset of the start of the comment within the source // buffer provided. int32_t start; // The comment's length, in the low 31 bits. The high bit is stolen for // `is_trailing` below to keep `CommentData` at 8 bytes. A byte length is // non-negative and the source size is required to be less than `INT32_MAX` // (see `Lex`), so the length always fits in 31 bits. uint32_t length : 31; // Whether this is a _trailing_ comment: one that follows other content on its // line, rather than being the only non-whitespace on the line. Trailing // comments are never coalesced with adjacent comments. uint32_t is_trailing : 1; }; static_assert(sizeof(CommentData) == 8, "CommentData should pack to 8 bytes"); // Indices for `CommentData` within the buffer. struct CommentIndex : public IndexBase { static constexpr llvm::StringLiteral Label = "comment"; static const CommentIndex None; using IndexBase::IndexBase; }; inline constexpr CommentIndex CommentIndex::None(NoneIndex); // Random-access iterator over comments within the buffer. using CommentIterator = IndexIterator; // Random-access iterator over tokens within the buffer. using TokenIterator = IndexIterator; // A token range which is inclusive of the begin and end. struct InclusiveTokenRange { TokenIndex begin; TokenIndex end; }; // A buffer of tokenized Carbon source code. // // This is constructed by lexing the source code text into a series of tokens. // The buffer provides lightweight handles to tokens and other lexed entities, // as well as iterations to walk the sequence of tokens found in the buffer. // // Lexing errors result in a potentially incomplete sequence of tokens and // `HasError` returning true. class TokenizedBuffer : public Printable { public: // A comment, which can be a block of lines. // // This is the API version of `CommentData`. struct CommentInfo { // The comment's full text, including `//` symbols. This may have several // lines for block comments. llvm::StringRef text; // The comment's indent. int32_t indent; // The first line of the comment. LineIndex start_line; }; // The number of `TokenKind::FileEnd` entries guaranteed to follow the last // token in the array returned by `kind_data`. static constexpr int32_t KindDataPadding = 64; auto GetKind(TokenIndex token) const -> TokenKind; // Returns a flat, contiguous array of the kinds of all tokens, indexed by // `TokenIndex`. The first `size()` entries are the kinds of the tokens, and // they are followed by at least `KindDataPadding` entries of // `TokenKind::FileEnd` so that callers can scan past the end of the tokens // without bounds checks, for example with SIMD loads. // // The returned pointer is invalidated by // `AddPostLexingRecoveryTokenAsIdentifier`. auto kind_data() const -> const TokenKind* { return token_kinds_.data(); } auto GetLine(TokenIndex token) const -> LineIndex; // Returns the 1-based line number. auto GetLineNumber(TokenIndex token) const -> int; // Returns the 1-based column number. auto GetColumnNumber(TokenIndex token) const -> int; // Returns the line and 1-based column number of the first character after // this token. auto GetEndLoc(TokenIndex token) const -> std::pair; // Returns the source text lexed into this token. auto GetTokenText(TokenIndex token) const -> llvm::StringRef; // Returns the identifier associated with this token. The token kind must be // an `Identifier`. auto GetIdentifier(TokenIndex token) const -> IdentifierId; // Returns the value of an `IntLiteral` token. auto GetIntLiteral(TokenIndex token) const -> IntId; // Returns the value of an `RealLiteral` token. auto GetRealLiteral(TokenIndex token) const -> RealId; // Returns the value of a `StringLiteral` token. auto GetStringLiteralValue(TokenIndex token) const -> StringLiteralValueId; // Returns the value of a `CharLiteral` token. auto GetCharLiteralValue(TokenIndex token) const -> CharLiteralValue; // Returns the size specified in a `*TypeLiteral` token. auto GetTypeLiteralSize(TokenIndex token) const -> IntId; // Returns the closing token matched with the given opening token. // // The given token must be an opening token kind. auto GetMatchedClosingToken(TokenIndex opening_token) const -> TokenIndex; // Returns the opening token matched with the given closing token. // // The given token must be a closing token kind. auto GetMatchedOpeningToken(TokenIndex closing_token) const -> TokenIndex; // Returns whether the given token has leading whitespace. auto HasLeadingWhitespace(TokenIndex token) const -> bool; // Returns whether the given token has trailing whitespace. auto HasTrailingWhitespace(TokenIndex token) const -> bool; // Returns whether the token was spelled as a raw identifier. auto IsRawIdentifier(TokenIndex token) const -> bool; // Returns whether the token was created as part of an error recovery effort. // // For example, a closing paren inserted to match an unmatched paren. auto IsRecoveryToken(TokenIndex token) const -> bool; // Adds and returns the index of an identifier token formed from the spelling // of the given word token. This should only be used for error recovery // purposes, when a phase after the lexer determines that a word token was // intended to represent an identifier rather than its special meaning. // // TODO: Recover with a raw identifier only when it names something, perhaps // with a note suggesting `r#` otherwise. The parser recovers with one for any // reserved word it takes as a name, so check cascades, for example to "name // `r#Cpp` not found" on `class Cpp.C {}`. auto AddPostLexingRecoveryTokenAsIdentifier(TokenIndex token) -> TokenIndex; // Returns the 1-based indentation column number. auto GetIndentColumnNumber(LineIndex line) const -> int; auto GetByteOffset(TokenIndex token) const -> int32_t { return token_infos_.Get(token).byte_offset(); } // Returns true if the token comes after the comment. auto IsAfterComment(TokenIndex token, CommentIndex comment_index) const -> bool; // Returns the comment's full text range. auto GetCommentText(CommentIndex comment_index) const -> llvm::StringRef; // Returns whether the comment is a trailing comment: one that follows other // content on its line. auto IsTrailingComment(CommentIndex comment_index) const -> bool; // Returns the line the comment begins on. auto GetLine(CommentIndex comment) const -> LineIndex; // Returns tokens as YAML. This prints the tracked token information on a // single line for each token. We use the single-line format so that output is // compact, and so that tools like `grep` are compatible. // // An example token looks like: // // - { index: 1, kind: 'Semi', line: 1, column: 1, indent: 1, spelling: ';' } auto Print(llvm::raw_ostream& out, bool omit_file_boundary_tokens = false) const -> void; // Prints a description of a single token. See `Print` for details on the // format. auto PrintToken(llvm::raw_ostream& output_stream, TokenIndex token) const -> void; // Collects memory usage of members. auto CollectMemUsage(MemUsage& mem_usage, llvm::StringRef label) const -> void; // Converts a token to a diagnostic location. auto TokenToDiagnosticLoc(TokenIndex token) const -> Diagnostics::ConvertedLoc; // Converts a run of tokens to a diagnostic location. A run spanning lines // covers the rest of its first line. auto TokenRangeToDiagnosticLoc(InclusiveTokenRange tokens) const -> Diagnostics::ConvertedLoc; // Converts the point just past `token`, where something missing after it // would be written, to a diagnostic location. auto PointAfterTokenToDiagnosticLoc(TokenIndex token) const -> Diagnostics::ConvertedLoc; // Returns true if the given range overlaps with an entry in // `dump_sem_ir_ranges_`. Must not be called when there are no ranges; query // `has_dump_sem_ir_ranges` first. auto OverlapsWithDumpSemIRRange(Lex::InclusiveTokenRange range) const -> bool; // Returns true if the buffer has errors that were detected at lexing time. auto has_errors() const -> bool { return has_errors_; } // Returns the tokens produced by lexing the source file. This includes any // recovery tokens inserted inline by lexing, such as matching brackets, but // excludes recovery tokens added after lexing finished. auto tokens() const -> llvm::iterator_range { return llvm::make_range(TokenIterator(TokenIndex(0)), TokenIterator(TokenIndex(num_lexed_tokens()))); } auto size() const -> int { return token_infos_.size(); } auto comments() const -> llvm::iterator_range { return llvm::make_range(CommentIterator(CommentIndex(0)), CommentIterator(CommentIndex(comments_.size()))); } auto comments_size() const -> size_t { return comments_.size(); } auto has_include_in_dumps() const -> bool { return has_include_in_dumps_; } // Returns true if any `DumpSemIRRange`s were provided. auto has_dump_sem_ir_ranges() const -> bool { return !dump_sem_ir_ranges_.empty(); } // This is an upper bound on the number of output parse nodes in the absence // of errors. auto expected_max_parse_tree_size() const -> int { return expected_max_parse_tree_size_; } auto source() const -> const SourceBuffer& { return *source_; } private: friend class Lexer; class SourceLocDiagnosticEmitter : public Diagnostics::Emitter { public: explicit SourceLocDiagnosticEmitter(Diagnostics::Consumer* consumer, const TokenizedBuffer* tokens) : Emitter(consumer), tokens_(tokens) {} protected: auto ConvertLoc(SourceLoc loc, ContextFnT /*context_fn*/) const -> Diagnostics::ConvertedLoc override { auto converted = tokens_->SourcePointerToDiagnosticLoc(loc.text().begin()); converted.loc.length = loc.text().size(); return converted; } private: const TokenizedBuffer* tokens_; }; class TokenDiagnosticEmitter : public Diagnostics::Emitter { public: explicit TokenDiagnosticEmitter(Diagnostics::Consumer* consumer, const TokenizedBuffer* tokens) : Emitter(consumer), tokens_(tokens) {} protected: auto ConvertLoc(TokenIndex token, ContextFnT /*context_fn*/) const -> Diagnostics::ConvertedLoc override { return tokens_->TokenToDiagnosticLoc(token); } private: const TokenizedBuffer* tokens_; }; // Converts a pointer into the source to a diagnostic location. auto SourcePointerToDiagnosticLoc(const char* loc) const -> Diagnostics::ConvertedLoc; // Specifies minimum widths to use when printing a token's fields via // `printToken`. struct PrintWidths { // Widens `this` to the maximum of `this` and `new_width` for each // dimension. auto Widen(const PrintWidths& widths) -> void; int index; int kind; int line; int column; int indent; }; // The constructor is merely responsible for trivial initialization of // members. A working object of this type is built with `Lex::Lex` so that its // return can indicate if an error was encountered while lexing. explicit TokenizedBuffer(SharedValueStores& value_stores [[clang::lifetimebound]], SourceBuffer& source [[clang::lifetimebound]]) : value_stores_(&value_stores), source_(&source) {} auto FindLineIndex(int32_t byte_offset) const -> LineIndex; // Returns the number of tokens produced by lexing, excluding recovery tokens // added after lexing finished. This is the end of the `tokens()` range. auto num_lexed_tokens() const -> int32_t { return token_infos_.size() - post_lexing_recovery_tokens_; } // Adds the token and adjusts the expected tree size. auto AddToken(TokenInfo info) -> TokenIndex; // Builds `token_kinds_` and `token_has_leading_space_` from `token_infos_`, // including the `FileEnd` padding. The lexer calls this once its token // sequence is complete, and again if bracket recovery rewrites the sequence. // Until then, `GetKind`, `HasLeadingWhitespace`, and `HasTrailingWhitespace` // must not be used; the lexer reads `token_infos_` directly instead. auto BuildTokenArrays() -> void; // Adds a post-lexing recovery token and adjusts the buffer state. auto AddPostLexingRecoveryToken(TokenInfo info) -> TokenIndex; auto GetTokenPrintWidths(TokenIndex token) const -> PrintWidths; auto PrintToken(llvm::raw_ostream& output_stream, TokenIndex token, PrintWidths widths) const -> void; // Adds a comment. For full-line comments (`is_trailing` is false), this uses // the indent to potentially stitch together two adjacent comments into a // single block. Trailing comments are never stitched, either onto a preceding // comment or as the target of a following one. auto AddComment(int32_t indent, int32_t start, int32_t end, bool is_trailing) -> void; // Used to allocate computed string literals. llvm::BumpPtrAllocator allocator_; SharedValueStores* value_stores_; SourceBuffer* source_; ValueStore token_infos_; // The kind of each token in `token_infos_`, as a flat array indexed by the // token index, followed by `KindDataPadding` entries of `TokenKind::FileEnd`. // The kind is also stored in each `TokenInfo`, but this flat array makes the // kind, which is by far the hottest token query after lexing, a single // contiguous load rather than a chunked `ValueStore` lookup. It also allows // scanning kinds in bulk; see `kind_data`. // // This is built from `token_infos_` in one pass once lexing is complete, by // `BuildTokenArrays`, rather than maintained while lexing: the lexer's token // emission is hot enough that even a few extra instructions there cost more // than the pass. llvm::SmallVector token_kinds_; // Whether each token in `token_infos_` has leading whitespace, as a flat // array indexed by the token index. This duplicates // `TokenInfo::has_leading_space` for the same reason as `token_kinds_` and is // built at the same time. // // This intentionally uses a byte-per-token `SmallVector` rather than // `llvm::BitVector` to facilitate vectorized population in // `BuildTokenArrays`. llvm::SmallVector token_has_leading_space_; ValueStore line_infos_; // Comments in the file. ValueStore comments_; // Whether SemIR dumping is explicitly enabled for this file. This is marked // by `//@include-in-dumps`, and overrides other file-inclusion selection // choices. It can be combined with ranges. bool has_include_in_dumps_ = false; // A range of tokens marked by `//@dump-sem-ir-[begin|end]`. // // The particular syntax was chosen because it can be lexed efficiently. It // only occurs in invalid comment strings, so shouldn't slow down lexing of // correct code. It's also comment-like because its presence won't affect // parse/check. llvm::SmallVector dump_sem_ir_ranges_; // An upper bound on the number of parse tree nodes that we expect to be // created for the tokens in this buffer. int expected_max_parse_tree_size_ = 0; bool has_errors_ = false; // The number of recovery tokens created after lexing finished. These tokens // are included in `token_infos_`, but are excluded from the token sequence // produced by `tokens()`. int32_t post_lexing_recovery_tokens_ = 0; // A vector of flags for recovery tokens. If empty, there are none. When doing // token recovery, this will be extended to be indexable by token indices and // contain true for the tokens that were synthesized for recovery. llvm::BitVector recovery_tokens_; }; inline auto TokenizedBuffer::GetKind(TokenIndex token) const -> TokenKind { CARBON_DCHECK(token.index >= 0 && token.index < size(), "{0}", token); CARBON_DCHECK(static_cast(token.index) < token_kinds_.size(), "Token arrays haven't been built yet"); return token_kinds_[token.index]; } inline auto TokenizedBuffer::HasLeadingWhitespace(TokenIndex token) const -> bool { CARBON_DCHECK(token.index >= 0 && token.index < size(), "{0}", token); CARBON_DCHECK( static_cast(token.index) < token_has_leading_space_.size(), "Token arrays haven't been built yet"); return token_has_leading_space_[token.index]; } inline auto TokenizedBuffer::HasTrailingWhitespace(TokenIndex token) const -> bool { CARBON_DCHECK(token.index >= 0 && token.index < size(), "{0}", token); // Trailing whitespace is the leading whitespace of the next lexed token, if // there is one. int32_t next = token.index + 1; return next < num_lexed_tokens() && HasLeadingWhitespace(TokenIndex(next)); } inline auto TokenizedBuffer::AddToken(TokenInfo info) -> TokenIndex { expected_max_parse_tree_size_ += info.kind().expected_max_parse_tree_size(); return token_infos_.Add(info); } } // namespace Carbon::Lex namespace Carbon { extern template class ValueStore; extern template class ValueStore; extern template class ValueStore; } // namespace Carbon #endif // CARBON_TOOLCHAIN_LEX_TOKENIZED_BUFFER_H_