www/ecrire/inc/diff.php

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