Invalidate eagerly by newline constraint

Propagate newline constrains eagerly when binding states in a Solution.

One of the main ways the formatter defines its formatting style is by having constraints that prohibit newlines in some child pieces when a parent is in a given state.

The two simplest examples (which cover a large amount of code) is that when an InfixPiece or a ListPiece is in State.unsplit, they don't allow any newlines in any of their children. That constraint effectively creates the desired style which is that a split inside an infix operand or list element forces the surrounding expression to split.

Whenever we bind a parent piece to some state, we can now ask it if it allows any of its children to contain newlines. For any given child, if the answer is "no" then:

If the child is already bound to a state that contains newlines, then we know this solution is a dead end. It and every solution you can ever derive from it will contain an invalid newline.
If the child isn't bound to a state yet, we can still look at all of its states and see which of them contain newlines. Any state that does can be eliminated because we'll never successfully bind the child to that state without violating this constraint.

It may turn out that no states are left, in which case again we have a dead end solution.

Or there may be just one valid state (usually State.unsplit), and we can immediately the child to that state and do this whole process recursively for this child.

Or there may be just a couple of states left and we can at least winnow this child's states down to that list when we go to expand it later.

The end result is that even before actually formatting a solution, we can often tell if it's a dead end and discard it. If not, we can often bind a whole bunch of the bound piece's children in one go instead of having to do them one at a time and slowly formatting the interim solutions at each step.

The end result is a pretty decent improvement. Here's the micro benchmarks:

Benchmark (tall)                fastest   median  slowest  average  baseline
-----------------------------  --------  -------  -------  -------  --------
block                             0.070    0.071    0.122    0.075     92.7%
chain                             0.640    0.654    0.681    0.655    254.5%
collection                        0.175    0.180    0.193    0.181     96.3%
collection_large                  0.930    0.955    0.988    0.955     97.2%
conditional                       0.067    0.068    0.086    0.071    132.4%
curry                             0.596    0.608    1.478    0.631    278.9%
flutter_popup_menu_test           0.293    0.302    0.326    0.303    141.4%
flutter_scrollbar_test            0.160    0.166    0.184    0.166     96.1%
function_call                     1.460    1.483    1.680    1.490     97.5%
infix_large                       0.709    0.733    0.761    0.733     97.4%
infix_small                       0.175    0.181    0.198    0.181     93.0%
interpolation                     0.091    0.096    0.118    0.096     98.7%
large                             3.514    3.574    3.767    3.596    129.5%
top_level                         0.146    0.150    0.182    0.152    106.7%

There's a slight regression on some of the tiny microbenchmarks (probably because there's some overhead traversing and binding children to State.unsplit when that solution ends up winning anyway). But the improvement to the larger ones is significant.

More interesting is the overall performance. Here's formatting the Flutter repo:

Current formatter     10.964 ========================================
This PR                8.826 ================================
Short style formatter  4.558 ================

The current formatter is 58.43% slower than the old short style formatter.

This PR is 24.22% faster than the current formatter. It's 48.36% slower than the old formatter, but it gets the formatter 33.37% of the way to the old short style one.

dart-lang / dart_style

Invalidate eagerly by newline constraint #1495