Creare un programma DIFF (parte 1)

Il post di oggi si applica nei più svariati campi: informatica, biologia, chimica, analisi forense, ecc. Inizialmente lo vedremo dal punto di vista informatico, e poi vedremo perchè si applica a tanti settori diversi. Siccome l'argomento può risultare complesso, vi chiedo di scrivere nei commenti ciò che non vi è chiaro.
Quando si scrive del codice un per un programma, di solito si scrivono delle righe di testo, dove ogni riga rappresenta un comando. Più il programma diventa complesso, più le righe di codice aumentano: si aggiungono comandi, si correggono errori, si torna indietro sul codice scritto e lo si modifica.
Ogni giorno che salviamo il nostro codice, creiamo una versione differente del listato.
Ad esempio prima potremmo scrivere un programma così:
leggi la posta
scrivi a Mario
spegni il pc

e poi il giorno dopo  potremmo modificare il codice con:
leggi la posta
scrivi a Mario
scrivi a Luigi
spegni il pc

e infine il giorno dopo ancora:
leggi la posta
scrivi a Pino
scrivi a Luigi
spegni il pc

Come vedete il programma è stato cambiato tre volte, quindi abbiamo fatto tre versioni diverse del nostro codice. Quando si programma è importante mantenere le versioni precedenti del codice. In questo modo possiamo tornare indietro in caso di errori o analizzare le differenze per capire in un attimo dove è il problema o cosa ha migliorato molto il vostro programma. I programmi DIFF servono proprio a questo, a mostrare le differenze. Sembra facile, ma è molto complicato.
Per capire come fare, dobbiamo prima capire che tipo di modifiche possono essere fatte. Per semplicità ci limiteremo alle righe, che è il caso più diffuso.
In un codice le righe possono essere aggiunte o cancellate. Se uno modifica una riga non fa altro che cancellarla e aggiungerne un'altra al suo posto.
Inserire una sola riga di codice, ad esempio, può dividere in due parti il testo; il DIFF deve riconoscere le parti uguali prima e dopo la riga inserita e segnalarci solo la riga aggiunta. Se facessimo un semplice confronto riga per riga, dalla riga aggiunta in poi il DIFF direbbe erroneamente che è tutto diverso.

DIFF sbagliato

Qui apriamo una piccola parentesi, qualcuno potrebbe dire che ognuno può mostrare le differenze come vuole, basta che portino allo stesso risultato. E' vero che le differenze mostrate nell'immagine sono a loro modo giuste, ma l'unica vera differenza nell'esempio è l'aggiunta della riga suona. La teoria che è dietro al trovare del differenze dice che il miglior DIFF è quello mostra le differenze, scrivendo il meno possibile.
Il DIFF corretto nell'esempio è:

DIFF corretto

Chiaramente va indicato anche dove è la modifica, ma questo è semplice da ottenere. Mi premeva chiarire questo concetto, che la vera differenza è la minima differenza trovabile. Chiusa parentesi.
Ora passiamo al difficile, come si può trovare la minima differenza?
Per fortuna parecchie persone hanno lavorato al problema e hanno trovato una soluzione che è spiegata qui: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem .
Riassumendo semplicemente, bisogna costruire una matrice delle sequenza comuni, tipo questa (v. esempio prima):

	0	Leggi	Suona	Scrivi	Spegni
0	0	0	0	0	0
Leggi	0	1	1	1	1
Scrivi	0	1	1	2	2
Spegni	0	1	1	2	3

La logica per costruirla e semplice, i titoli delle righe e delle colonne della matrice sono formati da 0 e le righe delle due versioni da analizzare, la prima riga e la prima colonna sono formati da zeri. Poi ogni elemento (X_i,Y_i) segue le segue le seguenti regole:

• se  il titolo della riga o colonna corrente è zero, la cella contiene zero
• se i titoli di riga e colonna sono diversi inserisco il valore più grande tra le celle (X_i-1,Y_i) e (X_i,Y_i-1), cioè rispettivamente a sinistra e sopra
• se i titoli di riga e colonna sono uguali inserisco 1 + il valore della cella a sinistra

Costruita una tabella del LCSL genere la si può attraversare partendo dalla casella in basso a destra per creare il DIFF.
Se facciamo uno stack con tre campi: versA, versB, uscita; mettiamo le due versioni dell'esempio ripettivamente in versA e verB. Lanciando il seguente codice:

on mouseUp
   #trasformiamo i testi in array, dove ogni riga è un elemento dell'array   
   put field "versA" into tOldSource
   put field "versB" into tNewSource
   split tOldSource using return
   split tNewSource using return
   #cerchiamo di capire di quanti elementi, cioè righe, è fatto ogni array
   #extents mostra una serie di righe con due numeri, il numero minimo e il massimo per ogni dimensione dell'array
   #qui la dimensione è 1
   put item 2 of the extents of tOldSource into tOldLineCount
   put item 2 of the extents of tNewSource into tNewLineCount
   #calcoliamo le varie sequenze con il massimo testo in comune (LCSL)   
   put CalculateLCSLengths(tOldSource, tNewSource, tOldLineCount, tNewLineCount) into LCLS
   #e adesso calcoliamo il DIFF   
   set the text of field uscita to empty
   put tOldLineCount,tNewLineCount into cella
   DetermineDiff LCLS, tOldSource, tNewSource, tOldLineCount, tNewLineCount
end mouseUp

function CalculateLCSLengths tOldSource, tNewSource, tOldLineCount, tNewLineCount   
   #costruiamo la tabella per il calcolo LCSL
   #la riga 0 è tutti 0
   repeat with tRow = 0 to tOldLineCount
      put 0 into pLCSLength[tRow,0]
   end repeat
   #la colonna 0 è tutti 0
   repeat with tCol = 0 to tNewLineCount
      put 0 into pLCSLength[0,tCol]
   end repeat
   #ora calcoliamo le altre varie celle della matrice LCLS
   repeat with tRow = 1 to tOldLineCount
      repeat with tCol = 1 to tNewLineCount
         put tOldSource[tRow] into tOldLine
         put tNewSource[tCol] into tNewLine
         if tOldLine = tNewLine then
            put pLCSLength[tRow - 1,tCol - 1] + 1 into pLCSLength[tRow,tCol]
         else
            put max(pLCSLength[tRow - 1,tCol],pLCSLength[tRow,tCol - 1]) into pLCSLength[tRow,tCol]
         end if
      end repeat
   end repeat
   #finito
   return pLCSLength
end CalculateLCSLengths


#abbiamo un messaggio che chiama se stesso parecchie volte
#qui usiamo le @ per risparmiare meomoria ed evitare troppe copie della stessa variabile, però stiamo attenti a non modificarle!
on DetermineDiff @pLCSLength, @pOldSource, @pNewSource, pRow, pCol
   put pOldSource[pRow] into tOldLine #la riga nel file originale
   put pNewSource[pCol] into tNewLine #la riga nella nuova versione
   if pRow > 0 and pCol > 0 and tOldLine = tNewLine then
      #sono uguali, andiamo alla cella in alto a sinistra rispetto all'attuale nel LCLS            
      DetermineDiff pLCSLength, pOldSource, pNewSource, pRow - 1, pCol - 1, "uguale"
      #set the text of field uscita to ( field uscita & " " & tab & tOldLine & return)
   else if pCol > 0 and (pRow = 0 or pLCSLength[pRow,pCol - 1]   >= pLCSLength[pRow - 1, pCol]) then
      ##caso la cella a sinistra è maggiore o uguale di quella sopra
      #è stata aggiunta una riga, moviamoci a sinistra nella tabella LCLS         
      DetermineDiff pLCSLength, pOldSource, pNewSource, pRow,   pCol - 1, "aggiungo"   
      set the text of field uscita to (field uscita & prow& "+" & tab & tNewLine & return )
   else if pRow > 0 and (pCol = 0 or pLCSLength[pRow,pCol - 1] < pLCSLength[pRow - 1, pCol]) then
      ##caso la cella a sinistra è minore di quella sopra
      #è stata rimossa una riga, saliamo di una riga nella tabella LCLS         
      DetermineDiff pLCSLength, pOldSource, pNewSource, pRow - 1, pCol, "sottraggo"         
      set the text of field uscita to (field uscita & prow& "-" & tab & tOldLine & return )
   end if
end DetermineDiff




otterremo nel campo uscita:
1+    Suona

Che è il DIFF corretto. Cioè alla riga 1 è stato aggiunto "Suona".
Se proviamo con un testo più lungo, ecco cosa succede:

Vers. A	Vers. B	Uscita
This part of the document has stayed the same from version to version. It shouldn't be shown if it doesn't change. Otherwise, that would not be helping to compress the size of the changes. This paragraph contains text that is outdated. It will be deleted in the near future. It is important to spell check this dokument. On the other hand, a misspelled word isn't the end of the world. Nothing in the rest of this paragraph needs to be changed. Things can be added after it.	This is an important notice! It should therefore be located at the beginning of this document! This part of the document has stayed the same from version to version. It shouldn't be shown if it doesn't change. Otherwise, that would not be helping to compress anything. It is important to spell check this document. On the other hand, a misspelled word isn't the end of the world. Nothing in the rest of this paragraph needs to be changed. Things can be added after it. This paragraph contains important new additions to this document.	0+        This is an important 0+        notice! It should 0+        therefore be located at 0+        the beginning of this 0+        document! 0+        8-        compress the size of the 9-        changes. 10-        11-        This paragraph contains 12-        text that is outdated. 13-        It will be deleted in the 14-        near future. 14+        compress anything. 17-        check this dokument. On 17+        check this document. On 24+        24+        This paragraph contains 24+        important new additions 24+        to this document.

Corretto ma bruttino da vedere, il DIFF ormai è uno standard che è anche pulito da vedere, quindi cerchiamo di raggruppare le righe consecutive in modo da renderlo più leggibile.
Aggiungendo il seguente codice:

on MouseUp
   put the text of field uscita into old
   set itemdel to tab
   put 0 into cont
   repeat for each line tLine in old
      put item 1 of tLine into variazione
      put char 1 to -2 of variazione into numriga
      put char -1 of variazione into tipo # + o -
      put item 2 of tLine into riga #il testo della riga
      #agg
      if tipo = "+"   then
         if numriga is not oldriga then
            put tipo & numriga & CR after nuovo #il testo riformattato
         end if
         if numriga = oldriga and oldtipo = "-" then
            put tipo & numriga & CR after nuovo #il testo riformattato
         end if
      end if
      if tipo = "-" and ((numriga - oldriga) > 1) then
         put tipo & numriga & CR after nuovo #il testo riformattato
      end if
      put riga & CR after nuovo
      put tipo into oldtipo
      put numriga into oldriga
   end repeat
set the text of field uscita to nuovo
end MouseUp

otteniamo:
+0
    This is an important
    notice! It should
    therefore be located at
    the beginning of this
    document!
   
-8
    compress the size of the
    changes.
   
    This paragraph contains
    text that is outdated.
    It will be deleted in the
    near future.
+14
    compress anything.
-17
    check this dokument. On
+17
    check this document. On
+24
   
    This paragraph contains
    important new additions
    to this document.

Che è proprio come il DIFF usuale, dove il più (+) indica un aggiunta, il meno (-) una cancellazione e il numero dopo il segno a che riga è avvenuta.
Ma ancora siamo a metà del lavoro, nel prossimo posto post vedremo qualche applicazione pratica e utile.