Mise en route du suivi.
[aidenligne_francais_universite.git] / ecrire / inc / diff.php
1 <?php
2
3 /***************************************************************************\
4 * SPIP, Systeme de publication pour l'internet *
5 * *
6 * Copyright (c) 2001-2007 *
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 // Attacher les raccourcis fermants au mot precedent
327 if (preg_match(',^[\]}]+$,', $punct)) {
328 $avant = substr($texte, 0, $p) . $regs[5] . $punct;
329 $texte = $regs[4] . substr($texte, $p + $l);
330 }
331 // Attacher les raccourcis ouvrants au mot suivant
332 else if ($regs[5] && preg_match(',^[\[{]+$,', $punct)) {
333 $avant = substr($texte, 0, $p) . $regs[5];
334 $texte = $punct . substr($texte, $p + $l);
335 }
336 // Les autres signes de ponctuation sont des mots a part entiere
337 else {
338 $avant = substr($texte, 0, $p);
339 $milieu = $regs[0];
340 $texte = substr($texte, $p + $l);
341 }
342 }
343 else {
344 $avant = substr($texte, 0, $p + $l);
345 $texte = substr($texte, $p + $l);
346 }
347 if ($avant) $paras[] = $avant;
348 if ($milieu) $paras[] = $milieu;
349 }
350 if ($texte) $paras[] = $texte;
351 return $paras;
352 }
353
354 // http://doc.spip.org/@ajouter
355 function ajouter($p) {
356 $this->r .= "<span class=\"diff-ajoute\" title=\""._T('diff_texte_ajoute')."\">".$p."</span rem=\"diff-\"> ";
357 }
358 // http://doc.spip.org/@supprimer
359 function supprimer($p_old) {
360 $this->r .= "<span class=\"diff-supprime\" title=\""._T('diff_texte_supprime')."\">".$p_old."</span rem=\"diff-\"> ";
361 }
362 // http://doc.spip.org/@comparer
363 function comparer($p, $p_old) {
364 $this->r .= $p;
365 }
366
367 // http://doc.spip.org/@resultat
368 function resultat() {
369 return $this->r;
370 }
371 }
372
373
374 // http://doc.spip.org/@preparer_diff
375 function preparer_diff($texte) {
376 include_spip('inc/charsets');
377
378 $charset = $GLOBALS['meta']['charset'];
379 if ($charset == 'utf-8')
380 return unicode_to_utf_8(html2unicode($texte));
381 return unicode_to_utf_8(html2unicode(charset2unicode($texte, $charset, true)));
382 }
383
384 // http://doc.spip.org/@afficher_diff
385 function afficher_diff($texte) {
386 $charset = $GLOBALS['meta']['charset'];
387 if ($charset == 'utf-8') return $texte;
388 return charset2unicode($texte, 'utf-8');
389 }
390
391
392 ?>