Skip to content

Refactor line building#4497

Merged
laurmaedje merged 1 commit intomainfrom
line-refactor
Jul 4, 2024
Merged

Refactor line building#4497
laurmaedje merged 1 commit intomainfrom
line-refactor

Conversation

@laurmaedje
Copy link
Member

@laurmaedje laurmaedje commented Jul 4, 2024

This PR refactors line building in paragraphs and adjacent code to improve correctness and maintainability. The code is now much simpler to follow and a few bugs have been fixed as a result.

  • The Line struct doesn't use the first, inner, last setup anymore. Instead it holds a Vec of Cow-like items. This enables various simplifications in the code. I also experimented with smallvec, but it didn't actually give any gains. Allocations do not seem to be the bottleneck here.

  • The reshaping code has gotten much simpler. Previously it was riddled with endless hard-to-follow conditions. Now all line-intersecting paragraph items are just iterated and everything that's split is reshaped. The line-intersecting was made much more efficient in the worst case. Previously, it was $O(n^2)$ with $n$ being the number of items, now it's $O(n)$. This doesn't make a big difference for normal paragraphs, but very long raw blocks, for example, do profit from it. And it's just good to not have accidental quadratic runtime.

  • BiDi reordering now happens eagerly in fn line instead of in fn commit. This means that line boundaries are actually properly known while the line is measured, improving correctness. BiDi reordering is now also fully skipped if the paragraph is mono-directional.

  • Line trimming was improved so that paragraphs with explicit trailing whitespace layout as intended (fixes Paragraphs with explicit trailing whitespace don't layout as intended #597). Also fixes a bug with equations (fixes Extra space is added when a line is broken at the beginning of an inline equation #4278). Trimming now also works in front of tags (there was no issue for this, but it was a bug).

  • A few bugs related to empty paragraphs (#"") have been fixed.

@laurmaedje laurmaedje enabled auto-merge July 4, 2024 10:57
@laurmaedje laurmaedje added this pull request to the merge queue Jul 4, 2024
Merged via the queue into main with commit 0ef672c Jul 4, 2024
@laurmaedje laurmaedje deleted the line-refactor branch July 4, 2024 12:21
Myriad-Dreamin pushed a commit to Myriad-Dreamin/typst that referenced this pull request Jul 9, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

1 participant