FileCheck.cpp 75 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009
  1. //===- FileCheck.cpp - Check that File's Contents match what is expected --===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. //
  9. // FileCheck does a line-by line check of a file that validates whether it
  10. // contains the expected content. This is useful for regression tests etc.
  11. //
  12. // This file implements most of the API that will be used by the FileCheck utility
  13. // as well as various unittests.
  14. //===----------------------------------------------------------------------===//
  15. #include "llvm/Support/FileCheck.h"
  16. #include "llvm/ADT/StringSet.h"
  17. #include "llvm/Support/FormatVariadic.h"
  18. #include <cstdint>
  19. #include <list>
  20. #include <map>
  21. #include <tuple>
  22. #include <utility>
  23. using namespace llvm;
  24. bool FileCheckNumericVariable::isValueKnownAtMatchTime() const {
  25. if (Value)
  26. return true;
  27. return ExpressionAST != nullptr;
  28. }
  29. void FileCheckNumericVariable::setValue(uint64_t NewValue) {
  30. if (ExpressionAST != nullptr) {
  31. // Caller is expected to call setValue only if substitution was successful.
  32. assert(NewValue == cantFail(ExpressionAST->eval(),
  33. "Failed to evaluate associated expression when "
  34. "sanity checking value") &&
  35. "Value being set to different from variable evaluation");
  36. }
  37. Value = NewValue;
  38. // Clear pointer to AST to ensure it is not used after the numeric
  39. // substitution defining this variable is processed since it's the
  40. // substitution that owns the pointer.
  41. ExpressionAST = nullptr;
  42. }
  43. Expected<uint64_t> FileCheckNumericVariableUse::eval() const {
  44. Optional<uint64_t> Value = NumericVariable->getValue();
  45. if (Value)
  46. return *Value;
  47. FileCheckExpressionAST *ExpressionAST = NumericVariable->getExpressionAST();
  48. if (!ExpressionAST)
  49. return make_error<FileCheckUndefVarError>(Name);
  50. return ExpressionAST->eval();
  51. }
  52. Expected<uint64_t> FileCheckASTBinop::eval() const {
  53. Expected<uint64_t> LeftOp = LeftOperand->eval();
  54. Expected<uint64_t> RightOp = RightOperand->eval();
  55. // Bubble up any error (e.g. undefined variables) in the recursive
  56. // evaluation.
  57. if (!LeftOp || !RightOp) {
  58. Error Err = Error::success();
  59. if (!LeftOp)
  60. Err = joinErrors(std::move(Err), LeftOp.takeError());
  61. if (!RightOp)
  62. Err = joinErrors(std::move(Err), RightOp.takeError());
  63. return std::move(Err);
  64. }
  65. return EvalBinop(*LeftOp, *RightOp);
  66. }
  67. Expected<std::string> FileCheckNumericSubstitution::getResult() const {
  68. Expected<uint64_t> EvaluatedValue = ExpressionAST->eval();
  69. if (!EvaluatedValue)
  70. return EvaluatedValue.takeError();
  71. return utostr(*EvaluatedValue);
  72. }
  73. Expected<std::string> FileCheckStringSubstitution::getResult() const {
  74. // Look up the value and escape it so that we can put it into the regex.
  75. Expected<StringRef> VarVal = Context->getPatternVarValue(FromStr);
  76. if (!VarVal)
  77. return VarVal.takeError();
  78. return Regex::escape(*VarVal);
  79. }
  80. bool FileCheckPattern::isValidVarNameStart(char C) {
  81. return C == '_' || isalpha(C);
  82. }
  83. Expected<FileCheckPattern::VariableProperties>
  84. FileCheckPattern::parseVariable(StringRef &Str, const SourceMgr &SM) {
  85. if (Str.empty())
  86. return FileCheckErrorDiagnostic::get(SM, Str, "empty variable name");
  87. bool ParsedOneChar = false;
  88. unsigned I = 0;
  89. bool IsPseudo = Str[0] == '@';
  90. // Global vars start with '$'.
  91. if (Str[0] == '$' || IsPseudo)
  92. ++I;
  93. for (unsigned E = Str.size(); I != E; ++I) {
  94. if (!ParsedOneChar && !isValidVarNameStart(Str[I]))
  95. return FileCheckErrorDiagnostic::get(SM, Str, "invalid variable name");
  96. // Variable names are composed of alphanumeric characters and underscores.
  97. if (Str[I] != '_' && !isalnum(Str[I]))
  98. break;
  99. ParsedOneChar = true;
  100. }
  101. StringRef Name = Str.take_front(I);
  102. Str = Str.substr(I);
  103. return VariableProperties {Name, IsPseudo};
  104. }
  105. // StringRef holding all characters considered as horizontal whitespaces by
  106. // FileCheck input canonicalization.
  107. StringRef SpaceChars = " \t";
  108. // Parsing helper function that strips the first character in S and returns it.
  109. static char popFront(StringRef &S) {
  110. char C = S.front();
  111. S = S.drop_front();
  112. return C;
  113. }
  114. char FileCheckUndefVarError::ID = 0;
  115. char FileCheckErrorDiagnostic::ID = 0;
  116. char FileCheckNotFoundError::ID = 0;
  117. Expected<FileCheckNumericVariable *>
  118. FileCheckPattern::parseNumericVariableDefinition(
  119. StringRef &Expr, FileCheckPatternContext *Context,
  120. Optional<size_t> LineNumber, FileCheckExpressionAST *ExpressionAST,
  121. const SourceMgr &SM) {
  122. Expected<VariableProperties> ParseVarResult = parseVariable(Expr, SM);
  123. if (!ParseVarResult)
  124. return ParseVarResult.takeError();
  125. StringRef Name = ParseVarResult->Name;
  126. if (ParseVarResult->IsPseudo)
  127. return FileCheckErrorDiagnostic::get(
  128. SM, Name, "definition of pseudo numeric variable unsupported");
  129. // Detect collisions between string and numeric variables when the latter
  130. // is created later than the former.
  131. if (Context->DefinedVariableTable.find(Name) !=
  132. Context->DefinedVariableTable.end())
  133. return FileCheckErrorDiagnostic::get(
  134. SM, Name, "string variable with name '" + Name + "' already exists");
  135. Expr = Expr.ltrim(SpaceChars);
  136. if (!Expr.empty())
  137. return FileCheckErrorDiagnostic::get(
  138. SM, Expr, "unexpected characters after numeric variable name");
  139. FileCheckNumericVariable *DefinedNumericVariable;
  140. auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
  141. if (VarTableIter != Context->GlobalNumericVariableTable.end())
  142. DefinedNumericVariable = VarTableIter->second;
  143. else
  144. DefinedNumericVariable =
  145. Context->makeNumericVariable(Name, LineNumber, ExpressionAST);
  146. return DefinedNumericVariable;
  147. }
  148. Expected<std::unique_ptr<FileCheckNumericVariableUse>>
  149. FileCheckPattern::parseNumericVariableUse(StringRef Name, bool IsPseudo,
  150. Optional<size_t> LineNumber,
  151. FileCheckPatternContext *Context,
  152. const SourceMgr &SM) {
  153. if (IsPseudo && !Name.equals("@LINE"))
  154. return FileCheckErrorDiagnostic::get(
  155. SM, Name, "invalid pseudo numeric variable '" + Name + "'");
  156. // Numeric variable definitions and uses are parsed in the order in which
  157. // they appear in the CHECK patterns. For each definition, the pointer to the
  158. // class instance of the corresponding numeric variable definition is stored
  159. // in GlobalNumericVariableTable in parsePattern. Therefore, if the pointer
  160. // we get below is null, it means no such variable was defined before. When
  161. // that happens, we create a dummy variable so that parsing can continue. All
  162. // uses of undefined variables, whether string or numeric, are then diagnosed
  163. // in printSubstitutions() after failing to match.
  164. auto VarTableIter = Context->GlobalNumericVariableTable.find(Name);
  165. FileCheckNumericVariable *NumericVariable;
  166. if (VarTableIter != Context->GlobalNumericVariableTable.end())
  167. NumericVariable = VarTableIter->second;
  168. else {
  169. NumericVariable = Context->makeNumericVariable(Name);
  170. Context->GlobalNumericVariableTable[Name] = NumericVariable;
  171. }
  172. Optional<size_t> DefLineNumber = NumericVariable->getDefLineNumber();
  173. if (DefLineNumber && LineNumber && *DefLineNumber == *LineNumber &&
  174. !NumericVariable->isValueKnownAtMatchTime())
  175. return FileCheckErrorDiagnostic::get(
  176. SM, Name,
  177. "numeric variable '" + Name +
  178. "' defined from input on the same line as used");
  179. return llvm::make_unique<FileCheckNumericVariableUse>(Name, NumericVariable);
  180. }
  181. Expected<std::unique_ptr<FileCheckExpressionAST>>
  182. FileCheckPattern::parseNumericOperand(StringRef &Expr, AllowedOperand AO,
  183. Optional<size_t> LineNumber,
  184. FileCheckPatternContext *Context,
  185. const SourceMgr &SM) {
  186. if (AO == AllowedOperand::LineVar || AO == AllowedOperand::Any) {
  187. // Try to parse as a numeric variable use.
  188. Expected<FileCheckPattern::VariableProperties> ParseVarResult =
  189. parseVariable(Expr, SM);
  190. if (ParseVarResult)
  191. return parseNumericVariableUse(ParseVarResult->Name,
  192. ParseVarResult->IsPseudo, LineNumber,
  193. Context, SM);
  194. if (AO == AllowedOperand::LineVar)
  195. return ParseVarResult.takeError();
  196. // Ignore the error and retry parsing as a literal.
  197. consumeError(ParseVarResult.takeError());
  198. }
  199. // Otherwise, parse it as a literal.
  200. uint64_t LiteralValue;
  201. if (!Expr.consumeInteger(/*Radix=*/10, LiteralValue))
  202. return llvm::make_unique<FileCheckExpressionLiteral>(LiteralValue);
  203. return FileCheckErrorDiagnostic::get(SM, Expr,
  204. "invalid operand format '" + Expr + "'");
  205. }
  206. static uint64_t add(uint64_t LeftOp, uint64_t RightOp) {
  207. return LeftOp + RightOp;
  208. }
  209. static uint64_t sub(uint64_t LeftOp, uint64_t RightOp) {
  210. return LeftOp - RightOp;
  211. }
  212. Expected<std::unique_ptr<FileCheckExpressionAST>> FileCheckPattern::parseBinop(
  213. StringRef &Expr, std::unique_ptr<FileCheckExpressionAST> LeftOp,
  214. bool IsLegacyLineExpr, Optional<size_t> LineNumber,
  215. FileCheckPatternContext *Context, const SourceMgr &SM) {
  216. Expr = Expr.ltrim(SpaceChars);
  217. if (Expr.empty())
  218. return std::move(LeftOp);
  219. // Check if this is a supported operation and select a function to perform
  220. // it.
  221. SMLoc OpLoc = SMLoc::getFromPointer(Expr.data());
  222. char Operator = popFront(Expr);
  223. binop_eval_t EvalBinop;
  224. switch (Operator) {
  225. case '+':
  226. EvalBinop = add;
  227. break;
  228. case '-':
  229. EvalBinop = sub;
  230. break;
  231. default:
  232. return FileCheckErrorDiagnostic::get(
  233. SM, OpLoc, Twine("unsupported operation '") + Twine(Operator) + "'");
  234. }
  235. // Parse right operand.
  236. Expr = Expr.ltrim(SpaceChars);
  237. if (Expr.empty())
  238. return FileCheckErrorDiagnostic::get(SM, Expr,
  239. "missing operand in expression");
  240. // The second operand in a legacy @LINE expression is always a literal.
  241. AllowedOperand AO =
  242. IsLegacyLineExpr ? AllowedOperand::Literal : AllowedOperand::Any;
  243. Expected<std::unique_ptr<FileCheckExpressionAST>> RightOpResult =
  244. parseNumericOperand(Expr, AO, LineNumber, Context, SM);
  245. if (!RightOpResult)
  246. return RightOpResult;
  247. Expr = Expr.ltrim(SpaceChars);
  248. return llvm::make_unique<FileCheckASTBinop>(EvalBinop, std::move(LeftOp),
  249. std::move(*RightOpResult));
  250. }
  251. Expected<std::unique_ptr<FileCheckExpressionAST>>
  252. FileCheckPattern::parseNumericSubstitutionBlock(
  253. StringRef Expr,
  254. Optional<FileCheckNumericVariable *> &DefinedNumericVariable,
  255. bool IsLegacyLineExpr, Optional<size_t> LineNumber,
  256. FileCheckPatternContext *Context, const SourceMgr &SM) {
  257. std::unique_ptr<FileCheckExpressionAST> ExpressionAST = nullptr;
  258. StringRef DefExpr = StringRef();
  259. DefinedNumericVariable = None;
  260. // Save variable definition expression if any.
  261. size_t DefEnd = Expr.find(':');
  262. if (DefEnd != StringRef::npos) {
  263. DefExpr = Expr.substr(0, DefEnd);
  264. Expr = Expr.substr(DefEnd + 1);
  265. }
  266. // Parse the expression itself.
  267. Expr = Expr.ltrim(SpaceChars);
  268. if (!Expr.empty()) {
  269. // The first operand in a legacy @LINE expression is always the @LINE
  270. // pseudo variable.
  271. AllowedOperand AO =
  272. IsLegacyLineExpr ? AllowedOperand::LineVar : AllowedOperand::Any;
  273. Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =
  274. parseNumericOperand(Expr, AO, LineNumber, Context, SM);
  275. while (ParseResult && !Expr.empty()) {
  276. ParseResult = parseBinop(Expr, std::move(*ParseResult), IsLegacyLineExpr,
  277. LineNumber, Context, SM);
  278. // Legacy @LINE expressions only allow 2 operands.
  279. if (ParseResult && IsLegacyLineExpr && !Expr.empty())
  280. return FileCheckErrorDiagnostic::get(
  281. SM, Expr,
  282. "unexpected characters at end of expression '" + Expr + "'");
  283. }
  284. if (!ParseResult)
  285. return ParseResult;
  286. ExpressionAST = std::move(*ParseResult);
  287. }
  288. // Parse the numeric variable definition.
  289. if (DefEnd != StringRef::npos) {
  290. DefExpr = DefExpr.ltrim(SpaceChars);
  291. Expected<FileCheckNumericVariable *> ParseResult =
  292. parseNumericVariableDefinition(DefExpr, Context, LineNumber,
  293. ExpressionAST.get(), SM);
  294. if (!ParseResult)
  295. return ParseResult.takeError();
  296. DefinedNumericVariable = *ParseResult;
  297. }
  298. return ExpressionAST;
  299. }
  300. bool FileCheckPattern::parsePattern(StringRef PatternStr, StringRef Prefix,
  301. SourceMgr &SM,
  302. const FileCheckRequest &Req) {
  303. bool MatchFullLinesHere = Req.MatchFullLines && CheckTy != Check::CheckNot;
  304. PatternLoc = SMLoc::getFromPointer(PatternStr.data());
  305. if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
  306. // Ignore trailing whitespace.
  307. while (!PatternStr.empty() &&
  308. (PatternStr.back() == ' ' || PatternStr.back() == '\t'))
  309. PatternStr = PatternStr.substr(0, PatternStr.size() - 1);
  310. // Check that there is something on the line.
  311. if (PatternStr.empty() && CheckTy != Check::CheckEmpty) {
  312. SM.PrintMessage(PatternLoc, SourceMgr::DK_Error,
  313. "found empty check string with prefix '" + Prefix + ":'");
  314. return true;
  315. }
  316. if (!PatternStr.empty() && CheckTy == Check::CheckEmpty) {
  317. SM.PrintMessage(
  318. PatternLoc, SourceMgr::DK_Error,
  319. "found non-empty check string for empty check with prefix '" + Prefix +
  320. ":'");
  321. return true;
  322. }
  323. if (CheckTy == Check::CheckEmpty) {
  324. RegExStr = "(\n$)";
  325. return false;
  326. }
  327. // Check to see if this is a fixed string, or if it has regex pieces.
  328. if (!MatchFullLinesHere &&
  329. (PatternStr.size() < 2 || (PatternStr.find("{{") == StringRef::npos &&
  330. PatternStr.find("[[") == StringRef::npos))) {
  331. FixedStr = PatternStr;
  332. return false;
  333. }
  334. if (MatchFullLinesHere) {
  335. RegExStr += '^';
  336. if (!Req.NoCanonicalizeWhiteSpace)
  337. RegExStr += " *";
  338. }
  339. // Paren value #0 is for the fully matched string. Any new parenthesized
  340. // values add from there.
  341. unsigned CurParen = 1;
  342. // Otherwise, there is at least one regex piece. Build up the regex pattern
  343. // by escaping scary characters in fixed strings, building up one big regex.
  344. while (!PatternStr.empty()) {
  345. // RegEx matches.
  346. if (PatternStr.startswith("{{")) {
  347. // This is the start of a regex match. Scan for the }}.
  348. size_t End = PatternStr.find("}}");
  349. if (End == StringRef::npos) {
  350. SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
  351. SourceMgr::DK_Error,
  352. "found start of regex string with no end '}}'");
  353. return true;
  354. }
  355. // Enclose {{}} patterns in parens just like [[]] even though we're not
  356. // capturing the result for any purpose. This is required in case the
  357. // expression contains an alternation like: CHECK: abc{{x|z}}def. We
  358. // want this to turn into: "abc(x|z)def" not "abcx|zdef".
  359. RegExStr += '(';
  360. ++CurParen;
  361. if (AddRegExToRegEx(PatternStr.substr(2, End - 2), CurParen, SM))
  362. return true;
  363. RegExStr += ')';
  364. PatternStr = PatternStr.substr(End + 2);
  365. continue;
  366. }
  367. // String and numeric substitution blocks. Pattern substitution blocks come
  368. // in two forms: [[foo:.*]] and [[foo]]. The former matches .* (or some
  369. // other regex) and assigns it to the string variable 'foo'. The latter
  370. // substitutes foo's value. Numeric substitution blocks recognize the same
  371. // form as string ones, but start with a '#' sign after the double
  372. // brackets. They also accept a combined form which sets a numeric variable
  373. // to the evaluation of an expression. Both string and numeric variable
  374. // names must satisfy the regular expression "[a-zA-Z_][0-9a-zA-Z_]*" to be
  375. // valid, as this helps catch some common errors.
  376. if (PatternStr.startswith("[[")) {
  377. StringRef UnparsedPatternStr = PatternStr.substr(2);
  378. // Find the closing bracket pair ending the match. End is going to be an
  379. // offset relative to the beginning of the match string.
  380. size_t End = FindRegexVarEnd(UnparsedPatternStr, SM);
  381. StringRef MatchStr = UnparsedPatternStr.substr(0, End);
  382. bool IsNumBlock = MatchStr.consume_front("#");
  383. if (End == StringRef::npos) {
  384. SM.PrintMessage(SMLoc::getFromPointer(PatternStr.data()),
  385. SourceMgr::DK_Error,
  386. "Invalid substitution block, no ]] found");
  387. return true;
  388. }
  389. // Strip the substitution block we are parsing. End points to the start
  390. // of the "]]" closing the expression so account for it in computing the
  391. // index of the first unparsed character.
  392. PatternStr = UnparsedPatternStr.substr(End + 2);
  393. bool IsDefinition = false;
  394. bool SubstNeeded = false;
  395. // Whether the substitution block is a legacy use of @LINE with string
  396. // substitution block syntax.
  397. bool IsLegacyLineExpr = false;
  398. StringRef DefName;
  399. StringRef SubstStr;
  400. StringRef MatchRegexp;
  401. size_t SubstInsertIdx = RegExStr.size();
  402. // Parse string variable or legacy @LINE expression.
  403. if (!IsNumBlock) {
  404. size_t VarEndIdx = MatchStr.find(":");
  405. size_t SpacePos = MatchStr.substr(0, VarEndIdx).find_first_of(" \t");
  406. if (SpacePos != StringRef::npos) {
  407. SM.PrintMessage(SMLoc::getFromPointer(MatchStr.data() + SpacePos),
  408. SourceMgr::DK_Error, "unexpected whitespace");
  409. return true;
  410. }
  411. // Get the name (e.g. "foo") and verify it is well formed.
  412. StringRef OrigMatchStr = MatchStr;
  413. Expected<FileCheckPattern::VariableProperties> ParseVarResult =
  414. parseVariable(MatchStr, SM);
  415. if (!ParseVarResult) {
  416. logAllUnhandledErrors(ParseVarResult.takeError(), errs());
  417. return true;
  418. }
  419. StringRef Name = ParseVarResult->Name;
  420. bool IsPseudo = ParseVarResult->IsPseudo;
  421. IsDefinition = (VarEndIdx != StringRef::npos);
  422. SubstNeeded = !IsDefinition;
  423. if (IsDefinition) {
  424. if ((IsPseudo || !MatchStr.consume_front(":"))) {
  425. SM.PrintMessage(SMLoc::getFromPointer(Name.data()),
  426. SourceMgr::DK_Error,
  427. "invalid name in string variable definition");
  428. return true;
  429. }
  430. // Detect collisions between string and numeric variables when the
  431. // former is created later than the latter.
  432. if (Context->GlobalNumericVariableTable.find(Name) !=
  433. Context->GlobalNumericVariableTable.end()) {
  434. SM.PrintMessage(
  435. SMLoc::getFromPointer(Name.data()), SourceMgr::DK_Error,
  436. "numeric variable with name '" + Name + "' already exists");
  437. return true;
  438. }
  439. DefName = Name;
  440. MatchRegexp = MatchStr;
  441. } else {
  442. if (IsPseudo) {
  443. MatchStr = OrigMatchStr;
  444. IsLegacyLineExpr = IsNumBlock = true;
  445. } else
  446. SubstStr = Name;
  447. }
  448. }
  449. // Parse numeric substitution block.
  450. std::unique_ptr<FileCheckExpressionAST> ExpressionAST;
  451. Optional<FileCheckNumericVariable *> DefinedNumericVariable;
  452. if (IsNumBlock) {
  453. Expected<std::unique_ptr<FileCheckExpressionAST>> ParseResult =
  454. parseNumericSubstitutionBlock(MatchStr, DefinedNumericVariable,
  455. IsLegacyLineExpr, LineNumber, Context,
  456. SM);
  457. if (!ParseResult) {
  458. logAllUnhandledErrors(ParseResult.takeError(), errs());
  459. return true;
  460. }
  461. ExpressionAST = std::move(*ParseResult);
  462. SubstNeeded = ExpressionAST != nullptr;
  463. if (DefinedNumericVariable) {
  464. IsDefinition = true;
  465. DefName = (*DefinedNumericVariable)->getName();
  466. }
  467. if (SubstNeeded)
  468. SubstStr = MatchStr;
  469. else
  470. MatchRegexp = "[0-9]+";
  471. }
  472. // Handle variable definition: [[<def>:(...)]] and [[#(...)<def>:(...)]].
  473. if (IsDefinition) {
  474. RegExStr += '(';
  475. ++SubstInsertIdx;
  476. if (IsNumBlock) {
  477. FileCheckNumericVariableMatch NumericVariableDefinition = {
  478. *DefinedNumericVariable, CurParen};
  479. NumericVariableDefs[DefName] = NumericVariableDefinition;
  480. // This store is done here rather than in match() to allow
  481. // parseNumericVariableUse() to get the pointer to the class instance
  482. // of the right variable definition corresponding to a given numeric
  483. // variable use.
  484. Context->GlobalNumericVariableTable[DefName] =
  485. *DefinedNumericVariable;
  486. } else {
  487. VariableDefs[DefName] = CurParen;
  488. // Mark string variable as defined to detect collisions between
  489. // string and numeric variables in parseNumericVariableUse() and
  490. // defineCmdlineVariables() when the latter is created later than the
  491. // former. We cannot reuse GlobalVariableTable for this by populating
  492. // it with an empty string since we would then lose the ability to
  493. // detect the use of an undefined variable in match().
  494. Context->DefinedVariableTable[DefName] = true;
  495. }
  496. ++CurParen;
  497. }
  498. if (!MatchRegexp.empty() && AddRegExToRegEx(MatchRegexp, CurParen, SM))
  499. return true;
  500. if (IsDefinition)
  501. RegExStr += ')';
  502. // Handle substitutions: [[foo]] and [[#<foo expr>]].
  503. if (SubstNeeded) {
  504. // Handle substitution of string variables that were defined earlier on
  505. // the same line by emitting a backreference. Expressions do not
  506. // support substituting a numeric variable defined on the same line.
  507. if (!IsNumBlock && VariableDefs.find(SubstStr) != VariableDefs.end()) {
  508. unsigned CaptureParenGroup = VariableDefs[SubstStr];
  509. if (CaptureParenGroup < 1 || CaptureParenGroup > 9) {
  510. SM.PrintMessage(SMLoc::getFromPointer(SubstStr.data()),
  511. SourceMgr::DK_Error,
  512. "Can't back-reference more than 9 variables");
  513. return true;
  514. }
  515. AddBackrefToRegEx(CaptureParenGroup);
  516. } else {
  517. // Handle substitution of string variables ([[<var>]]) defined in
  518. // previous CHECK patterns, and substitution of expressions.
  519. FileCheckSubstitution *Substitution =
  520. IsNumBlock
  521. ? Context->makeNumericSubstitution(
  522. SubstStr, std::move(ExpressionAST), SubstInsertIdx)
  523. : Context->makeStringSubstitution(SubstStr, SubstInsertIdx);
  524. Substitutions.push_back(Substitution);
  525. }
  526. }
  527. }
  528. // Handle fixed string matches.
  529. // Find the end, which is the start of the next regex.
  530. size_t FixedMatchEnd = PatternStr.find("{{");
  531. FixedMatchEnd = std::min(FixedMatchEnd, PatternStr.find("[["));
  532. RegExStr += Regex::escape(PatternStr.substr(0, FixedMatchEnd));
  533. PatternStr = PatternStr.substr(FixedMatchEnd);
  534. }
  535. if (MatchFullLinesHere) {
  536. if (!Req.NoCanonicalizeWhiteSpace)
  537. RegExStr += " *";
  538. RegExStr += '$';
  539. }
  540. return false;
  541. }
  542. bool FileCheckPattern::AddRegExToRegEx(StringRef RS, unsigned &CurParen, SourceMgr &SM) {
  543. Regex R(RS);
  544. std::string Error;
  545. if (!R.isValid(Error)) {
  546. SM.PrintMessage(SMLoc::getFromPointer(RS.data()), SourceMgr::DK_Error,
  547. "invalid regex: " + Error);
  548. return true;
  549. }
  550. RegExStr += RS.str();
  551. CurParen += R.getNumMatches();
  552. return false;
  553. }
  554. void FileCheckPattern::AddBackrefToRegEx(unsigned BackrefNum) {
  555. assert(BackrefNum >= 1 && BackrefNum <= 9 && "Invalid backref number");
  556. std::string Backref = std::string("\\") + std::string(1, '0' + BackrefNum);
  557. RegExStr += Backref;
  558. }
  559. Expected<size_t> FileCheckPattern::match(StringRef Buffer, size_t &MatchLen,
  560. const SourceMgr &SM) const {
  561. // If this is the EOF pattern, match it immediately.
  562. if (CheckTy == Check::CheckEOF) {
  563. MatchLen = 0;
  564. return Buffer.size();
  565. }
  566. // If this is a fixed string pattern, just match it now.
  567. if (!FixedStr.empty()) {
  568. MatchLen = FixedStr.size();
  569. size_t Pos = Buffer.find(FixedStr);
  570. if (Pos == StringRef::npos)
  571. return make_error<FileCheckNotFoundError>();
  572. return Pos;
  573. }
  574. // Regex match.
  575. // If there are substitutions, we need to create a temporary string with the
  576. // actual value.
  577. StringRef RegExToMatch = RegExStr;
  578. std::string TmpStr;
  579. if (!Substitutions.empty()) {
  580. TmpStr = RegExStr;
  581. if (LineNumber)
  582. Context->LineVariable->setValue(*LineNumber);
  583. size_t InsertOffset = 0;
  584. // Substitute all string variables and expressions whose values are only
  585. // now known. Use of string variables defined on the same line are handled
  586. // by back-references.
  587. for (const auto &Substitution : Substitutions) {
  588. // Substitute and check for failure (e.g. use of undefined variable).
  589. Expected<std::string> Value = Substitution->getResult();
  590. if (!Value)
  591. return Value.takeError();
  592. // Plop it into the regex at the adjusted offset.
  593. TmpStr.insert(TmpStr.begin() + Substitution->getIndex() + InsertOffset,
  594. Value->begin(), Value->end());
  595. InsertOffset += Value->size();
  596. }
  597. // Match the newly constructed regex.
  598. RegExToMatch = TmpStr;
  599. }
  600. SmallVector<StringRef, 4> MatchInfo;
  601. if (!Regex(RegExToMatch, Regex::Newline).match(Buffer, &MatchInfo))
  602. return make_error<FileCheckNotFoundError>();
  603. // Successful regex match.
  604. assert(!MatchInfo.empty() && "Didn't get any match");
  605. StringRef FullMatch = MatchInfo[0];
  606. // If this defines any string variables, remember their values.
  607. for (const auto &VariableDef : VariableDefs) {
  608. assert(VariableDef.second < MatchInfo.size() && "Internal paren error");
  609. Context->GlobalVariableTable[VariableDef.first] =
  610. MatchInfo[VariableDef.second];
  611. }
  612. // If this defines any numeric variables, remember their values.
  613. for (const auto &NumericVariableDef : NumericVariableDefs) {
  614. const FileCheckNumericVariableMatch &NumericVariableMatch =
  615. NumericVariableDef.getValue();
  616. unsigned CaptureParenGroup = NumericVariableMatch.CaptureParenGroup;
  617. assert(CaptureParenGroup < MatchInfo.size() && "Internal paren error");
  618. FileCheckNumericVariable *DefinedNumericVariable =
  619. NumericVariableMatch.DefinedNumericVariable;
  620. StringRef MatchedValue = MatchInfo[CaptureParenGroup];
  621. uint64_t Val;
  622. if (MatchedValue.getAsInteger(10, Val))
  623. return FileCheckErrorDiagnostic::get(SM, MatchedValue,
  624. "Unable to represent numeric value");
  625. DefinedNumericVariable->setValue(Val);
  626. }
  627. // Like CHECK-NEXT, CHECK-EMPTY's match range is considered to start after
  628. // the required preceding newline, which is consumed by the pattern in the
  629. // case of CHECK-EMPTY but not CHECK-NEXT.
  630. size_t MatchStartSkip = CheckTy == Check::CheckEmpty;
  631. MatchLen = FullMatch.size() - MatchStartSkip;
  632. return FullMatch.data() - Buffer.data() + MatchStartSkip;
  633. }
  634. unsigned FileCheckPattern::computeMatchDistance(StringRef Buffer) const {
  635. // Just compute the number of matching characters. For regular expressions, we
  636. // just compare against the regex itself and hope for the best.
  637. //
  638. // FIXME: One easy improvement here is have the regex lib generate a single
  639. // example regular expression which matches, and use that as the example
  640. // string.
  641. StringRef ExampleString(FixedStr);
  642. if (ExampleString.empty())
  643. ExampleString = RegExStr;
  644. // Only compare up to the first line in the buffer, or the string size.
  645. StringRef BufferPrefix = Buffer.substr(0, ExampleString.size());
  646. BufferPrefix = BufferPrefix.split('\n').first;
  647. return BufferPrefix.edit_distance(ExampleString);
  648. }
  649. void FileCheckPattern::printSubstitutions(const SourceMgr &SM, StringRef Buffer,
  650. SMRange MatchRange) const {
  651. // Print what we know about substitutions.
  652. if (!Substitutions.empty()) {
  653. for (const auto &Substitution : Substitutions) {
  654. SmallString<256> Msg;
  655. raw_svector_ostream OS(Msg);
  656. Expected<std::string> MatchedValue = Substitution->getResult();
  657. // Substitution failed or is not known at match time, print the undefined
  658. // variables it uses.
  659. if (!MatchedValue) {
  660. bool UndefSeen = false;
  661. handleAllErrors(MatchedValue.takeError(),
  662. [](const FileCheckNotFoundError &E) {},
  663. // Handled in PrintNoMatch().
  664. [](const FileCheckErrorDiagnostic &E) {},
  665. [&](const FileCheckUndefVarError &E) {
  666. if (!UndefSeen) {
  667. OS << "uses undefined variable(s):";
  668. UndefSeen = true;
  669. }
  670. OS << " ";
  671. E.log(OS);
  672. });
  673. } else {
  674. // Substitution succeeded. Print substituted value.
  675. OS << "with \"";
  676. OS.write_escaped(Substitution->getFromString()) << "\" equal to \"";
  677. OS.write_escaped(*MatchedValue) << "\"";
  678. }
  679. if (MatchRange.isValid())
  680. SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, OS.str(),
  681. {MatchRange});
  682. else
  683. SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()),
  684. SourceMgr::DK_Note, OS.str());
  685. }
  686. }
  687. }
  688. static SMRange ProcessMatchResult(FileCheckDiag::MatchType MatchTy,
  689. const SourceMgr &SM, SMLoc Loc,
  690. Check::FileCheckType CheckTy,
  691. StringRef Buffer, size_t Pos, size_t Len,
  692. std::vector<FileCheckDiag> *Diags,
  693. bool AdjustPrevDiag = false) {
  694. SMLoc Start = SMLoc::getFromPointer(Buffer.data() + Pos);
  695. SMLoc End = SMLoc::getFromPointer(Buffer.data() + Pos + Len);
  696. SMRange Range(Start, End);
  697. if (Diags) {
  698. if (AdjustPrevDiag)
  699. Diags->rbegin()->MatchTy = MatchTy;
  700. else
  701. Diags->emplace_back(SM, CheckTy, Loc, MatchTy, Range);
  702. }
  703. return Range;
  704. }
  705. void FileCheckPattern::printFuzzyMatch(
  706. const SourceMgr &SM, StringRef Buffer,
  707. std::vector<FileCheckDiag> *Diags) const {
  708. // Attempt to find the closest/best fuzzy match. Usually an error happens
  709. // because some string in the output didn't exactly match. In these cases, we
  710. // would like to show the user a best guess at what "should have" matched, to
  711. // save them having to actually check the input manually.
  712. size_t NumLinesForward = 0;
  713. size_t Best = StringRef::npos;
  714. double BestQuality = 0;
  715. // Use an arbitrary 4k limit on how far we will search.
  716. for (size_t i = 0, e = std::min(size_t(4096), Buffer.size()); i != e; ++i) {
  717. if (Buffer[i] == '\n')
  718. ++NumLinesForward;
  719. // Patterns have leading whitespace stripped, so skip whitespace when
  720. // looking for something which looks like a pattern.
  721. if (Buffer[i] == ' ' || Buffer[i] == '\t')
  722. continue;
  723. // Compute the "quality" of this match as an arbitrary combination of the
  724. // match distance and the number of lines skipped to get to this match.
  725. unsigned Distance = computeMatchDistance(Buffer.substr(i));
  726. double Quality = Distance + (NumLinesForward / 100.);
  727. if (Quality < BestQuality || Best == StringRef::npos) {
  728. Best = i;
  729. BestQuality = Quality;
  730. }
  731. }
  732. // Print the "possible intended match here" line if we found something
  733. // reasonable and not equal to what we showed in the "scanning from here"
  734. // line.
  735. if (Best && Best != StringRef::npos && BestQuality < 50) {
  736. SMRange MatchRange =
  737. ProcessMatchResult(FileCheckDiag::MatchFuzzy, SM, getLoc(),
  738. getCheckTy(), Buffer, Best, 0, Diags);
  739. SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note,
  740. "possible intended match here");
  741. // FIXME: If we wanted to be really friendly we would show why the match
  742. // failed, as it can be hard to spot simple one character differences.
  743. }
  744. }
  745. Expected<StringRef>
  746. FileCheckPatternContext::getPatternVarValue(StringRef VarName) {
  747. auto VarIter = GlobalVariableTable.find(VarName);
  748. if (VarIter == GlobalVariableTable.end())
  749. return make_error<FileCheckUndefVarError>(VarName);
  750. return VarIter->second;
  751. }
  752. template <class... Types>
  753. FileCheckNumericVariable *
  754. FileCheckPatternContext::makeNumericVariable(Types... args) {
  755. NumericVariables.push_back(
  756. llvm::make_unique<FileCheckNumericVariable>(args...));
  757. return NumericVariables.back().get();
  758. }
  759. FileCheckSubstitution *
  760. FileCheckPatternContext::makeStringSubstitution(StringRef VarName,
  761. size_t InsertIdx) {
  762. Substitutions.push_back(
  763. llvm::make_unique<FileCheckStringSubstitution>(this, VarName, InsertIdx));
  764. return Substitutions.back().get();
  765. }
  766. FileCheckSubstitution *FileCheckPatternContext::makeNumericSubstitution(
  767. StringRef ExpressionStr,
  768. std::unique_ptr<FileCheckExpressionAST> ExpressionAST, size_t InsertIdx) {
  769. Substitutions.push_back(llvm::make_unique<FileCheckNumericSubstitution>(
  770. this, ExpressionStr, std::move(ExpressionAST), InsertIdx));
  771. return Substitutions.back().get();
  772. }
  773. size_t FileCheckPattern::FindRegexVarEnd(StringRef Str, SourceMgr &SM) {
  774. // Offset keeps track of the current offset within the input Str
  775. size_t Offset = 0;
  776. // [...] Nesting depth
  777. size_t BracketDepth = 0;
  778. while (!Str.empty()) {
  779. if (Str.startswith("]]") && BracketDepth == 0)
  780. return Offset;
  781. if (Str[0] == '\\') {
  782. // Backslash escapes the next char within regexes, so skip them both.
  783. Str = Str.substr(2);
  784. Offset += 2;
  785. } else {
  786. switch (Str[0]) {
  787. default:
  788. break;
  789. case '[':
  790. BracketDepth++;
  791. break;
  792. case ']':
  793. if (BracketDepth == 0) {
  794. SM.PrintMessage(SMLoc::getFromPointer(Str.data()),
  795. SourceMgr::DK_Error,
  796. "missing closing \"]\" for regex variable");
  797. exit(1);
  798. }
  799. BracketDepth--;
  800. break;
  801. }
  802. Str = Str.substr(1);
  803. Offset++;
  804. }
  805. }
  806. return StringRef::npos;
  807. }
  808. StringRef FileCheck::CanonicalizeFile(MemoryBuffer &MB,
  809. SmallVectorImpl<char> &OutputBuffer) {
  810. OutputBuffer.reserve(MB.getBufferSize());
  811. for (const char *Ptr = MB.getBufferStart(), *End = MB.getBufferEnd();
  812. Ptr != End; ++Ptr) {
  813. // Eliminate trailing dosish \r.
  814. if (Ptr <= End - 2 && Ptr[0] == '\r' && Ptr[1] == '\n') {
  815. continue;
  816. }
  817. // If current char is not a horizontal whitespace or if horizontal
  818. // whitespace canonicalization is disabled, dump it to output as is.
  819. if (Req.NoCanonicalizeWhiteSpace || (*Ptr != ' ' && *Ptr != '\t')) {
  820. OutputBuffer.push_back(*Ptr);
  821. continue;
  822. }
  823. // Otherwise, add one space and advance over neighboring space.
  824. OutputBuffer.push_back(' ');
  825. while (Ptr + 1 != End && (Ptr[1] == ' ' || Ptr[1] == '\t'))
  826. ++Ptr;
  827. }
  828. // Add a null byte and then return all but that byte.
  829. OutputBuffer.push_back('\0');
  830. return StringRef(OutputBuffer.data(), OutputBuffer.size() - 1);
  831. }
  832. FileCheckDiag::FileCheckDiag(const SourceMgr &SM,
  833. const Check::FileCheckType &CheckTy,
  834. SMLoc CheckLoc, MatchType MatchTy,
  835. SMRange InputRange)
  836. : CheckTy(CheckTy), MatchTy(MatchTy) {
  837. auto Start = SM.getLineAndColumn(InputRange.Start);
  838. auto End = SM.getLineAndColumn(InputRange.End);
  839. InputStartLine = Start.first;
  840. InputStartCol = Start.second;
  841. InputEndLine = End.first;
  842. InputEndCol = End.second;
  843. Start = SM.getLineAndColumn(CheckLoc);
  844. CheckLine = Start.first;
  845. CheckCol = Start.second;
  846. }
  847. static bool IsPartOfWord(char c) {
  848. return (isalnum(c) || c == '-' || c == '_');
  849. }
  850. Check::FileCheckType &Check::FileCheckType::setCount(int C) {
  851. assert(Count > 0 && "zero and negative counts are not supported");
  852. assert((C == 1 || Kind == CheckPlain) &&
  853. "count supported only for plain CHECK directives");
  854. Count = C;
  855. return *this;
  856. }
  857. std::string Check::FileCheckType::getDescription(StringRef Prefix) const {
  858. switch (Kind) {
  859. case Check::CheckNone:
  860. return "invalid";
  861. case Check::CheckPlain:
  862. if (Count > 1)
  863. return Prefix.str() + "-COUNT";
  864. return Prefix;
  865. case Check::CheckNext:
  866. return Prefix.str() + "-NEXT";
  867. case Check::CheckSame:
  868. return Prefix.str() + "-SAME";
  869. case Check::CheckNot:
  870. return Prefix.str() + "-NOT";
  871. case Check::CheckDAG:
  872. return Prefix.str() + "-DAG";
  873. case Check::CheckLabel:
  874. return Prefix.str() + "-LABEL";
  875. case Check::CheckEmpty:
  876. return Prefix.str() + "-EMPTY";
  877. case Check::CheckEOF:
  878. return "implicit EOF";
  879. case Check::CheckBadNot:
  880. return "bad NOT";
  881. case Check::CheckBadCount:
  882. return "bad COUNT";
  883. }
  884. llvm_unreachable("unknown FileCheckType");
  885. }
  886. static std::pair<Check::FileCheckType, StringRef>
  887. FindCheckType(StringRef Buffer, StringRef Prefix) {
  888. if (Buffer.size() <= Prefix.size())
  889. return {Check::CheckNone, StringRef()};
  890. char NextChar = Buffer[Prefix.size()];
  891. StringRef Rest = Buffer.drop_front(Prefix.size() + 1);
  892. // Verify that the : is present after the prefix.
  893. if (NextChar == ':')
  894. return {Check::CheckPlain, Rest};
  895. if (NextChar != '-')
  896. return {Check::CheckNone, StringRef()};
  897. if (Rest.consume_front("COUNT-")) {
  898. int64_t Count;
  899. if (Rest.consumeInteger(10, Count))
  900. // Error happened in parsing integer.
  901. return {Check::CheckBadCount, Rest};
  902. if (Count <= 0 || Count > INT32_MAX)
  903. return {Check::CheckBadCount, Rest};
  904. if (!Rest.consume_front(":"))
  905. return {Check::CheckBadCount, Rest};
  906. return {Check::FileCheckType(Check::CheckPlain).setCount(Count), Rest};
  907. }
  908. if (Rest.consume_front("NEXT:"))
  909. return {Check::CheckNext, Rest};
  910. if (Rest.consume_front("SAME:"))
  911. return {Check::CheckSame, Rest};
  912. if (Rest.consume_front("NOT:"))
  913. return {Check::CheckNot, Rest};
  914. if (Rest.consume_front("DAG:"))
  915. return {Check::CheckDAG, Rest};
  916. if (Rest.consume_front("LABEL:"))
  917. return {Check::CheckLabel, Rest};
  918. if (Rest.consume_front("EMPTY:"))
  919. return {Check::CheckEmpty, Rest};
  920. // You can't combine -NOT with another suffix.
  921. if (Rest.startswith("DAG-NOT:") || Rest.startswith("NOT-DAG:") ||
  922. Rest.startswith("NEXT-NOT:") || Rest.startswith("NOT-NEXT:") ||
  923. Rest.startswith("SAME-NOT:") || Rest.startswith("NOT-SAME:") ||
  924. Rest.startswith("EMPTY-NOT:") || Rest.startswith("NOT-EMPTY:"))
  925. return {Check::CheckBadNot, Rest};
  926. return {Check::CheckNone, Rest};
  927. }
  928. // From the given position, find the next character after the word.
  929. static size_t SkipWord(StringRef Str, size_t Loc) {
  930. while (Loc < Str.size() && IsPartOfWord(Str[Loc]))
  931. ++Loc;
  932. return Loc;
  933. }
  934. /// Searches the buffer for the first prefix in the prefix regular expression.
  935. ///
  936. /// This searches the buffer using the provided regular expression, however it
  937. /// enforces constraints beyond that:
  938. /// 1) The found prefix must not be a suffix of something that looks like
  939. /// a valid prefix.
  940. /// 2) The found prefix must be followed by a valid check type suffix using \c
  941. /// FindCheckType above.
  942. ///
  943. /// \returns a pair of StringRefs into the Buffer, which combines:
  944. /// - the first match of the regular expression to satisfy these two is
  945. /// returned,
  946. /// otherwise an empty StringRef is returned to indicate failure.
  947. /// - buffer rewound to the location right after parsed suffix, for parsing
  948. /// to continue from
  949. ///
  950. /// If this routine returns a valid prefix, it will also shrink \p Buffer to
  951. /// start at the beginning of the returned prefix, increment \p LineNumber for
  952. /// each new line consumed from \p Buffer, and set \p CheckTy to the type of
  953. /// check found by examining the suffix.
  954. ///
  955. /// If no valid prefix is found, the state of Buffer, LineNumber, and CheckTy
  956. /// is unspecified.
  957. static std::pair<StringRef, StringRef>
  958. FindFirstMatchingPrefix(Regex &PrefixRE, StringRef &Buffer,
  959. unsigned &LineNumber, Check::FileCheckType &CheckTy) {
  960. SmallVector<StringRef, 2> Matches;
  961. while (!Buffer.empty()) {
  962. // Find the first (longest) match using the RE.
  963. if (!PrefixRE.match(Buffer, &Matches))
  964. // No match at all, bail.
  965. return {StringRef(), StringRef()};
  966. StringRef Prefix = Matches[0];
  967. Matches.clear();
  968. assert(Prefix.data() >= Buffer.data() &&
  969. Prefix.data() < Buffer.data() + Buffer.size() &&
  970. "Prefix doesn't start inside of buffer!");
  971. size_t Loc = Prefix.data() - Buffer.data();
  972. StringRef Skipped = Buffer.substr(0, Loc);
  973. Buffer = Buffer.drop_front(Loc);
  974. LineNumber += Skipped.count('\n');
  975. // Check that the matched prefix isn't a suffix of some other check-like
  976. // word.
  977. // FIXME: This is a very ad-hoc check. it would be better handled in some
  978. // other way. Among other things it seems hard to distinguish between
  979. // intentional and unintentional uses of this feature.
  980. if (Skipped.empty() || !IsPartOfWord(Skipped.back())) {
  981. // Now extract the type.
  982. StringRef AfterSuffix;
  983. std::tie(CheckTy, AfterSuffix) = FindCheckType(Buffer, Prefix);
  984. // If we've found a valid check type for this prefix, we're done.
  985. if (CheckTy != Check::CheckNone)
  986. return {Prefix, AfterSuffix};
  987. }
  988. // If we didn't successfully find a prefix, we need to skip this invalid
  989. // prefix and continue scanning. We directly skip the prefix that was
  990. // matched and any additional parts of that check-like word.
  991. Buffer = Buffer.drop_front(SkipWord(Buffer, Prefix.size()));
  992. }
  993. // We ran out of buffer while skipping partial matches so give up.
  994. return {StringRef(), StringRef()};
  995. }
  996. void FileCheckPatternContext::createLineVariable() {
  997. assert(!LineVariable && "@LINE pseudo numeric variable already created");
  998. StringRef LineName = "@LINE";
  999. LineVariable = makeNumericVariable(LineName);
  1000. GlobalNumericVariableTable[LineName] = LineVariable;
  1001. }
  1002. bool FileCheck::ReadCheckFile(SourceMgr &SM, StringRef Buffer, Regex &PrefixRE,
  1003. std::vector<FileCheckString> &CheckStrings) {
  1004. Error DefineError =
  1005. PatternContext.defineCmdlineVariables(Req.GlobalDefines, SM);
  1006. if (DefineError) {
  1007. logAllUnhandledErrors(std::move(DefineError), errs());
  1008. return true;
  1009. }
  1010. PatternContext.createLineVariable();
  1011. std::vector<FileCheckPattern> ImplicitNegativeChecks;
  1012. for (const auto &PatternString : Req.ImplicitCheckNot) {
  1013. // Create a buffer with fake command line content in order to display the
  1014. // command line option responsible for the specific implicit CHECK-NOT.
  1015. std::string Prefix = "-implicit-check-not='";
  1016. std::string Suffix = "'";
  1017. std::unique_ptr<MemoryBuffer> CmdLine = MemoryBuffer::getMemBufferCopy(
  1018. Prefix + PatternString + Suffix, "command line");
  1019. StringRef PatternInBuffer =
  1020. CmdLine->getBuffer().substr(Prefix.size(), PatternString.size());
  1021. SM.AddNewSourceBuffer(std::move(CmdLine), SMLoc());
  1022. ImplicitNegativeChecks.push_back(
  1023. FileCheckPattern(Check::CheckNot, &PatternContext));
  1024. ImplicitNegativeChecks.back().parsePattern(PatternInBuffer,
  1025. "IMPLICIT-CHECK", SM, Req);
  1026. }
  1027. std::vector<FileCheckPattern> DagNotMatches = ImplicitNegativeChecks;
  1028. // LineNumber keeps track of the line on which CheckPrefix instances are
  1029. // found.
  1030. unsigned LineNumber = 1;
  1031. while (1) {
  1032. Check::FileCheckType CheckTy;
  1033. // See if a prefix occurs in the memory buffer.
  1034. StringRef UsedPrefix;
  1035. StringRef AfterSuffix;
  1036. std::tie(UsedPrefix, AfterSuffix) =
  1037. FindFirstMatchingPrefix(PrefixRE, Buffer, LineNumber, CheckTy);
  1038. if (UsedPrefix.empty())
  1039. break;
  1040. assert(UsedPrefix.data() == Buffer.data() &&
  1041. "Failed to move Buffer's start forward, or pointed prefix outside "
  1042. "of the buffer!");
  1043. assert(AfterSuffix.data() >= Buffer.data() &&
  1044. AfterSuffix.data() < Buffer.data() + Buffer.size() &&
  1045. "Parsing after suffix doesn't start inside of buffer!");
  1046. // Location to use for error messages.
  1047. const char *UsedPrefixStart = UsedPrefix.data();
  1048. // Skip the buffer to the end of parsed suffix (or just prefix, if no good
  1049. // suffix was processed).
  1050. Buffer = AfterSuffix.empty() ? Buffer.drop_front(UsedPrefix.size())
  1051. : AfterSuffix;
  1052. // Complain about useful-looking but unsupported suffixes.
  1053. if (CheckTy == Check::CheckBadNot) {
  1054. SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,
  1055. "unsupported -NOT combo on prefix '" + UsedPrefix + "'");
  1056. return true;
  1057. }
  1058. // Complain about invalid count specification.
  1059. if (CheckTy == Check::CheckBadCount) {
  1060. SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Error,
  1061. "invalid count in -COUNT specification on prefix '" +
  1062. UsedPrefix + "'");
  1063. return true;
  1064. }
  1065. // Okay, we found the prefix, yay. Remember the rest of the line, but ignore
  1066. // leading whitespace.
  1067. if (!(Req.NoCanonicalizeWhiteSpace && Req.MatchFullLines))
  1068. Buffer = Buffer.substr(Buffer.find_first_not_of(" \t"));
  1069. // Scan ahead to the end of line.
  1070. size_t EOL = Buffer.find_first_of("\n\r");
  1071. // Remember the location of the start of the pattern, for diagnostics.
  1072. SMLoc PatternLoc = SMLoc::getFromPointer(Buffer.data());
  1073. // Parse the pattern.
  1074. FileCheckPattern P(CheckTy, &PatternContext, LineNumber);
  1075. if (P.parsePattern(Buffer.substr(0, EOL), UsedPrefix, SM, Req))
  1076. return true;
  1077. // Verify that CHECK-LABEL lines do not define or use variables
  1078. if ((CheckTy == Check::CheckLabel) && P.hasVariable()) {
  1079. SM.PrintMessage(
  1080. SMLoc::getFromPointer(UsedPrefixStart), SourceMgr::DK_Error,
  1081. "found '" + UsedPrefix + "-LABEL:'"
  1082. " with variable definition or use");
  1083. return true;
  1084. }
  1085. Buffer = Buffer.substr(EOL);
  1086. // Verify that CHECK-NEXT/SAME/EMPTY lines have at least one CHECK line before them.
  1087. if ((CheckTy == Check::CheckNext || CheckTy == Check::CheckSame ||
  1088. CheckTy == Check::CheckEmpty) &&
  1089. CheckStrings.empty()) {
  1090. StringRef Type = CheckTy == Check::CheckNext
  1091. ? "NEXT"
  1092. : CheckTy == Check::CheckEmpty ? "EMPTY" : "SAME";
  1093. SM.PrintMessage(SMLoc::getFromPointer(UsedPrefixStart),
  1094. SourceMgr::DK_Error,
  1095. "found '" + UsedPrefix + "-" + Type +
  1096. "' without previous '" + UsedPrefix + ": line");
  1097. return true;
  1098. }
  1099. // Handle CHECK-DAG/-NOT.
  1100. if (CheckTy == Check::CheckDAG || CheckTy == Check::CheckNot) {
  1101. DagNotMatches.push_back(P);
  1102. continue;
  1103. }
  1104. // Okay, add the string we captured to the output vector and move on.
  1105. CheckStrings.emplace_back(P, UsedPrefix, PatternLoc);
  1106. std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
  1107. DagNotMatches = ImplicitNegativeChecks;
  1108. }
  1109. // Add an EOF pattern for any trailing CHECK-DAG/-NOTs, and use the first
  1110. // prefix as a filler for the error message.
  1111. if (!DagNotMatches.empty()) {
  1112. CheckStrings.emplace_back(
  1113. FileCheckPattern(Check::CheckEOF, &PatternContext, LineNumber + 1),
  1114. *Req.CheckPrefixes.begin(), SMLoc::getFromPointer(Buffer.data()));
  1115. std::swap(DagNotMatches, CheckStrings.back().DagNotStrings);
  1116. }
  1117. if (CheckStrings.empty()) {
  1118. errs() << "error: no check strings found with prefix"
  1119. << (Req.CheckPrefixes.size() > 1 ? "es " : " ");
  1120. auto I = Req.CheckPrefixes.begin();
  1121. auto E = Req.CheckPrefixes.end();
  1122. if (I != E) {
  1123. errs() << "\'" << *I << ":'";
  1124. ++I;
  1125. }
  1126. for (; I != E; ++I)
  1127. errs() << ", \'" << *I << ":'";
  1128. errs() << '\n';
  1129. return true;
  1130. }
  1131. return false;
  1132. }
  1133. static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,
  1134. StringRef Prefix, SMLoc Loc, const FileCheckPattern &Pat,
  1135. int MatchedCount, StringRef Buffer, size_t MatchPos,
  1136. size_t MatchLen, const FileCheckRequest &Req,
  1137. std::vector<FileCheckDiag> *Diags) {
  1138. bool PrintDiag = true;
  1139. if (ExpectedMatch) {
  1140. if (!Req.Verbose)
  1141. return;
  1142. if (!Req.VerboseVerbose && Pat.getCheckTy() == Check::CheckEOF)
  1143. return;
  1144. // Due to their verbosity, we don't print verbose diagnostics here if we're
  1145. // gathering them for a different rendering, but we always print other
  1146. // diagnostics.
  1147. PrintDiag = !Diags;
  1148. }
  1149. SMRange MatchRange = ProcessMatchResult(
  1150. ExpectedMatch ? FileCheckDiag::MatchFoundAndExpected
  1151. : FileCheckDiag::MatchFoundButExcluded,
  1152. SM, Loc, Pat.getCheckTy(), Buffer, MatchPos, MatchLen, Diags);
  1153. if (!PrintDiag)
  1154. return;
  1155. std::string Message = formatv("{0}: {1} string found in input",
  1156. Pat.getCheckTy().getDescription(Prefix),
  1157. (ExpectedMatch ? "expected" : "excluded"))
  1158. .str();
  1159. if (Pat.getCount() > 1)
  1160. Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
  1161. SM.PrintMessage(
  1162. Loc, ExpectedMatch ? SourceMgr::DK_Remark : SourceMgr::DK_Error, Message);
  1163. SM.PrintMessage(MatchRange.Start, SourceMgr::DK_Note, "found here",
  1164. {MatchRange});
  1165. Pat.printSubstitutions(SM, Buffer, MatchRange);
  1166. }
  1167. static void PrintMatch(bool ExpectedMatch, const SourceMgr &SM,
  1168. const FileCheckString &CheckStr, int MatchedCount,
  1169. StringRef Buffer, size_t MatchPos, size_t MatchLen,
  1170. FileCheckRequest &Req,
  1171. std::vector<FileCheckDiag> *Diags) {
  1172. PrintMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,
  1173. MatchedCount, Buffer, MatchPos, MatchLen, Req, Diags);
  1174. }
  1175. static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,
  1176. StringRef Prefix, SMLoc Loc,
  1177. const FileCheckPattern &Pat, int MatchedCount,
  1178. StringRef Buffer, bool VerboseVerbose,
  1179. std::vector<FileCheckDiag> *Diags, Error MatchErrors) {
  1180. assert(MatchErrors && "Called on successful match");
  1181. bool PrintDiag = true;
  1182. if (!ExpectedMatch) {
  1183. if (!VerboseVerbose) {
  1184. consumeError(std::move(MatchErrors));
  1185. return;
  1186. }
  1187. // Due to their verbosity, we don't print verbose diagnostics here if we're
  1188. // gathering them for a different rendering, but we always print other
  1189. // diagnostics.
  1190. PrintDiag = !Diags;
  1191. }
  1192. // If the current position is at the end of a line, advance to the start of
  1193. // the next line.
  1194. Buffer = Buffer.substr(Buffer.find_first_not_of(" \t\n\r"));
  1195. SMRange SearchRange = ProcessMatchResult(
  1196. ExpectedMatch ? FileCheckDiag::MatchNoneButExpected
  1197. : FileCheckDiag::MatchNoneAndExcluded,
  1198. SM, Loc, Pat.getCheckTy(), Buffer, 0, Buffer.size(), Diags);
  1199. if (!PrintDiag) {
  1200. consumeError(std::move(MatchErrors));
  1201. return;
  1202. }
  1203. MatchErrors =
  1204. handleErrors(std::move(MatchErrors),
  1205. [](const FileCheckErrorDiagnostic &E) { E.log(errs()); });
  1206. // No problem matching the string per se.
  1207. if (!MatchErrors)
  1208. return;
  1209. consumeError(std::move(MatchErrors));
  1210. // Print "not found" diagnostic.
  1211. std::string Message = formatv("{0}: {1} string not found in input",
  1212. Pat.getCheckTy().getDescription(Prefix),
  1213. (ExpectedMatch ? "expected" : "excluded"))
  1214. .str();
  1215. if (Pat.getCount() > 1)
  1216. Message += formatv(" ({0} out of {1})", MatchedCount, Pat.getCount()).str();
  1217. SM.PrintMessage(
  1218. Loc, ExpectedMatch ? SourceMgr::DK_Error : SourceMgr::DK_Remark, Message);
  1219. // Print the "scanning from here" line.
  1220. SM.PrintMessage(SearchRange.Start, SourceMgr::DK_Note, "scanning from here");
  1221. // Allow the pattern to print additional information if desired.
  1222. Pat.printSubstitutions(SM, Buffer);
  1223. if (ExpectedMatch)
  1224. Pat.printFuzzyMatch(SM, Buffer, Diags);
  1225. }
  1226. static void PrintNoMatch(bool ExpectedMatch, const SourceMgr &SM,
  1227. const FileCheckString &CheckStr, int MatchedCount,
  1228. StringRef Buffer, bool VerboseVerbose,
  1229. std::vector<FileCheckDiag> *Diags, Error MatchErrors) {
  1230. PrintNoMatch(ExpectedMatch, SM, CheckStr.Prefix, CheckStr.Loc, CheckStr.Pat,
  1231. MatchedCount, Buffer, VerboseVerbose, Diags,
  1232. std::move(MatchErrors));
  1233. }
  1234. /// Counts the number of newlines in the specified range.
  1235. static unsigned CountNumNewlinesBetween(StringRef Range,
  1236. const char *&FirstNewLine) {
  1237. unsigned NumNewLines = 0;
  1238. while (1) {
  1239. // Scan for newline.
  1240. Range = Range.substr(Range.find_first_of("\n\r"));
  1241. if (Range.empty())
  1242. return NumNewLines;
  1243. ++NumNewLines;
  1244. // Handle \n\r and \r\n as a single newline.
  1245. if (Range.size() > 1 && (Range[1] == '\n' || Range[1] == '\r') &&
  1246. (Range[0] != Range[1]))
  1247. Range = Range.substr(1);
  1248. Range = Range.substr(1);
  1249. if (NumNewLines == 1)
  1250. FirstNewLine = Range.begin();
  1251. }
  1252. }
  1253. size_t FileCheckString::Check(const SourceMgr &SM, StringRef Buffer,
  1254. bool IsLabelScanMode, size_t &MatchLen,
  1255. FileCheckRequest &Req,
  1256. std::vector<FileCheckDiag> *Diags) const {
  1257. size_t LastPos = 0;
  1258. std::vector<const FileCheckPattern *> NotStrings;
  1259. // IsLabelScanMode is true when we are scanning forward to find CHECK-LABEL
  1260. // bounds; we have not processed variable definitions within the bounded block
  1261. // yet so cannot handle any final CHECK-DAG yet; this is handled when going
  1262. // over the block again (including the last CHECK-LABEL) in normal mode.
  1263. if (!IsLabelScanMode) {
  1264. // Match "dag strings" (with mixed "not strings" if any).
  1265. LastPos = CheckDag(SM, Buffer, NotStrings, Req, Diags);
  1266. if (LastPos == StringRef::npos)
  1267. return StringRef::npos;
  1268. }
  1269. // Match itself from the last position after matching CHECK-DAG.
  1270. size_t LastMatchEnd = LastPos;
  1271. size_t FirstMatchPos = 0;
  1272. // Go match the pattern Count times. Majority of patterns only match with
  1273. // count 1 though.
  1274. assert(Pat.getCount() != 0 && "pattern count can not be zero");
  1275. for (int i = 1; i <= Pat.getCount(); i++) {
  1276. StringRef MatchBuffer = Buffer.substr(LastMatchEnd);
  1277. size_t CurrentMatchLen;
  1278. // get a match at current start point
  1279. Expected<size_t> MatchResult = Pat.match(MatchBuffer, CurrentMatchLen, SM);
  1280. // report
  1281. if (!MatchResult) {
  1282. PrintNoMatch(true, SM, *this, i, MatchBuffer, Req.VerboseVerbose, Diags,
  1283. MatchResult.takeError());
  1284. return StringRef::npos;
  1285. }
  1286. size_t MatchPos = *MatchResult;
  1287. PrintMatch(true, SM, *this, i, MatchBuffer, MatchPos, CurrentMatchLen, Req,
  1288. Diags);
  1289. if (i == 1)
  1290. FirstMatchPos = LastPos + MatchPos;
  1291. // move start point after the match
  1292. LastMatchEnd += MatchPos + CurrentMatchLen;
  1293. }
  1294. // Full match len counts from first match pos.
  1295. MatchLen = LastMatchEnd - FirstMatchPos;
  1296. // Similar to the above, in "label-scan mode" we can't yet handle CHECK-NEXT
  1297. // or CHECK-NOT
  1298. if (!IsLabelScanMode) {
  1299. size_t MatchPos = FirstMatchPos - LastPos;
  1300. StringRef MatchBuffer = Buffer.substr(LastPos);
  1301. StringRef SkippedRegion = Buffer.substr(LastPos, MatchPos);
  1302. // If this check is a "CHECK-NEXT", verify that the previous match was on
  1303. // the previous line (i.e. that there is one newline between them).
  1304. if (CheckNext(SM, SkippedRegion)) {
  1305. ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
  1306. Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
  1307. Diags, Req.Verbose);
  1308. return StringRef::npos;
  1309. }
  1310. // If this check is a "CHECK-SAME", verify that the previous match was on
  1311. // the same line (i.e. that there is no newline between them).
  1312. if (CheckSame(SM, SkippedRegion)) {
  1313. ProcessMatchResult(FileCheckDiag::MatchFoundButWrongLine, SM, Loc,
  1314. Pat.getCheckTy(), MatchBuffer, MatchPos, MatchLen,
  1315. Diags, Req.Verbose);
  1316. return StringRef::npos;
  1317. }
  1318. // If this match had "not strings", verify that they don't exist in the
  1319. // skipped region.
  1320. if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))
  1321. return StringRef::npos;
  1322. }
  1323. return FirstMatchPos;
  1324. }
  1325. bool FileCheckString::CheckNext(const SourceMgr &SM, StringRef Buffer) const {
  1326. if (Pat.getCheckTy() != Check::CheckNext &&
  1327. Pat.getCheckTy() != Check::CheckEmpty)
  1328. return false;
  1329. Twine CheckName =
  1330. Prefix +
  1331. Twine(Pat.getCheckTy() == Check::CheckEmpty ? "-EMPTY" : "-NEXT");
  1332. // Count the number of newlines between the previous match and this one.
  1333. const char *FirstNewLine = nullptr;
  1334. unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
  1335. if (NumNewLines == 0) {
  1336. SM.PrintMessage(Loc, SourceMgr::DK_Error,
  1337. CheckName + ": is on the same line as previous match");
  1338. SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
  1339. "'next' match was here");
  1340. SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
  1341. "previous match ended here");
  1342. return true;
  1343. }
  1344. if (NumNewLines != 1) {
  1345. SM.PrintMessage(Loc, SourceMgr::DK_Error,
  1346. CheckName +
  1347. ": is not on the line after the previous match");
  1348. SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
  1349. "'next' match was here");
  1350. SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
  1351. "previous match ended here");
  1352. SM.PrintMessage(SMLoc::getFromPointer(FirstNewLine), SourceMgr::DK_Note,
  1353. "non-matching line after previous match is here");
  1354. return true;
  1355. }
  1356. return false;
  1357. }
  1358. bool FileCheckString::CheckSame(const SourceMgr &SM, StringRef Buffer) const {
  1359. if (Pat.getCheckTy() != Check::CheckSame)
  1360. return false;
  1361. // Count the number of newlines between the previous match and this one.
  1362. const char *FirstNewLine = nullptr;
  1363. unsigned NumNewLines = CountNumNewlinesBetween(Buffer, FirstNewLine);
  1364. if (NumNewLines != 0) {
  1365. SM.PrintMessage(Loc, SourceMgr::DK_Error,
  1366. Prefix +
  1367. "-SAME: is not on the same line as the previous match");
  1368. SM.PrintMessage(SMLoc::getFromPointer(Buffer.end()), SourceMgr::DK_Note,
  1369. "'next' match was here");
  1370. SM.PrintMessage(SMLoc::getFromPointer(Buffer.data()), SourceMgr::DK_Note,
  1371. "previous match ended here");
  1372. return true;
  1373. }
  1374. return false;
  1375. }
  1376. bool FileCheckString::CheckNot(
  1377. const SourceMgr &SM, StringRef Buffer,
  1378. const std::vector<const FileCheckPattern *> &NotStrings,
  1379. const FileCheckRequest &Req, std::vector<FileCheckDiag> *Diags) const {
  1380. for (const FileCheckPattern *Pat : NotStrings) {
  1381. assert((Pat->getCheckTy() == Check::CheckNot) && "Expect CHECK-NOT!");
  1382. size_t MatchLen = 0;
  1383. Expected<size_t> MatchResult = Pat->match(Buffer, MatchLen, SM);
  1384. if (!MatchResult) {
  1385. PrintNoMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer,
  1386. Req.VerboseVerbose, Diags, MatchResult.takeError());
  1387. continue;
  1388. }
  1389. size_t Pos = *MatchResult;
  1390. PrintMatch(false, SM, Prefix, Pat->getLoc(), *Pat, 1, Buffer, Pos, MatchLen,
  1391. Req, Diags);
  1392. return true;
  1393. }
  1394. return false;
  1395. }
  1396. size_t
  1397. FileCheckString::CheckDag(const SourceMgr &SM, StringRef Buffer,
  1398. std::vector<const FileCheckPattern *> &NotStrings,
  1399. const FileCheckRequest &Req,
  1400. std::vector<FileCheckDiag> *Diags) const {
  1401. if (DagNotStrings.empty())
  1402. return 0;
  1403. // The start of the search range.
  1404. size_t StartPos = 0;
  1405. struct MatchRange {
  1406. size_t Pos;
  1407. size_t End;
  1408. };
  1409. // A sorted list of ranges for non-overlapping CHECK-DAG matches. Match
  1410. // ranges are erased from this list once they are no longer in the search
  1411. // range.
  1412. std::list<MatchRange> MatchRanges;
  1413. // We need PatItr and PatEnd later for detecting the end of a CHECK-DAG
  1414. // group, so we don't use a range-based for loop here.
  1415. for (auto PatItr = DagNotStrings.begin(), PatEnd = DagNotStrings.end();
  1416. PatItr != PatEnd; ++PatItr) {
  1417. const FileCheckPattern &Pat = *PatItr;
  1418. assert((Pat.getCheckTy() == Check::CheckDAG ||
  1419. Pat.getCheckTy() == Check::CheckNot) &&
  1420. "Invalid CHECK-DAG or CHECK-NOT!");
  1421. if (Pat.getCheckTy() == Check::CheckNot) {
  1422. NotStrings.push_back(&Pat);
  1423. continue;
  1424. }
  1425. assert((Pat.getCheckTy() == Check::CheckDAG) && "Expect CHECK-DAG!");
  1426. // CHECK-DAG always matches from the start.
  1427. size_t MatchLen = 0, MatchPos = StartPos;
  1428. // Search for a match that doesn't overlap a previous match in this
  1429. // CHECK-DAG group.
  1430. for (auto MI = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) {
  1431. StringRef MatchBuffer = Buffer.substr(MatchPos);
  1432. Expected<size_t> MatchResult = Pat.match(MatchBuffer, MatchLen, SM);
  1433. // With a group of CHECK-DAGs, a single mismatching means the match on
  1434. // that group of CHECK-DAGs fails immediately.
  1435. if (!MatchResult) {
  1436. PrintNoMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, MatchBuffer,
  1437. Req.VerboseVerbose, Diags, MatchResult.takeError());
  1438. return StringRef::npos;
  1439. }
  1440. size_t MatchPosBuf = *MatchResult;
  1441. // Re-calc it as the offset relative to the start of the original string.
  1442. MatchPos += MatchPosBuf;
  1443. if (Req.VerboseVerbose)
  1444. PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,
  1445. MatchLen, Req, Diags);
  1446. MatchRange M{MatchPos, MatchPos + MatchLen};
  1447. if (Req.AllowDeprecatedDagOverlap) {
  1448. // We don't need to track all matches in this mode, so we just maintain
  1449. // one match range that encompasses the current CHECK-DAG group's
  1450. // matches.
  1451. if (MatchRanges.empty())
  1452. MatchRanges.insert(MatchRanges.end(), M);
  1453. else {
  1454. auto Block = MatchRanges.begin();
  1455. Block->Pos = std::min(Block->Pos, M.Pos);
  1456. Block->End = std::max(Block->End, M.End);
  1457. }
  1458. break;
  1459. }
  1460. // Iterate previous matches until overlapping match or insertion point.
  1461. bool Overlap = false;
  1462. for (; MI != ME; ++MI) {
  1463. if (M.Pos < MI->End) {
  1464. // !Overlap => New match has no overlap and is before this old match.
  1465. // Overlap => New match overlaps this old match.
  1466. Overlap = MI->Pos < M.End;
  1467. break;
  1468. }
  1469. }
  1470. if (!Overlap) {
  1471. // Insert non-overlapping match into list.
  1472. MatchRanges.insert(MI, M);
  1473. break;
  1474. }
  1475. if (Req.VerboseVerbose) {
  1476. // Due to their verbosity, we don't print verbose diagnostics here if
  1477. // we're gathering them for a different rendering, but we always print
  1478. // other diagnostics.
  1479. if (!Diags) {
  1480. SMLoc OldStart = SMLoc::getFromPointer(Buffer.data() + MI->Pos);
  1481. SMLoc OldEnd = SMLoc::getFromPointer(Buffer.data() + MI->End);
  1482. SMRange OldRange(OldStart, OldEnd);
  1483. SM.PrintMessage(OldStart, SourceMgr::DK_Note,
  1484. "match discarded, overlaps earlier DAG match here",
  1485. {OldRange});
  1486. } else
  1487. Diags->rbegin()->MatchTy = FileCheckDiag::MatchFoundButDiscarded;
  1488. }
  1489. MatchPos = MI->End;
  1490. }
  1491. if (!Req.VerboseVerbose)
  1492. PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, 1, Buffer, MatchPos,
  1493. MatchLen, Req, Diags);
  1494. // Handle the end of a CHECK-DAG group.
  1495. if (std::next(PatItr) == PatEnd ||
  1496. std::next(PatItr)->getCheckTy() == Check::CheckNot) {
  1497. if (!NotStrings.empty()) {
  1498. // If there are CHECK-NOTs between two CHECK-DAGs or from CHECK to
  1499. // CHECK-DAG, verify that there are no 'not' strings occurred in that
  1500. // region.
  1501. StringRef SkippedRegion =
  1502. Buffer.slice(StartPos, MatchRanges.begin()->Pos);
  1503. if (CheckNot(SM, SkippedRegion, NotStrings, Req, Diags))
  1504. return StringRef::npos;
  1505. // Clear "not strings".
  1506. NotStrings.clear();
  1507. }
  1508. // All subsequent CHECK-DAGs and CHECK-NOTs should be matched from the
  1509. // end of this CHECK-DAG group's match range.
  1510. StartPos = MatchRanges.rbegin()->End;
  1511. // Don't waste time checking for (impossible) overlaps before that.
  1512. MatchRanges.clear();
  1513. }
  1514. }
  1515. return StartPos;
  1516. }
  1517. // A check prefix must contain only alphanumeric, hyphens and underscores.
  1518. static bool ValidateCheckPrefix(StringRef CheckPrefix) {
  1519. Regex Validator("^[a-zA-Z0-9_-]*$");
  1520. return Validator.match(CheckPrefix);
  1521. }
  1522. bool FileCheck::ValidateCheckPrefixes() {
  1523. StringSet<> PrefixSet;
  1524. for (StringRef Prefix : Req.CheckPrefixes) {
  1525. // Reject empty prefixes.
  1526. if (Prefix == "")
  1527. return false;
  1528. if (!PrefixSet.insert(Prefix).second)
  1529. return false;
  1530. if (!ValidateCheckPrefix(Prefix))
  1531. return false;
  1532. }
  1533. return true;
  1534. }
  1535. Regex FileCheck::buildCheckPrefixRegex() {
  1536. // I don't think there's a way to specify an initial value for cl::list,
  1537. // so if nothing was specified, add the default
  1538. if (Req.CheckPrefixes.empty())
  1539. Req.CheckPrefixes.push_back("CHECK");
  1540. // We already validated the contents of CheckPrefixes so just concatenate
  1541. // them as alternatives.
  1542. SmallString<32> PrefixRegexStr;
  1543. for (StringRef Prefix : Req.CheckPrefixes) {
  1544. if (Prefix != Req.CheckPrefixes.front())
  1545. PrefixRegexStr.push_back('|');
  1546. PrefixRegexStr.append(Prefix);
  1547. }
  1548. return Regex(PrefixRegexStr);
  1549. }
  1550. Error FileCheckPatternContext::defineCmdlineVariables(
  1551. std::vector<std::string> &CmdlineDefines, SourceMgr &SM) {
  1552. assert(GlobalVariableTable.empty() && GlobalNumericVariableTable.empty() &&
  1553. "Overriding defined variable with command-line variable definitions");
  1554. if (CmdlineDefines.empty())
  1555. return Error::success();
  1556. // Create a string representing the vector of command-line definitions. Each
  1557. // definition is on its own line and prefixed with a definition number to
  1558. // clarify which definition a given diagnostic corresponds to.
  1559. unsigned I = 0;
  1560. Error Errs = Error::success();
  1561. std::string CmdlineDefsDiag;
  1562. SmallVector<std::pair<size_t, size_t>, 4> CmdlineDefsIndices;
  1563. for (StringRef CmdlineDef : CmdlineDefines) {
  1564. std::string DefPrefix = ("Global define #" + Twine(++I) + ": ").str();
  1565. size_t EqIdx = CmdlineDef.find('=');
  1566. if (EqIdx == StringRef::npos) {
  1567. CmdlineDefsIndices.push_back(std::make_pair(CmdlineDefsDiag.size(), 0));
  1568. continue;
  1569. }
  1570. // Numeric variable definition.
  1571. if (CmdlineDef[0] == '#') {
  1572. // Append a copy of the command-line definition adapted to use the same
  1573. // format as in the input file to be able to reuse
  1574. // parseNumericSubstitutionBlock.
  1575. CmdlineDefsDiag += (DefPrefix + CmdlineDef + " (parsed as: [[").str();
  1576. std::string SubstitutionStr = CmdlineDef;
  1577. SubstitutionStr[EqIdx] = ':';
  1578. CmdlineDefsIndices.push_back(
  1579. std::make_pair(CmdlineDefsDiag.size(), SubstitutionStr.size()));
  1580. CmdlineDefsDiag += (SubstitutionStr + Twine("]])\n")).str();
  1581. } else {
  1582. CmdlineDefsDiag += DefPrefix;
  1583. CmdlineDefsIndices.push_back(
  1584. std::make_pair(CmdlineDefsDiag.size(), CmdlineDef.size()));
  1585. CmdlineDefsDiag += (CmdlineDef + "\n").str();
  1586. }
  1587. }
  1588. // Create a buffer with fake command line content in order to display
  1589. // parsing diagnostic with location information and point to the
  1590. // global definition with invalid syntax.
  1591. std::unique_ptr<MemoryBuffer> CmdLineDefsDiagBuffer =
  1592. MemoryBuffer::getMemBufferCopy(CmdlineDefsDiag, "Global defines");
  1593. StringRef CmdlineDefsDiagRef = CmdLineDefsDiagBuffer->getBuffer();
  1594. SM.AddNewSourceBuffer(std::move(CmdLineDefsDiagBuffer), SMLoc());
  1595. for (std::pair<size_t, size_t> CmdlineDefIndices : CmdlineDefsIndices) {
  1596. StringRef CmdlineDef = CmdlineDefsDiagRef.substr(CmdlineDefIndices.first,
  1597. CmdlineDefIndices.second);
  1598. if (CmdlineDef.empty()) {
  1599. Errs = joinErrors(
  1600. std::move(Errs),
  1601. FileCheckErrorDiagnostic::get(
  1602. SM, CmdlineDef, "missing equal sign in global definition"));
  1603. continue;
  1604. }
  1605. // Numeric variable definition.
  1606. if (CmdlineDef[0] == '#') {
  1607. // Now parse the definition both to check that the syntax is correct and
  1608. // to create the necessary class instance.
  1609. StringRef CmdlineDefExpr = CmdlineDef.substr(1);
  1610. Optional<FileCheckNumericVariable *> DefinedNumericVariable;
  1611. Expected<std::unique_ptr<FileCheckExpressionAST>> ExpressionASTResult =
  1612. FileCheckPattern::parseNumericSubstitutionBlock(
  1613. CmdlineDefExpr, DefinedNumericVariable, false, None, this, SM);
  1614. if (!ExpressionASTResult) {
  1615. Errs = joinErrors(std::move(Errs), ExpressionASTResult.takeError());
  1616. continue;
  1617. }
  1618. std::unique_ptr<FileCheckExpressionAST> ExpressionAST =
  1619. std::move(*ExpressionASTResult);
  1620. // Now evaluate the expression whose value this variable should be set
  1621. // to, since the expression of a command-line variable definition should
  1622. // only use variables defined earlier on the command-line. If not, this
  1623. // is an error and we report it.
  1624. Expected<uint64_t> Value = ExpressionAST->eval();
  1625. if (!Value) {
  1626. Errs = joinErrors(std::move(Errs), Value.takeError());
  1627. continue;
  1628. }
  1629. assert(DefinedNumericVariable && "No variable defined");
  1630. (*DefinedNumericVariable)->setValue(*Value);
  1631. // Record this variable definition.
  1632. GlobalNumericVariableTable[(*DefinedNumericVariable)->getName()] =
  1633. *DefinedNumericVariable;
  1634. } else {
  1635. // String variable definition.
  1636. std::pair<StringRef, StringRef> CmdlineNameVal = CmdlineDef.split('=');
  1637. StringRef CmdlineName = CmdlineNameVal.first;
  1638. StringRef OrigCmdlineName = CmdlineName;
  1639. Expected<FileCheckPattern::VariableProperties> ParseVarResult =
  1640. FileCheckPattern::parseVariable(CmdlineName, SM);
  1641. if (!ParseVarResult) {
  1642. Errs = joinErrors(std::move(Errs), ParseVarResult.takeError());
  1643. continue;
  1644. }
  1645. // Check that CmdlineName does not denote a pseudo variable is only
  1646. // composed of the parsed numeric variable. This catches cases like
  1647. // "FOO+2" in a "FOO+2=10" definition.
  1648. if (ParseVarResult->IsPseudo || !CmdlineName.empty()) {
  1649. Errs = joinErrors(std::move(Errs),
  1650. FileCheckErrorDiagnostic::get(
  1651. SM, OrigCmdlineName,
  1652. "invalid name in string variable definition '" +
  1653. OrigCmdlineName + "'"));
  1654. continue;
  1655. }
  1656. StringRef Name = ParseVarResult->Name;
  1657. // Detect collisions between string and numeric variables when the former
  1658. // is created later than the latter.
  1659. if (GlobalNumericVariableTable.find(Name) !=
  1660. GlobalNumericVariableTable.end()) {
  1661. Errs = joinErrors(std::move(Errs), FileCheckErrorDiagnostic::get(
  1662. SM, Name,
  1663. "numeric variable with name '" +
  1664. Name + "' already exists"));
  1665. continue;
  1666. }
  1667. GlobalVariableTable.insert(CmdlineNameVal);
  1668. // Mark the string variable as defined to detect collisions between
  1669. // string and numeric variables in defineCmdlineVariables when the latter
  1670. // is created later than the former. We cannot reuse GlobalVariableTable
  1671. // for this by populating it with an empty string since we would then
  1672. // lose the ability to detect the use of an undefined variable in
  1673. // match().
  1674. DefinedVariableTable[Name] = true;
  1675. }
  1676. }
  1677. return Errs;
  1678. }
  1679. void FileCheckPatternContext::clearLocalVars() {
  1680. SmallVector<StringRef, 16> LocalPatternVars, LocalNumericVars;
  1681. for (const StringMapEntry<StringRef> &Var : GlobalVariableTable)
  1682. if (Var.first()[0] != '$')
  1683. LocalPatternVars.push_back(Var.first());
  1684. // Numeric substitution reads the value of a variable directly, not via
  1685. // GlobalNumericVariableTable. Therefore, we clear local variables by
  1686. // clearing their value which will lead to a numeric substitution failure. We
  1687. // also mark the variable for removal from GlobalNumericVariableTable since
  1688. // this is what defineCmdlineVariables checks to decide that no global
  1689. // variable has been defined.
  1690. for (const auto &Var : GlobalNumericVariableTable)
  1691. if (Var.first()[0] != '$') {
  1692. Var.getValue()->clearValue();
  1693. LocalNumericVars.push_back(Var.first());
  1694. }
  1695. for (const auto &Var : LocalPatternVars)
  1696. GlobalVariableTable.erase(Var);
  1697. for (const auto &Var : LocalNumericVars)
  1698. GlobalNumericVariableTable.erase(Var);
  1699. }
  1700. bool FileCheck::CheckInput(SourceMgr &SM, StringRef Buffer,
  1701. ArrayRef<FileCheckString> CheckStrings,
  1702. std::vector<FileCheckDiag> *Diags) {
  1703. bool ChecksFailed = false;
  1704. unsigned i = 0, j = 0, e = CheckStrings.size();
  1705. while (true) {
  1706. StringRef CheckRegion;
  1707. if (j == e) {
  1708. CheckRegion = Buffer;
  1709. } else {
  1710. const FileCheckString &CheckLabelStr = CheckStrings[j];
  1711. if (CheckLabelStr.Pat.getCheckTy() != Check::CheckLabel) {
  1712. ++j;
  1713. continue;
  1714. }
  1715. // Scan to next CHECK-LABEL match, ignoring CHECK-NOT and CHECK-DAG
  1716. size_t MatchLabelLen = 0;
  1717. size_t MatchLabelPos =
  1718. CheckLabelStr.Check(SM, Buffer, true, MatchLabelLen, Req, Diags);
  1719. if (MatchLabelPos == StringRef::npos)
  1720. // Immediately bail if CHECK-LABEL fails, nothing else we can do.
  1721. return false;
  1722. CheckRegion = Buffer.substr(0, MatchLabelPos + MatchLabelLen);
  1723. Buffer = Buffer.substr(MatchLabelPos + MatchLabelLen);
  1724. ++j;
  1725. }
  1726. // Do not clear the first region as it's the one before the first
  1727. // CHECK-LABEL and it would clear variables defined on the command-line
  1728. // before they get used.
  1729. if (i != 0 && Req.EnableVarScope)
  1730. PatternContext.clearLocalVars();
  1731. for (; i != j; ++i) {
  1732. const FileCheckString &CheckStr = CheckStrings[i];
  1733. // Check each string within the scanned region, including a second check
  1734. // of any final CHECK-LABEL (to verify CHECK-NOT and CHECK-DAG)
  1735. size_t MatchLen = 0;
  1736. size_t MatchPos =
  1737. CheckStr.Check(SM, CheckRegion, false, MatchLen, Req, Diags);
  1738. if (MatchPos == StringRef::npos) {
  1739. ChecksFailed = true;
  1740. i = j;
  1741. break;
  1742. }
  1743. CheckRegion = CheckRegion.substr(MatchPos + MatchLen);
  1744. }
  1745. if (j == e)
  1746. break;
  1747. }
  1748. // Success if no checks failed.
  1749. return !ChecksFailed;
  1750. }