1 //===- DependencyDirectivesSourceMinimizer.cpp - -------------------------===//
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
7 //===----------------------------------------------------------------------===//
10 /// This is the implementation for minimizing header and source files to the
11 /// minimum necessary preprocessor directives for evaluating includes. It
12 /// reduces the source down to #define, #include, #import, @import, and any
13 /// conditional preprocessor logic that contains one of those.
15 //===----------------------------------------------------------------------===//
17 #include "clang/Lex/DependencyDirectivesSourceMinimizer.h"
18 #include "clang/Basic/CharInfo.h"
19 #include "clang/Basic/Diagnostic.h"
20 #include "clang/Lex/LexDiagnostic.h"
21 #include "llvm/ADT/StringMap.h"
22 #include "llvm/ADT/StringSwitch.h"
23 #include "llvm/Support/MemoryBuffer.h"
26 using namespace clang;
27 using namespace clang::minimize_source_to_dependency_directives;
33 SmallVectorImpl<char> &Out;
34 /// The known tokens encountered during the minimization.
35 SmallVectorImpl<Token> &Tokens;
37 Minimizer(SmallVectorImpl<char> &Out, SmallVectorImpl<Token> &Tokens,
38 StringRef Input, DiagnosticsEngine *Diags,
39 SourceLocation InputSourceLoc)
40 : Out(Out), Tokens(Tokens), Input(Input), Diags(Diags),
41 InputSourceLoc(InputSourceLoc) {}
43 /// Lex the provided source and emit the minimized output.
45 /// \returns True on error.
54 /// Lex an identifier.
56 /// \pre First points at a valid identifier head.
57 LLVM_NODISCARD IdInfo lexIdentifier(const char *First, const char *const End);
58 LLVM_NODISCARD bool isNextIdentifier(StringRef Id, const char *&First,
59 const char *const End);
60 LLVM_NODISCARD bool minimizeImpl(const char *First, const char *const End);
61 LLVM_NODISCARD bool lexPPLine(const char *&First, const char *const End);
62 LLVM_NODISCARD bool lexAt(const char *&First, const char *const End);
63 LLVM_NODISCARD bool lexModule(const char *&First, const char *const End);
64 LLVM_NODISCARD bool lexDefine(const char *&First, const char *const End);
65 LLVM_NODISCARD bool lexPragma(const char *&First, const char *const End);
66 LLVM_NODISCARD bool lexEndif(const char *&First, const char *const End);
67 LLVM_NODISCARD bool lexDefault(TokenKind Kind, StringRef Directive,
68 const char *&First, const char *const End);
69 Token &makeToken(TokenKind K) {
70 Tokens.emplace_back(K, Out.size());
74 Out.resize(Tokens.back().Offset);
77 TokenKind top() const { return Tokens.empty() ? pp_none : Tokens.back().K; }
79 Minimizer &put(char Byte) {
83 Minimizer &append(StringRef S) { return append(S.begin(), S.end()); }
84 Minimizer &append(const char *First, const char *Last) {
85 Out.append(First, Last);
89 void printToNewline(const char *&First, const char *const End);
90 void printAdjacentModuleNameParts(const char *&First, const char *const End);
91 LLVM_NODISCARD bool printAtImportBody(const char *&First,
92 const char *const End);
93 void printDirectiveBody(const char *&First, const char *const End);
94 void printAdjacentMacroArgs(const char *&First, const char *const End);
95 LLVM_NODISCARD bool printMacroArgs(const char *&First, const char *const End);
97 /// Reports a diagnostic if the diagnostic engine is provided. Always returns
99 bool reportError(const char *CurPtr, unsigned Err);
101 StringMap<char> SplitIds;
103 DiagnosticsEngine *Diags;
104 SourceLocation InputSourceLoc;
107 } // end anonymous namespace
109 bool Minimizer::reportError(const char *CurPtr, unsigned Err) {
112 assert(CurPtr >= Input.data() && "invalid buffer ptr");
113 Diags->Report(InputSourceLoc.getLocWithOffset(CurPtr - Input.data()), Err);
117 static void skipOverSpaces(const char *&First, const char *const End) {
118 while (First != End && isHorizontalWhitespace(*First))
122 LLVM_NODISCARD static bool isRawStringLiteral(const char *First,
123 const char *Current) {
124 assert(First <= Current);
126 // Check if we can even back up.
127 if (*Current != '"' || First == Current)
134 if (First == Current || !isIdentifierBody(*--Current))
137 // Check for a prefix of "u", "U", or "L".
138 if (*Current == 'u' || *Current == 'U' || *Current == 'L')
139 return First == Current || !isIdentifierBody(*--Current);
141 // Check for a prefix of "u8".
142 if (*Current != '8' || First == Current || *Current-- != 'u')
144 return First == Current || !isIdentifierBody(*--Current);
147 static void skipRawString(const char *&First, const char *const End) {
148 assert(First[0] == '"');
149 assert(First[-1] == 'R');
151 const char *Last = ++First;
152 while (Last != End && *Last != '(')
155 First = Last; // Hit the end... just give up.
159 StringRef Terminator(First, Last - First);
161 // Move First to just past the next ")".
163 while (First != End && *First != ')')
169 // Look ahead for the terminator sequence.
171 while (Last != End && size_t(Last - First) < Terminator.size() &&
172 Terminator[Last - First] == *Last)
175 // Check if we hit it (or the end of the file).
180 if (size_t(Last - First) < Terminator.size())
189 // Returns the length of EOL, either 0 (no end-of-line), 1 (\n) or 2 (\r\n)
190 static unsigned isEOL(const char *First, const char *const End) {
193 if (End - First > 1 && isVerticalWhitespace(First[0]) &&
194 isVerticalWhitespace(First[1]) && First[0] != First[1])
196 return !!isVerticalWhitespace(First[0]);
199 static void skipString(const char *&First, const char *const End) {
200 assert(*First == '\'' || *First == '"' || *First == '<');
201 const char Terminator = *First == '<' ? '>' : *First;
202 for (++First; First != End && *First != Terminator; ++First) {
203 // String and character literals don't extend past the end of the line.
204 if (isVerticalWhitespace(*First))
208 // Skip past backslash to the next character. This ensures that the
209 // character right after it is skipped as well, which matters if it's
213 if (!isWhitespace(*First))
215 // Whitespace after the backslash might indicate a line continuation.
216 const char *FirstAfterBackslashPastSpace = First;
217 skipOverSpaces(FirstAfterBackslashPastSpace, End);
218 if (unsigned NLSize = isEOL(FirstAfterBackslashPastSpace, End)) {
219 // Advance the character pointer to the next line for the next
221 First = FirstAfterBackslashPastSpace + NLSize - 1;
225 ++First; // Finish off the string.
228 // Returns the length of the skipped newline
229 static unsigned skipNewline(const char *&First, const char *End) {
232 assert(isVerticalWhitespace(*First));
233 unsigned Len = isEOL(First, End);
234 assert(Len && "expected newline");
239 static bool wasLineContinuation(const char *First, unsigned EOLLen) {
240 return *(First - (int)EOLLen - 1) == '\\';
243 static void skipToNewlineRaw(const char *&First, const char *const End) {
248 unsigned Len = isEOL(First, End);
255 Len = isEOL(First, End);
258 if (First[-1] != '\\')
262 // Keep skipping lines...
266 static const char *findLastNonSpace(const char *First, const char *Last) {
267 assert(First <= Last);
268 while (First != Last && isHorizontalWhitespace(Last[-1]))
273 static const char *findFirstTrailingSpace(const char *First,
275 const char *LastNonSpace = findLastNonSpace(First, Last);
276 if (Last == LastNonSpace)
278 assert(isHorizontalWhitespace(LastNonSpace[0]));
279 return LastNonSpace + 1;
282 static void skipLineComment(const char *&First, const char *const End) {
283 assert(First[0] == '/' && First[1] == '/');
285 skipToNewlineRaw(First, End);
288 static void skipBlockComment(const char *&First, const char *const End) {
289 assert(First[0] == '/' && First[1] == '*');
290 if (End - First < 4) {
294 for (First += 3; First != End; ++First)
295 if (First[-1] == '*' && First[0] == '/') {
301 /// \returns True if the current single quotation mark character is a C++ 14
303 static bool isQuoteCppDigitSeparator(const char *const Start,
304 const char *const Cur,
305 const char *const End) {
306 assert(*Cur == '\'' && "expected quotation character");
307 // skipLine called in places where we don't expect a valid number
308 // body before `start` on the same line, so always return false at the start.
311 // The previous character must be a valid PP number character.
312 // Make sure that the L, u, U, u8 prefixes don't get marked as a
314 char Prev = *(Cur - 1);
315 if (Prev == 'L' || Prev == 'U' || Prev == 'u')
317 if (Prev == '8' && (Cur - 1 != Start) && *(Cur - 2) == 'u')
319 if (!isPreprocessingNumberBody(Prev))
321 // The next character should be a valid identifier body character.
322 return (Cur + 1) < End && isIdentifierBody(*(Cur + 1));
325 static void skipLine(const char *&First, const char *const End) {
327 assert(First <= End);
331 if (isVerticalWhitespace(*First)) {
332 skipNewline(First, End);
335 const char *Start = First;
336 while (First != End && !isVerticalWhitespace(*First)) {
337 // Iterate over strings correctly to avoid comments and newlines.
339 (*First == '\'' && !isQuoteCppDigitSeparator(Start, First, End))) {
340 if (isRawStringLiteral(Start, First))
341 skipRawString(First, End);
343 skipString(First, End);
347 // Iterate over comments correctly.
348 if (*First != '/' || End - First < 2) {
353 if (First[1] == '/') {
355 skipLineComment(First, End);
359 if (First[1] != '*') {
365 skipBlockComment(First, End);
370 // Skip over the newline.
371 unsigned Len = skipNewline(First, End);
372 if (!wasLineContinuation(First, Len)) // Continue past line-continuations.
377 static void skipDirective(StringRef Name, const char *&First,
378 const char *const End) {
379 if (llvm::StringSwitch<bool>(Name)
380 .Case("warning", true)
383 // Do not process quotes or comments.
384 skipToNewlineRaw(First, End);
386 skipLine(First, End);
389 void Minimizer::printToNewline(const char *&First, const char *const End) {
390 while (First != End && !isVerticalWhitespace(*First)) {
391 const char *Last = First;
393 // Iterate over strings correctly to avoid comments and newlines.
394 if (*Last == '"' || *Last == '\'' ||
395 (*Last == '<' && top() == pp_include)) {
396 if (LLVM_UNLIKELY(isRawStringLiteral(First, Last)))
397 skipRawString(Last, End);
399 skipString(Last, End);
402 if (*Last != '/' || End - Last < 2) {
404 continue; // Gather the rest up to print verbatim.
407 if (Last[1] != '/' && Last[1] != '*') {
412 // Deal with "//..." and "/*...*/".
413 append(First, findFirstTrailingSpace(First, Last));
416 if (Last[1] == '/') {
417 skipLineComment(First, End);
422 skipBlockComment(First, End);
423 skipOverSpaces(First, End);
425 } while (Last != End && !isVerticalWhitespace(*Last));
427 // Print out the string.
428 const char *LastBeforeTrailingSpace = findLastNonSpace(First, Last);
429 if (Last == End || LastBeforeTrailingSpace == First ||
430 LastBeforeTrailingSpace[-1] != '\\') {
431 append(First, LastBeforeTrailingSpace);
433 skipNewline(First, End);
437 // Print up to the backslash, backing up over spaces. Preserve at least one
438 // space, as the space matters when tokens are separated by a line
440 append(First, findFirstTrailingSpace(
441 First, LastBeforeTrailingSpace - 1));
444 skipNewline(First, End);
445 skipOverSpaces(First, End);
449 static void skipWhitespace(const char *&First, const char *const End) {
451 assert(First <= End);
452 skipOverSpaces(First, End);
457 if (First[0] == '\\' && isVerticalWhitespace(First[1])) {
458 skipNewline(++First, End);
462 // Check for a non-comment character.
467 if (First[1] == '/') {
468 skipLineComment(First, End);
472 // Cannot be a comment.
477 skipBlockComment(First, End);
481 void Minimizer::printAdjacentModuleNameParts(const char *&First,
482 const char *const End) {
483 // Skip over parts of the body.
484 const char *Last = First;
487 while (Last != End && (isIdentifierBody(*Last) || *Last == '.'));
492 bool Minimizer::printAtImportBody(const char *&First, const char *const End) {
494 skipWhitespace(First, End);
498 if (isVerticalWhitespace(*First)) {
499 skipNewline(First, End);
503 // Found a semicolon.
505 put(*First++).put('\n');
509 // Don't handle macro expansions inside @import for now.
510 if (!isIdentifierBody(*First) && *First != '.')
513 printAdjacentModuleNameParts(First, End);
517 void Minimizer::printDirectiveBody(const char *&First, const char *const End) {
518 skipWhitespace(First, End); // Skip initial whitespace.
519 printToNewline(First, End);
520 while (Out.back() == ' ')
525 LLVM_NODISCARD static const char *lexRawIdentifier(const char *First,
526 const char *const End) {
527 assert(isIdentifierBody(*First) && "invalid identifer");
528 const char *Last = First + 1;
529 while (Last != End && isIdentifierBody(*Last))
534 LLVM_NODISCARD static const char *
535 getIdentifierContinuation(const char *First, const char *const End) {
536 if (End - First < 3 || First[0] != '\\' || !isVerticalWhitespace(First[1]))
540 skipNewline(First, End);
543 return isIdentifierBody(First[0]) ? First : nullptr;
546 Minimizer::IdInfo Minimizer::lexIdentifier(const char *First,
547 const char *const End) {
548 const char *Last = lexRawIdentifier(First, End);
549 const char *Next = getIdentifierContinuation(Last, End);
550 if (LLVM_LIKELY(!Next))
551 return IdInfo{Last, StringRef(First, Last - First)};
553 // Slow path, where identifiers are split over lines.
554 SmallVector<char, 64> Id(First, Last);
556 Last = lexRawIdentifier(Next, End);
557 Id.append(Next, Last);
558 Next = getIdentifierContinuation(Last, End);
562 SplitIds.try_emplace(StringRef(Id.begin(), Id.size()), 0).first->first()};
565 void Minimizer::printAdjacentMacroArgs(const char *&First,
566 const char *const End) {
567 // Skip over parts of the body.
568 const char *Last = First;
571 while (Last != End &&
572 (isIdentifierBody(*Last) || *Last == '.' || *Last == ','));
577 bool Minimizer::printMacroArgs(const char *&First, const char *const End) {
578 assert(*First == '(');
581 skipWhitespace(First, End);
590 // This is intentionally fairly liberal.
591 if (!(isIdentifierBody(*First) || *First == '.' || *First == ','))
594 printAdjacentMacroArgs(First, End);
598 /// Looks for an identifier starting from Last.
600 /// Updates "First" to just past the next identifier, if any. Returns true iff
601 /// the identifier matches "Id".
602 bool Minimizer::isNextIdentifier(StringRef Id, const char *&First,
603 const char *const End) {
604 skipWhitespace(First, End);
605 if (First == End || !isIdentifierHead(*First))
608 IdInfo FoundId = lexIdentifier(First, End);
609 First = FoundId.Last;
610 return FoundId.Name == Id;
613 bool Minimizer::lexAt(const char *&First, const char *const End) {
615 const char *ImportLoc = First++;
616 if (!isNextIdentifier("import", First, End)) {
617 skipLine(First, End);
620 makeToken(decl_at_import);
622 if (printAtImportBody(First, End))
624 ImportLoc, diag::err_dep_source_minimizer_missing_sema_after_at_import);
625 skipWhitespace(First, End);
628 if (!isVerticalWhitespace(*First))
630 ImportLoc, diag::err_dep_source_minimizer_unexpected_tokens_at_import);
631 skipNewline(First, End);
635 bool Minimizer::lexModule(const char *&First, const char *const End) {
636 IdInfo Id = lexIdentifier(First, End);
639 if (Id.Name == "export") {
641 skipWhitespace(First, End);
642 if (!isIdentifierBody(*First)) {
643 skipLine(First, End);
646 Id = lexIdentifier(First, End);
650 if (Id.Name != "module" && Id.Name != "import") {
651 skipLine(First, End);
655 skipWhitespace(First, End);
657 // Ignore this as a module directive if the next character can't be part of
666 if (!isIdentifierBody(*First)) {
667 skipLine(First, End);
673 makeToken(cxx_export_decl);
677 if (Id.Name == "module")
678 makeToken(cxx_module_decl);
680 makeToken(cxx_import_decl);
683 printToNewline(First, End);
688 bool Minimizer::lexDefine(const char *&First, const char *const End) {
689 makeToken(pp_define);
691 skipWhitespace(First, End);
693 if (!isIdentifierHead(*First))
694 return reportError(First, diag::err_pp_macro_not_identifier);
696 IdInfo Id = lexIdentifier(First, End);
697 const char *Last = Id.Last;
702 size_t Size = Out.size();
703 if (printMacroArgs(Last, End)) {
704 // Be robust to bad macro arguments, since they can show up in disabled
707 append("(/* invalid */\n");
712 skipWhitespace(Last, End);
715 if (!isVerticalWhitespace(*Last))
717 printDirectiveBody(Last, End);
722 bool Minimizer::lexPragma(const char *&First, const char *const End) {
724 skipWhitespace(First, End);
725 if (First == End || !isIdentifierHead(*First))
728 IdInfo FoundId = lexIdentifier(First, End);
729 First = FoundId.Last;
730 if (FoundId.Name == "once") {
732 skipLine(First, End);
733 makeToken(pp_pragma_once);
734 append("#pragma once\n");
738 if (FoundId.Name != "clang") {
739 skipLine(First, End);
744 if (!isNextIdentifier("module", First, End)) {
745 skipLine(First, End);
749 // #pragma clang module.
750 if (!isNextIdentifier("import", First, End)) {
751 skipLine(First, End);
755 // #pragma clang module import.
756 makeToken(pp_pragma_import);
757 append("#pragma clang module import ");
758 printDirectiveBody(First, End);
762 bool Minimizer::lexEndif(const char *&First, const char *const End) {
763 // Strip out "#else" if it's empty.
764 if (top() == pp_else)
767 // If "#ifdef" is empty, strip it and skip the "#endif".
769 // FIXME: Once/if Clang starts disallowing __has_include in macro expansions,
770 // we can skip empty `#if` and `#elif` blocks as well after scanning for a
771 // literal __has_include in the condition. Even without that rule we could
772 // drop the tokens if we scan for identifiers in the condition and find none.
773 if (top() == pp_ifdef || top() == pp_ifndef) {
775 skipLine(First, End);
779 return lexDefault(pp_endif, "endif", First, End);
782 bool Minimizer::lexDefault(TokenKind Kind, StringRef Directive,
783 const char *&First, const char *const End) {
785 put('#').append(Directive).put(' ');
786 printDirectiveBody(First, End);
790 static bool isStartOfRelevantLine(char First) {
802 bool Minimizer::lexPPLine(const char *&First, const char *const End) {
803 assert(First != End);
805 skipWhitespace(First, End);
806 assert(First <= End);
810 if (!isStartOfRelevantLine(*First)) {
811 skipLine(First, End);
812 assert(First <= End);
818 return lexAt(First, End);
820 if (*First == 'i' || *First == 'e' || *First == 'm')
821 return lexModule(First, End);
823 // Handle preprocessing directives.
824 ++First; // Skip over '#'.
825 skipWhitespace(First, End);
828 return reportError(First, diag::err_pp_expected_eol);
830 if (!isIdentifierHead(*First)) {
831 skipLine(First, End);
835 // Figure out the token.
836 IdInfo Id = lexIdentifier(First, End);
838 auto Kind = llvm::StringSwitch<TokenKind>(Id.Name)
839 .Case("include", pp_include)
840 .Case("__include_macros", pp___include_macros)
841 .Case("define", pp_define)
842 .Case("undef", pp_undef)
843 .Case("import", pp_import)
844 .Case("include_next", pp_include_next)
846 .Case("ifdef", pp_ifdef)
847 .Case("ifndef", pp_ifndef)
848 .Case("elif", pp_elif)
849 .Case("else", pp_else)
850 .Case("endif", pp_endif)
851 .Case("pragma", pp_pragma_import)
853 if (Kind == pp_none) {
854 skipDirective(Id.Name, First, End);
858 if (Kind == pp_endif)
859 return lexEndif(First, End);
861 if (Kind == pp_define)
862 return lexDefine(First, End);
864 if (Kind == pp_pragma_import)
865 return lexPragma(First, End);
868 return lexDefault(Kind, Id.Name, First, End);
871 static void skipUTF8ByteOrderMark(const char *&First, const char *const End) {
872 if ((End - First) >= 3 && First[0] == '\xef' && First[1] == '\xbb' &&
877 bool Minimizer::minimizeImpl(const char *First, const char *const End) {
878 skipUTF8ByteOrderMark(First, End);
880 if (lexPPLine(First, End))
885 bool Minimizer::minimize() {
886 bool Error = minimizeImpl(Input.begin(), Input.end());
889 // Add a trailing newline and an EOF on success.
890 if (!Out.empty() && Out.back() != '\n')
895 // Null-terminate the output. This way the memory buffer that's passed to
896 // Clang will not have to worry about the terminating '\0'.
902 bool clang::minimize_source_to_dependency_directives::computeSkippedRanges(
903 ArrayRef<Token> Input, llvm::SmallVectorImpl<SkippedRange> &Range) {
906 If, // if/ifdef/ifndef
912 llvm::SmallVector<Directive, 32> Offsets;
913 for (const Token &T : Input) {
918 Offsets.push_back({T.Offset, Directive::If});
925 int PreviousOffset = Offsets.back().Offset;
926 Range.push_back({PreviousOffset, T.Offset - PreviousOffset});
927 Offsets.push_back({T.Offset, Directive::Else});
934 int PreviousOffset = Offsets.back().Offset;
935 Range.push_back({PreviousOffset, T.Offset - PreviousOffset});
937 Directive::DirectiveKind Kind = Offsets.pop_back_val().Kind;
938 if (Kind == Directive::If)
940 } while (!Offsets.empty());
950 bool clang::minimizeSourceToDependencyDirectives(
951 StringRef Input, SmallVectorImpl<char> &Output,
952 SmallVectorImpl<Token> &Tokens, DiagnosticsEngine *Diags,
953 SourceLocation InputSourceLoc) {
956 return Minimizer(Output, Tokens, Input, Diags, InputSourceLoc).minimize();