source: spip-zone/_core_/plugins/revisions/inc/diff.php

Last change on this file was 113294, checked in by spip.franck@…, 2 months ago

Il parait que le futur c'est maintenant :-D

File size: 12.2 KB
Line 
1<?php
2
3/***************************************************************************\
4 *  SPIP, Systeme de publication pour l'internet                           *
5 *                                                                         *
6 *  Copyright (c) 2001-2019                                                *
7 *  Arnaud Martin, Antoine Pitrou, Philippe Riviere, Emmanuel Saint-James  *
8 *                                                                         *
9 *  Ce programme est un logiciel libre distribue sous licence GNU/GPL.     *
10 *  Pour plus de details voir le fichier COPYING.txt ou l'aide en ligne.   *
11\***************************************************************************/
12
13/**
14 * Fonctions utilitaires du plugin révisions
15 *
16 * @package SPIP\Revisions\Diff
17 **/
18
19if (!defined("_ECRIRE_INC_VERSION")) {
20        return;
21}
22
23
24// LCS (Longest Common Subsequence) en deux versions
25// (ref: http://web.archive.org/web/20071206224029/http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE208.HTM#SECTION03178000000000000000)
26
27/**
28 * Calcule un LCS (Longest Common Subsequence) simplifié
29 *
30 * Chaque chaîne est une permutation de l'autre et on passe en paramètre
31 * un des deux tableaux de correspondances
32 *
33 * @see lcs()
34 * @param array $s
35 * @return array
36 **/
37function lcs_opt($s) {
38        $n = count($s);
39        if (!$n) {
40                return array();
41        }
42        $paths = array();
43        $paths_ymin = array();
44        $max_len = 0;
45
46        // Insertion des points
47        asort($s);
48        $max = 400;
49        foreach ($s as $y => $c) {
50                if ($max-- < 0) {
51                        break;
52                }  # eviter l'explosion memoire des tres gros diff
53                for ($len = $max_len; $len > 0; $len--) {
54                        if ($paths_ymin[$len] < $y) {
55                                $paths_ymin[$len + 1] = $y;
56                                $paths[$len + 1] = $paths[$len];
57                                $paths[$len + 1][$y] = $c;
58                                break;
59                        }
60                }
61                if ($len == 0) {
62                        $paths_ymin[1] = $y;
63                        $paths[1] = array($y => $c);
64                }
65                if ($len + 1 > $max_len) {
66                        $max_len = $len + 1;
67                }
68        }
69
70        return $paths[$max_len];
71}
72
73/**
74 * Calcule un LCS (Longest Common Subsequence)
75 *
76 * Les deux chaînes n'ont pas été traitées au préalable par la fonction d'appariement
77 *
78 * @see lcs_opt()
79 * @param array $s
80 * @param array $t
81 * @return array
82 **/
83function lcs($s, $t) {
84        $n = count($s);
85        $p = count($t);
86        if (!$n || !$p) {
87                return array(0 => array(), 1 => array());
88        }
89        $paths = array();
90        $paths_ymin = array();
91        $max_len = 0;
92        $s_pos = $t_pos = array();
93
94        // Insertion des points
95        foreach ($t as $y => $c) {
96                $t_pos[trim($c)][] = $y;
97        }
98
99        foreach ($s as $x => $c) {
100                $c = trim($c);
101                if (!isset($t_pos[$c])) {
102                        continue;
103                }
104                krsort($t_pos[$c]);
105                foreach ($t_pos[$c] as $y) {
106                        for ($len = $max_len; $len > 0; $len--) {
107                                if ($paths_ymin[$len] < $y) {
108                                        $paths_ymin[$len + 1] = $y;
109                                        // On construit le resultat sous forme de chaine d'abord,
110                                        // car les tableaux de PHP sont dispendieux en taille memoire
111                                        $paths[$len + 1] = $paths[$len] . " $x,$y";
112                                        break;
113                                }
114                        }
115                        if ($len + 1 > $max_len) {
116                                $max_len = $len + 1;
117                        }
118                        if ($len == 0) {
119                                $paths_ymin[1] = $y;
120                                $paths[1] = "$x,$y";
121                        }
122                }
123        }
124        if (isset($paths[$max_len]) and $paths[$max_len]) {
125                $path = explode(" ", $paths[$max_len]);
126                $u = $v = array();
127                foreach ($path as $p) {
128                        list($x, $y) = explode(",", $p);
129                        $u[$x] = $y;
130                        $v[$y] = $x;
131                }
132
133                return array($u, $v);
134        }
135
136        return array(0 => array(), 1 => array());
137}
138
139/**
140 * Génération de diff a plusieurs étages
141 *
142 * @package SPIP\Revisions\Diff
143 **/
144class Diff {
145        /**
146         * Objet DiffX d'un texte ou partie de texte
147         *
148         * @var Object Objet Diff* (DiffTexte, DiffPara, DiffPhrase)
149         */
150        public $diff;
151        public $fuzzy;
152
153        /**
154         * Constructeur
155         *
156         * @param Object $diff Objet Diff* d'un texte ou morceau de texte
157         **/
158        public function __construct($diff) {
159                $this->diff = $diff;
160                $this->fuzzy = true;
161        }
162
163// https://code.spip.net/@comparer
164        public function comparer($new, $old) {
165                $paras = $this->diff->segmenter($new);
166                $paras_old = $this->diff->segmenter($old);
167                if ($this->diff->fuzzy()) {
168                        list($trans_rev, $trans) = apparier_paras($paras_old, $paras);
169                        $lcs = lcs_opt($trans);
170                        $lcs_rev = array_flip($lcs);
171                } else {
172                        list($trans_rev, $trans) = lcs($paras_old, $paras);
173                        $lcs = $trans;
174                        $lcs_rev = $trans_rev;
175                }
176
177                reset($paras_old);
178                reset($paras);
179                reset($lcs);
180                unset($i_old);
181                $fin_old = false;
182                foreach ($paras as $i => $p) {
183                        if (!isset($trans[$i])) {
184                                // Paragraphe ajoute
185                                $this->diff->ajouter($p);
186                                continue;
187                        }
188                        $j = $trans[$i];
189                        if (!isset($lcs[$i])) {
190                                // Paragraphe deplace
191                                $this->diff->deplacer($p, $paras_old[$j]);
192                                continue;
193                        }
194                        if (!$fin_old) {
195                                // Paragraphes supprimes jusqu'au paragraphe courant
196                                if (!isset($i_old)) {
197                                        $i_old = key($paras_old);
198                                        $p_old = current($paras_old);
199                                        next($paras_old);
200                                        if (!$p_old) {
201                                                $fin_old = true;
202                                        }
203                                }
204                                while (!$fin_old && $i_old < $j) {
205                                        if (!isset($trans_rev[$i_old])) {
206                                                $this->diff->supprimer($p_old);
207                                        }
208                                        unset($i_old);
209                                        $i_old = key($paras_old);
210                                        $p_old = current($paras_old);
211                                        next($paras_old);
212                                        if (!$p_old) {
213                                                $fin_old = true;
214                                        }
215                                }
216                        }
217                        // Paragraphe n'ayant pas change de place
218                        $this->diff->comparer($p, $paras_old[$j]);
219                }
220                // Paragraphes supprimes a la fin du texte
221                if (!$fin_old) {
222                        if (!isset($i_old)) {
223                                $i_old = key($paras_old);
224                                $p_old = current($paras_old);
225                                next($paras_old);
226                                if (!strlen($p_old)) {
227                                        $fin_old = true;
228                                }
229                        }
230                        while (!$fin_old) {
231                                if (!isset($trans_rev[$i_old])) {
232                                        $this->diff->supprimer($p_old);
233                                }
234                                $i_old = key($paras_old);
235                                $p_old = current($paras_old);
236                                next($paras_old);
237                                if (!$p_old) {
238                                        $fin_old = true;
239                                }
240                        }
241                }
242                if (isset($i_old)) {
243                        if (!isset($trans_rev[$i_old])) {
244                                $this->diff->supprimer($p_old);
245                        }
246                }
247
248                return $this->diff->resultat();
249        }
250}
251
252/**
253 * Génération de diff sur un Texte
254 *
255 * @package SPIP\Revisions\Diff
256 **/
257class DiffTexte {
258        public $r;
259
260        /**
261         * Constructeur
262         **/
263        public function __construct() {
264                $this->r = "";
265        }
266
267// https://code.spip.net/@_diff
268        public function _diff($p, $p_old) {
269                $diff = new Diff(new DiffPara);
270
271                return $diff->comparer($p, $p_old);
272        }
273
274// https://code.spip.net/@fuzzy
275        public function fuzzy() {
276                return true;
277        }
278
279        /**
280         * Découper les paragraphes d'un texte en fragments
281         *
282         * @param string $texte Texte à fragmenter
283         * @return string[]       Tableau de fragments (paragraphes)
284         **/
285        public function segmenter($texte) {
286                return separer_paras($texte);
287        }
288
289        // NB :  rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies"
290// https://code.spip.net/@ajouter
291        public function ajouter($p) {
292                $p = trim($p);
293                $this->r .= "\n\n\n<span class=\"diff-para-ajoute\" title=\"" . _T('revisions:diff_para_ajoute') . "\">" . $p . "</span rem=\"diff-\">";
294        }
295
296// https://code.spip.net/@supprimer
297        public function supprimer($p_old) {
298                $p_old = trim($p_old);
299                $this->r .= "\n\n\n<span class=\"diff-para-supprime\" title=\"" . _T('revisions:diff_para_supprime') . "\">" . $p_old . "</span rem=\"diff-\">";
300        }
301
302// https://code.spip.net/@deplacer
303        public function deplacer($p, $p_old) {
304                $this->r .= "\n\n\n<span class=\"diff-para-deplace\" title=\"" . _T('revisions:diff_para_deplace') . "\">";
305                $this->r .= trim($this->_diff($p, $p_old));
306                $this->r .= "</span rem=\"diff-\">";
307        }
308
309// https://code.spip.net/@comparer
310        public function comparer($p, $p_old) {
311                $this->r .= "\n\n\n" . $this->_diff($p, $p_old);
312        }
313
314// https://code.spip.net/@resultat
315        public function resultat() {
316                return $this->r;
317        }
318}
319
320/**
321 * Génération de diff sur un paragraphe
322 *
323 * @package SPIP\Revisions\Diff
324 **/
325class DiffPara {
326        public $r;
327
328        /** Constructeur */
329        public function __construct() {
330                $this->r = "";
331        }
332
333// https://code.spip.net/@_diff
334        public function _diff($p, $p_old) {
335                $diff = new Diff(new DiffPhrase);
336
337                return $diff->comparer($p, $p_old);
338        }
339
340// https://code.spip.net/@fuzzy
341        public function fuzzy() {
342                return true;
343        }
344
345// https://code.spip.net/@segmenter
346        public function segmenter($texte) {
347                $paras = array();
348                $texte = trim($texte);
349                while (preg_match('/[\.!\?\]]+\s*/u', $texte, $regs)) {
350                        $p = strpos($texte, $regs[0]) + strlen($regs[0]);
351                        $paras[] = substr($texte, 0, $p);
352                        $texte = substr($texte, $p);
353                }
354                if ($texte) {
355                        $paras[] = $texte;
356                }
357
358                return $paras;
359        }
360
361// https://code.spip.net/@ajouter
362        public function ajouter($p) {
363                $this->r .= "<span class=\"diff-ajoute\" title=\"" . _T('revisions:diff_texte_ajoute') . "\">" . $p . "</span rem=\"diff-\">";
364        }
365
366// https://code.spip.net/@supprimer
367        public function supprimer($p_old) {
368                $this->r .= "<span class=\"diff-supprime\" title=\"" . _T('revisions:diff_texte_supprime') . "\">" . $p_old . "</span rem=\"diff-\">";
369        }
370
371// https://code.spip.net/@deplacer
372        public function deplacer($p, $p_old) {
373                $this->r .= "<span class=\"diff-deplace\" title=\"" . _T('revisions:diff_texte_deplace') . "\">" . $this->_diff($p,
374                                $p_old) . "</span rem=\"diff-\">";
375        }
376
377// https://code.spip.net/@comparer
378        public function comparer($p, $p_old) {
379                $this->r .= $this->_diff($p, $p_old);
380        }
381
382// https://code.spip.net/@resultat
383        public function resultat() {
384                return $this->r;
385        }
386}
387
388/**
389 * Génération de diff sur une phrase
390 *
391 * @package SPIP\Revisions\Diff
392 **/
393class DiffPhrase {
394        public $r;
395
396        /** Constructeur */
397        public function __construct() {
398                $this->r = "";
399        }
400
401// https://code.spip.net/@fuzzy
402        public function fuzzy() {
403                return false;
404        }
405
406// https://code.spip.net/@segmenter
407        public function segmenter($texte) {
408                $paras = array();
409                if (test_pcre_unicode()) {
410                        $punct = '([[:punct:]]|' . plage_punct_unicode() . ')';
411                        $mode = 'u';
412                } else {
413                        // Plages de poncutation pour preg_match bugge (ha ha)
414                        $punct = '([^\w\s\x80-\xFF]|' . plage_punct_unicode() . ')';
415                        $mode = '';
416                }
417                $preg = '/(' . $punct . '+)(\s+|$)|(\s+)(' . $punct . '*)/' . $mode;
418                while (preg_match($preg, $texte, $regs)) {
419                        $p = strpos($texte, $regs[0]);
420                        $l = strlen($regs[0]);
421                        $punct = $regs[1] ? $regs[1] : $regs[6];
422                        $milieu = "";
423                        if ($punct) {
424                                // notes
425                                if ($punct == '[[') {
426                                        $avant = substr($texte, 0, $p) . $regs[5] . $punct;
427                                        $texte = $regs[4] . substr($texte, $p + $l);
428                                } else {
429                                        if ($punct == ']]') {
430                                                $avant = substr($texte, 0, $p) . $regs[5] . $punct;
431                                                $texte = substr($texte, $p + $l);
432                                        } // Attacher les raccourcis fermants au mot precedent
433                                        else {
434                                                if (preg_match(',^[\]}]+$,', $punct)) {
435                                                        $avant = substr($texte, 0, $p) . (isset($regs[5]) ? $regs[5] : '') . $punct;
436                                                        $texte = $regs[4] . substr($texte, $p + $l);
437                                                } // Attacher les raccourcis ouvrants au mot suivant
438                                                else {
439                                                        if (isset($regs[5]) && $regs[5] && preg_match(',^[\[{]+$,', $punct)) {
440                                                                $avant = substr($texte, 0, $p) . $regs[5];
441                                                                $texte = $punct . substr($texte, $p + $l);
442                                                        } // Les autres signes de ponctuation sont des mots a part entiere
443                                                        else {
444                                                                $avant = substr($texte, 0, $p);
445                                                                $milieu = $regs[0];
446                                                                $texte = substr($texte, $p + $l);
447                                                        }
448                                                }
449                                        }
450                                }
451                        } else {
452                                $avant = substr($texte, 0, $p + $l);
453                                $texte = substr($texte, $p + $l);
454                        }
455                        if ($avant) {
456                                $paras[] = $avant;
457                        }
458                        if ($milieu) {
459                                $paras[] = $milieu;
460                        }
461                }
462                if ($texte) {
463                        $paras[] = $texte;
464                }
465
466                return $paras;
467        }
468
469// https://code.spip.net/@ajouter
470        public function ajouter($p) {
471                $this->r .= "<span class=\"diff-ajoute\" title=\"" . _T('revisions:diff_texte_ajoute') . "\">" . $p . "</span rem=\"diff-\"> ";
472        }
473
474// https://code.spip.net/@supprimer
475        public function supprimer($p_old) {
476                $this->r .= "<span class=\"diff-supprime\" title=\"" . _T('revisions:diff_texte_supprime') . "\">" . $p_old . "</span rem=\"diff-\"> ";
477        }
478
479// https://code.spip.net/@comparer
480        public function comparer($p, $p_old) {
481                $this->r .= $p;
482        }
483
484// https://code.spip.net/@resultat
485        public function resultat() {
486                return $this->r;
487        }
488}
489
490
491// https://code.spip.net/@preparer_diff
492function preparer_diff($texte) {
493        include_spip('inc/charsets');
494
495        $charset = $GLOBALS['meta']['charset'];
496        if ($charset == 'utf-8') {
497                return unicode_to_utf_8(html2unicode($texte));
498        }
499
500        return unicode_to_utf_8(html2unicode(charset2unicode($texte, $charset, true)));
501}
502
503// https://code.spip.net/@afficher_diff
504function afficher_diff($texte) {
505        $charset = $GLOBALS['meta']['charset'];
506        if ($charset == 'utf-8') {
507                return $texte;
508        }
509
510        return charset2unicode($texte, 'utf-8');
511}
Note: See TracBrowser for help on using the repository browser.