[cfe-dev] RFC: Easier AST Matching by Default

[Dmitri Gribenko via cfe-dev]

On Sun, Jan 26, 2020 at 8:54 PM Stephen Kelly <steveire at gmail.com> wrote:

>
> On 17/01/2020 12:54, Dmitri Gribenko wrote:
>
> On Fri, Jan 17, 2020 at 12:41 PM Stephen Kelly <steveire at gmail.com> wrote:
>
>>
>> On 13/01/2020 16:39, Dmitri Gribenko wrote:
>>
>> On Fri, Jan 10, 2020 at 4:34 PM Aaron Ballman via cfe-dev <
>> cfe-dev at lists.llvm.org> wrote:
>>
>>> I've not seen much to suggest the community is not in favor of this
>>> direction, so I think you're all set to post patches for review. If
>>> there are community concerns, we can address them during the review
>>> process. Thank you for working on this!
>>>
>>
>> Sorry, I just came back from vacation. I'm not sure if it is a good idea,
>> in particular, for the following reasons:
>>
>> - The document specifies the goals in terms of a solution: "Goal: Users
>> should not have to account for implicit AST nodes when writing AST
>> Matchers".
>>
>>
>> The goal is to make AST Matchers more accessible/easy to use for
>> newcomers/non-experts in the clang AST by no-longer confronting them with
>> 100% of the complexity on first use.
>>
>> I think it's important to bridge that gap. See my EuroLLVM talk for more.
>>
> I totally agree with the goal of making AST Matchers, refactoring, and
> tooling more accessible (which is why I'm helping with libraries like
> Stencil and Syntax trees).
>
>
> This change affects AST Matchers, but as far as I can see, it does not
> affect any other effort.
>
> I don't see why you mention those initiatives in this and your other
> email. We're only talking about AST Matchers. Unless AST Matchers are to be
> removed, we should improve them, regardless of Syntax Tree, Stencil and
> Transformer.
>

I mention all of these libraries because people don't use AST matchers just
for the sake of it. People use AST matchers to achieve a high-level goal.
Therefore, we should be thinking of the whole user journey, not just the
individual piece. My point is that, we are working on better solutions for
the whole user journey. Those better solutions will allow to achieve the
same high-level goals more easily than today's tools, and (I think) even
more easily than *any* modification restricted to just AST matchers would
have allowed us to do.

>
> However the goal that I quoted from the proposal on this thread ("Goal:
> Users should not have to account for implicit AST nodes when writing AST
> Matchers") constrains the solution to exactly what is being proposed.
>
>
> Perhaps there's a misunderstanding. That's the goal of changing the
> default.
>
The goal should be something high-level that the user cares about, for
example, "more easily write refactoring tools". Individual technical
details are not meaningful as goals, because they don't have intrinsic
value from the perspective of end users, maintainers of Clang, maintainers
of libraries etc.

How do we evaluate whether the proposal to change the default traversal is
good or bad, if changing the default *is* the goal? It becomes a circular
argument: we want to change it because we want it so. The goal should be
stated in terms of a problem that the user is trying to solve.

>
> - The complexity for implementers (although it also applies to
>> https://reviews.llvm.org/D61837, which landed a while ago, and I didn't
>> see it). Allowing to run the same matcher in multiple modes increases our
>> support and testing matrix.
>>
>>
>> I don't think it increases the test matrix more than any other feature.
>> Can you expand on this?
>>
> https://reviews.llvm.org/D61837 makes it possible to run every matcher
> with different traversal semantics. Our current tests only test one mode
> for each matcher, the default mode. There are two ways to define custom
> matchers: the advanced way (through the AST_MATCHER macro) that is needed
> when you want to traverse the AST yourself, and a simpler way -- by
> combining existing matchers.
>
>
> AFAICT, defining a matcher using the macro, or defining it as a
> composition function doesn't change much?
>
When you define a matcher using a macro, you usually traverse the AST
yourself, by directly using Clang AST APIs. However, when you define a
matcher as a composition of other matchers, the user of your matcher can
affect the traversal mode *within your matcher* by calling your matcher
within traverse(). In other words, there is no abstraction barrier between
the matcher and the user.

> Consider the `makeIteratorLoopMatcher` defined in
> clang-tools-extra/clang-tidy/modernize/LoopConvertCheck.cpp. The caller can
> run the newly made matcher in any traversal mode, even though the matcher
> was probably written with the default mode in mind.
>
> Clang codebase does not have many matchers that are combinations of
> existing matchers
>
>
> It does actually - callee() for example. The fact that is uses a macro
> doesn't change anything AFAICT. Also alignOfExpr() which does not use a
> macro, but I don't see how that changes anything.
>
> Am I missing something?
>
I didn't say such matchers *don't exist* in Clang, I said there are not
many of them. And yes, these are the types of matchers I am concerned about
being affected by traverse().

callee and alignOfExpr() are not affected by traverse() because they only
match one level of AST nodes -- the call expression, or the alignof
expression, and pass down the inner matcher. Had they been traversing
multiple levels of AST nodes, they would have been affected by traverse(),
if the user called these matchers within traverse().

> , but code that uses Clang as a library (and often written by engineers
> who are not compiler experts and just need to get some refactoring done)
> does that very often in my experience working at Google.
>
>
> I don't think the traverse() matcher changes so much in this area. "Just
> need to get some refactoring done" sounds like writing a composition
> matcher within a check, not writing it for some library code.
>
We have lots of engineers who are not Clang experts and write reusable
refactoring code.

> - The complexity cliff for users. Many non-trivial matchers need to
>> explicitly manage implicit AST nodes.
>>
>>
>> You just described the complexity cliff which is (after my change) not
>> the first thing a newcomer hits.
>>
>> It's good to move that cliff back so that the newcomer is not confronted
>> with it immediately.
>>
> As soon as you pretty-print the AST (which I think most people should do
> before writing a matcher), you see implicit nodes.
>
>
> If using clang-query, you can change the mode of how clang-query matches
> and dumps ASTs. But, in the future you won't need to dump the AST anyway,
> because clang-query will just tell you the available matchers and what they
> match.
>
> See my EuroLLVM talk for more, in particular the workflow diagram which
> does not include inspecting the AST:
> https://steveire.files.wordpress.com/2018/11/all-no-ast.png?w=900&h=590
>
>
> - The cost of ClangTidy. ClangTidy runs all matchers simultaneously in one
>> AST traversal. If we implement implicit/no-implicit modes as separate AST
>> traversals, ClangTidy would need to run two traversals, one for "easier"
>> matchers (skipping implicit code), and one for "expert" matchers
>> (traversing implicit code). We would also need to build two parent maps.
>>
>> As of https://reviews.llvm.org/D73388 we no longer create a parent map
> for each traversal kind used at runtime.
>
> This means I can no longer measure a runtime cost of introducing use of
> the traverse() matcher in clang-tidy.
>
Thank you, that's a great improvement! However, I'm not sure about the
absence of runtime cost -- I think it would be more fair to say that there
is no cost *right now*. This change adds extra logic
(AscendIgnoreUnlessSpelledInSource) that is only called in the case
of TK_IgnoreUnlessSpelledInSource traversal. Since most checkers in
ClangTidy don't use that mode, we see no increase in runtime cost today.
However, once the default is flipped, or once we start
using TK_IgnoreUnlessSpelledInSource more, we could see an increased cost
of AST matchers compared to the TK_AsIs traversal.

> As long as the current AST Matchers APIs exist, they should be improved.
>> Perhaps they will be less important in the future when we have Syntax Trees
>> for these use-cases instead. However, for now, I don't think the ease of
>> use improvement in my patches should be prevented based existence of a
>> future alternative system.
>>
> I agree that we should not block improvements on existence of a future
> system. However, each specific change should be evaluated based on its
> merits and costs. I think there are non-trivial downsides to offering a
> different mode in existing AST matchers, which create maintenance and
> testing costs that we will be paying perpetually.
>
>
> We may not achieve your agreement on this change, but I think we have
> consensus already that this change should proceed.
>
I'm not sure how you measured the degree of consensus -- could you clarify?

Here's what I see: so far, there have been few people participating on this
thread, and outside of the authors of the proposal (you and Aaron), only I
have provided direct feedback about supporting/opposing the proposal, other
people (Artem, Gabor, and Ilya) only asked questions, provided
clarifications, and provided feedback on the syntax trees developments. If
you count me as objecting to the traverse() API in general, and not
objecting to this change, then there has been no feedback from the
community on this proposal at all. If you count me as objecting to this
proposal, then there's one person objecting. Based on these observations, I
don't see consensus yet, even if you exclude my feedback.

>
> It instantly creates a huge testing gap for existing AST matchers (which
> we currently test only in one mode).
>
>
> The traverse() matcher does not introduce a need to test each AST matcher
> in each mode.
>
Why do you say so? Matchers composed out of other matchers are affected by
the traversal mode that the user invokes them in.

> It also creates traps for existing code that will be able to start
> accidentally calling existing matchers in a traversal mode that they were
> not designed for.
>
>
> Yes, true. It is possible to write a matcher which works as someone
> expects in one mode but not the other, such as a matcher which specifically
> expects to match a implicitCastExpr().
>
Exactly.

> This can matter for matchers which are in "libraries", but not for
> matchers which are implementation details inside checks. Unless a
> particular check exposes the traversal kind as an option, those matchers
> can not be affected. Any check which does expose that as an option has to
> do so consciously and explicitly and has to test it. Nothing new there.
>
I'm sorry if I have been unclear about this point, but during this whole
conversation I have been talking not about specific ClangTidy checkers, but
about libraries that provide matchers. Users of Clang (for example,
internal users at Google) have such libraries, and use them broadly outside
of ClangTidy. Previously in this thread I pointed at a matcher in ClangTidy
as an example because that's the only piece of open source code I could
easily find, that has similar complexity to libraries that we have at
Google. Introduction of traverse() has increased the testing matrix for
these matchers, so it is a new increase in complexity, and increase in
technical debt (missing tests).

Let me reiterate: I understand that Clang or Clang Tooling does not provide
a stable API, so making breaking changes here is totally within the policy.

However, the specific aspects of this change (silently breaking existing
matchers, creating new traps for people who write reusable AST matchers,
increasing the testing matrix) have consequences that are very different
from a typical API change in Clang AST, where the user of that API will see
a build break, and can easily locally fix code. The cost of this change is
much higher for users of the API being changed.

Let me point you at similar change that was done previously: the change in
elidable constructor representation in Clang AST between C++14 and C++17.
(TL;DR: AST built by Clang in C++11 mode has AST nodes for elidable
constructor calls, but in C++17 mode they are always elided.) Lots of
ClangTidy checkers were broken by this change, but nobody noticed, because
ClangTidy was not being tested in all language modes. I closed this testing
gap (https://reviews.llvm.org/D62125), and our team has fixed a bunch of
ClangTidy checkers, but other checkers still remain broken until this day
(run `git grep 'FIXME: Fix the checker to work in C++17 mode.'`) The worst
part of this story is that the breakage was noticed a long, long time after
the AST change was implemented, and that the cost of the change (expanding
testing, fixing checkers) has fallen onto people other than the ones who
changed the AST.

The proposal has been implying (correct me if I'm wrong) that the
maintenance cost and complexity that is being put onto experts with a
codebase that uses AST matchers that they maintain long-term is worth the
added convenience for novice users who write one-off tools that don't need
to be maintained. If it is indeed the case, I would prefer this argument to
be made explicitly (as in, the proposal should describe the downsides of
making this change; right now it does not describe them).

Dmitri

-- 
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr at gmail.com>*/
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/cfe-dev/attachments/20200126/4359125f/attachment-0001.html>