3 /***************************************************************************\
4 * SPIP, Systeme de publication pour l'internet *
6 * Copyright (c) 2001-2020 *
7 * Arnaud Martin, Antoine Pitrou, Philippe Riviere, Emmanuel Saint-James *
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 \***************************************************************************/
14 * Fonctions utilitaires du plugin révisions
16 * @package SPIP\Revisions\Diff
19 if (!defined("_ECRIRE_INC_VERSION")) {
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)
28 * Calcule un LCS (Longest Common Subsequence) simplifié
30 * Chaque chaîne est une permutation de l'autre et on passe en paramètre
31 * un des deux tableaux de correspondances
37 function lcs_opt($s) {
43 $paths_ymin = array();
46 // Insertion des points
49 foreach ($s as $y => $c) {
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;
63 $paths[1] = array($y => $c);
65 if ($len +
1 > $max_len) {
70 return $paths[$max_len];
74 * Calcule un LCS (Longest Common Subsequence)
76 * Les deux chaînes n'ont pas été traitées au préalable par la fonction d'appariement
83 function lcs($s, $t) {
87 return array(0 => array(), 1 => array());
90 $paths_ymin = array();
92 $s_pos = $t_pos = array();
94 // Insertion des points
95 foreach ($t as $y => $c) {
96 $t_pos[trim($c)][] = $y;
99 foreach ($s as $x => $c) {
101 if (!isset($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";
115 if ($len +
1 > $max_len) {
124 if (isset($paths[$max_len]) and $paths[$max_len]) {
125 $path = explode(" ", $paths[$max_len]);
127 foreach ($path as $p) {
128 list($x, $y) = explode(",", $p);
133 return array($u, $v);
136 return array(0 => array(), 1 => array());
140 * Génération de diff a plusieurs étages
142 * @package SPIP\Revisions\Diff
146 * Objet DiffX d'un texte ou partie de texte
148 * @var Object Objet Diff* (DiffTexte, DiffPara, DiffPhrase)
156 * @param Object $diff Objet Diff* d'un texte ou morceau de texte
158 public function __construct($diff) {
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);
172 list($trans_rev, $trans) = lcs($paras_old, $paras);
174 $lcs_rev = $trans_rev;
182 foreach ($paras as $i => $p) {
183 if (!isset($trans[$i])) {
185 $this->diff
->ajouter($p);
189 if (!isset($lcs[$i])) {
190 // Paragraphe deplace
191 $this->diff
->deplacer($p, $paras_old[$j]);
195 // Paragraphes supprimes jusqu'au paragraphe courant
196 if (!isset($i_old)) {
197 list($i_old, $p_old) = each($paras_old);
202 while (!$fin_old && $i_old < $j) {
203 if (!isset($trans_rev[$i_old])) {
204 $this->diff
->supprimer($p_old);
207 list($i_old, $p_old) = each($paras_old);
213 // Paragraphe n'ayant pas change de place
214 $this->diff
->comparer($p, $paras_old[$j]);
216 // Paragraphes supprimes a la fin du texte
218 if (!isset($i_old)) {
219 list($i_old, $p_old) = each($paras_old);
220 if (!strlen($p_old)) {
225 if (!isset($trans_rev[$i_old])) {
226 $this->diff
->supprimer($p_old);
228 list($i_old, $p_old) = each($paras_old);
235 if (!isset($trans_rev[$i_old])) {
236 $this->diff
->supprimer($p_old);
240 return $this->diff
->resultat();
245 * Génération de diff sur un Texte
247 * @package SPIP\Revisions\Diff
255 public function __construct() {
259 // https://code.spip.net/@_diff
260 public function _diff($p, $p_old) {
261 $diff = new Diff(new DiffPara
);
263 return $diff->comparer($p, $p_old);
266 // https://code.spip.net/@fuzzy
267 public function fuzzy() {
272 * Découper les paragraphes d'un texte en fragments
274 * @param string $texte Texte à fragmenter
275 * @return string[] Tableau de fragments (paragraphes)
277 public function segmenter($texte) {
278 return separer_paras($texte);
281 // NB : rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies"
282 // https://code.spip.net/@ajouter
283 public function ajouter($p) {
285 $this->r
.= "\n\n\n<span class=\"diff-para-ajoute\" title=\"" . _T('revisions:diff_para_ajoute') . "\">" . $p . "</span rem=\"diff-\">";
288 // https://code.spip.net/@supprimer
289 public 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-\">";
294 // https://code.spip.net/@deplacer
295 public 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-\">";
301 // https://code.spip.net/@comparer
302 public function comparer($p, $p_old) {
303 $this->r
.= "\n\n\n" . $this->_diff($p, $p_old);
306 // https://code.spip.net/@resultat
307 public function resultat() {
313 * Génération de diff sur un paragraphe
315 * @package SPIP\Revisions\Diff
321 public function __construct() {
325 // https://code.spip.net/@_diff
326 public function _diff($p, $p_old) {
327 $diff = new Diff(new DiffPhrase
);
329 return $diff->comparer($p, $p_old);
332 // https://code.spip.net/@fuzzy
333 public function fuzzy() {
337 // https://code.spip.net/@segmenter
338 public function segmenter($texte) {
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);
353 // https://code.spip.net/@ajouter
354 public function ajouter($p) {
355 $this->r
.= "<span class=\"diff-ajoute\" title=\"" . _T('revisions:diff_texte_ajoute') . "\">" . $p . "</span rem=\"diff-\">";
358 // https://code.spip.net/@supprimer
359 public function supprimer($p_old) {
360 $this->r
.= "<span class=\"diff-supprime\" title=\"" . _T('revisions:diff_texte_supprime') . "\">" . $p_old . "</span rem=\"diff-\">";
363 // https://code.spip.net/@deplacer
364 public 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-\">";
369 // https://code.spip.net/@comparer
370 public function comparer($p, $p_old) {
371 $this->r
.= $this->_diff($p, $p_old);
374 // https://code.spip.net/@resultat
375 public function resultat() {
381 * Génération de diff sur une phrase
383 * @package SPIP\Revisions\Diff
389 public function __construct() {
393 // https://code.spip.net/@fuzzy
394 public function fuzzy() {
398 // https://code.spip.net/@segmenter
399 public function segmenter($texte) {
401 if (test_pcre_unicode()) {
402 $punct = '([[:punct:]]|' . plage_punct_unicode() . ')';
405 // Plages de poncutation pour preg_match bugge (ha ha)
406 $punct = '([^\w\s\x80-\xFF]|' . plage_punct_unicode() . ')';
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];
417 if ($punct == '[[') {
418 $avant = substr($texte, 0, $p) . $regs[5] . $punct;
419 $texte = $regs[4] . substr($texte, $p +
$l);
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
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
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
436 $avant = substr($texte, 0, $p);
438 $texte = substr($texte, $p +
$l);
444 $avant = substr($texte, 0, $p +
$l);
445 $texte = substr($texte, $p +
$l);
461 // https://code.spip.net/@ajouter
462 public function ajouter($p) {
463 $this->r
.= "<span class=\"diff-ajoute\" title=\"" . _T('revisions:diff_texte_ajoute') . "\">" . $p . "</span rem=\"diff-\"> ";
466 // https://code.spip.net/@supprimer
467 public function supprimer($p_old) {
468 $this->r
.= "<span class=\"diff-supprime\" title=\"" . _T('revisions:diff_texte_supprime') . "\">" . $p_old . "</span rem=\"diff-\"> ";
471 // https://code.spip.net/@comparer
472 public function comparer($p, $p_old) {
476 // https://code.spip.net/@resultat
477 public function resultat() {
483 // https://code.spip.net/@preparer_diff
484 function preparer_diff($texte) {
485 include_spip('inc/charsets');
487 $charset = $GLOBALS['meta']['charset'];
488 if ($charset == 'utf-8') {
489 return unicode_to_utf_8(html2unicode($texte));
492 return unicode_to_utf_8(html2unicode(charset2unicode($texte, $charset, true)));
495 // https://code.spip.net/@afficher_diff
496 function afficher_diff($texte) {
497 $charset = $GLOBALS['meta']['charset'];
498 if ($charset == 'utf-8') {
502 return charset2unicode($texte, 'utf-8');