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

   1 <?php
   2
   3 /***************************************************************************\
   4  *  SPIP, Systeme de publication pour l'internet                           *
   5  *                                                                         *
   6  *  Copyright (c) 2001-2016                                                *
   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                                         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  **/
 249 class DiffTexte {
 250         public $r;
 251
 252         /**
 253          * Constructeur
 254          **/
 255         public function __construct() {
 256                 $this->r = "";
 257         }
 258
 259 // https://code.spip.net/@_diff
 260         public function _diff($p, $p_old) {
 261                 $diff = new Diff(new DiffPara);
 262
 263                 return $diff->comparer($p, $p_old);
 264         }
 265
 266 // https://code.spip.net/@fuzzy
 267         public 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         public function segmenter($texte) {
 278                 return separer_paras($texte);
 279         }
 280
 281         // NB :  rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies"
 282 // https://code.spip.net/@ajouter
 283         public 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 // 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-\">";
 292         }
 293
 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-\">";
 299         }
 300
 301 // https://code.spip.net/@comparer
 302         public function comparer($p, $p_old) {
 303                 $this->r .= "\n\n\n" . $this->_diff($p, $p_old);
 304         }
 305
 306 // https://code.spip.net/@resultat
 307         public 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  **/
 317 class DiffPara {
 318         public $r;
 319
 320         /** Constructeur */
 321         public function __construct() {
 322                 $this->r = "";
 323         }
 324
 325 // https://code.spip.net/@_diff
 326         public function _diff($p, $p_old) {
 327                 $diff = new Diff(new DiffPhrase);
 328
 329                 return $diff->comparer($p, $p_old);
 330         }
 331
 332 // https://code.spip.net/@fuzzy
 333         public function fuzzy() {
 334                 return true;
 335         }
 336
 337 // https://code.spip.net/@segmenter
 338         public 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 // 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-\">";
 356         }
 357
 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-\">";
 361         }
 362
 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-\">";
 367         }
 368
 369 // https://code.spip.net/@comparer
 370         public function comparer($p, $p_old) {
 371                 $this->r .= $this->_diff($p, $p_old);
 372         }
 373
 374 // https://code.spip.net/@resultat
 375         public 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  **/
 385 class DiffPhrase {
 386         public $r;
 387
 388         /** Constructeur */
 389         public function __construct() {
 390                 $this->r = "";
 391         }
 392
 393 // https://code.spip.net/@fuzzy
 394         public function fuzzy() {
 395                 return false;
 396         }
 397
 398 // https://code.spip.net/@segmenter
 399         public 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 // 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-\"> ";
 464         }
 465
 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-\"> ";
 469         }
 470
 471 // https://code.spip.net/@comparer
 472         public function comparer($p, $p_old) {
 473                 $this->r .= $p;
 474         }
 475
 476 // https://code.spip.net/@resultat
 477         public function resultat() {
 478                 return $this->r;
 479         }
 480 }
 481
 482
 483 // https://code.spip.net/@preparer_diff
 484 function 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 // https://code.spip.net/@afficher_diff
 496 function 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 }