29901166350

Committed 22 Jul 2026 07:42AM UTC coverage: 98.308% (-0.02%) from 98.332%

Build # 29901166350

Build Type

Pull #2222

github

Committed by

web-flow

Commit Message

Merge 42ab15820 into 56f91ebc1

Pull Request Pull Request #2222: feat: Added virtualization component

Coverage Stats

6106 of 6430 branches covered (94.96%)

Branch coverage included in aggregate %.

1004 of 1018 new or added lines in 7 files covered. (98.62%)

43172 of 43696 relevant lines covered (98.8%)

1545.62 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.02

/src/components/virtualization/engine.ts

/**
 * Probes the browser for the maximum scrollable coordinate it supports.
 */
function getMaxBrowserSizeProbePx(doc: Document): number {
  const container = doc.body ?? doc.documentElement;
  if (!container) {
    return Number.POSITIVE_INFINITY;
  }

  const div = doc.createElement('div');
  div.style.position = 'absolute';
  div.style.top = `${Number.MAX_SAFE_INTEGER}px`;
  container.appendChild(div);
  const size = Math.abs(div.getBoundingClientRect().top);
  container.removeChild(div);
  return size;
}

/**
 * Binary Indexed Tree (Fenwick tree) over item sizes.
 *
 * Replaces the previous O(N) prefix-sum rebuild that occurred on every
 * `measureItem` call. All hot-path operations are O(log N):
 *   - Point update (item measured)        : O(log N)
 *   - Prefix sum (scroll offset)          : O(log N)
 *   - Index at offset (scroll → item)     : O(log N) via binary lifting
 */
class BIT {
  public readonly length: number;

  /** 1-indexed BIT; each cell holds a partial range sum. */
  private readonly _tree: Float64Array;

  /** Raw per-item sizes (0-indexed) — kept for O(1) reads and delta calc. */
  private readonly _sizes: Float64Array;

  /** Running total maintained alongside tree updates in O(1). */
  private _total: number;

  private constructor(
    length: number,
    sizes: Float64Array,
    tree: Float64Array,
    total: number
  ) {
    this.length = length;
    this._sizes = sizes;
    this._tree = tree;
    this._total = total;
  }

  /**
   * Creates a BIT of `length` items all initialized to `fillSize`. O(N).
   */
  public static filled(length: number, fillSize: number): BIT {
    const sizes = new Float64Array(length).fill(fillSize);
    const tree = new Float64Array(length + 1);
    const total = length * fillSize;

    // O(N) build (vs O(N log N) for N individual insertions)
    for (let i = 1; i <= length; i++) {
      tree[i] += fillSize;
      const j = i + (i & -i);
      if (j <= length) {
        tree[j] += tree[i];
      }
    }
    return new BIT(length, sizes, tree, total);
  }

  /**
   * Creates a BIT from an existing sizes array. O(N).
   */
  public static fromSizes(sizes: Float64Array): BIT {
    const length = sizes.length;
    const tree = new Float64Array(length + 1);
    let total = 0;

    for (let i = 1; i <= length; i++) {
      tree[i] += sizes[i - 1];
      total += sizes[i - 1];
      const j = i + (i & -i);
      if (j <= length) {
        tree[j] += tree[i];
      }
    }
    return new BIT(length, sizes, tree, total);
  }

  /** Total size of all items. O(1). */
  public get totalSize(): number {
    return this._total;
  }

  /**
   * Prefix sum of items [0, i) — the virtual scroll offset at the leading
   * edge of item i. O(log N).
   */
  public prefixSum(i: number): number {
    let sum = 0;
    for (let j = i; j > 0; j -= j & -j) {
      sum += this._tree[j];
    }
    return sum;
  }

  /**
   * Update the size of the item at 0-based index.
   * Returns true when the size actually changed. O(log N).
   */
  public update(index: number, newSize: number): boolean {
    if (index < 0 || index >= this.length) return false;

    const old = this._sizes[index];
    if (old === newSize) return false;

    const delta = newSize - old;
    this._sizes[index] = newSize;
    this._total += delta;
    for (let i = index + 1; i <= this.length; i += i & -i) {
      this._tree[i] += delta;
    }
    return true;
  }

  /**
   * Returns a new BIT of `newLength` items.
   * Existing measured sizes are preserved up to `min(this.length, newLength)`;
   * new slots are filled with `fillSize`. Single O(N) build pass.
   */
  public cloneResized(newLength: number, fillSize: number): BIT {
    const sizes = new Float64Array(newLength).fill(fillSize);
    sizes.set(this._sizes.subarray(0, Math.min(this.length, newLength)));
    return BIT.fromSizes(sizes);
  }

  /**
   * Returns the 0-based index of the item that contains the given scroll `offset`,
   * i.e. the largest i such that `prefixSum(i) <= offset < prefixSum(i + 1)`.
   * O(log N) via binary lifting on the internal tree.
   */
  public findIndexAtOffset(offset: number): number {
    if (offset <= 0 || this.length === 0) return 0;

    let idx = 0;
    let remaining = offset;

    for (let bit = 1 << (31 - Math.clz32(this.length)); bit > 0; bit >>= 1) {
      const next = idx + bit;
      if (next <= this.length && this._tree[next] <= remaining) {
        idx = next;
        remaining -= this._tree[idx];
      }
    }
    return Math.min(this.length - 1, idx);
  }
}

/**
 * Describes the currently visible (and over-scanned) range of items.
 */
export interface VisibleRange {
  /** Index of the first rendered item (inclusive) */
  startIndex: number;
  /** Index of the last rendered item (inclusive) */
  endIndex: number;
}

/**
 * Pure scroll-math engine for a single axis of virtual scrolling.
 *
 * All size state is held as plain arrays. Consumers can register an
 * `onSizeChange` callback to react whenever item sizes or the item count
 * changes (e.g. to trigger a Lit `requestUpdate()`).
 */
export class VirtualScrollEngine {
  private _maxBrowserSize = Number.POSITIVE_INFINITY;

  /**
   * The ratio `totalSize / maxBrowserSize` when `totalSize` exceeds the
   * maximum DOM coordinate the browser supports; `1` otherwise.
   * Used to map virtual scroll positions to DOM scroll positions.
   */
  private _virtualRatio = 1;

  /** Binary Indexed Tree for O(log N) size queries and updates. */
  private _tree: BIT | null = null;

  /**
   * Called whenever item sizes or the item count change.
   * Assign a callback (e.g. `() => this.requestUpdate()`) to react to size updates.
   */
  public onSizeChange: (() => void) | null = null;

  /** Total virtual size of all items in px. */
  public get totalSize(): number {
    return this._tree?.totalSize ?? 0;
  }

  /** Actual DOM space size (clamped to the maximum browser size) */
  public get domSize(): number {
    return this._virtualRatio !== 1 ? this._maxBrowserSize : this.totalSize;
  }

  /**
   * Initializes the maximum browser size by probing the document, and updates the virtual ratio accordingly.
   */
  public initMaxBrowserSize(doc: Document): void {
    this._maxBrowserSize = getMaxBrowserSizeProbePx(doc);
    this._updateVirtualRatio();
  }

  /**
   * Grows or shrinks the internal sizes array to `length`.
   * New entries are filled with `estimatedSize`.
   * Existing measured sizes are preserved.
   */
  public resize(length: number, estimatedSize: number): void {
    if (this._tree?.length === length) return;

    this._tree = this._tree
      ? this._tree.cloneResized(length, estimatedSize)
      : BIT.filled(length, estimatedSize);
    this._updateVirtualRatio();
    this.onSizeChange?.();
  }

  /**
   * Records the measured DOM size for a single item.
   */
  public measureItem(index: number, size: number): void {
    if (!this._tree?.update(index, size)) return;

    this._updateVirtualRatio();
    this.onSizeChange?.();
  }

  /**
   * Returns the DOM scroll offset in pixels that brings item at `index` into view
   * at the leading edge of the viewport.
   */
  public getScrollOffsetForIndex(index: number): number {
    if (!this._tree || index <= 0) return 0;

    const clamped = Math.min(index, this._tree.length);
    return this._tree.prefixSum(clamped) / this._virtualRatio;
  }

  /** Returns the item index at the given DOM scroll position. */
  public getIndexAtScroll(scrollPosition: number): number {
    if (!this._tree || scrollPosition <= 0) return 0;
    return this._tree.findIndexAtOffset(scrollPosition * this._virtualRatio);
  }

  /**
   * Returns the visible + over-scanned item range for the given scroll state.
   */
  public getVisibleRange(
    scrollPosition: number,
    viewportSize: number,
    overScan: number,
    totalItems: number
  ): VisibleRange {
    if (totalItems === 0 || viewportSize <= 0) {
      return { startIndex: 0, endIndex: -1 };
    }

    const start = Math.max(0, this.getIndexAtScroll(scrollPosition) - overScan);
    const endScrollPosition = scrollPosition + viewportSize;
    const endRaw = this.getIndexAtScroll(endScrollPosition);
    const end = Math.min(totalItems - 1, endRaw + overScan);

    return { startIndex: start, endIndex: end };
  }

  /**
   * Returns the CSS `translateY` / `translateX` value (px) to apply to the
   * absolutely-positioned content wrapper.
   *
   * The content wrapper is `position: absolute; top: 0; left: 0` inside a
   * track element that is `totalSize` px tall/wide. Translating it to
   * `getContentPosition(startIndex)` places the first rendered item exactly
   * at its virtual scroll position within the track.
   */
  public getContentPosition(index: number): number {
    return this.getScrollOffsetForIndex(index);
  }

  /**
   * Returns the sum of actual sizes for items in [startIndex, endIndex].
   * Used to clamp the content translate offset under coordinate compression
   * so rendered items never overflow past `domSize`.
   */
  public getPhysicalRangeSize(startIndex: number, endIndex: number): number {
    if (!this._tree) return 0;

    const start = Math.max(0, startIndex);
    const end = Math.min(Math.max(endIndex + 1, start), this._tree.length);
    return this._tree.prefixSum(end) - this._tree.prefixSum(start);
  }

  private _updateVirtualRatio(): void {
    const totalSize = this._tree?.totalSize ?? 0;
    this._virtualRatio =
      this._maxBrowserSize === Number.POSITIVE_INFINITY ||
      totalSize <= this._maxBrowserSize
        ? 1
        : totalSize / this._maxBrowserSize;
  }
}

1	/**	9✔
2	* Probes the browser for the maximum scrollable coordinate it supports.	9✔
3	*/	9✔
4	function getMaxBrowserSizeProbePx(doc: Document): number {	129✔
5	const container = doc.body ?? doc.documentElement;	129!
6	if (!container) {	129!
NEW 7	return Number.POSITIVE_INFINITY;	×
NEW 8	}	×
9		129✔
10	const div = doc.createElement('div');	129✔
11	div.style.position = 'absolute';	129✔
12	div.style.top = `${Number.MAX_SAFE_INTEGER}px`;	129✔
13	container.appendChild(div);	129✔
14	const size = Math.abs(div.getBoundingClientRect().top);	129✔
15	container.removeChild(div);	129✔
16	return size;	129✔
17	}	129✔
18		9✔
19	/**	9✔
20	* Binary Indexed Tree (Fenwick tree) over item sizes.	9✔
21	*	9✔
22	* Replaces the previous O(N) prefix-sum rebuild that occurred on every	9✔
23	* `measureItem` call. All hot-path operations are O(log N):	9✔
24	* - Point update (item measured) : O(log N)	9✔
25	* - Prefix sum (scroll offset) : O(log N)	9✔
26	* - Index at offset (scroll → item) : O(log N) via binary lifting	9✔
27	*/	9✔
28	class BIT {	9✔
29	public readonly length: number;	9✔
30		9✔
31	/** 1-indexed BIT; each cell holds a partial range sum. */	9✔
32	private readonly _tree: Float64Array;	9✔
33		9✔
34	/** Raw per-item sizes (0-indexed) — kept for O(1) reads and delta calc. */	9✔
35	private readonly _sizes: Float64Array;	9✔
36		9✔
37	/** Running total maintained alongside tree updates in O(1). */	9✔
38	private _total: number;	9✔
39		9✔
40	private constructor(	9✔
41	length: number,	168✔
42	sizes: Float64Array,	168✔
43	tree: Float64Array,	168✔
44	total: number	168✔
45	) {	168✔
46	this.length = length;	168✔
47	this._sizes = sizes;	168✔
48	this._tree = tree;	168✔
49	this._total = total;	168✔
50	}	168✔
51		9✔
52	/**	9✔
53	* Creates a BIT of `length` items all initialized to `fillSize`. O(N).	9✔
54	*/	9✔
55	public static filled(length: number, fillSize: number): BIT {	9✔
56	const sizes = new Float64Array(length).fill(fillSize);	129✔
57	const tree = new Float64Array(length + 1);	129✔
58	const total = length * fillSize;	129✔
59		129✔
60	// O(N) build (vs O(N log N) for N individual insertions)	129✔
61	for (let i = 1; i <= length; i++) {	129✔
62	tree[i] += fillSize;	13,319✔
63	const j = i + (i & -i);	13,319✔
64	if (j <= length) {	13,319✔
65	tree[j] += tree[i];	13,126✔
66	}	13,126✔
67	}	13,319✔
68	return new BIT(length, sizes, tree, total);	129✔
69	}	129✔
70		9✔
71	/**	9✔
72	* Creates a BIT from an existing sizes array. O(N).	9✔
73	*/	9✔
74	public static fromSizes(sizes: Float64Array): BIT {	9✔
75	const length = sizes.length;	39✔
76	const tree = new Float64Array(length + 1);	39✔
77	let total = 0;	39✔
78		39✔
79	for (let i = 1; i <= length; i++) {	39✔
80	tree[i] += sizes[i - 1];	256✔
81	total += sizes[i - 1];	256✔
82	const j = i + (i & -i);	256✔
83	if (j <= length) {	256✔
84	tree[j] += tree[i];	208✔
85	}	208✔
86	}	256✔
87	return new BIT(length, sizes, tree, total);	39✔
88	}	39✔
89		9✔
90	/** Total size of all items. O(1). */	9✔
91	public get totalSize(): number {	9✔
92	return this._total;	1,728✔
93	}	1,728✔
94		9✔
95	/**	9✔
96	* Prefix sum of items [0, i) — the virtual scroll offset at the leading	9✔
97	* edge of item i. O(log N).	9✔
98	*/	9✔
99	public prefixSum(i: number): number {	9✔
100	let sum = 0;	953✔
101	for (let j = i; j > 0; j -= j & -j) {	953✔
102	sum += this._tree[j];	606✔
103	}	606✔
104	return sum;	953✔
105	}	953✔
106		9✔
107	/**	9✔
108	* Update the size of the item at 0-based index.	9✔
109	* Returns true when the size actually changed. O(log N).	9✔
110	*/	9✔
111	public update(index: number, newSize: number): boolean {	9✔
112	if (index < 0 \|\| index >= this.length) return false;	896!
113		896✔
114	const old = this._sizes[index];	896✔
115	if (old === newSize) return false;	896✔
116		499✔
117	const delta = newSize - old;	499✔
118	this._sizes[index] = newSize;	499✔
119	this._total += delta;	499✔
120	for (let i = index + 1; i <= this.length; i += i & -i) {	896✔
121	this._tree[i] += delta;	1,425✔
122	}	1,425✔
123	return true;	499✔
124	}	896✔
125		9✔
126	/**	9✔
127	* Returns a new BIT of `newLength` items.	9✔
128	* Existing measured sizes are preserved up to `min(this.length, newLength)`;	9✔
129	* new slots are filled with `fillSize`. Single O(N) build pass.	9✔
130	*/	9✔
131	public cloneResized(newLength: number, fillSize: number): BIT {	9✔
132	const sizes = new Float64Array(newLength).fill(fillSize);	39✔
133	sizes.set(this._sizes.subarray(0, Math.min(this.length, newLength)));	39✔
134	return BIT.fromSizes(sizes);	39✔
135	}	39✔
136		9✔
137	/**	9✔
138	* Returns the 0-based index of the item that contains the given scroll `offset`,	9✔
139	* i.e. the largest i such that `prefixSum(i) <= offset < prefixSum(i + 1)`.	9✔
140	* O(log N) via binary lifting on the internal tree.	9✔
141	*/	9✔
142	public findIndexAtOffset(offset: number): number {	9✔
143	if (offset <= 0 \|\| this.length === 0) return 0;	232!
144		232✔
145	let idx = 0;	232✔
146	let remaining = offset;	232✔
147		232✔
148	for (let bit = 1 << (31 - Math.clz32(this.length)); bit > 0; bit >>= 1) {	232✔
149	const next = idx + bit;	1,139✔
150	if (next <= this.length && this._tree[next] <= remaining) {	1,139✔
151	idx = next;	484✔
152	remaining -= this._tree[idx];	484✔
153	}	484✔
154	}	1,139✔
155	return Math.min(this.length - 1, idx);	232✔
156	}	232✔
157	}	9✔
158		9✔
159	/**	9✔
160	* Describes the currently visible (and over-scanned) range of items.	9✔
161	*/	9✔
162	export interface VisibleRange {	9✔
163	/** Index of the first rendered item (inclusive) */	9✔
164	startIndex: number;	9✔
165	/** Index of the last rendered item (inclusive) */	9✔
166	endIndex: number;	9✔
167	}	9✔
168		9✔
169	/**	9✔
170	* Pure scroll-math engine for a single axis of virtual scrolling.	9✔
171	*	9✔
172	* All size state is held as plain arrays. Consumers can register an	9✔
173	* `onSizeChange` callback to react whenever item sizes or the item count	9✔
174	* changes (e.g. to trigger a Lit `requestUpdate()`).	9✔
175	*/	9✔
176	export class VirtualScrollEngine {	9✔
177	private _maxBrowserSize = Number.POSITIVE_INFINITY;	129✔
178		129✔
179	/**	129✔
180	* The ratio `totalSize / maxBrowserSize` when `totalSize` exceeds the	129✔
181	* maximum DOM coordinate the browser supports; `1` otherwise.	129✔
182	* Used to map virtual scroll positions to DOM scroll positions.	129✔
183	*/	129✔
184	private _virtualRatio = 1;	129✔
185		129✔
186	/** Binary Indexed Tree for O(log N) size queries and updates. */	129✔
187	private _tree: BIT \| null = null;	129✔
188		129✔
189	/**	129✔
190	* Called whenever item sizes or the item count change.	129✔
191	* Assign a callback (e.g. `() => this.requestUpdate()`) to react to size updates.	129✔
192	*/	129✔
193	public onSizeChange: (() => void) \| null = null;	129✔
194		9✔
195	/** Total virtual size of all items in px. */	9✔
196	public get totalSize(): number {	9✔
197	return this._tree?.totalSize ?? 0;	1,061!
198	}	1,061✔
199		9✔
200	/** Actual DOM space size (clamped to the maximum browser size) */	9✔
201	public get domSize(): number {	9✔
202	return this._virtualRatio !== 1 ? this._maxBrowserSize : this.totalSize;	842!
203	}	842✔
204		9✔
205	/**	9✔
206	* Initializes the maximum browser size by probing the document, and updates the virtual ratio accordingly.	9✔
207	*/	9✔
208	public initMaxBrowserSize(doc: Document): void {	9✔
209	this._maxBrowserSize = getMaxBrowserSizeProbePx(doc);	129✔
210	this._updateVirtualRatio();	129✔
211	}	129✔
212		9✔
213	/**	9✔
214	* Grows or shrinks the internal sizes array to `length`.	9✔
215	* New entries are filled with `estimatedSize`.	9✔
216	* Existing measured sizes are preserved.	9✔
217	*/	9✔
218	public resize(length: number, estimatedSize: number): void {	9✔
219	if (this._tree?.length === length) return;	176✔
220		168✔
221	this._tree = this._tree	168✔
222	? this._tree.cloneResized(length, estimatedSize)	39✔
223	: BIT.filled(length, estimatedSize);	129✔
224	this._updateVirtualRatio();	176✔
225	this.onSizeChange?.();	176✔
226	}	176✔
227		9✔
228	/**	9✔
229	* Records the measured DOM size for a single item.	9✔
230	*/	9✔
231	public measureItem(index: number, size: number): void {	9✔
232	if (!this._tree?.update(index, size)) return;	896✔
233		499✔
234	this._updateVirtualRatio();	499✔
235	this.onSizeChange?.();	499✔
236	}	896✔
237		9✔
238	/**	9✔
239	* Returns the DOM scroll offset in pixels that brings item at `index` into view	9✔
240	* at the leading edge of the viewport.	9✔
241	*/	9✔
242	public getScrollOffsetForIndex(index: number): number {	9✔
243	if (!this._tree \|\| index <= 0) return 0;	521✔
244		111✔
245	const clamped = Math.min(index, this._tree.length);	111✔
246	return this._tree.prefixSum(clamped) / this._virtualRatio;	111✔
247	}	521✔
248		9✔
249	/** Returns the item index at the given DOM scroll position. */	9✔
250	public getIndexAtScroll(scrollPosition: number): number {	9✔
251	if (!this._tree \|\| scrollPosition <= 0) return 0;	438✔
252	return this._tree.findIndexAtOffset(scrollPosition * this._virtualRatio);	232✔
253	}	438✔
254		9✔
255	/**	9✔
256	* Returns the visible + over-scanned item range for the given scroll state.	9✔
257	*/	9✔
258	public getVisibleRange(	9✔
259	scrollPosition: number,	421✔
260	viewportSize: number,	421✔
261	overScan: number,	421✔
262	totalItems: number	421✔
263	): VisibleRange {	421✔
264	if (totalItems === 0 \|\| viewportSize <= 0) {	421✔
265	return { startIndex: 0, endIndex: -1 };	202✔
266	}	202✔
267		219✔
268	const start = Math.max(0, this.getIndexAtScroll(scrollPosition) - overScan);	219✔
269	const endScrollPosition = scrollPosition + viewportSize;	219✔
270	const endRaw = this.getIndexAtScroll(endScrollPosition);	219✔
271	const end = Math.min(totalItems - 1, endRaw + overScan);	219✔
272		219✔
273	return { startIndex: start, endIndex: end };	219✔
274	}	421✔
275		9✔
276	/**	9✔
277	* Returns the CSS `translateY` / `translateX` value (px) to apply to the	9✔
278	* absolutely-positioned content wrapper.	9✔
279	*	9✔
280	* The content wrapper is `position: absolute; top: 0; left: 0` inside a	9✔
281	* track element that is `totalSize` px tall/wide. Translating it to	9✔
282	* `getContentPosition(startIndex)` places the first rendered item exactly	9✔
283	* at its virtual scroll position within the track.	9✔
284	*/	9✔
285	public getContentPosition(index: number): number {	9✔
286	return this.getScrollOffsetForIndex(index);	421✔
287	}	421✔
288		9✔
289	/**	9✔
290	* Returns the sum of actual sizes for items in [startIndex, endIndex].	9✔
291	* Used to clamp the content translate offset under coordinate compression	9✔
292	* so rendered items never overflow past `domSize`.	9✔
293	*/	9✔
294	public getPhysicalRangeSize(startIndex: number, endIndex: number): number {	9✔
295	if (!this._tree) return 0;	421!
296		421✔
297	const start = Math.max(0, startIndex);	421✔
298	const end = Math.min(Math.max(endIndex + 1, start), this._tree.length);	421✔
299	return this._tree.prefixSum(end) - this._tree.prefixSum(start);	421✔
300	}	421✔
301		9✔
302	private _updateVirtualRatio(): void {	9✔
303	const totalSize = this._tree?.totalSize ?? 0;	796✔
304	this._virtualRatio =	796✔
305	this._maxBrowserSize === Number.POSITIVE_INFINITY \|\|	796✔
306	totalSize <= this._maxBrowserSize	796✔
307	? 1	796!
NEW 308	: totalSize / this._maxBrowserSize;	×
309	}	796✔
310	}	9✔

IgniteUI / igniteui-webcomponents / 29901166350

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous