Index: llvm/trunk/test/FileCheck/check-dag-not-dag.txt =================================================================== --- llvm/trunk/test/FileCheck/check-dag-not-dag.txt +++ llvm/trunk/test/FileCheck/check-dag-not-dag.txt @@ -0,0 +1,76 @@ +;--------------------------------------------------------------------- +; RUN: FileCheck -input-file %s %s -check-prefix=NotSearchEnd + +The search range for the NOTs used to end at the start of the match range for +the first DAG in the following DAG group. Now it ends at the start of the +match range for the entire following DAG group. + +__NotSearchEnd +x0 +x1 + +y1 +foobar +y0 + +z2 +foobar +z1 +foobar +z0 +__NotSearchEnd + +; NotSearchEnd: {{^}}__NotSearchEnd +; NotSearchEnd-DAG: {{^}}x0 +; NotSearchEnd-DAG: {{^}}x1 +; NotSearchEnd-NOT: {{^}}foobar +; NotSearchEnd-DAG: {{^}}y0 +; NotSearchEnd-DAG: {{^}}y1 +; NotSearchEnd-NOT: {{^}}foobar +; NotSearchEnd-DAG: {{^}}z0 +; NotSearchEnd-DAG: {{^}}z1 +; NotSearchEnd-DAG: {{^}}z2 +; NotSearchEnd: {{^}}__NotSearchEnd + +;--------------------------------------------------------------------- +; RUN: FileCheck -input-file %s %s -check-prefix=Dag2SearchStart + +The start of the search range for the second or later DAG group used to be +different for its first DAG than its other DAGs. For the first DAG, it was +the start of the permitted range for the preceding DAG group, and there was a +reordering complaint if the match range was in the first DAG group's match +range. For the other DAGs, it was the end of the match range for the +preceding DAG group, so reordering detection wasn't possible. Now, the +first DAG behaves like the others, and so reordering detection is no longer +implemented. As a result, matches that used to produce the reordering +complaint are now skipped, permitting later matches to succeed. + +__Dag2SearchStart +y0 +y1 +x0 +y0 +y1 +x1 + +z1 +z0 +y1 +z1 +z0 +y0 + +z0 +z1 +__Dag2SearchStart + +; Dag2SearchStart: {{^}}__Dag2SearchStart +; Dag2SearchStart-DAG: {{^}}x0 +; Dag2SearchStart-DAG: {{^}}x1 +; Dag2SearchStart-NOT: {{^}}foobar +; Dag2SearchStart-DAG: {{^}}y0 +; Dag2SearchStart-DAG: {{^}}y1 +; Dag2SearchStart-NOT: {{^}}foobar +; Dag2SearchStart-DAG: {{^}}z0 +; Dag2SearchStart-DAG: {{^}}z1 +; Dag2SearchStart: {{^}}__Dag2SearchStart \ No newline at end of file Index: llvm/trunk/test/FileCheck/check-dag-overlap.txt =================================================================== --- llvm/trunk/test/FileCheck/check-dag-overlap.txt +++ llvm/trunk/test/FileCheck/check-dag-overlap.txt @@ -168,7 +168,8 @@ the DAG groups such that the leading DAGs are x, y, and z. y won't match overlaps with matches from: -1. X. Otherwise, we could get a spurious reordering complaint. +1. X. Otherwise, we used to get a spurious reordering complaint (back + when reordering complaints on DAG-NOT-DAG were still implemented). 2. Y, because y is in Y. To prevent these overlaps, the implementation must be careful not to drop y's match from the previous matches list when it drops matches from X to save search time. Index: llvm/trunk/utils/FileCheck/FileCheck.cpp =================================================================== --- llvm/trunk/utils/FileCheck/FileCheck.cpp +++ llvm/trunk/utils/FileCheck/FileCheck.cpp @@ -1283,17 +1283,23 @@ if (DagNotStrings.empty()) return 0; - size_t LastPos = 0; - size_t StartPos = LastPos; + // The start of the search range. + size_t StartPos = 0; - // A sorted list of ranges for non-overlapping dag matches. - struct Match { + struct MatchRange { size_t Pos; size_t End; }; - std::list Matches; - - for (const Pattern &Pat : DagNotStrings) { + // A sorted list of ranges for non-overlapping CHECK-DAG matches. Match + // ranges are erased from this list once they are no longer in the search + // range. + std::list MatchRanges; + + // We need PatItr and PatEnd later for detecting the end of a CHECK-DAG + // group, so we don't use a range-based for loop here. + for (auto PatItr = DagNotStrings.begin(), PatEnd = DagNotStrings.end(); + PatItr != PatEnd; ++PatItr) { + const Pattern &Pat = *PatItr; assert((Pat.getCheckTy() == Check::CheckDAG || Pat.getCheckTy() == Check::CheckNot) && "Invalid CHECK-DAG or CHECK-NOT!"); @@ -1310,7 +1316,7 @@ // Search for a match that doesn't overlap a previous match in this // CHECK-DAG group. - for (auto MI = Matches.begin(), ME = Matches.end(); true; ++MI) { + for (auto MI = MatchRanges.begin(), ME = MatchRanges.end(); true; ++MI) { StringRef MatchBuffer = Buffer.substr(MatchPos); size_t MatchPosBuf = Pat.Match(MatchBuffer, MatchLen, VariableTable); // With a group of CHECK-DAGs, a single mismatching means the match on @@ -1325,10 +1331,21 @@ if (VerboseVerbose) PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, Buffer, VariableTable, MatchPos, MatchLen); - if (AllowDeprecatedDagOverlap) + MatchRange M{MatchPos, MatchPos + MatchLen}; + if (AllowDeprecatedDagOverlap) { + // We don't need to track all matches in this mode, so we just maintain + // one match range that encompasses the current CHECK-DAG group's + // matches. + if (MatchRanges.empty()) + MatchRanges.insert(MatchRanges.end(), M); + else { + auto Block = MatchRanges.begin(); + Block->Pos = std::min(Block->Pos, M.Pos); + Block->End = std::max(Block->End, M.End); + } break; + } // Iterate previous matches until overlapping match or insertion point. - Match M{MatchPos, MatchPos + MatchLen}; bool Overlap = false; for (; MI != ME; ++MI) { if (M.Pos < MI->End) { @@ -1340,7 +1357,7 @@ } if (!Overlap) { // Insert non-overlapping match into list. - Matches.insert(MI, M); + MatchRanges.insert(MI, M); break; } if (VerboseVerbose) { @@ -1357,46 +1374,29 @@ PrintMatch(true, SM, Prefix, Pat.getLoc(), Pat, Buffer, VariableTable, MatchPos, MatchLen); - if (!NotStrings.empty()) { - if (MatchPos < LastPos) { - // Reordered? - SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + MatchPos), - SourceMgr::DK_Error, - Prefix + "-DAG: found a match of CHECK-DAG" - " reordering across a CHECK-NOT"); - SM.PrintMessage(SMLoc::getFromPointer(Buffer.data() + LastPos), - SourceMgr::DK_Note, - Prefix + "-DAG: the farthest match of CHECK-DAG" - " is found here"); - SM.PrintMessage(NotStrings[0]->getLoc(), SourceMgr::DK_Note, - Prefix + "-NOT: the crossed pattern specified" - " here"); - SM.PrintMessage(Pat.getLoc(), SourceMgr::DK_Note, - Prefix + "-DAG: the reordered pattern specified" - " here"); - return StringRef::npos; + // Handle the end of a CHECK-DAG group. + if (std::next(PatItr) == PatEnd || + std::next(PatItr)->getCheckTy() == Check::CheckNot) { + if (!NotStrings.empty()) { + // If there are CHECK-NOTs between two CHECK-DAGs or from CHECK to + // CHECK-DAG, verify that there are no 'not' strings occurred in that + // region. + StringRef SkippedRegion = + Buffer.slice(StartPos, MatchRanges.begin()->Pos); + if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable)) + return StringRef::npos; + // Clear "not strings". + NotStrings.clear(); } - // All subsequent CHECK-DAGs should be matched from the farthest - // position of all precedent CHECK-DAGs (not including this one). - StartPos = LastPos; + // All subsequent CHECK-DAGs and CHECK-NOTs should be matched from the + // end of this CHECK-DAG group's match range. + StartPos = MatchRanges.rbegin()->End; // Don't waste time checking for (impossible) overlaps before that. - Matches.clear(); - Matches.push_back(Match{MatchPos, MatchPos + MatchLen}); - // If there's CHECK-NOTs between two CHECK-DAGs or from CHECK to - // CHECK-DAG, verify that there's no 'not' strings occurred in that - // region. - StringRef SkippedRegion = Buffer.slice(LastPos, MatchPos); - if (CheckNot(SM, SkippedRegion, NotStrings, VariableTable)) - return StringRef::npos; - // Clear "not strings". - NotStrings.clear(); + MatchRanges.clear(); } - - // Update the last position with CHECK-DAG matches. - LastPos = std::max(MatchPos + MatchLen, LastPos); } - return LastPos; + return StartPos; } // A check prefix must contain only alphanumeric, hyphens and underscores.