Name already in use

LLVM's bazel build has changed a bit, so this updates the tree for that.

LLVM is also moving `llvm::Optional` to match the standard API, but it seemed simpler to just switch to `std::optional`.

Co-authored-by: Jon Ross-Perkins <jperkins@google.com>

Might eventually want to change this further, but I'm just adding the quick framework for it.

Per discussion on #2424

Make `.run` targets include symbol information, and include token names on CHECK output in more places.

- Finishes remaining "todo" parse nodes.
- Improving error recovery for invalid designators and structs, so that the parse tree still looks similar to a valid parse tree.
- Call expressions now have the thing being called as a child (of the start) instead of a sibling.
- Use of Start is replacing use of End in several parse nodes, like structs and call expressions.
- Adjusting documentation of parse node structures in an attempt to make it more consistent and understandable.
- The current state for interfaces and if/else is mostly being documented, not altered.

Relates to #1881

- Add support for `.base` field in structs for [parent class initialization](https://github.com/carbon-language/carbon-lang/blob/trunk/docs/design/classes.md#constructors)
    - Disabling base class initialization without `.base`
- Support class constructors (`Create() -> Self`) for base classes
- Direct access to base class(es) attributes with `object.var` remains unaffected

Changes:
- Add `TypeChecker::FieldTypesWithBase` to help assessing if a struct with `base` fields can be converted to a class
- Add a new `base_type()` attribute+getter to `NominalClassDeclaration` to as a first step to allow resolving parametrized classes
- Add a new `base` attribute+getter to `NominalClassValue` that contains the base class `NominalClassValue`. It is currently used mainly to get and set members of a class object.
- Add `Interpreter::ConvertClassWithBase` to build `NominalClassValue` from a init struct, that contains `.base` fields with either `NominalClassValue` or `StructValue`
- Add `FindClassField` to find a field in a class or its base classes
- Remove superfluous `ClassDeclaration::base()` in favor of `ClassDeclaration::base_type()`

Limitations;
- Though some work is done in that direction, parametrized base class where time is not know at the declaration site are not supported. Namely the example below does not compile
```
base class A(T:! Type) {}
class B(T:! Type) extends A(T) {}
```
But this one is functional already
```
base class A(T:! Type) {}
class B extends A(i32) {}
```

Co-authored-by: Richard Smith <richard@metafoo.co.uk>

This works on multiple statements to make them better for the bracketing model. Stub nodes are added in more cases of invalid syntax, simply so that the semantics has reliably structured input. Comments in parse_node_kind.def now try to show the expected parse tree structure in postorder form.

This labels If, While, and For a little differently in parse nodes so that at the start of the postorder traversal, it'll already be available to semantics which structure is being processed. I need to do a little more with If in particular, but this felt like a reasonable stopping point.

While this makes significant parser changes, the changes to parser_state.def are minimal, mostly naming-related. The actual flow isn't substantively changed, just a couple minor names and the new As(If|While) state which allows distinguishing IfCondition and WhileCondition.

Co-authored-by: Chandler Carruth <chandlerc@gmail.com>

)

First change towards re-implementing interfaces using the new parser. I kept it small to make sure we are on the same page regarding stack states and how the parse tree should look like.

Co-authored-by: ergawy <kareem.ergawy@guardsquare.com>

This switches the Verify method to walk postorder so that we can see how much subtree_size is really used, and shift towards removing it. It also starts calling Verify.

Also, I think I'd lost the reserve/size check during Parser refactoring, so I'm putting that back in as part of Verify.

Co-authored-by: Chandler Carruth <chandlerc@gmail.com>

…index types. (#2398)

The intent here is to reduce use of vanilla `int32_t` without a clear indicator of what it's referencing, and to more tightly link references with the underlying types they reference into.

The type name DataIndex doesn't feel great, but I was kind of floundering for a better name.

When there's no semicolon for an invalid EmptyDeclaration, rather than producing nothing, produce an EmptyDeclaration with the original location that led to the error.

Note this removes a direct edit (the only one) of the parse tree's error state. Elsewhere it's an indirection from adding an error node.

This is a first pass at what semantic type checking might look like. Types propagate along nodes, we use an InvalidType object when there's an error, and once there's an InvalidType we stop doing so much type checking.

This adds some RealLiteral handling in order to get type mismatches. I'm cautious about creating some real value for SemanticsIR (since the tokenized buffer version is a bit constrained), so I'm not doing that yet. But I will probably need to in order to maintain SemanticsIR having hermetic copies of its data, without a parse tree dependency.

Add template generics, with optional constraints but no [SFINAE](https://en.cppreference.com/w/cpp/language/sfinae), to Carbon. Template generics allows the compiler postpone type checking of expressions dependent on a template parameter until the function is called and the value of that parameter is known.

Example usage:

```carbon
fn Identity[template T:! Type](x: T) -> T {
  return x;
}
```

Co-authored-by: Richard Smith <richard@metafoo.co.uk>
Co-authored-by: Chandler Carruth <chandlerc@gmail.com>

I'd noted this while rewriting the parser and, while I kept it there during conversion, I think switching is consistent with the higher-level desire and the use of references therein was just an oversight.

Discussed at:
https://discord.com/channels/655572317891461132/655578254970716160/1042551242813083840

Longer term, I think this is going to be important as part of associating errors with code after the particular node has been processed, even though it isn't used here.

#2405)

I've been meaning to do this -- just a couple days ago I processed some that we'd missed for a few weeks...

The code change is small here. I'm breaking this out because it has a lot of test churn, and semantics doesn't have significant logic around it yet.

As requested

We keep seeing fragility installing software, with both brew (e.g., the recent python issues) and apt.llvm.org (currently flaky).

At this point, images for both ubuntu and macos have versions of llvm-14 that seem to successfully compile:
https://github.com/carbon-language/carbon-lang/actions/runs/3474670746/jobs/5808098087

Although we may want to figure out a way to resume running llvm-15 so that we can see compatibility issues, this seems preferable for baseline testing in order to reduce maintenance churn.

In addition to the above changes, this also configures cancellation more precisely, and stops installing bazel/bazelisk (it should already be preinstalled).

Just trying to standardize the use in a few spots; no behavioral change.

…s start. (#2396)

This is necessary in order to use a bracketing approach; parsing doesn't know the contained format until it parses the first element, which we don't want to do look-ahead for. I think the bracketing is higher value than knowing the format before adding the node.

This changes `return`, `break`, and `continue` to treat the keyword as the "start" and semicolon as the "parent", essentially bracketing the keyword.

Pragmatically this is focusing on making `return` work with only one ParseNodeKind: because `return` and `;` now bracket the expression, we can tightly determine whether the `return` has arguments without looking at subtree size. However, it's possible that `break` and `continue` may in the future take some kind of label as an argument, so the consistency seems beneficial there too.

Note this eliminates the StatementEnd ParseNodeKind, as it's obsolete with this change.

Just some unnecessary functions.

#2385)

While the Parser has similar divergent states, lists of Expressions tend to be handled more like this. I'm keeping the divergent start state in order to continue support of a distinct error, but I think this organization of FunctionParameter/FunctionParameterFinish will be less surprising.

Patterns all compute their values when type-checked, so we never
actually need to do any multi-step evaluation to compute the value of a
pattern. Doing so was leading to quadratic runtime and excess noise in
the trace file.

```
==> Pouring python@3.11--3.11.0.monterey.bottle.tar.gz
Error: The brew link step did not complete successfully
The formula built, but is not symlinked into /usr/local
Could not symlink bin/2to3-3.11
Target /usr/local/bin/2to3-3.11
already exists. You may want to remove it:
  rm '/usr/local/bin/2to3-3.11'
```

Installing llvm with --overwrite didn't seem to pass it on dependencies, particularly python (https://github.com/carbon-language/carbon-lang/actions/runs/3464174572/jobs/5785378508). So this instead installs python separately, and then --overwrite works.

See https://github.com/carbon-language/carbon-lang/actions/runs/3464364789/jobs/5785802783 for the example passing run. The actions on this PR will probably still use the trunk version.

This is to keep the tree consistent with the error-free state. It also more precisely locates the error.

Makes explorer/testdata/assoc_const/rewrite_large_type.carbon NOAUTOUPDATE and no-trace because otherwise it takes ~130s to run. With this it's sub-second, explorer is just dumping a lot of trace output (maybe still something to fix).

e.g., for `//explorer/testdata:tuple/no_ending_comma.carbon.test`, `bazel run //explorer/testdata:tuple/no_ending_comma.carbon.run`

Example stack:

```
1.	node_stack_:
	0.	FunctionDefinitionStart
	1.	ReturnStatement -> node1
2.	node_block_stack_:
	0.	block0
	1.	block1
```

Example trace output:

```
*** SemanticsParseTreeHandler::Build Begin ***
Push 0: FunctionIntroducer
Push 1: DeclaredName
Push 2: ParameterListEnd
Pop 2: ParameterListEnd
Push 2: ParameterList
Pop 2: ParameterList
Pop 0: FunctionIntroducer
AddNode block0: FunctionDeclaration()
AddNode block0: BindName(ident0, node0)
AddNode block0: FunctionDefinition(node0, block1)
Push 0: FunctionDefinitionStart
Push 1: Literal -> IntegerLiteral
AddNode block1: IntegerLiteral(int0): node_xref1
Push 2: StatementEnd
Pop 2: StatementEnd
Pop 1: any (Literal) -> node0
Push 1: ReturnStatement -> ReturnExpression
AddNode block1: ReturnExpression(node0)
Pop 0: FunctionDefinitionStart
Push 0: FunctionDefinition
*** SemanticsParseTreeHandler::Build End ***
cross_reference_irs.size == 2,
cross_references = {
  node_xref0 = "xref(ir0, block0, node0)";
  node_xref1 = "xref(ir0, block0, node1)";
},
identifiers = {
  ident0 = "Foo";
},
integer_literals = {
  int0 = 0;
},
node_blocks = {
  block0 = {
    node0 = FunctionDeclaration();
    node1 = BindName(ident0, node0);
    node2 = FunctionDefinition(node0, block1);
  },
  block1 = {
    node0 = IntegerLiteral(int0): node_xref1;
    node1 = ReturnExpression(node0);
  },
}
```

Co-authored-by: Chandler Carruth <chandlerc@gmail.com>

This adds a second double linked list test carbon program, which has
the major difference, that it is not bound to a type but rather uses the
generics system to allow the type to be be specified at creation.
Of course this is heavily inspired by the first linked_list example program,
but this does show of/test a different feature set solving the same problem.

Adds remaining expression support, and switches the default to Parser2.

Note, this doesn't delete the current Parser yet. I'll just do that in its own PR.

Adds `while` and most of the expression support. Splits apart the fixity test to demonstrate more closely which bits are still failing.

```
//toolchain/parser/testdata:basics/fail_paren_match_regression.carbon.test FAILED in 0.8s
//toolchain/parser/testdata:basics/function_call.carbon.test             FAILED in 0.7s
//toolchain/parser/testdata:basics/package.carbon.test                   FAILED in 0.7s
//toolchain/parser/testdata:basics/structs.carbon.test                   FAILED in 0.7s
//toolchain/parser/testdata:basics/tuples.carbon.test                    FAILED in 0.6s
//toolchain/parser/testdata:basics/var.carbon.test                       FAILED in 0.7s
//toolchain/parser/testdata:for/fail_colon_instead_of_in.carbon.test     FAILED in 0.7s
//toolchain/parser/testdata:for/fail_missing_in.carbon.test              FAILED in 0.7s
//toolchain/parser/testdata:for/fail_missing_var.carbon.test             FAILED in 0.7s
//toolchain/parser/testdata:for/nested.carbon.test                       FAILED in 0.6s
//toolchain/parser/testdata:for/simple.carbon.test                       FAILED in 0.8s
//toolchain/parser/testdata:function/definition/with_params.carbon.test  FAILED in 0.8s
//toolchain/parser/testdata:operators/fixity_in_call.carbon.test         FAILED in 0.7s
//toolchain/parser/testdata:operators/fixity_in_var.carbon.test          FAILED in 0.8s
```

Co-authored-by: Chandler Carruth <chandlerc@gmail.com>