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/Support/CommandLine.h"
20 #include "llvm/Support/MemoryBuffer.h"
21 #include "llvm/Support/PrettyStackTrace.h"
22 #include "llvm/Support/Regex.h"
23 #include "llvm/Support/SourceMgr.h"
24 #include "llvm/Support/raw_ostream.h"
25 #include "llvm/System/Signals.h"
26 #include "llvm/ADT/SmallString.h"
27 #include "llvm/ADT/StringMap.h"
31 static cl::opt<std::string>
32 CheckFilename(cl::Positional, cl::desc("<check-file>"), cl::Required);
34 static cl::opt<std::string>
35 InputFilename("input-file", cl::desc("File to check (defaults to stdin)"),
36 cl::init("-"), cl::value_desc("filename"));
38 static cl::opt<std::string>
39 CheckPrefix("check-prefix", cl::init("CHECK"),
40 cl::desc("Prefix to use from check file (defaults to 'CHECK')"));
43 NoCanonicalizeWhiteSpace("strict-whitespace",
44 cl::desc("Do not treat all horizontal whitespace as equivalent"));
46 //===----------------------------------------------------------------------===//
47 // Pattern Handling Code.
48 //===----------------------------------------------------------------------===//
53 /// FixedStr - If non-empty, this pattern is a fixed string match with the
54 /// specified fixed string.
57 /// RegEx - If non-empty, this is a regex pattern.
60 /// VariableUses - Entries in this vector map to uses of a variable in the
61 /// pattern, e.g. "foo[[bar]]baz". In this case, the RegExStr will contain
62 /// "foobaz" and we'll get an entry in this vector that tells us to insert the
63 /// value of bar at offset 3.
64 std::vector<std::pair<StringRef, unsigned> > VariableUses;
66 /// VariableDefs - Entries in this vector map to definitions of a variable in
67 /// the pattern, e.g. "foo[[bar:.*]]baz". In this case, the RegExStr will
68 /// contain "foo(.*)baz" and VariableDefs will contain the pair "bar",1. The
69 /// index indicates what parenthesized value captures the variable value.
70 std::vector<std::pair<StringRef, unsigned> > VariableDefs;
76 bool ParsePattern(StringRef PatternStr, SourceMgr &SM);
78 /// Match - Match the pattern string against the input buffer Buffer. This
79 /// returns the position that is matched or npos if there is no match. If
80 /// there is a match, the size of the matched string is returned in MatchLen.
82 /// The VariableTable StringMap provides the current values of filecheck
83 /// variables and is updated if this match defines new values.
84 size_t Match(StringRef Buffer, size_t &MatchLen,
85 StringMap<StringRef> &VariableTable) const;
87 /// PrintFailureInfo - Print additional information about a failure to match
88 /// involving this pattern.
89 void PrintFailureInfo(const SourceMgr &SM, StringRef Buffer,
90 const StringMap<StringRef> &VariableTable) const;
93 static void AddFixedStringToRegEx(StringRef FixedStr, std::string &TheStr);
94 bool AddRegExToRegEx(StringRef RegExStr, unsigned &CurParen, SourceMgr &SM);
96 /// ComputeMatchDistance - Compute an arbitrary estimate for the quality of
97 /// matching this pattern at the start of \arg Buffer; a distance of zero
98 /// should correspond to a perfect match.
99 unsigned ComputeMatchDistance(StringRef Buffer,
100 const StringMap<StringRef> &VariableTable) const;
104 bool Pattern::ParsePattern(StringRef PatternStr, SourceMgr &SM) {
105 PatternLoc = SMLoc::getFromPointer(PatternStr.data());
107 // Ignore trailing whitespace.
108 while (!PatternStr.empty() &&
109 (PatternStr.back() == ' ' || PatternStr.back() == '\t'))
110 PatternStr = PatternStr.substr(0, PatternStr.size()-1);
112 // Check that there is something on the line.
113 if (PatternStr.empty()) {
114 SM.PrintMessage(PatternLoc, "found empty check string with prefix '" +
115 CheckPrefix+":'", "error");
119 // Check to see if this is a fixed string, or if it has regex pieces.
120 if (PatternStr.size() < 2 ||
121 (PatternStr.find("{{") == StringRef::npos &&
122 PatternStr.find("[[") == StringRef::npos)) {
123 FixedStr = PatternStr;
127 // Paren value #0 is for the fully matched string. Any new parenthesized
128 // values add from their.
129 unsigned CurParen = 1;
131 // Otherwise, there is at least one regex piece. Build up the regex pattern
132 // by escaping scary characters in fixed strings, building up one big regex.
133 while (!PatternStr.empty()) {
135 if (PatternStr.size() >= 2 &&
136 PatternStr[0] == '{' && PatternStr[1] == '{') {
138 // Otherwise, this is the start of a regex match. Scan for the }}.
139 size_t End = PatternStr.find("}}");
140 if (End == StringRef::npos) {
141 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
142 "found start of regex string with no end '}}'", "error");
146 if (AddRegExToRegEx(PatternStr.substr(2, End-2), CurParen, SM))
148 PatternStr = PatternStr.substr(End+2);
152 // Named RegEx matches. These are of two forms: [[foo:.*]] which matches .*
153 // (or some other regex) and assigns it to the FileCheck variable 'foo'. The
154 // second form is [[foo]] which is a reference to foo. The variable name
155 // itself must be of the form "[a-zA-Z_][0-9a-zA-Z_]*", otherwise we reject
156 // it. This is to catch some common errors.
157 if (PatternStr.size() >= 2 &&
158 PatternStr[0] == '[' && PatternStr[1] == '[') {
159 // Verify that it is terminated properly.
160 size_t End = PatternStr.find("]]");
161 if (End == StringRef::npos) {
162 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
163 "invalid named regex reference, no ]] found", "error");
167 StringRef MatchStr = PatternStr.substr(2, End-2);
168 PatternStr = PatternStr.substr(End+2);
170 // Get the regex name (e.g. "foo").
171 size_t NameEnd = MatchStr.find(':');
172 StringRef Name = MatchStr.substr(0, NameEnd);
175 SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
176 "invalid name in named regex: empty name", "error");
180 // Verify that the name is well formed.
181 for (unsigned i = 0, e = Name.size(); i != e; ++i)
182 if (Name[i] != '_' &&
183 (Name[i] < 'a' || Name[i] > 'z') &&
184 (Name[i] < 'A' || Name[i] > 'Z') &&
185 (Name[i] < '0' || Name[i] > '9')) {
186 SM.PrintMessage(SMLoc::getFromPointer(Name.data()+i),
187 "invalid name in named regex", "error");
191 // Name can't start with a digit.
192 if (isdigit(Name[0])) {
193 SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
194 "invalid name in named regex", "error");
199 if (NameEnd == StringRef::npos) {
200 VariableUses.push_back(std::make_pair(Name, RegExStr.size()));
204 // Handle [[foo:.*]].
205 VariableDefs.push_back(std::make_pair(Name, CurParen));
209 if (AddRegExToRegEx(MatchStr.substr(NameEnd+1), CurParen, SM))
215 // Handle fixed string matches.
216 // Find the end, which is the start of the next regex.
217 size_t FixedMatchEnd = PatternStr.find("{{");
218 FixedMatchEnd = std::min(FixedMatchEnd, PatternStr.find("[["));
219 AddFixedStringToRegEx(PatternStr.substr(0, FixedMatchEnd), RegExStr);
220 PatternStr = PatternStr.substr(FixedMatchEnd);
227 void Pattern::AddFixedStringToRegEx(StringRef FixedStr, std::string &TheStr) {
228 // Add the characters from FixedStr to the regex, escaping as needed. This
229 // avoids "leaning toothpicks" in common patterns.
230 for (unsigned i = 0, e = FixedStr.size(); i != e; ++i) {
231 switch (FixedStr[i]) {
232 // These are the special characters matched in "p_ere_exp".
248 TheStr += FixedStr[i];
254 bool Pattern::AddRegExToRegEx(StringRef RegexStr, unsigned &CurParen,
258 if (!R.isValid(Error)) {
259 SM.PrintMessage(SMLoc::getFromPointer(RegexStr.data()),
260 "invalid regex: " + Error, "error");
264 RegExStr += RegexStr.str();
265 CurParen += R.getNumMatches();
269 /// Match - Match the pattern string against the input buffer Buffer. This
270 /// returns the position that is matched or npos if there is no match. If
271 /// there is a match, the size of the matched string is returned in MatchLen.
272 size_t Pattern::Match(StringRef Buffer, size_t &MatchLen,
273 StringMap<StringRef> &VariableTable) const {
274 // If this is a fixed string pattern, just match it now.
275 if (!FixedStr.empty()) {
276 MatchLen = FixedStr.size();
277 return Buffer.find(FixedStr);
282 // If there are variable uses, we need to create a temporary string with the
284 StringRef RegExToMatch = RegExStr;
286 if (!VariableUses.empty()) {
289 unsigned InsertOffset = 0;
290 for (unsigned i = 0, e = VariableUses.size(); i != e; ++i) {
291 StringMap<StringRef>::iterator it =
292 VariableTable.find(VariableUses[i].first);
293 // If the variable is undefined, return an error.
294 if (it == VariableTable.end())
295 return StringRef::npos;
297 // Look up the value and escape it so that we can plop it into the regex.
299 AddFixedStringToRegEx(it->second, Value);
301 // Plop it into the regex at the adjusted offset.
302 TmpStr.insert(TmpStr.begin()+VariableUses[i].second+InsertOffset,
303 Value.begin(), Value.end());
304 InsertOffset += Value.size();
307 // Match the newly constructed regex.
308 RegExToMatch = TmpStr;
312 SmallVector<StringRef, 4> MatchInfo;
313 if (!Regex(RegExToMatch, Regex::Newline).match(Buffer, &MatchInfo))
314 return StringRef::npos;
316 // Successful regex match.
317 assert(!MatchInfo.empty() && "Didn't get any match");
318 StringRef FullMatch = MatchInfo[0];
320 // If this defines any variables, remember their values.
321 for (unsigned i = 0, e = VariableDefs.size(); i != e; ++i) {
322 assert(VariableDefs[i].second < MatchInfo.size() &&
323 "Internal paren error");
324 VariableTable[VariableDefs[i].first] = MatchInfo[VariableDefs[i].second];
327 MatchLen = FullMatch.size();
328 return FullMatch.data()-Buffer.data();
331 unsigned Pattern::ComputeMatchDistance(StringRef Buffer,
332 const StringMap<StringRef> &VariableTable) const {
333 // Just compute the number of matching characters. For regular expressions, we
334 // just compare against the regex itself and hope for the best.
336 // FIXME: One easy improvement here is have the regex lib generate a single
337 // example regular expression which matches, and use that as the example
339 StringRef ExampleString(FixedStr);
340 if (ExampleString.empty())
341 ExampleString = RegExStr;
343 unsigned Distance = 0;
344 for (unsigned i = 0, e = ExampleString.size(); i != e; ++i)
345 if (Buffer.substr(i, 1) != ExampleString.substr(i, 1))
351 void Pattern::PrintFailureInfo(const SourceMgr &SM, StringRef Buffer,
352 const StringMap<StringRef> &VariableTable) const{
353 // If this was a regular expression using variables, print the current
355 if (!VariableUses.empty()) {
356 for (unsigned i = 0, e = VariableUses.size(); i != e; ++i) {
357 StringRef Var = VariableUses[i].first;
358 StringMap<StringRef>::const_iterator it = VariableTable.find(Var);
359 SmallString<256> Msg;
360 raw_svector_ostream OS(Msg);
362 // Check for undefined variable references.
363 if (it == VariableTable.end()) {
364 OS << "uses undefined variable \"";
365 OS.write_escaped(Var) << "\"";;
367 OS << "with variable \"";
368 OS.write_escaped(Var) << "\" equal to \"";
369 OS.write_escaped(it->second) << "\"";
372 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), OS.str(), "note",
377 // Attempt to find the closest/best fuzzy match. Usually an error happens
378 // because some string in the output didn't exactly match. In these cases, we
379 // would like to show the user a best guess at what "should have" matched, to
380 // save them having to actually check the input manually.
381 size_t NumLinesForward = 0;
382 size_t Best = StringRef::npos;
383 double BestQuality = 0;
385 // Use an arbitrary 4k limit on how far we will search.
386 for (size_t i = 0, e = std::min(4096, int(Buffer.size())); i != e; ++i) {
387 if (Buffer[i] == '\n')
390 // Compute the "quality" of this match as an arbitrary combination of the
391 // match distance and the number of lines skipped to get to this match.
392 unsigned Distance = ComputeMatchDistance(Buffer.substr(i), VariableTable);
393 double Quality = Distance + (NumLinesForward / 100.);
395 if (Quality < BestQuality || Best == StringRef::npos) {
397 BestQuality = Quality;
401 if (Best != StringRef::npos && BestQuality < 50) {
402 // Print the "possible intended match here" line if we found something
404 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + Best),
405 "possible intended match here", "note");
407 // FIXME: If we wanted to be really friendly we would show why the match
408 // failed, as it can be hard to spot simple one character differences.
412 //===----------------------------------------------------------------------===//
414 //===----------------------------------------------------------------------===//
416 /// CheckString - This is a check that we found in the input file.
418 /// Pat - The pattern to match.
421 /// Loc - The location in the match file that the check string was specified.
424 /// IsCheckNext - This is true if this is a CHECK-NEXT: directive (as opposed
425 /// to a CHECK: directive.
428 /// NotStrings - These are all of the strings that are disallowed from
429 /// occurring between this match string and the previous one (or start of
431 std::vector<std::pair<SMLoc, Pattern> > NotStrings;
433 CheckString(const Pattern &P, SMLoc L, bool isCheckNext)
434 : Pat(P), Loc(L), IsCheckNext(isCheckNext) {}
437 /// CanonicalizeInputFile - Remove duplicate horizontal space from the specified
438 /// memory buffer, free it, and return a new one.
439 static MemoryBuffer *CanonicalizeInputFile(MemoryBuffer *MB) {
440 SmallVector<char, 16> NewFile;
441 NewFile.reserve(MB->getBufferSize());
443 for (const char *Ptr = MB->getBufferStart(), *End = MB->getBufferEnd();
445 // If C is not a horizontal whitespace, skip it.
446 if (*Ptr != ' ' && *Ptr != '\t') {
447 NewFile.push_back(*Ptr);
451 // Otherwise, add one space and advance over neighboring space.
452 NewFile.push_back(' ');
453 while (Ptr+1 != End &&
454 (Ptr[1] == ' ' || Ptr[1] == '\t'))
458 // Free the old buffer and return a new one.
460 MemoryBuffer::getMemBufferCopy(NewFile.data(),
461 NewFile.data() + NewFile.size(),
462 MB->getBufferIdentifier());
469 /// ReadCheckFile - Read the check file, which specifies the sequence of
470 /// expected strings. The strings are added to the CheckStrings vector.
471 static bool ReadCheckFile(SourceMgr &SM,
472 std::vector<CheckString> &CheckStrings) {
473 // Open the check file, and tell SourceMgr about it.
474 std::string ErrorStr;
476 MemoryBuffer::getFileOrSTDIN(CheckFilename.c_str(), &ErrorStr);
478 errs() << "Could not open check file '" << CheckFilename << "': "
483 // If we want to canonicalize whitespace, strip excess whitespace from the
484 // buffer containing the CHECK lines.
485 if (!NoCanonicalizeWhiteSpace)
486 F = CanonicalizeInputFile(F);
488 SM.AddNewSourceBuffer(F, SMLoc());
490 // Find all instances of CheckPrefix followed by : in the file.
491 StringRef Buffer = F->getBuffer();
493 std::vector<std::pair<SMLoc, Pattern> > NotMatches;
496 // See if Prefix occurs in the memory buffer.
497 Buffer = Buffer.substr(Buffer.find(CheckPrefix));
499 // If we didn't find a match, we're done.
503 const char *CheckPrefixStart = Buffer.data();
505 // When we find a check prefix, keep track of whether we find CHECK: or
507 bool IsCheckNext = false, IsCheckNot = false;
509 // Verify that the : is present after the prefix.
510 if (Buffer[CheckPrefix.size()] == ':') {
511 Buffer = Buffer.substr(CheckPrefix.size()+1);
512 } else if (Buffer.size() > CheckPrefix.size()+6 &&
513 memcmp(Buffer.data()+CheckPrefix.size(), "-NEXT:", 6) == 0) {
514 Buffer = Buffer.substr(CheckPrefix.size()+7);
516 } else if (Buffer.size() > CheckPrefix.size()+5 &&
517 memcmp(Buffer.data()+CheckPrefix.size(), "-NOT:", 5) == 0) {
518 Buffer = Buffer.substr(CheckPrefix.size()+6);
521 Buffer = Buffer.substr(1);
525 // Okay, we found the prefix, yay. Remember the rest of the line, but
526 // ignore leading and trailing whitespace.
527 Buffer = Buffer.substr(Buffer.find_first_not_of(" \t"));
529 // Scan ahead to the end of line.
530 size_t EOL = Buffer.find_first_of("\n\r");
532 // Parse the pattern.
534 if (P.ParsePattern(Buffer.substr(0, EOL), SM))
537 Buffer = Buffer.substr(EOL);
540 // Verify that CHECK-NEXT lines have at least one CHECK line before them.
541 if (IsCheckNext && CheckStrings.empty()) {
542 SM.PrintMessage(SMLoc::getFromPointer(CheckPrefixStart),
543 "found '"+CheckPrefix+"-NEXT:' without previous '"+
544 CheckPrefix+ ": line", "error");
550 NotMatches.push_back(std::make_pair(SMLoc::getFromPointer(Buffer.data()),
556 // Okay, add the string we captured to the output vector and move on.
557 CheckStrings.push_back(CheckString(P,
558 SMLoc::getFromPointer(Buffer.data()),
560 std::swap(NotMatches, CheckStrings.back().NotStrings);
563 if (CheckStrings.empty()) {
564 errs() << "error: no check strings found with prefix '" << CheckPrefix
569 if (!NotMatches.empty()) {
570 errs() << "error: '" << CheckPrefix
571 << "-NOT:' not supported after last check line.\n";
578 static void PrintCheckFailed(const SourceMgr &SM, const CheckString &CheckStr,
580 StringMap<StringRef> &VariableTable) {
581 // Otherwise, we have an error, emit an error message.
582 SM.PrintMessage(CheckStr.Loc, "expected string not found in input",
585 // Print the "scanning from here" line. If the current position is at the
586 // end of a line, advance to the start of the next line.
587 Buffer = Buffer.substr(Buffer.find_first_not_of(" \t\n\r"));
589 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), "scanning from here",
592 // Allow the pattern to print additional information if desired.
593 CheckStr.Pat.PrintFailureInfo(SM, Buffer, VariableTable);
596 /// CountNumNewlinesBetween - Count the number of newlines in the specified
598 static unsigned CountNumNewlinesBetween(StringRef Range) {
599 unsigned NumNewLines = 0;
602 Range = Range.substr(Range.find_first_of("\n\r"));
603 if (Range.empty()) return NumNewLines;
607 // Handle \n\r and \r\n as a single newline.
608 if (Range.size() > 1 &&
609 (Range[1] == '\n' || Range[1] == '\r') &&
610 (Range[0] != Range[1]))
611 Range = Range.substr(1);
612 Range = Range.substr(1);
616 int main(int argc, char **argv) {
617 sys::PrintStackTraceOnErrorSignal();
618 PrettyStackTraceProgram X(argc, argv);
619 cl::ParseCommandLineOptions(argc, argv);
623 // Read the expected strings from the check file.
624 std::vector<CheckString> CheckStrings;
625 if (ReadCheckFile(SM, CheckStrings))
628 // Open the file to check and add it to SourceMgr.
629 std::string ErrorStr;
631 MemoryBuffer::getFileOrSTDIN(InputFilename.c_str(), &ErrorStr);
633 errs() << "Could not open input file '" << InputFilename << "': "
638 // Remove duplicate spaces in the input file if requested.
639 if (!NoCanonicalizeWhiteSpace)
640 F = CanonicalizeInputFile(F);
642 SM.AddNewSourceBuffer(F, SMLoc());
644 /// VariableTable - This holds all the current filecheck variables.
645 StringMap<StringRef> VariableTable;
647 // Check that we have all of the expected strings, in order, in the input
649 StringRef Buffer = F->getBuffer();
651 const char *LastMatch = Buffer.data();
653 for (unsigned StrNo = 0, e = CheckStrings.size(); StrNo != e; ++StrNo) {
654 const CheckString &CheckStr = CheckStrings[StrNo];
656 StringRef SearchFrom = Buffer;
658 // Find StrNo in the file.
660 Buffer = Buffer.substr(CheckStr.Pat.Match(Buffer, MatchLen, VariableTable));
662 // If we didn't find a match, reject the input.
663 if (Buffer.empty()) {
664 PrintCheckFailed(SM, CheckStr, SearchFrom, VariableTable);
668 StringRef SkippedRegion(LastMatch, Buffer.data()-LastMatch);
670 // If this check is a "CHECK-NEXT", verify that the previous match was on
671 // the previous line (i.e. that there is one newline between them).
672 if (CheckStr.IsCheckNext) {
673 // Count the number of newlines between the previous match and this one.
674 assert(LastMatch != F->getBufferStart() &&
675 "CHECK-NEXT can't be the first check in a file");
677 unsigned NumNewLines = CountNumNewlinesBetween(SkippedRegion);
678 if (NumNewLines == 0) {
679 SM.PrintMessage(CheckStr.Loc,
680 CheckPrefix+"-NEXT: is on the same line as previous match",
682 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),
683 "'next' match was here", "note");
684 SM.PrintMessage(SMLoc::getFromPointer(LastMatch),
685 "previous match was here", "note");
689 if (NumNewLines != 1) {
690 SM.PrintMessage(CheckStr.Loc,
692 "-NEXT: is not on the line after the previous match",
694 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),
695 "'next' match was here", "note");
696 SM.PrintMessage(SMLoc::getFromPointer(LastMatch),
697 "previous match was here", "note");
702 // If this match had "not strings", verify that they don't exist in the
704 for (unsigned ChunkNo = 0, e = CheckStr.NotStrings.size();
705 ChunkNo != e; ++ChunkNo) {
707 size_t Pos = CheckStr.NotStrings[ChunkNo].second.Match(SkippedRegion,
710 if (Pos == StringRef::npos) continue;
712 SM.PrintMessage(SMLoc::getFromPointer(LastMatch+Pos),
713 CheckPrefix+"-NOT: string occurred!", "error");
714 SM.PrintMessage(CheckStr.NotStrings[ChunkNo].first,
715 CheckPrefix+"-NOT: pattern specified here", "note");
720 // Otherwise, everything is good. Step over the matched text and remember
721 // the position after the match as the end of the last match.
722 Buffer = Buffer.substr(MatchLen);
723 LastMatch = Buffer.data();