polygerrit-ui/app/embed/diff/gr-diff-processor/gr-diff-processor.ts

/**
 * @license
 * Copyright 2016 Google LLC
 * SPDX-License-Identifier: Apache-2.0
 */
import {GrDiffLine, Highlights} from '../gr-diff/gr-diff-line';
import {
  GrDiffGroup,
  GrDiffGroupType,
  hideInContextControl,
} from '../gr-diff/gr-diff-group';
import {DiffContent} from '../../../types/diff';
import {Side} from '../../../constants/constants';
import {debounce, DelayedTask} from '../../../utils/async-util';
import {assert} from '../../../utils/common-util';
import {getStringLength} from '../gr-diff-highlight/gr-annotation';
import {GrDiffLineType, LineNumber} from '../../../api/diff';
import {FULL_CONTEXT, KeyLocations} from '../gr-diff/gr-diff-utils';

// visible for testing
export interface State {
  lineNums: {
    left: number;
    right: number;
  };
  chunkIndex: number;
}

interface ChunkEnd {
  offset: number;
  keyLocation: boolean;
}

/**
 * The maximum size for an addition or removal chunk before it is broken down
 * into a series of chunks that are this size at most.
 *
 * Note: The value of 120 is chosen so that it is larger than the default
 * asyncThreshold of 64, but feel free to tune this constant to your
 * performance needs.
 */
function calcMaxGroupSize(asyncThreshold?: number): number {
  if (!asyncThreshold) return 120;
  return asyncThreshold * 2;
}

/** Interface for listening to the output of the processor. */
export interface GroupConsumer {
  addGroup(group: GrDiffGroup): void;
  clearGroups(): void;
}

/** Interface for listening to the output of the processor. */
export interface ProcessingOptions {
  context: number;
  keyLocations?: KeyLocations;
  asyncThreshold?: number;
  isBinary?: boolean;
}

/**
 * Converts the API's `DiffContent`s  to `GrDiffGroup`s for rendering.
 *
 * Glossary:
 * - "chunk": A single `DiffContent` as returned by the API.
 * - "group": A single `GrDiffGroup` as used for rendering.
 * - "common" chunk/group: A chunk/group that should be considered unchanged
 *   for diffing purposes. This can mean its either actually unchanged, or it
 *   has only whitespace changes.
 * - "key location": A line number and side of the diff that should not be
 *   collapsed e.g. because a comment is attached to it, or because it was
 *   provided in the URL and thus should be visible
 * - "uncollapsible" chunk/group: A chunk/group that is either not "common",
 *   or cannot be collapsed because it contains a key location
 *
 * Here a a number of tasks this processor performs:
 *  - splitting large chunks to allow more granular async rendering
 *  - adding a group for the "File" pseudo line that file-level comments can
 *    be attached to
 *  - replacing common parts of the diff that are outside the user's
 *    context setting and do not have comments with a group representing the
 *    "expand context" widget. This may require splitting a chunk/group so
 *    that the part that is within the context or has comments is shown, while
 *    the rest is not.
 */
export class GrDiffProcessor {
  // visible for testing
  context: number;

  // visible for testing
  keyLocations: KeyLocations;

  private asyncThreshold: number;

  private isBinary: boolean;

  // visible for testing
  isScrolling?: boolean;

  /** Just for making sure that process() is only called once. */
  private isStarted = false;

  /** Indicates that processing should be stopped. */
  private isCancelled = false;

  private resetIsScrollingTask?: DelayedTask;

  private readonly groups: GrDiffGroup[] = [];

  constructor(options: ProcessingOptions) {
    this.context = options.context;
    this.asyncThreshold = options.asyncThreshold ?? 64;
    this.keyLocations = options.keyLocations ?? {left: {}, right: {}};
    this.isBinary = options.isBinary ?? false;
  }

  private readonly handleWindowScroll = () => {
    this.isScrolling = true;
    this.resetIsScrollingTask = debounce(
      this.resetIsScrollingTask,
      () => (this.isScrolling = false),
      50
    );
  };

  /**
   * Asynchronously process the diff chunks into groups. As it processes, it
   * will splice groups into the `groups` property of the component.
   *
   * @return A promise that resolves with an
   * array of GrDiffGroups when the diff is completely processed.
   */
  async process(chunks: DiffContent[]): Promise<GrDiffGroup[]> {
    assert(this.isStarted === false, 'diff processor cannot be started twice');

    window.addEventListener('scroll', this.handleWindowScroll);

    this.groups.push(this.makeGroup('LOST'));
    this.groups.push(this.makeGroup('FILE'));

    if (this.isBinary) return this.groups;
    try {
      await this.processChunks(chunks);
    } finally {
      this.finish();
    }
    return this.groups;
  }

  finish() {
    window.removeEventListener('scroll', this.handleWindowScroll);
  }

  cancel() {
    this.isCancelled = true;
    this.finish();
  }

  async processChunks(chunks: DiffContent[]) {
    let completed = () => {};
    const promise = new Promise<void>(resolve => (completed = resolve));

    const state = {
      lineNums: {left: 0, right: 0},
      chunkIndex: 0,
    };

    chunks = this.splitLargeChunks(chunks);
    chunks = this.splitCommonChunksWithKeyLocations(chunks);

    let currentBatch = 0;
    const nextStep = () => {
      if (this.isCancelled || state.chunkIndex >= chunks.length) {
        completed();
        return;
      }
      if (this.isScrolling) {
        window.setTimeout(nextStep, 100);
        return;
      }

      const stateUpdate = this.processNext(state, chunks);
      for (const group of stateUpdate.groups) {
        this.groups.push(group);
        currentBatch += group.lines.length;
      }
      state.lineNums.left += stateUpdate.lineDelta.left;
      state.lineNums.right += stateUpdate.lineDelta.right;

      state.chunkIndex = stateUpdate.newChunkIndex;
      if (currentBatch >= this.asyncThreshold) {
        currentBatch = 0;
        window.setTimeout(nextStep, 1);
      } else {
        nextStep.call(this);
      }
    };

    nextStep.call(this);
    await promise;
  }

  /**
   * Process the next uncollapsible chunk, or the next collapsible chunks.
   */
  // visible for testing
  processNext(state: State, chunks: DiffContent[]) {
    const firstUncollapsibleChunkIndex = this.firstUncollapsibleChunkIndex(
      chunks,
      state.chunkIndex
    );
    if (firstUncollapsibleChunkIndex === state.chunkIndex) {
      const chunk = chunks[state.chunkIndex];
      return {
        lineDelta: {
          left: this.linesLeft(chunk).length,
          right: this.linesRight(chunk).length,
        },
        groups: [
          this.chunkToGroup(
            chunk,
            state.lineNums.left + 1,
            state.lineNums.right + 1
          ),
        ],
        newChunkIndex: state.chunkIndex + 1,
      };
    }

    return this.processCollapsibleChunks(
      state,
      chunks,
      firstUncollapsibleChunkIndex
    );
  }

  private linesLeft(chunk: DiffContent) {
    return chunk.ab || chunk.a || [];
  }

  private linesRight(chunk: DiffContent) {
    return chunk.ab || chunk.b || [];
  }

  private firstUncollapsibleChunkIndex(chunks: DiffContent[], offset: number) {
    let chunkIndex = offset;
    while (
      chunkIndex < chunks.length &&
      this.isCollapsibleChunk(chunks[chunkIndex])
    ) {
      chunkIndex++;
    }
    return chunkIndex;
  }

  private isCollapsibleChunk(chunk: DiffContent) {
    return (chunk.ab || chunk.common || chunk.skip) && !chunk.keyLocation;
  }

  /**
   * Process a stretch of collapsible chunks.
   *
   * Outputs up to three groups:
   * 1) Visible context before the hidden common code, unless it's the
   * very beginning of the file.
   * 2) Context hidden behind a context bar, unless empty.
   * 3) Visible context after the hidden common code, unless it's the very
   * end of the file.
   */
  private processCollapsibleChunks(
    state: State,
    chunks: DiffContent[],
    firstUncollapsibleChunkIndex: number
  ) {
    const collapsibleChunks = chunks.slice(
      state.chunkIndex,
      firstUncollapsibleChunkIndex
    );
    const lineCount = collapsibleChunks.reduce(
      (sum, chunk) => sum + this.commonChunkLength(chunk),
      0
    );

    let groups = this.chunksToGroups(
      collapsibleChunks,
      state.lineNums.left + 1,
      state.lineNums.right + 1
    );

    const hasSkippedGroup = !!groups.find(g => g.skip);
    if (this.context !== FULL_CONTEXT || hasSkippedGroup) {
      const contextNumLines = this.context > 0 ? this.context : 0;
      const hiddenStart = state.chunkIndex === 0 ? 0 : contextNumLines;
      const hiddenEnd =
        lineCount -
        (firstUncollapsibleChunkIndex === chunks.length ? 0 : this.context);
      groups = hideInContextControl(groups, hiddenStart, hiddenEnd);
    }

    return {
      lineDelta: {
        left: lineCount,
        right: lineCount,
      },
      groups,
      newChunkIndex: firstUncollapsibleChunkIndex,
    };
  }

  private commonChunkLength(chunk: DiffContent) {
    if (chunk.skip) {
      return chunk.skip;
    }
    console.assert(!!chunk.ab || !!chunk.common);

    console.assert(
      !chunk.a || (!!chunk.b && chunk.a.length === chunk.b.length),
      'common chunk needs same number of a and b lines: ',
      chunk
    );
    return this.linesLeft(chunk).length;
  }

  private chunksToGroups(
    chunks: DiffContent[],
    offsetLeft: number,
    offsetRight: number
  ): GrDiffGroup[] {
    return chunks.map(chunk => {
      const group = this.chunkToGroup(chunk, offsetLeft, offsetRight);
      const chunkLength = this.commonChunkLength(chunk);
      offsetLeft += chunkLength;
      offsetRight += chunkLength;
      return group;
    });
  }

  private chunkToGroup(
    chunk: DiffContent,
    offsetLeft: number,
    offsetRight: number
  ): GrDiffGroup {
    const type =
      chunk.ab || chunk.skip ? GrDiffGroupType.BOTH : GrDiffGroupType.DELTA;
    const lines = this.linesFromChunk(chunk, offsetLeft, offsetRight);
    const options = {
      moveDetails: chunk.move_details,
      dueToRebase: !!chunk.due_to_rebase,
      ignoredWhitespaceOnly: !!chunk.common,
      keyLocation: !!chunk.keyLocation,
    };
    if (chunk.skip !== undefined) {
      return new GrDiffGroup({
        type,
        skip: chunk.skip,
        offsetLeft,
        offsetRight,
        ...options,
      });
    } else {
      return new GrDiffGroup({
        type,
        lines,
        ...options,
      });
    }
  }

  private linesFromChunk(
    chunk: DiffContent,
    offsetLeft: number,
    offsetRight: number
  ) {
    if (chunk.ab) {
      return chunk.ab.map((row, i) =>
        this.lineFromRow(GrDiffLineType.BOTH, offsetLeft, offsetRight, row, i)
      );
    }
    let lines: GrDiffLine[] = [];
    if (chunk.a) {
      // Avoiding a.push(...b) because that causes callstack overflows for
      // large b, which can occur when large files are added removed.
      lines = lines.concat(
        this.linesFromRows(
          GrDiffLineType.REMOVE,
          chunk.a,
          offsetLeft,
          chunk.edit_a
        )
      );
    }
    if (chunk.b) {
      // Avoiding a.push(...b) because that causes callstack overflows for
      // large b, which can occur when large files are added removed.
      lines = lines.concat(
        this.linesFromRows(
          GrDiffLineType.ADD,
          chunk.b,
          offsetRight,
          chunk.edit_b
        )
      );
    }
    return lines;
  }

  // visible for testing
  linesFromRows(
    lineType: GrDiffLineType,
    rows: string[],
    offset: number,
    intralineInfos?: number[][]
  ): GrDiffLine[] {
    const grDiffHighlights = intralineInfos
      ? this.convertIntralineInfos(rows, intralineInfos)
      : undefined;
    return rows.map((row, i) =>
      this.lineFromRow(lineType, offset, offset, row, i, grDiffHighlights)
    );
  }

  private lineFromRow(
    type: GrDiffLineType,
    offsetLeft: number,
    offsetRight: number,
    row: string,
    i: number,
    highlights?: Highlights[]
  ): GrDiffLine {
    const line = new GrDiffLine(type);
    line.text = row;
    if (type !== GrDiffLineType.ADD) line.beforeNumber = offsetLeft + i;
    if (type !== GrDiffLineType.REMOVE) line.afterNumber = offsetRight + i;
    if (highlights) {
      line.hasIntralineInfo = true;
      line.highlights = highlights.filter(hl => hl.contentIndex === i);
    } else {
      line.hasIntralineInfo = false;
    }
    return line;
  }

  private makeGroup(number: LineNumber) {
    const line = new GrDiffLine(GrDiffLineType.BOTH);
    line.beforeNumber = number;
    line.afterNumber = number;
    return new GrDiffGroup({type: GrDiffGroupType.BOTH, lines: [line]});
  }

  /**
   * Split chunks into smaller chunks of the same kind.
   *
   * This is done to prevent doing too much work on the main thread in one
   * uninterrupted rendering step, which would make the browser unresponsive.
   *
   * Note that in the case of unmodified chunks, we only split chunks if the
   * context is set to file (because otherwise they are split up further down
   * the processing into the visible and hidden context), and only split it
   * into 2 chunks, one max sized one and the rest (for reasons that are
   * unclear to me).
   *
   * @param chunks Chunks as returned from the server
   * @return Finer grained chunks.
   */
  // visible for testing
  splitLargeChunks(chunks: DiffContent[]): DiffContent[] {
    const newChunks = [];

    for (const chunk of chunks) {
      if (!chunk.ab) {
        for (const subChunk of this.breakdownChunk(chunk)) {
          newChunks.push(subChunk);
        }
        continue;
      }

      // If the context is set to "whole file", then break down the shared
      // chunks so they can be rendered incrementally. Note: this is not
      // enabled for any other context preference because manipulating the
      // chunks in this way violates assumptions by the context grouper logic.
      const MAX_GROUP_SIZE = calcMaxGroupSize(this.asyncThreshold);
      if (
        this.context === FULL_CONTEXT &&
        chunk.ab.length > MAX_GROUP_SIZE * 2
      ) {
        // Split large shared chunks in two, where the first is the maximum
        // group size.
        newChunks.push({ab: chunk.ab.slice(0, MAX_GROUP_SIZE)});
        newChunks.push({ab: chunk.ab.slice(MAX_GROUP_SIZE)});
      } else {
        newChunks.push(chunk);
      }
    }
    return newChunks;
  }

  /**
   * In order to show key locations, such as comments, out of the bounds of
   * the selected context, treat them as separate chunks within the model so
   * that the content (and context surrounding it) renders correctly.
   *
   * @param chunks DiffContents as returned from server.
   * @return Finer grained DiffContents.
   */
  // visible for testing
  splitCommonChunksWithKeyLocations(chunks: DiffContent[]): DiffContent[] {
    const result = [];
    let leftLineNum = 1;
    let rightLineNum = 1;

    for (const chunk of chunks) {
      // If it isn't a common chunk, append it as-is and update line numbers.
      if (!chunk.ab && !chunk.skip && !chunk.common) {
        if (chunk.a) {
          leftLineNum += chunk.a.length;
        }
        if (chunk.b) {
          rightLineNum += chunk.b.length;
        }
        result.push(chunk);
        continue;
      }

      if (chunk.common && chunk.a!.length !== chunk.b!.length) {
        throw new Error(
          'DiffContent with common=true must always have equal length'
        );
      }
      const numLines = this.commonChunkLength(chunk);
      const chunkEnds = this.findChunkEndsAtKeyLocations(
        numLines,
        leftLineNum,
        rightLineNum
      );
      leftLineNum += numLines;
      rightLineNum += numLines;

      if (chunk.skip) {
        result.push({
          ...chunk,
          skip: chunk.skip,
          keyLocation: false,
        });
      } else if (chunk.ab) {
        result.push(
          ...this.splitAtChunkEnds(chunk.ab, chunkEnds).map(
            ({lines, keyLocation}) => {
              return {
                ...chunk,
                ab: lines,
                keyLocation,
              };
            }
          )
        );
      } else if (chunk.common) {
        const aChunks = this.splitAtChunkEnds(chunk.a!, chunkEnds);
        const bChunks = this.splitAtChunkEnds(chunk.b!, chunkEnds);
        result.push(
          ...aChunks.map(({lines, keyLocation}, i) => {
            return {
              ...chunk,
              a: lines,
              b: bChunks[i].lines,
              keyLocation,
            };
          })
        );
      }
    }

    return result;
  }

  /**
   * @return Offsets of the new chunk ends, including whether it's a key
   * location.
   */
  private findChunkEndsAtKeyLocations(
    numLines: number,
    leftOffset: number,
    rightOffset: number
  ): ChunkEnd[] {
    const result = [];
    let lastChunkEnd = 0;
    for (let i = 0; i < numLines; i++) {
      // If this line should not be collapsed.
      if (
        this.keyLocations[Side.LEFT][leftOffset + i] ||
        this.keyLocations[Side.RIGHT][rightOffset + i]
      ) {
        // If any lines have been accumulated into the chunk leading up to
        // this non-collapse line, then add them as a chunk and start a new
        // one.
        if (i > lastChunkEnd) {
          result.push({offset: i, keyLocation: false});
          lastChunkEnd = i;
        }

        // Add the non-collapse line as its own chunk.
        result.push({offset: i + 1, keyLocation: true});
      }
    }

    if (numLines > lastChunkEnd) {
      result.push({offset: numLines, keyLocation: false});
    }

    return result;
  }

  private splitAtChunkEnds(lines: string[], chunkEnds: ChunkEnd[]) {
    const result = [];
    let lastChunkEndOffset = 0;
    for (const {offset, keyLocation} of chunkEnds) {
      if (lastChunkEndOffset === offset) continue;
      result.push({
        lines: lines.slice(lastChunkEndOffset, offset),
        keyLocation,
      });
      lastChunkEndOffset = offset;
    }
    return result;
  }

  /**
   * Converts `IntralineInfo`s return by the API to `GrLineHighlights` used
   * for rendering.
   */
  // visible for testing
  convertIntralineInfos(
    rows: string[],
    intralineInfos: number[][]
  ): Highlights[] {
    // +1 to account for the \n that is not part of the rows passed here
    const lineLengths = rows.map(r => getStringLength(r) + 1);

    let rowIndex = 0;
    let idx = 0;
    const normalized = [];
    for (const [skipLength, markLength] of intralineInfos) {
      let lineLength = lineLengths[rowIndex];
      let j = 0;
      while (j < skipLength) {
        if (idx === lineLength) {
          idx = 0;
          lineLength = lineLengths[++rowIndex];
          continue;
        }
        idx++;
        j++;
      }
      let lineHighlight: Highlights = {
        contentIndex: rowIndex,
        startIndex: idx,
      };

      j = 0;
      while (lineLength && j < markLength) {
        if (idx === lineLength) {
          idx = 0;
          lineLength = lineLengths[++rowIndex];
          normalized.push(lineHighlight);
          lineHighlight = {
            contentIndex: rowIndex,
            startIndex: idx,
          };
          continue;
        }
        idx++;
        j++;
      }
      lineHighlight.endIndex = idx;
      normalized.push(lineHighlight);
    }
    return normalized;
  }

  /**
   * If a group is an addition or a removal, break it down into smaller groups
   * of that type using the MAX_GROUP_SIZE. If the group is a shared chunk
   * or a delta it is returned as the single element of the result array.
   */
  // visible for testing
  breakdownChunk(chunk: DiffContent): DiffContent[] {
    let key: 'a' | 'b' | 'ab' | null = null;
    const {a, b, ab, move_details} = chunk;
    if (a?.length && !b?.length) {
      key = 'a';
    } else if (b?.length && !a?.length) {
      key = 'b';
    } else if (ab?.length) {
      key = 'ab';
    }

    // Move chunks should not be divided because of move label
    // positioned in the top of the chunk
    if (!key || move_details) {
      return [chunk];
    }

    const MAX_GROUP_SIZE = calcMaxGroupSize(this.asyncThreshold);
    return this.breakdown(chunk[key]!, MAX_GROUP_SIZE).map(subChunkLines => {
      const subChunk: DiffContent = {};
      subChunk[key!] = subChunkLines;
      if (chunk.due_to_rebase) {
        subChunk.due_to_rebase = true;
      }
      if (chunk.move_details) {
        subChunk.move_details = chunk.move_details;
      }
      return subChunk;
    });
  }

  /**
   * Given an array and a size, return an array of arrays where no inner array
   * is larger than that size, preserving the original order.
   */
  // visible for testing
  breakdown<T>(array: T[], size: number): T[][] {
    if (!array.length) {
      return [];
    }
    if (array.length < size) {
      return [array];
    }

    const head = array.slice(0, array.length - size);
    const tail = array.slice(array.length - size);

    return this.breakdown(head, size).concat([tail]);
  }
}