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