Fix two bugs around pinned states in the Solver and SolutionCache. (#1409)
Fix two bugs around pinned states in the Solver and SolutionCache.
I was working on an unrelated bug fix and I stumbled into a couple of
incorrect formats in some complex examples. After poking around, I found
two bugs:
- In SolutionCache, it always used the given state of the root Piece
even if that state wasn't explicitly bound in the parent Solution.
This causes incorrect output if we are separately formatting a child,
the parent Solution doesn't bind the child's root, and the best state
for the child is *not* the unsplit state.
That's a rare enough combination of events that none of the existing
tests hit it, but I'll have some new tests for the unrelated bug fix
that do.
- In Solution, when applying constraints between pieces, it doesn't
take into account conflicts from pinned pieces. This bug was
introduced by #1407. It wasn't caught because the one test that
happens to tickle this doesn't tickle it when a certain child piece
is formatted separately, but does if you disable that optimization.
The fix to SolutionCache also means we no longer use the root piece's
state as part of the cache key. Somewhat surprisingly, it doesn't seem
to be necessary. Taking the state out of the cache key is good because
it means we're able to reuse more cached Solutions in different
contexts. This PR makes the large benchmark about 5% faster.
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 78a6193..35f27ae 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,8 @@
+## 2.3.6-wip
+
+There are no user-visible changes in this release. The only changes are behind
+the `tall-style` experiment flag.
+
## 2.3.5
* Ensure switch expressions containing line comments split (#1404).
diff --git a/lib/src/back_end/code_writer.dart b/lib/src/back_end/code_writer.dart
index 751af83..5d13bec 100644
--- a/lib/src/back_end/code_writer.dart
+++ b/lib/src/back_end/code_writer.dart
@@ -266,7 +266,7 @@
/// writer's [_solution].
void _formatSeparate(Piece piece) {
var solution = _cache.find(
- _pageWidth, piece, _solution.pieceState(piece), _pendingIndent);
+ _pageWidth, piece, _pendingIndent, _solution.pieceStateIfBound(piece));
_pendingIndent = 0;
_flushWhitespace();
diff --git a/lib/src/back_end/solution.dart b/lib/src/back_end/solution.dart
index 2e557e4..5cf275f 100644
--- a/lib/src/back_end/solution.dart
+++ b/lib/src/back_end/solution.dart
@@ -128,11 +128,16 @@
_nextPieceToExpand = nextPieceToExpand;
}
- /// The state this solution selects for [piece].
+ /// The state that [piece] is pinned to or that this solution selects.
///
/// If no state has been selected, defaults to the first state.
- State pieceState(Piece piece) =>
- piece.pinnedState ?? _pieceStates[piece] ?? State.unsplit;
+ State pieceState(Piece piece) => pieceStateIfBound(piece) ?? State.unsplit;
+
+ /// The state that [piece] is pinned to or that this solution selects.
+ ///
+ /// If no state has been selected, returns `null`.
+ State? pieceStateIfBound(Piece piece) =>
+ piece.pinnedState ?? _pieceStates[piece];
/// Whether [piece] has been bound to a state in this set (or is pinned).
bool isBound(Piece piece) =>
@@ -278,7 +283,7 @@
if (overflow > 0) '($overflow over)',
if (!isValid) '(invalid)',
states.join(' '),
- ].join(' ');
+ ].join(' ').trim();
}
/// Attempts to add a binding from [piece] to [state] in [boundStates], and
@@ -302,7 +307,7 @@
if (!success) return;
// Apply the new binding if it doesn't conflict with an existing one.
- switch (boundStates[thisPiece]) {
+ switch (thisPiece.pinnedState ?? boundStates[thisPiece]) {
case null:
// Binding a unbound piece to a state.
additionalCost += thisPiece.stateCost(thisState);
diff --git a/lib/src/back_end/solution_cache.dart b/lib/src/back_end/solution_cache.dart
index 892fee0..b2b5184 100644
--- a/lib/src/back_end/solution_cache.dart
+++ b/lib/src/back_end/solution_cache.dart
@@ -9,10 +9,10 @@
/// Maintains a cache of [Piece] subtrees that have been previously solved.
///
/// If a given [Piece] has newlines before and after it, then (in most cases,
-/// assuming there are no other constraints), then the way it is formatted
-/// really only depends on its leading indentation and state. In that case, we
-/// can format that piece using a separate Solver and insert the results in any
-/// Solution that has that piece at that leading indentation.
+/// assuming there are no other constraints) the way it is formatted only
+/// depends on its leading indentation. In that case, we can format that piece
+/// using a separate Solver and insert the results in any Solution that has
+/// that piece at that leading indentation.
///
/// This cache stores those previously formatted subtree pieces so that
/// [CodeWriter] can reuse them across [Solution]s.
@@ -27,23 +27,28 @@
/// Returns a previously cached solution for formatting [root] with leading
/// [indent] or produces a new solution, caches it, and returns it.
- Solution find(int pageWidth, Piece root, State state, int indent) {
+ ///
+ /// If [root] is already bound to a state in the surrounding piece tree's
+ /// [Solution], then [stateIfBound] is that state. Otherwise, it is treated
+ /// as unbound and the cache will find a state for [root] as well as its
+ /// children.
+ Solution find(int pageWidth, Piece root, int indent, State? stateIfBound) {
// See if we've already formatted this piece at this indentation. If not,
// format it and store the result.
return _cache.putIfAbsent(
- (root, state, indent: indent),
+ (root, indent: indent),
() => Solver(this, pageWidth: pageWidth, leadingIndent: indent)
- .format(root, state));
+ .format(root, stateIfBound));
}
}
/// The key used to uniquely identify a previously formatted Piece.
///
-/// Each subtree solution depends only on the Piece, the State it's bound to,
-/// and amount of leading indentation in the context where it appears (which
-/// may vary based on how surrounding pieces end up splitting).
+/// Each subtree solution depends only on the Piece and the amount of leading
+/// indentation in the context where it appears (which may vary based on how
+/// surrounding pieces end up splitting).
///
/// In particular, note that if surrounding pieces split in *different* ways
/// that still end up producing the same overall leading indentation, we are
/// able to reuse a previously cached Solution for some Piece.
-typedef _Key = (Piece, State, {int indent});
+typedef _Key = (Piece, {int indent});
diff --git a/lib/src/back_end/solver.dart b/lib/src/back_end/solver.dart
index c890ea2..4648d6d 100644
--- a/lib/src/back_end/solver.dart
+++ b/lib/src/back_end/solver.dart
@@ -51,28 +51,32 @@
///
/// If [rootState] is given, then [root] is bound to that state.
Solution format(Piece root, [State? rootState]) {
- var solution = Solution(_cache, root,
- pageWidth: _pageWidth,
- leadingIndent: _leadingIndent,
- rootState: rootState);
if (debug.traceSolver) {
var unsolved = <Piece>[];
void traverse(Piece piece) {
- if (piece.additionalStates.isNotEmpty &&
- piece.pinnedState == null &&
- !solution.isBound(piece)) {
- unsolved.add(piece);
- }
+ if (piece.states.length > 1) unsolved.add(piece);
piece.forEachChild(traverse);
}
traverse(root);
- debug.log(debug.bold('Solving $root for ${unsolved.join(' ')}:'));
+ var label = [
+ 'Solving $root',
+ if (rootState != null) 'at state $rootState',
+ if (unsolved.isNotEmpty) 'for ${unsolved.join(', ')}',
+ ].join(' ');
+
+ debug.log(debug.bold('$label:'));
+ debug.indent();
debug.log(debug.pieceTree(root));
}
+ var solution = Solution(_cache, root,
+ pageWidth: _pageWidth,
+ leadingIndent: _leadingIndent,
+ rootState: rootState);
+
_queue.add(solution);
// The lowest cost solution found so far that does overflow.
@@ -87,7 +91,7 @@
tries++;
if (debug.traceSolver) {
- debug.log(debug.bold('#$tries $solution'));
+ debug.log(debug.bold('Try #$tries $solution'));
debug.log(solution.text);
debug.log('');
}
@@ -116,6 +120,7 @@
// If we didn't find a solution without overflow, pick the least bad one.
if (debug.traceSolver) {
+ debug.unindent();
debug.log(debug.bold('Solved $root to $best:'));
debug.log(best.text);
debug.log('');
diff --git a/pubspec.yaml b/pubspec.yaml
index 0d19a28..be4f69c 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,6 +1,6 @@
name: dart_style
# Note: See tool/grind.dart for how to bump the version.
-version: 2.3.5
+version: 2.3.6-wip
description: >-
Opinionated, automatic Dart source code formatter.
Provides an API and a CLI tool.
