Page MenuHomePhabricator

[AST] Add a flag indicating if any subexpression had errors
Needs ReviewPublic

Authored by ilya-biryukov on Aug 1 2019, 10:27 AM.

Details

Reviewers
rsmith
Summary

The only subexpression that is considered an error now is TypoExpr, but
we plan to add expressions with errors to improve editor tooling on broken
code. We intend to use the same mechanism to guard against spurious
diagnostics on those as well.

See the follow-up revision for an actual usage of the flag.

Diff Detail

Unit TestsFailed

TimeTest
50 msLLVM.tools/llvm-ar::mri-utf8.test
Script: -- : 'RUN: at line 4'; rm -rf /mnt/disks/ssd0/agent/workspace/Phabricator/build/test/tools/llvm-ar/Output/mri-utf8.test.tmp && mkdir -p /mnt/disks/ssd0/agent/workspace/Phabricator/build/test/tools/llvm-ar/Output/mri-utf8.test.tmp/extracted
40 msLLVM.tools/llvm-objdump/X86::disassemble-functions.test
Script: -- : 'RUN: at line 4'; /mnt/disks/ssd0/agent/workspace/Phabricator/build/bin/yaml2obj -o /mnt/disks/ssd0/agent/workspace/Phabricator/build/test/tools/llvm-objdump/X86/Output/disassemble-functions.test.tmp.out /mnt/disks/ssd0/agent/workspace/Phabricator/llvm/test/tools/llvm-objdump/X86/Inputs/simple-executable-x86_64.yaml

Event Timeline

ilya-biryukov created this revision.Aug 1 2019, 10:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 1 2019, 10:27 AM
Herald added a subscriber: jfb. · View Herald Transcript

Gentle ping. @rsmith, please take a look when you have time.

Rather than adding a bit onto Expr to specify whether it's erroneous, have you considered making this a property of the type system by introducing an ErrorExpr AST node that other nodes can inherit from? I think that approach would work more naturally for things like AST matchers while solving some problems we have with being able to pretty printing or AST dump erroneous ASTs. The ErrorExpr node could contain a subnode of a partially-valid Expr object that would retain as much of the information as we've been able to gather, but the error node (or its subclasses) could contain other information useful when handling errors, such as storing the original source text (or range) for the expression, potential fixes, etc.

It seems that these two options are not exactly the same right ? The ContainsError bit is useful to quickly answer "Does this expression contains an invalid sub-expression" without doing the search, while adding an ErrorExpr node is useful to note that this sub-expression is invalid (and as Aaron says the hypothetical ErrorExpr node can carry more info about the error).

clang/include/clang/AST/Expr.h
1526

/*ContainsError=*/false here and elsewhere ?

3607

What is this dead2 ?

clang/lib/AST/ExprObjC.cpp
29

s/ContainsErros/ContainsErrors

It seems that these two options are not exactly the same right ? The ContainsError bit is useful to quickly answer "Does this expression contains an invalid sub-expression" without doing the search, while adding an ErrorExpr node is useful to note that this sub-expression is invalid (and as Aaron says the hypothetical ErrorExpr node can carry more info about the error).

Exactly right, thanks for summing this up!

Rather than adding a bit onto Expr to specify whether it's erroneous, have you considered making this a property of the type system by introducing an ErrorExpr AST node that other nodes can inherit from? I think that approach would work more naturally for things like AST matchers while solving some problems we have with being able to pretty printing or AST dump erroneous ASTs. The ErrorExpr node could contain a subnode of a partially-valid Expr object that would retain as much of the information as we've been able to gather, but the error node (or its subclasses) could contain other information useful when handling errors, such as storing the original source text (or range) for the expression, potential fixes, etc.

Having something similar to ErrorExpr is actually the next logical step I'm currently exploring. The idea of this bit is to carry information on whether any (recursive) child of an expression had an error that was already diagnosed.
Detecting those expression is useful to avoid producing additional irrelevant diagnostics (see the dependent revision that uses the bit to get rid of one such diagnostic) and avoid running various functions that are not prepared to handle subexpressions that have errors (e.g. constant evaluation).

It seems that these two options are not exactly the same right ? The ContainsError bit is useful to quickly answer "Does this expression contains an invalid sub-expression" without doing the search, while adding an ErrorExpr node is useful to note that this sub-expression is invalid (and as Aaron says the hypothetical ErrorExpr node can carry more info about the error).

That's true. I had figured that answering "does this expression contain an invalid sub-expression" could be implemented with a walk of the expression tree rather than consuming a bit. To consumers of containsErrors(), there shouldn't be much difference aside from performance (and that may be sufficient reason to go with a bit, but I think I'd like to see performance measurements that show the bit is necessary).

It seems that these two options are not exactly the same right ? The ContainsError bit is useful to quickly answer "Does this expression contains an invalid sub-expression" without doing the search, while adding an ErrorExpr node is useful to note that this sub-expression is invalid (and as Aaron says the hypothetical ErrorExpr node can carry more info about the error).

That's true. I had figured that answering "does this expression contain an invalid sub-expression" could be implemented with a walk of the expression tree rather than consuming a bit. To consumers of containsErrors(), there shouldn't be much difference aside from performance (and that may be sufficient reason to go with a bit, but I think I'd like to see performance measurements that show the bit is necessary).

Fair enough, especially given that IIRC there are not many bits left in these bit-fields classes.

ilya-biryukov added a comment.EditedAug 12 2019, 7:10 AM

It seems that these two options are not exactly the same right ? The ContainsError bit is useful to quickly answer "Does this expression contains an invalid sub-expression" without doing the search, while adding an ErrorExpr node is useful to note that this sub-expression is invalid (and as Aaron says the hypothetical ErrorExpr node can carry more info about the error).

That's true. I had figured that answering "does this expression contain an invalid sub-expression" could be implemented with a walk of the expression tree rather than consuming a bit. To consumers of containsErrors(), there shouldn't be much difference aside from performance (and that may be sufficient reason to go with a bit, but I think I'd like to see performance measurements that show the bit is necessary).

Are expression bits scarce?
We don't have any checks if expressions contain errors now, we simply drop too many invalid expressions and never put them into the AST.
It's impossible to do the measurements at this point, but it would be nice if adding those checks was cheap.

We can also assume they're cheap, use the visitor-based implementation and later switch if this turn out to be a problem.
I think we should prefer the approach that guarantees the compiler is not getting slow ever rather than chase the slowness later.

Fair enough, especially given that IIRC there are not many bits left in these bit-fields classes.

May be reasonable in that case, but we should be aware of a potential O(n^2) and even exponential complexities in the frontend arising from calling containsErrors in too many places in that case.
If we ever run out of bits, we could remove this bit and instead introduce a cache (something like set<Expr*> InvalidExprs) in ASTContext.

It seems that these two options are not exactly the same right ? The ContainsError bit is useful to quickly answer "Does this expression contains an invalid sub-expression" without doing the search, while adding an ErrorExpr node is useful to note that this sub-expression is invalid (and as Aaron says the hypothetical ErrorExpr node can carry more info about the error).

That's true. I had figured that answering "does this expression contain an invalid sub-expression" could be implemented with a walk of the expression tree rather than consuming a bit. To consumers of containsErrors(), there shouldn't be much difference aside from performance (and that may be sufficient reason to go with a bit, but I think I'd like to see performance measurements that show the bit is necessary).

Are expression bits scarce?
We don't have any checks if expressions contain errors now, we simply drop too many invalid expressions and never put them into the AST.
It's impossible to do the measurements at this point, but it would be nice if adding those checks was cheap.

Sort of... I went through the list of bit-fields classes and if I count correctly there is 4 (possibly 5) bits left in Stmt or Expr which can be used without doing anything else. I guess that using one of them is okay.

We can also assume they're cheap, use the visitor-based implementation and later switch if this turn out to be a problem.
I think we should prefer the approach that guarantees the compiler is not getting slow ever rather than chase the slowness later.

Fair enough, especially given that IIRC there are not many bits left in these bit-fields classes.

May be reasonable in that case, but we should be aware of a potential O(n^2) and even exponential complexities in the frontend arising from calling containsErrors in too many places in that case.
If we ever run out of bits, we could remove this bit and instead introduce a cache (something like set<Expr*> InvalidExprs) in ASTContext.

It seems that these two options are not exactly the same right ? The ContainsError bit is useful to quickly answer "Does this expression contains an invalid sub-expression" without doing the search, while adding an ErrorExpr node is useful to note that this sub-expression is invalid (and as Aaron says the hypothetical ErrorExpr node can carry more info about the error).

That's true. I had figured that answering "does this expression contain an invalid sub-expression" could be implemented with a walk of the expression tree rather than consuming a bit. To consumers of containsErrors(), there shouldn't be much difference aside from performance (and that may be sufficient reason to go with a bit, but I think I'd like to see performance measurements that show the bit is necessary).

Are expression bits scarce?
We don't have any checks if expressions contain errors now, we simply drop too many invalid expressions and never put them into the AST.
It's impossible to do the measurements at this point, but it would be nice if adding those checks was cheap.

We can also assume they're cheap, use the visitor-based implementation and later switch if this turn out to be a problem.
I think we should prefer the approach that guarantees the compiler is not getting slow ever rather than chase the slowness later.

The problem is: those bits are not infinite and we only have a handful left until bumping the allocation size; is this use case critical enough to use one of those bits? I don't think it will be -- it seems like premature optimization. Also, by calculating rather than using a bit, you don't have to touch every Expr constructor, which reduces the complexity of the patch.

Some other things I think are missing from the patch (regardless of whether you go with a bit or calculate on the fly):

  • Do you need some changes to AST serialization and deserialization? Does anything special need to happen for modules?
  • I would expect to see this information reflected in an AST dump
  • How should this impact AST matching interfaces?
  • Test cases

The problem is: those bits are not infinite and we only have a handful left until bumping the allocation size; is this use case critical enough to use one of those bits? I don't think it will be -- it seems like premature optimization. Also, by calculating rather than using a bit, you don't have to touch every Expr constructor, which reduces the complexity of the patch.

Alternatively, we could keep an equivalent of set<Expr*> InvalidExprs in ASTContext. Gives the same computational complexity, but has a higher constant overhead factor.
Does that look reasonable?

Some other things I think are missing from the patch (regardless of whether you go with a bit or calculate on the fly):

  • Do you need some changes to AST serialization and deserialization?

Good point, will update the patch.

  • Does anything special need to happen for modules?

Not sure. What are the potential problems you foresee?

  • I would expect to see this information reflected in an AST dump

Good point. Will do. Although it's a little hard to test in this patch, since it's hard to catch a TypoExpr in the AST dump.

  • How should this impact AST matching interfaces?

We could add a matcher that filters on this flag, but I would start with adding more expressions first (something similar to ErrorExpr);
For the purposes of this patch, I'd keep the matcher interfaces untouched.

  • Test cases

Again, since it's hard to catch a TypoExpr in the final AST dump, it's hard to catch this bit. See the dependent revision for a bogus diagnostic not being emitted anymore.

The problem is: those bits are not infinite and we only have a handful left until bumping the allocation size; is this use case critical enough to use one of those bits? I don't think it will be -- it seems like premature optimization. Also, by calculating rather than using a bit, you don't have to touch every Expr constructor, which reduces the complexity of the patch.

Alternatively, we could keep an equivalent of set<Expr*> InvalidExprs in ASTContext. Gives the same computational complexity, but has a higher constant overhead factor.
Does that look reasonable?

Yup, that is also very reasonable.

Some other things I think are missing from the patch (regardless of whether you go with a bit or calculate on the fly):

  • Do you need some changes to AST serialization and deserialization?

Good point, will update the patch.

  • Does anything special need to happen for modules?

Not sure. What are the potential problems you foresee?

I'm not certain there are real problems there, but I am wondering whether something like a BMI should include serialized error AST nodes or not. Would a consumer of the module expect that? I suppose it could if we wanted it to.

  • I would expect to see this information reflected in an AST dump

Good point. Will do. Although it's a little hard to test in this patch, since it's hard to catch a TypoExpr in the AST dump.

Ah, drat, I was hoping we had at least one test that already did this, but I don't see one.

  • How should this impact AST matching interfaces?

We could add a matcher that filters on this flag, but I would start with adding more expressions first (something similar to ErrorExpr);
For the purposes of this patch, I'd keep the matcher interfaces untouched.

I think that makes sense. The sort of things I'm wondering about are: if we are going to start retaining error nodes in the AST more regularly, should AST matchers opt into matching on those nodes, or opt out of matching on them? I think the answer should be that we only AST match on valid AST nodes, but I could see arguments being made either way, so maybe this part needs an RFC for more opinions.

  • Test cases

Again, since it's hard to catch a TypoExpr in the final AST dump, it's hard to catch this bit. See the dependent revision for a bogus diagnostic not being emitted anymore.

Yeah, I was hoping we'd have some AST dumping mechanism for testing this. If not, though, perhaps we could still use a unit test?

I did some experiments with adding something similar to the ErrorExpr Aaron suggest. It has this flag set and does not get removed from the AST.
I believe the best way to address Aaron's comments is to add tests mentioning this expression instead of trying to catch TypoExpr, which normally get removed from the AST.

Would need some time to fix a few remaining test failures (bogus diagnostics), I'll update this patch when I have something (hopefully tomorrow).

  • Add the added bit to serialization
  • Mention contains-errors in the AST dump. Still not tests in this revision, see D69330 for an expression that is actually preserved and has this bit.

Build result: fail - 59344 tests passed, 2 failed and 812 were skipped.

failed: LLVM.tools/llvm-ar/mri-utf8.test
failed: LLVM.tools/llvm-objdump/X86/disassemble-functions.test

Log files: cmake-log.txt, ninja_check_all-log.txt, CMakeCache.txt

We can also assume they're cheap, use the visitor-based implementation and later switch if this turn out to be a problem.
I think we should prefer the approach that guarantees the compiler is not getting slow ever rather than chase the slowness later.

The problem is: those bits are not infinite and we only have a handful left until bumping the allocation size; is this use case critical enough to use one of those bits?

In the abstract, improving error recovery and toolability are among the more important things we could do, and it certainly seems worth spending a bit on every Expr on this to me, if there's no better alternative. (That is: I think this approach is OK if we don't find something better.)

It's not obvious to me whether recomputing this information by AST traversal would be fast enough: *if* we want to perform the "does this contain errors?" check from contexts we encounter frequently (eg, when deciding whether to produce warnings, whether we should skip certain semantic actions, and similar), we can't do that if it requires a traversal.

Alternatively, we could keep an equivalent of set<Expr*> InvalidExprs in ASTContext. Gives the same computational complexity, but has a higher constant overhead factor.
Does that look reasonable?

Yup, that is also very reasonable.

I think this will be very expensive from a maintenance (and potentially performance) perspective: every constructor for every expression node will need to check whether its subexpressions are in the set, and if so, add themselves to the set.

As a variant on this, we could build a map<Expr*, bool> to track whether each expression is known to contain errors, or known to not contain errors, populate it lazily when queried, and shortcut the whole mechanism if we've never created an error node. That still seems a little expensive, but at least we'd only pay the cost for invalid programs. If we could produce a dense numbering of Exprs, this'd suddenly seem pretty good, though, and we know that Exprs are allocated on the ASTContext's bump allocator, so maybe there's something we can do there...

Another option is to represent "contains an error" with a specific Type. This'd mean we'd not preserve type information in less-common cases such as: f( T(some-erroneous-expression) ), and wouldn't be able to diagnose if there's no function f that takes a T, but I think that's an acceptable loss. The downside is that we would need logic to create representations with the appropriate "contains an error" type throughout Sema -- everywhere where we create nodes with dependent types, plus some additional cases like cast expressions that are never type-dependent (but can contain errors).

Here's my current thinking:

  • Using dependence to model "contains errors" is a mistake. We should stop doing that.
  • We therefore need a different type to indicate "couldn't determine the type of this because it contains errors", and should add a new builtin type for that.
  • In cases like int( thing-containing-errors ), it's probably completely fine that we can't determine whether the expression contains errors, and we shouldn't provide an interface to ask that question. (The current flag bit doesn't help with that anyway, since the errors could be nested indirectly, say inside a lambda, and we don't propagate the flag through that.)

So my proposal would be: stop trying to track whether expressions contain errors. Instead, add a builtin type to indicate whether the type of an expression couldn't be determined due to an error, and propagate that in the same way we propagate type-dependence. Would that address the use cases here?

I'm not certain there are real problems there, but I am wondering whether something like a BMI should include serialized error AST nodes or not. Would a consumer of the module expect that? I suppose it could if we wanted it to.

We already do preserve invalid AST through AST files if we're asked to do so; this isn't new. (For example, the Invalid flag on Decls is preserved.) This is important for some tooling scenarios: you want to be able to produce and use a precompiled preamble even if it contains errors.

Ah, drat, I was hoping we had at least one test that already did this, but I don't see one.

Maybe we should introduce a __builtin_dump(expr) function that dumps its operand at the point where semantic analysis is first done? That'd be useful for other things too (#pragma clang __debug dump X is a little unwieldy).

I would actually try to counter the type proposal and defend the containsErrors bit. Here's my thinking.

Not knowing that int(<something-that-contains-errors>) had errors inside can lead to situations with bad diagnostics.
We won't be able to suppress any non-type-related error, e.g. int *a = int(<something-that-contains-errors>) will probably complain that you can't assign an int to a pointer. This diagnostics is spurious, because <something-that-contains-error> might have actually evaluated to 0 and the users are better-off fixing the original error first and showing the other diagnostic is just noise.
The example might look a little contrived, but having an easy-to-use mechanism to suppress those errors is useful.

Expressions are not the only construct where we loose information. Something like containsErrors could generalize to types, template arguments, name qualifiers and other constructs that can potentially have valid sub-components, even if the compiler chooses to not produce them now due to semantic errors. This is forward-looking and I don't think we have concrete plans to make this happen, but it would be sad to go with a design that can't be extended to anything beyond expressions even theoretically.

Adding a new type, properly propagating it and checking for it in all places where we suppress diagnostics is a lot of work. containsErrors is a good way to incrementally find places that need to be tweaked and fix them to avoid producing extra diagnostics and running function that require well-formed ASTs. Having a new type seems like an all-or-nothing effort, i.e. one would have to spend considerable time building it and fixing everything that used to produce invalid expressions.
As for the lamda case: can we actually propagate containsErrors through lambdas? That probably means lifting this bit to the statement level, but that could definitely work. Knowing that lambda (or any other function, for that matter) produced an error somewhere inside its body actually looks like useful information and propagating it is not a lot of effort (in fact, I did try this and, while being more complicated than expressions, propagating this flag for statements seems doable).

nridge added a subscriber: nridge.Dec 15 2019, 3:58 PM
rsmith added a comment.EditedDec 19 2019, 2:40 PM

Summary of an off-line discussion with Ilya:

  • The current situation where Clang can do delayed typo correction for C++ but not for C is not a good long-term position. The reason for that situation is that we use a dependent type to represent a type with errors. There are two natural paths out of this situation: (1) use something other than a dependent type, such as an error type, for this purpose, and (2) support dependence in C. Of these, (1) is pretty much strictly more expensive than (2): whatever work we need to do for the C-only parts of Clang in (2), we will need to do the same work in the C-only parts of Clang for (1), and much more work in addition. It's also worth noting that we will in fact want all the different flavors of dependence for error tracking too: we will ideally want to distinguish between "this expression can't be evaluated because its value depends on an error" and "this expression doesn't have a meaningful type because its type depends on an error". Conclusions: 1. we should support delayed typo-correction in C by supporting dependence in C, and 2. we should generalize what we mean by "dependent" to mean "depends on a template parameter or an error".
  • Computing 4 (with this patch, 5) bits of status summarizing properties of subexpressions is highly undesirable: it's error-prone, repetitive, and expensive. It would be better if we packed these five bits into an enum and had a single consistent mechanism for computing them based on the corresponding properties of subexpressions, and if we had some way to do that that didn't require complexity in every constructor for every AST node. (We could, for example, set the bits from the FooExpr::Create functions by calling one centralized function that walks the children and accumulates properties from them -- with all exceptions to that general pattern in a single place.) Conclusions: 3. it's time to refactor these bits; the proof that we've done this right will be that adding the fifth such bit is easy.
  • A transitive "does this or anything within it contain errors" flag has value. It may not be exactly the right information for any particular query, but finer-grained information (eg, "do we know the type of this expression?") can be obtained using the various dependence bits. Example: this bit lets us determine whether dependence means "depends on a template parameter" (bit is false) or whether it means "don't know what this depends on, suppress follow-on errors" (bit is true). Eg, we could stop producing a bogus diagnostic for a missing template keyword in typo.function<int>(). Example: this bit will permit us to distinguish between "function has a body and as far as we know it's valid" and "function has a body that contained errors", and suppress errors for (eg) missing return statements in a constexpr function, and likewise suppress control-flow-based warnings on function granularity rather than whole-compilation granularity. (These examples are all cases where we have a significant diagnostic quality problem today.)

Here's the plan we came up with:

  1. (Notionally) generalize what we mean by "dependent" to mean "depends on a template parameter or on an error".
  2. Refactor and centralize the computation and propagation of the dependence and "contains pack" bits.
  3. Add the containsErrors bit (after (2) this should be easy) to all statements (not only expressions)
  4. (Asynchronously) add support for dependent constructs to Clang's C-only codepaths and start doing delayed typo-correction (and preserving invalid subexpressions) even in C.

@ilya-biryukov Did I forget anything?

Summary of an off-line discussion with Ilya:

<snip>

I think that summary sounds very sensible. Thank you both for working on this!

@ilya-biryukov Did I forget anything?

SG, I don't think anything is missing. Thanks for the write-up!