threeWayMerge method

MergeResult threeWayMerge(String base, String ours, String theirs)

Perform a three-way merge between base, ours, and theirs.

Returns a MergeResult containing the merged text and any conflict regions. Conflict markers follow the standard Git format.

Implementation

MergeResult threeWayMerge(String base, String ours, String theirs) {
  final baseLines = base.split('\n');
  final ourLines = ours.split('\n');
  final theirLines = theirs.split('\n');

  final ourEdits = _myersDiff(baseLines, ourLines);
  final theirEdits = _myersDiff(baseLines, theirLines);

  final ourChanges = _editsToCh(ourEdits, baseLines, ourLines);
  final theirChanges = _editsToCh(theirEdits, baseLines, theirLines);

  final merged = <String>[];
  final conflicts = <ConflictRegion>[];

  var baseIdx = 0;

  // Build indexed change maps: baseLineIndex -> replacement lines.
  final ourMap = <int, List<String>>{};
  final theirMap = <int, List<String>>{};
  final ourDeletes = <int>{};
  final theirDeletes = <int>{};

  for (final c in ourChanges) {
    if (c.type == _EditType.delete) ourDeletes.add(c.oldIndex);
    if (c.type == _EditType.insert) {
      ourMap.putIfAbsent(c.oldIndex, () => []).add(ourLines[c.newIndex]);
    }
  }
  for (final c in theirChanges) {
    if (c.type == _EditType.delete) theirDeletes.add(c.oldIndex);
    if (c.type == _EditType.insert) {
      theirMap.putIfAbsent(c.oldIndex, () => []).add(theirLines[c.newIndex]);
    }
  }

  for (baseIdx = 0; baseIdx < baseLines.length; baseIdx++) {
    final ourDel = ourDeletes.contains(baseIdx);
    final theirDel = theirDeletes.contains(baseIdx);
    final ourIns = ourMap[baseIdx];
    final theirIns = theirMap[baseIdx];

    // Both sides same change — no conflict.
    if (ourDel == theirDel && _listEq(ourIns, theirIns)) {
      if (!ourDel) merged.add(baseLines[baseIdx]);
      if (ourIns != null) merged.addAll(ourIns);
      continue;
    }

    // Only one side changed.
    if (!ourDel && ourIns == null) {
      if (!theirDel) merged.add(baseLines[baseIdx]);
      if (theirIns != null) merged.addAll(theirIns);
      continue;
    }
    if (!theirDel && theirIns == null) {
      if (!ourDel) merged.add(baseLines[baseIdx]);
      if (ourIns != null) merged.addAll(ourIns);
      continue;
    }

    // Conflict.
    final startLine = merged.length + 1;
    final ourBlock = <String>[];
    final theirBlock = <String>[];
    if (!ourDel) ourBlock.add(baseLines[baseIdx]);
    if (ourIns != null) ourBlock.addAll(ourIns);
    if (!theirDel) theirBlock.add(baseLines[baseIdx]);
    if (theirIns != null) theirBlock.addAll(theirIns);

    conflicts.add(
      ConflictRegion(
        base: [baseLines[baseIdx]],
        ours: ourBlock,
        theirs: theirBlock,
        startLine: startLine,
      ),
    );

    merged.add('<<<<<<< ours');
    merged.addAll(ourBlock);
    merged.add('=======');
    merged.addAll(theirBlock);
    merged.add('>>>>>>> theirs');
  }

  // Handle trailing inserts past the end of base.
  final ourTrail = ourMap[baseLines.length];
  final theirTrail = theirMap[baseLines.length];
  if (ourTrail != null) merged.addAll(ourTrail);
  if (theirTrail != null) merged.addAll(theirTrail);

  return MergeResult(merged: merged.join('\n'), conflicts: conflicts);
}