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

Last change on this file since 93622 was 93622, checked in by cedric@…, 5 years ago

Indentation et regles de codage selon http://www.spip.net/fr_article3497.html#regles_codage

File size: 11.8 KB
Line 
1<?php
2
3/***************************************************************************\
4 *  SPIP, Systeme de publication pour l'internet                           *
5 *                                                                         *
6 *  Copyright (c) 2001-2015                                                *
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        var $diff;
151        var $fuzzy;
152
153        /**
154         * Constructeur
155         *
156         * @param Object $diff Objet Diff* d'un texte ou morceau de texte
157         **/
158        function __construct($diff) {
159                $this->diff = $diff;
160                $this->fuzzy = true;
161        }
162
163// http://code.spip.net/@comparer
164        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                                        list($i_old, $p_old) = each($paras_old);
198                                        if (!$p_old) {
199                                                $fin_old = true;
200                                        }
201                                }
202                                while (!$fin_old && $i_old < $j) {
203                                        if (!isset($trans_rev[$i_old])) {
204                                                $this->diff->supprimer($p_old);
205                                        }
206                                        unset($i_old);
207                                        list($i_old, $p_old) = each($paras_old);
208                                        if (!$p_old) {
209                                                $fin_old = true;
210                                        }
211                                }
212                        }
213                        // Paragraphe n'ayant pas change de place
214                        $this->diff->comparer($p, $paras_old[$j]);
215                }
216                // Paragraphes supprimes a la fin du texte
217                if (!$fin_old) {
218                        if (!isset($i_old)) {
219                                list($i_old, $p_old) = each($paras_old);
220                                if (!strlen($p_old)) {
221                                        $fin_old = true;
222                                }
223                        }
224                        while (!$fin_old) {
225                                if (!isset($trans_rev[$i_old])) {
226                                        $this->diff->supprimer($p_old);
227                                }
228                                list($i_old, $p_old) = each($paras_old);
229                                if (!$p_old) {
230                                        $fin_old = true;
231                                }
232                        }
233                }
234                if (isset($i_old)) {
235                        if (!isset($trans_rev[$i_old])) {
236                                $this->diff->supprimer($p_old);
237                        }
238                }
239
240                return $this->diff->resultat();
241        }
242}
243
244/**
245 * Génération de diff sur un Texte
246 *
247 * @package SPIP\Revisions\Diff
248 **/
249class DiffTexte {
250        var $r;
251
252        /**
253         * Constructeur
254         **/
255        function __construct() {
256                $this->r = "";
257        }
258
259// http://code.spip.net/@_diff
260        function _diff($p, $p_old) {
261                $diff = new Diff(new DiffPara);
262
263                return $diff->comparer($p, $p_old);
264        }
265
266// http://code.spip.net/@fuzzy
267        function fuzzy() {
268                return true;
269        }
270
271        /**
272         * Découper les paragraphes d'un texte en fragments
273         *
274         * @param string $texte Texte à fragmenter
275         * @return string[]       Tableau de fragments (paragraphes)
276         **/
277        function segmenter($texte) {
278                return separer_paras($texte);
279        }
280
281        // NB :  rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies"
282// http://code.spip.net/@ajouter
283        function ajouter($p) {
284                $p = trim($p);
285                $this->r .= "\n\n\n<span class=\"diff-para-ajoute\" title=\"" . _T('revisions:diff_para_ajoute') . "\">" . $p . "</span rem=\"diff-\">";
286        }
287
288// http://code.spip.net/@supprimer
289        function supprimer($p_old) {
290                $p_old = trim($p_old);
291                $this->r .= "\n\n\n<span class=\"diff-para-supprime\" title=\"" . _T('revisions:diff_para_supprime') . "\">" . $p_old . "</span rem=\"diff-\">";
292        }
293
294// http://code.spip.net/@deplacer
295        function deplacer($p, $p_old) {
296                $this->r .= "\n\n\n<span class=\"diff-para-deplace\" title=\"" . _T('revisions:diff_para_deplace') . "\">";
297                $this->r .= trim($this->_diff($p, $p_old));
298                $this->r .= "</span rem=\"diff-\">";
299        }
300
301// http://code.spip.net/@comparer
302        function comparer($p, $p_old) {
303                $this->r .= "\n\n\n" . $this->_diff($p, $p_old);
304        }
305
306// http://code.spip.net/@resultat
307        function resultat() {
308                return $this->r;
309        }
310}
311
312/**
313 * Génération de diff sur un paragraphe
314 *
315 * @package SPIP\Revisions\Diff
316 **/
317class DiffPara {
318        var $r;
319
320        /** Constructeur */
321        function __construct() {
322                $this->r = "";
323        }
324
325// http://code.spip.net/@_diff
326        function _diff($p, $p_old) {
327                $diff = new Diff(new DiffPhrase);
328
329                return $diff->comparer($p, $p_old);
330        }
331
332// http://code.spip.net/@fuzzy
333        function fuzzy() {
334                return true;
335        }
336
337// http://code.spip.net/@segmenter
338        function segmenter($texte) {
339                $paras = array();
340                $texte = trim($texte);
341                while (preg_match('/[\.!\?\]]+\s*/u', $texte, $regs)) {
342                        $p = strpos($texte, $regs[0])+strlen($regs[0]);
343                        $paras[] = substr($texte, 0, $p);
344                        $texte = substr($texte, $p);
345                }
346                if ($texte) {
347                        $paras[] = $texte;
348                }
349
350                return $paras;
351        }
352
353// http://code.spip.net/@ajouter
354        function ajouter($p) {
355                $this->r .= "<span class=\"diff-ajoute\" title=\"" . _T('revisions:diff_texte_ajoute') . "\">" . $p . "</span rem=\"diff-\">";
356        }
357
358// http://code.spip.net/@supprimer
359        function supprimer($p_old) {
360                $this->r .= "<span class=\"diff-supprime\" title=\"" . _T('revisions:diff_texte_supprime') . "\">" . $p_old . "</span rem=\"diff-\">";
361        }
362
363// http://code.spip.net/@deplacer
364        function deplacer($p, $p_old) {
365                $this->r .= "<span class=\"diff-deplace\" title=\"" . _T('revisions:diff_texte_deplace') . "\">" . $this->_diff($p,
366                                $p_old) . "</span rem=\"diff-\">";
367        }
368
369// http://code.spip.net/@comparer
370        function comparer($p, $p_old) {
371                $this->r .= $this->_diff($p, $p_old);
372        }
373
374// http://code.spip.net/@resultat
375        function resultat() {
376                return $this->r;
377        }
378}
379
380/**
381 * Génération de diff sur une phrase
382 *
383 * @package SPIP\Revisions\Diff
384 **/
385class DiffPhrase {
386        var $r;
387
388        /** Constructeur */
389        function __construct() {
390                $this->r = "";
391        }
392
393// http://code.spip.net/@fuzzy
394        function fuzzy() {
395                return false;
396        }
397
398// http://code.spip.net/@segmenter
399        function segmenter($texte) {
400                $paras = array();
401                if (test_pcre_unicode()) {
402                        $punct = '([[:punct:]]|' . plage_punct_unicode() . ')';
403                        $mode = 'u';
404                } else {
405                        // Plages de poncutation pour preg_match bugge (ha ha)
406                        $punct = '([^\w\s\x80-\xFF]|' . plage_punct_unicode() . ')';
407                        $mode = '';
408                }
409                $preg = '/(' . $punct . '+)(\s+|$)|(\s+)(' . $punct . '*)/' . $mode;
410                while (preg_match($preg, $texte, $regs)) {
411                        $p = strpos($texte, $regs[0]);
412                        $l = strlen($regs[0]);
413                        $punct = $regs[1] ? $regs[1] : $regs[6];
414                        $milieu = "";
415                        if ($punct) {
416                                // notes
417                                if ($punct == '[[') {
418                                        $avant = substr($texte, 0, $p) . $regs[5] . $punct;
419                                        $texte = $regs[4] . substr($texte, $p+$l);
420                                } else {
421                                        if ($punct == ']]') {
422                                                $avant = substr($texte, 0, $p) . $regs[5] . $punct;
423                                                $texte = substr($texte, $p+$l);
424                                        } // Attacher les raccourcis fermants au mot precedent
425                                        else {
426                                                if (preg_match(',^[\]}]+$,', $punct)) {
427                                                        $avant = substr($texte, 0, $p) . (isset($regs[5]) ? $regs[5] : '') . $punct;
428                                                        $texte = $regs[4] . substr($texte, $p+$l);
429                                                } // Attacher les raccourcis ouvrants au mot suivant
430                                                else {
431                                                        if (isset($regs[5]) && $regs[5] && preg_match(',^[\[{]+$,', $punct)) {
432                                                                $avant = substr($texte, 0, $p) . $regs[5];
433                                                                $texte = $punct . substr($texte, $p+$l);
434                                                        } // Les autres signes de ponctuation sont des mots a part entiere
435                                                        else {
436                                                                $avant = substr($texte, 0, $p);
437                                                                $milieu = $regs[0];
438                                                                $texte = substr($texte, $p+$l);
439                                                        }
440                                                }
441                                        }
442                                }
443                        } else {
444                                $avant = substr($texte, 0, $p+$l);
445                                $texte = substr($texte, $p+$l);
446                        }
447                        if ($avant) {
448                                $paras[] = $avant;
449                        }
450                        if ($milieu) {
451                                $paras[] = $milieu;
452                        }
453                }
454                if ($texte) {
455                        $paras[] = $texte;
456                }
457
458                return $paras;
459        }
460
461// http://code.spip.net/@ajouter
462        function ajouter($p) {
463                $this->r .= "<span class=\"diff-ajoute\" title=\"" . _T('revisions:diff_texte_ajoute') . "\">" . $p . "</span rem=\"diff-\"> ";
464        }
465
466// http://code.spip.net/@supprimer
467        function supprimer($p_old) {
468                $this->r .= "<span class=\"diff-supprime\" title=\"" . _T('revisions:diff_texte_supprime') . "\">" . $p_old . "</span rem=\"diff-\"> ";
469        }
470
471// http://code.spip.net/@comparer
472        function comparer($p, $p_old) {
473                $this->r .= $p;
474        }
475
476// http://code.spip.net/@resultat
477        function resultat() {
478                return $this->r;
479        }
480}
481
482
483// http://code.spip.net/@preparer_diff
484function preparer_diff($texte) {
485        include_spip('inc/charsets');
486
487        $charset = $GLOBALS['meta']['charset'];
488        if ($charset == 'utf-8') {
489                return unicode_to_utf_8(html2unicode($texte));
490        }
491
492        return unicode_to_utf_8(html2unicode(charset2unicode($texte, $charset, true)));
493}
494
495// http://code.spip.net/@afficher_diff
496function afficher_diff($texte) {
497        $charset = $GLOBALS['meta']['charset'];
498        if ($charset == 'utf-8') {
499                return $texte;
500        }
501
502        return charset2unicode($texte, 'utf-8');
503}
504
505
506?>
Note: See TracBrowser for help on using the repository browser.