Parse parenthesis in type grammar into syntax tree

[straight-shoota]

The parser currently skips parenthesis in type grammar expressions. It still registers the effects for grouping expressions, so the semantic result is complete.

crystal/src/compiler/crystal/tools/formatter.cr

Lines 132 to 137 in 82920b7

	# When we parse a type, parentheses information is not stored in ASTs, unlike
	# for an Expressions node. So when we are printing a type (Path, ProcNotation, Union, etc.)
	# we increment this when we find a '(', and decrement it when we find ')', but
	# only if `paren_count > 0`: it might be the case of `def foo(x : A)`, but we don't
	# want to print that last ')' when printing the type A.
	@paren_count = 0

But it does not fully capture the syntactic expressiveness. This would be useful for the formatter and other tooling that operates on the syntax tree and needs to be aware of parenthesis semantics. This information would be critical for formatter enhancements that rewrite parenthesis.

In the normal language, parenthesis map to Expressions nodes, which makes a clear assignment possible.

We can transfer that to the type grammar and introduce a similar node. I believe a Union node with a single member could be a good representation for that. It's semantically valid, even though it's technically redundant (a union of one element is equivalent to that element).

Since it's only needed for the syntax tree, we could consider cleaning up those extra nodes afterwards. Or perhaps make their creation conditional.
I suppose it wouldn't be much overhead to have them created in every parse run.

As a first effect, we can simplify the convoluted formatter code for dealing with parenthesis immensely. It's so much cleaner.

And it opens the door to make enhancements such as #11966 and #16728 relatively trivial to implement.

---

Add a 👍 reaction to issues you find important.

[ysbaddaden]

I agree there should be a node to distinguish (A) and (A | B) vs A and A | B, at least for tooling.

Still, it's weird for (A) to become Union(A) and (A | B) to become Union(Union(A | B)). That's redundant and it feels out of place: it's not an union but an extra pair of parenthesis.

Maybe a new AST node, like Group or Paren?

[straight-shoota]

The singleton union is super convenient because it just works. There's no need to introduce a new concept into the AST.
Introducing a new node type seems pretty heavy if we can get this basically for free.

However, regardless of how we represent parenthesis in the tree, I believe it shouldn't leak into the semantic stage.
Otherwise it causes a breaking change for tooling, as evidenced by this spec failure: https://github.com/crystal-lang/crystal/actions/runs/23143275608/job/67224722451?pr=16744

    1) Semantic: def overload matches a union metaclass argument with free var (#8071)
  
         error in line 5
         Error: expected argument #1 to 'foo' to be Nil.class, not (String | Nil).class
         
         Overloads are:
          - foo(x : (T | Nil).class) forall T  from src/compiler/crystal/semantic/ast.cr:6:7 in 'raise'
           from src/compiler/crystal/semantic/ast.cr:5:5 in 'raise'
           from src/array.cr:118:5 in 'raise_argument_type_mismatch'
           from src/reference.cr:71:3 in 'raise_matches_not_found'
           from src/compiler/crystal/semantic/call.cr:294:9 in 'lookup_matches_in_type'
           from src/compiler/crystal/semantic/call.cr:127:17 in 'lookup_matches:with_autocast'
           from src/compiler/crystal/semantic/call.cr:116:5 in 'recalculate'
           from src/compiler/crystal/semantic/main_visitor.cr:1515:7 in 'visit'
           from src/compiler/crystal/syntax/visitor.cr:27:12 in 'accept'
           from src/compiler/crystal/syntax/ast.cr:582:23 in 'accept_children'
           from src/compiler/crystal/syntax/visitor.cr:28:11 in 'accept'
           from src/compiler/crystal/semantic/main_visitor.cr:688:11 in 'visit'
           from src/compiler/crystal/syntax/visitor.cr:27:12 in 'accept'
           from src/compiler/crystal/semantic/main_visitor.cr:7:7 in 'visit_main:process_finished_hooks:cleanup:visitor'
           from src/compiler/crystal/semantic.cr:39:7 in 'semantic'
           from spec/spec_helper.cr:81:10 in 'semantic'
           from spec/compiler/semantic/def_overload_spec.cr:1190:43 in '->'
           from src/spec/example.cr:50:13 in 'internal_run'
           from src/spec/example.cr:38:16 in 'run'
           from src/spec/context.cr:20:23 in 'run'
           from src/spec/context.cr:20:23 in '->'
           from src/crystal/at_exit_handlers.cr:26:17 in 'main'
           from src/crystal/system/unix/main.cr:10:3 in 'main'
           from /lib/x86_64-linux-gnu/libc.so.6 in '??'
           from /lib/x86_64-linux-gnu/libc.so.6 in '__libc_start_main'
           from .build/compiler_spec in '_start'
           from ???
         
  
  Finished in 13:25 minutes
  13188 examples, 0 failures, 1 errors, 23 pending
  
  Failed examples:
  
  crystal spec spec/compiler/semantic/def_overload_spec.cr:1188 # Semantic: def overload matches a union metaclass argument with free var (#8071)

So the lifetime of this AST construct would be limited to the parser stage anyway.
Even more reason to work with existing tools instead of introducing a new node type.

In #16744 I added a commit that removes singleton unions in the normalizer.
Alternatively, we could skip instantiating these nodes in the first place unless a special parser mode for syntax tooling is requested.

[ysbaddaden]

Why would it be more complex? It's actually simpler.

While reading #16477 I didn't understand why we'd print parens for singleton unions (it felt completely illogical). A Paren node makes it obvious.

I replaced the singleton from #16477 with a new Crystal::Paren AST node, and instead of asking every Union if it's a singleton union, we can have an overload for visit(node : Paren). Simple and explicit.

While inspecting, instead of Union(Union(A, B)) (huh?) we see Paren(Union(A, B)) (obvious).

EDIT: the complexity of a new AST node is adding a few overloads to unwrap the wrapped type (TypeLookup, ...).

[straight-shoota]

Introducing a completely new syntax node type is a significant change. We need to make sure that AST visitors can handle this new type. That includes visitors in this repo as well as tooling built around the compiler (such as linter, lsp).

Union however is already covered in all visitors. There's no need to change anything in order to support this new behaviour. Unless you explicitly need to cover the specifics of parenthesis parsing.

An alternative to introducing a new type would be to reuse the existing Expressions with keyword: :parens. This is how we represent parenthesis in the regular language.
This would probably be easier than adding a completely new type, because existing visitors can already handle Expressions. But
we would still need to make sure AST visitors can handle Expressions in the type grammar.

If we can reuse existing semantics, that feels much more appealing than introducing a new concept. Even if it describes a new nuance.

Yes, we have to write conditions to handle singleton unions specially. But that's only necessary in the few cases where it actually needs a distinct behaviour.

[ysbaddaden]

It would be nice to reuse Expressions, but it would mix expressions into type nodes. Isn't that asking for weird bugs? 🙈

I just tried, and an AST node needs to add unwrap overloads to 4 additional visitors (macros/interpreter, semantic/main_visitor, semantic/type_lookup, tools/doc/type): master...ysbaddaden:crystal:feat/parser-union-parens

EDIT: nope, new compiler ends up failing, so yeah, it's not that trivial.

[ysbaddaden]

I'm okay-ish with a singleton union, but that still feels hack-y...

What about an Union#parens? property? A singleton union would be an artifact with an explicit meaning (keep parens), no need to wrap an union in a singleton union, and we wouldn't wonder why the formatter prints parenthesis around a singleton union:

• A <=> A
• (A) <=> Union.new([A], parens: true) (becomes A in semantic/normalizer)
• A, B <=> Union.new([A, B])
• (A, B) <=> Union.new([A, B], parens: true)

Don't get me wrong: it's still hack-ish, but intent is explicit.

[straight-shoota]

An explicit property is indeed better than implicit semantics.

I added that to #16744