<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">Hi Paul,<br></div><div class="gmail_quote"><br></div><div class="gmail_quote">On Thu, May 24, 2018 at 9:46 AM,  <span dir="ltr"><<a href="mailto:paul.robinson@sony.com" target="_blank">paul.robinson@sony.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Background<br>
----------<br>
<br>
FileCheck [0] is a cornerstone testing tool for the LLVM project.  It<br>
has grown new features over the years to meet new needs, but these<br>
sometimes have surprising and counter-intuitive behavior [1].  This<br>
has become even more evident in Joel Denny's recent quest to repair<br>
what seemed like an obvious defect [2] but which led me to the<br>
conclusion [3] that FileCheck sorely needed a clear, intuitive<br>
conceptual model. </blockquote><div><br></div><div>Agreed.  Thanks for doing this.<br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> And then someone to make it work that way (hi<br>
Joel!).<br></blockquote><div><br></div><div>Sure, I can help with the implementation given that I'm running into these issues a lot in my own work.  As I'm a bit too close to the FileCheck implementation at this point, I would suggest that someone else write the initial specification-based tests to find the deviations from the description we arrive at.  Paul, you're the obvious person for that one.  I can of course work on further implementation-based testing.</div><div><br></div><div>I also recommend we make changes toward the new specification incrementally.</div><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Basic Conceptual Model<br>
----------------------<br>
<br>
FileCheck should operate on the basis of these three fundamental<br>
concepts.<br>
<br>
(1) Search range.  This is some substring of the input text where one<br>
or more directives will do their pattern-matching magic.<br>
<br>
(2) Match range.  This is a substring of a search range where a<br>
directive (or in one case, a group of directives) has matched a<br>
pattern.<br>
<br>
(3) Directive groups.  These are sequences of adjacent directives that<br>
operate in a related way on a search range.  Directives within a group<br>
are processed in order, except as noted in the directive description.<br>
<br>
Finally we add The Rule:  No match ranges may overlap.<br>
<br>
(This is largely formalizing what FileCheck already does, except that<br>
it didn't have The Rule with respect to DAG matches.  That's the bug<br>
that Joel was originally trying to fix, until I stuck my nose into<br>
it.)<br></blockquote><div> </div>I agree with The Rule.  I haven't found any real use case yet that needs to violate that rule.<br></div><div class="gmail_quote"><div> <br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Directive Descriptions Based On Conceptual Model<br>
------------------------------<wbr>------------------<br>
<br>
Given the conceptual model, all directives can be defined in terms of<br>
it. This is possibly going overboard with the formalism but hey, we're<br>
all compiler geeks here.<br></blockquote><div><br></div><div>I think it's great.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
CHECK: Scans the search range for a pattern match. Fails if no match<br>
is found.  The end of the match range becomes the start of the search<br>
range for subsequent directives.<br>
<br>
CHECK-SAME: Like CHECK, plus there must be zero newlines prior to the<br>
start of the match range.<br></blockquote><div><br></div><div></div><div>... within the search range.</div><div><br></div><div>Should it be possible for CHECK-SAME match range to include newlines?<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
CHECK-NEXT: Like CHECK, plus there must be exactly one newline prior<br>
to the start of the match range.<br></blockquote><div><br></div><div>... within the search range.<br></div><div><br></div><div>Your choice to talk about the match range rather than the search range for CHECK-SAME and CHECK-NEXT implies you like the current behavior that extends the search range beyond these match range restrictions and then complains if the match range restrictions aren't met.  For example, CHECK-SAME searches past the newline and then complains if the match range starts after the newline.  Is that what you prefer?</div><div><br></div><div>I'd note that, in the case of CHECK-NEXT, that choice can restrict what CHECK-NEXT can match.  That is, it will complain about a match on the previous line rather than skip it and look on the next line.<br></div><div></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
CHECK-LABEL: All LABEL directives are processed before any other<br>
directives.  These directives have two effects.  First, they act like<br>
CHECK directives, but also partition the input text into disjoint<br>
search ranges, delimited by the match ranges of the LABEL directives.<br>
Second, they partition the remaining directives into Label Groups,<br>
each of which operates on the corresponding search range.  For truly<br>
pedantic formalism, we can say there are implicit LABEL directives<br>
matching the start and end of the entire input text, thus all<br>
non-LABEL directives are always in some Label Group.<br>
<br>
CHECK-NOT: A sequence of NOT directives forms a NOT Group. The group<br>
is not executed immediately; instead the next non-NOT directive is<br>
executed first, and the start of that directive's match range becomes<br>
the end of the NOT Group's search range.</blockquote><div><br></div><div>Based on the following, that wording is not quite right when a DAG group follows, so there should probably be some note about that here.<br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">  (If the next directive is<br>
LABEL, it has already executed and has a match range, which is already<br>
the end of the search range.)  After the NOT Group's search range is<br>
defined, each NOT directive scans the range for a match, and fails if<br>
a match is found.<br></blockquote><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
CHECK-DAG: A sequence of DAG directives forms a DAG Group. The group<br>
is not executed immediately; instead the next non-DAG directive is<br>
executed first, and the start of that directive's match range becomes<br>
the end of the DAG Group's search range.</blockquote><div><br></div><div>That's definitely a change from the current behavior.  Currently, the DAG group finds its own end based on the farthest match.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">  If the next directive is<br>
CHECK-NOT, the end of the DAG Group's search range is<br>
unaffected.</blockquote><div><br></div><div>Unaffected means that it's as if there's no following directive?  So next CHECK-LABEL (possibly the implicit one at EOF)?  What if there's a CHECK, CHECK-NEXT, or CHECK-SAME after all the DAGs and NOTs?<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> (This might or might not be FileCheck's historical<br>
behavior; I didn't check.)  After the DAG Group's search range is<br>
defined, each DAG directive scans the range for a match, and fails if<br>
a match is not found.  Per The Rule, match ranges for DAG directives<br>
may not overlap. (This is not historical FileCheck behavior, and the<br>
bug Joel Denny wanted to fix.)  After all DAG directives run, the<br>
match range for the entire DAG Group extends from the start of the<br>
earliest match to the end of the latest match.  The end of that match<br>
range becomes the start of the search range for subsequent directives.<br></blockquote><div><br></div><div>That last sentence contradicts the first few sentences: the subsequent directive has already been matched.<br></div><div><br></div><div></div><div>One point not addressed here is the start of the DAG group's search range.  Currently, if the DAG group is preceded by a NOT group preceded by a DAG group, the last DAG group's search range starts at the start of the first DAG group's match range.  Any matches in the first DAG group's match range produces a reordering error.  This is somewhat similar to the CHECK-SAME and CHECK-NEXT behavior I mentioned earlier: the search ranges permit invalid match ranges and then complain about them in an effort to diagnose mistakes.  However, that restricts what can be matched.</div><div><br></div><div>I'm not claiming that either behavior is best.  It's not clear to me.  The best use of DAG-NOT-DAG is very confusing to me.  An effort to prescribe the right semantics to it needs to be informed by real use cases, in my opinion.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Observations<br>
------------<br>
<br>
A CHECK-NOT still separates surrounding CHECK-DAG directives into<br>
disjoint groups, and does not permit matches from the two groups to<br>
overlap. DAG was originally implemented to detect and diagnose an<br>
overlap, but this worked only for the first DAG after a NOT. This can<br>
lead to counter-intuitive behavior and potentially makes certain kinds<br>
of matches impossible.<br></blockquote><div><br></div><div>I definitely agree it shouldn't be just the first DAG.  The reordering detection should happen for all consecutive DAGs after the NOT or none of them.<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<br>
Putting CHECK-SAME and CHECK-NEXT after CHECK-DAG now has defined<br>
behavior, but it's unlikely to be useful.</blockquote><div><br></div><div>I believe they had predictable behavior before (their search ranges started at the end of the match range for the entire CHECK-DAG), but it's different with the above description (they define the end of the search range for the preceding CHECK-DAG group).</div><div><br></div><div>Thanks.</div><div><br></div><div>Joel<br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">  Putting SAME or NEXT as the<br>
first directive in a file likewise has defined behavior, matching<br>
precisely the first or second line (respectively) of the input text.<br>
<br>
<br>
References<br>
----------<br>
[0] <a href="https://llvm.org/docs/CommandGuide/FileCheck.html" rel="noreferrer" target="_blank">https://llvm.org/docs/CommandG<wbr>uide/FileCheck.html</a><br>
[1] <a href="https://www.youtube.com/watch?v=4rhW8knj0L8" rel="noreferrer" target="_blank">https://www.youtube.com/watch?<wbr>v=4rhW8knj0L8</a><br>
[2] <a href="https://lists.llvm.org/pipermail/llvm-dev/2018-May/123010.html" rel="noreferrer" target="_blank">https://lists.llvm.org/piperma<wbr>il/llvm-dev/2018-May/123010.<wbr>html</a><br>
[3] <a href="https://reviews.llvm.org/D47106" rel="noreferrer" target="_blank">https://reviews.llvm.org/D4710<wbr>6</a><br>
<br>
</blockquote></div><br></div></div>