Rule lookup as a trie, and `>` for cascade

[webdevred]

Two changes to the same thing. The rule lookup is a linear scan that costs most of what the formatter allocates, and it has no way to say that a rule applies to a node but not below it. Both are the shape of RuleSet.

Which mode each property is read in

• Exact, applies at the matched node only: AutoPad, AlignObjectKeys, AutoPadSubObjects
• Cascading, applies at the node and below: ComplexNewLine, PreserveNumberFormat, Indent, PadDecimals, PadAmount, TrailingComma

The split is hardcoded in doFormatNode and the author of a ruleset cannot change it. The three exact ones are about how a container lays out its own children, which is why they do not cascade.

>

a > b { ... } applies to b and not below it. Everything cascades unless > is used, so the three exact properties above get > to keep behaving as they do now, and the six cascading ones stay as they are.

It restricts and never widens. There is no operator for the opposite, so a property that is exact today cannot be made to cascade.

> does not address long lines, which is worth stating because the two get conflated. Formatting the 37 files in tune-files.txt with complex.jbfl gives 244 lines over 200 characters, 231 of them carrying five keys or more. Small and large objects sit at the same path, since one driveModes settings row holds two keys and the next holds eight, so no selector can tell them apart. That needs a size threshold and is a separate feature.

Order

1. Precedence. Decided and tested, waiting on rank in Rules.hs becoming total and Ord coming out of the deriving clause on NodeSelector. See Rule lookup as a trie #232.
2. The trie: Map NodeSelector to either another RuleSet or a leaf, descending one selector at a time. The leaf carries whether a rule applies at the node or below it.
3. >, letting the syntax set the leaf.

Comparing keys by name was on this list and has been dropped: measured with optimization on it costs nothing.

No format version and no migration tool. The user base is small enough that the behaviour change can land without one.

What counts as unchanged behaviour

examples/formatted_jbeam/ must not change by a byte before step 4. examples/ast/jbfl/*.hs will change at steps 1 and 3, since they store the Show of a Map and both steps reorder or reshape its keys. Regenerate them in commits of their own so each diff is visibly a reordering and nothing else.

Decided along the way

Precedence is specificity, meaning how many nodes a selector can match at that level: a named key, then a positional index, then a prefix key with the longer prefix winning, then the wildcards. It used to be whatever fell out of Ord NodePattern, and one part was wrong: against the key deformGroups the pattern .de* beat .deform*. A less specific pattern still contributes properties the winner does not set, which every shipped ruleset depends on since .* carries Indent and TrailingComma for the whole file.

[webdevred]

What the refactoring does, and what it costs today.

findPropertiesForCursor compares the cursor against every pattern in the set, for every node visited, and each comparison walks both sequences with go (p :<| ps) (b :<| bs). :<| on a Seq is viewl, which allocates once per element, per pattern, per node. On a 150 KB stock body file with the shipped ruleset, built with optimization on:

viewl          23.2 %time   71.7 %alloc
sameBy.go      13.6 %time    0.0 %alloc
filterWithKey   8.9 %time    0.0 %alloc

Almost three quarters of everything the formatter allocates is one Seq view, and close to half the time is the sweep around it. Allocation grows eight times for ten times the input, so this is a large constant rather than an asymptotic problem, and it is paid once per file the formatter touches. --transform reformats every neighbour that referenced a renamed node, which across four stock vehicles was 1, 8, 37 and 52 files.

The earlier version of this comment listed unpackCString# at 15% and put Ord SomeKey in the plan because of it. That measurement came from an unoptimized build. With optimization GHC floats the string literals in propertyName into shared CAFs and the cost disappears entirely, so comparing keys by name is free and that step is dropped.

What replaces it. RuleSet becomes Map NodeSelector to either another RuleSet or a leaf. Matching descends one selector at a time in step with the tree, so it is a lookup per level rather than a scan over every pattern, and no full path is ever compared because there is no full path to compare. The leaf carries what MatchMode decides today, namely whether a rule applies at that node or below it, which is also what > needs somewhere to put.

The lookup can go further later. The cursor grows one breadcrumb at a time in applyCrumb, and under a cascading match a pattern that has matched keeps matching every descendant, so the parent already holds what the child needs. Carrying the surviving positions down in a FormattingState field would make each step one lookup instead of a fresh descent. That is not part of this work; it is only worth doing if the numbers after the trie still say so.

Two parts without a clean shape yet. .* can be a second lookup per level alongside the concrete breadcrumb. Prefix keys cannot be looked up by equality at all, since the stored key is a prefix of the breadcrumb rather than the same text, so that level needs either a scan of just its prefix patterns or a character trie over the key text. .test* is documented in JBFL_DOCS.md and ships with the package, so it has to be solved rather than dropped.