3 /***************************************************************************\
4 * SPIP, Systeme de publication pour l'internet *
6 * Copyright (c) 2001-2014 *
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 if (!defined("_ECRIRE_INC_VERSION")) return;
17 // LCS (Longest Common Subsequence) en deux versions
18 // (ref: http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE208.HTM)
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) {
25 if (!$n) return array();
27 $paths_ymin = array();
30 // Insertion des points
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;
45 $paths[1] = array($y => $c);
47 if ($len +
1 > $max_len) $max_len = $len +
1;
49 return $paths[$max_len];
52 // Version normale : les deux chaines n'ont pas ete traitees au prealable
53 // par la fonction d'appariement
54 // http://doc.spip.org/@lcs
55 function lcs($s, $t) {
58 if (!$n ||
!$p) return array(0 => array(), 1 => array());
60 $paths_ymin = array();
62 $s_pos = $t_pos = array();
64 // Insertion des points
65 foreach ($t as $y => $c) $t_pos[trim($c)][] = $y;
67 foreach ($s as $x => $c) {
69 if (!isset($t_pos[$c])) continue;
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";
81 if ($len +
1 > $max_len) $max_len = $len +
1;
88 if (isset($paths[$max_len]) AND $paths[$max_len]) {
89 $path = explode(" ", $paths[$max_len]);
91 foreach ($path as $p) {
92 list($x, $y) = explode(",", $p);
98 return array(0 => array(), 1 => array());
102 // Generation de diff a plusieurs etages
105 // http://doc.spip.org/@Diff
110 // http://doc.spip.org/@Diff
111 function Diff($diff) {
116 // http://doc.spip.org/@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);
126 list($trans_rev, $trans) = lcs($paras_old, $paras);
128 $lcs_rev = $trans_rev;
136 foreach ($paras as $i => $p) {
137 if (!isset($trans[$i])) {
139 $this->diff
->ajouter($p);
143 if (!isset($lcs[$i])) {
144 // Paragraphe deplace
145 $this->diff
->deplacer($p, $paras_old[$j]);
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;
154 while (!$fin_old && $i_old < $j) {
155 if (!isset($trans_rev[$i_old])) {
156 $this->diff
->supprimer($p_old);
159 list($i_old, $p_old) = each($paras_old);
160 if (!$p_old) $fin_old = true;
163 // Paragraphe n'ayant pas change de place
164 $this->diff
->comparer($p, $paras_old[$j]);
166 // Paragraphes supprimes a la fin du texte
168 if (!isset($i_old)) {
169 list($i_old, $p_old) = each($paras_old);
170 if (!strlen($p_old)) $fin_old = true;
173 if (!isset($trans_rev[$i_old])) {
174 $this->diff
->supprimer($p_old);
176 list($i_old, $p_old) = each($paras_old);
177 if (!$p_old) $fin_old = true;
181 if (!isset($trans_rev[$i_old])) {
182 $this->diff
->supprimer($p_old);
185 return $this->diff
->resultat();
189 // http://doc.spip.org/@DiffTexte
193 // http://doc.spip.org/@DiffTexte
194 function DiffTexte() {
198 // http://doc.spip.org/@_diff
199 function _diff($p, $p_old) {
200 $diff = new Diff(new DiffPara
);
201 return $diff->comparer($p, $p_old);
204 // http://doc.spip.org/@fuzzy
208 // http://doc.spip.org/@segmenter
209 function segmenter($texte) {
210 return separer_paras($texte);
213 // NB : rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies"
214 // http://doc.spip.org/@ajouter
215 function ajouter($p) {
217 $this->r
.= "\n\n\n<span class=\"diff-para-ajoute\" title=\""._T('revisions:diff_para_ajoute')."\">".$p."</span rem=\"diff-\">";
219 // http://doc.spip.org/@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-\">";
224 // http://doc.spip.org/@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-\">";
230 // http://doc.spip.org/@comparer
231 function comparer($p, $p_old) {
232 $this->r
.= "\n\n\n".$this->_diff($p, $p_old);
235 // http://doc.spip.org/@resultat
236 function resultat() {
241 // http://doc.spip.org/@DiffPara
245 // http://doc.spip.org/@DiffPara
246 function DiffPara() {
250 // http://doc.spip.org/@_diff
251 function _diff($p, $p_old) {
252 $diff = new Diff(new DiffPhrase
);
253 return $diff->comparer($p, $p_old);
256 // http://doc.spip.org/@fuzzy
260 // http://doc.spip.org/@segmenter
261 function segmenter($texte) {
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);
269 if ($texte) $paras[] = $texte;
273 // http://doc.spip.org/@ajouter
274 function ajouter($p) {
275 $this->r
.= "<span class=\"diff-ajoute\" title=\""._T('revisions:diff_texte_ajoute')."\">".$p."</span rem=\"diff-\">";
277 // http://doc.spip.org/@supprimer
278 function supprimer($p_old) {
279 $this->r
.= "<span class=\"diff-supprime\" title=\""._T('revisions:diff_texte_supprime')."\">".$p_old."</span rem=\"diff-\">";
281 // http://doc.spip.org/@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-\">";
285 // http://doc.spip.org/@comparer
286 function comparer($p, $p_old) {
287 $this->r
.= $this->_diff($p, $p_old);
290 // http://doc.spip.org/@resultat
291 function resultat() {
296 // http://doc.spip.org/@DiffPhrase
300 // http://doc.spip.org/@DiffPhrase
301 function DiffPhrase() {
305 // http://doc.spip.org/@fuzzy
309 // http://doc.spip.org/@segmenter
310 function segmenter($texte) {
312 if (test_pcre_unicode()) {
313 $punct = '([[:punct:]]|'.plage_punct_unicode().')';
317 // Plages de poncutation pour preg_match bugge (ha ha)
318 $punct = '([^\w\s\x80-\xFF]|'.plage_punct_unicode().')';
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];
329 if ($punct == '[[') {
330 $avant = substr($texte, 0, $p) . $regs[5] . $punct;
331 $texte = $regs[4] . substr($texte, $p +
$l);
334 if ($punct == ']]') {
335 $avant = substr($texte, 0, $p) . $regs[5] . $punct;
336 $texte = substr($texte, $p +
$l);
338 // Attacher les raccourcis fermants au mot precedent
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);
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);
349 // Les autres signes de ponctuation sont des mots a part entiere
351 $avant = substr($texte, 0, $p);
353 $texte = substr($texte, $p +
$l);
357 $avant = substr($texte, 0, $p +
$l);
358 $texte = substr($texte, $p +
$l);
360 if ($avant) $paras[] = $avant;
361 if ($milieu) $paras[] = $milieu;
363 if ($texte) $paras[] = $texte;
367 // http://doc.spip.org/@ajouter
368 function ajouter($p) {
369 $this->r
.= "<span class=\"diff-ajoute\" title=\""._T('revisions:diff_texte_ajoute')."\">".$p."</span rem=\"diff-\"> ";
371 // http://doc.spip.org/@supprimer
372 function supprimer($p_old) {
373 $this->r
.= "<span class=\"diff-supprime\" title=\""._T('revisions:diff_texte_supprime')."\">".$p_old."</span rem=\"diff-\"> ";
375 // http://doc.spip.org/@comparer
376 function comparer($p, $p_old) {
380 // http://doc.spip.org/@resultat
381 function resultat() {
387 // http://doc.spip.org/@preparer_diff
388 function preparer_diff($texte) {
389 include_spip('inc/charsets');
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)));
397 // http://doc.spip.org/@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');