var __defProp = Object.defineProperty;
var __getOwnPropDesc = Object.getOwnPropertyDescriptor;
var __getOwnPropNames = Object.getOwnPropertyNames;
var __hasOwnProp = Object.prototype.hasOwnProperty;
var __export = (target, all) => {
  for (var name in all)
    __defProp(target, name, { get: all[name], enumerable: true });
};
var __copyProps = (to, from, except, desc) => {
  if (from && typeof from === "object" || typeof from === "function") {
    for (let key of __getOwnPropNames(from))
      if (!__hasOwnProp.call(to, key) && key !== except)
        __defProp(to, key, { get: () => from[key], enumerable: !(desc = __getOwnPropDesc(from, key)) || desc.enumerable });
  }
  return to;
};
var __toCommonJS = (mod) => __copyProps(__defProp({}, "__esModule", { value: true }), mod);
var node_diff3_exports = {};
__export(node_diff3_exports, {
  LCS: () => LCS,
  TimeoutError: () => TimeoutError,
  diff3Merge: () => diff3Merge,
  diff3MergeRegions: () => diff3MergeRegions,
  diffComm: () => diffComm,
  diffIndices: () => diffIndices,
  diffPatch: () => diffPatch,
  invertPatch: () => invertPatch,
  merge: () => merge,
  mergeDiff3: () => mergeDiff3,
  mergeDigIn: () => mergeDigIn,
  patch: () => patch,
  stripPatch: () => stripPatch
});
module.exports = __toCommonJS(node_diff3_exports);
class TimeoutError extends Error {
  constructor() {
    super("timeout reached");
  }
}
function getAssertTimeout(timeout) {
  if (typeof timeout === "number") {
    const endTime = Date.now() + timeout;
    return () => {
      if (Date.now() > endTime) {
        throw new TimeoutError();
      }
    };
  }
  if (typeof timeout === "function") {
    return timeout;
  }
  return () => {
  };
}
function LCS(buffer1, buffer2, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  let equivalenceClasses = {};
  for (let j = 0; j < buffer2.length; j++) {
    const item = buffer2[j];
    if (equivalenceClasses[item]) {
      equivalenceClasses[item].push(j);
    } else {
      equivalenceClasses[item] = [j];
    }
  }
  const NULLRESULT = { buffer1index: -1, buffer2index: -1, chain: null };
  let candidates = [NULLRESULT];
  for (let i = 0; i < buffer1.length; i++) {
    assertTimeout();
    const item = buffer1[i];
    const buffer2indices = equivalenceClasses[item] || [];
    let r = 0;
    let c = candidates[0];
    for (let jx = 0; jx < buffer2indices.length; jx++) {
      assertTimeout();
      const j = buffer2indices[jx];
      let s;
      for (s = r; s < candidates.length; s++) {
        if (candidates[s].buffer2index < j && (s === candidates.length - 1 || candidates[s + 1].buffer2index > j)) {
          break;
        }
      }
      if (s < candidates.length) {
        const newCandidate = { buffer1index: i, buffer2index: j, chain: candidates[s] };
        if (r === candidates.length) {
          candidates.push(c);
        } else {
          candidates[r] = c;
        }
        r = s + 1;
        c = newCandidate;
        if (r === candidates.length) {
          break;
        }
      }
    }
    candidates[r] = c;
  }
  return candidates[candidates.length - 1];
}
function diffComm(buffer1, buffer2, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  const lcs = LCS(buffer1, buffer2, assertTimeout);
  let result = [];
  let tail1 = buffer1.length;
  let tail2 = buffer2.length;
  let common = { common: [] };
  function processCommon() {
    if (common.common.length) {
      common.common.reverse();
      result.push(common);
      common = { common: [] };
    }
  }
  for (let candidate = lcs; candidate !== null; candidate = candidate.chain) {
    assertTimeout();
    let different = { buffer1: [], buffer2: [] };
    while (--tail1 > candidate.buffer1index) {
      different.buffer1.push(buffer1[tail1]);
    }
    while (--tail2 > candidate.buffer2index) {
      different.buffer2.push(buffer2[tail2]);
    }
    if (different.buffer1.length || different.buffer2.length) {
      processCommon();
      different.buffer1.reverse();
      different.buffer2.reverse();
      result.push(different);
    }
    if (tail1 >= 0) {
      common.common.push(buffer1[tail1]);
    }
  }
  processCommon();
  result.reverse();
  return result;
}
function diffIndices(buffer1, buffer2, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  const lcs = LCS(buffer1, buffer2, assertTimeout);
  let result = [];
  let tail1 = buffer1.length;
  let tail2 = buffer2.length;
  for (let candidate = lcs; candidate !== null; candidate = candidate.chain) {
    assertTimeout();
    const mismatchLength1 = tail1 - candidate.buffer1index - 1;
    const mismatchLength2 = tail2 - candidate.buffer2index - 1;
    tail1 = candidate.buffer1index;
    tail2 = candidate.buffer2index;
    if (mismatchLength1 || mismatchLength2) {
      result.push({
        buffer1: [tail1 + 1, mismatchLength1],
        buffer1Content: buffer1.slice(tail1 + 1, tail1 + 1 + mismatchLength1),
        buffer2: [tail2 + 1, mismatchLength2],
        buffer2Content: buffer2.slice(tail2 + 1, tail2 + 1 + mismatchLength2)
      });
    }
  }
  result.reverse();
  return result;
}
function diffPatch(buffer1, buffer2, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  const lcs = LCS(buffer1, buffer2, assertTimeout);
  let result = [];
  let tail1 = buffer1.length;
  let tail2 = buffer2.length;
  function chunkDescription(buffer, offset, length) {
    let chunk = [];
    for (let i = 0; i < length; i++) {
      chunk.push(buffer[offset + i]);
    }
    return {
      offset,
      length,
      chunk
    };
  }
  for (let candidate = lcs; candidate !== null; candidate = candidate.chain) {
    assertTimeout();
    const mismatchLength1 = tail1 - candidate.buffer1index - 1;
    const mismatchLength2 = tail2 - candidate.buffer2index - 1;
    tail1 = candidate.buffer1index;
    tail2 = candidate.buffer2index;
    if (mismatchLength1 || mismatchLength2) {
      result.push({
        buffer1: chunkDescription(buffer1, candidate.buffer1index + 1, mismatchLength1),
        buffer2: chunkDescription(buffer2, candidate.buffer2index + 1, mismatchLength2)
      });
    }
  }
  result.reverse();
  return result;
}
function diff3MergeRegions(a, o, b, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  let hunks = [];
  function addHunk(h, ab) {
    hunks.push({
      ab,
      oStart: h.buffer1[0],
      oLength: h.buffer1[1],
      // length of o to remove
      abStart: h.buffer2[0],
      abLength: h.buffer2[1]
      // length of a/b to insert
      // abContent: (ab === 'a' ? a : b).slice(h.buffer2[0], h.buffer2[0] + h.buffer2[1])
    });
  }
  diffIndices(o, a, assertTimeout).forEach((item) => addHunk(item, "a"));
  diffIndices(o, b, assertTimeout).forEach((item) => addHunk(item, "b"));
  hunks.sort((x, y) => x.oStart - y.oStart);
  let results = [];
  let currOffset = 0;
  function advanceTo(endOffset) {
    if (endOffset > currOffset) {
      results.push({
        stable: true,
        buffer: "o",
        bufferStart: currOffset,
        bufferLength: endOffset - currOffset,
        bufferContent: o.slice(currOffset, endOffset)
      });
      currOffset = endOffset;
    }
  }
  while (hunks.length) {
    assertTimeout();
    let hunk = hunks.shift();
    let regionStart = hunk.oStart;
    let regionEnd = hunk.oStart + hunk.oLength;
    let regionHunks = [hunk];
    advanceTo(regionStart);
    while (hunks.length) {
      assertTimeout();
      const nextHunk = hunks[0];
      const nextHunkStart = nextHunk.oStart;
      if (nextHunkStart > regionEnd) break;
      regionEnd = Math.max(regionEnd, nextHunkStart + nextHunk.oLength);
      regionHunks.push(hunks.shift());
    }
    if (regionHunks.length === 1) {
      if (hunk.abLength > 0) {
        const buffer = hunk.ab === "a" ? a : b;
        results.push({
          stable: true,
          buffer: hunk.ab,
          bufferStart: hunk.abStart,
          bufferLength: hunk.abLength,
          bufferContent: buffer.slice(hunk.abStart, hunk.abStart + hunk.abLength)
        });
      }
    } else {
      let bounds = {
        a: [a.length, -1, o.length, -1],
        b: [b.length, -1, o.length, -1]
      };
      while (regionHunks.length) {
        assertTimeout();
        hunk = regionHunks.shift();
        const oStart = hunk.oStart;
        const oEnd = oStart + hunk.oLength;
        const abStart = hunk.abStart;
        const abEnd = abStart + hunk.abLength;
        let b2 = bounds[hunk.ab];
        b2[0] = Math.min(abStart, b2[0]);
        b2[1] = Math.max(abEnd, b2[1]);
        b2[2] = Math.min(oStart, b2[2]);
        b2[3] = Math.max(oEnd, b2[3]);
      }
      const aStart = bounds.a[0] + (regionStart - bounds.a[2]);
      const aEnd = bounds.a[1] + (regionEnd - bounds.a[3]);
      const bStart = bounds.b[0] + (regionStart - bounds.b[2]);
      const bEnd = bounds.b[1] + (regionEnd - bounds.b[3]);
      let result = {
        stable: false,
        aStart,
        aLength: aEnd - aStart,
        aContent: a.slice(aStart, aEnd),
        oStart: regionStart,
        oLength: regionEnd - regionStart,
        oContent: o.slice(regionStart, regionEnd),
        bStart,
        bLength: bEnd - bStart,
        bContent: b.slice(bStart, bEnd)
      };
      results.push(result);
    }
    currOffset = regionEnd;
  }
  advanceTo(o.length);
  return results;
}
function diff3Merge(a, o, b, options, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  let defaults = {
    excludeFalseConflicts: true,
    stringSeparator: /\s+/
  };
  options = Object.assign(defaults, options);
  if (typeof a === "string") a = a.split(options.stringSeparator);
  if (typeof o === "string") o = o.split(options.stringSeparator);
  if (typeof b === "string") b = b.split(options.stringSeparator);
  let results = [];
  const regions = diff3MergeRegions(a, o, b, assertTimeout);
  let okBuffer = [];
  function flushOk() {
    if (okBuffer.length) {
      results.push({ ok: okBuffer });
    }
    okBuffer = [];
  }
  function isFalseConflict(a2, b2) {
    if (a2.length !== b2.length) return false;
    for (let i = 0; i < a2.length; i++) {
      if (a2[i] !== b2[i]) return false;
    }
    return true;
  }
  regions.forEach((region) => {
    assertTimeout();
    if (region.stable) {
      okBuffer.push(...region.bufferContent);
    } else {
      if (options.excludeFalseConflicts && isFalseConflict(region.aContent, region.bContent)) {
        okBuffer.push(...region.aContent);
      } else {
        flushOk();
        results.push({
          conflict: {
            a: region.aContent,
            aIndex: region.aStart,
            o: region.oContent,
            oIndex: region.oStart,
            b: region.bContent,
            bIndex: region.bStart
          }
        });
      }
    }
  });
  flushOk();
  return results;
}
function mergeDiff3(a, o, b, options, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  const defaults = {
    excludeFalseConflicts: true,
    stringSeparator: /\s+/,
    label: {}
  };
  options = Object.assign(defaults, options);
  const aSection = "<<<<<<<" + (options.label.a ? ` ${options.label.a}` : "");
  const oSection = "|||||||" + (options.label.o ? ` ${options.label.o}` : "");
  const xSection = "=======";
  const bSection = ">>>>>>>" + (options.label.b ? ` ${options.label.b}` : "");
  const regions = diff3Merge(a, o, b, options, assertTimeout);
  let conflict = false;
  let result = [];
  regions.forEach((region) => {
    assertTimeout();
    if (region.ok) {
      result = result.concat(region.ok);
    } else if (region.conflict) {
      conflict = true;
      result = result.concat(
        [aSection],
        region.conflict.a,
        [oSection],
        region.conflict.o,
        [xSection],
        region.conflict.b,
        [bSection]
      );
    }
  });
  return {
    conflict,
    result
  };
}
function merge(a, o, b, options, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  const defaults = {
    excludeFalseConflicts: true,
    stringSeparator: /\s+/,
    label: {}
  };
  options = Object.assign(defaults, options);
  const aSection = "<<<<<<<" + (options.label.a ? ` ${options.label.a}` : "");
  const xSection = "=======";
  const bSection = ">>>>>>>" + (options.label.b ? ` ${options.label.b}` : "");
  const regions = diff3Merge(a, o, b, options, assertTimeout);
  let conflict = false;
  let result = [];
  regions.forEach((region) => {
    assertTimeout();
    if (region.ok) {
      result = result.concat(region.ok);
    } else if (region.conflict) {
      conflict = true;
      result = result.concat(
        [aSection],
        region.conflict.a,
        [xSection],
        region.conflict.b,
        [bSection]
      );
    }
  });
  return {
    conflict,
    result
  };
}
function mergeDigIn(a, o, b, options, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  const defaults = {
    excludeFalseConflicts: true,
    stringSeparator: /\s+/,
    label: {}
  };
  options = Object.assign(defaults, options);
  const aSection = "<<<<<<<" + (options.label.a ? ` ${options.label.a}` : "");
  const xSection = "=======";
  const bSection = ">>>>>>>" + (options.label.b ? ` ${options.label.b}` : "");
  const regions = diff3Merge(a, o, b, options, assertTimeout);
  let conflict = false;
  let result = [];
  regions.forEach((region) => {
    assertTimeout();
    if (region.ok) {
      result = result.concat(region.ok);
    } else {
      const c = diffComm(region.conflict.a, region.conflict.b, assertTimeout);
      for (let j = 0; j < c.length; j++) {
        assertTimeout();
        let inner = c[j];
        if (inner.common) {
          result = result.concat(inner.common);
        } else {
          conflict = true;
          result = result.concat(
            [aSection],
            inner.buffer1,
            [xSection],
            inner.buffer2,
            [bSection]
          );
        }
      }
    }
  });
  return {
    conflict,
    result
  };
}
function patch(buffer, patch2, timeout) {
  const assertTimeout = getAssertTimeout(timeout);
  let result = [];
  let currOffset = 0;
  function advanceTo(targetOffset) {
    while (currOffset < targetOffset) {
      result.push(buffer[currOffset]);
      currOffset++;
    }
  }
  for (let chunkIndex = 0; chunkIndex < patch2.length; chunkIndex++) {
    assertTimeout();
    let chunk = patch2[chunkIndex];
    advanceTo(chunk.buffer1.offset);
    for (let itemIndex = 0; itemIndex < chunk.buffer2.chunk.length; itemIndex++) {
      result.push(chunk.buffer2.chunk[itemIndex]);
    }
    currOffset += chunk.buffer1.length;
  }
  advanceTo(buffer.length);
  return result;
}
function stripPatch(patch2) {
  return patch2.map((chunk) => ({
    buffer1: { offset: chunk.buffer1.offset, length: chunk.buffer1.length },
    buffer2: { chunk: chunk.buffer2.chunk }
  }));
}
function invertPatch(patch2) {
  return patch2.map((chunk) => ({
    buffer1: chunk.buffer2,
    buffer2: chunk.buffer1
  }));
}
// Annotate the CommonJS export names for ESM import in node:
0 && (module.exports = {
  LCS,
  TimeoutError,
  diff3Merge,
  diff3MergeRegions,
  diffComm,
  diffIndices,
  diffPatch,
  invertPatch,
  merge,
  mergeDiff3,
  mergeDigIn,
  patch,
  stripPatch
});
//# sourceMappingURL=index.cjs.map