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<Match> 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<MatchRange> 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.