/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

import {
  IDiffChange,
  ISequence,
  LcsDiff,
  IDiffResult,
} from '../../../../vs/base/common/diff/diff';
import * as strings from '../../../../vs/base/common/strings';
import {
  ICharChange,
  ILineChange,
} from '../../../../vs/editor/common/editorCommon';

const MINIMUM_MATCHING_CHARACTER_LENGTH = 3;

export interface IDiffComputerResult {
  quitEarly: boolean;
  changes: ILineChange[];
}

function computeDiff(
  originalSequence: ISequence,
  modifiedSequence: ISequence,
  continueProcessingPredicate: () => boolean,
  pretty: boolean
): IDiffResult {
  const diffAlgo = new LcsDiff(
    originalSequence,
    modifiedSequence,
    continueProcessingPredicate
  );
  return diffAlgo.ComputeDiff(pretty);
}

class LineSequence implements ISequence {
  public readonly lines: string[];
  private readonly _startColumns: number[];
  private readonly _endColumns: number[];

  constructor(lines: string[]) {
    const startColumns: number[] = [];
    const endColumns: number[] = [];
    for (let i = 0, length = lines.length; i < length; i++) {
      startColumns[i] = getFirstNonBlankColumn(lines[i], 1);
      endColumns[i] = getLastNonBlankColumn(lines[i], 1);
    }
    this.lines = lines;
    this._startColumns = startColumns;
    this._endColumns = endColumns;
  }

  public getElements(): Int32Array | number[] | string[] {
    const elements: string[] = [];
    for (let i = 0, len = this.lines.length; i < len; i++) {
      elements[i] = this.lines[i].substring(
        this._startColumns[i] - 1,
        this._endColumns[i] - 1
      );
    }
    return elements;
  }

  public getStartLineNumber(i: number): number {
    return i + 1;
  }

  public getEndLineNumber(i: number): number {
    return i + 1;
  }

  public createCharSequence(
    shouldIgnoreTrimWhitespace: boolean,
    startIndex: number,
    endIndex: number
  ): CharSequence {
    const charCodes: number[] = [];
    const lineNumbers: number[] = [];
    const columns: number[] = [];
    let len = 0;
    for (let index = startIndex; index <= endIndex; index++) {
      const lineContent = this.lines[index];
      const startColumn = shouldIgnoreTrimWhitespace
        ? this._startColumns[index]
        : 1;
      const endColumn = shouldIgnoreTrimWhitespace
        ? this._endColumns[index]
        : lineContent.length + 1;
      for (let col = startColumn; col < endColumn; col++) {
        charCodes[len] = lineContent.charCodeAt(col - 1);
        lineNumbers[len] = index + 1;
        columns[len] = col;
        len++;
      }
    }
    return new CharSequence(charCodes, lineNumbers, columns);
  }
}

class CharSequence implements ISequence {
  private readonly _charCodes: number[];
  private readonly _lineNumbers: number[];
  private readonly _columns: number[];

  constructor(charCodes: number[], lineNumbers: number[], columns: number[]) {
    this._charCodes = charCodes;
    this._lineNumbers = lineNumbers;
    this._columns = columns;
  }

  public getElements(): Int32Array | number[] | string[] {
    return this._charCodes;
  }

  public getStartLineNumber(i: number): number {
    return this._lineNumbers[i];
  }

  public getStartColumn(i: number): number {
    return this._columns[i];
  }

  public getEndLineNumber(i: number): number {
    return this._lineNumbers[i];
  }

  public getEndColumn(i: number): number {
    return this._columns[i] + 1;
  }
}

class CharChange implements ICharChange {
  public originalStartLineNumber: number;
  public originalStartColumn: number;
  public originalEndLineNumber: number;
  public originalEndColumn: number;

  public modifiedStartLineNumber: number;
  public modifiedStartColumn: number;
  public modifiedEndLineNumber: number;
  public modifiedEndColumn: number;

  constructor(
    originalStartLineNumber: number,
    originalStartColumn: number,
    originalEndLineNumber: number,
    originalEndColumn: number,
    modifiedStartLineNumber: number,
    modifiedStartColumn: number,
    modifiedEndLineNumber: number,
    modifiedEndColumn: number
  ) {
    this.originalStartLineNumber = originalStartLineNumber;
    this.originalStartColumn = originalStartColumn;
    this.originalEndLineNumber = originalEndLineNumber;
    this.originalEndColumn = originalEndColumn;
    this.modifiedStartLineNumber = modifiedStartLineNumber;
    this.modifiedStartColumn = modifiedStartColumn;
    this.modifiedEndLineNumber = modifiedEndLineNumber;
    this.modifiedEndColumn = modifiedEndColumn;
  }

  public static createFromDiffChange(
    diffChange: IDiffChange,
    originalCharSequence: CharSequence,
    modifiedCharSequence: CharSequence
  ): CharChange {
    let originalStartLineNumber: number;
    let originalStartColumn: number;
    let originalEndLineNumber: number;
    let originalEndColumn: number;
    let modifiedStartLineNumber: number;
    let modifiedStartColumn: number;
    let modifiedEndLineNumber: number;
    let modifiedEndColumn: number;

    if (diffChange.originalLength === 0) {
      originalStartLineNumber = 0;
      originalStartColumn = 0;
      originalEndLineNumber = 0;
      originalEndColumn = 0;
    } else {
      originalStartLineNumber = originalCharSequence.getStartLineNumber(
        diffChange.originalStart
      );
      originalStartColumn = originalCharSequence.getStartColumn(
        diffChange.originalStart
      );
      originalEndLineNumber = originalCharSequence.getEndLineNumber(
        diffChange.originalStart + diffChange.originalLength - 1
      );
      originalEndColumn = originalCharSequence.getEndColumn(
        diffChange.originalStart + diffChange.originalLength - 1
      );
    }

    if (diffChange.modifiedLength === 0) {
      modifiedStartLineNumber = 0;
      modifiedStartColumn = 0;
      modifiedEndLineNumber = 0;
      modifiedEndColumn = 0;
    } else {
      modifiedStartLineNumber = modifiedCharSequence.getStartLineNumber(
        diffChange.modifiedStart
      );
      modifiedStartColumn = modifiedCharSequence.getStartColumn(
        diffChange.modifiedStart
      );
      modifiedEndLineNumber = modifiedCharSequence.getEndLineNumber(
        diffChange.modifiedStart + diffChange.modifiedLength - 1
      );
      modifiedEndColumn = modifiedCharSequence.getEndColumn(
        diffChange.modifiedStart + diffChange.modifiedLength - 1
      );
    }

    return new CharChange(
      originalStartLineNumber,
      originalStartColumn,
      originalEndLineNumber,
      originalEndColumn,
      modifiedStartLineNumber,
      modifiedStartColumn,
      modifiedEndLineNumber,
      modifiedEndColumn
    );
  }
}

function postProcessCharChanges(rawChanges: IDiffChange[]): IDiffChange[] {
  if (rawChanges.length <= 1) {
    return rawChanges;
  }

  const result = [rawChanges[0]];
  let prevChange = result[0];

  for (let i = 1, len = rawChanges.length; i < len; i++) {
    const currChange = rawChanges[i];

    const originalMatchingLength =
      currChange.originalStart -
      (prevChange.originalStart + prevChange.originalLength);
    const modifiedMatchingLength =
      currChange.modifiedStart -
      (prevChange.modifiedStart + prevChange.modifiedLength);
    // Both of the above should be equal, but the continueProcessingPredicate may prevent this from being true
    const matchingLength = Math.min(
      originalMatchingLength,
      modifiedMatchingLength
    );

    if (matchingLength < MINIMUM_MATCHING_CHARACTER_LENGTH) {
      // Merge the current change into the previous one
      prevChange.originalLength =
        currChange.originalStart +
        currChange.originalLength -
        prevChange.originalStart;
      prevChange.modifiedLength =
        currChange.modifiedStart +
        currChange.modifiedLength -
        prevChange.modifiedStart;
    } else {
      // Add the current change
      result.push(currChange);
      prevChange = currChange;
    }
  }

  return result;
}

class LineChange implements ILineChange {
  public originalStartLineNumber: number;
  public originalEndLineNumber: number;
  public modifiedStartLineNumber: number;
  public modifiedEndLineNumber: number;
  public charChanges: CharChange[] | undefined;

  constructor(
    originalStartLineNumber: number,
    originalEndLineNumber: number,
    modifiedStartLineNumber: number,
    modifiedEndLineNumber: number,
    charChanges: CharChange[] | undefined
  ) {
    this.originalStartLineNumber = originalStartLineNumber;
    this.originalEndLineNumber = originalEndLineNumber;
    this.modifiedStartLineNumber = modifiedStartLineNumber;
    this.modifiedEndLineNumber = modifiedEndLineNumber;
    this.charChanges = charChanges;
  }

  public static createFromDiffResult(
    shouldIgnoreTrimWhitespace: boolean,
    diffChange: IDiffChange,
    originalLineSequence: LineSequence,
    modifiedLineSequence: LineSequence,
    continueCharDiff: () => boolean,
    shouldComputeCharChanges: boolean,
    shouldPostProcessCharChanges: boolean
  ): LineChange {
    let originalStartLineNumber: number;
    let originalEndLineNumber: number;
    let modifiedStartLineNumber: number;
    let modifiedEndLineNumber: number;
    let charChanges: CharChange[] | undefined = undefined;

    if (diffChange.originalLength === 0) {
      originalStartLineNumber =
        originalLineSequence.getStartLineNumber(diffChange.originalStart) - 1;
      originalEndLineNumber = 0;
    } else {
      originalStartLineNumber = originalLineSequence.getStartLineNumber(
        diffChange.originalStart
      );
      originalEndLineNumber = originalLineSequence.getEndLineNumber(
        diffChange.originalStart + diffChange.originalLength - 1
      );
    }

    if (diffChange.modifiedLength === 0) {
      modifiedStartLineNumber =
        modifiedLineSequence.getStartLineNumber(diffChange.modifiedStart) - 1;
      modifiedEndLineNumber = 0;
    } else {
      modifiedStartLineNumber = modifiedLineSequence.getStartLineNumber(
        diffChange.modifiedStart
      );
      modifiedEndLineNumber = modifiedLineSequence.getEndLineNumber(
        diffChange.modifiedStart + diffChange.modifiedLength - 1
      );
    }

    if (
      shouldComputeCharChanges &&
      diffChange.originalLength > 0 &&
      diffChange.originalLength < 20 &&
      diffChange.modifiedLength > 0 &&
      diffChange.modifiedLength < 20 &&
      continueCharDiff()
    ) {
      // Compute character changes for diff chunks of at most 20 lines...
      const originalCharSequence = originalLineSequence.createCharSequence(
        shouldIgnoreTrimWhitespace,
        diffChange.originalStart,
        diffChange.originalStart + diffChange.originalLength - 1
      );
      const modifiedCharSequence = modifiedLineSequence.createCharSequence(
        shouldIgnoreTrimWhitespace,
        diffChange.modifiedStart,
        diffChange.modifiedStart + diffChange.modifiedLength - 1
      );

      let rawChanges = computeDiff(
        originalCharSequence,
        modifiedCharSequence,
        continueCharDiff,
        true
      ).changes;

      if (shouldPostProcessCharChanges) {
        rawChanges = postProcessCharChanges(rawChanges);
      }

      charChanges = [];
      for (let i = 0, length = rawChanges.length; i < length; i++) {
        charChanges.push(
          CharChange.createFromDiffChange(
            rawChanges[i],
            originalCharSequence,
            modifiedCharSequence
          )
        );
      }
    }

    return new LineChange(
      originalStartLineNumber,
      originalEndLineNumber,
      modifiedStartLineNumber,
      modifiedEndLineNumber,
      charChanges
    );
  }
}

export interface IDiffComputerOpts {
  shouldComputeCharChanges: boolean;
  shouldPostProcessCharChanges: boolean;
  shouldIgnoreTrimWhitespace: boolean;
  shouldMakePrettyDiff: boolean;
  maxComputationTime: number;
}

export class DiffComputer {
  private readonly shouldComputeCharChanges: boolean;
  private readonly shouldPostProcessCharChanges: boolean;
  private readonly shouldIgnoreTrimWhitespace: boolean;
  private readonly shouldMakePrettyDiff: boolean;
  private readonly originalLines: string[];
  private readonly modifiedLines: string[];
  private readonly original: LineSequence;
  private readonly modified: LineSequence;
  private readonly continueLineDiff: () => boolean;
  private readonly continueCharDiff: () => boolean;

  constructor(
    originalLines: string[],
    modifiedLines: string[],
    opts: IDiffComputerOpts
  ) {
    this.shouldComputeCharChanges = opts.shouldComputeCharChanges;
    this.shouldPostProcessCharChanges = opts.shouldPostProcessCharChanges;
    this.shouldIgnoreTrimWhitespace = opts.shouldIgnoreTrimWhitespace;
    this.shouldMakePrettyDiff = opts.shouldMakePrettyDiff;
    this.originalLines = originalLines;
    this.modifiedLines = modifiedLines;
    this.original = new LineSequence(originalLines);
    this.modified = new LineSequence(modifiedLines);

    this.continueLineDiff = createContinueProcessingPredicate(
      opts.maxComputationTime
    );
    this.continueCharDiff = createContinueProcessingPredicate(
      opts.maxComputationTime === 0
        ? 0
        : Math.min(opts.maxComputationTime, 5000)
    ); // never run after 5s for character changes...
  }

  public computeDiff(): IDiffComputerResult {
    if (
      this.original.lines.length === 1 &&
      this.original.lines[0].length === 0
    ) {
      // empty original => fast path
      if (
        this.modified.lines.length === 1 &&
        this.modified.lines[0].length === 0
      ) {
        return {
          quitEarly: false,
          changes: [],
        };
      }

      return {
        quitEarly: false,
        changes: [
          {
            originalStartLineNumber: 1,
            originalEndLineNumber: 1,
            modifiedStartLineNumber: 1,
            modifiedEndLineNumber: this.modified.lines.length,
            charChanges: [
              {
                modifiedEndColumn: 0,
                modifiedEndLineNumber: 0,
                modifiedStartColumn: 0,
                modifiedStartLineNumber: 0,
                originalEndColumn: 0,
                originalEndLineNumber: 0,
                originalStartColumn: 0,
                originalStartLineNumber: 0,
              },
            ],
          },
        ],
      };
    }

    if (
      this.modified.lines.length === 1 &&
      this.modified.lines[0].length === 0
    ) {
      // empty modified => fast path
      return {
        quitEarly: false,
        changes: [
          {
            originalStartLineNumber: 1,
            originalEndLineNumber: this.original.lines.length,
            modifiedStartLineNumber: 1,
            modifiedEndLineNumber: 1,
            charChanges: [
              {
                modifiedEndColumn: 0,
                modifiedEndLineNumber: 0,
                modifiedStartColumn: 0,
                modifiedStartLineNumber: 0,
                originalEndColumn: 0,
                originalEndLineNumber: 0,
                originalStartColumn: 0,
                originalStartLineNumber: 0,
              },
            ],
          },
        ],
      };
    }

    const diffResult = computeDiff(
      this.original,
      this.modified,
      this.continueLineDiff,
      this.shouldMakePrettyDiff
    );
    const rawChanges = diffResult.changes;
    const quitEarly = diffResult.quitEarly;

    // The diff is always computed with ignoring trim whitespace
    // This ensures we get the prettiest diff

    if (this.shouldIgnoreTrimWhitespace) {
      const lineChanges: LineChange[] = [];
      for (let i = 0, length = rawChanges.length; i < length; i++) {
        lineChanges.push(
          LineChange.createFromDiffResult(
            this.shouldIgnoreTrimWhitespace,
            rawChanges[i],
            this.original,
            this.modified,
            this.continueCharDiff,
            this.shouldComputeCharChanges,
            this.shouldPostProcessCharChanges
          )
        );
      }
      return {
        quitEarly: quitEarly,
        changes: lineChanges,
      };
    }

    // Need to post-process and introduce changes where the trim whitespace is different
    // Note that we are looping starting at -1 to also cover the lines before the first change
    const result: LineChange[] = [];

    let originalLineIndex = 0;
    let modifiedLineIndex = 0;
    for (let i = -1 /* !!!! */, len = rawChanges.length; i < len; i++) {
      const nextChange = i + 1 < len ? rawChanges[i + 1] : null;
      const originalStop = nextChange
        ? nextChange.originalStart
        : this.originalLines.length;
      const modifiedStop = nextChange
        ? nextChange.modifiedStart
        : this.modifiedLines.length;

      while (
        originalLineIndex < originalStop &&
        modifiedLineIndex < modifiedStop
      ) {
        const originalLine = this.originalLines[originalLineIndex];
        const modifiedLine = this.modifiedLines[modifiedLineIndex];

        if (originalLine !== modifiedLine) {
          // These lines differ only in trim whitespace

          // Check the leading whitespace
          {
            let originalStartColumn = getFirstNonBlankColumn(originalLine, 1);
            let modifiedStartColumn = getFirstNonBlankColumn(modifiedLine, 1);
            while (originalStartColumn > 1 && modifiedStartColumn > 1) {
              const originalChar = originalLine.charCodeAt(
                originalStartColumn - 2
              );
              const modifiedChar = modifiedLine.charCodeAt(
                modifiedStartColumn - 2
              );
              if (originalChar !== modifiedChar) {
                break;
              }
              originalStartColumn--;
              modifiedStartColumn--;
            }

            if (originalStartColumn > 1 || modifiedStartColumn > 1) {
              this._pushTrimWhitespaceCharChange(
                result,
                originalLineIndex + 1,
                1,
                originalStartColumn,
                modifiedLineIndex + 1,
                1,
                modifiedStartColumn
              );
            }
          }

          // Check the trailing whitespace
          {
            let originalEndColumn = getLastNonBlankColumn(originalLine, 1);
            let modifiedEndColumn = getLastNonBlankColumn(modifiedLine, 1);
            const originalMaxColumn = originalLine.length + 1;
            const modifiedMaxColumn = modifiedLine.length + 1;
            while (
              originalEndColumn < originalMaxColumn &&
              modifiedEndColumn < modifiedMaxColumn
            ) {
              const originalChar = originalLine.charCodeAt(
                originalEndColumn - 1
              );
              const modifiedChar = originalLine.charCodeAt(
                modifiedEndColumn - 1
              );
              if (originalChar !== modifiedChar) {
                break;
              }
              originalEndColumn++;
              modifiedEndColumn++;
            }

            if (
              originalEndColumn < originalMaxColumn ||
              modifiedEndColumn < modifiedMaxColumn
            ) {
              this._pushTrimWhitespaceCharChange(
                result,
                originalLineIndex + 1,
                originalEndColumn,
                originalMaxColumn,
                modifiedLineIndex + 1,
                modifiedEndColumn,
                modifiedMaxColumn
              );
            }
          }
        }
        originalLineIndex++;
        modifiedLineIndex++;
      }

      if (nextChange) {
        // Emit the actual change
        result.push(
          LineChange.createFromDiffResult(
            this.shouldIgnoreTrimWhitespace,
            nextChange,
            this.original,
            this.modified,
            this.continueCharDiff,
            this.shouldComputeCharChanges,
            this.shouldPostProcessCharChanges
          )
        );

        originalLineIndex += nextChange.originalLength;
        modifiedLineIndex += nextChange.modifiedLength;
      }
    }

    return {
      quitEarly: quitEarly,
      changes: result,
    };
  }

  private _pushTrimWhitespaceCharChange(
    result: LineChange[],
    originalLineNumber: number,
    originalStartColumn: number,
    originalEndColumn: number,
    modifiedLineNumber: number,
    modifiedStartColumn: number,
    modifiedEndColumn: number
  ): void {
    if (
      this._mergeTrimWhitespaceCharChange(
        result,
        originalLineNumber,
        originalStartColumn,
        originalEndColumn,
        modifiedLineNumber,
        modifiedStartColumn,
        modifiedEndColumn
      )
    ) {
      // Merged into previous
      return;
    }

    let charChanges: CharChange[] | undefined = undefined;
    if (this.shouldComputeCharChanges) {
      charChanges = [
        new CharChange(
          originalLineNumber,
          originalStartColumn,
          originalLineNumber,
          originalEndColumn,
          modifiedLineNumber,
          modifiedStartColumn,
          modifiedLineNumber,
          modifiedEndColumn
        ),
      ];
    }
    result.push(
      new LineChange(
        originalLineNumber,
        originalLineNumber,
        modifiedLineNumber,
        modifiedLineNumber,
        charChanges
      )
    );
  }

  private _mergeTrimWhitespaceCharChange(
    result: LineChange[],
    originalLineNumber: number,
    originalStartColumn: number,
    originalEndColumn: number,
    modifiedLineNumber: number,
    modifiedStartColumn: number,
    modifiedEndColumn: number
  ): boolean {
    const len = result.length;
    if (len === 0) {
      return false;
    }

    const prevChange = result[len - 1];

    if (
      prevChange.originalEndLineNumber === 0 ||
      prevChange.modifiedEndLineNumber === 0
    ) {
      // Don't merge with inserts/deletes
      return false;
    }

    if (
      prevChange.originalEndLineNumber + 1 === originalLineNumber &&
      prevChange.modifiedEndLineNumber + 1 === modifiedLineNumber
    ) {
      prevChange.originalEndLineNumber = originalLineNumber;
      prevChange.modifiedEndLineNumber = modifiedLineNumber;
      if (this.shouldComputeCharChanges && prevChange.charChanges) {
        prevChange.charChanges.push(
          new CharChange(
            originalLineNumber,
            originalStartColumn,
            originalLineNumber,
            originalEndColumn,
            modifiedLineNumber,
            modifiedStartColumn,
            modifiedLineNumber,
            modifiedEndColumn
          )
        );
      }
      return true;
    }

    return false;
  }
}

function getFirstNonBlankColumn(txt: string, defaultValue: number): number {
  const r = strings.firstNonWhitespaceIndex(txt);
  if (r === -1) {
    return defaultValue;
  }
  return r + 1;
}

function getLastNonBlankColumn(txt: string, defaultValue: number): number {
  const r = strings.lastNonWhitespaceIndex(txt);
  if (r === -1) {
    return defaultValue;
  }
  return r + 2;
}

function createContinueProcessingPredicate(
  maximumRuntime: number
): () => boolean {
  if (maximumRuntime === 0) {
    return () => true;
  }

  const startTime = Date.now();
  return () => {
    return Date.now() - startTime < maximumRuntime;
  };
}