FileCheck.cpp revision d9a84efe44db2f4d983e49bc7370fc8cef449214
1//===- FileCheck.cpp - Check that File's Contents match what is expected --===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 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. 12// 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. 16// 17//===----------------------------------------------------------------------===// 18 19#include "llvm/ADT/OwningPtr.h" 20#include "llvm/ADT/SmallString.h" 21#include "llvm/ADT/StringExtras.h" 22#include "llvm/ADT/StringMap.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" 30#include "llvm/Support/system_error.h" 31#include <algorithm> 32#include <map> 33#include <string> 34#include <vector> 35using namespace llvm; 36 37static cl::opt<std::string> 38CheckFilename(cl::Positional, cl::desc("<check-file>"), cl::Required); 39 40static cl::opt<std::string> 41InputFilename("input-file", cl::desc("File to check (defaults to stdin)"), 42 cl::init("-"), cl::value_desc("filename")); 43 44static cl::opt<std::string> 45CheckPrefix("check-prefix", cl::init("CHECK"), 46 cl::desc("Prefix to use from check file (defaults to 'CHECK')")); 47 48static cl::opt<bool> 49NoCanonicalizeWhiteSpace("strict-whitespace", 50 cl::desc("Do not treat all horizontal whitespace as equivalent")); 51 52//===----------------------------------------------------------------------===// 53// Pattern Handling Code. 54//===----------------------------------------------------------------------===// 55 56class Pattern { 57 SMLoc PatternLoc; 58 59 /// MatchEOF - When set, this pattern only matches the end of file. This is 60 /// used for trailing CHECK-NOTs. 61 bool MatchEOF; 62 63 /// MatchNot 64 bool MatchNot; 65 66 /// MatchDag 67 bool MatchDag; 68 69 /// FixedStr - If non-empty, this pattern is a fixed string match with the 70 /// specified fixed string. 71 StringRef FixedStr; 72 73 /// RegEx - If non-empty, this is a regex pattern. 74 std::string RegExStr; 75 76 /// \brief Contains the number of line this pattern is in. 77 unsigned LineNumber; 78 79 /// VariableUses - Entries in this vector map to uses of a variable in the 80 /// pattern, e.g. "foo[[bar]]baz". In this case, the RegExStr will contain 81 /// "foobaz" and we'll get an entry in this vector that tells us to insert the 82 /// value of bar at offset 3. 83 std::vector<std::pair<StringRef, unsigned> > VariableUses; 84 85 /// VariableDefs - Maps definitions of variables to their parenthesized 86 /// capture numbers. 87 /// E.g. for the pattern "foo[[bar:.*]]baz", VariableDefs will map "bar" to 1. 88 std::map<StringRef, unsigned> VariableDefs; 89 90public: 91 92 Pattern(bool matchEOF = false) 93 : MatchEOF(matchEOF), MatchNot(false), MatchDag(false) { } 94 95 /// getLoc - Return the location in source code. 96 SMLoc getLoc() const { return PatternLoc; } 97 98 /// ParsePattern - Parse the given string into the Pattern. SM provides the 99 /// SourceMgr used for error reports, and LineNumber is the line number in 100 /// the input file from which the pattern string was read. 101 /// Returns true in case of an error, false otherwise. 102 bool ParsePattern(StringRef PatternStr, SourceMgr &SM, unsigned LineNumber); 103 104 /// Match - Match the pattern string against the input buffer Buffer. This 105 /// returns the position that is matched or npos if there is no match. If 106 /// there is a match, the size of the matched string is returned in MatchLen. 107 /// 108 /// The VariableTable StringMap provides the current values of filecheck 109 /// variables and is updated if this match defines new values. 110 size_t Match(StringRef Buffer, size_t &MatchLen, 111 StringMap<StringRef> &VariableTable) const; 112 113 /// PrintFailureInfo - Print additional information about a failure to match 114 /// involving this pattern. 115 void PrintFailureInfo(const SourceMgr &SM, StringRef Buffer, 116 const StringMap<StringRef> &VariableTable) const; 117 118 bool hasVariable() const { return !(VariableUses.empty() && 119 VariableDefs.empty()); } 120 121 void setMatchNot(bool Not) { MatchNot = Not; } 122 bool getMatchNot() const { return MatchNot; } 123 124 void setMatchDag(bool Dag) { MatchDag = Dag; } 125 bool getMatchDag() const { return MatchDag; } 126 127private: 128 static void AddFixedStringToRegEx(StringRef FixedStr, std::string &TheStr); 129 bool AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM); 130 void AddBackrefToRegEx(unsigned BackrefNum); 131 132 /// ComputeMatchDistance - Compute an arbitrary estimate for the quality of 133 /// matching this pattern at the start of \arg Buffer; a distance of zero 134 /// should correspond to a perfect match. 135 unsigned ComputeMatchDistance(StringRef Buffer, 136 const StringMap<StringRef> &VariableTable) const; 137 138 /// \brief Evaluates expression and stores the result to \p Value. 139 /// \return true on success. false when the expression has invalid syntax. 140 bool EvaluateExpression(StringRef Expr, std::string &Value) const; 141 142 /// \brief Finds the closing sequence of a regex variable usage or 143 /// definition. Str has to point in the beginning of the definition 144 /// (right after the opening sequence). 145 /// \return offset of the closing sequence within Str, or npos if it was not 146 /// found. 147 size_t FindRegexVarEnd(StringRef Str); 148}; 149 150 151bool Pattern::ParsePattern(StringRef PatternStr, SourceMgr &SM, 152 unsigned LineNumber) { 153 this->LineNumber = LineNumber; 154 PatternLoc = SMLoc::getFromPointer(PatternStr.data()); 155 156 // Ignore trailing whitespace. 157 while (!PatternStr.empty() && 158 (PatternStr.back() == ' ' || PatternStr.back() == '\t')) 159 PatternStr = PatternStr.substr(0, PatternStr.size()-1); 160 161 // Check that there is something on the line. 162 if (PatternStr.empty()) { 163 SM.PrintMessage(PatternLoc, SourceMgr::DK_Error, 164 "found empty check string with prefix '" + 165 CheckPrefix+":'"); 166 return true; 167 } 168 169 // Check to see if this is a fixed string, or if it has regex pieces. 170 if (PatternStr.size() < 2 || 171 (PatternStr.find("{{") == StringRef::npos && 172 PatternStr.find("[[") == StringRef::npos)) { 173 FixedStr = PatternStr; 174 return false; 175 } 176 177 // Paren value #0 is for the fully matched string. Any new parenthesized 178 // values add from there. 179 unsigned CurParen = 1; 180 181 // Otherwise, there is at least one regex piece. Build up the regex pattern 182 // by escaping scary characters in fixed strings, building up one big regex. 183 while (!PatternStr.empty()) { 184 // RegEx matches. 185 if (PatternStr.startswith("{{")) { 186 // This is the start of a regex match. Scan for the }}. 187 size_t End = PatternStr.find("}}"); 188 if (End == StringRef::npos) { 189 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()), 190 SourceMgr::DK_Error, 191 "found start of regex string with no end '}}'"); 192 return true; 193 } 194 195 // Enclose {{}} patterns in parens just like [[]] even though we're not 196 // capturing the result for any purpose. This is required in case the 197 // expression contains an alternation like: CHECK: abc{{x|z}}def. We 198 // want this to turn into: "abc(x|z)def" not "abcx|zdef". 199 RegExStr += '('; 200 ++CurParen; 201 202 if (AddRegExToRegEx(PatternStr.substr(2, End-2), CurParen, SM)) 203 return true; 204 RegExStr += ')'; 205 206 PatternStr = PatternStr.substr(End+2); 207 continue; 208 } 209 210 // Named RegEx matches. These are of two forms: [[foo:.*]] which matches .* 211 // (or some other regex) and assigns it to the FileCheck variable 'foo'. The 212 // second form is [[foo]] which is a reference to foo. The variable name 213 // itself must be of the form "[a-zA-Z_][0-9a-zA-Z_]*", otherwise we reject 214 // it. This is to catch some common errors. 215 if (PatternStr.startswith("[[")) { 216 // Find the closing bracket pair ending the match. End is going to be an 217 // offset relative to the beginning of the match string. 218 size_t End = FindRegexVarEnd(PatternStr.substr(2)); 219 220 if (End == StringRef::npos) { 221 SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()), 222 SourceMgr::DK_Error, 223 "invalid named regex reference, no ]] found"); 224 return true; 225 } 226 227 StringRef MatchStr = PatternStr.substr(2, End); 228 PatternStr = PatternStr.substr(End+4); 229 230 // Get the regex name (e.g. "foo"). 231 size_t NameEnd = MatchStr.find(':'); 232 StringRef Name = MatchStr.substr(0, NameEnd); 233 234 if (Name.empty()) { 235 SM.PrintMessage(SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error, 236 "invalid name in named regex: empty name"); 237 return true; 238 } 239 240 // Verify that the name/expression is well formed. FileCheck currently 241 // supports @LINE, @LINE+number, @LINE-number expressions. The check here 242 // is relaxed, more strict check is performed in \c EvaluateExpression. 243 bool IsExpression = false; 244 for (unsigned i = 0, e = Name.size(); i != e; ++i) { 245 if (i == 0 && Name[i] == '@') { 246 if (NameEnd != StringRef::npos) { 247 SM.PrintMessage(SMLoc::getFromPointer(Name.data()), 248 SourceMgr::DK_Error, 249 "invalid name in named regex definition"); 250 return true; 251 } 252 IsExpression = true; 253 continue; 254 } 255 if (Name[i] != '_' && !isalnum(Name[i]) && 256 (!IsExpression || (Name[i] != '+' && Name[i] != '-'))) { 257 SM.PrintMessage(SMLoc::getFromPointer(Name.data()+i), 258 SourceMgr::DK_Error, "invalid name in named regex"); 259 return true; 260 } 261 } 262 263 // Name can't start with a digit. 264 if (isdigit(static_cast<unsigned char>(Name[0]))) { 265 SM.PrintMessage(SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error, 266 "invalid name in named regex"); 267 return true; 268 } 269 270 // Handle [[foo]]. 271 if (NameEnd == StringRef::npos) { 272 // Handle variables that were defined earlier on the same line by 273 // emitting a backreference. 274 if (VariableDefs.find(Name) != VariableDefs.end()) { 275 unsigned VarParenNum = VariableDefs[Name]; 276 if (VarParenNum < 1 || VarParenNum > 9) { 277 SM.PrintMessage(SMLoc::getFromPointer(Name.data()), 278 SourceMgr::DK_Error, 279 "Can't back-reference more than 9 variables"); 280 return true; 281 } 282 AddBackrefToRegEx(VarParenNum); 283 } else { 284 VariableUses.push_back(std::make_pair(Name, RegExStr.size())); 285 } 286 continue; 287 } 288 289 // Handle [[foo:.*]]. 290 VariableDefs[Name] = CurParen; 291 RegExStr += '('; 292 ++CurParen; 293 294 if (AddRegExToRegEx(MatchStr.substr(NameEnd+1), CurParen, SM)) 295 return true; 296 297 RegExStr += ')'; 298 } 299 300 // Handle fixed string matches. 301 // Find the end, which is the start of the next regex. 302 size_t FixedMatchEnd = PatternStr.find("{{"); 303 FixedMatchEnd = std::min(FixedMatchEnd, PatternStr.find("[[")); 304 AddFixedStringToRegEx(PatternStr.substr(0, FixedMatchEnd), RegExStr); 305 PatternStr = PatternStr.substr(FixedMatchEnd); 306 } 307 308 return false; 309} 310 311void Pattern::AddFixedStringToRegEx(StringRef FixedStr, std::string &TheStr) { 312 // Add the characters from FixedStr to the regex, escaping as needed. This 313 // avoids "leaning toothpicks" in common patterns. 314 for (unsigned i = 0, e = FixedStr.size(); i != e; ++i) { 315 switch (FixedStr[i]) { 316 // These are the special characters matched in "p_ere_exp". 317 case '(': 318 case ')': 319 case '^': 320 case '$': 321 case '|': 322 case '*': 323 case '+': 324 case '?': 325 case '.': 326 case '[': 327 case '\\': 328 case '{': 329 TheStr += '\\'; 330 // FALL THROUGH. 331 default: 332 TheStr += FixedStr[i]; 333 break; 334 } 335 } 336} 337 338bool Pattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen, 339 SourceMgr &SM) { 340 Regex R(RS); 341 std::string Error; 342 if (!R.isValid(Error)) { 343 SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error, 344 "invalid regex: " + Error); 345 return true; 346 } 347 348 RegExStr += RS.str(); 349 CurParen += R.getNumMatches(); 350 return false; 351} 352 353void Pattern::AddBackrefToRegEx(unsigned BackrefNum) { 354 assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number"); 355 std::string Backref = std::string("\\") + 356 std::string(1, '0' + BackrefNum); 357 RegExStr += Backref; 358} 359 360bool Pattern::EvaluateExpression(StringRef Expr, std::string &Value) const { 361 // The only supported expression is @LINE([\+-]\d+)? 362 if (!Expr.startswith("@LINE")) 363 return false; 364 Expr = Expr.substr(StringRef("@LINE").size()); 365 int Offset = 0; 366 if (!Expr.empty()) { 367 if (Expr[0] == '+') 368 Expr = Expr.substr(1); 369 else if (Expr[0] != '-') 370 return false; 371 if (Expr.getAsInteger(10, Offset)) 372 return false; 373 } 374 Value = llvm::itostr(LineNumber + Offset); 375 return true; 376} 377 378/// Match - Match the pattern string against the input buffer Buffer. This 379/// returns the position that is matched or npos if there is no match. If 380/// there is a match, the size of the matched string is returned in MatchLen. 381size_t Pattern::Match(StringRef Buffer, size_t &MatchLen, 382 StringMap<StringRef> &VariableTable) const { 383 // If this is the EOF pattern, match it immediately. 384 if (MatchEOF) { 385 MatchLen = 0; 386 return Buffer.size(); 387 } 388 389 // If this is a fixed string pattern, just match it now. 390 if (!FixedStr.empty()) { 391 MatchLen = FixedStr.size(); 392 return Buffer.find(FixedStr); 393 } 394 395 // Regex match. 396 397 // If there are variable uses, we need to create a temporary string with the 398 // actual value. 399 StringRef RegExToMatch = RegExStr; 400 std::string TmpStr; 401 if (!VariableUses.empty()) { 402 TmpStr = RegExStr; 403 404 unsigned InsertOffset = 0; 405 for (unsigned i = 0, e = VariableUses.size(); i != e; ++i) { 406 std::string Value; 407 408 if (VariableUses[i].first[0] == '@') { 409 if (!EvaluateExpression(VariableUses[i].first, Value)) 410 return StringRef::npos; 411 } else { 412 StringMap<StringRef>::iterator it = 413 VariableTable.find(VariableUses[i].first); 414 // If the variable is undefined, return an error. 415 if (it == VariableTable.end()) 416 return StringRef::npos; 417 418 // Look up the value and escape it so that we can plop it into the regex. 419 AddFixedStringToRegEx(it->second, Value); 420 } 421 422 // Plop it into the regex at the adjusted offset. 423 TmpStr.insert(TmpStr.begin()+VariableUses[i].second+InsertOffset, 424 Value.begin(), Value.end()); 425 InsertOffset += Value.size(); 426 } 427 428 // Match the newly constructed regex. 429 RegExToMatch = TmpStr; 430 } 431 432 433 SmallVector<StringRef, 4> MatchInfo; 434 if (!Regex(RegExToMatch, Regex::Newline).match(Buffer, &MatchInfo)) 435 return StringRef::npos; 436 437 // Successful regex match. 438 assert(!MatchInfo.empty() && "Didn't get any match"); 439 StringRef FullMatch = MatchInfo[0]; 440 441 // If this defines any variables, remember their values. 442 for (std::map<StringRef, unsigned>::const_iterator I = VariableDefs.begin(), 443 E = VariableDefs.end(); 444 I != E; ++I) { 445 assert(I->second < MatchInfo.size() && "Internal paren error"); 446 VariableTable[I->first] = MatchInfo[I->second]; 447 } 448 449 MatchLen = FullMatch.size(); 450 return FullMatch.data()-Buffer.data(); 451} 452 453unsigned Pattern::ComputeMatchDistance(StringRef Buffer, 454 const StringMap<StringRef> &VariableTable) const { 455 // Just compute the number of matching characters. For regular expressions, we 456 // just compare against the regex itself and hope for the best. 457 // 458 // FIXME: One easy improvement here is have the regex lib generate a single 459 // example regular expression which matches, and use that as the example 460 // string. 461 StringRef ExampleString(FixedStr); 462 if (ExampleString.empty()) 463 ExampleString = RegExStr; 464 465 // Only compare up to the first line in the buffer, or the string size. 466 StringRef BufferPrefix = Buffer.substr(0, ExampleString.size()); 467 BufferPrefix = BufferPrefix.split('\n').first; 468 return BufferPrefix.edit_distance(ExampleString); 469} 470 471void Pattern::PrintFailureInfo(const SourceMgr &SM, StringRef Buffer, 472 const StringMap<StringRef> &VariableTable) const{ 473 // If this was a regular expression using variables, print the current 474 // variable values. 475 if (!VariableUses.empty()) { 476 for (unsigned i = 0, e = VariableUses.size(); i != e; ++i) { 477 SmallString<256> Msg; 478 raw_svector_ostream OS(Msg); 479 StringRef Var = VariableUses[i].first; 480 if (Var[0] == '@') { 481 std::string Value; 482 if (EvaluateExpression(Var, Value)) { 483 OS << "with expression \""; 484 OS.write_escaped(Var) << "\" equal to \""; 485 OS.write_escaped(Value) << "\""; 486 } else { 487 OS << "uses incorrect expression \""; 488 OS.write_escaped(Var) << "\""; 489 } 490 } else { 491 StringMap<StringRef>::const_iterator it = VariableTable.find(Var); 492 493 // Check for undefined variable references. 494 if (it == VariableTable.end()) { 495 OS << "uses undefined variable \""; 496 OS.write_escaped(Var) << "\""; 497 } else { 498 OS << "with variable \""; 499 OS.write_escaped(Var) << "\" equal to \""; 500 OS.write_escaped(it->second) << "\""; 501 } 502 } 503 504 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note, 505 OS.str()); 506 } 507 } 508 509 // Attempt to find the closest/best fuzzy match. Usually an error happens 510 // because some string in the output didn't exactly match. In these cases, we 511 // would like to show the user a best guess at what "should have" matched, to 512 // save them having to actually check the input manually. 513 size_t NumLinesForward = 0; 514 size_t Best = StringRef::npos; 515 double BestQuality = 0; 516 517 // Use an arbitrary 4k limit on how far we will search. 518 for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) { 519 if (Buffer[i] == '\n') 520 ++NumLinesForward; 521 522 // Patterns have leading whitespace stripped, so skip whitespace when 523 // looking for something which looks like a pattern. 524 if (Buffer[i] == ' ' || Buffer[i] == '\t') 525 continue; 526 527 // Compute the "quality" of this match as an arbitrary combination of the 528 // match distance and the number of lines skipped to get to this match. 529 unsigned Distance = ComputeMatchDistance(Buffer.substr(i), VariableTable); 530 double Quality = Distance + (NumLinesForward / 100.); 531 532 if (Quality < BestQuality || Best == StringRef::npos) { 533 Best = i; 534 BestQuality = Quality; 535 } 536 } 537 538 // Print the "possible intended match here" line if we found something 539 // reasonable and not equal to what we showed in the "scanning from here" 540 // line. 541 if (Best && Best != StringRef::npos && BestQuality < 50) { 542 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + Best), 543 SourceMgr::DK_Note, "possible intended match here"); 544 545 // FIXME: If we wanted to be really friendly we would show why the match 546 // failed, as it can be hard to spot simple one character differences. 547 } 548} 549 550size_t Pattern::FindRegexVarEnd(StringRef Str) { 551 // Offset keeps track of the current offset within the input Str 552 size_t Offset = 0; 553 // [...] Nesting depth 554 size_t BracketDepth = 0; 555 556 while (!Str.empty()) { 557 if (Str.startswith("]]") && BracketDepth == 0) 558 return Offset; 559 if (Str[0] == '\\') { 560 // Backslash escapes the next char within regexes, so skip them both. 561 Str = Str.substr(2); 562 Offset += 2; 563 } else { 564 switch (Str[0]) { 565 default: 566 break; 567 case '[': 568 BracketDepth++; 569 break; 570 case ']': 571 assert(BracketDepth > 0 && "Invalid regex"); 572 BracketDepth--; 573 break; 574 } 575 Str = Str.substr(1); 576 Offset++; 577 } 578 } 579 580 return StringRef::npos; 581} 582 583 584//===----------------------------------------------------------------------===// 585// Check Strings. 586//===----------------------------------------------------------------------===// 587 588/// CheckString - This is a check that we found in the input file. 589struct CheckString { 590 /// Pat - The pattern to match. 591 Pattern Pat; 592 593 /// Loc - The location in the match file that the check string was specified. 594 SMLoc Loc; 595 596 /// IsCheckNext - This is true if this is a CHECK-NEXT: directive (as opposed 597 /// to a CHECK: directive. 598 bool IsCheckNext; 599 600 /// IsCheckLabel - This is true if this is a CHECK-LABEL: directive (as 601 /// opposed to a CHECK: directive. 602 bool IsCheckLabel; 603 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 606 /// file). 607 std::vector<Pattern> DagNotStrings; 608 609 CheckString(const Pattern &P, SMLoc L, bool isCheckNext, bool isCheckLabel) 610 : Pat(P), Loc(L), IsCheckNext(isCheckNext), IsCheckLabel(isCheckLabel) {} 611 612 /// Check - Match check string and its "not strings" and/or "dag strings". 613 size_t Check(const SourceMgr &SM, StringRef Buffer, bool IsLabel, 614 size_t &MatchLen, StringMap<StringRef> &VariableTable) const; 615 616 /// CheckNext - Verify there is a single line in the given buffer. 617 bool CheckNext(const SourceMgr &SM, StringRef Buffer) const; 618 619 /// CheckNot - Verify there's no "not strings" in the given buffer. 620 bool CheckNot(const SourceMgr &SM, StringRef Buffer, 621 const std::vector<const Pattern *> &NotStrings, 622 StringMap<StringRef> &VariableTable) const; 623 624 /// CheckDag - Match "dag strings" and their mixed "not strings". 625 size_t CheckDag(const SourceMgr &SM, StringRef Buffer, 626 std::vector<const Pattern *> &NotStrings, 627 StringMap<StringRef> &VariableTable) const; 628}; 629 630/// Canonicalize whitespaces in the input file. Line endings are replaced 631/// with UNIX-style '\n'. 632/// 633/// \param PreserveHorizontal Don't squash consecutive horizontal whitespace 634/// characters to a single space. 635static MemoryBuffer *CanonicalizeInputFile(MemoryBuffer *MB, 636 bool PreserveHorizontal) { 637 SmallString<128> NewFile; 638 NewFile.reserve(MB->getBufferSize()); 639 640 for (const char *Ptr = MB->getBufferStart(), *End = MB->getBufferEnd(); 641 Ptr != End; ++Ptr) { 642 // Eliminate trailing dosish \r. 643 if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') { 644 continue; 645 } 646 647 // If current char is not a horizontal whitespace or if horizontal 648 // whitespace canonicalization is disabled, dump it to output as is. 649 if (PreserveHorizontal || (*Ptr != ' ' && *Ptr != '\t')) { 650 NewFile.push_back(*Ptr); 651 continue; 652 } 653 654 // Otherwise, add one space and advance over neighboring space. 655 NewFile.push_back(' '); 656 while (Ptr+1 != End && 657 (Ptr[1] == ' ' || Ptr[1] == '\t')) 658 ++Ptr; 659 } 660 661 // Free the old buffer and return a new one. 662 MemoryBuffer *MB2 = 663 MemoryBuffer::getMemBufferCopy(NewFile.str(), MB->getBufferIdentifier()); 664 665 delete MB; 666 return MB2; 667} 668 669 670/// ReadCheckFile - Read the check file, which specifies the sequence of 671/// expected strings. The strings are added to the CheckStrings vector. 672/// Returns true in case of an error, false otherwise. 673static bool ReadCheckFile(SourceMgr &SM, 674 std::vector<CheckString> &CheckStrings) { 675 OwningPtr<MemoryBuffer> File; 676 if (error_code ec = 677 MemoryBuffer::getFileOrSTDIN(CheckFilename, File)) { 678 errs() << "Could not open check file '" << CheckFilename << "': " 679 << ec.message() << '\n'; 680 return true; 681 } 682 683 // If we want to canonicalize whitespace, strip excess whitespace from the 684 // buffer containing the CHECK lines. Remove DOS style line endings. 685 MemoryBuffer *F = 686 CanonicalizeInputFile(File.take(), NoCanonicalizeWhiteSpace); 687 688 SM.AddNewSourceBuffer(F, SMLoc()); 689 690 // Find all instances of CheckPrefix followed by : in the file. 691 StringRef Buffer = F->getBuffer(); 692 std::vector<Pattern> DagNotMatches; 693 694 // LineNumber keeps track of the line on which CheckPrefix instances are 695 // found. 696 unsigned LineNumber = 1; 697 698 while (1) { 699 // See if Prefix occurs in the memory buffer. 700 size_t PrefixLoc = Buffer.find(CheckPrefix); 701 // If we didn't find a match, we're done. 702 if (PrefixLoc == StringRef::npos) 703 break; 704 705 LineNumber += Buffer.substr(0, PrefixLoc).count('\n'); 706 707 // Keep the charcter before our prefix so we can validate that we have 708 // found our prefix, and account for cases when PrefixLoc is 0. 709 Buffer = Buffer.substr(std::min(PrefixLoc-1, PrefixLoc)); 710 711 const char *CheckPrefixStart = Buffer.data() + (PrefixLoc == 0 ? 0 : 1); 712 713 // When we find a check prefix, keep track of whether we find CHECK: or 714 // CHECK-NEXT: 715 bool IsCheckNext = false, IsCheckNot = false, IsCheckDag = false, 716 IsCheckLabel = false; 717 718 // Make sure we have actually found our prefix, and not a word containing 719 // our prefix. 720 if (PrefixLoc != 0 && (isalnum(Buffer[0]) || 721 Buffer[0] == '-' || 722 Buffer[0] == '_')) { 723 Buffer = Buffer.substr(CheckPrefix.size()); 724 continue; 725 } 726 727 // Verify that the : is present after the prefix. 728 if (Buffer[CheckPrefix.size()] == ':') { 729 Buffer = Buffer.substr(CheckPrefix.size()+1); 730 } else if (Buffer.size() > CheckPrefix.size()+6 && 731 memcmp(Buffer.data()+CheckPrefix.size(), "-NEXT:", 6) == 0) { 732 Buffer = Buffer.substr(CheckPrefix.size()+6); 733 IsCheckNext = true; 734 } else if (Buffer.size() > CheckPrefix.size()+5 && 735 memcmp(Buffer.data()+CheckPrefix.size(), "-NOT:", 5) == 0) { 736 Buffer = Buffer.substr(CheckPrefix.size()+5); 737 IsCheckNot = true; 738 } else if (Buffer.size() > CheckPrefix.size()+5 && 739 memcmp(Buffer.data()+CheckPrefix.size(), "-DAG:", 5) == 0) { 740 Buffer = Buffer.substr(CheckPrefix.size()+5); 741 IsCheckDag = true; 742 } else if (Buffer.size() > CheckPrefix.size()+7 && 743 memcmp(Buffer.data()+CheckPrefix.size(), "-LABEL:", 7) == 0) { 744 Buffer = Buffer.substr(CheckPrefix.size()+7); 745 IsCheckLabel = true; 746 } else { 747 Buffer = Buffer.substr(1); 748 continue; 749 } 750 751 // Okay, we found the prefix, yay. Remember the rest of the line, but 752 // ignore leading and trailing whitespace. 753 Buffer = Buffer.substr(Buffer.find_first_not_of(" \t")); 754 755 // Scan ahead to the end of line. 756 size_t EOL = Buffer.find_first_of("\n\r"); 757 758 // Remember the location of the start of the pattern, for diagnostics. 759 SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data()); 760 761 // Parse the pattern. 762 Pattern P; 763 if (P.ParsePattern(Buffer.substr(0, EOL), SM, LineNumber)) 764 return true; 765 766 // Verify that CHECK-LABEL lines do not define or use variables 767 if (IsCheckLabel && P.hasVariable()) { 768 SM.PrintMessage(SMLoc::getFromPointer(CheckPrefixStart), 769 SourceMgr::DK_Error, 770 "found '"+CheckPrefix+"-LABEL:' with variable definition" 771 " or use'"); 772 return true; 773 } 774 775 P.setMatchNot(IsCheckNot); 776 P.setMatchDag(IsCheckDag); 777 778 Buffer = Buffer.substr(EOL); 779 780 // Verify that CHECK-NEXT lines have at least one CHECK line before them. 781 if (IsCheckNext && CheckStrings.empty()) { 782 SM.PrintMessage(SMLoc::getFromPointer(CheckPrefixStart), 783 SourceMgr::DK_Error, 784 "found '"+CheckPrefix+"-NEXT:' without previous '"+ 785 CheckPrefix+ ": line"); 786 return true; 787 } 788 789 // Handle CHECK-DAG/-NOT. 790 if (IsCheckDag || IsCheckNot) { 791 DagNotMatches.push_back(P); 792 continue; 793 } 794 795 // Okay, add the string we captured to the output vector and move on. 796 CheckStrings.push_back(CheckString(P, 797 PatternLoc, 798 IsCheckNext, 799 IsCheckLabel)); 800 std::swap(DagNotMatches, CheckStrings.back().DagNotStrings); 801 } 802 803 // Add an EOF pattern for any trailing CHECK-DAG/-NOTs. 804 if (!DagNotMatches.empty()) { 805 CheckStrings.push_back(CheckString(Pattern(true), 806 SMLoc::getFromPointer(Buffer.data()), 807 false, 808 false)); 809 std::swap(DagNotMatches, CheckStrings.back().DagNotStrings); 810 } 811 812 if (CheckStrings.empty()) { 813 errs() << "error: no check strings found with prefix '" << CheckPrefix 814 << ":'\n"; 815 return true; 816 } 817 818 return false; 819} 820 821static void PrintCheckFailed(const SourceMgr &SM, const SMLoc &Loc, 822 const Pattern &Pat, StringRef Buffer, 823 StringMap<StringRef> &VariableTable) { 824 // Otherwise, we have an error, emit an error message. 825 SM.PrintMessage(Loc, SourceMgr::DK_Error, 826 "expected string not found in input"); 827 828 // Print the "scanning from here" line. If the current position is at the 829 // end of a line, advance to the start of the next line. 830 Buffer = Buffer.substr(Buffer.find_first_not_of(" \t\n\r")); 831 832 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note, 833 "scanning from here"); 834 835 // Allow the pattern to print additional information if desired. 836 Pat.PrintFailureInfo(SM, Buffer, VariableTable); 837} 838 839static void PrintCheckFailed(const SourceMgr &SM, const CheckString &CheckStr, 840 StringRef Buffer, 841 StringMap<StringRef> &VariableTable) { 842 PrintCheckFailed(SM, CheckStr.Loc, CheckStr.Pat, Buffer, VariableTable); 843} 844 845/// CountNumNewlinesBetween - Count the number of newlines in the specified 846/// range. 847static unsigned CountNumNewlinesBetween(StringRef Range) { 848 unsigned NumNewLines = 0; 849 while (1) { 850 // Scan for newline. 851 Range = Range.substr(Range.find_first_of("\n\r")); 852 if (Range.empty()) return NumNewLines; 853 854 ++NumNewLines; 855 856 // Handle \n\r and \r\n as a single newline. 857 if (Range.size() > 1 && 858 (Range[1] == '\n' || Range[1] == '\r') && 859 (Range[0] != Range[1])) 860 Range = Range.substr(1); 861 Range = Range.substr(1); 862 } 863} 864 865size_t CheckString::Check(const SourceMgr &SM, StringRef Buffer, 866 bool IsLabel, size_t &MatchLen, 867 StringMap<StringRef> &VariableTable) const { 868 size_t LastPos = 0; 869 std::vector<const Pattern *> NotStrings; 870 871 if (!IsLabel) { 872 // Match "dag strings" (with mixed "not strings" if any). 873 LastPos = CheckDag(SM, Buffer, NotStrings, VariableTable); 874 if (LastPos == StringRef::npos) 875 return StringRef::npos; 876 } 877 878 // Match itself from the last position after matching CHECK-DAG. 879 StringRef MatchBuffer = Buffer.substr(LastPos); 880 size_t MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable); 881 if (MatchPos == StringRef::npos) { 882 PrintCheckFailed(SM, *this, MatchBuffer, VariableTable); 883 return StringRef::npos; 884 } 885 MatchPos += LastPos; 886 887 if (!IsLabel) { 888 StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos); 889 890 // If this check is a "CHECK-NEXT", verify that the previous match was on 891 // the previous line (i.e. that there is one newline between them). 892 if (CheckNext(SM, SkippedRegion)) 893 return StringRef::npos; 894 895 // If this match had "not strings", verify that they don't exist in the 896 // skipped region. 897 if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable)) 898 return StringRef::npos; 899 } 900 901 return MatchPos; 902} 903 904bool CheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const { 905 if (!IsCheckNext) 906 return false; 907 908 // Count the number of newlines between the previous match and this one. 909 assert(Buffer.data() != 910 SM.getMemoryBuffer( 911 SM.FindBufferContainingLoc( 912 SMLoc::getFromPointer(Buffer.data())))->getBufferStart() && 913 "CHECK-NEXT can't be the first check in a file"); 914 915 unsigned NumNewLines = CountNumNewlinesBetween(Buffer); 916 917 if (NumNewLines == 0) { 918 SM.PrintMessage(Loc, SourceMgr::DK_Error, CheckPrefix+ 919 "-NEXT: is on the same line as previous match"); 920 SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), 921 SourceMgr::DK_Note, "'next' match was here"); 922 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note, 923 "previous match ended here"); 924 return true; 925 } 926 927 if (NumNewLines != 1) { 928 SM.PrintMessage(Loc, SourceMgr::DK_Error, CheckPrefix+ 929 "-NEXT: is not on the line after the previous match"); 930 SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), 931 SourceMgr::DK_Note, "'next' match was here"); 932 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note, 933 "previous match ended here"); 934 return true; 935 } 936 937 return false; 938} 939 940bool CheckString::CheckNot(const SourceMgr &SM, StringRef Buffer, 941 const std::vector<const Pattern *> &NotStrings, 942 StringMap<StringRef> &VariableTable) const { 943 for (unsigned ChunkNo = 0, e = NotStrings.size(); 944 ChunkNo != e; ++ChunkNo) { 945 const Pattern *Pat = NotStrings[ChunkNo]; 946 assert(Pat->getMatchNot() && "Expect CHECK-NOT!"); 947 948 size_t MatchLen = 0; 949 size_t Pos = Pat->Match(Buffer, MatchLen, VariableTable); 950 951 if (Pos == StringRef::npos) continue; 952 953 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()+Pos), 954 SourceMgr::DK_Error, 955 CheckPrefix+"-NOT: string occurred!"); 956 SM.PrintMessage(Pat->getLoc(), SourceMgr::DK_Note, 957 CheckPrefix+"-NOT: pattern specified here"); 958 return true; 959 } 960 961 return false; 962} 963 964size_t CheckString::CheckDag(const SourceMgr &SM, StringRef Buffer, 965 std::vector<const Pattern *> &NotStrings, 966 StringMap<StringRef> &VariableTable) const { 967 if (DagNotStrings.empty()) 968 return 0; 969 970 size_t LastPos = 0; 971 size_t StartPos = LastPos; 972 973 for (unsigned ChunkNo = 0, e = DagNotStrings.size(); 974 ChunkNo != e; ++ChunkNo) { 975 const Pattern &Pat = DagNotStrings[ChunkNo]; 976 977 assert((Pat.getMatchDag() ^ Pat.getMatchNot()) && 978 "Invalid CHECK-DAG or CHECK-NOT!"); 979 980 if (Pat.getMatchNot()) { 981 NotStrings.push_back(&Pat); 982 continue; 983 } 984 985 assert(Pat.getMatchDag() && "Expect CHECK-DAG!"); 986 987 size_t MatchLen = 0, MatchPos; 988 989 // CHECK-DAG always matches from the start. 990 StringRef MatchBuffer = Buffer.substr(StartPos); 991 MatchPos = Pat.Match(MatchBuffer, MatchLen, VariableTable); 992 // With a group of CHECK-DAGs, a single mismatching means the match on 993 // that group of CHECK-DAGs fails immediately. 994 if (MatchPos == StringRef::npos) { 995 PrintCheckFailed(SM, Pat.getLoc(), Pat, MatchBuffer, VariableTable); 996 return StringRef::npos; 997 } 998 // Re-calc it as the offset relative to the start of the original string. 999 MatchPos += StartPos; 1000 1001 if (!NotStrings.empty()) { 1002 if (MatchPos < LastPos) { 1003 // Reordered? 1004 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + MatchPos), 1005 SourceMgr::DK_Error, 1006 CheckPrefix+"-DAG: found a match of CHECK-DAG" 1007 " reordering across a CHECK-NOT"); 1008 SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + LastPos), 1009 SourceMgr::DK_Note, 1010 CheckPrefix+"-DAG: the farthest match of CHECK-DAG" 1011 " is found here"); 1012 SM.PrintMessage(NotStrings[0]->getLoc(), SourceMgr::DK_Note, 1013 CheckPrefix+"-NOT: the crossed pattern specified" 1014 " here"); 1015 SM.PrintMessage(Pat.getLoc(), SourceMgr::DK_Note, 1016 CheckPrefix+"-DAG: the reordered pattern specified" 1017 " here"); 1018 return StringRef::npos; 1019 } 1020 // All subsequent CHECK-DAGs should be matched from the farthest 1021 // position of all precedent CHECK-DAGs (including this one.) 1022 StartPos = LastPos; 1023 // If there's CHECK-NOTs between two CHECK-DAGs or from CHECK to 1024 // CHECK-DAG, verify that there's no 'not' strings occurred in that 1025 // region. 1026 StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos); 1027 if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable)) 1028 return StringRef::npos; 1029 // Clear "not strings". 1030 NotStrings.clear(); 1031 } 1032 1033 // Update the last position with CHECK-DAG matches. 1034 LastPos = std::max(MatchPos + MatchLen, LastPos); 1035 } 1036 1037 return LastPos; 1038} 1039 1040bool ValidateCheckPrefix() { 1041 // The check prefix must contain only alphanumeric, hyphens and underscores. 1042 Regex prefixValidator("^[a-zA-Z0-9_-]*$"); 1043 return prefixValidator.match(CheckPrefix); 1044} 1045 1046int main(int argc, char **argv) { 1047 sys::PrintStackTraceOnErrorSignal(); 1048 PrettyStackTraceProgram X(argc, argv); 1049 cl::ParseCommandLineOptions(argc, argv); 1050 1051 if (!ValidateCheckPrefix()) { 1052 errs() << "Supplied check-prefix is invalid! Prefixes must start with a " 1053 "letter and contain only alphanumeric characters, hyphens and " 1054 "underscores\n"; 1055 return 2; 1056 } 1057 1058 SourceMgr SM; 1059 1060 // Read the expected strings from the check file. 1061 std::vector<CheckString> CheckStrings; 1062 if (ReadCheckFile(SM, CheckStrings)) 1063 return 2; 1064 1065 // Open the file to check and add it to SourceMgr. 1066 OwningPtr<MemoryBuffer> File; 1067 if (error_code ec = 1068 MemoryBuffer::getFileOrSTDIN(InputFilename, File)) { 1069 errs() << "Could not open input file '" << InputFilename << "': " 1070 << ec.message() << '\n'; 1071 return 2; 1072 } 1073 1074 if (File->getBufferSize() == 0) { 1075 errs() << "FileCheck error: '" << InputFilename << "' is empty.\n"; 1076 return 2; 1077 } 1078 1079 // Remove duplicate spaces in the input file if requested. 1080 // Remove DOS style line endings. 1081 MemoryBuffer *F = 1082 CanonicalizeInputFile(File.take(), NoCanonicalizeWhiteSpace); 1083 1084 SM.AddNewSourceBuffer(F, SMLoc()); 1085 1086 /// VariableTable - This holds all the current filecheck variables. 1087 StringMap<StringRef> VariableTable; 1088 1089 // Check that we have all of the expected strings, in order, in the input 1090 // file. 1091 StringRef Buffer = F->getBuffer(); 1092 1093 bool hasError = false; 1094 1095 unsigned i = 0, j = 0, e = CheckStrings.size(); 1096 1097 while (true) { 1098 StringRef CheckRegion; 1099 if (j == e) { 1100 CheckRegion = Buffer; 1101 } else { 1102 const CheckString &CheckLabelStr = CheckStrings[j]; 1103 if (!CheckLabelStr.IsCheckLabel) { 1104 ++j; 1105 continue; 1106 } 1107 1108 // Scan to next CHECK-LABEL match, ignoring CHECK-NOT and CHECK-DAG 1109 size_t MatchLabelLen = 0; 1110 size_t MatchLabelPos = CheckLabelStr.Check(SM, Buffer, true, 1111 MatchLabelLen, VariableTable); 1112 if (MatchLabelPos == StringRef::npos) { 1113 hasError = true; 1114 break; 1115 } 1116 1117 CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen); 1118 Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen); 1119 ++j; 1120 } 1121 1122 for ( ; i != j; ++i) { 1123 const CheckString &CheckStr = CheckStrings[i]; 1124 1125 // Check each string within the scanned region, including a second check 1126 // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG) 1127 size_t MatchLen = 0; 1128 size_t MatchPos = CheckStr.Check(SM, CheckRegion, false, MatchLen, 1129 VariableTable); 1130 1131 if (MatchPos == StringRef::npos) { 1132 hasError = true; 1133 i = j; 1134 break; 1135 } 1136 1137 CheckRegion = CheckRegion.substr(MatchPos + MatchLen); 1138 } 1139 1140 if (j == e) 1141 break; 1142 } 1143 1144 return hasError ? 1 : 0; 1145} 1146