1 //===- FileCheck.cpp - Check that File's Contents match what is expected --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // FileCheck does a line-by line check of a file that validates whether it
11 // contains the expected content. This is useful for regression tests etc.
13 // This program exits with an error status of 2 on error, exit status of 0 if
14 // the file matched the expected contents, and exit status of 1 if it did not
15 // contain the expected contents.
17 //===----------------------------------------------------------------------===//
19 #include "llvm/ADT/SmallString.h"
20 #include "llvm/ADT/StringExtras.h"
21 #include "llvm/ADT/StringMap.h"
22 #include "llvm/ADT/StringSet.h"
23 #include "llvm/Support/CommandLine.h"
24 #include "llvm/Support/MemoryBuffer.h"
25 #include "llvm/Support/PrettyStackTrace.h"
26 #include "llvm/Support/Regex.h"
27 #include "llvm/Support/Signals.h"
28 #include "llvm/Support/SourceMgr.h"
29 #include "llvm/Support/raw_ostream.h"
34 #include <system_error>
38 static cl::opt<std::string>
39 CheckFilename(cl::Positional, cl::desc("<check-file>"), cl::Required);
41 static cl::opt<std::string>
42 InputFilename("input-file", cl::desc("File to check (defaults to stdin)"),
43 cl::init("-"), cl::value_desc("filename"));
45 static cl::list<std::string>
46 CheckPrefixes("check-prefix",
47 cl::desc("Prefix to use from check file (defaults to 'CHECK')"));
50 NoCanonicalizeWhiteSpace("strict-whitespace",
51 cl::desc("Do not treat all horizontal whitespace as equivalent"));
53 static cl::list<std::string> ImplicitCheckNot(
55 cl::desc("Add an implicit negative check with this pattern to every\n"
56 "positive check. This can be used to ensure that no instances of\n"
57 "this pattern occur which are not matched by a positive pattern"),
58 cl::value_desc("pattern"));
60 static cl::opt<bool> AllowEmptyInput(
61 "allow-empty", cl::init(false),
62 cl::desc("Allow the input file to be empty. This is useful when making\n"
63 "checks that some error message does not occur, for example."));
65 typedef cl::list<std::string>::const_iterator prefix_iterator;
67 //===----------------------------------------------------------------------===//
68 // Pattern Handling Code.
69 //===----------------------------------------------------------------------===//
80 /// MatchEOF - When set, this pattern only matches the end of file. This is
81 /// used for trailing CHECK-NOTs.
89 Check::CheckType CheckTy;
91 /// FixedStr - If non-empty, this pattern is a fixed string match with the
92 /// specified fixed string.
95 /// RegEx - If non-empty, this is a regex pattern.
98 /// \brief Contains the number of line this pattern is in.
101 /// VariableUses - Entries in this vector map to uses of a variable in the
102 /// pattern, e.g. "foo[[bar]]baz". In this case, the RegExStr will contain
103 /// "foobaz" and we'll get an entry in this vector that tells us to insert the
104 /// value of bar at offset 3.
105 std::vector<std::pair<StringRef, unsigned> > VariableUses;
107 /// VariableDefs - Maps definitions of variables to their parenthesized
109 /// E.g. for the pattern "foo[[bar:.*]]baz", VariableDefs will map "bar" to 1.
110 std::map<StringRef, unsigned> VariableDefs;
114 Pattern(Check::CheckType Ty)
117 /// getLoc - Return the location in source code.
118 SMLoc getLoc() const { return PatternLoc; }
120 /// ParsePattern - Parse the given string into the Pattern. Prefix provides
121 /// which prefix is being matched, SM provides the SourceMgr used for error
122 /// reports, and LineNumber is the line number in the input file from which
123 /// the pattern string was read. Returns true in case of an error, false
125 bool ParsePattern(StringRef PatternStr,
128 unsigned LineNumber);
130 /// Match - Match the pattern string against the input buffer Buffer. This
131 /// returns the position that is matched or npos if there is no match. If
132 /// there is a match, the size of the matched string is returned in MatchLen.
134 /// The VariableTable StringMap provides the current values of filecheck
135 /// variables and is updated if this match defines new values.
136 size_t Match(StringRef Buffer, size_t &MatchLen,
137 StringMap<StringRef> &VariableTable) const;
139 /// PrintFailureInfo - Print additional information about a failure to match
140 /// involving this pattern.
141 void PrintFailureInfo(const SourceMgr &SM, StringRef Buffer,
142 const StringMap<StringRef> &VariableTable) const;
144 bool hasVariable() const { return !(VariableUses.empty() &&
145 VariableDefs.empty()); }
147 Check::CheckType getCheckTy() const { return CheckTy; }
150 bool AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM);
151 void AddBackrefToRegEx(unsigned BackrefNum);
153 /// ComputeMatchDistance - Compute an arbitrary estimate for the quality of
154 /// matching this pattern at the start of \arg Buffer; a distance of zero
155 /// should correspond to a perfect match.
156 unsigned ComputeMatchDistance(StringRef Buffer,
157 const StringMap<StringRef> &VariableTable) const;
159 /// \brief Evaluates expression and stores the result to \p Value.
160 /// \return true on success. false when the expression has invalid syntax.
161 bool EvaluateExpression(StringRef Expr, std::string &Value) const;
163 /// \brief Finds the closing sequence of a regex variable usage or
164 /// definition. Str has to point in the beginning of the definition
165 /// (right after the opening sequence).
166 /// \return offset of the closing sequence within Str, or npos if it was not
168 size_t FindRegexVarEnd(StringRef Str, SourceMgr &SM);
172 bool Pattern::ParsePattern(StringRef PatternStr,
175 unsigned LineNumber) {
176 this->LineNumber = LineNumber;
177 PatternLoc = SMLoc::getFromPointer(PatternStr.data());
179 // Ignore trailing whitespace.
180 while (!PatternStr.empty() &&
181 (PatternStr.back() == ' ' || PatternStr.back() == '\t'))
182 PatternStr = PatternStr.substr(0, PatternStr.size()-1);
184 // Check that there is something on the line.
185 if (PatternStr.empty()) {
186 SM.PrintMessage(PatternLoc, SourceMgr::DK_Error,
187 "found empty check string with prefix '" +
192 // Check to see if this is a fixed string, or if it has regex pieces.
193 if (PatternStr.size() < 2 ||
194 (PatternStr.find("{{") == StringRef::npos &&
195 PatternStr.find("[[") == StringRef::npos)) {
196 FixedStr = PatternStr;
200 // Paren value #0 is for the fully matched string. Any new parenthesized
201 // values add from there.
202 unsigned CurParen = 1;
204 // Otherwise, there is at least one regex piece. Build up the regex pattern
205 // by escaping scary characters in fixed strings, building up one big regex.
206 while (!PatternStr.empty()) {
208 if (PatternStr.startswith("{{")) {
209 // This is the start of a regex match. Scan for the }}.
210 size_t End = PatternStr.find("}}");
211 if (End == StringRef::npos) {
212 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
214 "found start of regex string with no end '}}'");
218 // Enclose {{}} patterns in parens just like [[]] even though we're not
219 // capturing the result for any purpose. This is required in case the
220 // expression contains an alternation like: CHECK: abc{{x|z}}def. We
221 // want this to turn into: "abc(x|z)def" not "abcx|zdef".
225 if (AddRegExToRegEx(PatternStr.substr(2, End-2), CurParen, SM))
229 PatternStr = PatternStr.substr(End+2);
233 // Named RegEx matches. These are of two forms: [[foo:.*]] which matches .*
234 // (or some other regex) and assigns it to the FileCheck variable 'foo'. The
235 // second form is [[foo]] which is a reference to foo. The variable name
236 // itself must be of the form "[a-zA-Z_][0-9a-zA-Z_]*", otherwise we reject
237 // it. This is to catch some common errors.
238 if (PatternStr.startswith("[[")) {
239 // Find the closing bracket pair ending the match. End is going to be an
240 // offset relative to the beginning of the match string.
241 size_t End = FindRegexVarEnd(PatternStr.substr(2), SM);
243 if (End == StringRef::npos) {
244 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
246 "invalid named regex reference, no ]] found");
250 StringRef MatchStr = PatternStr.substr(2, End);
251 PatternStr = PatternStr.substr(End+4);
253 // Get the regex name (e.g. "foo").
254 size_t NameEnd = MatchStr.find(':');
255 StringRef Name = MatchStr.substr(0, NameEnd);
258 SM.PrintMessage(SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,
259 "invalid name in named regex: empty name");
263 // Verify that the name/expression is well formed. FileCheck currently
264 // supports @LINE, @LINE+number, @LINE-number expressions. The check here
265 // is relaxed, more strict check is performed in \c EvaluateExpression.
266 bool IsExpression = false;
267 for (unsigned i = 0, e = Name.size(); i != e; ++i) {
268 if (i == 0 && Name[i] == '@') {
269 if (NameEnd != StringRef::npos) {
270 SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
272 "invalid name in named regex definition");
278 if (Name[i] != '_' && !isalnum(Name[i]) &&
279 (!IsExpression || (Name[i] != '+' && Name[i] != '-'))) {
280 SM.PrintMessage(SMLoc::getFromPointer(Name.data()+i),
281 SourceMgr::DK_Error, "invalid name in named regex");
286 // Name can't start with a digit.
287 if (isdigit(static_cast<unsigned char>(Name[0]))) {
288 SM.PrintMessage(SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,
289 "invalid name in named regex");
294 if (NameEnd == StringRef::npos) {
295 // Handle variables that were defined earlier on the same line by
296 // emitting a backreference.
297 if (VariableDefs.find(Name) != VariableDefs.end()) {
298 unsigned VarParenNum = VariableDefs[Name];
299 if (VarParenNum < 1 || VarParenNum > 9) {
300 SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
302 "Can't back-reference more than 9 variables");
305 AddBackrefToRegEx(VarParenNum);
307 VariableUses.push_back(std::make_pair(Name, RegExStr.size()));
312 // Handle [[foo:.*]].
313 VariableDefs[Name] = CurParen;
317 if (AddRegExToRegEx(MatchStr.substr(NameEnd+1), CurParen, SM))
323 // Handle fixed string matches.
324 // Find the end, which is the start of the next regex.
325 size_t FixedMatchEnd = PatternStr.find("{{");
326 FixedMatchEnd = std::min(FixedMatchEnd, PatternStr.find("[["));
327 RegExStr += Regex::escape(PatternStr.substr(0, FixedMatchEnd));
328 PatternStr = PatternStr.substr(FixedMatchEnd);
334 bool Pattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen,
338 if (!R.isValid(Error)) {
339 SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error,
340 "invalid regex: " + Error);
344 RegExStr += RS.str();
345 CurParen += R.getNumMatches();
349 void Pattern::AddBackrefToRegEx(unsigned BackrefNum) {
350 assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number");
351 std::string Backref = std::string("\\") +
352 std::string(1, '0' + BackrefNum);
356 bool Pattern::EvaluateExpression(StringRef Expr, std::string &Value) const {
357 // The only supported expression is @LINE([\+-]\d+)?
358 if (!Expr.startswith("@LINE"))
360 Expr = Expr.substr(StringRef("@LINE").size());
364 Expr = Expr.substr(1);
365 else if (Expr[0] != '-')
367 if (Expr.getAsInteger(10, Offset))
370 Value = llvm::itostr(LineNumber + Offset);
374 /// Match - Match the pattern string against the input buffer Buffer. This
375 /// returns the position that is matched or npos if there is no match. If
376 /// there is a match, the size of the matched string is returned in MatchLen.
377 size_t Pattern::Match(StringRef Buffer, size_t &MatchLen,
378 StringMap<StringRef> &VariableTable) const {
379 // If this is the EOF pattern, match it immediately.
380 if (CheckTy == Check::CheckEOF) {
382 return Buffer.size();
385 // If this is a fixed string pattern, just match it now.
386 if (!FixedStr.empty()) {
387 MatchLen = FixedStr.size();
388 return Buffer.find(FixedStr);
393 // If there are variable uses, we need to create a temporary string with the
395 StringRef RegExToMatch = RegExStr;
397 if (!VariableUses.empty()) {
400 unsigned InsertOffset = 0;
401 for (unsigned i = 0, e = VariableUses.size(); i != e; ++i) {
404 if (VariableUses[i].first[0] == '@') {
405 if (!EvaluateExpression(VariableUses[i].first, Value))
406 return StringRef::npos;
408 StringMap<StringRef>::iterator it =
409 VariableTable.find(VariableUses[i].first);
410 // If the variable is undefined, return an error.
411 if (it == VariableTable.end())
412 return StringRef::npos;
414 // Look up the value and escape it so that we can put it into the regex.
415 Value += Regex::escape(it->second);
418 // Plop it into the regex at the adjusted offset.
419 TmpStr.insert(TmpStr.begin()+VariableUses[i].second+InsertOffset,
420 Value.begin(), Value.end());
421 InsertOffset += Value.size();
424 // Match the newly constructed regex.
425 RegExToMatch = TmpStr;
429 SmallVector<StringRef, 4> MatchInfo;
430 if (!Regex(RegExToMatch, Regex::Newline).match(Buffer, &MatchInfo))
431 return StringRef::npos;
433 // Successful regex match.
434 assert(!MatchInfo.empty() && "Didn't get any match");
435 StringRef FullMatch = MatchInfo[0];
437 // If this defines any variables, remember their values.
438 for (std::map<StringRef, unsigned>::const_iterator I = VariableDefs.begin(),
439 E = VariableDefs.end();
441 assert(I->second < MatchInfo.size() && "Internal paren error");
442 VariableTable[I->first] = MatchInfo[I->second];
445 MatchLen = FullMatch.size();
446 return FullMatch.data()-Buffer.data();
449 unsigned Pattern::ComputeMatchDistance(StringRef Buffer,
450 const StringMap<StringRef> &VariableTable) const {
451 // Just compute the number of matching characters. For regular expressions, we
452 // just compare against the regex itself and hope for the best.
454 // FIXME: One easy improvement here is have the regex lib generate a single
455 // example regular expression which matches, and use that as the example
457 StringRef ExampleString(FixedStr);
458 if (ExampleString.empty())
459 ExampleString = RegExStr;
461 // Only compare up to the first line in the buffer, or the string size.
462 StringRef BufferPrefix = Buffer.substr(0, ExampleString.size());
463 BufferPrefix = BufferPrefix.split('\n').first;
464 return BufferPrefix.edit_distance(ExampleString);
467 void Pattern::PrintFailureInfo(const SourceMgr &SM, StringRef Buffer,
468 const StringMap<StringRef> &VariableTable) const{
469 // If this was a regular expression using variables, print the current
471 if (!VariableUses.empty()) {
472 for (unsigned i = 0, e = VariableUses.size(); i != e; ++i) {
473 SmallString<256> Msg;
474 raw_svector_ostream OS(Msg);
475 StringRef Var = VariableUses[i].first;
478 if (EvaluateExpression(Var, Value)) {
479 OS << "with expression \"";
480 OS.write_escaped(Var) << "\" equal to \"";
481 OS.write_escaped(Value) << "\"";
483 OS << "uses incorrect expression \"";
484 OS.write_escaped(Var) << "\"";
487 StringMap<StringRef>::const_iterator it = VariableTable.find(Var);
489 // Check for undefined variable references.
490 if (it == VariableTable.end()) {
491 OS << "uses undefined variable \"";
492 OS.write_escaped(Var) << "\"";
494 OS << "with variable \"";
495 OS.write_escaped(Var) << "\" equal to \"";
496 OS.write_escaped(it->second) << "\"";
500 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
505 // Attempt to find the closest/best fuzzy match. Usually an error happens
506 // because some string in the output didn't exactly match. In these cases, we
507 // would like to show the user a best guess at what "should have" matched, to
508 // save them having to actually check the input manually.
509 size_t NumLinesForward = 0;
510 size_t Best = StringRef::npos;
511 double BestQuality = 0;
513 // Use an arbitrary 4k limit on how far we will search.
514 for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) {
515 if (Buffer[i] == '\n')
518 // Patterns have leading whitespace stripped, so skip whitespace when
519 // looking for something which looks like a pattern.
520 if (Buffer[i] == ' ' || Buffer[i] == '\t')
523 // Compute the "quality" of this match as an arbitrary combination of the
524 // match distance and the number of lines skipped to get to this match.
525 unsigned Distance = ComputeMatchDistance(Buffer.substr(i), VariableTable);
526 double Quality = Distance + (NumLinesForward / 100.);
528 if (Quality < BestQuality || Best == StringRef::npos) {
530 BestQuality = Quality;
534 // Print the "possible intended match here" line if we found something
535 // reasonable and not equal to what we showed in the "scanning from here"
537 if (Best && Best != StringRef::npos && BestQuality < 50) {
538 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + Best),
539 SourceMgr::DK_Note, "possible intended match here");
541 // FIXME: If we wanted to be really friendly we would show why the match
542 // failed, as it can be hard to spot simple one character differences.
546 size_t Pattern::FindRegexVarEnd(StringRef Str, SourceMgr &SM) {
547 // Offset keeps track of the current offset within the input Str
549 // [...] Nesting depth
550 size_t BracketDepth = 0;
552 while (!Str.empty()) {
553 if (Str.startswith("]]") && BracketDepth == 0)
555 if (Str[0] == '\\') {
556 // Backslash escapes the next char within regexes, so skip them both.
567 if (BracketDepth == 0) {
568 SM.PrintMessage(SMLoc::getFromPointer(Str.data()),
570 "missing closing \"]\" for regex variable");
581 return StringRef::npos;
585 //===----------------------------------------------------------------------===//
587 //===----------------------------------------------------------------------===//
589 /// CheckString - This is a check that we found in the input file.
591 /// Pat - The pattern to match.
594 /// Prefix - Which prefix name this check matched.
597 /// Loc - The location in the match file that the check string was specified.
600 /// CheckTy - Specify what kind of check this is. e.g. CHECK-NEXT: directive,
601 /// as opposed to a CHECK: directive.
602 Check::CheckType CheckTy;
604 /// DagNotStrings - These are all of the strings that are disallowed from
605 /// occurring between this match string and the previous one (or start of
607 std::vector<Pattern> DagNotStrings;
610 CheckString(const Pattern &P,
614 : Pat(P), Prefix(S), Loc(L), CheckTy(Ty) {}
616 /// Check - Match check string and its "not strings" and/or "dag strings".
617 size_t Check(const SourceMgr &SM, StringRef Buffer, bool IsLabelScanMode,
618 size_t &MatchLen, StringMap<StringRef> &VariableTable) const;
620 /// CheckNext - Verify there is a single line in the given buffer.
621 bool CheckNext(const SourceMgr &SM, StringRef Buffer) const;
623 /// CheckNot - Verify there's no "not strings" in the given buffer.
624 bool CheckNot(const SourceMgr &SM, StringRef Buffer,
625 const std::vector<const Pattern *> &NotStrings,
626 StringMap<StringRef> &VariableTable) const;
628 /// CheckDag - Match "dag strings" and their mixed "not strings".
629 size_t CheckDag(const SourceMgr &SM, StringRef Buffer,
630 std::vector<const Pattern *> &NotStrings,
631 StringMap<StringRef> &VariableTable) const;
634 /// Canonicalize whitespaces in the input file. Line endings are replaced
635 /// with UNIX-style '\n'.
637 /// \param PreserveHorizontal Don't squash consecutive horizontal whitespace
638 /// characters to a single space.
639 static std::unique_ptr<MemoryBuffer>
640 CanonicalizeInputFile(std::unique_ptr<MemoryBuffer> MB,
641 bool PreserveHorizontal) {
642 SmallString<128> NewFile;
643 NewFile.reserve(MB->getBufferSize());
645 for (const char *Ptr = MB->getBufferStart(), *End = MB->getBufferEnd();
647 // Eliminate trailing dosish \r.
648 if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') {
652 // If current char is not a horizontal whitespace or if horizontal
653 // whitespace canonicalization is disabled, dump it to output as is.
654 if (PreserveHorizontal || (*Ptr != ' ' && *Ptr != '\t')) {
655 NewFile.push_back(*Ptr);
659 // Otherwise, add one space and advance over neighboring space.
660 NewFile.push_back(' ');
661 while (Ptr+1 != End &&
662 (Ptr[1] == ' ' || Ptr[1] == '\t'))
666 return std::unique_ptr<MemoryBuffer>(
667 MemoryBuffer::getMemBufferCopy(NewFile.str(), MB->getBufferIdentifier()));
670 static bool IsPartOfWord(char c) {
671 return (isalnum(c) || c == '-' || c == '_');
674 // Get the size of the prefix extension.
675 static size_t CheckTypeSize(Check::CheckType Ty) {
677 case Check::CheckNone:
680 case Check::CheckPlain:
681 return sizeof(":") - 1;
683 case Check::CheckNext:
684 return sizeof("-NEXT:") - 1;
686 case Check::CheckNot:
687 return sizeof("-NOT:") - 1;
689 case Check::CheckDAG:
690 return sizeof("-DAG:") - 1;
692 case Check::CheckLabel:
693 return sizeof("-LABEL:") - 1;
695 case Check::CheckEOF:
696 llvm_unreachable("Should not be using EOF size");
699 llvm_unreachable("Bad check type");
702 static Check::CheckType FindCheckType(StringRef Buffer, StringRef Prefix) {
703 char NextChar = Buffer[Prefix.size()];
705 // Verify that the : is present after the prefix.
707 return Check::CheckPlain;
710 return Check::CheckNone;
712 StringRef Rest = Buffer.drop_front(Prefix.size() + 1);
713 if (Rest.startswith("NEXT:"))
714 return Check::CheckNext;
716 if (Rest.startswith("NOT:"))
717 return Check::CheckNot;
719 if (Rest.startswith("DAG:"))
720 return Check::CheckDAG;
722 if (Rest.startswith("LABEL:"))
723 return Check::CheckLabel;
725 return Check::CheckNone;
728 // From the given position, find the next character after the word.
729 static size_t SkipWord(StringRef Str, size_t Loc) {
730 while (Loc < Str.size() && IsPartOfWord(Str[Loc]))
735 // Try to find the first match in buffer for any prefix. If a valid match is
736 // found, return that prefix and set its type and location. If there are almost
737 // matches (e.g. the actual prefix string is found, but is not an actual check
738 // string), but no valid match, return an empty string and set the position to
739 // resume searching from. If no partial matches are found, return an empty
740 // string and the location will be StringRef::npos. If one prefix is a substring
741 // of another, the maximal match should be found. e.g. if "A" and "AA" are
742 // prefixes then AA-CHECK: should match the second one.
743 static StringRef FindFirstCandidateMatch(StringRef &Buffer,
744 Check::CheckType &CheckTy,
746 StringRef FirstPrefix;
747 size_t FirstLoc = StringRef::npos;
748 size_t SearchLoc = StringRef::npos;
749 Check::CheckType FirstTy = Check::CheckNone;
751 CheckTy = Check::CheckNone;
752 CheckLoc = StringRef::npos;
754 for (prefix_iterator I = CheckPrefixes.begin(), E = CheckPrefixes.end();
756 StringRef Prefix(*I);
757 size_t PrefixLoc = Buffer.find(Prefix);
759 if (PrefixLoc == StringRef::npos)
762 // Track where we are searching for invalid prefixes that look almost right.
763 // We need to only advance to the first partial match on the next attempt
764 // since a partial match could be a substring of a later, valid prefix.
765 // Need to skip to the end of the word, otherwise we could end up
766 // matching a prefix in a substring later.
767 if (PrefixLoc < SearchLoc)
768 SearchLoc = SkipWord(Buffer, PrefixLoc);
770 // We only want to find the first match to avoid skipping some.
771 if (PrefixLoc > FirstLoc)
773 // If one matching check-prefix is a prefix of another, choose the
775 if (PrefixLoc == FirstLoc && Prefix.size() < FirstPrefix.size())
778 StringRef Rest = Buffer.drop_front(PrefixLoc);
779 // Make sure we have actually found the prefix, and not a word containing
780 // it. This should also prevent matching the wrong prefix when one is a
781 // substring of another.
782 if (PrefixLoc != 0 && IsPartOfWord(Buffer[PrefixLoc - 1]))
783 FirstTy = Check::CheckNone;
785 FirstTy = FindCheckType(Rest, Prefix);
787 FirstLoc = PrefixLoc;
788 FirstPrefix = Prefix;
791 // If the first prefix is invalid, we should continue the search after it.
792 if (FirstTy == Check::CheckNone) {
793 CheckLoc = SearchLoc;
802 static StringRef FindFirstMatchingPrefix(StringRef &Buffer,
803 unsigned &LineNumber,
804 Check::CheckType &CheckTy,
806 while (!Buffer.empty()) {
807 StringRef Prefix = FindFirstCandidateMatch(Buffer, CheckTy, CheckLoc);
808 // If we found a real match, we are done.
809 if (!Prefix.empty()) {
810 LineNumber += Buffer.substr(0, CheckLoc).count('\n');
814 // We didn't find any almost matches either, we are also done.
815 if (CheckLoc == StringRef::npos)
818 LineNumber += Buffer.substr(0, CheckLoc + 1).count('\n');
820 // Advance to the last possible match we found and try again.
821 Buffer = Buffer.drop_front(CheckLoc + 1);
827 /// ReadCheckFile - Read the check file, which specifies the sequence of
828 /// expected strings. The strings are added to the CheckStrings vector.
829 /// Returns true in case of an error, false otherwise.
830 static bool ReadCheckFile(SourceMgr &SM,
831 std::vector<CheckString> &CheckStrings) {
832 ErrorOr<std::unique_ptr<MemoryBuffer>> FileOrErr =
833 MemoryBuffer::getFileOrSTDIN(CheckFilename);
834 if (std::error_code EC = FileOrErr.getError()) {
835 errs() << "Could not open check file '" << CheckFilename
836 << "': " << EC.message() << '\n';
840 // If we want to canonicalize whitespace, strip excess whitespace from the
841 // buffer containing the CHECK lines. Remove DOS style line endings.
842 std::unique_ptr<MemoryBuffer> F =
843 CanonicalizeInputFile(std::move(*FileOrErr), NoCanonicalizeWhiteSpace);
845 // Find all instances of CheckPrefix followed by : in the file.
846 StringRef Buffer = F->getBuffer();
848 SM.AddNewSourceBuffer(std::move(F), SMLoc());
850 std::vector<Pattern> ImplicitNegativeChecks;
851 for (const auto &PatternString : ImplicitCheckNot) {
852 // Create a buffer with fake command line content in order to display the
853 // command line option responsible for the specific implicit CHECK-NOT.
854 std::string Prefix = std::string("-") + ImplicitCheckNot.ArgStr + "='";
855 std::string Suffix = "'";
856 std::unique_ptr<MemoryBuffer> CmdLine(MemoryBuffer::getMemBufferCopy(
857 Prefix + PatternString + Suffix, "command line"));
858 StringRef PatternInBuffer =
859 CmdLine->getBuffer().substr(Prefix.size(), PatternString.size());
860 SM.AddNewSourceBuffer(std::move(CmdLine), SMLoc());
862 ImplicitNegativeChecks.push_back(Pattern(Check::CheckNot));
863 ImplicitNegativeChecks.back().ParsePattern(PatternInBuffer,
864 "IMPLICIT-CHECK", SM, 0);
868 std::vector<Pattern> DagNotMatches = ImplicitNegativeChecks;
870 // LineNumber keeps track of the line on which CheckPrefix instances are
872 unsigned LineNumber = 1;
875 Check::CheckType CheckTy;
878 // See if a prefix occurs in the memory buffer.
879 StringRef UsedPrefix = FindFirstMatchingPrefix(Buffer,
883 if (UsedPrefix.empty())
886 Buffer = Buffer.drop_front(PrefixLoc);
888 // Location to use for error messages.
889 const char *UsedPrefixStart = Buffer.data() + (PrefixLoc == 0 ? 0 : 1);
891 // PrefixLoc is to the start of the prefix. Skip to the end.
892 Buffer = Buffer.drop_front(UsedPrefix.size() + CheckTypeSize(CheckTy));
894 // Okay, we found the prefix, yay. Remember the rest of the line, but ignore
895 // leading and trailing whitespace.
896 Buffer = Buffer.substr(Buffer.find_first_not_of(" \t"));
898 // Scan ahead to the end of line.
899 size_t EOL = Buffer.find_first_of("\n\r");
901 // Remember the location of the start of the pattern, for diagnostics.
902 SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data());
904 // Parse the pattern.
906 if (P.ParsePattern(Buffer.substr(0, EOL), UsedPrefix, SM, LineNumber))
909 // Verify that CHECK-LABEL lines do not define or use variables
910 if ((CheckTy == Check::CheckLabel) && P.hasVariable()) {
911 SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
913 "found '" + UsedPrefix + "-LABEL:'"
914 " with variable definition or use");
918 Buffer = Buffer.substr(EOL);
920 // Verify that CHECK-NEXT lines have at least one CHECK line before them.
921 if ((CheckTy == Check::CheckNext) && CheckStrings.empty()) {
922 SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
924 "found '" + UsedPrefix + "-NEXT:' without previous '"
925 + UsedPrefix + ": line");
929 // Handle CHECK-DAG/-NOT.
930 if (CheckTy == Check::CheckDAG || CheckTy == Check::CheckNot) {
931 DagNotMatches.push_back(P);
935 // Okay, add the string we captured to the output vector and move on.
936 CheckStrings.push_back(CheckString(P,
940 std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
941 DagNotMatches = ImplicitNegativeChecks;
944 // Add an EOF pattern for any trailing CHECK-DAG/-NOTs, and use the first
945 // prefix as a filler for the error message.
946 if (!DagNotMatches.empty()) {
947 CheckStrings.push_back(CheckString(Pattern(Check::CheckEOF),
949 SMLoc::getFromPointer(Buffer.data()),
951 std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
954 if (CheckStrings.empty()) {
955 errs() << "error: no check strings found with prefix"
956 << (CheckPrefixes.size() > 1 ? "es " : " ");
957 for (size_t I = 0, N = CheckPrefixes.size(); I != N; ++I) {
958 StringRef Prefix(CheckPrefixes[I]);
959 errs() << '\'' << Prefix << ":'";
971 static void PrintCheckFailed(const SourceMgr &SM, const SMLoc &Loc,
972 const Pattern &Pat, StringRef Buffer,
973 StringMap<StringRef> &VariableTable) {
974 // Otherwise, we have an error, emit an error message.
975 SM.PrintMessage(Loc, SourceMgr::DK_Error,
976 "expected string not found in input");
978 // Print the "scanning from here" line. If the current position is at the
979 // end of a line, advance to the start of the next line.
980 Buffer = Buffer.substr(Buffer.find_first_not_of(" \t\n\r"));
982 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
983 "scanning from here");
985 // Allow the pattern to print additional information if desired.
986 Pat.PrintFailureInfo(SM, Buffer, VariableTable);
989 static void PrintCheckFailed(const SourceMgr &SM, const CheckString &CheckStr,
991 StringMap<StringRef> &VariableTable) {
992 PrintCheckFailed(SM, CheckStr.Loc, CheckStr.Pat, Buffer, VariableTable);
995 /// CountNumNewlinesBetween - Count the number of newlines in the specified
997 static unsigned CountNumNewlinesBetween(StringRef Range,
998 const char *&FirstNewLine) {
999 unsigned NumNewLines = 0;
1001 // Scan for newline.
1002 Range = Range.substr(Range.find_first_of("\n\r"));
1003 if (Range.empty()) return NumNewLines;
1007 // Handle \n\r and \r\n as a single newline.
1008 if (Range.size() > 1 &&
1009 (Range[1] == '\n' || Range[1] == '\r') &&
1010 (Range[0] != Range[1]))
1011 Range = Range.substr(1);
1012 Range = Range.substr(1);
1014 if (NumNewLines == 1)
1015 FirstNewLine = Range.begin();
1019 size_t CheckString::Check(const SourceMgr &SM, StringRef Buffer,
1020 bool IsLabelScanMode, size_t &MatchLen,
1021 StringMap<StringRef> &VariableTable) const {
1023 std::vector<const Pattern *> NotStrings;
1025 // IsLabelScanMode is true when we are scanning forward to find CHECK-LABEL
1026 // bounds; we have not processed variable definitions within the bounded block
1027 // yet so cannot handle any final CHECK-DAG yet; this is handled when going
1028 // over the block again (including the last CHECK-LABEL) in normal mode.
1029 if (!IsLabelScanMode) {
1030 // Match "dag strings" (with mixed "not strings" if any).
1031 LastPos = CheckDag(SM, Buffer, NotStrings, VariableTable);
1032 if (LastPos == StringRef::npos)
1033 return StringRef::npos;
1036 // Match itself from the last position after matching CHECK-DAG.
1037 StringRef MatchBuffer = Buffer.substr(LastPos);
1038 size_t MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable);
1039 if (MatchPos == StringRef::npos) {
1040 PrintCheckFailed(SM, *this, MatchBuffer, VariableTable);
1041 return StringRef::npos;
1043 MatchPos += LastPos;
1045 // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT
1047 if (!IsLabelScanMode) {
1048 StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
1050 // If this check is a "CHECK-NEXT", verify that the previous match was on
1051 // the previous line (i.e. that there is one newline between them).
1052 if (CheckNext(SM, SkippedRegion))
1053 return StringRef::npos;
1055 // If this match had "not strings", verify that they don't exist in the
1057 if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
1058 return StringRef::npos;
1064 bool CheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {
1065 if (CheckTy != Check::CheckNext)
1068 // Count the number of newlines between the previous match and this one.
1069 assert(Buffer.data() !=
1071 SM.FindBufferContainingLoc(
1072 SMLoc::getFromPointer(Buffer.data())))->getBufferStart() &&
1073 "CHECK-NEXT can't be the first check in a file");
1075 const char *FirstNewLine = nullptr;
1076 unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
1078 if (NumNewLines == 0) {
1079 SM.PrintMessage(Loc, SourceMgr::DK_Error, Prefix +
1080 "-NEXT: is on the same line as previous match");
1081 SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()),
1082 SourceMgr::DK_Note, "'next' match was here");
1083 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
1084 "previous match ended here");
1088 if (NumNewLines != 1) {
1089 SM.PrintMessage(Loc, SourceMgr::DK_Error, Prefix +
1090 "-NEXT: is not on the line after the previous match");
1091 SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()),
1092 SourceMgr::DK_Note, "'next' match was here");
1093 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
1094 "previous match ended here");
1095 SM.PrintMessage(SMLoc::getFromPointer(FirstNewLine), SourceMgr::DK_Note,
1096 "non-matching line after previous match is here");
1103 bool CheckString::CheckNot(const SourceMgr &SM, StringRef Buffer,
1104 const std::vector<const Pattern *> &NotStrings,
1105 StringMap<StringRef> &VariableTable) const {
1106 for (unsigned ChunkNo = 0, e = NotStrings.size();
1107 ChunkNo != e; ++ChunkNo) {
1108 const Pattern *Pat = NotStrings[ChunkNo];
1109 assert((Pat->getCheckTy() == Check::CheckNot) && "Expect CHECK-NOT!");
1111 size_t MatchLen = 0;
1112 size_t Pos = Pat->Match(Buffer, MatchLen, VariableTable);
1114 if (Pos == StringRef::npos) continue;
1116 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()+Pos),
1117 SourceMgr::DK_Error,
1118 Prefix + "-NOT: string occurred!");
1119 SM.PrintMessage(Pat->getLoc(), SourceMgr::DK_Note,
1120 Prefix + "-NOT: pattern specified here");
1127 size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
1128 std::vector<const Pattern *> &NotStrings,
1129 StringMap<StringRef> &VariableTable) const {
1130 if (DagNotStrings.empty())
1134 size_t StartPos = LastPos;
1136 for (unsigned ChunkNo = 0, e = DagNotStrings.size();
1137 ChunkNo != e; ++ChunkNo) {
1138 const Pattern &Pat = DagNotStrings[ChunkNo];
1140 assert((Pat.getCheckTy() == Check::CheckDAG ||
1141 Pat.getCheckTy() == Check::CheckNot) &&
1142 "Invalid CHECK-DAG or CHECK-NOT!");
1144 if (Pat.getCheckTy() == Check::CheckNot) {
1145 NotStrings.push_back(&Pat);
1149 assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
1151 size_t MatchLen = 0, MatchPos;
1153 // CHECK-DAG always matches from the start.
1154 StringRef MatchBuffer = Buffer.substr(StartPos);
1155 MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable);
1156 // With a group of CHECK-DAGs, a single mismatching means the match on
1157 // that group of CHECK-DAGs fails immediately.
1158 if (MatchPos == StringRef::npos) {
1159 PrintCheckFailed(SM, Pat.getLoc(), Pat, MatchBuffer, VariableTable);
1160 return StringRef::npos;
1162 // Re-calc it as the offset relative to the start of the original string.
1163 MatchPos += StartPos;
1165 if (!NotStrings.empty()) {
1166 if (MatchPos < LastPos) {
1168 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + MatchPos),
1169 SourceMgr::DK_Error,
1170 Prefix + "-DAG: found a match of CHECK-DAG"
1171 " reordering across a CHECK-NOT");
1172 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + LastPos),
1174 Prefix + "-DAG: the farthest match of CHECK-DAG"
1176 SM.PrintMessage(NotStrings[0]->getLoc(), SourceMgr::DK_Note,
1177 Prefix + "-NOT: the crossed pattern specified"
1179 SM.PrintMessage(Pat.getLoc(), SourceMgr::DK_Note,
1180 Prefix + "-DAG: the reordered pattern specified"
1182 return StringRef::npos;
1184 // All subsequent CHECK-DAGs should be matched from the farthest
1185 // position of all precedent CHECK-DAGs (including this one.)
1187 // If there's CHECK-NOTs between two CHECK-DAGs or from CHECK to
1188 // CHECK-DAG, verify that there's no 'not' strings occurred in that
1190 StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
1191 if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable))
1192 return StringRef::npos;
1193 // Clear "not strings".
1197 // Update the last position with CHECK-DAG matches.
1198 LastPos = std::max(MatchPos + MatchLen, LastPos);
1204 // A check prefix must contain only alphanumeric, hyphens and underscores.
1205 static bool ValidateCheckPrefix(StringRef CheckPrefix) {
1206 Regex Validator("^[a-zA-Z0-9_-]*$");
1207 return Validator.match(CheckPrefix);
1210 static bool ValidateCheckPrefixes() {
1211 StringSet<> PrefixSet;
1213 for (prefix_iterator I = CheckPrefixes.begin(), E = CheckPrefixes.end();
1215 StringRef Prefix(*I);
1217 // Reject empty prefixes.
1221 if (!PrefixSet.insert(Prefix))
1224 if (!ValidateCheckPrefix(Prefix))
1231 // I don't think there's a way to specify an initial value for cl::list,
1232 // so if nothing was specified, add the default
1233 static void AddCheckPrefixIfNeeded() {
1234 if (CheckPrefixes.empty())
1235 CheckPrefixes.push_back("CHECK");
1238 int main(int argc, char **argv) {
1239 sys::PrintStackTraceOnErrorSignal();
1240 PrettyStackTraceProgram X(argc, argv);
1241 cl::ParseCommandLineOptions(argc, argv);
1243 if (!ValidateCheckPrefixes()) {
1244 errs() << "Supplied check-prefix is invalid! Prefixes must be unique and "
1245 "start with a letter and contain only alphanumeric characters, "
1246 "hyphens and underscores\n";
1250 AddCheckPrefixIfNeeded();
1254 // Read the expected strings from the check file.
1255 std::vector<CheckString> CheckStrings;
1256 if (ReadCheckFile(SM, CheckStrings))
1259 // Open the file to check and add it to SourceMgr.
1260 ErrorOr<std::unique_ptr<MemoryBuffer>> FileOrErr =
1261 MemoryBuffer::getFileOrSTDIN(InputFilename);
1262 if (std::error_code EC = FileOrErr.getError()) {
1263 errs() << "Could not open input file '" << InputFilename
1264 << "': " << EC.message() << '\n';
1267 std::unique_ptr<MemoryBuffer> &File = FileOrErr.get();
1269 if (File->getBufferSize() == 0 && !AllowEmptyInput) {
1270 errs() << "FileCheck error: '" << InputFilename << "' is empty.\n";
1274 // Remove duplicate spaces in the input file if requested.
1275 // Remove DOS style line endings.
1276 std::unique_ptr<MemoryBuffer> F =
1277 CanonicalizeInputFile(std::move(File), NoCanonicalizeWhiteSpace);
1279 // Check that we have all of the expected strings, in order, in the input
1281 StringRef Buffer = F->getBuffer();
1283 SM.AddNewSourceBuffer(std::move(F), SMLoc());
1285 /// VariableTable - This holds all the current filecheck variables.
1286 StringMap<StringRef> VariableTable;
1288 bool hasError = false;
1290 unsigned i = 0, j = 0, e = CheckStrings.size();
1293 StringRef CheckRegion;
1295 CheckRegion = Buffer;
1297 const CheckString &CheckLabelStr = CheckStrings[j];
1298 if (CheckLabelStr.CheckTy != Check::CheckLabel) {
1303 // Scan to next CHECK-LABEL match, ignoring CHECK-NOT and CHECK-DAG
1304 size_t MatchLabelLen = 0;
1305 size_t MatchLabelPos = CheckLabelStr.Check(SM, Buffer, true,
1306 MatchLabelLen, VariableTable);
1307 if (MatchLabelPos == StringRef::npos) {
1312 CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);
1313 Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);
1317 for ( ; i != j; ++i) {
1318 const CheckString &CheckStr = CheckStrings[i];
1320 // Check each string within the scanned region, including a second check
1321 // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG)
1322 size_t MatchLen = 0;
1323 size_t MatchPos = CheckStr.Check(SM, CheckRegion, false, MatchLen,
1326 if (MatchPos == StringRef::npos) {
1332 CheckRegion = CheckRegion.substr(MatchPos + MatchLen);
1339 return hasError ? 1 : 0;