Currently, LayoutManager has a Heights tree that stores the height of each line in the document. Lines that haven't been laid out yet have an estimated height, and when a line gets laid out, its height is updated to the actual height.

The Heights tree is used for setting the y-offset of lines during layout, telling our parent NSScrollView how tall the document is, and translating back and forth between position in the underlying text and y-offset in the TextView, which is used for mouse handling, system IME integration, etc.

For large documents, creating this tree can take a long time, contributing to slow document loading. While we could create the heights tree asynchronously in the background, it would be nicer if we could find a way to "virtualize" the heights tree, so that it only contains the heights of the lines on the screen.

For practical purposes, I think this is necessary for #124.

This is a hard problem. Here are some thoughts and questions:

Does this even have to be a tree? If we're really only keeping the heights that are in the viewport, perhaps we can just store the full estimated document height and an array of line heights that are present in the viewport.

If it does stay a tree, we could just relax the restriction that each position in a HeightsLeaf represents a line: at the start, the empty heights tree can have a single range (0..<buffer.count) with a height estimated from the total number of characters in the file. If we ever virtualize the text contents itself (i.e. don't load the full file into memory), we can base the initial height estimate on the number of bytes in the file.

If we're half way through the document and there are 10 lines in the viewport, the tree should contain 12 ranges – one range for everything before the viewport, the 10 lines in the viewport, and one range for everything after the viewport. That said, the tree could just as easily have multiple dense ranges separated by multiple sparse ranges. The data representation is the same.

How to calculate the minY or maxY of the line fragment containing index i?

• Take the height of the range containing i and multiply it by (i - range.lowerBound)/range.count. We can get an even better estimate if we give Heights some metrics, like the width of the viewport and the average width of a character.
• This won't be good enough for clicking within the viewport though.
  • One option: if an (x, y) position is contained within the viewport, iterate through the viewports layers to get exact locations.

How to know whether the document grew or shrunk after laying out a line? This is important for things like scroll correction.

• If the old line range exactly coincides with a range of a Line in the viewport, we know the old height precisely.
• If it doesn't, find the range containing (or ranges overlapping) range, take the height of the containing range, and multiply it by range.count / containingRange.count. This is the old height. The new height should be known because we just did layout.
  • Similar to above, if we pass in some metrics like the width of the viewport and the average width of a character, we can have even more accurate estimates.