В этой статье я хочу поделиться своим подходом к решению задачи виртуализации списка элементов неизвестной высоты. Популярные библиотеки решают эту задачу с помощью приблизительных оценочных размеров с последующими замерами и корректировкой. Я хочу описать метод, основанный на привязке индексов к положению скроллбара, который позволяет достаточно точно позиционировать видимый диапазон элементов, при этом, не зная даже приблизительных размеров всех предыдущих элементов, используя только простую математику и родные механизмы позиционирования и разметки браузера.

С примерами работы на TypeScript, React, Vue и Angular можно ознакомиться на домашней странице проекта Layout Virtual.

Репозиторий с проектом тут.

Традиционный подход

Для начала рассмотрим список элементов фиксированной высоты. Чтобы найти начало видимого диапазона, нужно разделить отскроленную высоту полотна (scrollTop) на высоту элемента списка (она одна для всех элементов).Так мы получим количество отскроленных элементов (начальный видимый индекс). Чтобы узнать количество элементов, необходимое для заполнения вьюпорта, нужно высоту вьюпорта разделить на высоту элемента. Всё просто.

Немного сложнее дело обстоит со списком элементов разной известной высоты. Здесь уже необходимо, как минимум на этапе инициализации (а как максимум при каждом изменении состава элементов), пройтись по всем элементам списка и составить массив смещений каждого элемента (префиксные суммы высот всех предыдущих элементов, O(N)) для того чтобы в дальнейшем при прокрутке быстро находить видимый диапазон по смещению за время O(logN) , используя бинарный поиск. Можно оптимизировать проход по всем элементам, “размазав” вычисления по фреймам, чтобы не заморозить интерфейс, а также применить “ленивые” вычисления - пересчитывать смещения элементов, до которых пользователь реально доскролил.

Ещё более интересно дело обстоит со списком элементов неизвестной высоты, динамический список, где высота элементов зависит от их содержимого, а также может меняться в результате изменения ширины элементов и построчного переноса текста. Если в предыдущем случае мы рассчитывали смещение, основываясь на известных высотах элементов, то как быть здесь, когда высоты элементов неизвестны? Задать примерную высоту и далее, по мере прокрутки, обмерять отрисованные элементы (с помощью ResizeObserver например) и корректировать смещение измеренными значениями.

Суть метода

Вместо того чтобы привязывать смещение видимого диапазона элементов к абсолютным значениям их высот, которые неизвестны, можно привязать индексы элементов к процентному соотношению прокрутки.

Представьте себе список из 110 элементов с высотой вьюпорта 100px, индексами от 0 до 109, где каждый элемент имеет высоту 10px. Тогда при положении слайдера скроллбара равному 0% будет соответствовать индекс 0, находящийся у верхнего края вьюпорта. Положение скроллбара в 25% будет соответствовать индексу 25 вверху вьюпорта. Положение скроллбара в 50% будет соответствовать индексу 50 там же вверху. Положение скроллбара в 75% будет соответствовать индексу 75. И наконец, положение скроллбара в 100% будет соответствовать индексу 100 вверху. Здесь для наглядности я специально подобрал размеры и количество так, чтобы процент прокрутки точно соответствовал индексу первого видимого элемента.

Ссылка на пример, чтобы легче было представить.

Из этого примера следует, что первый видимый индекс относится к общему количеству элементов за вычетом количества, которое помещается во вьюпорт, так же как величина прокрутки к полному диапазону прокрутки:

viewportTopIndex / (itemsCount - viewportItemCount) = scrollTop / (scrollHeight - clientHeight)

Но в случае с динамическим списком мы ведь не знаем сколько элементов поместится во вьюпорт?

Якорные точки

Предположим, что существует некоторый элемент, индекс которого соответствует текущему положению скроллбара. Этот элемент не обязательно находится в начале видимого диапазона. Если из предыдущей формулы убрать то, что неизвестно, останется соотношение некого индекса к общему количеству элементов равное процентному отношению величины прокрутки:

index / itemsCount = scrollTop / (scrollHeight - clientHeight)

Этот некий индекс, находящийся в пределах видимого диапазона, будет служить якорем. Его положение будет определяться якорной точкой вьюпорта, процентом прокрутки (правая часть предыдущей формулы) умноженным на высоту вьюпорта:

viewportAnchor = scrollTop / (scrollHeight - clientHeight) * clientHeight

То есть, чем ближе слайдер скроллбара к началу, тем ближе якорная точка будет к верхнему краю видимой области, чем ближе слайдер к концу, тем ближе она будет к низу, ну а при 50% она будет ровно посередине вьюпорта соответственно.

А теперь, чтобы определить положение элемента-якоря в пределах видимой области, выразим индекс из предыдущей формулы и для нашего примера со 110 элементами вычислим его для положения скроллбара, скажем, в 25%:

anchorIndex = scrollTop / (scrollHeight - clientHeight) * itemsCount

0.25 * 110 = 27.5 ←27 - индекс, 0.5 - 50% высоты элемента

Здесь дробная часть “0.5” в получившемся результате отражает процент собственной высоты элемента, на который этот элемент должен находится выше якорной точки вьюпорта. Это значит, что при положении скроллбара в 25% элемент с индексом 27 будет находится на половину своей высоты выше якорной точки, которая в свою очередь, находится на 25% высоты вьюпорта ниже верхнего края.

Теперь если изменить количество элементов в нашем предыдущем примере со 110 на 100 ровно, те элементы, что были первыми видимыми становятся якорями. То есть:

0% - индекс 0
25% - индекс 25
50% - индекс 50
и т.д.

По сути вот эта высота элемента-якоря - это единственная высота, которую нужно измерять в реальном времени для определения положения всех видимых элементов. Нет никакой необходимости в знании ни абсолютных, ни даже примерных размеров всех остальных элементов. Следовательно, при данном подходе отпадает необходимость и в построении массива смещений, бинарном поиске и уж тем более в применении разного рода деревьев (AA-tree, дерево Фенвика и т.д).

Задача сводится к тому чтобы рендерить диапазон элементов, включающий в себя элемент-якорь, и далее позиционировать весь этот диапазон так, чтобы якорь оказался в якорной точке вьюпорта, соответствующей текущему положению скроллбара, т.е. синхронизировать скроллбар с индексами так, чтобы левая и правая часть нашей первой формулы оставались равными. Если выдержать это соотношение, реальный скроллбар и виртуальные элементы всегда будут сходится к началу и концу, независимо от реальных размеров элементов.

Для этого необходимо отделить скроллбар от полотна так чтобы элементы двигались вместе с полотном а скроллбар отражал продвижение индексов.

Есть ещё одна проблема. Адаптивная разметка предполагает рендеринг элементов “как есть” без оберток, трансформаций (transform: translate()) и абсолютного позиционирования. Это значит, что добавление и удаление элементов в начале видимого диапазона будет приводить к смещению всех остальных элементов, которое нужно компенсировать. И если при движении вниз и удалении элементов сверху высота удаляемых элементов известна, то как быть с добавлением элементов неизвестной высоты в начало при движении вверх?

Анатомия контейнера

Для того чтобы решить эту проблему нужно вспомнить свойства Flexbox элементов, а именно свойство flex-grow. Выравнивать контент будем с помощью заполнителей сверху и снизу, где один из заполнителей имеет фиксированную высоту, а второй растягивается, занимая всё оставшееся пространство и придавливая контент к первому заполнителю, как “пружина” к “упору”. Теперь при прокрутке вниз и удалении элементов сверху для компенсации смещения контента вверх необходимо увеличивать верхний “упор” на высоту удаляемых элементов. При добавлении элементов снизу “пружина” сама сожмётся на необходимую величину.

При прокрутке вверх просто меняем местами “пружину” и “упор”. Теперь можно не беспокоиться за добавление элементов неизвестной высоты сверху, браузер сам всё рассчитает.

Чтобы отделить скроллбар от полотна нам необходимо два прокручиваемых контейнера, один внутри другого, только у внутреннего необходимо скрыть скроллбар.

Так если источником скролл события является внутренний контейнер (вьюпорт), то мы отрисовываем нужный диапазон элементов и подстраиваем скроллбар внешнего контейнера под положение элемента-якоря. Здесь стоит отметить, что возможна ситуация, когда якорь не доехал до точки якорения, в этом случае просто увеличиваем (или уменьшаем, в зависимости от направления скролла) положение внешнего скроллбара на 1 и ждем пока доедет. Вероятно, это основной источник погрешности. Когда же источником события является внешний контейнер, мы, опять же, отрисовываем нужный диапазон элементов и подстраиваем полотно внутреннего контейнера так, чтобы элемент-якорь оказался в нужной точке.

Размер заполнителя высоты прокрутки рассчитывается как среднее арифметическое между минимальной и максимальной известной высотой умноженное на количество элементов:

scrollHeightFillerSize = (minItemHeight + maxItemHeight) / 2 * itemsCount

Рендер

Поскольку мы не знаем размеры добавляемых элементов, заполнять вьюпорт будем исходя из минимальной известной высоты чтоб уж наверняка. Предположим у нас есть какой-то отрисованный диапазон и рассчитанный диапазон. Тогда все, что входит в первый, но не входит во второй, удаляем. Все, что находится на пересечении обоих диапазонов оставляем. Все, что включает в себя второй, но не включает первый, добавляем.

Если пересечения диапазонов нет (быстрый скролл), то просто все что есть, удаляется, все, что рассчитано, добавляется.

Но тут возникает другая проблема. Как не отрисовывать слишком много элементов?

Во избежание добавления избыточного количества элементов необходимо ограничить рассчитываемый диапазон с двух сторон: минимальным (или максимальным, в зависимости от направлиения) видимым индексом с одной стороны, и буферной зоной предзагрузки (overscanHeight) в направлении скролла — с другой. Таким образом отрисованный диапазон элементов всегда смещен с запасом в направлении прокрутки. Если этот запас превышает высоту буферной зоны, нет необходимости добавлять еще элементы. То есть, мы как бы “ждем” пока запас не станет меньше высоты буферной зоны (пока элементы не заедут в буферную зону при дальнейшем движении) чтобы добавить новую порцию из рассчитанного диапазона. В моменте в DOM может оказаться чуть больше элементов, чем нужно, но последующий избыточный рендеринг блокируется этим естественным ограничителем.

Так в итоге выглядят границы отрисованного контента в динамике:

Grid разметка

Для того чтоб данный подход работал с сеткой, все что необходимо сделать, это добавить в расчеты еще один параметр - количество колонок, который определяется буквально так:

columnsCount = getComputedStyle(contentLayer).gridTemplateColumns.split(' ').length

Найдем количество строк:

rowsCount = Math.ceil(itemsCount / columnsCount)

Тогда в нашей первой формуле индекс уже будет относится не к общему количеству элементов, а к количеству строк:

index / rowsCount = scrollTop / (scrollHeight - clientHeight)

Таким образом, поддержка Grid-разметки сводится к переходу от индексов элементов к индексам строк. Остальная часть алгоритма остается неизменной.

А чтобы элементы не перескакивали со строки на строку добавлять и удалять элементы в начале видимого диапазона нужно строго в количестве, кратном количеству столбцов.

Итог

Идея родилась из попытки отказаться от вычисления абсолютных смещений элементов вообще и посмотреть на задачу под другим углом. Ведь если в каждый конкретный момент времени мы видим лишь часть диапазона, тогда зачем вычислять невидимую его часть? Задача же не в том, чтобы точно расположить виртуальные элементы там, где они были бы в реальном контейнере, если бы были отрисованы в полном составе. Задача — создать визуальное впечатление соответствия отрисованного контента положению скроллбара. Я представил две шкалы: одна линейная — проценты прокрутки скроллбара, вторая нелинейная — индексы, где каждый индекс обозначает элемент произвольной высоты. Оставалось лишь найти способ сопоставить эти две шкалы вместе.

Алгоритм получился легковесным, предсказуемым и, что самое главное, устойчивым к динамическому изменению контента и адаптивной Grid-разметке. Размер бандла в текущей реализации составляет от 5 до 6 кБ в сжатом виде (где ~4.5 кБ — ядро и ~1.5 кБ — компонент-адаптер для фреймворка). Думаю, что этот размер можно еще сократить.

Данный метод, как и другие, имеет свои ограничения. Однако он позволяет существенно упростить виртуализацию динамических списков и адаптивных сеток.

Покрутить и поресайзить демо, посмотреть код и оценить работу алгоритма вживую на React, Vue или Angular можно на домашней странице проекта. Если вам понравилась идея, заглядывайте в репозиторий — буду рад вашим звездам, фидбеку в комментариях и, конечно же, пул-реквестам!