Repository: jupyter/nbdime (language: python)

Issue:
findAlignedLines sometimes returns unexpected results
In some case it has been observed that the method `findAlignedLines`used to determine which line numbers align with each other, in the set of DiffViews, return a non correct result, leading to wrong alignment.

We can see here an example of a mergeview:
![Screenshot from 2023-09-05 23-40-52](https://github.com/jupyter/nbdime/assets/99649086/0f9c3a7a-cb5b-4008-8d34-aa6770ac83f0)
The result given by `findAlignedLines`is.
[3, 3, 3, 3]
[4, 5, 4, 5]
[11, 11, 11, 12]
[18, 18, 13, 14]
There is an additionnal padding in the left editor above line 12 causing that this line is not aligned with the 2 lines 11 of central and right editors.

After proposing this manual correction for the array return by `findAlignedLines`, alignment is fixed:
[3, 3, 3, 3]
[4, 5, 4, 5]
[11, **12** 11, 12]
[18, **19**, 13, 14]
![Screenshot from 2023-09-06 00-15-44](https://github.com/jupyter/nbdime/assets/99649086/e647a686-0677-450b-930e-c6ecf6ac961a)



Discussion / hints:
That error is more specifically coming from 

https://github.com/jupyter/nbdime/blob/8eb311d9465203d57e102bdc565c1cffc1c66cc6/packages/nbdime/src/common/mergeview.ts#L997

it does not handle properly finding a chunk in an editor that does not have that chunk; e.g. if a chunk is between base and right editors, that method does not return the proper alignment for that chunk in the left editor.

Fix patch:
diff --git a/packages/nbdime/src/common/mergeview.ts b/packages/nbdime/src/common/mergeview.ts
index 9790b95d..b316149e 100644
--- a/packages/nbdime/src/common/mergeview.ts
+++ b/packages/nbdime/src/common/mergeview.ts
@@ -48,8 +48,8 @@ import type { IMergeViewOptions } from './interfaces';
 
 import { valueIn, hasEntries, splitLines } from './util';
 
-const PICKER_SYMBOL = '\u27ad';
-const CONFLICT_MARKER = '\u26A0';
+const PICKER_SYMBOL = '\u27ad\uFE0E';
+const CONFLICT_MARKER = '\u26A0\uFE0E';
 
 export enum DIFF_OP {
   DIFF_DELETE = -1,
@@ -1179,17 +1179,26 @@ function getMatchingEditLine(baseLine: number, chunks: Chunk[]): number {
  *
  */
 function getMatchingEditLineLC(toMatch: Chunk, chunks: Chunk[]): number {
-  let editLine = toMatch.baseFrom;
+  console.log(toMatch, chunks)
+  const editLine = toMatch.baseFrom;
+  // Initialize with the last chunk in case we don't hit one of the
+  // two escape conditions in the for loop.
+  let previous: Chunk | undefined = chunks[chunks.length - 1];
   for (let i = 0; i < chunks.length; ++i) {
-    let chunk = chunks[i];
+    const chunk = chunks[i];
     if (chunk.baseFrom === editLine) {
+      // Chunk is part of the chunk list
       return chunk.remoteTo;
     }
     if (chunk.baseFrom > editLine) {
+      // Remaining chunks are after the one we are interested
+      previous = chunks[i - 1];
       break;
     }
   }
-  return toMatch.baseTo;
+  // toMatch is not in chunks list, add lines delta from the last chunk
+  console.log(previous, toMatch.baseTo + (previous ? (previous.remoteTo - previous.baseTo) : 0))
+  return toMatch.baseTo + (previous ? (previous.remoteTo - previous.baseTo) : 0);
 }
 
 /**
@@ -1211,7 +1220,7 @@ function findAlignedLines(dvs: Readonly<DiffView[]>): number[][] {
     let chunk = dv.lineChunks[i];
     let lines = [chunk.baseTo, chunk.remoteTo];
 
-    for (let o of others) {
+    for (const o of others) {
       lines.push(getMatchingEditLineLC(chunk, o.lineChunks));
     }
     if (
@@ -1226,6 +1235,7 @@ function findAlignedLines(dvs: Readonly<DiffView[]>): number[][] {
       if (linesToAlign.length > 0) {
         let prev = linesToAlign[linesToAlign.length - 1];
         let diff: number | null = lines[0] - prev[0];
+        // Skip this chunk if it does not required spacers
         for (let j = 1; j < lines.length; ++j) {
           if (diff !== lines[j] - prev[j]) {
             diff = null;
@@ -1619,7 +1629,7 @@ export class MergeView extends Panel {
    * Align the matching lines of the different editors
    */
   alignViews() {
-    let lineHeight = this._showBase
+    const lineHeight = this._showBase
       ? this._base.cm.defaultLineHeight
       : this._diffViews[0].remoteEditorWidget.cm.defaultLineHeight;
     if (this._aligning) {
@@ -1627,45 +1637,48 @@ export class MergeView extends Panel {
     }
     this._aligning = true;
     // Find matching lines
-    let linesToAlign = findAlignedLines(this._diffViews);
+    const linesToAlign = findAlignedLines(this._diffViews);
+    console.log(linesToAlign)
 
     // Function modifying DOM to perform alignment:
-    let editors: EditorView[] = [
+    const editors: EditorView[] = [
       this.base.cm,
       ...this._diffViews.map(dv => dv.remoteEditorWidget.cm),
     ];
-    let builders: RangeSetBuilder<Decoration>[] = [];
+    const builders: RangeSetBuilder<Decoration>[] = [];
     for (let i = 0; i < editors.length; i++) {
       builders.push(new RangeSetBuilder<Decoration>());
     }
 
-    let sumDeltas = new Array(editors.length).fill(0);
-    let nLines = editors.map(editor => editor.state.doc.lines);
+    const sumDeltas = new Array(editors.length).fill(0);
+    const nLines = editors.map(editor => editor.state.doc.lines);
 
-    for (let alignment_ of linesToAlign) {
-      let alignment = this._showBase ? alignment_.slice(0, 3) : alignment_;
-      let lastLine = Math.max(...alignment);
-      let lineDeltas = alignment.map(
+    for (const alignment_ of linesToAlign) {
+      const alignment = this._showBase ? alignment_.slice(0, 3) : alignment_;
+      const lastLine = Math.max(...alignment);
+      const lineDeltas = alignment.map(
         (line, i) => lastLine - line - sumDeltas[i],
       );
       // If some paddings will be before the current line, it means all other editors
       // must add a padding.
-      let minDelta = this._showBase
+      const minDelta = this._showBase
         ? Math.min(...lineDeltas)
         : Math.min(...lineDeltas.slice(1));
-      let correctedDeltas = lineDeltas.map(line => line - minDelta);
+      const correctedDeltas = lineDeltas.map(line => line - minDelta);
 
       correctedDeltas.forEach((delta, i) => {
         // Don't compute anything for the base editor if it is hidden
         if (!this._showBase && i === 0) {
           return;
         }
+        // Alignments are zero-based
         let line = alignment[i];
 
         if (delta > 0 && line < nLines[i]) {
           sumDeltas[i] += delta;
 
-          let offset = posToOffset(editors[i].state.doc, {
+          // This method include the correction from zero-based lines to one-based lines
+          const offset = posToOffset(editors[i].state.doc, {
             line,
             column: 0,
           });
@@ -1684,12 +1697,12 @@ export class MergeView extends Panel {
     }
 
     // Padding at the last line of the editor
-    let totalHeight = nLines.map((line, i) => line + sumDeltas[i]);
-    let maxHeight = Math.max(...totalHeight);
+    const totalHeight = nLines.map((line, i) => line + sumDeltas[i]);
+    const maxHeight = Math.max(...totalHeight);
     totalHeight.slice(0, this._showBase ? 3 : 4).forEach((line, i) => {
       if (maxHeight > line) {
-        let end = editors[i].state.doc.length;
-        let delta = maxHeight - line;
+        const end = editors[i].state.doc.length;
+        const delta = maxHeight - line;
         sumDeltas[i] += delta;
         builders[i].add(
           end,
@@ -1717,7 +1730,7 @@ export class MergeView extends Panel {
         continue;
       }
 
-      let decoSet: DecorationSet = builders[i].finish();
+      const decoSet: DecorationSet = builders[i].finish();
       if (
         !RangeSet.eq([decoSet], [editors[i].state.field(paddingWidgetField)])
       ) {


Test patch:
diff --git a/examples/example5/center.ipynb b/ui-tests/data/merge_test5/center.ipynb
similarity index 100%
rename from examples/example5/center.ipynb
rename to ui-tests/data/merge_test5/center.ipynb
diff --git a/examples/example5/left.ipynb b/ui-tests/data/merge_test5/left.ipynb
similarity index 100%
rename from examples/example5/left.ipynb
rename to ui-tests/data/merge_test5/left.ipynb
diff --git a/examples/example5/right.ipynb b/ui-tests/data/merge_test5/right.ipynb
similarity index 100%
rename from examples/example5/right.ipynb
rename to ui-tests/data/merge_test5/right.ipynb
diff --git a/ui-tests/tests/nbdime-merge-test1.spec.ts b/ui-tests/tests/nbdime-merge-test1.spec.ts
index dbf48598..018cf5a3 100644
--- a/ui-tests/tests/nbdime-merge-test1.spec.ts
+++ b/ui-tests/tests/nbdime-merge-test1.spec.ts
@@ -23,8 +23,10 @@ test.describe('merge test1', () => {
 
   test('choose left version for conflict', async ({ page }) => {
     await page
-      .locator('div:nth-child(2) > .jp-Merge-gutter-picker')
-      .first()
+      .locator('.cm-merge-left-editor')
+      .nth(1)  // This select the cell; 0 being the notebook metadata
+      .locator('.jp-Merge-gutter-picker')
+      .last()
       .click();
     await page.getByText('⚠').click();
     expect(await page.locator('#main').screenshot()).toMatchSnapshot();
@@ -32,10 +34,10 @@ test.describe('merge test1', () => {
 
   test('choose central version for conflict', async ({ page }) => {
     await page
-      .locator('div')
-      .filter({ hasText: /^➭➭➭$/ })
-      .locator('div')
-      .nth(3)
+      .locator('.cm-central-editor')
+      .nth(1)  // This select the cell; 0 being the notebook metadata
+      .locator('.jp-Merge-gutter-picker')
+      .nth(2)
       .click();
     await page.getByText('⚠').click();
     expect(await page.locator('#main').screenshot()).toMatchSnapshot();
@@ -43,9 +45,10 @@ test.describe('merge test1', () => {
 
   test('choose right version for conflict', async ({ page }) => {
     await page
-      .locator(
-        'div:nth-child(3) > .cm-editor > .cm-scroller > .cm-gutters > div:nth-child(2) > div:nth-child(2) > .jp-Merge-gutter-picker',
-      )
+      .locator('.cm-merge-right-editor')
+      .nth(1)  // This select the cell; 0 being the notebook metadata
+      .locator('.jp-Merge-gutter-picker')
+      .last()
       .click();
     await page.getByText('⚠').click();
     expect(await page.locator('#main').screenshot()).toMatchSnapshot();
diff --git a/ui-tests/tests/nbdime-merge-test2.spec.ts b/ui-tests/tests/nbdime-merge-test2.spec.ts
index fae54227..cf3d3704 100644
--- a/ui-tests/tests/nbdime-merge-test2.spec.ts
+++ b/ui-tests/tests/nbdime-merge-test2.spec.ts
@@ -17,27 +17,30 @@ test.describe('merge test2 ', () => {
 
   test('choose left version', async ({ page }) => {
     await page
-      .locator('div:nth-child(2) > .jp-Merge-gutter-picker')
-      .first()
+      .locator('.cm-merge-left-editor')
+      .nth(1)  // This select the cell; 0 being the notebook metadata
+      .locator('.jp-Merge-gutter-picker')
+      .last()
       .click();
     expect(await page.locator('#main').screenshot()).toMatchSnapshot();
   });
 
   test('choose central version', async ({ page }) => {
     await page
-      .locator('div')
-      .filter({ hasText: /^➭➭➭$/ })
-      .locator('div')
-      .nth(3)
+      .locator('.cm-central-editor')
+      .nth(1)  // This select the cell; 0 being the notebook metadata
+      .locator('.jp-Merge-gutter-picker')
+      .nth(2)
       .click();
     expect(await page.locator('#main').screenshot()).toMatchSnapshot();
   });
 
   test('choose right version', async ({ page }) => {
     await page
-      .locator(
-        'div:nth-child(3) > .cm-editor > .cm-scroller > .cm-gutters > div:nth-child(2) > div:nth-child(2) > .jp-Merge-gutter-picker',
-      )
+      .locator('.cm-merge-right-editor')
+      .nth(1)  // This select the cell; 0 being the notebook metadata
+      .locator('.jp-Merge-gutter-picker')
+      .last()
       .click();
     expect(await page.locator('#main').screenshot()).toMatchSnapshot();
   });
diff --git a/ui-tests/tests/nbdime-merge-test5.spec.ts b/ui-tests/tests/nbdime-merge-test5.spec.ts
new file mode 100644
index 00000000..d0b53554
--- /dev/null
+++ b/ui-tests/tests/nbdime-merge-test5.spec.ts
@@ -0,0 +1,16 @@
+import { expect, test } from '@playwright/test';
+
+test.describe('merge test5', () => {
+  test.beforeEach(async ({ page }) => {
+    await page.goto('http://localhost:41000/merge');
+    await page.locator('#merge-local').fill('data/merge_test5/left.ipynb');
+    await page.locator('#merge-base').fill('data/merge_test5/center.ipynb');
+    await page.locator('#merge-remote').fill('data/merge_test5/right.ipynb');
+    await page.getByRole('button', { name: 'Merge files' }).click();
+  });
+
+  test('take a snapshot at opening', async ({ page }) => {
+    await expect.soft(page.getByText('➭')).toHaveCount(16);
+    expect.soft(await page.locator('#main').screenshot()).toMatchSnapshot();
+  });
+});
diff --git a/ui-tests/tests/nbdime-merge-test5.spec.ts-snapshots/merge-test5-take-a-snapshot-at-opening-1-linux.png b/ui-tests/tests/nbdime-merge-test5.spec.ts-snapshots/merge-test5-take-a-snapshot-at-opening-1-linux.png
new file mode 100644
index 00000000..f4fb6938
Binary files /dev/null and b/ui-tests/tests/nbdime-merge-test5.spec.ts-snapshots/merge-test5-take-a-snapshot-at-opening-1-linux.png differ
diff --git a/ui-tests/tests/nbdime-merge-test5.spec.ts-snapshots/merge-test5-take-a-snapshot-at-opening-1-win32.png b/ui-tests/tests/nbdime-merge-test5.spec.ts-snapshots/merge-test5-take-a-snapshot-at-opening-1-win32.png
new file mode 100644
index 00000000..01f9a073
Binary files /dev/null and b/ui-tests/tests/nbdime-merge-test5.spec.ts-snapshots/merge-test5-take-a-snapshot-at-opening-1-win32.png differ