Skip to content

Commit d407efb

Browse files
denbezrukovematipicoautofix-ci[bot]
authored
refactor(formatter): reduce best fitting allocations (#8137)
Co-authored-by: Emanuele Stoppa <[email protected]> Co-authored-by: autofix-ci[bot] <114827586+autofix-ci[bot]@users.noreply.github.com>
1 parent 4976d1b commit d407efb

16 files changed

Lines changed: 1157 additions & 921 deletions

File tree

‎.changeset/blue-teeth-obey.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
"@biomejs/biome": patch
3+
---
4+
5+
Reduced the internal memory used by the Biome formatter.

‎crates/biome_analyze/src/diagnostics.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ impl From<RuleDiagnostic> for AnalyzerDiagnostic {
3333
}
3434

3535
#[derive(Debug)]
36-
enum DiagnosticKind {
36+
pub enum DiagnosticKind {
3737
/// It holds various info related to diagnostics emitted by the rules
3838
Rule(Box<RuleDiagnostic>),
3939
/// We have raw information to create a basic [Diagnostic]
@@ -135,7 +135,7 @@ impl AnalyzerDiagnostic {
135135
}
136136

137137
/// The location of the diagnostic is shifted using this offset.
138-
/// This is only applied when the [Self::kind] is [DiagnosticKind::Rule]
138+
/// This is only applied when the `Self::kind` is [DiagnosticKind::Rule]
139139
pub fn add_diagnostic_offset(&mut self, offset: TextSize) {
140140
if let DiagnosticKind::Rule(rule_diagnostic) = &mut self.kind {
141141
let diagnostic = rule_diagnostic.as_mut();

‎crates/biome_configuration/src/analyzer/assist/actions.rs‎

Lines changed: 4 additions & 4 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎crates/biome_configuration/src/analyzer/linter/rules.rs‎

Lines changed: 8 additions & 8 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎crates/biome_formatter/src/builders.rs‎

Lines changed: 6 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,7 @@
11
use crate::format_element::tag::{Condition, Tag};
22
use crate::prelude::tag::{DedentMode, GroupMode, LabelId};
33
use crate::prelude::*;
4-
use crate::{Argument, Arguments, GroupId, TextRange, TextSize, format_element, write};
4+
use crate::{Argument, Arguments, GroupId, TextRange, TextSize, write};
55
use crate::{Buffer, VecBuffer};
66
use Tag::*;
77
use biome_rowan::{Language, SyntaxNode, SyntaxToken, TextLen, TokenText};
@@ -2669,25 +2669,20 @@ impl<'a, Context> BestFitting<'a, Context> {
26692669

26702670
impl<Context> Format<Context> for BestFitting<'_, Context> {
26712671
fn fmt(&self, f: &mut Formatter<Context>) -> FormatResult<()> {
2672-
let mut buffer = VecBuffer::new(f.state_mut());
26732672
let variants = self.variants.items();
2674-
2675-
let mut formatted_variants = Vec::with_capacity(variants.len());
2673+
// Each variant is wrapped in Start/End tags
2674+
let mut buffer = VecBuffer::with_capacity(variants.len() * 3, f.state_mut());
26762675

26772676
for variant in variants {
2678-
buffer.write_element(FormatElement::Tag(StartEntry))?;
2677+
buffer.write_element(FormatElement::Tag(StartBestFittingEntry))?;
26792678
buffer.write_fmt(Arguments::from(variant))?;
2680-
buffer.write_element(FormatElement::Tag(EndEntry))?;
2681-
2682-
formatted_variants.push(buffer.take_vec().into_boxed_slice());
2679+
buffer.write_element(FormatElement::Tag(EndBestFittingEntry))?;
26832680
}
26842681

26852682
// SAFETY: The constructor guarantees that there are always at least two variants. It's, therefore,
26862683
// safe to call into the unsafe `from_vec_unchecked` function
26872684
let element = unsafe {
2688-
FormatElement::BestFitting(format_element::BestFittingElement::from_vec_unchecked(
2689-
formatted_variants,
2690-
))
2685+
FormatElement::BestFitting(BestFittingVariants::from_vec_unchecked(buffer.into_vec()))
26912686
};
26922687

26932688
f.write_element(element)

‎crates/biome_formatter/src/format_element.rs‎

Lines changed: 117 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ use biome_rowan::TokenText;
99
#[cfg(target_pointer_width = "64")]
1010
use biome_rowan::static_assert;
1111
use std::hash::{Hash, Hasher};
12+
use std::iter::FusedIterator;
1213
use std::ops::Deref;
1314
use std::rc::Rc;
1415

@@ -58,7 +59,7 @@ pub enum FormatElement {
5859

5960
/// A list of different variants representing the same content. The printer picks the best fitting content.
6061
/// Line breaks inside of a best fitting don't propagate to parent groups.
61-
BestFitting(BestFittingElement),
62+
BestFitting(BestFittingVariants),
6263

6364
/// A [Tag] that marks the start/end of some content to which some special formatting is applied.
6465
Tag(Tag),
@@ -229,6 +230,14 @@ impl FormatElement {
229230
pub const fn is_line(&self) -> bool {
230231
matches!(self, Self::Line(_))
231232
}
233+
234+
pub fn tag_kind(&self) -> Option<TagKind> {
235+
if let Self::Tag(tag) = self {
236+
Some(tag.kind())
237+
} else {
238+
None
239+
}
240+
}
232241
}
233242

234243
impl FormatElements for FormatElement {
@@ -279,65 +288,145 @@ impl FormatElements for FormatElement {
279288
/// Provides the printer with different representations for the same element so that the printer
280289
/// can pick the best fitting variant.
281290
///
282-
/// Best fitting is defined as the variant that takes the most horizontal space but fits on the line.
283-
#[derive(Clone, Eq, PartialEq)]
284-
pub struct BestFittingElement {
285-
/// The different variants for this element.
286-
/// The first element is the one that takes up the most space horizontally (the most flat),
287-
/// The last element takes up the least space horizontally (but most horizontal space).
288-
variants: Box<[Box<[FormatElement]>]>,
289-
}
291+
/// The best fitting is defined as the variant
292+
/// that takes the most horizontal space but fits on the line.
293+
/// The different variants for this element.
294+
///
295+
/// The first element is the one that takes up the most space horizontally (the most flat),
296+
/// The last element takes up the least horizontal (most vertical).
297+
#[derive(Clone, Eq, PartialEq, Debug)]
298+
pub struct BestFittingVariants(Box<[FormatElement]>);
290299

291-
impl BestFittingElement {
300+
impl BestFittingVariants {
292301
/// Creates a new best fitting IR with the given variants. The method itself isn't unsafe
293302
/// but it is to discourage people from using it because the printer will panic if
294303
/// the slice doesn't contain at least the least and most expanded variants.
295304
///
296305
/// You're looking for a way to create a `BestFitting` object, use the `best_fitting![least_expanded, most_expanded]` macro.
297306
///
298307
/// ## Safety
299-
/// The slice must contain at least two variants.
308+
/// The slice must contain at least two variants (each delimited by StartEntry/EndEntry tags).
300309
#[doc(hidden)]
301-
pub unsafe fn from_vec_unchecked(variants: Vec<Box<[FormatElement]>>) -> Self {
310+
pub unsafe fn from_vec_unchecked(variants: Vec<FormatElement>) -> Self {
302311
debug_assert!(
303-
variants.len() >= 2,
312+
variants
313+
.iter()
314+
.filter(|element| matches!(element, FormatElement::Tag(Tag::StartBestFittingEntry)))
315+
.count()
316+
>= 2,
304317
"Requires at least the least expanded and most expanded variants"
305318
);
306-
307-
Self {
308-
variants: variants.into_boxed_slice(),
309-
}
319+
Self(variants.into_boxed_slice())
310320
}
311321

312322
/// Returns the most expanded variant
313323
pub fn most_expanded(&self) -> &[FormatElement] {
314-
self.variants.last().expect(
324+
debug_assert!(
325+
self.as_slice()
326+
.iter()
327+
.filter(|element| matches!(element, FormatElement::Tag(Tag::StartBestFittingEntry)))
328+
.count()
329+
>= 2,
330+
"Requires at least the least expanded and most expanded variants"
331+
);
332+
333+
self.into_iter().last().expect(
315334
"Most contain at least two elements, as guaranteed by the best fitting builder.",
316335
)
317336
}
318337

319-
pub fn variants(&self) -> &[Box<[FormatElement]>] {
320-
&self.variants
338+
pub fn as_slice(&self) -> &[FormatElement] {
339+
&self.0
321340
}
322341

323-
pub(crate) fn variants_mut(&mut self) -> &mut [Box<[FormatElement]>] {
324-
&mut self.variants
342+
pub(crate) fn as_slice_mut(&mut self) -> &mut [FormatElement] {
343+
&mut self.0
325344
}
326345

327346
/// Returns the least expanded variant
347+
///
348+
/// # Panics
349+
///
350+
/// When the number of variants is less than two.
328351
pub fn most_flat(&self) -> &[FormatElement] {
329-
self.variants.first().expect(
330-
"Most contain at least two elements, as guaranteed by the best fitting builder.",
331-
)
352+
debug_assert!(
353+
self.as_slice()
354+
.iter()
355+
.filter(|element| matches!(element, FormatElement::Tag(Tag::StartBestFittingEntry)))
356+
.count()
357+
>= 2,
358+
"Requires at least the least expanded and most expanded variants"
359+
);
360+
self.into_iter().next().unwrap()
332361
}
333362
}
334363

335-
impl std::fmt::Debug for BestFittingElement {
336-
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
337-
f.debug_list().entries(&*self.variants).finish()
364+
impl Deref for BestFittingVariants {
365+
type Target = [FormatElement];
366+
367+
fn deref(&self) -> &Self::Target {
368+
self.as_slice()
338369
}
339370
}
340371

372+
pub struct BestFittingVariantsIter<'a> {
373+
elements: &'a [FormatElement],
374+
}
375+
376+
impl<'a> IntoIterator for &'a BestFittingVariants {
377+
type Item = &'a [FormatElement];
378+
type IntoIter = BestFittingVariantsIter<'a>;
379+
380+
fn into_iter(self) -> Self::IntoIter {
381+
BestFittingVariantsIter { elements: &self.0 }
382+
}
383+
}
384+
385+
impl<'a> Iterator for BestFittingVariantsIter<'a> {
386+
type Item = &'a [FormatElement];
387+
388+
fn next(&mut self) -> Option<Self::Item> {
389+
match self.elements.first()? {
390+
FormatElement::Tag(Tag::StartBestFittingEntry) => {
391+
let end = self
392+
.elements
393+
.iter()
394+
.position(|element| {
395+
matches!(element, FormatElement::Tag(Tag::EndBestFittingEntry))
396+
})
397+
.map_or(self.elements.len(), |position| position + 1);
398+
399+
let (variant, rest) = self.elements.split_at(end);
400+
self.elements = rest;
401+
402+
Some(variant)
403+
}
404+
_ => None,
405+
}
406+
}
407+
408+
fn last(mut self) -> Option<Self::Item>
409+
where
410+
Self: Sized,
411+
{
412+
self.next_back()
413+
}
414+
}
415+
416+
impl<'a> DoubleEndedIterator for BestFittingVariantsIter<'a> {
417+
fn next_back(&mut self) -> Option<Self::Item> {
418+
let start_position = self.elements.iter().rposition(|element| {
419+
matches!(element, FormatElement::Tag(Tag::StartBestFittingEntry))
420+
})?;
421+
422+
let (rest, variant) = self.elements.split_at(start_position);
423+
self.elements = rest;
424+
Some(variant)
425+
}
426+
}
427+
428+
impl FusedIterator for BestFittingVariantsIter<'_> {}
429+
341430
pub trait FormatElements {
342431
/// Returns true if this [FormatElement] is guaranteed to break across multiple lines by the printer.
343432
/// This is the case if this format element recursively contains a:

‎crates/biome_formatter/src/format_element/document.rs‎

Lines changed: 16 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -72,13 +72,10 @@ impl Document {
7272
interned_expands
7373
}
7474
},
75-
FormatElement::BestFitting(best_fitting) => {
75+
FormatElement::BestFitting(variants) => {
7676
enclosing.push(Enclosing::BestFitting);
7777

78-
for variant in best_fitting.variants() {
79-
propagate_expands(variant, enclosing, checked_interned);
80-
}
81-
78+
propagate_expands(variants, enclosing, checked_interned);
8279
enclosing.pop();
8380
// BestFitting acts as a boundary, meaning there is no need to continue
8481
// processing this element and we can move onto the next. However, we
@@ -182,9 +179,7 @@ fn transform_elements(
182179
*element = FormatElement::Interned(Interned::new(nested_elements));
183180
}
184181
FormatElement::BestFitting(best_fitting) => {
185-
for variant in best_fitting.variants_mut() {
186-
transform_elements(variant, visitor);
187-
}
182+
transform_elements(best_fitting.as_slice_mut(), visitor);
188183
}
189184
_ => {
190185
if let Some(replacement) = visitor(element) {
@@ -377,8 +372,8 @@ impl Format<IrFormatContext> for &[FormatElement] {
377372
FormatElement::Line(LineMode::Hard),
378373
])?;
379374

380-
for variant in best_fitting.variants() {
381-
write!(f, [variant.deref(), hard_line_break()])?;
375+
for variant in best_fitting {
376+
write!(f, [variant, hard_line_break()])?;
382377
}
383378

384379
f.write_elements([
@@ -586,10 +581,10 @@ impl Format<IrFormatContext> for &[FormatElement] {
586581
StartEmbedded(_) => {
587582
write!(f, [token("embedded(")])?;
588583
}
589-
StartEntry => {
584+
StartEntry | StartBestFittingEntry => {
590585
// handled after the match for all start tags
591586
}
592-
EndEntry => write!(f, [ContentArrayEnd])?,
587+
EndEntry | EndBestFittingEntry => write!(f, [ContentArrayEnd])?,
593588

594589
EndFill
595590
| EndLabelled
@@ -886,9 +881,13 @@ mod tests {
886881
// best_fitting(...)
887882
// ]
888883
let interned = Interned::new(vec![FormatElement::ExpandParent, unsafe {
889-
FormatElement::BestFitting(BestFittingElement::from_vec_unchecked(vec![
890-
Box::new([FormatElement::Token { text: "a" }]),
891-
Box::new([FormatElement::Token { text: "b" }]),
884+
FormatElement::BestFitting(BestFittingVariants::from_vec_unchecked(vec![
885+
FormatElement::Tag(StartBestFittingEntry),
886+
FormatElement::Token { text: "a" },
887+
FormatElement::Tag(EndBestFittingEntry),
888+
FormatElement::Tag(StartBestFittingEntry),
889+
FormatElement::Token { text: "b" },
890+
FormatElement::Tag(EndBestFittingEntry),
892891
]))
893892
}]);
894893

@@ -913,8 +912,8 @@ mod tests {
913912
<interned 0> [
914913
expand_parent,
915914
best_fitting([
916-
["a"]
917-
["b"]
915+
[["a"]]
916+
[["b"]]
918917
])
919918
]
920919
]),

0 commit comments

Comments
 (0)