71.0 KB2090 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 {Hash, RepoPath} from 'shared/types/common';
10import type {
11 ExportFile,
12 ExportStack,
13 ImportAction,
14 ImportCommit,
15 ImportStack,
16 Mark,
17} from 'shared/types/stack';
18import type {AbsorbEdit, AbsorbEditId} from './absorb';
19import type {CommitRev, FileFlag, FileMetadata, FileRev, FileStackIndex} from './common';
20
21import deepEqual from 'fast-deep-equal';
22import {Map as ImMap, Set as ImSet, List, Record, Seq, is} from 'immutable';
23import {LRU, cachedMethod} from 'shared/LRU';
24import {SelfUpdate} from 'shared/immutableExt';
25import {firstLine, generatorContains, nullthrows, zip} from 'shared/utils';
26import {
27 commitMessageFieldsSchema,
28 commitMessageFieldsToString,
29 mergeCommitMessageFields,
30 parseCommitMessageFields,
31} from '../CommitInfoView/CommitMessageFields';
32import {WDIR_NODE} from '../dag/virtualCommit';
33import {t} from '../i18n';
34import {readAtom} from '../jotaiUtils';
35import {assert} from '../utils';
36import {
37 calculateAbsorbEditsForFileStack,
38 embedAbsorbId,
39 extractRevAbsorbId,
40 revWithAbsorb,
41} from './absorb';
42import {
43 ABSENT_FILE,
44 ABSENT_FLAG,
45 Base85,
46 CommitIdx,
47 CommitState,
48 DataRef,
49 DateTuple,
50 FileIdx,
51 FileState,
52 isAbsent,
53 isContentSame,
54 isRename,
55 isUtf8,
56 toMetadata,
57} from './common';
58import {FileStackState} from './fileStackState';
59import {max, next, prev} from './revMath';
60
61type CommitStackProps = {
62 /**
63 * Original stack exported by `debugexportstack`. Immutable.
64 * Useful to calculate "predecessor" information.
65 */
66 originalStack: Readonly<ExportStack>;
67
68 /**
69 * File contents at the bottom of the stack.
70 *
71 * For example, when editing stack with two commits A and B:
72 *
73 * ```
74 * B <- draft, rev 2
75 * |
76 * A <- draft, modifies foo.txt, rev 1
77 * /
78 * P <- public, does not modify foo.txt, rev 0
79 * ```
80 *
81 * `bottomFiles['foo.txt']` would be the `foo.txt` content in P,
82 * despite P does not change `foo.txt`.
83 *
84 * `bottomFiles` are considered immutable - stack editing operations
85 * won't change `bottomFiles` directly.
86 *
87 * This also assumes there are only one root of the stack.
88 *
89 * This implies that: every file referenced or edited by any commit
90 * in the stack will be present in this map. If a file was added
91 * later in the stack, it is in this map and marked as absent.
92 */
93 bottomFiles: Readonly<Map<RepoPath, FileState>>;
94
95 /**
96 * Mutable commit stack. Indexed by rev.
97 * Only stores "modified (added, edited, deleted)" files.
98 */
99 stack: List<CommitState>;
100
101 /**
102 * File stack states.
103 * They are constructed on demand, and provide advanced features.
104 */
105 fileStacks: List<FileStackState>;
106
107 /**
108 * Map from `CommitIdx` (commitRev and path) to `FileIdx` (FileStack index and rev).
109 * Note the commitRev could be -1, meaning that `bottomFiles` is used.
110 */
111 commitToFile: ImMap<CommitIdx, FileIdx>;
112
113 /**
114 * Reverse (swapped key and value) mapping of `commitToFile` mapping.
115 * Note the commitRev could be -1, meaning that `bottomFiles` is used.
116 */
117 fileToCommit: ImMap<FileIdx, CommitIdx>;
118
119 /**
120 * Extra information for absorb.
121 *
122 * The state might also be calculated from the linelog file stacks
123 * (by editing the linelogs, and calculating diffs). It's also tracked here
124 * for ease-of-access.
125 */
126 absorbExtra: AbsorbExtra;
127};
128
129// Factory function for creating instances.
130// Its type is the factory function (or the "class type" in OOP sense).
131const CommitStackRecord = Record<CommitStackProps>({
132 originalStack: [],
133 bottomFiles: new Map(),
134 stack: List(),
135 fileStacks: List(),
136 commitToFile: ImMap(),
137 fileToCommit: ImMap(),
138 absorbExtra: ImMap(),
139});
140
141/**
142 * For absorb use-case, each file stack (keyed by the index of fileStacks) has
143 * an AbsorbEditId->AbsorbEdit mapping.
144 */
145type AbsorbExtra = ImMap<FileStackIndex, ImMap<AbsorbEditId, AbsorbEdit>>;
146
147// Type of *instances* created by the `CommitStackRecord`.
148// This makes `CommitStackState` work more like a common OOP `class Foo`:
149// `new Foo(...)` is a constructor, and `Foo` is the type of the instances,
150// not the constructor or factory.
151type CommitStackRecord = RecordOf<CommitStackProps>;
152
153/**
154 * A stack of commits with stack editing features.
155 *
156 * Provides read write APIs for editing the stack.
157 * Under the hood, continuous changes to a same file are grouped
158 * to file stacks. Part of analysis and edit operations are delegated
159 * to corresponding file stacks.
160 */
161export class CommitStackState extends SelfUpdate<CommitStackRecord> {
162 // Initial setup.
163
164 /**
165 * Construct from an exported stack. For efficient operations,
166 * call `.buildFileStacks()` to build up states.
167 *
168 * `record` initialization is for internal use only.
169 */
170 constructor(originalStack?: Readonly<ExportStack>, record?: CommitStackRecord) {
171 super(
172 originalStack !== undefined
173 ? CommitStackRecord({
174 originalStack,
175 bottomFiles: getBottomFilesFromExportStack(originalStack),
176 stack: getCommitStatesFromExportStack(originalStack),
177 })
178 : record !== undefined
179 ? record
180 : CommitStackRecord(),
181 );
182 }
183
184 // Delegates to SelfUpdate.inner
185
186 get originalStack(): Readonly<ExportStack> {
187 return this.inner.originalStack;
188 }
189
190 get bottomFiles(): Readonly<Map<RepoPath, FileState>> {
191 return this.inner.bottomFiles;
192 }
193
194 get stack(): List<CommitState> {
195 return this.inner.stack;
196 }
197
198 get fileStacks(): List<FileStackState> {
199 return this.inner.fileStacks;
200 }
201
202 get commitToFile(): ImMap<CommitIdx, FileIdx> {
203 return this.inner.commitToFile;
204 }
205
206 get fileToCommit(): ImMap<FileIdx, CommitIdx> {
207 return this.inner.fileToCommit;
208 }
209
210 get absorbExtra(): AbsorbExtra {
211 return this.inner.absorbExtra;
212 }
213
214 merge(props: Partial<CommitStackProps>): CommitStackState {
215 return new CommitStackState(undefined, this.inner.merge(props));
216 }
217
218 set<K extends keyof CommitStackProps>(key: K, value: CommitStackProps[K]): CommitStackState {
219 return new CommitStackState(undefined, this.inner.set(key, value));
220 }
221
222 // Read operations.
223
224 /** Returns all valid revs. */
225 revs(): CommitRev[] {
226 return [...this.stack.keys()] as CommitRev[];
227 }
228
229 /** Find the first "Rev" that satisfy the condition. */
230 findRev(predicate: (commit: CommitState, rev: CommitRev) => boolean): CommitRev | undefined {
231 return this.stack.findIndex(predicate as (commit: CommitState, rev: number) => boolean) as
232 | CommitRev
233 | undefined;
234 }
235
236 /** Find the last "Rev" that satisfy the condition. */
237 findLastRev(predicate: (commit: CommitState, rev: CommitRev) => boolean): CommitRev | undefined {
238 return this.stack.findLastIndex(predicate as (commit: CommitState, rev: number) => boolean) as
239 | CommitRev
240 | undefined;
241 }
242
243 /**
244 * Return mutable revs.
245 * This filters out public or commits outside the original stack export request.
246 */
247 mutableRevs(): CommitRev[] {
248 return [...this.stack.filter(c => c.immutableKind !== 'hash').map(c => c.rev)];
249 }
250
251 /**
252 * Get the file at the given `rev`.
253 *
254 * Returns `ABSENT_FILE` if the file does not exist in the commit.
255 * Throws if the stack does not have information about the path.
256 *
257 * Note this is different from `this.stack[rev].files.get(path)`,
258 * since `files` only tracks modified files, not existing files
259 * created from the bottom of the stack.
260 *
261 * If `rev` is `-1`, check `bottomFiles`.
262 */
263 getFile(rev: CommitRev, path: RepoPath): FileState {
264 if (rev > -1) {
265 for (const logRev of this.log(rev)) {
266 const commit = this.stack.get(logRev);
267 if (commit == null) {
268 return ABSENT_FILE;
269 }
270 const file = commit.files.get(path);
271 if (file !== undefined) {
272 // Commit modified `file`.
273 return file;
274 }
275 }
276 }
277 const file = this.bottomFiles.get(path) ?? ABSENT_FILE;
278 if (file === undefined) {
279 throw new Error(
280 `file ${path} is not tracked by stack (tracked files: ${JSON.stringify(
281 this.getAllPaths(),
282 )})`,
283 );
284 }
285 return file;
286 }
287
288 /**
289 * Update a single file without affecting the rest of the stack.
290 * Use `getFile` to get the `FileState`.
291 *
292 * Does some normalization:
293 * - If a file is non-empty, then "absent" flag will be ignored.
294 * - If a file is absent, then "copyFrom" and other flags will be ignored.
295 * - If the "copyFrom" file does not exist in parent, it'll be ignored.
296 * - If a file is not newly added, "copyFrom" will be ignored.
297 *
298 * `rev` cannot be `-1`. `bottomFiles` cannot be modified.
299 */
300 setFile(rev: CommitRev, path: RepoPath, editFile: (f: FileState) => FileState): CommitStackState {
301 if (rev < 0) {
302 throw new Error(`invalid rev for setFile: ${rev}`);
303 }
304 const origFile = this.getFile(rev, path);
305 const newFile = editFile(origFile);
306 let file = newFile;
307 // Remove 'absent' for non-empty files.
308 if (isAbsent(file) && this.getUtf8Data(file) !== '') {
309 const newFlags: FileFlag = file.flags === ABSENT_FLAG ? '' : (file.flags ?? '');
310 file = file.set('flags', newFlags);
311 }
312 // Remove other flags for absent files.
313 if (isAbsent(file) && file.flags !== ABSENT_FLAG) {
314 file = file.set('flags', ABSENT_FLAG);
315 }
316 // Check "copyFrom".
317 const copyFrom = file.copyFrom;
318 if (copyFrom != null) {
319 const p1 = this.singleParentRev(rev) ?? (-1 as CommitRev);
320 if (!isAbsent(this.getFile(p1, path))) {
321 file = file.remove('copyFrom');
322 } else {
323 const copyFromFile = this.getFile(p1, copyFrom);
324 if (isAbsent(copyFromFile)) {
325 file = file.remove('copyFrom');
326 }
327 }
328 }
329 let newStack: CommitStackState = this.set(
330 'stack',
331 this.stack.setIn([rev, 'files', path], file),
332 );
333 // Adjust "copyFrom" of child commits.
334 // If this file is deleted, then child commits cannot copy from it.
335 if (isAbsent(file) && !isAbsent(origFile)) {
336 newStack.childRevs(rev).forEach(childRev => {
337 newStack = newStack.dropCopyFromIf(childRev, (_p, f) => f.copyFrom === path);
338 });
339 }
340 // If this file is added, then the same path in the child commits cannot use copyFrom.
341 if (!isAbsent(file) && isAbsent(origFile)) {
342 newStack.childRevs(rev).forEach(childRev => {
343 newStack = newStack.dropCopyFromIf(childRev, (p, _f) => p === path);
344 });
345 }
346 return newStack;
347 }
348
349 dropCopyFromIf(
350 rev: CommitRev,
351 predicate: (path: RepoPath, file: FileState) => boolean,
352 ): CommitStackState {
353 const commit = this.stack.get(rev);
354 if (commit == null) {
355 return this;
356 }
357 const newFiles = commit.files.mapEntries(([path, file]) => {
358 const newFile = predicate(path, file) ? file.remove('copyFrom') : file;
359 return [path, newFile];
360 });
361 const newStack = this.stack.setIn([rev, 'files'], newFiles);
362 return this.set('stack', newStack);
363 }
364
365 childRevs(rev: CommitRev): Array<CommitRev> {
366 const result = [];
367 for (let i = rev + 1; i < this.stack.size; ++i) {
368 if (this.stack.get(i)?.parents?.contains(rev)) {
369 result.push(i as CommitRev);
370 }
371 }
372 return result;
373 }
374
375 /**
376 * Get a list of paths changed by a commit.
377 *
378 * If `text` is set to `true`, only return text (content editable) paths.
379 * If `text` is set to `false`, only return non-text (not content editable) paths.
380 */
381 getPaths(rev: CommitRev, props?: {text?: boolean}): RepoPath[] {
382 const commit = this.stack.get(rev);
383 if (commit == null) {
384 return [];
385 }
386 const text = props?.text;
387 const result = [];
388 for (const [path, file] of commit.files) {
389 if (text != null && isUtf8(file) !== text) {
390 continue;
391 }
392 result.push(path);
393 }
394 return result.sort();
395 }
396
397 /** Get all file paths ever referred (via "copy from") or changed in the stack. */
398 getAllPaths(): RepoPath[] {
399 return [...this.bottomFiles.keys()].sort();
400 }
401
402 /** List revs, starting from the given rev. */
403 *log(startRev: CommitRev): Generator<CommitRev, void> {
404 const toVisit = [startRev];
405 while (true) {
406 const rev = toVisit.pop();
407 if (rev === undefined || rev < 0) {
408 break;
409 }
410 yield rev;
411 const commit = this.stack.get(rev);
412 if (commit != null) {
413 // Visit parent commits.
414 commit.parents.forEach(parentRev => {
415 assert(parentRev < rev, 'parent rev must < child to prevent infinite loop in log()');
416 toVisit.push(parentRev);
417 });
418 }
419 }
420 }
421
422 /**
423 * List revs that change the given file, starting from the given rev.
424 * Optionally follow renames.
425 * Optionally return bottom (rev -1) file.
426 */
427 *logFile(
428 startRev: CommitRev,
429 startPath: RepoPath,
430 followRenames = false,
431 includeBottom = false,
432 ): Generator<[CommitRev, RepoPath, FileState], void> {
433 let path = startPath;
434 let lastFile = undefined;
435 let lastPath = path;
436 for (const rev of this.log(startRev)) {
437 const commit = this.stack.get(rev);
438 if (commit == null) {
439 continue;
440 }
441 const file = commit.files.get(path);
442 if (file !== undefined) {
443 yield [rev, path, file];
444 lastFile = file;
445 lastPath = path;
446 }
447 if (followRenames && file?.copyFrom) {
448 path = file.copyFrom;
449 }
450 }
451 if (includeBottom && lastFile != null) {
452 const bottomFile = this.bottomFiles.get(path);
453 if (bottomFile != null && (path !== lastPath || !bottomFile.equals(lastFile))) {
454 yield [-1 as CommitRev, path, bottomFile];
455 }
456 }
457 }
458
459 // "Save changes" related.
460
461 /**
462 * Produce a `ImportStack` useful for the `debugimportstack` command
463 * to save changes.
464 *
465 * Note this function only returns parts that are changed. If nothing is
466 * changed, this function might return an empty array.
467 *
468 * Options:
469 * - goto: specify a rev or (old commit) to goto. The rev must be changed
470 * otherwise this parameter is ignored.
471 * - preserveDirtyFiles: if true, do not change files in the working copy.
472 * Under the hood, this changes the "goto" to "reset".
473 * - rewriteDate: if set, the unix timestamp (in seconds) for newly
474 * created commits.
475 * - skipWdir: if set, skip changes for the wdir() virtual commit.
476 * This is desirable for operations like absorb, or "amend --to",
477 * where the working copy is expected to stay unchanged regardless
478 * of the current partial/chunk selection.
479 *
480 * Example use-cases:
481 * - Editing a stack (clean working copy): goto = origCurrentHash
482 * - commit -i: create new rev, goto = maxRev, preserveDirtyFiles = true
483 * - amend -i, absorb: goto = origCurrentHash, preserveDirtyFiles = true
484 */
485 calculateImportStack(opts?: {
486 goto?: CommitRev | Hash;
487 preserveDirtyFiles?: boolean;
488 rewriteDate?: number;
489 skipWdir?: boolean;
490 }): ImportStack {
491 // Resolve goto to a Rev.
492 // Special case: if it's at the old stack top, use the new stack top instead.
493 const gotoRev: CommitRev | undefined =
494 typeof opts?.goto === 'string'
495 ? this.originalStack.at(-1)?.node == opts.goto
496 ? this.stack.last()?.rev
497 : this.findLastRev(c => c.originalNodes.has(opts.goto as string))
498 : opts?.goto;
499
500 // Figure out the first changed rev.
501 const state = this.useFileContent();
502 const originalState = new CommitStackState(state.originalStack);
503 const firstChangedRev = state.stack.findIndex((commit, i) => {
504 const originalCommit = originalState.stack.get(i);
505 return originalCommit == null || !is(commit, originalCommit);
506 });
507
508 // Figure out what commits are changed.
509 let changedCommits: CommitState[] =
510 firstChangedRev < 0 ? [] : state.stack.slice(firstChangedRev).toArray();
511 if (opts?.skipWdir) {
512 changedCommits = changedCommits.filter(c => !c.originalNodes.contains(WDIR_NODE));
513 }
514 const changedRevs: Set<CommitRev> = new Set(changedCommits.map(c => c.rev));
515 const revToMark = (rev: CommitRev): Mark => `:r${rev}`;
516 const revToMarkOrHash = (rev: CommitRev): Mark | Hash => {
517 if (changedRevs.has(rev)) {
518 return revToMark(rev);
519 } else {
520 const nodes = nullthrows(state.stack.get(rev)).originalNodes;
521 assert(nodes.size === 1, 'unchanged commits should have exactly 1 nodes');
522 return nullthrows(nodes.first());
523 }
524 };
525
526 // "commit" new commits based on state.stack.
527 const actions: ImportAction[] = changedCommits.map(commit => {
528 assert(commit.immutableKind !== 'hash', 'immutable commits should not be changed');
529 const newFiles: {[path: RepoPath]: ExportFile | null} = Object.fromEntries(
530 [...commit.files.entries()].map(([path, file]) => {
531 if (isAbsent(file)) {
532 return [path, null];
533 }
534 const newFile: ExportFile = {};
535 if (typeof file.data === 'string') {
536 newFile.data = file.data;
537 } else if (file.data instanceof Base85) {
538 newFile.dataBase85 = file.data.dataBase85;
539 } else if (file.data instanceof DataRef) {
540 newFile.dataRef = file.data.toJS();
541 }
542 if (file.copyFrom != null) {
543 newFile.copyFrom = file.copyFrom;
544 }
545 if (file.flags != null) {
546 newFile.flags = file.flags;
547 }
548 return [path, newFile];
549 }),
550 );
551 // Ensure the text is not empty with a filler title.
552 const text =
553 commit.text.trim().length === 0 ||
554 // if a commit template is used, but the title is not given, then we may have non-title text.
555 // sl would trim the leading whitespace, which can end up using the commit template as the commit title.
556 // Instead, use the same filler title.
557 commit.text[0] === '\n'
558 ? t('(no title provided)') + commit.text
559 : commit.text;
560 const importCommit: ImportCommit = {
561 mark: revToMark(commit.rev),
562 author: commit.author,
563 date: [opts?.rewriteDate ?? commit.date.unix, commit.date.tz],
564 text,
565 parents: commit.parents.toArray().map(revToMarkOrHash),
566 predecessors: commit.originalNodes.toArray().filter(n => n !== WDIR_NODE),
567 files: newFiles,
568 };
569 return ['commit', importCommit];
570 });
571
572 // "goto" or "reset" as requested.
573 if (gotoRev != null && changedRevs.has(gotoRev)) {
574 if (opts?.preserveDirtyFiles) {
575 actions.push(['reset', {mark: revToMark(gotoRev)}]);
576 } else {
577 actions.push(['goto', {mark: revToMark(gotoRev)}]);
578 }
579 }
580
581 // "hide" commits that disappear from state.originalStack => state.stack.
582 // Only requested mutable commits are considered.
583 const coveredNodes: Set<Hash> = state.stack.reduce((acc, commit) => {
584 commit.originalNodes.forEach((n: Hash): Set<Hash> => acc.add(n));
585 return acc;
586 }, new Set<Hash>());
587 const orphanedNodes: Hash[] = state.originalStack
588 .filter(c => c.requested && !c.immutable && !coveredNodes.has(c.node))
589 .map(c => c.node);
590 if (orphanedNodes.length > 0) {
591 actions.push(['hide', {nodes: orphanedNodes}]);
592 }
593
594 return actions;
595 }
596
597 // File stack related.
598
599 /**
600 * Get the parent version of a file and its introducing rev.
601 * If the returned `rev` is -1, it means the file comes from
602 * "bottomFiles", aka. its introducing rev is outside the stack.
603 */
604 parentFile(
605 rev: CommitRev,
606 path: RepoPath,
607 followRenames = true,
608 ): [CommitRev, RepoPath, FileState] {
609 let prevRev = -1 as CommitRev;
610 let prevPath = path;
611 let prevFile = nullthrows(this.bottomFiles.get(path));
612 const includeBottom = true;
613 const logFile = this.logFile(rev, path, followRenames, includeBottom);
614 for (const [logRev, logPath, file] of logFile) {
615 if (logRev !== rev) {
616 [prevRev, prevPath] = [logRev, logPath];
617 prevFile = file;
618 break;
619 }
620 }
621 return [prevRev, prevPath, prevFile];
622 }
623
624 /** Assert that the revs are in the right order. */
625 assertRevOrder() {
626 assert(
627 this.stack.every(c => c.parents.every(p => p < c.rev)),
628 'parent rev should < child rev',
629 );
630 assert(
631 this.stack.every((c, i) => c.rev === i),
632 'rev should equal to stack index',
633 );
634 }
635
636 // Absorb related {{{
637
638 /** Check if there is a pending absorb in this stack */
639 hasPendingAbsorb(): boolean {
640 return !this.inner.absorbExtra.isEmpty();
641 }
642
643 /**
644 * Prepare for absorb use-case. Break down "wdir()" edits into the stack
645 * with special revs so they can be later moved around.
646 * See `calculateAbsorbEditsForFileStack` for details.
647 *
648 * This function assumes the stack top is "wdir()" to absorb, and the stack
649 * bottom is immutable (public()).
650 */
651 analyseAbsorb(): CommitStackState {
652 const stack = this.useFileStack();
653 const wdirCommitRev = stack.stack.size - 1;
654 assert(wdirCommitRev > 0, 'stack cannot be empty');
655 let newFileStacks = stack.fileStacks;
656 let absorbExtra: AbsorbExtra = ImMap();
657 stack.fileStacks.forEach((fileStack, fileIdx) => {
658 const topFileRev = prev(fileStack.revLength);
659 if (topFileRev < 0) {
660 // Empty file stack. Skip.
661 return;
662 }
663 const rev = stack.fileToCommit.get(FileIdx({fileIdx, fileRev: topFileRev}))?.rev;
664 if (rev != wdirCommitRev) {
665 // wdir() did not change this file. Skip.
666 return;
667 }
668 const [newFileStack, absorbMap] = calculateAbsorbEditsForFileStack(fileStack, {
669 fileStackIndex: fileIdx,
670 });
671 absorbExtra = absorbExtra.set(fileIdx, absorbMap);
672 newFileStacks = newFileStacks.set(fileIdx, newFileStack);
673 });
674 const newStackInner = stack.inner.set('fileStacks', newFileStacks);
675 const newStack = new CommitStackState(undefined, newStackInner).set('absorbExtra', absorbExtra);
676 return newStack;
677 }
678
679 /**
680 * For an absorb edit, defined by `fileIdx`, and `absorbEditId`, return the
681 * currently selected and possible "absorb into" commit revs.
682 *
683 * The edit can be looked up from the `absorbExtra` state.
684 */
685 getAbsorbCommitRevs(
686 fileIdx: number,
687 absorbEditId: AbsorbEditId,
688 ): {candidateRevs: ReadonlyArray<CommitRev>; selectedRev?: CommitRev} {
689 const fileStack = nullthrows(this.fileStacks.get(fileIdx));
690 const edit = nullthrows(this.absorbExtra.get(fileIdx)?.get(absorbEditId));
691 const toCommitRev = (fileRev: FileRev | null | undefined): CommitRev | undefined => {
692 if (fileRev == null) {
693 return undefined;
694 }
695 return this.fileToCommit.get(FileIdx({fileIdx, fileRev}))?.rev;
696 };
697 // diffChunk uses fileRev, map it to commitRev.
698 const selectedRev = toCommitRev(edit.selectedRev);
699 const startCandidateFileRev = Math.max(1, edit.introductionRev); // skip file rev 0 (bottomFiles)
700 const endCandidateFileRev = fileStack.revLength;
701 const candidateRevs: CommitRev[] = [];
702 for (let fileRev = startCandidateFileRev; fileRev <= endCandidateFileRev; ++fileRev) {
703 const rev = toCommitRev(fileRev as FileRev);
704 // Skip immutable (public) commits.
705 if (rev != null && this.get(rev)?.immutableKind !== 'hash') {
706 candidateRevs.push(rev);
707 }
708 }
709 return {selectedRev, candidateRevs};
710 }
711
712 /**
713 * Filter `absorbExtra` by commit rev.
714 *
715 * Only returns a subset of `absorbExtra` that has the `rev` selected.
716 */
717 absorbExtraByCommitRev(rev: CommitRev): AbsorbExtra {
718 const commit = this.get(rev);
719 const isWdir = commit?.originalNodes.contains(WDIR_NODE);
720 return ImMap<FileStackIndex, ImMap<AbsorbEditId, AbsorbEdit>>().withMutations(mut => {
721 let result = mut;
722 this.absorbExtra.forEach((edits, fileStackIndex) => {
723 edits.forEach((edit, editId) => {
724 assert(edit.absorbEditId === editId, 'absorbEditId should match its map key');
725 const fileRev = edit.selectedRev;
726 const fileIdx = edit.fileStackIndex;
727 const selectedCommitRev =
728 fileRev != null &&
729 fileIdx != null &&
730 this.fileToCommit.get(FileIdx({fileIdx, fileRev}))?.rev;
731 if (selectedCommitRev === rev || (edit.selectedRev == null && isWdir)) {
732 if (!result.has(fileStackIndex)) {
733 result = result.set(fileStackIndex, ImMap<AbsorbEditId, AbsorbEdit>());
734 }
735 result = result.setIn([fileStackIndex, editId], edit);
736 }
737 });
738 });
739 return result;
740 });
741 }
742
743 /**
744 * Calculates the "candidateRevs" for all absorb edits.
745 *
746 * For example, in a 26-commit stack A..Z, only C and K changes a.txt, E and J
747 * changes b.txt. When the user wants to absorb changes from a.txt and b.txt,
748 * we only show 4 relevant commits: C, E, J, K.
749 *
750 * This function does not report public commits.
751 */
752 getAllAbsorbCandidateCommitRevs(): Set<CommitRev> {
753 const result = new Set<CommitRev>();
754 this.absorbExtra.forEach((edits, fileIdx) => {
755 edits.forEach((_edit, absorbEditId) => {
756 this.getAbsorbCommitRevs(fileIdx, absorbEditId)?.candidateRevs.forEach(rev => {
757 if (this.get(rev)?.immutableKind !== 'hash') {
758 result.add(rev);
759 }
760 });
761 });
762 });
763 return result;
764 }
765
766 /**
767 * Set `rev` as the "target commit" (amend --to) of an "absorb edit".
768 * Happens when the user moves the absorb edit among candidate commits.
769 *
770 * Throws if the edit cannot be fulfilled, for example, the `commitRev` is
771 * before the commit introducing the change (conflict), or if the `commitRev`
772 * does not touch the file being edited (current limitation, might be lifted).
773 */
774 setAbsorbEditDestination(
775 fileIdx: number,
776 absorbEditId: AbsorbEditId,
777 commitRev: CommitRev,
778 ): CommitStackState {
779 assert(this.hasPendingAbsorb(), 'stack is not prepared for absorb');
780 const fileStack = nullthrows(this.fileStacks.get(fileIdx));
781 const edit = nullthrows(this.absorbExtra.get(fileIdx)?.get(absorbEditId));
782 const selectedFileRev = edit.selectedRev;
783 if (selectedFileRev != null) {
784 const currentCommitRev = this.fileToCommit.get(
785 FileIdx({fileIdx, fileRev: selectedFileRev}),
786 )?.rev;
787 if (currentCommitRev === commitRev) {
788 // No need to edit.
789 return this;
790 }
791 }
792 // Figure out the "file rev" from "commit rev", since we don't know the
793 // "path" of the file at the "commitRev", for now, we just naively looks up
794 // the fileRev one by one... for now
795 for (let fileRev = max(edit.introductionRev, 1); ; fileRev = next(fileRev)) {
796 const candidateCommitRev = this.fileToCommit.get(FileIdx({fileIdx, fileRev}))?.rev;
797 if (candidateCommitRev == null) {
798 break;
799 }
800 if (candidateCommitRev === commitRev) {
801 // Update linelog to move the edit to "fileRev".
802 const newFileRev = embedAbsorbId(fileRev, absorbEditId);
803 const newFileStack = fileStack.remapRevs(rev =>
804 !Number.isInteger(rev) && extractRevAbsorbId(rev)[1] === absorbEditId ? newFileRev : rev,
805 );
806 // Update the absorb extra too.
807 const newEdit = edit.set('selectedRev', fileRev);
808 const newAbsorbExtra = this.absorbExtra.setIn([fileIdx, absorbEditId], newEdit);
809 // It's possible that "wdir()" is all absorbed, the new stack is
810 // shorter than the original stack. So we bypass the length check.
811 const newStack = this.setFileStackInternal(fileIdx, newFileStack).set(
812 'absorbExtra',
813 newAbsorbExtra,
814 );
815 return newStack;
816 }
817 }
818 throw new Error('setAbsorbIntoRev did not find corresponding commit to absorb');
819 }
820
821 /**
822 * Apply pending absorb edits.
823 *
824 * After this, absorb edits can no longer be edited by `setAbsorbEditDestination`,
825 * `hasPendingAbsorb()` returns `false`, and `calculateImportStack()` can be used.
826 */
827 applyAbsorbEdits(): CommitStackState {
828 if (!this.hasPendingAbsorb()) {
829 return this;
830 }
831 return this.useFileContent().set('absorbExtra', ImMap());
832 }
833
834 // }}} (absorb related)
835
836 /**
837 * (Re-)build file stacks and mappings.
838 *
839 * If `followRenames` is true, then attempt to follow renames
840 * when building linelogs (default: true).
841 */
842 buildFileStacks(opts?: BuildFileStackOptions): CommitStackState {
843 const fileStacks: FileStackState[] = [];
844 let commitToFile = ImMap<CommitIdx, FileIdx>();
845 let fileToCommit = ImMap<FileIdx, CommitIdx>();
846
847 const followRenames = opts?.followRenames ?? true;
848
849 this.assertRevOrder();
850
851 const processFile = (
852 state: CommitStackState,
853 rev: CommitRev,
854 file: FileState,
855 path: RepoPath,
856 ) => {
857 const [prevRev, prevPath, prevFile] = state.parentFile(rev, path, followRenames);
858 if (isUtf8(file)) {
859 // File was added or modified and has utf-8 content.
860 let fileAppended = false;
861 if (prevRev >= 0) {
862 // Try to reuse an existing file stack.
863 const prev = commitToFile.get(CommitIdx({rev: prevRev, path: prevPath}));
864 if (prev) {
865 const prevFileStack = fileStacks[prev.fileIdx];
866 // File stack history is linear. Only reuse it if its last
867 // rev matches `prevFileRev`
868 if (prevFileStack.source.revLength === prev.fileRev + 1) {
869 const fileRev = next(prev.fileRev);
870 fileStacks[prev.fileIdx] = prevFileStack.editText(
871 fileRev,
872 state.getUtf8Data(file),
873 false,
874 );
875 const cIdx = CommitIdx({rev, path});
876 const fIdx = FileIdx({fileIdx: prev.fileIdx, fileRev});
877 commitToFile = commitToFile.set(cIdx, fIdx);
878 fileToCommit = fileToCommit.set(fIdx, cIdx);
879 fileAppended = true;
880 }
881 }
882 }
883 if (!fileAppended) {
884 // Cannot reuse an existing file stack. Create a new file stack.
885 const fileIdx = fileStacks.length;
886 let fileTextList = [state.getUtf8Data(file)];
887 let fileRev = 0 as FileRev;
888 if (isUtf8(prevFile)) {
889 // Use "prevFile" as rev 0 (immutable public).
890 fileTextList = [state.getUtf8Data(prevFile), ...fileTextList];
891 const cIdx = CommitIdx({rev: prevRev, path: prevPath});
892 const fIdx = FileIdx({fileIdx, fileRev});
893 commitToFile = commitToFile.set(cIdx, fIdx);
894 fileToCommit = fileToCommit.set(fIdx, cIdx);
895 fileRev = 1 as FileRev;
896 }
897 const fileStack = new FileStackState(fileTextList);
898 fileStacks.push(fileStack);
899 const cIdx = CommitIdx({rev, path});
900 const fIdx = FileIdx({fileIdx, fileRev});
901 commitToFile = commitToFile.set(cIdx, fIdx);
902 fileToCommit = fileToCommit.set(fIdx, cIdx);
903 }
904 }
905 };
906
907 // Migrate off 'fileStack' type, since we are going to replace the file stacks.
908 const state = this.useFileContent();
909
910 state.stack.forEach((commit, revNumber) => {
911 const rev = revNumber as CommitRev;
912 const files = commit.files;
913 // Process order: renames, non-copy, copies.
914 const priorityFiles: [number, RepoPath, FileState][] = [...files.entries()].map(
915 ([path, file]) => {
916 const priority =
917 followRenames && isRename(commit, path) ? 0 : file.copyFrom == null ? 1 : 2;
918 return [priority, path, file];
919 },
920 );
921 const renamed = new Set<RepoPath>();
922 priorityFiles
923 .sort(([aPri, aPath, _aFile], [bPri, bPath, _bFile]) =>
924 aPri < bPri || (aPri === bPri && aPath < bPath) ? -1 : 1,
925 )
926 .forEach(([priority, path, file]) => {
927 // Skip already "renamed" absent files.
928 let skip = false;
929 if (priority === 0 && file.copyFrom != null) {
930 renamed.add(file.copyFrom);
931 } else {
932 skip = isAbsent(file) && renamed.has(path);
933 }
934 if (!skip) {
935 processFile(state, rev, file, path);
936 }
937 });
938 });
939
940 return state.merge({
941 fileStacks: List(fileStacks),
942 commitToFile,
943 fileToCommit,
944 });
945 }
946
947 /**
948 * Build file stacks if it's not present.
949 * This is part of the `useFileStack` implementation detail.
950 * It does not ensure the file stack references are actually used for `getFile`.
951 * For public API, use `useFileStack` instead.
952 */
953 private maybeBuildFileStacks(opts?: BuildFileStackOptions): CommitStackState {
954 return this.fileStacks.size === 0 ? this.buildFileStacks(opts) : this;
955 }
956
957 /**
958 * Switch file contents to use FileStack as source of truth.
959 * Useful when using FileStack to edit files.
960 */
961 useFileStack(): CommitStackState {
962 const state = this.maybeBuildFileStacks();
963 return state.updateEachFile((rev, file, path) => {
964 if (typeof file.data === 'string') {
965 const index = state.commitToFile.get(CommitIdx({rev, path}));
966 if (index != null) {
967 return file.set('data', index);
968 }
969 }
970 return file;
971 });
972 }
973
974 /**
975 * Switch file contents to use string as source of truth.
976 * Useful when rebuilding FileStack.
977 */
978 useFileContent(): CommitStackState {
979 return this.updateEachFile((_rev, file) => {
980 if (typeof file.data !== 'string' && isUtf8(file)) {
981 const data = this.getUtf8Data(file);
982 return file.set('data', data);
983 }
984 return file;
985 }).merge({
986 fileStacks: List(),
987 commitToFile: ImMap(),
988 fileToCommit: ImMap(),
989 });
990 }
991
992 /**
993 * Iterate through all changed files via the given function.
994 */
995 updateEachFile(
996 func: (commitRev: CommitRev, file: FileState, path: RepoPath) => FileState,
997 ): CommitStackState {
998 const newStack = this.stack.map(commit => {
999 const newFiles = commit.files.map((file, path) => {
1000 return func(commit.rev, file, path);
1001 });
1002 return commit.set('files', newFiles);
1003 });
1004 return this.set('stack', newStack);
1005 }
1006
1007 /**
1008 * Describe all file stacks for testing purpose.
1009 * Each returned string represents a file stack.
1010 *
1011 * Output in `rev:commit/path(content)` format.
1012 * If `(content)` is left out it means the file at the rev is absent.
1013 * If `commit` is `.` then it comes from `bottomFiles` meaning that
1014 * the commit last modifies the path might be outside the stack.
1015 *
1016 * Rev 0 is usually the "public" version that is not editable.
1017 *
1018 * For example, `0:./x.txt 1:A/x.txt(33) 2:B/y.txt(33)` means:
1019 * commit A added `x.txt` with the content `33`, and commit B renamed it to
1020 * `y.txt`.
1021 *
1022 * `0:./z.txt(11) 1:A/z.txt(22) 2:C/z.txt` means: `z.txt` existed at
1023 * the bottom of the stack with the content `11`. Commit A modified
1024 * its content to `22` and commit C deleted `z.txt`.
1025 */
1026 describeFileStacks(showContent = true): string[] {
1027 const state = this.useFileStack();
1028 const fileToCommit = state.fileToCommit;
1029 const stack = state.stack;
1030 const hasAbsorb = state.hasPendingAbsorb();
1031 return state.fileStacks
1032 .map((fileStack, fileIdx) => {
1033 return fileStack
1034 .revs()
1035 .map(fileRev => {
1036 const value = fileToCommit.get(FileIdx({fileIdx, fileRev}));
1037 const spans = [`${fileRev}:`];
1038 assert(
1039 value != null,
1040 `fileToCommit should have all file stack revs (missing: fileIdx=${fileIdx} fileRev=${fileRev})`,
1041 );
1042 const {rev, path} = value;
1043 const [commitTitle, absent] =
1044 rev < 0
1045 ? ['.', isAbsent(state.bottomFiles.get(path))]
1046 : ((c: CommitState): [string, boolean] => [
1047 c.text.split('\n').at(0) || [...c.originalNodes].at(0) || '?',
1048 isAbsent(c.files.get(path)),
1049 ])(nullthrows(stack.get(rev)));
1050 spans.push(`${commitTitle}/${path}`);
1051 if (showContent && !absent) {
1052 let content = fileStack.getRev(fileRev).replaceAll('\n', '↵');
1053 if (hasAbsorb) {
1054 const absorbedContent = fileStack
1055 .getRev(revWithAbsorb(fileRev))
1056 .replaceAll('\n', '↵');
1057 if (absorbedContent !== content) {
1058 content += `;absorbed:${absorbedContent}`;
1059 }
1060 }
1061 spans.push(`(${content})`);
1062 }
1063 return spans.join('');
1064 })
1065 .join(' ');
1066 })
1067 .toArray();
1068 }
1069
1070 /** File name for `fileStacks[index]`. If the file is renamed, return */
1071 getFileStackDescription(fileIdx: number): string {
1072 const fileStack = nullthrows(this.fileStacks.get(fileIdx));
1073 const revLength = prev(fileStack.revLength);
1074 const nameAtFirstRev = this.getFileStackPath(fileIdx, 0 as FileRev);
1075 const nameAtLastRev = this.getFileStackPath(fileIdx, prev(revLength));
1076 const words = [];
1077 if (nameAtFirstRev) {
1078 words.push(nameAtFirstRev);
1079 }
1080 if (nameAtLastRev && nameAtLastRev !== nameAtFirstRev) {
1081 // U+2192. Rightwards Arrow (Unicode 1.1).
1082 words.push('→');
1083 words.push(nameAtLastRev);
1084 }
1085 if (revLength > 1) {
1086 words.push(t('(edited by $n commits)', {replace: {$n: revLength.toString()}}));
1087 }
1088 return words.join(' ');
1089 }
1090
1091 /** Get the path name for a specific revision in the given file stack. */
1092 getFileStackPath(fileIdx: number, fileRev: FileRev): string | undefined {
1093 return this.fileToCommit.get(FileIdx({fileIdx, fileRev}))?.path;
1094 }
1095
1096 /**
1097 * Get the commit from a file stack revision.
1098 * Returns undefined when rev is out of range, or the commit is "public" (ex. fileRev is 0).
1099 */
1100 getCommitFromFileStackRev(fileIdx: number, fileRev: FileRev): CommitState | undefined {
1101 const commitRev = this.fileToCommit.get(FileIdx({fileIdx, fileRev}))?.rev;
1102 if (commitRev == null || commitRev < 0) {
1103 return undefined;
1104 }
1105 return nullthrows(this.stack.get(commitRev));
1106 }
1107
1108 /**
1109 * Test if a file rev is "absent". An absent file is different from an empty file.
1110 */
1111 isAbsentFromFileStackRev(fileIdx: number, fileRev: FileRev): boolean {
1112 const commitIdx = this.fileToCommit.get(FileIdx({fileIdx, fileRev}));
1113 if (commitIdx == null) {
1114 return true;
1115 }
1116 const {rev, path} = commitIdx;
1117 const file = rev < 0 ? this.bottomFiles.get(path) : this.getFile(rev, path);
1118 return file == null || isAbsent(file);
1119 }
1120
1121 /**
1122 * Extract utf-8 data from a file.
1123 * Pending absorb is applied if considerPendingAbsorb is true.
1124 */
1125 getUtf8Data(file: FileState, considerPendingAbsorb = true): string {
1126 if (typeof file.data === 'string') {
1127 return file.data;
1128 }
1129 if (file.data instanceof FileIdx) {
1130 let fileRev = file.data.fileRev;
1131 if (considerPendingAbsorb && this.hasPendingAbsorb()) {
1132 fileRev = revWithAbsorb(fileRev);
1133 }
1134 return nullthrows(this.fileStacks.get(file.data.fileIdx)).getRev(fileRev);
1135 } else {
1136 throw new Error('getUtf8Data called on non-utf8 file.');
1137 }
1138 }
1139
1140 /** Similar to `getUtf8Data`, but returns `null` if not utf-8 */
1141 getUtf8DataOptional(file: FileState, considerPendingAbsorb = true): string | null {
1142 return isUtf8(file) ? this.getUtf8Data(file, considerPendingAbsorb) : null;
1143 }
1144
1145 /** Test if two files have the same data. */
1146 isEqualFile(a: FileState, b: FileState): boolean {
1147 if ((a.flags ?? '') !== (b.flags ?? '')) {
1148 return false;
1149 }
1150 if (isUtf8(a) && isUtf8(b)) {
1151 return this.getUtf8Data(a) === this.getUtf8Data(b);
1152 }
1153 // We assume base85 data is immutable, non-utf8 so they won't match utf8 data.
1154 if (a.data instanceof Base85 && b.data instanceof Base85) {
1155 return a.data.dataBase85 === b.data.dataBase85;
1156 }
1157 if (a.data instanceof DataRef && b.data instanceof DataRef) {
1158 return is(a.data, b.data);
1159 }
1160 return false;
1161 }
1162
1163 /** Test if the stack is linear. */
1164 isStackLinear(): boolean {
1165 return this.stack.every(
1166 (commit, rev) =>
1167 rev === 0 || (commit.parents.size === 1 && commit.parents.first() === rev - 1),
1168 );
1169 }
1170
1171 /** Find a commit by key. */
1172 findCommitByKey(key: string): CommitState | undefined {
1173 return this.stack.find(c => c.key === key);
1174 }
1175
1176 /** Get a specified commit. */
1177 get(rev: CommitRev): CommitState | undefined {
1178 return this.stack.get(rev);
1179 }
1180
1181 /** Get the stack size. */
1182 get size(): number {
1183 return this.stack.size;
1184 }
1185
1186 // Histedit-related operations.
1187
1188 /**
1189 * Calculate the dependencies of revisions.
1190 * For example, `{5: [3, 1]}` means rev 5 depends on rev 3 and rev 1.
1191 *
1192 * This is used to detect what's reasonable when reordering and dropping
1193 * commits. For example, if rev 3 depends on rev 2, then rev 3 cannot be
1194 * moved to be an ancestor of rev 2, and rev 2 cannot be dropped alone.
1195 */
1196 calculateDepMap = cachedMethod(this.calculateDepMapImpl, {cache: calculateDepMapCache});
1197 private calculateDepMapImpl(): Readonly<Map<CommitRev, Set<CommitRev>>> {
1198 const state = this.useFileStack();
1199 const depMap = new Map<CommitRev, Set<CommitRev>>(state.stack.map(c => [c.rev, new Set()]));
1200
1201 const fileIdxRevToCommitRev = (fileIdx: FileStackIndex, fileRev: FileRev): CommitRev =>
1202 nullthrows(state.fileToCommit.get(FileIdx({fileIdx, fileRev}))).rev;
1203
1204 // Ask FileStack for dependencies about content edits.
1205 state.fileStacks.forEach((fileStack, fileIdx) => {
1206 const fileDepMap = fileStack.calculateDepMap();
1207 const toCommitRev = (rev: FileRev) => fileIdxRevToCommitRev(fileIdx, rev);
1208 // Convert file revs to commit revs.
1209 fileDepMap.forEach((valueFileRevs, keyFileRev) => {
1210 const keyCommitRev = toCommitRev(keyFileRev);
1211 if (keyCommitRev >= 0) {
1212 const set = nullthrows(depMap.get(keyCommitRev));
1213 valueFileRevs.forEach(fileRev => {
1214 const rev = toCommitRev(fileRev);
1215 if (rev >= 0) {
1216 set.add(rev);
1217 }
1218 });
1219 }
1220 });
1221 });
1222
1223 // Besides, file deletion / addition / renames also introduce dependencies.
1224 state.stack.forEach(commit => {
1225 const set = nullthrows(depMap.get(commit.rev));
1226 commit.files.forEach((file, path) => {
1227 const [prevRev, prevPath, prevFile] = state.parentFile(commit.rev, path, true);
1228 if (prevRev >= 0 && (isAbsent(prevFile) !== isAbsent(file) || prevPath !== path)) {
1229 set.add(prevRev);
1230 }
1231 });
1232 });
1233
1234 return depMap;
1235 }
1236
1237 /** Return the single parent rev, or null. */
1238 singleParentRev(rev: CommitRev): CommitRev | null {
1239 const commit = this.stack.get(rev);
1240 const parents = commit?.parents;
1241 if (parents != null) {
1242 const parentRev = parents?.first();
1243 if (parentRev != null && parents.size === 1) {
1244 return parentRev;
1245 }
1246 }
1247 return null;
1248 }
1249
1250 /**
1251 * Test if the commit can be folded with its parent.
1252 */
1253 canFoldDown = cachedMethod(this.canFoldDownImpl, {cache: canFoldDownCache});
1254 private canFoldDownImpl(rev: CommitRev): boolean {
1255 if (rev <= 0) {
1256 return false;
1257 }
1258 const commit = this.stack.get(rev);
1259 if (commit == null) {
1260 return false;
1261 }
1262 const parentRev = this.singleParentRev(rev);
1263 if (parentRev == null) {
1264 return false;
1265 }
1266 const parent = nullthrows(this.stack.get(parentRev));
1267 if (commit.immutableKind !== 'none' || parent.immutableKind !== 'none') {
1268 return false;
1269 }
1270 // This is a bit conservative. But we're not doing complex content check for now.
1271 const childCount = this.stack.count(c => c.parents.includes(parentRev));
1272 if (childCount > 1) {
1273 return false;
1274 }
1275 return true;
1276 }
1277
1278 /**
1279 * Drop the given `rev`.
1280 * The callsite should take care of `files` updates.
1281 */
1282 rewriteStackDroppingRev(rev: CommitRev): CommitStackState {
1283 const revMapFunc = (r: CommitRev) => (r < rev ? r : prev(r));
1284 const newStack = this.stack
1285 .filter(c => c.rev !== rev)
1286 .map(c => rewriteCommitRevs(c, revMapFunc));
1287 // Recalculate file stacks.
1288 return this.set('stack', newStack).buildFileStacks();
1289 }
1290
1291 /**
1292 * Fold the commit with its parent.
1293 * This should only be called when `canFoldDown(rev)` returned `true`.
1294 */
1295 foldDown(rev: CommitRev) {
1296 const commit = nullthrows(this.stack.get(rev));
1297 const parentRev = nullthrows(this.singleParentRev(rev));
1298 const parent = nullthrows(this.stack.get(parentRev));
1299 let newParentFiles = parent.files;
1300 const newFiles = commit.files.map((origFile, path) => {
1301 // Fold copyFrom. `-` means "no change".
1302 //
1303 // | grand | direct | | |
1304 // | parent | parent | rev | folded (copyFrom) |
1305 // +--------------------------------------------+
1306 // | A | A->B | B->C | A->C (parent) |
1307 // | A | A->B | B | A->B (parent) |
1308 // | A | A->B | - | A->B (parent) |
1309 // | A | A | A->C | A->C (rev) |
1310 // | A | - | A->C | A->C (rev) |
1311 // | - | B | B->C | C (drop) |
1312 let file = origFile;
1313 const optionalParentFile = newParentFiles.get(file.copyFrom ?? path);
1314 const copyFrom = optionalParentFile?.copyFrom ?? file.copyFrom;
1315 if (copyFrom != null && isAbsent(this.parentFile(parentRev, file.copyFrom ?? path)[2])) {
1316 // "copyFrom" is no longer valid (not existed in grand parent). Drop it.
1317 file = file.set('copyFrom', undefined);
1318 } else {
1319 file = file.set('copyFrom', copyFrom);
1320 }
1321 if (this.isEqualFile(this.parentFile(parentRev, path, false /* [1] */)[2], file)) {
1322 // The file changes cancel out. Remove it.
1323 // [1]: we need to disable following renames when comparing files for cancel-out check.
1324 newParentFiles = newParentFiles.delete(path);
1325 } else {
1326 // Fold the change of this file.
1327 newParentFiles = newParentFiles.set(path, file);
1328 }
1329 return file;
1330 });
1331
1332 // Fold other properties to parent.
1333 let newParentText = parent.text;
1334 if (isMeaningfulText(commit.text)) {
1335 const schema = readAtom(commitMessageFieldsSchema);
1336 const parentTitle = firstLine(parent.text);
1337 const parentFields = parseCommitMessageFields(
1338 schema,
1339 parentTitle,
1340 parent.text.slice(parentTitle.length),
1341 );
1342 const commitTitle = firstLine(commit.text);
1343 const commitFields = parseCommitMessageFields(
1344 schema,
1345 commitTitle,
1346 commit.text.slice(commitTitle.length),
1347 );
1348 const merged = mergeCommitMessageFields(schema, parentFields, commitFields);
1349 newParentText = commitMessageFieldsToString(schema, merged);
1350 }
1351
1352 const newParent = parent.merge({
1353 text: newParentText,
1354 date: commit.date,
1355 originalNodes: parent.originalNodes.merge(commit.originalNodes),
1356 files: newParentFiles,
1357 });
1358 const newCommit = commit.set('files', newFiles);
1359 const newStack = this.stack.withMutations(mutStack => {
1360 mutStack.set(parentRev, newParent).set(rev, newCommit);
1361 });
1362
1363 return this.set('stack', newStack).rewriteStackDroppingRev(rev);
1364 }
1365
1366 /**
1367 * Test if the commit can be dropped. That is, none of its descendants depend on it.
1368 */
1369 canDrop = cachedMethod(this.canDropImpl, {cache: canDropCache});
1370 private canDropImpl(rev: CommitRev): boolean {
1371 if (rev < 0 || this.stack.get(rev)?.immutableKind !== 'none') {
1372 return false;
1373 }
1374 const depMap = this.calculateDepMap();
1375 for (const [currentRev, dependentRevs] of depMap.entries()) {
1376 if (dependentRevs.has(rev) && generatorContains(this.log(currentRev), rev)) {
1377 return false;
1378 }
1379 }
1380 return true;
1381 }
1382
1383 /**
1384 * Drop a commit. Changes made by the commit will be removed in its
1385 * descendants.
1386 *
1387 * This should only be called when `canDrop(rev)` returned `true`.
1388 */
1389 drop(rev: CommitRev): CommitStackState {
1390 let state = this.useFileStack().inner;
1391 const commit = nullthrows(state.stack.get(rev));
1392 commit.files.forEach((file, path) => {
1393 const fileIdxRev: FileIdx | undefined = state.commitToFile.get(CommitIdx({rev, path}));
1394 if (fileIdxRev != null) {
1395 const {fileIdx, fileRev} = fileIdxRev;
1396 const fileStack = nullthrows(state.fileStacks.get(fileIdx));
1397 // Drop the rev by remapping it to an unused rev.
1398 const unusedFileRev = fileStack.source.revLength;
1399 const newFileStack = fileStack.remapRevs(new Map([[fileRev, unusedFileRev]]));
1400 state = state.setIn(['fileStacks', fileIdx], newFileStack);
1401 }
1402 });
1403
1404 return new CommitStackState(undefined, state).rewriteStackDroppingRev(rev);
1405 }
1406
1407 /**
1408 * Insert an empty commit at `rev`.
1409 * Cannot insert to an empty stack.
1410 */
1411 insertEmpty(rev: CommitRev, message: string, splitFromRev?: CommitRev): CommitStackState {
1412 assert(rev <= this.stack.size && rev >= 0, 'rev out of range');
1413 const state = this.useFileContent();
1414 let newStack;
1415 const newKey = this.nextKey('insert');
1416 const originalNodes = splitFromRev == null ? undefined : state.get(splitFromRev)?.originalNodes;
1417 if (rev === this.stack.size) {
1418 const top = this.stack.last();
1419 assert(top != null, 'stack cannot be empty');
1420 newStack = this.stack.push(
1421 CommitState({
1422 rev,
1423 parents: List(rev === 0 ? [] : [prev(rev)]),
1424 text: message,
1425 key: newKey,
1426 author: top.author,
1427 date: top.date,
1428 originalNodes,
1429 }),
1430 );
1431 } else {
1432 const revMapFunc = (r: CommitRev) => (r >= rev ? next(r) : r);
1433 const origParents = nullthrows(state.stack.get(rev)).parents;
1434 newStack = state.stack
1435 .map(c => rewriteCommitRevs(c, revMapFunc))
1436 .flatMap(c => {
1437 if (c.rev == rev + 1) {
1438 return Seq([
1439 CommitState({
1440 rev,
1441 parents: origParents,
1442 text: message,
1443 key: newKey,
1444 author: c.author,
1445 date: c.date,
1446 originalNodes,
1447 }),
1448 c.set('parents', List([rev])),
1449 ]);
1450 } else {
1451 return Seq([c]);
1452 }
1453 });
1454 }
1455 return this.set('stack', newStack).buildFileStacks();
1456 }
1457
1458 /**
1459 * Update commit message.
1460 */
1461 editCommitMessage(rev: CommitRev, message: string): CommitStackState {
1462 assert(rev <= this.stack.size && rev >= 0, 'rev out of range');
1463 const newStack = this.stack.setIn([rev, 'text'], message);
1464 return this.set('stack', newStack);
1465 }
1466
1467 /**
1468 * Find a unique "key" not yet used by the commit stack.
1469 */
1470 nextKey(prefix: string): string {
1471 const usedKeys = ImSet(this.stack.map(c => c.key));
1472 for (let i = 0; ; i++) {
1473 const key = `${prefix}-${i}`;
1474 if (usedKeys.has(key)) {
1475 continue;
1476 }
1477 return key;
1478 }
1479 }
1480
1481 /**
1482 * Check if reorder is conflict-free.
1483 *
1484 * `order` defines the new order as a "from rev" list.
1485 * For example, when `this.revs()` is `[0, 1, 2, 3]` and `order` is
1486 * `[0, 2, 3, 1]`, it means moving the second (rev 1) commit to the
1487 * stack top.
1488 *
1489 * Reordering in a non-linear stack is not supported and will return
1490 * `false`. This is because it's tricky to describe the desired
1491 * new parent relationships with just `order`.
1492 *
1493 * If `order` is `this.revs()` then no reorder is done.
1494 */
1495 canReorder(order: CommitRev[]): boolean {
1496 const state = this.useFileStack();
1497 if (!state.isStackLinear()) {
1498 return false;
1499 }
1500 if (
1501 !deepEqual(
1502 [...order].sort((a, b) => a - b),
1503 state.revs(),
1504 )
1505 ) {
1506 return false;
1507 }
1508
1509 // "hash" immutable commits cannot be moved.
1510 if (state.stack.some((commit, rev) => commit.immutableKind === 'hash' && order[rev] !== rev)) {
1511 return false;
1512 }
1513
1514 const map = new Map<CommitRev, CommitRev>(
1515 order.map((fromRev, toRev) => [fromRev as CommitRev, toRev as CommitRev]),
1516 );
1517 // Check dependencies.
1518 const depMap = state.calculateDepMap();
1519 for (const [rev, depRevs] of depMap) {
1520 const newRev = map.get(rev);
1521 if (newRev == null) {
1522 return false;
1523 }
1524 for (const depRev of depRevs) {
1525 const newDepRev = map.get(depRev);
1526 if (newDepRev == null) {
1527 return false;
1528 }
1529 if (!generatorContains(state.log(newRev), newDepRev)) {
1530 return false;
1531 }
1532 }
1533 }
1534 // Passed checks.
1535 return true;
1536 }
1537
1538 canMoveDown = cachedMethod(this.canMoveDownImpl, {cache: canMoveDownCache});
1539 private canMoveDownImpl(rev: CommitRev): boolean {
1540 return rev > 0 && this.canMoveUp(prev(rev));
1541 }
1542
1543 canMoveUp = cachedMethod(this.canMoveUpImpl, {cache: canMoveUpCache});
1544 private canMoveUpImpl(rev: CommitRev): boolean {
1545 return this.canReorder(reorderedRevs(this, rev));
1546 }
1547
1548 /**
1549 * Reorder stack. Similar to running `histedit`, followed by reordering
1550 * commits.
1551 *
1552 * See `canReorder` for the meaning of `order`.
1553 * This should only be called when `canReorder(order)` returned `true`.
1554 */
1555 reorder(order: CommitRev[]): CommitStackState {
1556 const commitRevMap = new Map<CommitRev, CommitRev>(
1557 order.map((fromRev, toRev) => [fromRev, toRev as CommitRev]),
1558 );
1559
1560 // Reorder file contents. This is somewhat tricky involving multiple
1561 // mappings. Here is an example:
1562 //
1563 // Stack: A-B-C-D. Original file contents: [11, 112, 0112, 01312].
1564 // Reorder to: A-D-B-C. Expected result: [11, 131, 1312, 01312].
1565 //
1566 // First, we figure out the file stack, and reorder it. The file stack
1567 // now has the content [11 (A), 131 (B), 1312 (C), 01312 (D)], but the
1568 // commit stack is still in the A-B-C-D order and refers to the file stack
1569 // using **fileRev**s. If we blindly reorder the commit stack to A-D-B-C,
1570 // the resulting files would be [11 (A), 01312 (D), 131 (B), 1312 (C)].
1571 //
1572 // To make it work properly, we apply a reverse mapping (A-D-B-C =>
1573 // A-B-C-D) to the file stack before reordering commits, changing
1574 // [11 (A), 131 (D), 1312 (B), 01312 (C)] to [11 (A), 1312 (B), 01312 (C),
1575 // 131 (D)]. So after the commit remapping it produces the desired
1576 // output.
1577 let state = this.useFileStack();
1578 const newFileStacks = state.fileStacks.map((origFileStack, fileIdx) => {
1579 let fileStack: FileStackState = origFileStack;
1580
1581 // file revs => commit revs => mapped commit revs => mapped file revs
1582 const fileRevs = fileStack.revs();
1583 const commitRevPaths: CommitIdx[] = fileRevs.map(fileRev =>
1584 nullthrows(state.fileToCommit.get(FileIdx({fileIdx, fileRev}))),
1585 );
1586 const commitRevs: CommitRev[] = commitRevPaths.map(({rev}) => rev);
1587 const mappedCommitRevs: CommitRev[] = commitRevs.map(rev => commitRevMap.get(rev) ?? rev);
1588 // commitRevs and mappedCommitRevs might not overlap, although they
1589 // have the same length (fileRevs.length). Turn them into compact
1590 // sequence to reason about.
1591 const fromRevs: FileRev[] = compactSequence(commitRevs);
1592 const toRevs: FileRev[] = compactSequence(mappedCommitRevs);
1593 if (deepEqual(fromRevs, toRevs)) {
1594 return fileStack;
1595 }
1596 // Mapping: zip(original revs, mapped file revs)
1597 const fileRevMap = new Map<FileRev, FileRev>(zip(fromRevs, toRevs));
1598 fileStack = fileStack.remapRevs(fileRevMap);
1599 // Apply the reverse mapping. See the above comment for why this is necessary.
1600 return new FileStackState(fileRevs.map(fileRev => fileStack.getRev(toRevs[fileRev])));
1601 });
1602 state = state.set('fileStacks', newFileStacks);
1603
1604 // Update state.stack.
1605 const newStack = state.stack.map((_commit, rev) => {
1606 const commit = nullthrows(state.stack.get(order[rev]));
1607 return commit.merge({
1608 parents: List(rev > 0 ? [prev(rev as CommitRev)] : []),
1609 rev: rev as CommitRev,
1610 });
1611 });
1612 state = state.set('stack', newStack);
1613
1614 return state.buildFileStacks();
1615 }
1616
1617 /** Replace a file stack. Throws if the new stack has a different length. */
1618 setFileStack(fileIdx: number, stack: FileStackState): CommitStackState {
1619 return this.setFileStackInternal(fileIdx, stack, (oldStack, newStack) => {
1620 assert(oldStack.revLength === newStack.revLength, 'fileStack length mismatch');
1621 });
1622 }
1623
1624 /** Internal use: replace a file stack. */
1625 private setFileStackInternal(
1626 fileIdx: number,
1627 stack: FileStackState,
1628 check?: (oldStack: FileStackState, newStack: FileStackState) => void,
1629 ): CommitStackState {
1630 const oldStack = this.fileStacks.get(fileIdx);
1631 assert(oldStack != null, 'fileIdx out of range');
1632 check?.(oldStack, stack);
1633 const newInner = this.inner.setIn(['fileStacks', fileIdx], stack);
1634 return new CommitStackState(undefined, newInner);
1635 }
1636
1637 /**
1638 * Extract part of the commit stack as a new linear stack.
1639 *
1640 * The new stack is "dense" in a way that each commit's "files"
1641 * include all files every referred by the stack, even if the
1642 * file is not modified.
1643 *
1644 * The new stack:
1645 * - Does not have "originalStack".
1646 * - "Dense". Therefore file revs (in fileStacks) map to all
1647 * commits.
1648 * - Preserves the rename information, but does not follow renames
1649 * when building the file stacks.
1650 * - Preserves non-utf8 files, but does not build into the file
1651 * stacks, which means their content cannot be edited, but might
1652 * still be moved around.
1653 *
1654 * It is for the interactive split use-case.
1655 */
1656 denseSubStack(revs: List<CommitRev>): CommitStackState {
1657 const commits = revs.map(rev => this.stack.get(rev)).filter(Boolean) as List<CommitState>;
1658 const bottomFiles = new Map<RepoPath, FileState>();
1659 const followRenames = false;
1660
1661 // Use this.parentFile to populate bottomFiles.
1662 commits.forEach(commit => {
1663 const startRev = commit.rev;
1664 commit.files.forEach((file, startPath) => {
1665 ([startPath].filter(Boolean) as [string]).forEach(path => {
1666 if (!bottomFiles.has(path)) {
1667 const [, , file] = this.parentFile(startRev, path, false);
1668 bottomFiles.set(path, file);
1669 }
1670 if (file.copyFrom != null) {
1671 const [, fromPath, fromFile] = this.parentFile(startRev, path, true);
1672 bottomFiles.set(fromPath, fromFile);
1673 }
1674 });
1675 });
1676 });
1677
1678 // Modify stack:
1679 // - Re-assign "rev"s (including "parents").
1680 // - Assign file contents so files are considered changed in every commit.
1681 const currentFiles = new Map(bottomFiles);
1682 const stack: List<CommitState> = commits.map((commit, i) => {
1683 const newFiles = commit.files.withMutations(mut => {
1684 let files = mut;
1685 // Add unchanged files to force treating files as "modified".
1686 currentFiles.forEach((file, path) => {
1687 const inCommitFile = files.get(path);
1688 if (inCommitFile == undefined) {
1689 // Update files so all files are considered changed and got a file rev assigned.
1690 files = files.set(path, file ?? ABSENT_FILE);
1691 } else {
1692 // Update currentFiles so it can be used by the next commit.
1693 // Avoid repeating "copyFrom".
1694 currentFiles.set(path, inCommitFile.remove('copyFrom'));
1695 }
1696 });
1697 return files;
1698 });
1699 const parents = i === 0 ? List<CommitRev>() : List([prev(i as CommitRev)]);
1700 return commit.merge({rev: i as CommitRev, files: newFiles, parents});
1701 });
1702
1703 const record = CommitStackRecord({
1704 stack,
1705 bottomFiles,
1706 });
1707 const newStack = new CommitStackState(undefined, record);
1708 return newStack.buildFileStacks({followRenames}).useFileStack();
1709 }
1710
1711 /**
1712 * Replace the `startRev` (inclusive) to `endRev` (exclusive) sub stack
1713 * with commits from the `subStack`.
1714 *
1715 * Unmodified changes will be dropped. Top commits with empty changes are
1716 * dropped. This turns a "dense" back to a non-"dense" one.
1717 *
1718 * Intended for interactive split use-case.
1719 */
1720 applySubStack(
1721 startRev: CommitRev,
1722 endRev: CommitRev,
1723 subStack: CommitStackState,
1724 ): CommitStackState {
1725 assert(
1726 startRev >= 0 && endRev <= this.stack.size && startRev < endRev,
1727 'startRev or endRev out of range',
1728 );
1729
1730 const contentSubStack = subStack.useFileContent();
1731 const state = this.useFileContent();
1732
1733 // Used to detect "unchanged" files in subStack.
1734 const afterFileMap = new Map(
1735 [...state.bottomFiles.entries()].map(([path, file]) => [path, file]),
1736 );
1737
1738 // Used to check the original "final" content of files.
1739 const beforeFileMap = new Map(afterFileMap);
1740
1741 const updateFileMap = (commit: CommitState, map: Map<string, FileState>) =>
1742 commit.files.forEach((file, path) => map.set(path, file));
1743
1744 // Pick an unused key.
1745 const usedKeys = new Set(
1746 state.stack
1747 .filter(c => c.rev < startRev || c.rev >= endRev)
1748 .map(c => c.key)
1749 .toArray(),
1750 );
1751 const pickKey = (c: CommitState): CommitState => {
1752 if (usedKeys.has(c.key)) {
1753 for (let i = 0; ; ++i) {
1754 const key = `${c.key}-${i}`;
1755 if (!usedKeys.has(key)) {
1756 usedKeys.add(c.key);
1757 return c.set('key', key);
1758 }
1759 }
1760 } else {
1761 usedKeys.add(c.key);
1762 return c;
1763 }
1764 };
1765
1766 // Process commits in a "dense" stack.
1767 // - Update afterFileMap.
1768 // - Drop unchanged files.
1769 // - Drop the "absent" flag from files if they are not empty.
1770 // - Pick a unique key.
1771 // - Add "parent" for the first commit.
1772 // - Adjust "revs".
1773 const processDenseCommit = (c: CommitState): CommitState => {
1774 const newFiles = c.files.flatMap<RepoPath, FileState>((currentFile, path) => {
1775 let file: FileState = currentFile;
1776 const oldFile = afterFileMap.get(path);
1777 // Drop "absent" flag (and reuse the old flag).
1778 if (
1779 file.flags?.includes(ABSENT_FLAG) &&
1780 typeof file.data === 'string' &&
1781 file.data.length > 0
1782 ) {
1783 let oldFlag = oldFile?.flags;
1784 if (oldFlag === ABSENT_FLAG) {
1785 oldFlag = undefined;
1786 }
1787 if (oldFlag == null) {
1788 file = file.remove('flags');
1789 } else {
1790 file = file.set('flags', oldFlag);
1791 }
1792 }
1793 // Drop unchanged files.
1794 const keep = oldFile == null || !isContentSame(oldFile, file);
1795 // Update afterFileMap.
1796 if (keep) {
1797 afterFileMap.set(path, file);
1798 }
1799 return Seq(keep ? [[path, file]] : []);
1800 });
1801 const isFirst = c.rev === 0;
1802 let commit = rewriteCommitRevs(pickKey(c), r => (r + startRev) as CommitRev).set(
1803 'files',
1804 newFiles,
1805 );
1806 if (isFirst && startRev > 0) {
1807 commit = commit.set('parents', List([prev(startRev)]));
1808 }
1809 return commit;
1810 };
1811
1812 // |<--- to delete --->|
1813 // Before: ... |startRev ... endRev| ...
1814 // New: ... |filter(substack) | ...
1815 // filter: remove empty commits
1816 let newSubStackSize = 0;
1817 const newStack = state.stack.flatMap(c => {
1818 updateFileMap(c, beforeFileMap);
1819 if (c.rev < startRev) {
1820 updateFileMap(c, afterFileMap);
1821 return Seq([c]);
1822 } else if (c.rev === startRev) {
1823 // dropUnchangedFiles updates afterFileMap.
1824 let commits = contentSubStack.stack.map(c => processDenseCommit(c));
1825 // Drop empty commits at the end. Adjust offset.
1826 while (commits.last()?.files?.isEmpty()) {
1827 commits = commits.pop();
1828 }
1829 newSubStackSize = commits.size;
1830 return commits;
1831 } else if (c.rev > startRev && c.rev < endRev) {
1832 return Seq([]);
1833 } else {
1834 let commit = c;
1835 assert(c.rev >= endRev, 'bug: c.rev < endRev should be handled above');
1836 if (c.rev === endRev) {
1837 // This commit should have the same exact content as before, not just the
1838 // modified files, but also the unmodified ones.
1839 // We check all files ever changed by the stack between "before" and "after",
1840 // and bring their content back to "before" in this commit.
1841 beforeFileMap.forEach((beforeFile, path) => {
1842 if (commit.files.has(path)) {
1843 return;
1844 }
1845 const afterFile = afterFileMap.get(path);
1846 if (afterFile == null || !isContentSame(beforeFile, afterFile)) {
1847 commit = commit.setIn(['files', path], beforeFile);
1848 }
1849 });
1850 // Delete file added by the subStack that do not exist before.
1851 afterFileMap.forEach((_, path) => {
1852 if (!beforeFileMap.has(path)) {
1853 commit = commit.setIn(['files', path], ABSENT_FILE);
1854 }
1855 });
1856 }
1857 const offset = newSubStackSize - (endRev - startRev);
1858 return Seq([
1859 rewriteCommitRevs(
1860 commit,
1861 r => ((r >= startRev && r < endRev ? endRev - 1 : r) + offset) as CommitRev,
1862 ),
1863 ]);
1864 }
1865 });
1866
1867 // This function might be frequnetly called during interacitve split.
1868 // Do not build file stacks (potentially slow) now.
1869 return state.set('stack', newStack);
1870 }
1871
1872 /** Test if a path at the given rev is a renamed (not copy). */
1873 isRename(rev: CommitRev, path: RepoPath): boolean {
1874 const commit = this.get(rev);
1875 if (commit == null) {
1876 return false;
1877 }
1878 return isRename(commit, path);
1879 }
1880
1881 /**
1882 * If the given file has a metadata change, return the old and new metadata.
1883 * Otherwise, return undefined.
1884 */
1885 changedFileMetadata(
1886 rev: CommitRev,
1887 path: RepoPath,
1888 followRenames = false,
1889 ): [FileMetadata, FileMetadata] | undefined {
1890 const file = this.getFile(rev, path);
1891 const parentFile = this.parentFile(rev, path, followRenames)[2];
1892 const fileMeta = toMetadata(file);
1893 // Only report "changed" if copyFrom is newly set.
1894 const parentMeta = toMetadata(parentFile).remove('copyFrom');
1895 return fileMeta.equals(parentMeta) ? undefined : [parentMeta, fileMeta];
1896 }
1897}
1898
1899const canDropCache = new LRU(1000);
1900const calculateDepMapCache = new LRU(1000);
1901const canFoldDownCache = new LRU(1000);
1902const canMoveUpCache = new LRU(1000);
1903const canMoveDownCache = new LRU(1000);
1904
1905function getBottomFilesFromExportStack(stack: Readonly<ExportStack>): Map<RepoPath, FileState> {
1906 // bottomFiles requires that the stack only has one root.
1907 checkStackSingleRoot(stack);
1908
1909 // Calculate bottomFiles.
1910 const bottomFiles: Map<RepoPath, FileState> = new Map();
1911 stack.forEach(commit => {
1912 for (const [path, file] of Object.entries(commit.relevantFiles ?? {})) {
1913 if (!bottomFiles.has(path)) {
1914 bottomFiles.set(path, convertExportFileToFileState(file));
1915 }
1916 }
1917
1918 // Files not yet existed in `bottomFiles` means they are added (in root commits)
1919 // mark them as "missing" in the stack bottom.
1920 for (const path of Object.keys(commit.files ?? {})) {
1921 if (!bottomFiles.has(path)) {
1922 bottomFiles.set(path, ABSENT_FILE);
1923 }
1924 }
1925 });
1926
1927 return bottomFiles;
1928}
1929
1930function convertExportFileToFileState(file: ExportFile | null): FileState {
1931 if (file == null) {
1932 return ABSENT_FILE;
1933 }
1934 return FileState({
1935 data:
1936 file.data != null
1937 ? file.data
1938 : file.dataBase85
1939 ? Base85({dataBase85: file.dataBase85})
1940 : DataRef(nullthrows(file.dataRef)),
1941 copyFrom: file.copyFrom,
1942 flags: file.flags,
1943 });
1944}
1945
1946function getCommitStatesFromExportStack(stack: Readonly<ExportStack>): List<CommitState> {
1947 checkStackParents(stack);
1948
1949 // Prepare nodeToRev conversion.
1950 const revs: CommitRev[] = [...stack.keys()] as CommitRev[];
1951 const nodeToRevMap: Map<Hash, CommitRev> = new Map(revs.map(rev => [stack[rev].node, rev]));
1952 const nodeToRev = (node: Hash): CommitRev => {
1953 const rev = nodeToRevMap.get(node);
1954 if (rev == null) {
1955 throw new Error(
1956 `Rev ${rev} should be known ${JSON.stringify(nodeToRevMap)} (bug in debugexportstack?)`,
1957 );
1958 }
1959 return rev;
1960 };
1961
1962 // Calculate requested stack.
1963 const commitStates = stack.map(commit =>
1964 CommitState({
1965 originalNodes: ImSet([commit.node]),
1966 rev: nodeToRev(commit.node),
1967 key: commit.node,
1968 author: commit.author,
1969 date: DateTuple({unix: commit.date[0], tz: commit.date[1]}),
1970 text: commit.text,
1971 // Treat commits that are not requested explicitly as immutable too.
1972 immutableKind: commit.immutable || !commit.requested ? 'hash' : 'none',
1973 parents: List((commit.parents ?? []).map(p => nodeToRev(p))),
1974 files: ImMap<RepoPath, FileState>(
1975 Object.entries(commit.files ?? {}).map(([path, file]) => [
1976 path,
1977 convertExportFileToFileState(file),
1978 ]),
1979 ),
1980 }),
1981 );
1982
1983 return List(commitStates);
1984}
1985
1986/** Check that there is only one root in the stack. */
1987function checkStackSingleRoot(stack: Readonly<ExportStack>) {
1988 const rootNodes = stack.filter(commit => (commit.parents ?? []).length === 0);
1989 if (rootNodes.length > 1) {
1990 throw new Error(
1991 `Multiple roots ${JSON.stringify(rootNodes.map(c => c.node))} is not supported`,
1992 );
1993 }
1994}
1995
1996/**
1997 * Check the exported stack and throws if it breaks assumptions.
1998 * - No duplicated commits.
1999 * - "parents" refer to other commits in the stack.
2000 */
2001function checkStackParents(stack: Readonly<ExportStack>) {
2002 const knownNodes = new Set();
2003 stack.forEach(commit => {
2004 const parents = commit.parents ?? [];
2005 if (parents.length > 0) {
2006 if (!commit.requested) {
2007 throw new Error(
2008 `Requested commit ${commit.node} should not have parents ${JSON.stringify(
2009 parents,
2010 )} (bug in debugexportstack?)`,
2011 );
2012 }
2013 parents.forEach(parentNode => {
2014 if (!knownNodes.has(parentNode)) {
2015 throw new Error(`Parent commit ${parentNode} is not exported (bug in debugexportstack?)`);
2016 }
2017 });
2018 }
2019 if (parents.length > 1) {
2020 throw new Error(`Merge commit ${commit.node} is not supported`);
2021 }
2022 knownNodes.add(commit.node);
2023 });
2024 if (knownNodes.size != stack.length) {
2025 throw new Error('Commit stack has duplicated nodes (bug in debugexportstack?)');
2026 }
2027}
2028
2029/** Rewrite fields that contains `rev` based on the mapping function. */
2030function rewriteCommitRevs(
2031 commit: CommitState,
2032 revMapFunc: (rev: CommitRev) => CommitRev,
2033): CommitState {
2034 return commit.merge({
2035 rev: revMapFunc(commit.rev),
2036 parents: commit.parents.map(revMapFunc),
2037 });
2038}
2039
2040/** Guess if commit message is meaningful. Messages like "wip" or "fixup" are meaningless. */
2041function isMeaningfulText(text: string): boolean {
2042 const trimmed = text.trim();
2043 return trimmed.includes(' ') || trimmed.includes('\n') || trimmed.length > 20;
2044}
2045
2046/**
2047 * Turn distinct numbers to a 0..n sequence preserving the order.
2048 * For example, turn [0, 100, 50] into [0, 2, 1].
2049 * This could convert CommitRevs to FileRevs, assuming the file
2050 * stack is a sub-sequence of the commit sequence.
2051 */
2052function compactSequence(revs: CommitRev[]): FileRev[] {
2053 const sortedRevs = [...revs].sort((aRev, bRev) => aRev - bRev);
2054 return revs.map(rev => sortedRevs.indexOf(rev) as FileRev);
2055}
2056
2057/** Reorder rev and rev + 1. Return [] if rev is out of range */
2058export function reorderedRevs(state: CommitStackState, rev: number): CommitRev[] {
2059 // Basically, `toSpliced`, but it's not available everywhere.
2060 const order = state.revs();
2061 if (rev < 0 || rev >= order.length - 1) {
2062 return [];
2063 }
2064 const rev1 = order[rev];
2065 const rev2 = order[rev + 1];
2066 order.splice(rev, 2, rev2, rev1);
2067 return order;
2068}
2069
2070type BuildFileStackOptions = {followRenames?: boolean};
2071
2072// Re-export for compatibility
2073export {
2074 ABSENT_FILE,
2075 ABSENT_FLAG,
2076 Base85,
2077 CommitIdx,
2078 CommitState,
2079 DataRef,
2080 DateTuple,
2081 FileIdx,
2082 FileState,
2083 isAbsent,
2084 isContentSame,
2085 isRename,
2086 isUtf8,
2087 toMetadata,
2088};
2089export type {CommitRev, FileMetadata, FileRev, FileStackIndex};
2090