addons/isl/src/stackEdit/absorb.tsblame
View source
b69ab311/**
b69ab312 * Copyright (c) Meta Platforms, Inc. and affiliates.
b69ab313 *
b69ab314 * This source code is licensed under the MIT license found in the
b69ab315 * LICENSE file in the root directory of this source tree.
b69ab316 */
b69ab317
b69ab318import type {RecordOf} from 'immutable';
b69ab319import type {LineInfo} from '../linelog';
b69ab3110import type {FileStackIndex} from './commitStackState';
b69ab3111import type {FileRev, FileStackState} from './fileStackState';
b69ab3112
b69ab3113import {Map as ImMap, List, Record} from 'immutable';
b69ab3114import {diffLines, splitLines} from 'shared/diff';
b69ab3115import {dedup, nullthrows} from 'shared/utils';
b69ab3116import {t} from '../i18n';
b69ab3117import {assert} from '../utils';
b69ab3118import {max, prev} from './revMath';
b69ab3119
b69ab3120/** A diff chunk analyzed by `analyseFileStack`. */
b69ab3121export type AbsorbEditProps = {
b69ab3122 /** The start line of the old content (start from 0, inclusive). */
b69ab3123 oldStart: number;
b69ab3124 /** The end line of the old content (start from 0, exclusive). */
b69ab3125 oldEnd: number;
b69ab3126 /**
b69ab3127 * The old content to be replaced by newLines.
b69ab3128 * If you know the full content of the old file as `allLines`, you
b69ab3129 * can also use `allLines.slice(oldStart, oldEnd)` to get this.
b69ab3130 */
b69ab3131 oldLines: List<string>;
b69ab3132 /** The start line of the new content (start from 0, inclusive). */
b69ab3133 newStart: number;
b69ab3134 /** The end line of the new content (start from 0, exclusive). */
b69ab3135 newEnd: number;
b69ab3136 /** The new content to replace oldLines. */
b69ab3137 newLines: List<string>;
b69ab3138 /**
b69ab3139 * Which rev introduces the "old" chunk.
b69ab3140 * The following revs are expected to contain this chunk too.
b69ab3141 * This is usually the "blame" rev in the stack.
b69ab3142 */
b69ab3143 introductionRev: FileRev;
b69ab3144 /**
b69ab3145 * File revision (starts from 0) that the diff chunk is currently
b69ab3146 * selected to apply to. `null`: no selectioin.
b69ab3147 * Initially, this is the "suggested" rev to absorb to. Later,
b69ab3148 * the user can change this to a different rev.
b69ab3149 * Must be >= introductionRev.
b69ab3150 */
b69ab3151 selectedRev: FileRev | null;
b69ab3152 /** The "AbsorbEditId" associated with this diff chunk. */
b69ab3153 absorbEditId: AbsorbEditId;
b69ab3154 /** The file stack index (in commitState) associated with this diff chunk. */
b69ab3155 fileStackIndex?: FileStackIndex;
b69ab3156};
b69ab3157
b69ab3158/**
b69ab3159 * Represents an absorb edit from the wdir to the stack.
b69ab3160 *
b69ab3161 * This looks like a diff chunk, with extra info like "blame" (introductionRev)
b69ab3162 * and "amend -to" (selectedRev). Note this is not 1:1 mapping to diff chunks,
b69ab3163 * since one diff chunk might be split into multiple `AbsorbEdit`s if they need
b69ab3164 * to be absorbed to different commits.
b69ab3165 */
b69ab3166export const AbsorbEdit = Record<AbsorbEditProps>({
b69ab3167 oldStart: 0,
b69ab3168 oldEnd: 0,
b69ab3169 oldLines: List(),
b69ab3170 newStart: 0,
b69ab3171 newEnd: 0,
b69ab3172 newLines: List(),
b69ab3173 introductionRev: 0 as FileRev,
b69ab3174 selectedRev: null,
b69ab3175 absorbEditId: 0,
b69ab3176 fileStackIndex: undefined,
b69ab3177});
b69ab3178export type AbsorbEdit = RecordOf<AbsorbEditProps>;
b69ab3179
b69ab3180/**
b69ab3181 * Identifier of an `AbsorbEdit` in a file stack.
b69ab3182 */
b69ab3183export type AbsorbEditId = number;
b69ab3184
b69ab3185/**
b69ab3186 * Maximum `AbsorbEditId` (exclusive). Must be an exponent of 2.
b69ab3187 *
b69ab3188 * Practically this shares the 52 bits (defined by IEEE 754) with the integer
b69ab3189 * part of the `Rev`.
b69ab3190 */
b69ab3191// eslint-disable-next-line no-bitwise
b69ab3192const MAX_ABSORB_EDIT_ID = 1 << 20;
b69ab3193const ABSORB_EDIT_ID_FRACTIONAL_UNIT = 1 / MAX_ABSORB_EDIT_ID;
b69ab3194
b69ab3195/** Extract the "AbsorbEditId" from a linelog Rev */
b69ab3196export function extractRevAbsorbId(rev: FileRev): [FileRev, AbsorbEditId] {
b69ab3197 const fractional = rev % 1;
b69ab3198 const integerRev = rev - fractional;
b69ab3199 const absorbEditId = fractional / ABSORB_EDIT_ID_FRACTIONAL_UNIT - 1;
b69ab31100 assert(
b69ab31101 Number.isInteger(absorbEditId) && absorbEditId >= 0,
b69ab31102 `${rev} does not contain valid AbsorbEditId`,
b69ab31103 );
b69ab31104 return [integerRev as FileRev, absorbEditId];
b69ab31105}
b69ab31106
b69ab31107/** Embed an absorbEditId into a Rev */
b69ab31108export function embedAbsorbId(rev: FileRev, absorbEditId: AbsorbEditId): FileRev {
b69ab31109 assert(Number.isInteger(rev), `${rev} already has an absorbEditId embedded`);
b69ab31110 assert(
b69ab31111 absorbEditId < MAX_ABSORB_EDIT_ID - 1,
b69ab31112 t(
b69ab31113 `Number of absorb diff chunks exceeds maximum limit ($count). Please retry with only a subset of the changes.`,
b69ab31114 {replace: {$count: (absorbEditId + 1).toString()}},
b69ab31115 ),
b69ab31116 );
b69ab31117 return (rev + ABSORB_EDIT_ID_FRACTIONAL_UNIT * (absorbEditId + 1)) as FileRev;
b69ab31118}
b69ab31119
b69ab31120/**
b69ab31121 * Returns a rev with all absorb edits for this rev included.
b69ab31122 * For example, `revWithAbsorb(2)` might return something like `2.999`.
b69ab31123 * */
b69ab31124export function revWithAbsorb(rev: FileRev): FileRev {
b69ab31125 return (Math.floor(rev) + 1 - ABSORB_EDIT_ID_FRACTIONAL_UNIT) as FileRev;
b69ab31126}
b69ab31127
b69ab31128/**
b69ab31129 * Calculate absorb edits for a stack.
b69ab31130 *
b69ab31131 * The stack top is treated as `wdir()` to be absorbed to the rest of the
b69ab31132 * stack. The stack bottom is treated as imutable `public()`.
b69ab31133 *
b69ab31134 * All edits in `wdir()` will be broken down and labeled with `AbsorbEditId`s.
b69ab31135 * If an edit with `id: AbsorbEditId` has a default absorb destination
b69ab31136 * `x: Rev`, then this edit will be inserted in linelog as rev
b69ab31137 * `embedAbsorbId(x, id)`, and can be checked out via
b69ab31138 * `linelog.checkOut(revWithAbsorb(x))`.
b69ab31139 *
b69ab31140 * If an edit has no default destination, for example, the surrounding lines
b69ab31141 * belong to public commit (rev 0), the edit will be left in the `wdir()`,
b69ab31142 * and can be checked out using `revWithAbsorb(wdirRev)`, where `wdirRev` is
b69ab31143 * the max integer rev in the linelog.
b69ab31144 *
b69ab31145 * Returns `FileStackState` with absorb edits embedded in the linelog, along
b69ab31146 * with a mapping from the `AbsorbEditId` to the diff chunk.
b69ab31147 */
b69ab31148export function calculateAbsorbEditsForFileStack(
b69ab31149 stack: FileStackState,
b69ab31150 options?: {fileStackIndex?: FileStackIndex},
b69ab31151): [FileStackState, ImMap<AbsorbEditId, AbsorbEdit>] {
b69ab31152 // rev 0 (public), 1, 2, ..., wdirRev-1 (stack top to absorb), wdirRev (wdir virtual rev)
b69ab31153 const wdirRev = prev(stack.revLength);
b69ab31154 assert(
b69ab31155 wdirRev >= 1,
b69ab31156 'calculateAbsorbEditsForFileStack requires at least one wdir(), one public()',
b69ab31157 );
b69ab31158 const fileStackIndex = options?.fileStackIndex;
b69ab31159 const diffChunks = analyseFileStackWithWdirAtTop(stack, {wdirRev, fileStackIndex});
b69ab31160 // Drop wdirRev, then re-insert the chunks.
b69ab31161 let newStack = stack.truncate(wdirRev);
b69ab31162 let absorbIdToDiffChunk = ImMap<AbsorbEditId, AbsorbEdit>();
b69ab31163 const diffChunksWithAbsorbId = diffChunks.map(chunk => {
b69ab31164 absorbIdToDiffChunk = absorbIdToDiffChunk.set(chunk.absorbEditId, chunk);
b69ab31165 return chunk;
b69ab31166 });
b69ab31167 // Re-insert the chunks with the absorbId.
b69ab31168 newStack = applyFileStackEditsWithAbsorbId(newStack, diffChunksWithAbsorbId);
b69ab31169 return [newStack, absorbIdToDiffChunk];
b69ab31170}
b69ab31171
b69ab31172/**
b69ab31173 * Similar to `analyseFileStack`, but the stack contains the "wdir()" at the top:
b69ab31174 * The stack revisions look like: `[0:public] [1] [2] ... [stackTop] [wdir]`.
b69ab31175 */
b69ab31176export function analyseFileStackWithWdirAtTop(
b69ab31177 stack: FileStackState,
b69ab31178 options?: {wdirRev?: FileRev; fileStackIndex?: FileStackIndex},
b69ab31179): List<AbsorbEdit> {
b69ab31180 const wdirRev = options?.wdirRev ?? prev(stack.revLength);
b69ab31181 const stackTopRev = prev(wdirRev);
b69ab31182 assert(stackTopRev >= 0, 'stackTopRev must be positive');
b69ab31183 const newText = stack.getRev(wdirRev);
b69ab31184 let edits = analyseFileStack(stack, newText, stackTopRev);
b69ab31185 const fileStackIndex = options?.fileStackIndex;
b69ab31186 if (fileStackIndex != null) {
b69ab31187 edits = edits.map(edit => edit.set('fileStackIndex', fileStackIndex));
b69ab31188 }
b69ab31189 return edits;
b69ab31190}
b69ab31191
b69ab31192/**
b69ab31193 * Given a stack and the latest changes (usually at the stack top),
b69ab31194 * calculate the diff chunks and the revs that they might be absorbed to.
b69ab31195 * The rev 0 of the file stack should come from a "public" (immutable) commit.
b69ab31196 */
b69ab31197export function analyseFileStack(
b69ab31198 stack: FileStackState,
b69ab31199 newText: string,
b69ab31200 stackTopRev?: FileRev,
b69ab31201): List<AbsorbEdit> {
b69ab31202 assert(stack.revLength > 0, 'stack should not be empty');
b69ab31203 const linelog = stack.convertToLineLog();
b69ab31204 const oldRev = stackTopRev ?? prev(stack.revLength);
b69ab31205 const oldText = stack.getRev(oldRev);
b69ab31206 const oldLines = splitLines(oldText);
b69ab31207 // The `LineInfo` contains "blame" information.
b69ab31208 const oldLineInfos = linelog.checkOutLines(oldRev);
b69ab31209 const newLines = splitLines(newText);
b69ab31210 const result: Array<AbsorbEdit> = [];
b69ab31211 let nextAbsorbId = 0;
b69ab31212 const allocateAbsorbId = () => {
b69ab31213 const id = nextAbsorbId;
b69ab31214 nextAbsorbId += 1;
b69ab31215 return id;
b69ab31216 };
b69ab31217 diffLines(oldLines, newLines).forEach(([a1, a2, b1, b2]) => {
b69ab31218 // a1, a2: line numbers in the `oldRev`.
b69ab31219 // b1, b2: line numbers in `newText`.
b69ab31220 // See also [`_analysediffchunk`](https://github.com/facebook/sapling/blob/6f29531e83daa62d9bd3bc58b712755d34f41493/eden/scm/sapling/ext/absorb/__init__.py#L346)
b69ab31221 let involvedLineInfos = oldLineInfos.slice(a1, a2);
b69ab31222 if (involvedLineInfos.length === 0 && oldLineInfos.length > 0) {
b69ab31223 // This is an insertion. Check the surrounding lines, excluding lines from the public commit.
b69ab31224 const nearbyLineNumbers = dedup([a2, Math.max(0, a1 - 1)]);
b69ab31225 involvedLineInfos = nearbyLineNumbers.map(i => oldLineInfos[i]);
b69ab31226 }
b69ab31227 // Check the revs. Skip public commits. The Python implementation only skips public
b69ab31228 // for insertions. Here we aggressively skip public lines for modification and deletion too.
b69ab31229 const involvedRevs = dedup(
b69ab31230 involvedLineInfos.map(info => info.rev as FileRev).filter(rev => rev > 0),
b69ab31231 );
b69ab31232 // Normalize `selectedRev` so it cannot be a public commit (fileRev === 0).
b69ab31233 // Setting to `null` to make the edit deselected (left in the working copy).
b69ab31234 const normalizeSelectedRev = (rev: FileRev): FileRev | null => (rev === 0 ? null : rev);
b69ab31235 if (involvedRevs.length === 1) {
b69ab31236 // Only one rev. Set selectedRev to this.
b69ab31237 // For simplicity, we're not checking the "continuous" lines here yet (different from Python).
b69ab31238 const introductionRev = involvedRevs[0];
b69ab31239 result.push(
b69ab31240 AbsorbEdit({
b69ab31241 oldStart: a1,
b69ab31242 oldEnd: a2,
b69ab31243 oldLines: List(oldLines.slice(a1, a2)),
b69ab31244 newStart: b1,
b69ab31245 newEnd: b2,
b69ab31246 newLines: List(newLines.slice(b1, b2)),
b69ab31247 introductionRev,
b69ab31248 selectedRev: normalizeSelectedRev(introductionRev),
b69ab31249 absorbEditId: allocateAbsorbId(),
b69ab31250 }),
b69ab31251 );
b69ab31252 } else if (b1 === b2) {
b69ab31253 // Deletion. Break the chunk into sub-chunks with different selectedRevs.
b69ab31254 // For simplicity, we're not checking the "continuous" lines here yet (different from Python).
b69ab31255 splitChunk(a1, a2, oldLineInfos, (oldStart, oldEnd, introductionRev) => {
b69ab31256 result.push(
b69ab31257 AbsorbEdit({
b69ab31258 oldStart,
b69ab31259 oldEnd,
b69ab31260 oldLines: List(oldLines.slice(oldStart, oldEnd)),
b69ab31261 newStart: b1,
b69ab31262 newEnd: b2,
b69ab31263 newLines: List([]),
b69ab31264 introductionRev,
b69ab31265 selectedRev: normalizeSelectedRev(introductionRev),
b69ab31266 absorbEditId: allocateAbsorbId(),
b69ab31267 }),
b69ab31268 );
b69ab31269 });
b69ab31270 } else if (a2 - a1 === b2 - b1 && involvedLineInfos.some(info => info.rev > 0)) {
b69ab31271 // Line count matches on both side. No public lines.
b69ab31272 // We assume the "a" and "b" sides are 1:1 mapped.
b69ab31273 // So, even if the "a"-side lines blame to different revs, we can
b69ab31274 // still break the chunks to individual lines.
b69ab31275 const delta = b1 - a1;
b69ab31276 splitChunk(a1, a2, oldLineInfos, (oldStart, oldEnd, introductionRev) => {
b69ab31277 const newStart = oldStart + delta;
b69ab31278 const newEnd = oldEnd + delta;
b69ab31279 result.push(
b69ab31280 AbsorbEdit({
b69ab31281 oldStart,
b69ab31282 oldEnd,
b69ab31283 oldLines: List(oldLines.slice(oldStart, oldEnd)),
b69ab31284 newStart,
b69ab31285 newEnd,
b69ab31286 newLines: List(newLines.slice(newStart, newEnd)),
b69ab31287 introductionRev,
b69ab31288 selectedRev: normalizeSelectedRev(introductionRev),
b69ab31289 absorbEditId: allocateAbsorbId(),
b69ab31290 }),
b69ab31291 );
b69ab31292 });
b69ab31293 } else {
b69ab31294 // Other cases, like replacing 10 lines from 3 revs to 20 lines.
b69ab31295 // It might be possible to build extra fancy UIs to support it
b69ab31296 // asking the user which sub-chunk on the "a" side matches which
b69ab31297 // sub-chunk on the "b" side.
b69ab31298 // For now, we just report this chunk as a whole chunk that can
b69ab31299 // only be absorbed to the "max" rev where the left side is
b69ab31300 // "settled" down.
b69ab31301 result.push(
b69ab31302 AbsorbEdit({
b69ab31303 oldStart: a1,
b69ab31304 oldEnd: a2,
b69ab31305 oldLines: List(oldLines.slice(a1, a2)),
b69ab31306 newStart: b1,
b69ab31307 newEnd: b2,
b69ab31308 newLines: List(newLines.slice(b1, b2)),
b69ab31309 introductionRev: max(...involvedRevs, 0),
b69ab31310 selectedRev: null,
b69ab31311 absorbEditId: allocateAbsorbId(),
b69ab31312 }),
b69ab31313 );
b69ab31314 }
b69ab31315 });
b69ab31316 return List(result);
b69ab31317}
b69ab31318
b69ab31319/**
b69ab31320 * Apply edits specified by `chunks`.
b69ab31321 * The `chunk.selectedRev` is expected to include the `AbsorbEditId`.
b69ab31322 */
b69ab31323export function applyFileStackEditsWithAbsorbId(
b69ab31324 stack: FileStackState,
b69ab31325 chunks: Iterable<AbsorbEdit>,
b69ab31326): FileStackState {
b69ab31327 assert(stack.revLength > 0, 'stack should not be empty');
b69ab31328 let linelog = stack.convertToLineLog();
b69ab31329 const wdirRev = stack.revLength;
b69ab31330 const stackTopRev = wdirRev - 1;
b69ab31331 // Apply the changes. Assuming there are no overlapping chunks, we apply
b69ab31332 // from end to start so the line numbers won't need change.
b69ab31333 const sortedChunks = [...chunks].toSorted((a, b) => b.oldEnd - a.oldEnd);
b69ab31334 sortedChunks.forEach(chunk => {
b69ab31335 // If not "selected" to amend to a commit, leave the chunk at the wdir.
b69ab31336 const baseRev = chunk.selectedRev ?? (wdirRev as FileRev);
b69ab31337 const absorbEditId = nullthrows(chunk.absorbEditId);
b69ab31338 const targetRev = embedAbsorbId(baseRev, absorbEditId);
b69ab31339 assert(
b69ab31340 targetRev >= chunk.introductionRev,
b69ab31341 `selectedRev ${targetRev} must be >= introductionRev ${chunk.introductionRev}`,
b69ab31342 );
b69ab31343 assert(
b69ab31344 targetRev > 0,
b69ab31345 'selectedRev must be > 0 since rev 0 is from the immutable public commit',
b69ab31346 );
b69ab31347 // Edit the content of a past revision (targetRev, and follow-ups) from a
b69ab31348 // future revision (oldRev, matches the line numbers).
b69ab31349 linelog = linelog.editChunk(
b69ab31350 stackTopRev,
b69ab31351 chunk.oldStart,
b69ab31352 chunk.oldEnd,
b69ab31353 targetRev,
b69ab31354 chunk.newLines.toArray(),
b69ab31355 );
b69ab31356 });
b69ab31357 return stack.fromLineLog(linelog);
b69ab31358}
b69ab31359
b69ab31360/** Split the start..end chunk into sub-chunks so each chunk has the same "blame" rev. */
b69ab31361function splitChunk(
b69ab31362 start: number,
b69ab31363 end: number,
b69ab31364 lineInfos: readonly LineInfo[],
b69ab31365 callback: (_start: number, _end: number, _introductionRev: FileRev) => void,
b69ab31366) {
b69ab31367 let lastStart = start;
b69ab31368 for (let i = start; i < end; i++) {
b69ab31369 const introductionRev = lineInfos[i].rev as FileRev;
b69ab31370 if (i + 1 === end || introductionRev != lineInfos[i + 1].rev) {
b69ab31371 callback(lastStart, i + 1, introductionRev);
b69ab31372 lastStart = i + 1;
b69ab31373 }
b69ab31374 }
b69ab31375}