Skip to content

Improve computational time complexity for printing fill() #16595

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
sosukesuzuki merged 11 commits into from
Aug 23, 2024
Merged

Improve computational time complexity for printing fill() #16595

Show file tree
Hide file tree
Changes from 1 commit
Commits
Show all changes
11 commits
Select commit Hold shift + click to select a range
16088fc
add failing test
seiyab Aug 22, 2024
cdcfd4d
improve computation time complexity for printing fill()
seiyab Aug 22, 2024
1208acd
refactoring
seiyab Aug 22, 2024
daede49
update expected threshold
seiyab Aug 22, 2024
3e7baf5
update test name
seiyab Aug 22, 2024
713b115
refactor (introduce ListOptimizedToPrintFill)
seiyab Aug 22, 2024
964c378
resolve type error
seiyab Aug 22, 2024
3a11e74
make change simpler
seiyab Aug 22, 2024
3ae179f
remove unnecessary line
seiyab Aug 22, 2024
681a603
just hold offset in doc
seiyab Aug 23, 2024
be84e87
rename symbol
seiyab Aug 23, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
just hold offset in doc
  • Loading branch information
@seiyab
seiyab committed Aug 23, 2024
commit 681a603c4651b8c43dd72f1f504e9bce1f01b712
27 changes: 12 additions & 15 deletions src/document/printer.js
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,7 +20,6 @@ import {
} from "./constants.js";
import InvalidDocError from "./invalid-doc-error.js";
import { getDocType, propagateBreaks } from "./utils.js";
import { ListOptimizedToPrintFill } from "./utils/list-optimized-to-print-fill.js";

/** @typedef {typeof MODE_BREAK | typeof MODE_FLAT} Mode */
/** @typedef {{ ind: any, doc: any, mode: Mode }} Command */
Expand All @@ -33,6 +32,8 @@ const MODE_FLAT = Symbol("MODE_FLAT");

const CURSOR_PLACEHOLDER = Symbol("cursor");

const INDEX_OFFSET_OF_FILL = Symbol("INDEX_OFFSET_OF_FILL");
Comment thread
fisker marked this conversation as resolved.
Outdated

function rootIndent() {
return { value: "", length: 0, queue: [] };
}
Expand Down Expand Up @@ -462,19 +463,15 @@ function printDocToString(doc, options) {
case DOC_TYPE_FILL: {
const rem = width - pos;

// Naive implementation with array make this algorithm quadratic. We use specialized List.
// https://github.com/prettier/prettier/issues/3263#issuecomment-344275152
/** @type {ListOptimizedToPrintFill} */
const parts =
doc.parts instanceof ListOptimizedToPrintFill
? doc.parts
: new ListOptimizedToPrintFill(doc.parts);
if (parts.length === 0) {
const offset = doc[INDEX_OFFSET_OF_FILL] ?? 0;
const { parts } = doc;
const length = parts.length - offset;
if (length === 0) {
break;
}

const content = parts.at(0);
const whitespace = parts.at(1);
const content = parts[offset + 0];
const whitespace = parts[offset + 1];
/** @type {Command} */
const contentFlatCmd = { ind, mode: MODE_FLAT, doc: content };
/** @type {Command} */
Expand All @@ -488,7 +485,7 @@ function printDocToString(doc, options) {
true,
);

if (parts.length === 1) {
if (length === 1) {
if (contentFits) {
cmds.push(contentFlatCmd);
} else {
Expand All @@ -502,7 +499,7 @@ function printDocToString(doc, options) {
/** @type {Command} */
const whitespaceBreakCmd = { ind, mode: MODE_BREAK, doc: whitespace };

if (parts.length === 2) {
if (length === 2) {
if (contentFits) {
cmds.push(whitespaceFlatCmd, contentFlatCmd);
} else {
Expand All @@ -511,13 +508,13 @@ function printDocToString(doc, options) {
break;
}

const secondContent = parts.at(2);
const secondContent = parts[offset + 2];

/** @type {Command} */
const remainingCmd = {
ind,
mode,
doc: { ...doc, parts: parts.slice(2) },
doc: { ...doc, [INDEX_OFFSET_OF_FILL]: offset + 2 },
};

/** @type {Command} */
Expand Down
41 changes: 0 additions & 41 deletions src/document/utils/list-optimized-to-print-fill.js
View file
Open in desktop

This file was deleted.