14.2 KB453 lines
Blame
1/**
2 * Copyright (c) Meta Platforms, Inc. and affiliates.
3 *
4 * This source code is licensed under the MIT license found in the
5 * LICENSE file in the root directory of this source tree.
6 */
7
8import type {RecordOf} from 'immutable';
9import type {FlattenLine, LineIdx} from '../linelog';
10
11import {Set as ImSet, List, Record} from 'immutable';
12import {LRU, cachedMethod} from 'shared/LRU';
13import {SelfUpdate} from 'shared/immutableExt';
14import {FileStackState} from './fileStackState';
15
16/**
17 * Represents selections of changes between 2 texts (`a` and `b`), optionally
18 * the selection text can be edited free-form.
19 *
20 * Based on a 3-rev `FlattenLine`s representation:
21 * - Rev 0: The `a` side (not editable by this `ChunkSelectState`).
22 * - Rev 1: The selection (editable by this `ChunkSelectState`).
23 * - Rev 2: The `b` side (not editable by this `ChunkSelectState`).
24 *
25 * Support operations:
26 * - getLines: Obtain lines for rendering. See `SelectLine` for details.
27 * - setSelectedLines: Set line selections. Only added or removed lines can be selected.
28 * - getSelectedText: Obtain selected or edited text.
29 * - setSelectedText: Set edited text. Useful for free-form editing.
30 *
31 * With free-from editing, there are two "special" cases:
32 *
33 * revs | meaning
34 * -----------------------------
35 * {0,1,2} | unchanged
36 * {0,1} | deletion; not selected
37 * {0,2} | special: extra deletion [*]
38 * {0} | deletion; selected
39 * {1,2} | insertion; selected
40 * {1} | special: extra insertion
41 * {2} | insertion; not selected
42 *
43 * [*]: LineLog.flatten() never produces {0,2}. It generates {0} and {2} as
44 * separate lines. But `getLines()` post-processing might produce {0,2} lines.
45 *
46 * The callsite might want to treat the "special: extra insertion" like an
47 * insertion with a different highlighting.
48 *
49 * This state does not care about collapsing unmodified lines, "context lines"
50 * or "code expansion" states. They do not affect editing state, and belong to
51 * the UI components.
52 */
53export class ChunkSelectState extends SelfUpdate<ChunkSelectRecord> {
54 /**
55 * Initialize ChunkSelectState from text `a` and `b`.
56 *
57 * If `selected` is `true`, then all changes are selected, selection result is `b`.
58 * If `selected` is `false`, none of the changes are selected, selection result is `a`.
59 * If `selected` is a string, then the selections are "inferred" from the string.
60 *
61 * If `normalize` is `true`, drop changes in `selected` that is not in `a` or `b`.
62 */
63 static fromText(
64 a: string,
65 b: string,
66 selected: boolean | string,
67 normalize = false,
68 ): ChunkSelectState {
69 const mid = selected === true ? b : selected === false ? a : selected;
70 const fileStack = new FileStackState([a, mid, b]);
71 let lines = fileStack.convertToFlattenLines().map(l => toLineBits(l));
72 if (normalize) {
73 lines = lines.filter(l => l.bits !== 0b101 && l.bits !== 0b010 && l.bits !== 0b000);
74 }
75 return new ChunkSelectState(ChunkSelectRecord({a, b, lines}));
76 }
77
78 /** Get the text of the "a" side. */
79 get a(): string {
80 return this.inner.a;
81 }
82
83 /** Get the text of the "b" side. */
84 get b(): string {
85 return this.inner.b;
86 }
87
88 /**
89 * Get the `SelectLine`s. Useful for rendering the lines.
90 * See `SelectLine` for details.
91 */
92 getLines = cachedMethod(this.getLinesImpl, {cache: getLinesCache});
93 private getLinesImpl(): Readonly<SelectLine[]> {
94 let nextALine = 1;
95 let nextBLine = 1;
96 let nextSelLine = 1;
97 let result: SelectLine[] = [];
98
99 // Modified lines to sort before appending to `result`.
100 let buffer: SelectLine[] = [];
101 const pushBuffer = () => {
102 buffer.sort((a, b) => {
103 // In this order: Deletion, insertion.
104 const aOrder = bitsToOrder[a.bits];
105 const bOrder = bitsToOrder[b.bits];
106 if (aOrder !== bOrder) {
107 return aOrder - bOrder;
108 }
109 return a.rawIndex - b.rawIndex;
110 });
111 // Merge "selected deletion + deselected insertion" with
112 // the same content into "unselectable deletion".
113 let nextDelIndex = 0;
114 buffer.forEach((line, i) => {
115 if (line.bits === 0b001 /* deselected insertion */) {
116 // Try to find the matched "selected deletion" line.
117 while (nextDelIndex < i) {
118 const otherLine = buffer[nextDelIndex];
119 if (otherLine.data === line.data && otherLine.bits === 0b100) {
120 // Change otherLine to "unselectable deletion",
121 // then remove this line.
122 otherLine.bits = 0b101;
123 otherLine.selected = null;
124 otherLine.bLine = line.bLine;
125 otherLine.sign = '!-';
126 line.bits = 0;
127 break;
128 }
129 nextDelIndex += 1;
130 }
131 }
132 });
133 buffer = buffer.filter(line => line.bits !== 0);
134 result = result.concat(buffer);
135 buffer = [];
136 };
137
138 this.inner.lines.forEach((line, rawIndex) => {
139 const bits = line.bits;
140 let sign: Sign = '';
141 let selected: boolean | null = null;
142 let aLine: LineIdx | null = null;
143 let bLine: LineIdx | null = null;
144 let selLine: LineIdx | null = null;
145 // eslint-disable-next-line no-bitwise
146 if (bits >> 2 !== 0) {
147 aLine = nextALine;
148 nextALine += 1;
149 }
150 // eslint-disable-next-line no-bitwise
151 if ((bits & 1) !== 0) {
152 bLine = nextBLine;
153 nextBLine += 1;
154 }
155 // eslint-disable-next-line no-bitwise
156 if ((bits & 2) !== 0) {
157 selLine = nextSelLine;
158 nextSelLine += 1;
159 }
160 switch (bits) {
161 case 0b001:
162 sign = '+';
163 selected = false;
164 break;
165 case 0b010:
166 sign = '!+';
167 break;
168 case 0b011:
169 sign = '+';
170 selected = true;
171 break;
172 case 0b100:
173 sign = '-';
174 selected = true;
175 break;
176 case 0b101:
177 sign = '!-';
178 break;
179 case 0b110:
180 sign = '-';
181 selected = false;
182 break;
183 case 0b111:
184 break;
185 }
186 const selectLine: SelectLine = {
187 rawIndex,
188 aLine,
189 bLine,
190 selLine,
191 sign,
192 selected,
193 bits,
194 data: line.data,
195 };
196 if (sign === '') {
197 pushBuffer();
198 result.push(selectLine);
199 } else {
200 buffer.push(selectLine);
201 }
202 });
203 pushBuffer();
204 return result;
205 }
206
207 /**
208 * Get the line regions. By default, unchanged lines are collapsed.
209 *
210 * `config.contextLines` sets how many lines to expand around
211 * changed or current lines.
212 *
213 * `config.expanded` and `config.caretLine` specify lines to
214 * expanded.
215 */
216 getLineRegions(config?: {
217 contextLines?: number;
218 /** Line numbers on the "A" side to expand. */
219 expandedALines: ImSet<number>;
220 /** Line number on the "M" (selection) side to expand. */
221 expandedSelLine?: number;
222 }): Readonly<LineRegion[]> {
223 const contextLines = config?.contextLines ?? 2;
224 const lines = this.getLines();
225 const expandedSelLine = config?.expandedSelLine ?? -1;
226 const expandedALines = config?.expandedALines ?? ImSet();
227 const regions: LineRegion[] = [];
228
229 // Figure out indexes of `lines` to collapse (skip).
230 const collapsedLines = Array<boolean>(lines.length + contextLines).fill(true);
231 lines.forEach((line, i) => {
232 if (
233 line.bits !== 0b111 ||
234 expandedALines.has(line.aLine ?? -1) ||
235 line.selLine === expandedSelLine
236 ) {
237 for (let j = i + contextLines; j >= 0 && j >= i - contextLines && collapsedLines[j]; j--) {
238 collapsedLines[j] = false;
239 }
240 }
241 });
242
243 // Scan through regions.
244 let currentRegion: LineRegion | null = null;
245 lines.forEach((line, i) => {
246 const same = line.bits === 0b111;
247 const collapsed = collapsedLines[i];
248 if (currentRegion?.same === same && currentRegion?.collapsed === collapsed) {
249 currentRegion.lines.push(line);
250 } else {
251 if (currentRegion !== null) {
252 regions.push(currentRegion);
253 }
254 currentRegion = {lines: [line], same, collapsed};
255 }
256 });
257 if (currentRegion !== null) {
258 regions.push(currentRegion);
259 }
260
261 return regions;
262 }
263
264 /**
265 * Get the text of selected lines. It is the editing result.
266 *
267 * Note: passing `getSelectedText` to `fromText` does not maintain the selection
268 * state. For example, from an empty text to `1\n1\n1\n`. The user might select
269 * the 1st, 2nd, or 3rd line. That's 3 different ways of selections with the same
270 * `getSelectedText` output.
271 */
272 getSelectedText = cachedMethod(this.getSelectedTextImpl, {cache: getSelectedTextCache});
273 private getSelectedTextImpl(): string {
274 return (
275 this.inner.lines
276 // eslint-disable-next-line no-bitwise
277 .filter(l => (l.bits & 0b010) !== 0)
278 .map(l => l.data)
279 .join('')
280 );
281 }
282
283 /**
284 * Calculate the "inverse" of selected text. Useful for `revert -i` or "Discard".
285 *
286 * A Selected B | Inverse Note
287 * 0 0 1 | 1 + not selected, preserve B
288 * 0 1 0 | 0 = preserve B
289 * 0 1 1 | 0 + selected, drop B, preserve A
290 * 1 0 0 | 1 - selected, drop B, preserve A
291 * 1 0 1 | 1 = preserve B
292 * 1 1 0 | 0 - not selected, preserve B
293 * 1 1 1 | 1 = preserve B
294 */
295 getInverseText(): string {
296 return this.inner.lines
297 .filter(l => [0b001, 0b100, 0b101, 0b111].includes(l.bits))
298 .map(l => l.data)
299 .join('');
300 }
301
302 /**
303 * Select or deselect lines.
304 *
305 * `selects` is a list of tuples. Each tuple has a `rawIndex` and whether that
306 * line is selected or not.
307 * Note if a line is deleted (sign is '-'), then selected means deleting that line.
308 *
309 * Note all lines are editable. Lines that are not editable are silently ignored.
310 */
311 setSelectedLines(selects: Array<[LineIdx, boolean]>): ChunkSelectState {
312 const newLines = this.inner.lines.withMutations(mutLines => {
313 let lines = mutLines;
314 selects.forEach(([idx, selected]) => {
315 const line = lines.get(idx);
316 if (line === undefined) {
317 return;
318 }
319 const {bits} = line;
320 // eslint-disable-next-line no-bitwise
321 const bits101 = bits & 0b101;
322 if (bits101 === 0 || bits101 === 0b101) {
323 // Not changed in v0 and v2 - ignore editing.
324 return;
325 }
326 const oldSelected: boolean =
327 // eslint-disable-next-line no-bitwise
328 bits101 === 0b100 ? (bits & 0b010) === 0 : (bits & 0b010) !== 0;
329 if (oldSelected !== selected) {
330 // Update selection by toggling (xor) rev 1.
331 // eslint-disable-next-line no-bitwise
332 const newBits = bits ^ 0b010;
333 const newLine = line.set('bits', newBits as Bits);
334 lines = lines.set(idx, newLine);
335 }
336 });
337 return lines;
338 });
339 return new ChunkSelectState(this.inner.set('lines', newLines));
340 }
341
342 /**
343 * Free-form edit selected text.
344 *
345 * Runs analysis to mark lines as selected. Consider only calling this once
346 * when switching from free-form editing to line selections.
347 */
348 setSelectedText(text: string): ChunkSelectState {
349 const {a, b} = this.inner;
350 return ChunkSelectState.fromText(a, b, text);
351 }
352
353 /**
354 * The constructor is for internal use only.
355 * Use static methods to construct `ChunkSelectState`.
356 */
357 constructor(record: ChunkSelectRecord) {
358 super(record);
359 }
360}
361
362const getLinesCache = new LRU(1000);
363const getSelectedTextCache = new LRU(1000);
364
365/** A line and its position on both sides, and selection state. */
366export type SelectLine = {
367 /** Index in the `lines` internal state. Starting from 0. */
368 rawIndex: LineIdx;
369
370 /** Line index on the `a` side for rendering, or `null` if the line does not exist on the `a` side. */
371 aLine: LineIdx | null;
372
373 /** Line index on the `b` side for rendering, or `null` if the line does not exist on the `b` side. */
374 bLine: LineIdx | null;
375
376 /** Line index for "selected" lines, for rendering, or `null` if the line is not in the "selected" side. */
377 selLine: LineIdx | null;
378
379 /** See `Sign` for description. */
380 sign: Sign;
381
382 /**
383 * Whether the line is selected or not. Only used when sign is '-' or '+'.
384 * Note if a line is deleted (sign is '-'), then selected means deleting that line.
385 */
386 selected: boolean | null;
387
388 /** Line selection bits. */
389 bits: Bits;
390
391 /** Content of the line. */
392 data: string;
393};
394
395/**
396 * A contiguous range of lines that share same properties.
397 * Properties include: "same for all version", "collapsed".
398 */
399export type LineRegion = {
400 /** Lines in the region. */
401 lines: SelectLine[];
402
403 /** If the region has the same content for all versions. */
404 same: boolean;
405
406 /** If the region is collapsed. */
407 collapsed: boolean;
408};
409
410/** '-': deletion; '+': insertion; '': unchanged; '!+', '!-': forced insertion or deletion, not selectable. */
411type Sign = '' | '+' | '-' | '!+' | '!-';
412
413type ChunkSelectProps = {
414 a: string;
415 b: string;
416 lines: List<LineBitsRecord>;
417};
418const ChunkSelectRecord = Record<ChunkSelectProps>({a: '', b: '', lines: List()});
419type ChunkSelectRecord = RecordOf<ChunkSelectProps>;
420
421type Bits = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7;
422
423/** Similar to `FlattenLine` but compress Set<Rev> into 3 bits for easier access. */
424type LineBitsProps = {
425 /** Line content including `\n` EOL. */
426 data: string;
427 /** Bitset. 0b100: left side; 0b001: right side; 0b010: editing / selecting text. */
428 bits: Bits;
429};
430const LineBitsRecord = Record<LineBitsProps>({data: '', bits: 0});
431type LineBitsRecord = RecordOf<LineBitsProps>;
432
433/**
434 * Converts `FlattenLine` to `LineBits`.
435 * `line.revs` (`ImSet<Rev>`) is converted to 3 bits. 0b100: rev 0; 0b010: rev 1; 0b001: rev 2
436 */
437function toLineBits(line: FlattenLine): LineBitsRecord {
438 // eslint-disable-next-line no-bitwise
439 const bits = line.revs.reduce((acc, rev) => acc | (4 >> rev), 0);
440 return LineBitsRecord({data: line.data, bits: bits as Bits});
441}
442
443const bitsToOrder = [
444 0, // 0b000: unused
445 2, // 0b001: normal insertion
446 2, // 0b010: unselectable insertion
447 2, // 0b011: normal insertion
448 1, // 0b100: normal deletion
449 1, // 0b101: unselectable deletion
450 1, // 0b110: normal deletion
451 0, // 0b111: normal
452];
453