addons/isl/src/linelog.tsblame
View source
b69ab311/**
b69ab312 * Portions 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
b69ab318/*
b69ab319
b69ab3110Copyright (c) 2020 Jun Wu
b69ab3111
b69ab3112Permission is hereby granted, free of charge, to any person obtaining a copy
b69ab3113of this software and associated documentation files (the "Software"), to deal
b69ab3114in the Software without restriction, including without limitation the rights
b69ab3115to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
b69ab3116copies of the Software, and to permit persons to whom the Software is
b69ab3117furnished to do so, subject to the following conditions:
b69ab3118
b69ab3119The above copyright notice and this permission notice shall be included in all
b69ab3120copies or substantial portions of the Software.
b69ab3121
b69ab3122THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
b69ab3123IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
b69ab3124FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
b69ab3125AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
b69ab3126LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
b69ab3127OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
b69ab3128SOFTWARE.
b69ab3129
b69ab3130*/
b69ab3131
b69ab3132import type {RecordOf, ValueObject} from 'immutable';
b69ab3133import type {LRUWithStats} from 'shared/LRU';
b69ab3134
b69ab3135import {hash, Set as ImSet, List, Record} from 'immutable';
b69ab3136import {cached, cachedMethod, LRU} from 'shared/LRU';
b69ab3137import {diffLines, splitLines} from 'shared/diff';
b69ab3138import {SelfUpdate} from 'shared/immutableExt';
b69ab3139import {nullthrows} from 'shared/utils';
b69ab3140import {assert} from './utils';
b69ab3141
b69ab3142/** Operation code. */
b69ab3143enum Op {
b69ab3144 /** Unconditional jump. */
b69ab3145 J = 0,
b69ab3146 /** Jump if the current rev >= operand. */
b69ab3147 JGE = 1,
b69ab3148 /** Jump if the current rev < operand. */
b69ab3149 JL = 2,
b69ab3150 /** Append a line. */
b69ab3151 LINE = 3,
b69ab3152 /** End execution. */
b69ab3153 END = 4,
b69ab3154}
b69ab3155
b69ab3156/** J instruction. */
b69ab3157const J = Record(
b69ab3158 {
b69ab3159 /** Opcode: J */
b69ab3160 op: Op.J,
b69ab3161 /** Program counter (offset to jump). */
b69ab3162 pc: 0,
b69ab3163 },
b69ab3164 'J',
b69ab3165);
b69ab3166type J = RecordOf<{
b69ab3167 op: Op.J;
b69ab3168 pc: number;
b69ab3169}>;
b69ab3170
b69ab3171/** JGE instruction. */
b69ab3172const JGE = Record(
b69ab3173 {
b69ab3174 /** Opcode: JGE */
b69ab3175 op: Op.JGE,
b69ab3176 /** `rev` to test. */
b69ab3177 rev: 0,
b69ab3178 /** Program counter (offset to jump). */
b69ab3179 pc: 0,
b69ab3180 },
b69ab3181 'JGE',
b69ab3182);
b69ab3183type JGE = RecordOf<{
b69ab3184 op: Op.JGE;
b69ab3185 rev: Rev;
b69ab3186 pc: number;
b69ab3187}>;
b69ab3188
b69ab3189/** JL instruction. */
b69ab3190const JL = Record(
b69ab3191 {
b69ab3192 /** Opcode: JL */
b69ab3193 op: Op.JL,
b69ab3194 /** `rev` to test. */
b69ab3195 rev: 0,
b69ab3196 /** Program counter (offset to jump). */
b69ab3197 pc: 0,
b69ab3198 },
b69ab3199 'JL',
b69ab31100);
b69ab31101type JL = RecordOf<{
b69ab31102 op: Op.JL;
b69ab31103 rev: Rev;
b69ab31104 pc: number;
b69ab31105}>;
b69ab31106
b69ab31107/** LINE instruction. */
b69ab31108const LINE = Record(
b69ab31109 {
b69ab31110 /** Opcode: LINE */
b69ab31111 op: Op.LINE,
b69ab31112 /** `rev` to test. */
b69ab31113 rev: 0,
b69ab31114 /** Line content. Includes EOL. */
b69ab31115 data: '',
b69ab31116 },
b69ab31117 'LINE',
b69ab31118);
b69ab31119type LINE = RecordOf<{
b69ab31120 op: Op.LINE;
b69ab31121 rev: Rev;
b69ab31122 data: string;
b69ab31123}>;
b69ab31124
b69ab31125/** END instruction. */
b69ab31126const END = Record(
b69ab31127 {
b69ab31128 /** Opcode: END */
b69ab31129 op: Op.END,
b69ab31130 },
b69ab31131 'END',
b69ab31132);
b69ab31133type END = RecordOf<{
b69ab31134 op: Op.END;
b69ab31135}>;
b69ab31136
b69ab31137/** Program counter (offset to instructions). */
b69ab31138type Pc = number;
b69ab31139
b69ab31140/** Revision number. Usually starts from 1. Larger number means newer versions.
b69ab31141 *
b69ab31142 * For advanced use-cases, this can be a floating number. For example, absorb
b69ab31143 * might use rev 2.5 between rev2 and rev 3, indicating the chunk is currently
b69ab31144 * absorbed into rev 2 (by checking out 2.999), while still preserving the rev
b69ab31145 * 2 losslessly (by checking out 2, instead of 2.999). `absorb` might also use
b69ab31146 * different fractional part to "tag" the chunk so they can be treated
b69ab31147 * differently. For example, there are 2 chunk edits in the working copy a.txt,
b69ab31148 * absorb might use `1 / 1024` to represent the first edit, and `2 / 1024` for
b69ab31149 * the second chunk edit so those edits can be moved (remapped) separately.
b69ab31150 * absorb might also split a chunk edit into multiple edits so the individual
b69ab31151 * lines can be moved separately.
b69ab31152 */
b69ab31153type Rev = number;
b69ab31154
b69ab31155/** Index of a line. Starts from 0. */
b69ab31156type LineIdx = number;
b69ab31157
b69ab31158/** Instruction. */
b69ab31159type Inst = J | END | JGE | JL | LINE;
b69ab31160
b69ab31161/** Information about a line. Internal (`lines`) result of `LineLog.checkOut`. */
b69ab31162interface LineInfo {
b69ab31163 /** Line content. Includes EOL. */
b69ab31164 data: string;
b69ab31165 /** Added by the given rev. */
b69ab31166 rev: Rev;
b69ab31167 /** Produced by the instruction at the given offset. */
b69ab31168 pc: Pc;
b69ab31169 /**
b69ab31170 * Whether the line is deleted.
b69ab31171 * This is always `false` if `checkOut(rev, None)`.
b69ab31172 * It might be `true` when checking out a range of revisions
b69ab31173 * (aka. `start` passed to `checkOut` is not `null`).
b69ab31174 */
b69ab31175 deleted: boolean;
b69ab31176}
b69ab31177
b69ab31178/** A "flatten" line. Result of `LineLog.flatten()`. */
b69ab31179type FlattenLineProps = {
b69ab31180 /** The line is present in the given revisions. */
b69ab31181 revs: ImSet<Rev>;
b69ab31182 /** Content of the line, including `\n`. */
b69ab31183 data: string;
b69ab31184};
b69ab31185const FlattenLine = Record<FlattenLineProps>({revs: ImSet(), data: ''});
b69ab31186type FlattenLine = RecordOf<FlattenLineProps>;
b69ab31187
b69ab31188/** Used by visitWithInsDelStacks */
b69ab31189type Frame = {rev: Rev; endPc: Pc};
b69ab31190
b69ab31191/**
b69ab31192 * List of instructions.
b69ab31193 *
b69ab31194 * This is a wrapper of `List<Inst>` for more efficient `hashCode` and `equals`
b69ab31195 * calculations. The default `hashCode` from `immutable.js` scans the whole
b69ab31196 * `List`. In this implementation we keep 2 internal values: hash and str. The
b69ab31197 * `hash` is used for hashCode, and the `str` is an append-only string that
b69ab31198 * tracks the `editChunk` and other operations to `List<Inst>` for testing
b69ab31199 * equality.
b69ab31200 *
b69ab31201 * You might have noticed that the `str` equality might not match the
b69ab31202 * `List<Inst>` equality. For example, if we remap 1 to 2, then remap 2 to 1,
b69ab31203 * the `List<Inst>` is not changed, but the `str` is changed. It is okay to
b69ab31204 * treat the linelogs as different in this case as we almost always immediately
b69ab31205 * rebuild linelogs after a `remap`. It's important to make sure `recordText`
b69ab31206 * with the same text list gets cache hit.
b69ab31207 */
b69ab31208class Code implements ValueObject {
b69ab31209 constructor(
b69ab31210 private instList: List<Inst> = List([END() as Inst]),
b69ab31211 private __hash: Readonly<number> = 0,
b69ab31212 private __valueOf: Readonly<string> = '',
b69ab31213 ) {}
b69ab31214
b69ab31215 getSize(): number {
b69ab31216 return this.instList.size;
b69ab31217 }
b69ab31218
b69ab31219 get(pc: Pc): Readonly<Inst> | undefined {
b69ab31220 return this.instList.get(pc);
b69ab31221 }
b69ab31222
b69ab31223 valueOf(): string {
b69ab31224 return this.__valueOf;
b69ab31225 }
b69ab31226
b69ab31227 equals(other: Code): boolean {
b69ab31228 return this.__valueOf === other.__valueOf;
b69ab31229 }
b69ab31230
b69ab31231 hashCode(): number {
b69ab31232 return this.__hash;
b69ab31233 }
b69ab31234
b69ab31235 /**
b69ab31236 * Dump instructions in a human readable format. Useful for debugging.
b69ab31237 * Note: This exposes internal details which might change in the future.
b69ab31238 */
b69ab31239 describeHumanReadableInstructions(): string[] {
b69ab31240 return this.instList.map((inst, i) => `${i}: ${describeInst(inst)}`).toArray();
b69ab31241 }
b69ab31242
b69ab31243 /**
b69ab31244 * Dump lines with ASCII annotated insertions and deletions stacks.
b69ab31245 */
b69ab31246 describeHumanReadableInsDelStacks(): string[] {
b69ab31247 // 1st Pass: Figure out the max stack depth, line length for padding.
b69ab31248 let maxInsStackDepth = 0;
b69ab31249 let maxDelStackDepth = 0;
b69ab31250 let maxLineLength = 'Insert (rev: 1000)'.length;
b69ab31251 this.visitWithInsDelStacks((insStack, delStack) => {
b69ab31252 return {
b69ab31253 onStackPush: () => {
b69ab31254 maxInsStackDepth = Math.max(maxInsStackDepth, insStack.length + 1);
b69ab31255 maxDelStackDepth = Math.max(maxDelStackDepth, delStack.length + 2);
b69ab31256 },
b69ab31257 onLine: line => {
b69ab31258 maxLineLength = Math.max(maxLineLength, line.data.length + 'Line: '.length);
b69ab31259 },
b69ab31260 };
b69ab31261 });
b69ab31262 // 2nd Pass: Render the instructions.
b69ab31263 const result: string[] = [];
b69ab31264 this.visitWithInsDelStacks((insStack, delStack) => {
b69ab31265 const pushLine = (data: string, leftAdjust?: number, rightAdjust?: number) => {
b69ab31266 const insDepth = insStack.length - 1 + (leftAdjust ?? 0);
b69ab31267 const delDepth = delStack.length + (rightAdjust ?? 0);
b69ab31268 const insPad = maxInsStackDepth - insDepth;
b69ab31269 const delPad = maxDelStackDepth - delDepth;
b69ab31270 const left =
b69ab31271 '|'.repeat(insDepth) +
b69ab31272 (leftAdjust == null ? ' '.repeat(insPad + 1) : `+${'-'.repeat(insPad)}`);
b69ab31273 const right =
b69ab31274 (rightAdjust == null ? ' '.repeat(delPad + 1) : `${'-'.repeat(delPad)}+`) +
b69ab31275 '|'.repeat(delDepth);
b69ab31276 const middle = data + ' '.repeat(maxLineLength - data.length);
b69ab31277 result.push(left + middle + right);
b69ab31278 };
b69ab31279 return {
b69ab31280 onStackPush: stack => {
b69ab31281 const rev = stack.at(-1)?.rev ?? 0;
b69ab31282 if (stack === insStack) {
b69ab31283 // | | +------ Insert (rev x) <- this line
b69ab31284 // | | | Line: .... <- following lines
b69ab31285 pushLine(`Insert (rev ${rev})`, -1);
b69ab31286 } else {
b69ab31287 pushLine(`Delete (rev ${rev})`, undefined, -1);
b69ab31288 }
b69ab31289 },
b69ab31290 onStackPop: stack => {
b69ab31291 if (stack === insStack) {
b69ab31292 pushLine('', 0);
b69ab31293 } else {
b69ab31294 pushLine('', undefined, 0);
b69ab31295 }
b69ab31296 },
b69ab31297 onLine: line => {
b69ab31298 pushLine(`Line: ${line.data.trimEnd()}`);
b69ab31299 },
b69ab31300 };
b69ab31301 });
b69ab31302 return result;
b69ab31303 }
b69ab31304
b69ab31305 editChunk(
b69ab31306 aRev: Rev,
b69ab31307 a1: LineIdx,
b69ab31308 a2: LineIdx,
b69ab31309 bRev: Rev,
b69ab31310 bLines: string[],
b69ab31311 [aLines, aLinesMutable]: [LineInfo[], true] | [Readonly<LineInfo[]>, false],
b69ab31312 ): Code {
b69ab31313 const start = this.instList.size;
b69ab31314
b69ab31315 assert(a1 <= a2, 'illegal chunk (a1 < a2)');
b69ab31316 assert(a2 <= aLines.length, 'out of bound a2 (wrong aRev?)');
b69ab31317
b69ab31318 // See also https://sapling-scm.com/docs/internals/linelog/#editing-linelog
b69ab31319 // # Before # After
b69ab31320 // # (pc): Instruction # (pc): Instruction
b69ab31321 // : ... : ...
b69ab31322 // a1Pc: <a1Inst> a1Pc: J start
b69ab31323 // a1Pc+1: ... a1Pc+1: ...
b69ab31324 // : ... : ...
b69ab31325 // a2Pc: ... a2Pc: ...
b69ab31326 // : ... : ...
b69ab31327 // len: N/A start: JL brev b2Pc [1]
b69ab31328 // : LINE brev b1 [1]
b69ab31329 // : LINE brev b1+1 [1]
b69ab31330 // : ... [1]
b69ab31331 // : LINE brev b2-1 [1]
b69ab31332 // b2Pc: JGE brev a2Pc [2]
b69ab31333 // : <a1Inst> (moved) [3]
b69ab31334 // : J a1Pc+1 [4]
b69ab31335 // [1]: Only present if `bLines` is not empty.
b69ab31336 // [2]: Only present if `a1 < a2`.
b69ab31337 // There are 2 choices for "a2Pc":
b69ab31338 // - The a2 line exactly: aLines[a2].pc
b69ab31339 // - The next instruction of the "a2 -1" line: aLines[a2 - 1].pc + 1
b69ab31340 // We pick the latter to avoid overly aggressive deletion.
b69ab31341 // The original C implementation might pick the former when editing
b69ab31342 // the last rev for performance optimization.
b69ab31343 // [3]: <a1 Inst> could be LINE or END.
b69ab31344 // [4]: As an optimization, this is only present if <a1 Inst> is not END.
b69ab31345 //
b69ab31346 // Optimization [OPT1] to make reorder less restrictive, treat insertion
b69ab31347 // (a1 == a2) at the beginning of another insertion (<a1 Inst> is after a
b69ab31348 // <JL>) specially. Our goal is to avoid nested JLs. Instead of patching
b69ab31349 // the a1Inst after the JL, we patch the JL (jlInst) so we can insert our
b69ab31350 // new JL (for this edit) before the old JL (jlInst, being patched).
b69ab31351 // Note this "JL followed by a1Inst" optimization needs to be applicable
b69ab31352 // multiple times. To do that, we also move the a1Inst to right after the
b69ab31353 // jlInst so the pattern "JL followed by a1Inst" can be recognized by the
b69ab31354 // next editChunk to apply the same optimization.
b69ab31355 //
b69ab31356 // # Before # After
b69ab31357 // # (pc): Instruction # (pc): Instruction
b69ab31358 // : ... : ...
b69ab31359 // : <jlInst> a1Pc-1: J start [*]
b69ab31360 // a1Pc: <a1Inst> a1Pc: NOP (J a1Pc+1) [*]
b69ab31361 // : ... : ...
b69ab31362 // len: N/A start: JL brev b2Pc
b69ab31363 // : (bLines)
b69ab31364 // b2Pc: <jlInst> (moved) [*]
b69ab31365 // : <a1Inst> (moved)
b69ab31366 // : J a1Pc [*]
b69ab31367 const newInstList = this.instList.withMutations(origCode => {
b69ab31368 let code = origCode;
b69ab31369 const a1Pc = aLines[a1].pc;
b69ab31370 // If `jlInst` is set, optimization [OPT1] is in effect.
b69ab31371 let jlInst = a1Pc > 0 && a1 === a2 ? code.get(a1Pc - 1) : undefined;
b69ab31372 if (jlInst?.op !== Op.JL) {
b69ab31373 jlInst = undefined;
b69ab31374 }
b69ab31375 if (bLines.length > 0) {
b69ab31376 // [1]
b69ab31377 const b2Pc = start + bLines.length + 1;
b69ab31378 code = code.push(JL({rev: bRev, pc: b2Pc}) as Inst);
b69ab31379 bLines.forEach(line => {
b69ab31380 code = code.push(LINE({rev: bRev, data: line}) as Inst);
b69ab31381 });
b69ab31382 assert(b2Pc === code.size, 'bug: wrong pc');
b69ab31383 }
b69ab31384 if (a1 < a2) {
b69ab31385 assert(jlInst === undefined, 'OPT1 requires no deletion');
b69ab31386 // [2]
b69ab31387 const a2Pc = aLines[a2 - 1].pc + 1;
b69ab31388 code = code.push(JGE({rev: bRev, pc: a2Pc}) as Inst);
b69ab31389 }
b69ab31390 if (aLinesMutable) {
b69ab31391 aLines[a1] = {...aLines[a1], pc: jlInst == null ? code.size : code.size + 1};
b69ab31392 }
b69ab31393 const a1Inst = nullthrows(code.get(a1Pc));
b69ab31394 if (jlInst === undefined) {
b69ab31395 // [3]
b69ab31396 code = code.push(a1Inst);
b69ab31397 if (a1Inst.op /* LINE or END */ !== Op.END) {
b69ab31398 // [4]
b69ab31399 code = code.push(J({pc: a1Pc + 1}) as Inst);
b69ab31400 }
b69ab31401 code = code.set(a1Pc, J({pc: start}) as Inst);
b69ab31402 } else {
b69ab31403 code = code
b69ab31404 .push(jlInst)
b69ab31405 .push(a1Inst)
b69ab31406 .push(J({pc: a1Pc}) as Inst)
b69ab31407 .set(a1Pc - 1, J({pc: start}) as Inst)
b69ab31408 .set(a1Pc, J({pc: a1Pc + 1}) as J);
b69ab31409 }
b69ab31410 return code;
b69ab31411 });
b69ab31412
b69ab31413 if (aLinesMutable) {
b69ab31414 const newLines = bLines.map((s, i) => {
b69ab31415 return {data: s, rev: bRev, pc: start + 1 + i, deleted: false};
b69ab31416 });
b69ab31417 aLines.splice(a1, a2 - a1, ...newLines);
b69ab31418 }
b69ab31419
b69ab31420 const newValueOf = `E${aRev},${a1},${a2},${bRev},${bLines.join('')}`;
b69ab31421 return this.newCode(newInstList, newValueOf);
b69ab31422 }
b69ab31423
b69ab31424 /**
b69ab31425 * Visit (execute) instructions with the insertion and deletion stacks
b69ab31426 * converted from JGE and JL instructions maintained by this function.
b69ab31427 *
b69ab31428 * See the comment in this function about how to turn JGE and JL to
b69ab31429 * the stacks.
b69ab31430 *
b69ab31431 * For stacks like this:
b69ab31432 *
b69ab31433 * +---- Insertion (rev 1)
b69ab31434 * | Line 1
b69ab31435 * | ----+ Deletion (rev 4)
b69ab31436 * | Line 2 |
b69ab31437 * | +-- Insertion (rev 2) |
b69ab31438 * | | Line 3 |
b69ab31439 * | | --+ | Deletion (rev 3)
b69ab31440 * | | Line 4 | |
b69ab31441 * | +-- | |
b69ab31442 * | Line 5 | |
b69ab31443 * | --+ |
b69ab31444 * | Line 6 |
b69ab31445 * | ----+
b69ab31446 * | Line 7
b69ab31447 * +----
b69ab31448 *
b69ab31449 * When visiting "Line 3", the callsite will get insertion stack =
b69ab31450 * [rev 1, rev 2] and deletion stack = [rev 4].
b69ab31451 *
b69ab31452 * Internally, this is done by turning conditional jumps (JGE or JL)
b69ab31453 * to stack pushes, pops at the JGE or JL destinations, and follow
b69ab31454 * unconditional jumps (J) as usual. For more details, see the comment
b69ab31455 * inside this function.
b69ab31456 *
b69ab31457 * This function will call `withContext` to provide the `insStack` and
b69ab31458 * `delStack` context, and expect the callsite to provide handlers it
b69ab31459 * is interested in.
b69ab31460 *
b69ab31461 * Typical use-cases include features that need to scan all (ever existed)
b69ab31462 * lines like flatten() and calculateDepMap().
b69ab31463 */
b69ab31464 visitWithInsDelStacks(
b69ab31465 withContext: (
b69ab31466 insStack: Readonly<Frame[]>,
b69ab31467 delStack: Readonly<Frame[]>,
b69ab31468 ) => {
b69ab31469 /** Before stack pop or push */
b69ab31470 onPc?: (pc: number) => void;
b69ab31471 /** After stack pop, before stack push */
b69ab31472 onLine?: (inst: LINE) => void;
b69ab31473 /** After stack pop, before stack push */
b69ab31474 onConditionalJump?: (inst: JGE | JL) => void;
b69ab31475 /** After stack push */
b69ab31476 onStackPush?: (stack: Readonly<Frame[]>) => void;
b69ab31477 /** After stack pop */
b69ab31478 onStackPop?: (stack: Readonly<Frame[]>) => void;
b69ab31479 },
b69ab31480 ) {
b69ab31481 // How does it work? First, insertions and deletions in linelog form
b69ab31482 // tree structures. For example:
b69ab31483 //
b69ab31484 // +---- Insertion (rev 1)
b69ab31485 // | Line 1
b69ab31486 // | ----+ Deletion (rev 4)
b69ab31487 // | Line 2 |
b69ab31488 // | +-- Insertion (rev 2) |
b69ab31489 // | | Line 3 |
b69ab31490 // | | --+ | Deletion (rev 3)
b69ab31491 // | | Line 4 | |
b69ab31492 // | +-- | |
b69ab31493 // | Line 5 | |
b69ab31494 // | --+ |
b69ab31495 // | Line 6 |
b69ab31496 // | ----+
b69ab31497 // | Line 7
b69ab31498 // +----
b69ab31499 //
b69ab31500 // Note interleaved insertions do not happen. For example, this does not
b69ab31501 // happen:
b69ab31502 //
b69ab31503 // +---- Insertion (rev 1)
b69ab31504 // | Line 1
b69ab31505 // | +-- Insertion (rev 2)
b69ab31506 // | | Line 2
b69ab31507 // +-|--
b69ab31508 // | Line 3
b69ab31509 // +--
b69ab31510 //
b69ab31511 // Similarly, interleaved deletions do not happen. However, insertions
b69ab31512 // might interleave with deletions, as shown above.
b69ab31513 //
b69ab31514 // Let's look at how this is done at the instruction level. First, look at
b69ab31515 // the instructions generated by editChunk:
b69ab31516 //
b69ab31517 // a2Pc: ...
b69ab31518 // ...
b69ab31519 // start: JL brev b2Pc
b69ab31520 // ...
b69ab31521 // b2Pc: JGE brev a2Pc
b69ab31522 // : <a1 Inst>
b69ab31523 // end: J a1Pc+1
b69ab31524 //
b69ab31525 // JL is used for insertion, JGE is used for deletion. We then use them to
b69ab31526 // manipulate the insStack and delStack:
b69ab31527 //
b69ab31528 // insStack:
b69ab31529 //
b69ab31530 // - On "start: JL brev b2Pc":
b69ab31531 // Do not follow the JL jump.
b69ab31532 // Push {rev, b2Pc} to insStack.
b69ab31533 // - When pc is b2Pc, pop insStack.
b69ab31534 //
b69ab31535 // delStack:
b69ab31536 //
b69ab31537 // - On "b2Pc: JGE brev a2Pc":
b69ab31538 // Do not follow the JGE jump.
b69ab31539 // Push {rev, a2Pc} to delStack.
b69ab31540 // - When pc is a2Pc, pop delStack.
b69ab31541 //
b69ab31542 // You might have noticed that we don't use the revs in LINE instructions
b69ab31543 // at all. This is because that LINE rev always matches its JL rev in this
b69ab31544 // implementation. In other words, the "rev" in LINE instruction is
b69ab31545 // redundant as it can be inferred from JL, with an insStack. Note in the
b69ab31546 // original C implementation of LineLog the LINE rev can be different from
b69ab31547 // the JL rev, to deal with merges while maintaining a linear history.
b69ab31548 const insStack: Frame[] = [{rev: 0, endPc: -1}];
b69ab31549 const delStack: Frame[] = [];
b69ab31550 const {onPc, onLine, onConditionalJump, onStackPush, onStackPop} = withContext(
b69ab31551 insStack,
b69ab31552 delStack,
b69ab31553 );
b69ab31554 let pc = 0;
b69ab31555 let patience = this.getSize() * 2;
b69ab31556 while (patience > 0) {
b69ab31557 onPc?.(pc);
b69ab31558 if (insStack.at(-1)?.endPc === pc) {
b69ab31559 insStack.pop();
b69ab31560 onStackPop?.(insStack);
b69ab31561 }
b69ab31562 if (delStack.at(-1)?.endPc === pc) {
b69ab31563 delStack.pop();
b69ab31564 onStackPop?.(delStack);
b69ab31565 }
b69ab31566 const code = nullthrows(this.get(pc));
b69ab31567 switch (code.op) {
b69ab31568 case Op.LINE:
b69ab31569 onLine?.(code);
b69ab31570 pc += 1;
b69ab31571 break;
b69ab31572 case Op.END:
b69ab31573 patience = -1;
b69ab31574 break;
b69ab31575 case Op.J:
b69ab31576 pc = code.pc;
b69ab31577 break;
b69ab31578 case Op.JGE:
b69ab31579 onConditionalJump?.(code);
b69ab31580 delStack.push({rev: code.rev, endPc: code.pc});
b69ab31581 onStackPush?.(delStack);
b69ab31582 pc += 1;
b69ab31583 break;
b69ab31584 case Op.JL:
b69ab31585 onConditionalJump?.(code);
b69ab31586 insStack.push({rev: code.rev, endPc: code.pc});
b69ab31587 onStackPush?.(insStack);
b69ab31588 pc += 1;
b69ab31589 break;
b69ab31590 default:
b69ab31591 assert(false, 'bug: unknown code');
b69ab31592 }
b69ab31593 patience -= 1;
b69ab31594 }
b69ab31595 if (patience === 0) {
b69ab31596 assert(false, 'bug: code does not end in time');
b69ab31597 }
b69ab31598 }
b69ab31599
b69ab31600 remapRevs(revMapOrFunc: Map<Rev, Rev> | ((rev: Rev) => Rev)): [Code, Rev] {
b69ab31601 let revMap = new Map<Rev, Rev>();
b69ab31602 if (typeof revMapOrFunc === 'function') {
b69ab31603 this.instList.forEach(inst => {
b69ab31604 const rev = (inst as RecordOf<{rev?: number}>).rev;
b69ab31605 if (rev != null && !revMap.has(rev)) {
b69ab31606 revMap.set(rev, revMapOrFunc(rev));
b69ab31607 }
b69ab31608 });
b69ab31609 } else {
b69ab31610 revMap = revMapOrFunc;
b69ab31611 }
b69ab31612
b69ab31613 const valueOfString = [...revMap.entries()].toString();
b69ab31614 return this.rewriteInsts((c, _pc) => {
b69ab31615 if (c.op === Op.JGE || c.op === Op.JL || c.op === Op.LINE) {
b69ab31616 const newRev = revMap.get(c.rev) ?? c.rev;
b69ab31617 // TypeScript cannot prove `c` has `rev`. Ideally it can figure out it automatically.
b69ab31618 return (c as RecordOf<{rev: number}>).set('rev', newRev) as Inst;
b69ab31619 }
b69ab31620 return c;
b69ab31621 }, valueOfString);
b69ab31622 }
b69ab31623
b69ab31624 /**
b69ab31625 * Rewrite all instructions. Returns [newCode, newMaxRev].
b69ab31626 * `valueOfString` sets a unique string that represents the change for equal tests.
b69ab31627 */
b69ab31628 rewriteInsts(func: (inst: Inst, pc: Pc) => Inst, valueOfString?: string): [Code, Rev] {
b69ab31629 let newMaxRev = 0;
b69ab31630 const newInstList = this.instList
b69ab31631 .map((inst, pc) => {
b69ab31632 const newInst = func(inst, pc);
b69ab31633 const newRev = (newInst as RecordOf<{rev: number}>).rev;
b69ab31634 if (newRev != null && newRev > newMaxRev) {
b69ab31635 newMaxRev = newRev;
b69ab31636 }
b69ab31637 return newInst;
b69ab31638 })
b69ab31639 .toList();
b69ab31640 const newValueOf = `R${valueOfString ?? func}`;
b69ab31641 const newCode = this.newCode(newInstList, newValueOf);
b69ab31642 return [newCode, newMaxRev];
b69ab31643 }
b69ab31644
b69ab31645 /**
b69ab31646 * Drop edits for revs >= the given rev. Returns [newCode, newMaxRev].
b69ab31647 */
b69ab31648 truncate(rev: Rev): [Code, Rev] {
b69ab31649 const valueOfString = `TRUNC${rev}`;
b69ab31650 return this.rewriteInsts((inst, pc) => {
b69ab31651 if (inst.op === Op.JGE || inst.op === Op.LINE) {
b69ab31652 if (inst.rev >= rev) {
b69ab31653 // NOP.
b69ab31654 return J({pc: pc + 1}) as Inst;
b69ab31655 }
b69ab31656 } else if (inst.op === Op.JL) {
b69ab31657 if (inst.rev >= rev) {
b69ab31658 // Unconditional jump.
b69ab31659 return J({pc: inst.pc}) as Inst;
b69ab31660 }
b69ab31661 }
b69ab31662 return inst;
b69ab31663 }, valueOfString);
b69ab31664 }
b69ab31665
b69ab31666 private newCode(instList: List<Inst>, newValueOf: string): Code {
b69ab31667 const newStr = this.__valueOf + '\0' + newValueOf;
b69ab31668 // We want bitwise operations.
b69ab31669 // eslint-disable-next-line no-bitwise
b69ab31670 const newHash = (this.__hash * 23 + hash(newValueOf)) & 0x7fffffff;
b69ab31671 return new Code(instList, newHash, newStr);
b69ab31672 }
b69ab31673}
b69ab31674
b69ab31675// Export for testing purpose.
b69ab31676export const executeCache: LRUWithStats = new LRU(1000);
b69ab31677const calculateDepCache: LRUWithStats = new LRU(1000);
b69ab31678const flattenCache: LRUWithStats = new LRU(1000);
b69ab31679const recordTextCache: LRUWithStats = new LRU(1000);
b69ab31680
b69ab31681type LineLogProps = {
b69ab31682 /** Core state: instructions. The array index type is `Pc`. */
b69ab31683 code: Code;
b69ab31684 /** Maximum rev tracked (inclusive). */
b69ab31685 maxRev: Rev;
b69ab31686};
b69ab31687
b69ab31688const LineLogRecord = Record<LineLogProps>({
b69ab31689 code: new Code(),
b69ab31690 maxRev: 0 as Rev,
b69ab31691});
b69ab31692type LineLogRecord = RecordOf<LineLogProps>;
b69ab31693
b69ab31694/**
b69ab31695 * `LineLog` is a data structure that tracks linear changes to a single text
b69ab31696 * file. Conceptually similar to a list of texts like `string[]`, with extra
b69ab31697 * features suitable for stack editing:
b69ab31698 * - Calculate the "blame" of the text of a given version efficiently.
b69ab31699 * - Edit lines or trunks in a past version, and affect future versions.
b69ab31700 * - List all lines that ever existed with each line annotated, like
b69ab31701 * a unified diff, but for all versions, not just 2 versions.
b69ab31702 *
b69ab31703 * Internally, `LineLog` is a byte-code interpreter that runs a program to
b69ab31704 * emit lines. Changes are done by patching in new byte-codes. There are
b69ab31705 * no traditional text patch involved. No operations would cause merge
b69ab31706 * conflicts. See https://sapling-scm.com/docs/internals/linelog for more
b69ab31707 * details.
b69ab31708 *
b69ab31709 * This implementation of `LineLog` uses immutable patterns.
b69ab31710 * Write operations return new `LineLog`s.
b69ab31711 */
b69ab31712class LineLog extends SelfUpdate<LineLogRecord> {
b69ab31713 constructor(props?: {code?: Code; maxRev?: Rev}) {
b69ab31714 const record = LineLogRecord(props);
b69ab31715 super(record);
b69ab31716 }
b69ab31717
b69ab31718 get maxRev(): Rev {
b69ab31719 return this.inner.maxRev;
b69ab31720 }
b69ab31721
b69ab31722 get code(): Code {
b69ab31723 return this.inner.code;
b69ab31724 }
b69ab31725
b69ab31726 /**
b69ab31727 * Edit chunk. Replace line `a1` (inclusive) to `a2` (exclusive) in rev
b69ab31728 * `aRev` with `bLines`. `bLines` are considered introduced by `bRev`.
b69ab31729 * If `bLines` is empty, the edit is a deletion. If `a1` equals to `a2`,
b69ab31730 * the edit is an insertion. Otherwise, the edit is a modification.
b69ab31731 *
b69ab31732 * While this function does not cause conflicts or error out, not all
b69ab31733 * editings make practical sense. The callsite might want to do some
b69ab31734 * extra checks to ensure the edit is meaningful.
b69ab31735 *
b69ab31736 * `aLinesCache` is optional. If provided, then `editChunk` will skip a
b69ab31737 * `checkOutLines` call and modify `aLinesCache` *in place* to reflect
b69ab31738 * the edit. It is used by `recordText`.
b69ab31739 *
b69ab31740 * If `blockShift` is `true`, consider shifting the insertion lines
b69ab31741 * to relax dependency for easier reordering. Check the comments
b69ab31742 * in this function for details.
b69ab31743 */
b69ab31744 editChunk(
b69ab31745 aRev: Rev,
b69ab31746 a1: LineIdx,
b69ab31747 a2: LineIdx,
b69ab31748 bRev: Rev,
b69ab31749 bLines: string[],
b69ab31750 aLinesCache?: LineInfo[],
b69ab31751 blockShift = true,
b69ab31752 ): LineLog {
b69ab31753 const aLinesMutable = aLinesCache != null;
b69ab31754 const aLinesInfo: [LineInfo[], true] | [Readonly<LineInfo[]>, false] = aLinesMutable
b69ab31755 ? [aLinesCache, true]
b69ab31756 : [this.checkOutLines(aRev), false];
b69ab31757
b69ab31758 const bLen = bLines.length;
b69ab31759 if (a1 === a2 && bLen > 0 && blockShift) {
b69ab31760 // Attempt to shift the insertion chunk so the start of insertion aligns
b69ab31761 // with another "start insertion". This might trigger the [OPT1]
b69ab31762 // optimization in `code.editChunk`, avoid nested insertions and enable
b69ab31763 // more flexible reordering.
b69ab31764 //
b69ab31765 // For example, we might get "Insert (rev 3)" below that forces a nested
b69ab31766 // insertion block. However, if we shift the block and use the
b69ab31767 // "Alternative Insert (rev 3)", we can use the [OPT1] optimization.
b69ab31768 //
b69ab31769 // +----Insert (rev 1)
b69ab31770 // | Line: function a () {
b69ab31771 // | Line: return 'a';
b69ab31772 // | Line: }
b69ab31773 // +----
b69ab31774 // +----Insert (rev 2)
b69ab31775 // | ----+ Alternative Insert (rev 3)
b69ab31776 // | Line: |
b69ab31777 // |+---Insert (rev 3) |
b69ab31778 // || Line: function b () { |
b69ab31779 // || Line: return 'b'; |
b69ab31780 // || Line: } |
b69ab31781 // || ----+
b69ab31782 // || Line:
b69ab31783 // |+---
b69ab31784 // | Line: function c () {
b69ab31785 // | Line: return 'c';
b69ab31786 // | Line: }
b69ab31787 // +----
b69ab31788 //
b69ab31789 // Block shifting works if the surrounding lines match, see:
b69ab31790 //
b69ab31791 // A A
b69ab31792 // B +-------+
b69ab31793 // +-------+ is equivalent to | B |
b69ab31794 // | block | === shift up ==> | block |
b69ab31795 // | B | <== shift down === +-------+
b69ab31796 // +-------+ B
b69ab31797 // C C
b69ab31798
b69ab31799 const aLines: Readonly<LineInfo[]> = aLinesInfo[0];
b69ab31800 const canUseOpt1 = (a: LineIdx): boolean => {
b69ab31801 const pc = aLines.at(a)?.pc;
b69ab31802 // Check [OPT1] for how this works.
b69ab31803 return pc != null && pc > 0 && this.code.get(pc - 1)?.op === Op.JL;
b69ab31804 };
b69ab31805 if (!canUseOpt1(a1)) {
b69ab31806 const considerShift = (step: 'down' | 'up'): LineLog | undefined => {
b69ab31807 let ai = a1;
b69ab31808 let lines = [...bLines];
b69ab31809 // Limit overhead.
b69ab31810 const threshold = 10;
b69ab31811 for (let i = 0; i < threshold; ++i) {
b69ab31812 // Out of range?
b69ab31813 if (step === 'up' ? ai === 0 : ai === aLines.length - 1) {
b69ab31814 return undefined;
b69ab31815 }
b69ab31816 // Surrounding lines match?
b69ab31817 const [aIdx, bIdx] = step === 'up' ? [ai - 1, -1] : [ai, 0];
b69ab31818 const aData = aLines.at(aIdx)?.data;
b69ab31819 const bData = lines.at(bIdx);
b69ab31820 if (bData !== aData || bData == null) {
b69ab31821 return undefined;
b69ab31822 }
b69ab31823 // Shift.
b69ab31824 lines =
b69ab31825 step === 'up' ? [bData].concat(lines.slice(0, -1)) : lines.slice(1).concat([bData]);
b69ab31826 ai += step === 'up' ? -1 : 1;
b69ab31827 // Good enough?
b69ab31828 if (canUseOpt1(ai)) {
b69ab31829 return this.editChunk(aRev, ai, ai, bRev, lines, aLinesCache, false);
b69ab31830 }
b69ab31831 }
b69ab31832 };
b69ab31833 const maybeShifted = considerShift('up') ?? considerShift('down');
b69ab31834 if (maybeShifted != null) {
b69ab31835 return maybeShifted;
b69ab31836 }
b69ab31837 }
b69ab31838 }
b69ab31839 const newCode = this.code.editChunk(aRev, a1, a2, bRev, bLines, aLinesInfo);
b69ab31840 const newMaxRev = Math.max(bRev, this.maxRev);
b69ab31841 return new LineLog({code: newCode, maxRev: newMaxRev});
b69ab31842 }
b69ab31843
b69ab31844 /**
b69ab31845 * Rewrite `rev` to `mapping[rev] ?? rev`.
b69ab31846 * This can be useful for reordering, folding, or insertion.
b69ab31847 *
b69ab31848 * Note: There are no checks about whether the reordering is
b69ab31849 * meaningful or not. The callsite is responsible to perform
b69ab31850 * a dependency check and avoid troublesome reorders like
b69ab31851 * moving a change to before its dependency.
b69ab31852 */
b69ab31853 remapRevs(revMap: Map<Rev, Rev> | ((rev: Rev) => Rev)): LineLog {
b69ab31854 const [newCode, newMaxRev] = this.code.remapRevs(revMap);
b69ab31855 return new LineLog({code: newCode, maxRev: newMaxRev});
b69ab31856 }
b69ab31857
b69ab31858 /**
b69ab31859 * Truncate linelog. Drop rev (inclusive) and higher revs.
b69ab31860 */
b69ab31861 truncate(rev: Rev): LineLog {
b69ab31862 const [newCode, newMaxRev] = this.code.truncate(rev);
b69ab31863 return new LineLog({code: newCode, maxRev: newMaxRev});
b69ab31864 }
b69ab31865
b69ab31866 /**
b69ab31867 * Calculate the dependencies of revisions.
b69ab31868 * For example, `{5: [3, 1]}` means rev 5 depends on rev 3 and rev 1.
b69ab31869 *
b69ab31870 * Based on LineLog, which could be different from traditional textual
b69ab31871 * context-line dependencies. LineLog dependency is to prevent
b69ab31872 * "malformed cases" [1] when following the dependency to `remapRevs`.
b69ab31873 * Practically, LineLog might allow reorder cases that would be
b69ab31874 * disallowed by traditional context-line dependencies. See tests
b69ab31875 * for examples.
b69ab31876 *
b69ab31877 * [1]: Malformed cases are when nested blocks (insertions or deletions)
b69ab31878 * might be skipped incorrectly. The outer block says "skip" and the
b69ab31879 * inner block does not want to "skip" but is still skipped since it
b69ab31880 * is skipped altogether with the outer block. See also section 0.4
b69ab31881 * and 0.5 in D3628440.
b69ab31882 */
b69ab31883 public calculateDepMap = cachedMethod(this.calculateDepMapImpl, {cache: calculateDepCache});
b69ab31884
b69ab31885 private calculateDepMapImpl(): Readonly<Map<Rev, Set<Rev>>> {
b69ab31886 // With the insertion and deletion stacks (see explanation in
b69ab31887 // visitWithInsDelStacks), when we see a new insertion block, or deletion
b69ab31888 // block, we add two dependencies:
b69ab31889 // - The inner rev depends on the outer insertion rev.
b69ab31890 // - The outer deletion rev (if present) depends on the inner rev.
b69ab31891 //
b69ab31892 // Let's look at how this is done at the instruction level.
b69ab31893 // the instructions generated by editChunk:
b69ab31894 //
b69ab31895 // a2Pc: ...
b69ab31896 // ...
b69ab31897 // start: JL brev b2Pc
b69ab31898 // ...
b69ab31899 // b2Pc: JGE brev a2Pc
b69ab31900 // : <a1 Inst>
b69ab31901 // end: J a1Pc+1
b69ab31902 //
b69ab31903 // JL is used for insertion, JGE is used for deletion. We then use them to
b69ab31904 // manipulate the insStack and delStack:
b69ab31905 //
b69ab31906 // insStack:
b69ab31907 //
b69ab31908 // - On "start: JL brev b2Pc":
b69ab31909 // Do not follow the JL jump. (by visitWithInsDelStacks)
b69ab31910 // Mark brev as dependent on the outer insertion.
b69ab31911 // Mark the outer deletion as dependent on this brev.
b69ab31912 // Push {rev, b2Pc} to insStack. (by visitWithInsDelStacks)
b69ab31913 // - When pc is b2Pc, pop insStack. (by visitWithInsDelStacks)
b69ab31914 //
b69ab31915 // delStack:
b69ab31916 //
b69ab31917 // - On "b2Pc: JGE brev a2Pc":
b69ab31918 // Do not follow the JGE jump. (by visitWithInsDelStacks)
b69ab31919 // Mark brev as dependent on the outer insertion.
b69ab31920 // Mark the outer deletion as dependent on this brev.
b69ab31921 // Push {rev, a2Pc} to delStack. (by visitWithInsDelStacks)
b69ab31922 // - When pc is a2Pc, pop delStack. (by visitWithInsDelStacks)
b69ab31923 const depMap = new Map<Rev, Set<Rev>>();
b69ab31924 const addDep = (child: Rev, parent: Rev) => {
b69ab31925 if (child > parent) {
b69ab31926 if (!depMap.has(child)) {
b69ab31927 depMap.set(child, new Set());
b69ab31928 }
b69ab31929 depMap.get(child)?.add(parent);
b69ab31930 }
b69ab31931 };
b69ab31932 this.code.visitWithInsDelStacks((insStack, delStack) => {
b69ab31933 const markDep = (rev: Rev) => {
b69ab31934 const ins = insStack.at(-1);
b69ab31935 if (ins !== undefined) {
b69ab31936 addDep(rev, ins.rev);
b69ab31937 }
b69ab31938 const del = delStack.at(-1);
b69ab31939 if (del !== undefined) {
b69ab31940 addDep(del.rev, rev);
b69ab31941 }
b69ab31942 };
b69ab31943 return {
b69ab31944 onConditionalJump: inst => markDep(inst.rev),
b69ab31945 };
b69ab31946 });
b69ab31947 return depMap;
b69ab31948 }
b69ab31949
b69ab31950 /**
b69ab31951 * Interpret the bytecodes with the given revision range.
b69ab31952 * Used by `checkOut`.
b69ab31953 */
b69ab31954 public execute = cachedMethod(this.executeImpl, {cache: executeCache});
b69ab31955
b69ab31956 private executeImpl(
b69ab31957 startRev: Rev,
b69ab31958 endRev: Rev = startRev,
b69ab31959 present?: {[pc: number]: boolean},
b69ab31960 ): Readonly<LineInfo[]> {
b69ab31961 const rev = endRev;
b69ab31962 const lines: LineInfo[] = [];
b69ab31963 let pc = 0;
b69ab31964 let patience = this.code.getSize() * 2;
b69ab31965 const deleted = present == null ? () => false : (pc: Pc) => !present[pc];
b69ab31966 while (patience > 0) {
b69ab31967 const code = nullthrows(this.code.get(pc));
b69ab31968 switch (code.op) {
b69ab31969 case Op.END:
b69ab31970 lines.push({data: '', rev: 0, pc, deleted: deleted(pc)});
b69ab31971 patience = -1;
b69ab31972 break;
b69ab31973 case Op.LINE:
b69ab31974 lines.push({data: code.data, rev: code.rev, pc, deleted: deleted(pc)});
b69ab31975 pc += 1;
b69ab31976 break;
b69ab31977 case Op.J:
b69ab31978 pc = code.pc;
b69ab31979 break;
b69ab31980 case Op.JGE:
b69ab31981 if (startRev >= code.rev) {
b69ab31982 pc = code.pc;
b69ab31983 } else {
b69ab31984 pc += 1;
b69ab31985 }
b69ab31986 break;
b69ab31987 case Op.JL:
b69ab31988 if (rev < code.rev) {
b69ab31989 pc = code.pc;
b69ab31990 } else {
b69ab31991 pc += 1;
b69ab31992 }
b69ab31993 break;
b69ab31994 default:
b69ab31995 assert(false, 'bug: unknown code');
b69ab31996 }
b69ab31997 patience -= 1;
b69ab31998 }
b69ab31999 if (patience === 0) {
b69ab311000 assert(false, 'bug: code does not end in time');
b69ab311001 }
b69ab311002 return lines;
b69ab311003 }
b69ab311004
b69ab311005 /**
b69ab311006 * Flatten lines. Each returned line is associated with a set
b69ab311007 * of `Rev`s, meaning that line is present in those `Rev`s.
b69ab311008 *
b69ab311009 * The returned lines can be useful to figure out file contents
b69ab311010 * after reordering, folding commits. It can also provide a view
b69ab311011 * similar to `absorb -e FILE` to edit all versions of a file in
b69ab311012 * a single view.
b69ab311013 */
b69ab311014 public flatten = cachedMethod(this.flattenImpl, {cache: flattenCache});
b69ab311015
b69ab311016 private flattenImpl(): List<FlattenLine> {
b69ab311017 const result: FlattenLine[] = [];
b69ab311018
b69ab311019 // See the comments in calculateDepMap for what the stacks mean.
b69ab311020 //
b69ab311021 // The flatten algorithm works as follows:
b69ab311022 // - For each line, we got an insRev (insStack.at(-1).rev), and a
b69ab311023 // delRev (delStack.at(-1)?.rev ?? maxRev + 1), meaning the rev
b69ab311024 // attached to the innermost insertion or deletion blocks,
b69ab311025 // respectively.
b69ab311026 // - That line is then present in insRev .. delRev (exclusive) revs.
b69ab311027 //
b69ab311028 // This works because:
b69ab311029 // - The blocks are nested in order:
b69ab311030 // - For nested insertions, the nested one must have a larger rev, and
b69ab311031 // lines inside the nested block are only present starting from the
b69ab311032 // larger rev.
b69ab311033 // - For nested deletions, the nested one must have a smaller rev, and
b69ab311034 // lines inside the nested block are considered as deleted by the
b69ab311035 // smaller rev.
b69ab311036 // - For interleaved insertion and deletions, insertion rev and deletion
b69ab311037 // rev are tracked separately so their calculations are independent
b69ab311038 // from each other.
b69ab311039 // - Linelog tracks linear history, so (insRev, delRev) can be converted to
b69ab311040 // a Set<Rev>.
b69ab311041 this.code.visitWithInsDelStacks((insStack, delStack) => {
b69ab311042 const maxDelRev = this.maxRev + 1;
b69ab311043 const getCurrentRevs = (): ImSet<Rev> => {
b69ab311044 const insRev = insStack.at(-1)?.rev ?? 0;
b69ab311045 const delRev = delStack.at(-1)?.rev ?? maxDelRev;
b69ab311046 return revRangeToSet(insRev, delRev);
b69ab311047 };
b69ab311048 let currentRevs = getCurrentRevs();
b69ab311049 return {
b69ab311050 onStackPush: () => {
b69ab311051 currentRevs = getCurrentRevs();
b69ab311052 },
b69ab311053 onStackPop: () => {
b69ab311054 currentRevs = getCurrentRevs();
b69ab311055 },
b69ab311056 onLine: ({data}) => {
b69ab311057 result.push(FlattenLine({data, revs: currentRevs}));
b69ab311058 },
b69ab311059 };
b69ab311060 });
b69ab311061 return List(result);
b69ab311062 }
b69ab311063
b69ab311064 /**
b69ab311065 * Checkout the lines of the given revision `rev`.
b69ab311066 *
b69ab311067 * If `start` is not `null`, checkout a revision range. For example,
b69ab311068 * if `start` is 0, and `rev` is `this.maxRev`, `this.lines` will
b69ab311069 * include all lines ever existed in all revisions.
b69ab311070 *
b69ab311071 * @returns Content of the specified revision.
b69ab311072 */
b69ab311073 public checkOutLines(rev: Rev, start: Rev | null = null): Readonly<LineInfo[]> {
b69ab311074 // eslint-disable-next-line no-param-reassign
b69ab311075 rev = Math.min(rev, this.maxRev);
b69ab311076 let lines = this.execute(rev);
b69ab311077 if (start !== null) {
b69ab311078 // Checkout a range, including deleted revs.
b69ab311079 const present: {[key: number]: boolean} = {};
b69ab311080 lines.forEach(l => {
b69ab311081 present[l.pc] = true;
b69ab311082 });
b69ab311083
b69ab311084 // Go through all lines again. But do not skip chunks.
b69ab311085 lines = this.execute(start, rev, present);
b69ab311086 }
b69ab311087 return lines;
b69ab311088 }
b69ab311089
b69ab311090 /** Checkout the content of the given rev. */
b69ab311091 public checkOut(rev: Rev): string {
b69ab311092 const lines = this.checkOutLines(rev);
b69ab311093 const content = lines.map(l => l.data).join('');
b69ab311094 return content;
b69ab311095 }
b69ab311096
b69ab311097 /**
b69ab311098 * Edit LineLog to match the content of `text`.
b69ab311099 * This might affect `rev`s that are >= `rev` in the stack.
b69ab311100 * Previous revisions won't be affected.
b69ab311101 *
b69ab311102 * @param text Content to match.
b69ab311103 * @param rev Revision to to edit (in-place). If not set, append a new revision.
b69ab311104 * @returns A new `LineLog` with the change.
b69ab311105 */
b69ab311106 public recordText = cachedMethod(this.recordTextImpl, {cache: recordTextCache});
b69ab311107
b69ab311108 private recordTextImpl(text: string, rev: Rev | null = null): LineLog {
b69ab311109 // rev to edit from, and rev to match 'text'.
b69ab311110 const [aRev, bRev] = rev != null ? [rev, rev] : [this.maxRev, this.maxRev + 1];
b69ab311111 const b = text;
b69ab311112
b69ab311113 const aLineInfos = [...this.checkOutLines(aRev)];
b69ab311114 const bLines = splitLines(b);
b69ab311115 const aLines = aLineInfos.map(l => l.data);
b69ab311116 aLines.pop(); // Drop the last END empty line.
b69ab311117 const blocks = diffLines(aLines, bLines);
b69ab311118 // eslint-disable-next-line @typescript-eslint/no-this-alias
b69ab311119 let log: LineLog = this;
b69ab311120
b69ab311121 blocks.reverse().forEach(([a1, a2, b1, b2]) => {
b69ab311122 log = log.editChunk(aRev, a1, a2, bRev, bLines.slice(b1, b2), aLineInfos);
b69ab311123 });
b69ab311124
b69ab311125 // This is needed in case editChunk is not called (no difference).
b69ab311126 const newMaxRev = Math.max(bRev, log.maxRev);
b69ab311127
b69ab311128 // Populate cache for checking out bRev.
b69ab311129 const newLog = new LineLog({code: log.code, maxRev: newMaxRev});
b69ab311130 executeCache.set(List([newLog, bRev]), aLineInfos);
b69ab311131
b69ab311132 return newLog;
b69ab311133 }
b69ab311134}
b69ab311135
b69ab311136/** Turn (3, 6) to Set([3, 4, 5]). */
b69ab311137const revRangeToSet = cached(
b69ab311138 (startRev, endRev: Rev): ImSet<Rev> => {
b69ab311139 const result: Rev[] = [];
b69ab311140 for (let rev = startRev; rev < endRev; rev++) {
b69ab311141 result.push(rev);
b69ab311142 }
b69ab311143 return ImSet(result);
b69ab311144 },
b69ab311145 {cacheSize: 1000},
b69ab311146);
b69ab311147
b69ab311148function describeInst(inst: Inst): string {
b69ab311149 switch (inst.op) {
b69ab311150 case Op.J:
b69ab311151 return `J ${inst.pc}`;
b69ab311152 case Op.JGE:
b69ab311153 return `JGE ${inst.rev} ${inst.pc}`;
b69ab311154 case Op.JL:
b69ab311155 return `JL ${inst.rev} ${inst.pc}`;
b69ab311156 case Op.LINE:
b69ab311157 return `LINE ${inst.rev} ${JSON.stringify(inst.data.trimEnd())}`;
b69ab311158 case Op.END:
b69ab311159 return 'END';
b69ab311160 }
b69ab311161}
b69ab311162
b69ab311163export {FlattenLine, LineLog};
b69ab311164export type {LineIdx, LineInfo, Rev};