www/plugins-dist/revisions/inc/diff.php

   1 <?php
   2
   3 /***************************************************************************\
   4  *  SPIP, Systeme de publication pour l'internet                           *
   5  *                                                                         *
   6  *  Copyright (c) 2001-2020                                                *
   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
  19 if (!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  **/
  37 function 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  **/
  83 function 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  **/
 144 class 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  **/
 257 class 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  **/
 325 class 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  **/
 393 class 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
 492 function 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
 504 function 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 }