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

Last change on this file since 93105 was 93105, checked in by marcimat@…, 4 years ago

Compat PHP7

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