[RecoveryAST] Add design doc to clang internal manual.

[hokein]

Summary

Hopefully it would be useful for new developers.

[kadircet]

thanks! i think this mostly looks great, leaving a couple of suggestions and questions in comments.

clang/docs/InternalsManual.rst

1882

rather than some form maybe say while indicating the error ?

1886

so far we've always been talking about the current state right? comparison to past seems surprising now. can we have a couple of examples for the cases that we still drop the nodes today?

1889

s/nice/better

1890

maybe drop to AST consumers or move it to the begining of the statement i.e.
provides AST consumers with a rich AST reflecting the written source code as ....

1910

s/was/would be

1933

this talks about why it would be hard to make use of CallExprs but doesn't say what we would gain by doing so. I suppose it would come with the benefit of preserving more details about the source code, like locations for parantheses and knowing the type of the expr? (or are these still accessible e.g. do we have an enum in RecoveryExpr telling us about its type?)

1959

that's great to know! i would expect it to be there already, but i think we should have this as a comment within the code too, so that future maintainers can feel confident when setting the type of a recovery expr.

1971

IIRC, there were other problems with clang trying to emit secondary diags on such cases. It might be worth mentioning those too, again to warn future travellers about the side effects of making this non-value-dependent.

1978

might be worth mentioning this only exists for expressions.

1979

not sure what second this is for

1980

this sounds like it is propagated all the way to the TUDecl, but i suppose that's not the case. can you elaborate on when the propagation stops?

[sammccall]

I've reviewed this previously and am happy with how it ended up.
But Kadir's comments are good, and we should also wait a few days in case others want changes.

clang/docs/InternalsManual.rst

1886

nit: "graceful recovery. Prior to..."

1933

Ooh, you're right: this says "the trade off" but only mentions one side :-)

Maybe "This would capture more call details and allow it to be treated uniformly with valid CallExprs. However, jamming..."

1971

Do you have an example? I chatted with Haojian offline about this and we couldn't find a good one apart from constant contexts. (And the wording of the standard suggests that value-dependence is a concept that's only interesting in constant contexts)

[hokein]

address review comments

[hokein]

clang/docs/InternalsManual.rst

1882

I'm not sure this will be better. indicating error seems to be a bit strong.

e.g. if () {}, this ill-formed statement, the AST node is like below, which doesn't have an obvious error signal (we could argue the OpaqueValueExpr is )

`-IfStmt
   |-OpaqueValueExpr 'bool'
   `-CompoundStmt

1886

. can we have a couple of examples for the cases that we still drop the nodes today?

The concern of giving a dropped example is that it might be stale once it gets preserved and recovered in the future. So personally, I'd prefer to give a true example, it was the mismatched-argument function call.

I guess this is not too hard for readers to come up with an example, a pretty broken statement would be the case.

1933

yeah, this is good point. added.

1959

yeah, we already have this in the comment of RecoveryExpr.

1971

I think the existing doesn't emit more errors texts already indicate we suppress the secondary diags etc.

1978

in reality, they are complicated, these bits (template, contains-errors) are not only for expressions, but also for Type, NestedNameSpecifier, TemplateArgument.

1979

oh, removed it.

1980

you're right, but the whole propagation process is complex, I think it needs more words to explain how and when it stops (and it is probably out-of-scope). I adjusted the word a bit to make less confusing.

[kadircet]

clang/docs/InternalsManual.rst

1882

oh okay didn't know that. i thought we would always have a node which can indicate the error somehow (not having that is still surprising though).

1971

Do you have an example?

unfortunately not :( but something tells me the particular bug was somehow about typo correction happening inside recoveryexprs ?

I think the existing doesn't emit more errors texts already indicate we suppress the secondary diags etc.

yeah i guess you are right.

clang/docs/InternalsManual.rst

 the definiition of the class, and the others are treated as non-defining
 declarations that happen to also contain member declarations. Corresponding
 members in each definition of such multiply-defined classes are identified
 either by redeclaration chains (if the members are ``Redeclarable``)
 or by simply a pointer to the canonical declaration (if the declarations
 are not ``Redeclarable`` -- in that case, a ``Mergeable`` base class is used
 instead).
 
+Error Handling
+--------------
+
+Clang produces an AST even when the code contains errors. Clang won't generate
+and optimize code for it, but it's used as parsing continues to detect further
+errors in the input. Clang-based tools also depend on such ASTs, and IDEs in
+particular benefit from a high-quality AST for broken code.
+
+In presence of errors, clang uses a few error-recovery strategies to present the
+broken code in the AST:
+
+- correcting errors: in cases where clang is confident about the fix, it
+  provides a FixIt attaching to the error diagnostic and emits a corrected AST
+  (reflecting the written code with FixIts applied). The advantage of that is to
+  provide more accurate subsequent diagnostics. Typo correction is a typical
+  example.
+- representing invalid node: the invalid node is preserved in the AST in some
+  form, e.g. when the "declaration" part of the declaration contains semantic
+  errors, the Decl node is marked as invalid.
+- dropping invalid node: this often happens for errors that we don’t have
+  graceful recovery. Prior to Recovery AST, a mismatched-argument function call
+  expression was dropped though a CallExpr was created for semantic analysis.
+
+With these strategies, clang surfaces better diagnostics, and provides AST
+consumers a rich AST reflecting the written source code as much as possible even
+for broken code.
+
+Recovery AST
+^^^^^^^^^^^^
+
+The idea of Recovery AST is to use recovery nodes which act as a placeholder to
+maintain the rough structure of the parsing tree, preserve locations and
+children but have no language semantics attached to them.
+
+For example, consider the following mismatched function call:
+
+.. code-block:: c++
+
+   int NoArg();
+   void test(int abc) {
+     NoArg(abc); // oops, mismatched function arguments.
+   }
+
+Without Recovery AST, the invalid function call expression (and its child
+expressions) would be dropped in the AST:
+
+::
+
+    |-FunctionDecl <line:1:1, col:11> NoArg 'int ()'
+    `-FunctionDecl <line:2:1, line:4:1> test 'void (int)'
+     |-ParmVarDecl <col:11, col:15> col:15 used abc 'int'
+     `-CompoundStmt <col:20, line:4:1>
+
+
+With Recovery AST, the AST looks like:
+
+::
+
+    |-FunctionDecl <line:1:1, col:11> NoArg 'int ()'
+    `-FunctionDecl <line:2:1, line:4:1> test 'void (int)'
+      |-ParmVarDecl <col:11, col:15> used abc 'int'
+      `-CompoundStmt <col:20, line:4:1>
+        `-RecoveryExpr <line:3:3, col:12> 'int' contains-errors
+          |-UnresolvedLookupExpr <col:3> '<overloaded function type>' lvalue (ADL) = 'NoArg'
+          `-DeclRefExpr <col:9> 'int' lvalue ParmVar 'abc' 'int'
+
+
+An alternative is to use existing Exprs, e.g. CallExpr for the above example.
+This would capture more call details (e.g. locations of parentheses) and allow
+it to be treated uniformly with valid CallExprs. However, jamming the data we
+have into CallExpr forces us to weaken its invariants, e.g. arg count may be
+wrong. This would introduce a huge burden on consumers of the AST to handle such
+"impossible" cases. So when we're representing (rather than correcting) errors,
+we use a distinct recovery node type with extremely weak invariants instead.
+
+``RecoveryExpr`` is the only recovery node so far. In practice, broken decls
+need more detailed semantics preserved (the current ``Invalid`` flag works
+fairly well), and completely broken statements with interesting internal
+structure are rare (so dropping the statements is OK).
+
+Types and dependence
+^^^^^^^^^^^^^^^^^^^^
+
+``RecoveryExpr`` is an ``Expr``, so it must have a type. In many cases the true
+type can't really be known until the code is corrected (e.g. a call to a
+function that doesn't exist). And it means that we can't properly perform type
+checks on some containing constructs, such as ``return 42 + unknownFunction()``.
+
+To model this, we generalize the concept of dependence from C++ templates to
+mean dependence on a template parameter or how an error is repaired. The
+``RecoveryExpr`` ``unknownFunction()`` has the totally unknown type
+``DependentTy``, and this suppresses type-based analysis in the same way it
+would inside a template.
+
+In cases where we are confident about the concrete type (e.g. the return type
+for a broken non-overloaded function call), the ``RecoveryExpr`` will have this
+type. This allows more code to be typechecked, and produces a better AST and
+more diagnostics. For example:
+
+.. code-block:: C++
+
+   unknownFunction().size() // .size() is a CXXDependentScopeMemberExpr
+   std::string(42).size() // .size() is a resolved MemberExpr
+
+Whether or not the ``RecoveryExpr`` has a dependent type, it is always
+considered value-dependent, because its value isn't well-defined until the error
+is resolved. Among other things, this means that clang doesn't emit more errors
+where a RecoveryExpr is used as a constant (e.g. array size), but also won't try
+to evaluate it.
+
+ContainsErrors bit
+^^^^^^^^^^^^^^^^^^
+
+Beyond the template dependence bits, we add a new “ContainsErrors” bit to
+express “Does this expression or anything within it contain errors” semantic,
+this bit is always set for RecoveryExpr, and propagated to other related nodes.
+This provides a fast way to query whether any (recursive) child of an expression
+had an error, which is often used to improve diagnostics.
+
+.. code-block:: C++
+
+   // C++
+   void recoveryExpr(int abc) {
+    unknownFunction(); // type-dependent, value-dependent, contains-errors
+
+    std::string(42).size(); // value-dependent, contains-errors,
+                            // not type-dependent, as we know the type is std::string
+   }
+
+
+.. code-block:: C
+
+   // C
+   void recoveryExpr(int abc) {
+     unknownVar + abc; // type-dependent, value-dependent, contains-errors
+   }
+
+
 The ASTImporter
 ---------------
 
 The ``ASTImporter`` class imports nodes of an ``ASTContext`` into another
 ``ASTContext``. Please refer to the document :doc:`ASTImporter: Merging Clang
 ASTs <LibASTImporter>` for an introduction. And please read through the
 high-level `description of the import algorithm
 <LibASTImporter.html#algorithm-of-the-import>`_, this is essential for