feat: new formatter

[asterite]

Description

Problem

Resolves #5281
Resolves #4768
Resolves #4767
Resolves #4766
Resolves #4558
Resolves #4462
Resolves #3945
Resolves #3312

Summary

I thought about trying to extend the existing formatter to format more code, but I couldn't understand it very well: it partially implemented things, and it lacked comments and some explanation of how it works. I think some chunks might have been copied from the Rust formatter. I also took a look into it but though it might be too complex.

I wrote a formatter in the past for Crystal with a technique that I saw was used in the Java formatter written for Eclipse. The idea is to traverse the AST together with a Lexer, writing things along the way, bumping into comments and formatting those, etc. It works pretty well! But that's not enough for the Noir formatter because here we also want to automatically wrap long lines (Crystal's formatter doesn't do that). That part (wrapping) is partially based on this excellent blog post.

Benefits:

• All code kinds are formatted. For example previously traits weren't formatted.
• Comments are never lost.
• Lambdas appearing as the last argument of a call are formatted nicely (this was maybe the most trickier part to get right).
• I believe the new code ends up being simpler than before, even though it's (slightly) longer (previously is was 2138 lines, now it's 6139, though 2608 lines are tests, so it ends up being 3531 lines, but this new formatter does many things the old one didn't). I tried to comment and document it well.
• Adding new formatting rules, new configurations, or enabling formatting of new syntax should be relatively easy to do.
• There are lots and lots of tests for each of the different scenarios. The existing overall formatter tests were kept, but with unit tests it's easier to see how edge cases are formatted.

Here's Aztec-Packages formatted with the new formatter:

• Max line width seems to be respected more (making it more readable)
• unsafe { ... } and comptime { ... } expressions will be inlined if possible (shortening the code and making it more readable)

Additional Context

Some things are subjective. For example Rust will put a function where clause in a separate line, with each trait bound on its own line. The new formatter does that too. But Rust will sometimes put an impl where clause on the same line. It's not clear to me why. I chose to always put where clauses on a separate line, but this could easily be changed if we wanted to.

Documentation

Check one:

• No documentation needed.
• Documentation included in this PR.
• [For Experimental Features] Documentation to be submitted in a separate PR.

PR Checklist

• I have tested the changes locally.
• I have formatted the changes with Prettier and/or cargo fmt on default settings.

[TomAFrench]

LGTM, we've got better coverage of the syntax and actual testing so this is a direct upgrade over the previous formatter.

[aakoshh]

I'm surprised this isn't 'a, since ChunkFormatter<'a, 'b> has a 'b reference to a Formatter<'a> 🤔

[asterite]

Oh, good point, it should be 'a. I don't know why it works, maybe the lifetimes are the same? I'll change it in a follow-up PR after I finish what I'm doing (or feel free to send a PR).