Skip to content

Commit cff348c

Browse files
committed
fix(web): bound spreadsheet merge selection expansion
1 parent e0379fb commit cff348c

2 files changed

Lines changed: 100 additions & 16 deletions

File tree

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
import { describe, expect, it } from "vite-plus/test";
2+
3+
import { coverMerges } from "./sheet-cells";
4+
5+
describe("coverMerges", () => {
6+
it.each([false, true])("expands a long merge chain (reversed: %s)", (reversed) => {
7+
const count = 15_000;
8+
const merges = Array.from({ length: count }, (_, i) => ({
9+
top: i,
10+
bottom: i + 1,
11+
left: i % 2,
12+
right: i % 2,
13+
}));
14+
if (reversed) merges.reverse();
15+
const range = { top: count, bottom: count, left: 0, right: 1 };
16+
17+
expect(coverMerges(range, merges)).toEqual({ ...range, top: 0 });
18+
expect(range.top).toBe(count);
19+
});
20+
21+
it("revisits merges reached through expansion on every edge without including distant merges", () => {
22+
const merges = [
23+
{ top: 1, bottom: 1, left: 0, right: 2 },
24+
{ top: 1, bottom: 2, left: 3, right: 3 },
25+
{ top: 3, bottom: 3, left: 3, right: 5 },
26+
{ top: 2, bottom: 5, left: 2, right: 2 },
27+
{ top: 6, bottom: 7, left: 6, right: 7 },
28+
];
29+
const range = { top: 3, bottom: 3, left: 2, right: 3 };
30+
31+
expect(coverMerges(range, merges)).toEqual({ top: 1, bottom: 5, left: 0, right: 5 });
32+
expect(coverMerges(range, [])).toEqual(range);
33+
expect(coverMerges({ top: 6, bottom: 6, left: 0, right: 0 }, merges)).toEqual({
34+
top: 6,
35+
bottom: 6,
36+
left: 0,
37+
right: 0,
38+
});
39+
});
40+
});

‎apps/web/src/components/files/office/sheet-cells.ts‎

Lines changed: 60 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -46,23 +46,67 @@ export function parseRange(a1: string): CellRange | undefined {
4646

4747
/** Grows a range until it covers every merged cell it touches, as Excel selects. */
4848
export function coverMerges(range: CellRange, merges: readonly CellRange[]): CellRange {
49-
const grown = merges.reduce(
50-
(current, merge) =>
51-
overlaps(current, merge)
52-
? {
53-
top: Math.min(current.top, merge.top),
54-
left: Math.min(current.left, merge.left),
55-
bottom: Math.max(current.bottom, merge.bottom),
56-
right: Math.max(current.right, merge.right),
57-
}
58-
: current,
59-
range,
60-
);
61-
62-
// A merge the range grew into can touch another one it did not reach before.
63-
if (same(grown, range)) return grown;
49+
let grown = range;
50+
for (let pass = 0; pass < 2; pass++) {
51+
const next = merges.reduce(
52+
(current, merge) =>
53+
overlaps(current, merge)
54+
? {
55+
top: Math.min(current.top, merge.top),
56+
left: Math.min(current.left, merge.left),
57+
bottom: Math.max(current.bottom, merge.bottom),
58+
right: Math.max(current.right, merge.right),
59+
}
60+
: current,
61+
grown,
62+
);
63+
if (same(next, grown)) return next;
64+
grown = next;
65+
}
6466

65-
return coverMerges(grown, merges);
67+
// Each overlap inequality becomes true only once as the selection grows. Sweep sorted
68+
// edges so a chain of merges cannot force repeated full scans or recursive stack growth.
69+
const sweeps = (
70+
[
71+
{ mergeEdge: "top", rangeEdge: "bottom", direction: 1 },
72+
{ mergeEdge: "bottom", rangeEdge: "top", direction: -1 },
73+
{ mergeEdge: "left", rangeEdge: "right", direction: 1 },
74+
{ mergeEdge: "right", rangeEdge: "left", direction: -1 },
75+
] as const
76+
).map(({ mergeEdge, rangeEdge, direction }) => ({
77+
rangeEdge,
78+
direction,
79+
position: 0,
80+
edges: merges
81+
.map((merge, index) => ({ index, value: direction * merge[mergeEdge] }))
82+
.sort((a, b) => a.value - b.value),
83+
}));
84+
const crossed = new Uint8Array(merges.length);
85+
let changed;
86+
do {
87+
changed = false;
88+
for (const sweep of sweeps) {
89+
let edge = sweep.edges[sweep.position];
90+
while (edge && edge.value <= sweep.direction * grown[sweep.rangeEdge]) {
91+
const index = edge.index;
92+
crossed[index] = crossed[index]! + 1;
93+
if (crossed[index] === 4) {
94+
const merge = merges[index]!;
95+
const next = {
96+
top: Math.min(grown.top, merge.top),
97+
left: Math.min(grown.left, merge.left),
98+
bottom: Math.max(grown.bottom, merge.bottom),
99+
right: Math.max(grown.right, merge.right),
100+
};
101+
changed ||= !same(grown, next);
102+
grown = next;
103+
}
104+
edge = sweep.edges[++sweep.position];
105+
}
106+
}
107+
} while (changed);
108+
109+
return grown;
66110
}
67111

68112
/**

0 commit comments

Comments
 (0)