https://creaconnect.world/src/app-diff-lignes.js

1/* ═══════════════════════════════════════════════════════════════════════════
2 * LE DIFF, LIGNE PAR LIGNE — ET UN SEUL CALCUL POUR LE COMPTE ET L'AFFICHAGE
3 *
4 * « Le diff, au lieu de l'afficher dans Changements, il me l'affiche
5 *  [ailleurs]. »
6 *
7 * La vue « Changements » ne POUVAIT pas montrer le changement : `_resumeDuDiff`
8 * calculait la longueur de la plus longue sous-suite commune en ne gardant
9 * qu'UNE rangée de la table — assez pour dire « +12 −3 », pas pour dire QUOI.
10 * Cliquer envoyait donc vers l'atelier, c'est-à-dire ailleurs, pour voir la
11 * chose qu'on était venu voir.
12 *
13 * ── POURQUOI UN MORCEAU, ET PAS DIX LIGNES DANS LE TRONC ───────────────────
14 *
15 * C'est un calcul pur : deux textes entrent, une liste de lignes sort. Rien du
16 * DOM, rien de STATE. Le tronc ne grossit pas, et la garde peut le rejouer
17 * sans navigateur.
18 *
19 * ── L'ALGORITHME, ET POURQUOI CELUI-LÀ ─────────────────────────────────────
20 *
21 * Myers, en O(N·D) : D est le nombre de différences, pas la taille des
22 * fichiers. Sur une retouche de trois lignes dans un fichier de deux mille, D
23 * vaut six et le calcul est instantané. La table complète de la LCS, elle,
24 * ferait 1500 × 1500 entiers pour la même réponse — c'est précisément la
25 * raison pour laquelle l'ancienne version n'en gardait qu'une rangée, et donc
26 * pourquoi elle ne pouvait pas rendre les lignes.
27 *
28 * DEUX BORNES, ET ELLES DISENT DEUX CHOSES DIFFÉRENTES :
29 *   · LIGNES_MAX  — le fichier est trop gros pour qu'on le compare ;
30 *   · ECARTS_MAX  — les deux versions n'ont presque rien en commun, donc le
31 *                   diff n'apprendrait rien même calculé. On le dit au lieu de
32 *                   faire tourner la machine pour un résultat illisible.
33 * Les confondre ferait croire qu'un petit fichier entièrement réécrit est un
34 * gros fichier.
35 *
36 * ── CE QUE CE FICHIER NE FAIT PAS ──────────────────────────────────────────
37 *
38 * Il ne dessine rien. Le rendu vit dans la vue, avec le reste de son écran.
39 * ═══════════════════════════════════════════════════════════════════════════ */
40
41/* La coupe en lignes est CELLE DU COMPTE D'AVANT, mot pour mot, et elle a sa
42   raison : `''.split('\n')` rend `['']`, une ligne fantôme qui ferait dire
43   « +3 −1 » à un fichier tout neuf. Un chiffre faux d'une unité est plus
44   difficile à voir qu'un chiffre absent, donc plus dangereux. */
45function _enLignes(v) {
46  const t = String(v == null ? '' : v)
47  return t === '' ? [] : t.split('\n')
48}
49
50const DIFF_ECARTS_MAX = 400
51
52/**
53 * Le diff de deux textes, ligne par ligne.
54 *
55 * Rend `{ lignes, ajoutees, retirees, tropGrand }` où chaque ligne porte son
56 * signe : ' ' (commune), '+' (ajoutée), '-' (retirée). LES COMPTES SORTENT DE
57 * LA MÊME PASSE que les lignes — les calculer à part serait la seconde version
58 * qui dérive, et c'est exactement ce qui existait avant ce fichier.
59 *
60 * `lignesMax` est passé par l'appelant : le tronc tient déjà cette borne, et en
61 * garder une seconde ici les ferait diverger.
62 */
63function diffDesLignes(avant, apres, lignesMax) {
64  const A = _enLignes(avant)
65  const B = _enLignes(apres)
66  const max = Number.isFinite(lignesMax) ? lignesMax : 1500
67  if (A.length > max || B.length > max) {
68    return { lignes: [], ajoutees: 0, retirees: 0, tropGrand: true }
69  }
70  const maxD = Math.min(A.length + B.length, DIFF_ECARTS_MAX)
71  const decalage = maxD + 1
72  const trace = _traceDeMyers(A, B, decalage, maxD)
73  if (!trace) return { lignes: [], ajoutees: 0, retirees: 0, tropGrand: true }
74  const lignes = _relireLaTrace(trace, A, B, decalage)
75  let ajoutees = 0, retirees = 0
76  for (const l of lignes) { if (l.s === '+') ajoutees++; else if (l.s === '-') retirees++ }
77  return { lignes, ajoutees, retirees, tropGrand: false }
78}
79
80/* Myers. La passe avant avance en diagonale tant que les lignes se ressemblent
81   et garde l'état de CHAQUE profondeur ; la passe arrière remonte cette trace
82   et nomme chaque pas. Rend `null` au-delà du budget d'écarts — voir la note du
83   haut.
84
85   LE DÉCALAGE EST CALCULÉ UNE FOIS ET PARTAGÉ. Premier jet : la passe avant
86   indexait sur `maxD + 1` et la passe arrière sur `trace.length + 1`. Les deux
87   passes lisaient donc deux tableaux différents, et le diff rendu était faux
88   sans jamais lever — « une » sortait à la fois ajoutée et retirée sur un
89   exemple de cinq lignes. Un diff faux est pire qu'un diff absent : on le
90   croit. */
91function _traceDeMyers(A, B, decalage, maxD) {
92  const N = A.length, M = B.length
93  const v = new Int32Array(2 * maxD + 3)
94  const trace = []
95  for (let d = 0; d <= maxD; d++) {
96    trace.push(v.slice())          // l'état AVANT le pas d
97    for (let k = -d; k <= d; k += 2) {
98      // Descendre (une ligne ajoutée) ou aller à droite (une ligne retirée) :
99      // on suit celui des deux chemins qui est déjà allé le plus loin.
100      const descend = k === -d || (k !== d && v[k - 1 + decalage] < v[k + 1 + decalage])
101      let x = descend ? v[k + 1 + decalage] : v[k - 1 + decalage] + 1
102      let y = x - k
103      while (x < N && y < M && A[x] === B[y]) { x++; y++ }
104      v[k + decalage] = x
105      if (x >= N && y >= M) return trace
106    }
107  }
108  return null
109}
110
111function _relireLaTrace(trace, A, B, decalage) {
112  const out = []
113  let x = A.length, y = B.length
114  for (let d = trace.length - 1; d >= 0; d--) {
115    const v = trace[d]

116    const k = x - y
117    const descend = k === -d || (k !== d && v[k - 1 + decalage] < v[k + 1 + decalage])
118    const kPrec = descend ? k + 1 : k - 1
119    const xPrec = v[kPrec + decalage]
120    const yPrec = xPrec - kPrec
121    while (x > xPrec && y > yPrec) { out.push({ s: ' ', t: A[x - 1] }); x--; y-- }
122    if (d > 0) {
123      if (x === xPrec) out.push({ s: '+', t: B[y - 1] })
124      else out.push({ s: '-', t: A[x - 1] })
125    }
126    x = xPrec; y = yPrec
127  }
128  out.reverse()
129  return out
130}
131
132/* CE QU'ON MONTRE D'UN DIFF DE DEUX MILLE LIGNES : les endroits qui changent,
133   avec trois lignes autour pour savoir où on est. Le reste est du bruit — et
134   une vue qui déroule deux mille lignes inchangées ne se lit pas.
135   Rend des TRANCHES, chacune avec le rang de sa première ligne, pour que la vue
136   puisse dire « … » entre deux.
137
138   ── ET CHAQUE LIGNE PORTE SON NUMÉRO, DES DEUX CÔTÉS ─────────────────────
139
140   « La vue Changements devient le lecteur : arborescence + sections repliables
141    + numéros de ligne. »
142
143   Sans eux, une tranche prise au milieu d'un fichier ne dit pas OÙ elle est :
144   on lit trois lignes de contexte et on ne peut ni les retrouver dans
145   l'éditeur, ni en parler à quelqu'un. Le « ⋯ » entre deux tranches devient
146   alors un trou de taille inconnue.
147
148   LE NUMÉROTAGE EST ICI, PAS DANS LA VUE, et c'est la même raison que le
149   reste de ce fichier : c'est un calcul pur, dérivé des signes, et une vue qui
150   le referait tiendrait une seconde règle qui dérive. Il se compte sur TOUTES
151   les lignes avant la découpe — recompter tranche par tranche redonnerait 1 à
152   chaque tranche, c'est-à-dire un numéro faux, et un numéro faux se croit.
153
154   Une ligne ajoutée n'existe pas dans l'avant : son `a` vaut `null`, pas 0 —
155   zéro se confondrait avec « première ligne ». Idem pour `b` d'une ligne
156   retirée. */
157const DIFF_CONTEXTE = 3
158
159function tranchesDuDiff(lignes, contexte) {
160  const c = Number.isFinite(contexte) ? contexte : DIFF_CONTEXTE
161  const garde = new Array(lignes.length).fill(false)
162  lignes.forEach((l, i) => {
163    if (l.s === ' ') return
164    for (let j = Math.max(0, i - c); j <= Math.min(lignes.length - 1, i + c); j++) garde[j] = true
165  })
166  // Les rangs, comptés sur la suite ENTIÈRE — voir la note ci-dessus.
167  const numerotees = []
168  let na = 0, nb = 0
169  for (const l of lignes) {
170    if (l.s === '+') { nb++; numerotees.push({ s: l.s, t: l.t, a: null, b: nb }) }
171    else if (l.s === '-') { na++; numerotees.push({ s: l.s, t: l.t, a: na, b: null }) }
172    else { na++; nb++; numerotees.push({ s: l.s, t: l.t, a: na, b: nb }) }
173  }
174  const tranches = []
175  let courante = null
176  for (let i = 0; i < numerotees.length; i++) {
177    if (!garde[i]) { courante = null; continue }
178    const l = numerotees[i]
179    if (!courante) {
180      /* CE QUE LA TRANCHE ANNONCE, c'est le premier numéro RÉEL de chaque
181         côté — celui de sa première ligne qui existe de ce côté-là. Une
182         tranche qui commence par une ligne ajoutée n'a pas de première ligne
183         « avant » à cet endroit ; on prend celle de la première ligne du
184         diff qui en a une, sinon on ne montre pas de numéro plutôt que d'en
185         inventer un. */
186      courante = { debut: i, debutA: null, debutB: null, lignes: [] }
187      tranches.push(courante)
188    }
189    if (courante.debutA === null && l.a !== null) courante.debutA = l.a
190    if (courante.debutB === null && l.b !== null) courante.debutB = l.b
191    courante.lignes.push(l)
192  }
193  return tranches
194}
195
196if (typeof window !== 'undefined') {
197  window.diffDesLignes = diffDesLignes
198  window.tranchesDuDiff = tranchesDuDiff
199}