14.1 KB376 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 {LineInfo} from '../linelog';
10import type {FileStackIndex} from './commitStackState';
11import type {FileRev, FileStackState} from './fileStackState';
12
13import {Map as ImMap, List, Record} from 'immutable';
14import {diffLines, splitLines} from 'shared/diff';
15import {dedup, nullthrows} from 'shared/utils';
16import {t} from '../i18n';
17import {assert} from '../utils';
18import {max, prev} from './revMath';
19
20/** A diff chunk analyzed by `analyseFileStack`. */
21export type AbsorbEditProps = {
22 /** The start line of the old content (start from 0, inclusive). */
23 oldStart: number;
24 /** The end line of the old content (start from 0, exclusive). */
25 oldEnd: number;
26 /**
27 * The old content to be replaced by newLines.
28 * If you know the full content of the old file as `allLines`, you
29 * can also use `allLines.slice(oldStart, oldEnd)` to get this.
30 */
31 oldLines: List<string>;
32 /** The start line of the new content (start from 0, inclusive). */
33 newStart: number;
34 /** The end line of the new content (start from 0, exclusive). */
35 newEnd: number;
36 /** The new content to replace oldLines. */
37 newLines: List<string>;
38 /**
39 * Which rev introduces the "old" chunk.
40 * The following revs are expected to contain this chunk too.
41 * This is usually the "blame" rev in the stack.
42 */
43 introductionRev: FileRev;
44 /**
45 * File revision (starts from 0) that the diff chunk is currently
46 * selected to apply to. `null`: no selectioin.
47 * Initially, this is the "suggested" rev to absorb to. Later,
48 * the user can change this to a different rev.
49 * Must be >= introductionRev.
50 */
51 selectedRev: FileRev | null;
52 /** The "AbsorbEditId" associated with this diff chunk. */
53 absorbEditId: AbsorbEditId;
54 /** The file stack index (in commitState) associated with this diff chunk. */
55 fileStackIndex?: FileStackIndex;
56};
57
58/**
59 * Represents an absorb edit from the wdir to the stack.
60 *
61 * This looks like a diff chunk, with extra info like "blame" (introductionRev)
62 * and "amend -to" (selectedRev). Note this is not 1:1 mapping to diff chunks,
63 * since one diff chunk might be split into multiple `AbsorbEdit`s if they need
64 * to be absorbed to different commits.
65 */
66export const AbsorbEdit = Record<AbsorbEditProps>({
67 oldStart: 0,
68 oldEnd: 0,
69 oldLines: List(),
70 newStart: 0,
71 newEnd: 0,
72 newLines: List(),
73 introductionRev: 0 as FileRev,
74 selectedRev: null,
75 absorbEditId: 0,
76 fileStackIndex: undefined,
77});
78export type AbsorbEdit = RecordOf<AbsorbEditProps>;
79
80/**
81 * Identifier of an `AbsorbEdit` in a file stack.
82 */
83export type AbsorbEditId = number;
84
85/**
86 * Maximum `AbsorbEditId` (exclusive). Must be an exponent of 2.
87 *
88 * Practically this shares the 52 bits (defined by IEEE 754) with the integer
89 * part of the `Rev`.
90 */
91// eslint-disable-next-line no-bitwise
92const MAX_ABSORB_EDIT_ID = 1 << 20;
93const ABSORB_EDIT_ID_FRACTIONAL_UNIT = 1 / MAX_ABSORB_EDIT_ID;
94
95/** Extract the "AbsorbEditId" from a linelog Rev */
96export function extractRevAbsorbId(rev: FileRev): [FileRev, AbsorbEditId] {
97 const fractional = rev % 1;
98 const integerRev = rev - fractional;
99 const absorbEditId = fractional / ABSORB_EDIT_ID_FRACTIONAL_UNIT - 1;
100 assert(
101 Number.isInteger(absorbEditId) && absorbEditId >= 0,
102 `${rev} does not contain valid AbsorbEditId`,
103 );
104 return [integerRev as FileRev, absorbEditId];
105}
106
107/** Embed an absorbEditId into a Rev */
108export function embedAbsorbId(rev: FileRev, absorbEditId: AbsorbEditId): FileRev {
109 assert(Number.isInteger(rev), `${rev} already has an absorbEditId embedded`);
110 assert(
111 absorbEditId < MAX_ABSORB_EDIT_ID - 1,
112 t(
113 `Number of absorb diff chunks exceeds maximum limit ($count). Please retry with only a subset of the changes.`,
114 {replace: {$count: (absorbEditId + 1).toString()}},
115 ),
116 );
117 return (rev + ABSORB_EDIT_ID_FRACTIONAL_UNIT * (absorbEditId + 1)) as FileRev;
118}
119
120/**
121 * Returns a rev with all absorb edits for this rev included.
122 * For example, `revWithAbsorb(2)` might return something like `2.999`.
123 * */
124export function revWithAbsorb(rev: FileRev): FileRev {
125 return (Math.floor(rev) + 1 - ABSORB_EDIT_ID_FRACTIONAL_UNIT) as FileRev;
126}
127
128/**
129 * Calculate absorb edits for a stack.
130 *
131 * The stack top is treated as `wdir()` to be absorbed to the rest of the
132 * stack. The stack bottom is treated as imutable `public()`.
133 *
134 * All edits in `wdir()` will be broken down and labeled with `AbsorbEditId`s.
135 * If an edit with `id: AbsorbEditId` has a default absorb destination
136 * `x: Rev`, then this edit will be inserted in linelog as rev
137 * `embedAbsorbId(x, id)`, and can be checked out via
138 * `linelog.checkOut(revWithAbsorb(x))`.
139 *
140 * If an edit has no default destination, for example, the surrounding lines
141 * belong to public commit (rev 0), the edit will be left in the `wdir()`,
142 * and can be checked out using `revWithAbsorb(wdirRev)`, where `wdirRev` is
143 * the max integer rev in the linelog.
144 *
145 * Returns `FileStackState` with absorb edits embedded in the linelog, along
146 * with a mapping from the `AbsorbEditId` to the diff chunk.
147 */
148export function calculateAbsorbEditsForFileStack(
149 stack: FileStackState,
150 options?: {fileStackIndex?: FileStackIndex},
151): [FileStackState, ImMap<AbsorbEditId, AbsorbEdit>] {
152 // rev 0 (public), 1, 2, ..., wdirRev-1 (stack top to absorb), wdirRev (wdir virtual rev)
153 const wdirRev = prev(stack.revLength);
154 assert(
155 wdirRev >= 1,
156 'calculateAbsorbEditsForFileStack requires at least one wdir(), one public()',
157 );
158 const fileStackIndex = options?.fileStackIndex;
159 const diffChunks = analyseFileStackWithWdirAtTop(stack, {wdirRev, fileStackIndex});
160 // Drop wdirRev, then re-insert the chunks.
161 let newStack = stack.truncate(wdirRev);
162 let absorbIdToDiffChunk = ImMap<AbsorbEditId, AbsorbEdit>();
163 const diffChunksWithAbsorbId = diffChunks.map(chunk => {
164 absorbIdToDiffChunk = absorbIdToDiffChunk.set(chunk.absorbEditId, chunk);
165 return chunk;
166 });
167 // Re-insert the chunks with the absorbId.
168 newStack = applyFileStackEditsWithAbsorbId(newStack, diffChunksWithAbsorbId);
169 return [newStack, absorbIdToDiffChunk];
170}
171
172/**
173 * Similar to `analyseFileStack`, but the stack contains the "wdir()" at the top:
174 * The stack revisions look like: `[0:public] [1] [2] ... [stackTop] [wdir]`.
175 */
176export function analyseFileStackWithWdirAtTop(
177 stack: FileStackState,
178 options?: {wdirRev?: FileRev; fileStackIndex?: FileStackIndex},
179): List<AbsorbEdit> {
180 const wdirRev = options?.wdirRev ?? prev(stack.revLength);
181 const stackTopRev = prev(wdirRev);
182 assert(stackTopRev >= 0, 'stackTopRev must be positive');
183 const newText = stack.getRev(wdirRev);
184 let edits = analyseFileStack(stack, newText, stackTopRev);
185 const fileStackIndex = options?.fileStackIndex;
186 if (fileStackIndex != null) {
187 edits = edits.map(edit => edit.set('fileStackIndex', fileStackIndex));
188 }
189 return edits;
190}
191
192/**
193 * Given a stack and the latest changes (usually at the stack top),
194 * calculate the diff chunks and the revs that they might be absorbed to.
195 * The rev 0 of the file stack should come from a "public" (immutable) commit.
196 */
197export function analyseFileStack(
198 stack: FileStackState,
199 newText: string,
200 stackTopRev?: FileRev,
201): List<AbsorbEdit> {
202 assert(stack.revLength > 0, 'stack should not be empty');
203 const linelog = stack.convertToLineLog();
204 const oldRev = stackTopRev ?? prev(stack.revLength);
205 const oldText = stack.getRev(oldRev);
206 const oldLines = splitLines(oldText);
207 // The `LineInfo` contains "blame" information.
208 const oldLineInfos = linelog.checkOutLines(oldRev);
209 const newLines = splitLines(newText);
210 const result: Array<AbsorbEdit> = [];
211 let nextAbsorbId = 0;
212 const allocateAbsorbId = () => {
213 const id = nextAbsorbId;
214 nextAbsorbId += 1;
215 return id;
216 };
217 diffLines(oldLines, newLines).forEach(([a1, a2, b1, b2]) => {
218 // a1, a2: line numbers in the `oldRev`.
219 // b1, b2: line numbers in `newText`.
220 // See also [`_analysediffchunk`](https://github.com/facebook/sapling/blob/6f29531e83daa62d9bd3bc58b712755d34f41493/eden/scm/sapling/ext/absorb/__init__.py#L346)
221 let involvedLineInfos = oldLineInfos.slice(a1, a2);
222 if (involvedLineInfos.length === 0 && oldLineInfos.length > 0) {
223 // This is an insertion. Check the surrounding lines, excluding lines from the public commit.
224 const nearbyLineNumbers = dedup([a2, Math.max(0, a1 - 1)]);
225 involvedLineInfos = nearbyLineNumbers.map(i => oldLineInfos[i]);
226 }
227 // Check the revs. Skip public commits. The Python implementation only skips public
228 // for insertions. Here we aggressively skip public lines for modification and deletion too.
229 const involvedRevs = dedup(
230 involvedLineInfos.map(info => info.rev as FileRev).filter(rev => rev > 0),
231 );
232 // Normalize `selectedRev` so it cannot be a public commit (fileRev === 0).
233 // Setting to `null` to make the edit deselected (left in the working copy).
234 const normalizeSelectedRev = (rev: FileRev): FileRev | null => (rev === 0 ? null : rev);
235 if (involvedRevs.length === 1) {
236 // Only one rev. Set selectedRev to this.
237 // For simplicity, we're not checking the "continuous" lines here yet (different from Python).
238 const introductionRev = involvedRevs[0];
239 result.push(
240 AbsorbEdit({
241 oldStart: a1,
242 oldEnd: a2,
243 oldLines: List(oldLines.slice(a1, a2)),
244 newStart: b1,
245 newEnd: b2,
246 newLines: List(newLines.slice(b1, b2)),
247 introductionRev,
248 selectedRev: normalizeSelectedRev(introductionRev),
249 absorbEditId: allocateAbsorbId(),
250 }),
251 );
252 } else if (b1 === b2) {
253 // Deletion. Break the chunk into sub-chunks with different selectedRevs.
254 // For simplicity, we're not checking the "continuous" lines here yet (different from Python).
255 splitChunk(a1, a2, oldLineInfos, (oldStart, oldEnd, introductionRev) => {
256 result.push(
257 AbsorbEdit({
258 oldStart,
259 oldEnd,
260 oldLines: List(oldLines.slice(oldStart, oldEnd)),
261 newStart: b1,
262 newEnd: b2,
263 newLines: List([]),
264 introductionRev,
265 selectedRev: normalizeSelectedRev(introductionRev),
266 absorbEditId: allocateAbsorbId(),
267 }),
268 );
269 });
270 } else if (a2 - a1 === b2 - b1 && involvedLineInfos.some(info => info.rev > 0)) {
271 // Line count matches on both side. No public lines.
272 // We assume the "a" and "b" sides are 1:1 mapped.
273 // So, even if the "a"-side lines blame to different revs, we can
274 // still break the chunks to individual lines.
275 const delta = b1 - a1;
276 splitChunk(a1, a2, oldLineInfos, (oldStart, oldEnd, introductionRev) => {
277 const newStart = oldStart + delta;
278 const newEnd = oldEnd + delta;
279 result.push(
280 AbsorbEdit({
281 oldStart,
282 oldEnd,
283 oldLines: List(oldLines.slice(oldStart, oldEnd)),
284 newStart,
285 newEnd,
286 newLines: List(newLines.slice(newStart, newEnd)),
287 introductionRev,
288 selectedRev: normalizeSelectedRev(introductionRev),
289 absorbEditId: allocateAbsorbId(),
290 }),
291 );
292 });
293 } else {
294 // Other cases, like replacing 10 lines from 3 revs to 20 lines.
295 // It might be possible to build extra fancy UIs to support it
296 // asking the user which sub-chunk on the "a" side matches which
297 // sub-chunk on the "b" side.
298 // For now, we just report this chunk as a whole chunk that can
299 // only be absorbed to the "max" rev where the left side is
300 // "settled" down.
301 result.push(
302 AbsorbEdit({
303 oldStart: a1,
304 oldEnd: a2,
305 oldLines: List(oldLines.slice(a1, a2)),
306 newStart: b1,
307 newEnd: b2,
308 newLines: List(newLines.slice(b1, b2)),
309 introductionRev: max(...involvedRevs, 0),
310 selectedRev: null,
311 absorbEditId: allocateAbsorbId(),
312 }),
313 );
314 }
315 });
316 return List(result);
317}
318
319/**
320 * Apply edits specified by `chunks`.
321 * The `chunk.selectedRev` is expected to include the `AbsorbEditId`.
322 */
323export function applyFileStackEditsWithAbsorbId(
324 stack: FileStackState,
325 chunks: Iterable<AbsorbEdit>,
326): FileStackState {
327 assert(stack.revLength > 0, 'stack should not be empty');
328 let linelog = stack.convertToLineLog();
329 const wdirRev = stack.revLength;
330 const stackTopRev = wdirRev - 1;
331 // Apply the changes. Assuming there are no overlapping chunks, we apply
332 // from end to start so the line numbers won't need change.
333 const sortedChunks = [...chunks].toSorted((a, b) => b.oldEnd - a.oldEnd);
334 sortedChunks.forEach(chunk => {
335 // If not "selected" to amend to a commit, leave the chunk at the wdir.
336 const baseRev = chunk.selectedRev ?? (wdirRev as FileRev);
337 const absorbEditId = nullthrows(chunk.absorbEditId);
338 const targetRev = embedAbsorbId(baseRev, absorbEditId);
339 assert(
340 targetRev >= chunk.introductionRev,
341 `selectedRev ${targetRev} must be >= introductionRev ${chunk.introductionRev}`,
342 );
343 assert(
344 targetRev > 0,
345 'selectedRev must be > 0 since rev 0 is from the immutable public commit',
346 );
347 // Edit the content of a past revision (targetRev, and follow-ups) from a
348 // future revision (oldRev, matches the line numbers).
349 linelog = linelog.editChunk(
350 stackTopRev,
351 chunk.oldStart,
352 chunk.oldEnd,
353 targetRev,
354 chunk.newLines.toArray(),
355 );
356 });
357 return stack.fromLineLog(linelog);
358}
359
360/** Split the start..end chunk into sub-chunks so each chunk has the same "blame" rev. */
361function splitChunk(
362 start: number,
363 end: number,
364 lineInfos: readonly LineInfo[],
365 callback: (_start: number, _end: number, _introductionRev: FileRev) => void,
366) {
367 let lastStart = start;
368 for (let i = start; i < end; i++) {
369 const introductionRev = lineInfos[i].rev as FileRev;
370 if (i + 1 === end || introductionRev != lineInfos[i + 1].rev) {
371 callback(lastStart, i + 1, introductionRev);
372 lastStart = i + 1;
373 }
374 }
375}
376