3 /***************************************************************************\
4 * SPIP, Systeme de publication pour l'internet *
6 * Copyright (c) 2001-2011 *
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
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;
43 $paths[1] = array($y => $c);
45 if ($len +
1 > $max_len) $max_len = $len +
1;
47 return $paths[$max_len];
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) {
56 if (!$n ||
!$p) return array(0 => array(), 1 => array());
58 $paths_ymin = array();
60 $s_pos = $t_pos = array();
62 // Insertion des points
63 foreach ($t as $y => $c) $t_pos[trim($c)][] = $y;
65 foreach ($s as $x => $c) {
67 if (!isset($t_pos[$c])) continue;
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";
79 if ($len +
1 > $max_len) $max_len = $len +
1;
86 if ($paths[$max_len]) {
87 $path = explode(" ", $paths[$max_len]);
89 foreach ($path as $p) {
90 list($x, $y) = explode(",", $p);
96 return array(0 => array(), 1 => array());
100 // Generation de diff a plusieurs etages
103 // http://doc.spip.org/@Diff
108 // http://doc.spip.org/@Diff
109 function Diff($diff) {
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);
124 list($trans_rev, $trans) = lcs($paras_old, $paras);
126 $lcs_rev = $trans_rev;
134 foreach ($paras as $i => $p) {
135 if (!isset($trans[$i])) {
137 $this->diff
->ajouter($p);
141 if (!isset($lcs[$i])) {
142 // Paragraphe deplace
143 $this->diff
->deplacer($p, $paras_old[$j]);
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;
152 while (!$fin_old && $i_old < $j) {
153 if (!isset($trans_rev[$i_old])) {
154 $this->diff
->supprimer($p_old);
157 list($i_old, $p_old) = each($paras_old);
158 if (!$p_old) $fin_old = true;
161 // Paragraphe n'ayant pas change de place
162 $this->diff
->comparer($p, $paras_old[$j]);
164 // Paragraphes supprimes a la fin du texte
166 if (!isset($i_old)) {
167 list($i_old, $p_old) = each($paras_old);
168 if (!strlen($p_old)) $fin_old = true;
171 if (!isset($trans_rev[$i_old])) {
172 $this->diff
->supprimer($p_old);
174 list($i_old, $p_old) = each($paras_old);
175 if (!$p_old) $fin_old = true;
179 if (!isset($trans_rev[$i_old])) {
180 $this->diff
->supprimer($p_old);
183 return $this->diff
->resultat();
187 // http://doc.spip.org/@DiffTexte
191 // http://doc.spip.org/@DiffTexte
192 function DiffTexte() {
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);
202 // http://doc.spip.org/@fuzzy
206 // http://doc.spip.org/@segmenter
207 function segmenter($texte) {
208 return separer_paras($texte);
211 // NB : rem=\"diff-\" est un signal pour la fonction "afficher_para_modifies"
212 // http://doc.spip.org/@ajouter
213 function ajouter($p) {
215 $this->r
.= "\n\n\n<div class=\"diff-para-ajoute\" title=\""._T('diff_para_ajoute')."\">".$p."</div rem=\"diff-\">";
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-\">";
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-\">";
228 // http://doc.spip.org/@comparer
229 function comparer($p, $p_old) {
230 $this->r
.= "\n\n\n".$this->_diff($p, $p_old);
233 // http://doc.spip.org/@resultat
234 function resultat() {
239 // http://doc.spip.org/@DiffPara
243 // http://doc.spip.org/@DiffPara
244 function DiffPara() {
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);
254 // http://doc.spip.org/@fuzzy
258 // http://doc.spip.org/@segmenter
259 function segmenter($texte) {
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);
267 if ($texte) $paras[] = $texte;
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-\">";
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-\">";
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-\">";
283 // http://doc.spip.org/@comparer
284 function comparer($p, $p_old) {
285 $this->r
.= $this->_diff($p, $p_old);
288 // http://doc.spip.org/@resultat
289 function resultat() {
294 // http://doc.spip.org/@DiffPhrase
298 // http://doc.spip.org/@DiffPhrase
299 function DiffPhrase() {
303 // http://doc.spip.org/@fuzzy
307 // http://doc.spip.org/@segmenter
308 function segmenter($texte) {
310 if (test_pcre_unicode()) {
311 $punct = '([[:punct:]]|'.plage_punct_unicode().')';
315 // Plages de poncutation pour preg_match bugge (ha ha)
316 $punct = '([^\w\s\x80-\xFF]|'.plage_punct_unicode().')';
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];
327 if ($punct == '[[') {
328 $avant = substr($texte, 0, $p) . $regs[5] . $punct;
329 $texte = $regs[4] . substr($texte, $p +
$l);
332 if ($punct == ']]') {
333 $avant = substr($texte, 0, $p) . $regs[5] . $punct;
334 $texte = substr($texte, $p +
$l);
336 // Attacher les raccourcis fermants au mot precedent
338 if (preg_match(',^[\]}]+$,', $punct)) {
339 $avant = substr($texte, 0, $p) . $regs[5] . $punct;
340 $texte = $regs[4] . substr($texte, $p +
$l);
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);
347 // Les autres signes de ponctuation sont des mots a part entiere
349 $avant = substr($texte, 0, $p);
351 $texte = substr($texte, $p +
$l);
355 $avant = substr($texte, 0, $p +
$l);
356 $texte = substr($texte, $p +
$l);
358 if ($avant) $paras[] = $avant;
359 if ($milieu) $paras[] = $milieu;
361 if ($texte) $paras[] = $texte;
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-\"> ";
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-\"> ";
373 // http://doc.spip.org/@comparer
374 function comparer($p, $p_old) {
378 // http://doc.spip.org/@resultat
379 function resultat() {
385 // http://doc.spip.org/@preparer_diff
386 function preparer_diff($texte) {
387 include_spip('inc/charsets');
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)));
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');