[ANY] Diff tra due rami di filesystem

[malocchio]

Torno dopo mesi di inattività per chiedere il vostro aiuto! :help:

Non so se il titolo rende bene l'idea di cosa voglio fare, ma mi spiego meglio ora:

Ho un'applicazione (attualmente in Php ma conto di portare tutto quanto in Java il prima possibile) che scansiona (si può dire?) ricorsivamente un ramo di filesystem (diciamo una o più cartelle), trova ovviamente dei file, ne esclude alcuni (ad esempio "thumbs.db", ".", "..", "*.dat" ... ), raccoglie informazioni sui restanti (cartella, nome file, dimensione, hash md5...) e salva queste informazioni in una tabella SQL.

La funzionalità che mi manca è la seguente:
in un momento successivo alla prima scansione, ho bisogno che l'applicazione rifaccia la scansione delle cartelle, legga i dati salvati in precedenza sul db e calcoli una "differenza" tra il filesystem scansionato e i dati memorizzati.

Questa "differenza" deve darmi la certezza che, se "applicata" ai dati già salvati (risolvendo gli eventuali conflitti), quello che ottengo è la versione aggiornata del filesystem salvata sul db, come se avessi rifatto la scansione completa e reinserito tutti i record da zero.

Per intenderci, il sistema è concettualmente uguale al software diff/patch disponibile sotto Linux, con la differenza che io ho bisogno di calcolare la differenza tra rami di filesystem e non di contenuti di file.
E' praticamente (con qualche aggiustamento) quello che fa SVN quando si esegue un commit ed esso trasmette solo le differenze tra il repository e la copia locale.

La cosa essenziale è che, una volta applicata la patch, il database rispecchi correttamente la situazione attuale sul filesystem.

Ho cercato con google qualcosa ma mi ha restituito solo algoritmi per diff su file di testo (ad esempio il three-way merge).

Per adesso sto solo cercando un'idea di partenza... il mio fine è creare un sistema di diff simile a quello di SVN, ma leggermente più "intelligente" e adattato alle mie esigenze che, ad esempio, sappia riconoscere automaticamente il più delle volte se un file è stato spostato o copiato invece che marcarne uno come eliminato e l'altro come nuovo.

Non mi interessa calcolare il diff del contenuto di due file, l'importante è riuscire a riconoscere se A è diverso o uguale per contenuto a B (questo è già implementato :) ).

Si accettano idee :D

[malocchio]

UPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPPP :cry:

http://news.cnet.com/i/bto/20090531/Up325.jpg

:D :D :D

[WarDuck]

Implicitamente il confronto lo fai anche sul contenuto, perché se un dato record del DB ha uno schema tipo:

(cartella, nome file, dimensione, hash)

Allora significa che se il file cambia (in particolare dimensione e hash) anche il record cambia.

O forse non ho capito bene cosa vuoi fare.

Comunque per ogni file devi valutare se il record nel db è presente o meno.

Se è presente fai un update, se non lo è fai un insert.

Chiaramente dato che sono due insiemi valgono le proprietà insiemistiche per cui un insieme A è uguale ad un insieme B se e solo se A è contenuto in B e B è contenuto in A.

Ergo devi fare il controllo anche al contrario (dal db verso il filesystem).

[malocchio]

Implicitamente il confronto lo fai anche sul contenuto, perché se un dato record del DB ha uno schema tipo:

(cartella, nome file, dimensione, hash)

Allora significa che se il file cambia (in particolare dimensione e hash) anche il record cambia.

O forse non ho capito bene cosa vuoi fare.

Comunque per ogni file devi valutare se il record nel db è presente o meno.

Se è presente fai un update, se non lo è fai un insert.

Chiaramente dato che sono due insiemi valgono le proprietà insiemistiche per cui un insieme A è uguale ad un insieme B se e solo se A è contenuto in B e B è contenuto in A.

Ergo devi fare il controllo anche al contrario (dal db verso il filesystem).

Certo, ovviamente tengo traccia anche del contenuto dei file, ma si tratta principalmente di file binari di qualche centinaio di megabyte che difficilmente vengono toccati, e per quello che serve a me se un file viene modificato devo solo aggiornarne la dimensione e l'hash nel db, niente altro.
La cosa che mi preme di più è creare un algoritmo corretto, perché se il database viene corrotto una volta poi diventa (quasi) inutilizzabile...

Avevo pensato anche io ad una cosa a due passaggi. Avevo già creato una classe che tramite hashtable mi permetteva di indicizzare i file di un insieme per poter fare il confronto velocemente tra il filesystem e il db.
Quindi, diciamo che faccio il confronto in un verso e poi nell'altro. Però la mia idea era quella di memorizzare le differenze in una qualche struttura (che ancora non ho progettato - in realtà le istanze saranno due, una per ogni verso) e poi, con un terzo passaggio, processare i risultati e determinare quali modifiche apportare al database. In realtà quello che servirebbe a me è che il sistema generasse questa lista di modifiche da fare al database, me la proponesse con un'interfaccia grafica così io la posso accettare così com'è oppure aggiustare in qualche maniera.

Mi manca qualche idea su questo terzo passaggio, visto che è quello che deve fare il compito intelligente e rischia secondo me di diventare una sfilza molto lunga di codice, che vorrei evitare.

[WarDuck]

Una volta che fai il confronto direi che puoi far uscire un output le query da fare in SQL e questo file rappresenterà di fatto il tuo diff.

Ad esempio se vedi che il file pippo viene modificato puoi stampare sul file qualcosa del tipo:

UPDATE tabella SET dim = <nuova dim>, hash = <nuovo hash> WHERE nome = "pippo".

E questo per ogni modifica o nuova entry che vedi.

Alla fine della storia in output avrai una specie di script SQL con tutte le query da effettuare.

Puoi pensare a fare una interfaccia che legge poi ogni riga di questo file e presenta una casellina in maniera da scegliere o meno se fare la query.

Dopodiché fai girare lo script sul tuo db e il gioco dovrebbe essere fatto. Volendo puoi saltare il passaggio di fare il file intermedio, potresti memorizzare direttamente le query in memoria in una lista, così verrebbe anche più semplice attivare/disattivare la query.

[malocchio]

Una volta che fai il confronto direi che puoi far uscire un output le query da fare in SQL e questo file rappresenterà di fatto il tuo diff.

Ad esempio se vedi che il file pippo viene modificato puoi stampare sul file qualcosa del tipo:

UPDATE tabella SET dim = <nuova dim>, hash = <nuovo hash> WHERE nome = "pippo".

E questo per ogni modifica o nuova entry che vedi.

Alla fine della storia in output avrai una specie di script SQL con tutte le query da effettuare.

Puoi pensare a fare una interfaccia che legge poi ogni riga di questo file e presenta una casellina in maniera da scegliere o meno se fare la query.

Dopodiché fai girare lo script sul tuo db e il gioco dovrebbe essere fatto. Volendo puoi saltare il passaggio di fare il file intermedio, potresti memorizzare direttamente le query in memoria in una lista, così verrebbe anche più semplice attivare/disattivare la query.

L'idea di stampare a video le query sql non mi piace proprio per niente... ho bisogno di un'interfaccia molto veloce da usare e comunque lo scopo di questa non è selezionare quali modifiche applicare al database.

Mi spiego meglio. L'applicazione, alla prima scansione del filesystem, associa un valore ad ogni file (in modo automatico). Finita la scansione, mi si presenta un'interfaccia con l'elenco dei file, varie informazioni su di essi e questi valori che il sistema vi ha associato e che io posso cambiare in maniera manuale, poi faccio il submit e l'applicazione sostituisce i valori nel database con quelli che gli ho specificato io. Il fatto di rendere il sistema di diff intelligente mi serve per preservare quei valori associati ai file nel caso il file stesso sia stato spostato o rinominato (o copiato). In questo caso il software dovrebbe riconoscere che il file è lo stesso presente prima, ma con un nome/percorso diverso e comunicarmelo tramite la gui. Se io gli confermo che il file è lo stesso di quello trovato in precedenza il sistema gli aggiorna nome/percorso nel db e mantiene il valore già presente, altrimenti, se gli comunico che il file non ha niente a che fare con file vecchi già presenti (caso piuttosto raro, visto che il sistema dovrebbe basarsi sull'hash del contenuto per determinare quali file sono uguali, ma ammettiamo pure che ci possa essere un conflitto) allora lui elimina il record vecchio e ne inserisce uno nuovo, associando automaticamente il valore al nuovo file e magari chiedermi conferma anche riguardo a questo.
Ci sono diversi casi che il sistema dovrebbe riconoscere. Ad esempio:
il file A è stato rinominato
il file A è stato spostato (magari è stata spostata una cartella che lo conteneva...)
è stata creata una copia del file A in un'altra cartella

La cose si complicano se ad esempio questi casi si presentano più volte nella stessa scansione, ad esempio se sono state create due copie del file A (penso che non mi sia mai capitato, però devo prendere in considerazione tutte le possibilità).
Oppure può accadere che due file abbiano un contenuto apparentemente uguale (stessa dimensione e hash) ma valori associati diversi. In una scansione il sistema rileva un nuovo file che sembra essere una copia di uno dei due, ma non può sapere di quale, quindi mi deve chiedere di quale file deve prendere il valore associato o anche se lo deve associare automaticamente lui...

So che all'inizio poteva sembrare particolarmente semplice come problema, ma la presenza di questi casi limite che potrebbe farmi scrivere un algoritmo che produce risultati scorretti mi spaventa un po', per questo ho scritto qui.

Ah, so di voler pretendere molto da questo software (e da me stesso che lo voglio scrivere), però mi sembra un'interessante occasione per me di imparare qualcosa di buono.

[PGI-Bis]

Un'idea potrebbe essere questa.

Premesse:

file e record sono elementi
gli elementi hanno delle proprietà (percorso assoluto, hash, attributi)
il database e il filesystem sono sorgenti
la sorgente di un file è il filesystem, la sorgente di un record è il database
i sorgenti hanno una destinazione
la destinazione del filesystem è il database, la destinazione del database è il filesystem
esistono tre operazioni dette crea, elimina, aggiorna
crea è un'operazione di un file che genera un record
elimina è un'operazione di un record
aggiorna è un'operazione di un file che aggiorna un record
ogni operazione ha un insieme di controlli
un controllo è l'applicazione di un elemento alla sua destinazione che produce un risultato che può essere un impedimento o una conferma
il controllo decide se emettere un impedimento o una conferma sulla base delle proprietà dell'elemento

Ciò detto, il programma funzionerebbe come segue:

data la lista di operazioni L inizialmente vuota
-per ogni elemento e
--per ogni tipo di operazione op
---crea l'operazione e applica i suoi controlli all'elemento e
---salva l'operazione nella lista L
-per ogni operazione op in L
--se op contiene solo impedimenti, non eseguirla
--se op contiene solo conferme, eseguila
--se op contiene almeno un impedimento e almeno una conferma
---presenta conflitti e conferme all'utente chiedendo cosa fare
--se op è vuota non eseguirla

Poi decidi arbitrariamente quali siano i fatti da considerare conferme e quali impedimenti.

Ad esempio l'operazione crea potrebbe essere confermata dall'assenza di file con lo stesso percorso e impedita dall'esistenza di file con lo stesso hash

L'operazione aggiorna potrebbe essere confermata dalla presenza di record con lo stesso percorso e hash diverso ma impedita da un conflitto tra le proprietà del record e quelle del file

L'operazione di rimozione sarebbe confermata dall'assenza di file e impedita se l'utente abbia selezionato una casella nella ui (stile conferma prima di eliminare).

Forse se ragionassimo in termini di affermazioni-negazioni anzichè di impedimenti e verifiche le condizioni sarebbero meno arbitrarie ma per essere una stupidata di mezzanotte direi che come modello potrebbe anche funzionare (e sembra anche facilme da eseguire in parallelo)

[malocchio]

Un'idea potrebbe essere questa.

Premesse:

file e record sono elementi
gli elementi hanno delle proprietà (percorso assoluto, hash, attributi)
il database e il filesystem sono sorgenti
la sorgente di un file è il filesystem, la sorgente di un record è il database
i sorgenti hanno una destinazione
la destinazione del filesystem è il database, la destinazione del database è il filesystem
esistono tre operazioni dette crea, elimina, aggiorna
crea è un'operazione di un file che genera un record
elimina è un'operazione di un record
aggiorna è un'operazione di un file che aggiorna un record
ogni operazione ha un insieme di controlli
un controllo è l'applicazione di un elemento alla sua destinazione che produce un risultato che può essere un impedimento o una conferma
il controllo decide se emettere un impedimento o una conferma sulla base delle proprietà dell'elemento

Ciò detto, il programma funzionerebbe come segue:

data la lista di operazioni L inizialmente vuota
-per ogni elemento e
--per ogni tipo di operazione op
---crea l'operazione e applica i suoi controlli all'elemento e
---salva l'operazione nella lista L
-per ogni operazione op in L
--se op contiene solo impedimenti, non eseguirla
--se op contiene solo conferme, eseguila
--se op contiene almeno un impedimento e almeno una conferma
---presenta conflitti e conferme all'utente chiedendo cosa fare
--se op è vuota non eseguirla

Poi decidi arbitrariamente quali siano i fatti da considerare conferme e quali impedimenti.

Ad esempio l'operazione crea potrebbe essere confermata dall'assenza di file con lo stesso percorso e impedita dall'esistenza di file con lo stesso hash

L'operazione aggiorna potrebbe essere confermata dalla presenza di record con lo stesso percorso e hash diverso ma impedita da un conflitto tra le proprietà del record e quelle del file

L'operazione di rimozione sarebbe confermata dall'assenza di file e impedita se l'utente abbia selezionato una casella nella ui (stile conferma prima di eliminare).

Forse se ragionassimo in termini di affermazioni-negazioni anzichè di impedimenti e verifiche le condizioni sarebbero meno arbitrarie ma per essere una stupidata di mezzanotte direi che come modello potrebbe anche funzionare (e sembra anche facilme da eseguire in parallelo)

Le tue astrazioni mi lasciano sempre di stucco... :eek:
Vabbè dai lo rileggo domani mattina :asd:

Grazie sia a te che a Warduck. Mi dispiace solo di essere sotto esami e non poter dedicare molto tempo a questo progettino...

[WarDuck]

=== PREMESSA ===
A questo punto date le premesse non so se conviene usare un modo per metterti direttamente in ascolto degli eventi dal file system.

Sotto linux c'è la chiamata di sistema C inotify, mentre sotto Windows in C# è disponibile la classe FileSystemWatcher.

http://msdn.microsoft.com/en-us/library/system.io.filesystemwatcher(v=VS.90).aspx

Questo ti aiuta a notificare i cambiamenti alle cartelle in realtime e sicuramente facilita la gestione di eventi come il rename dei files.
=== FINE PREMESSA ===


Immagino comunque che tu non voglia necessariamente usare un sistema realtime, quindi andiamo in ordine.

Innanzitutto quando fai questa operazione il file system dev'essere blindato, nel senso che assumiamo che non vengano fatte modifiche al file system mentre il programma gira, altrimenti rischiamo di avere incoerenza.

Non ricordo se le varie funzioni quando iterano lungo una directory fanno una copia per evitare di dover gestire i cambiamenti nel layer sottostante, presumo di si comunque.

ALGORITMO A

per ogni file f in cartella:
calcola l'hash di f
se f non è presente né come file né come hash nel DB:
# nuovo file
OP -> aggiungi f a DB
altrimenti:
se è presente come file:
se hash è cambiato:
# file modificato
OP -> cambia hash e dim del file f in DB
altrimenti se è presente come hash:
se hash coincide con un file:
# file rinominato
OP -> cambia il nome del file f nel DB


Ora sicuramente al termine della prima procedura hai che i file rinominati adesso coincidono nel DB.

L'unica cosa è che nel DB potrebbero esserti rimasti dei files che invece sono stati cancellati dal file system.

Quindi ora fai il controllo inverso, che tuttavia risulta "più semplice":

ALGORITMO B

per ogni record r in db:
se r non è in cartella (come file):
# file eliminato
OP -> cancella record r
altrimenti:
se informazioni coincidono con il file system:
continua
altrimenti:
[ERRORE] possibile incoerenza.


Ora delle considerazioni:

- Il file system dev'essere "bloccato" mentre gira il programma, ma questo già l'abbiamo detto

- Per tutti e due gli algoritmi OP è una astrazione dell'operazione che devi fare, nel senso che non è detto che tu debba necessariamente modificare il DB, ma sta solo ad indicare che fai qualcosa per tenere traccia dei cambiamenti. Ergo quell'OP può essere benissimo qualcosa come scrivere "+file1 hash size" su un file.

- Dall'algoritmo A si evince che è consigliabile usare 2 indici nel DB per nome del file e per hash.

- Nell'algoritmo B si evince che implementi l'uguaglianza tra insiemi perché controlli se i dati del DB sono effettivamente coerenti con il file system.
Notare che è un controllo che potresti anche decidere di non fare nel momento in cui comunque hai freezato il file system e quindi sei ragionevolmente sicuro che tutti e soli i file che sono nella cartella, per l'algoritmo A sono stati inseriti nel DB.

[malocchio]

=== PREMESSA ===
A questo punto date le premesse non so se conviene usare un modo per metterti direttamente in ascolto degli eventi dal file system.

Sotto linux c'è la chiamata di sistema C inotify, mentre sotto Windows in C# è disponibile la classe FileSystemWatcher.

http://msdn.microsoft.com/en-us/library/system.io.filesystemwatcher(v=VS.90).aspx

Questo ti aiuta a notificare i cambiamenti alle cartelle in realtime e sicuramente facilita la gestione di eventi come il rename dei files.
=== FINE PREMESSA ===


Immagino comunque che tu non voglia necessariamente usare un sistema realtime, quindi andiamo in ordine.

Innanzitutto quando fai questa operazione il file system dev'essere blindato, nel senso che assumiamo che non vengano fatte modifiche al file system mentre il programma gira, altrimenti rischiamo di avere incoerenza.

Non ricordo se le varie funzioni quando iterano lungo una directory fanno una copia per evitare di dover gestire i cambiamenti nel layer sottostante, presumo di si comunque.

ALGORITMO A

per ogni file f in cartella:
calcola l'hash di f
se f non è presente né come file né come hash nel DB:
# nuovo file
OP -> aggiungi f a DB
altrimenti:
se è presente come file:
se hash è cambiato:
# file modificato
OP -> cambia hash e dim del file f in DB
altrimenti se è presente come hash:
se hash coincide con un file:
# file rinominato
OP -> cambia il nome del file f nel DB


Ora sicuramente al termine della prima procedura hai che i file rinominati adesso coincidono nel DB.

L'unica cosa è che nel DB potrebbero esserti rimasti dei files che invece sono stati cancellati dal file system.

Quindi ora fai il controllo inverso, che tuttavia risulta "più semplice":

ALGORITMO B

per ogni record r in db:
se r non è in cartella (come file):
# file eliminato
OP -> cancella record r
altrimenti:
se informazioni coincidono con il file system:
continua
altrimenti:
[ERRORE] possibile incoerenza.


Ora delle considerazioni:

- Il file system dev'essere "bloccato" mentre gira il programma, ma questo già l'abbiamo detto

- Per tutti e due gli algoritmi OP è una astrazione dell'operazione che devi fare, nel senso che non è detto che tu debba necessariamente modificare il DB, ma sta solo ad indicare che fai qualcosa per tenere traccia dei cambiamenti. Ergo quell'OP può essere benissimo qualcosa come scrivere "+file1 hash size" su un file.

- Dall'algoritmo A si evince che è consigliabile usare 2 indici nel DB per nome del file e per hash.

- Nell'algoritmo B si evince che implementi l'uguaglianza tra insiemi perché controlli se i dati del DB sono effettivamente coerenti con il file system.
Notare che è un controllo che potresti anche decidere di non fare nel momento in cui comunque hai freezato il file system e quindi sei ragionevolmente sicuro che tutti e soli i file che sono nella cartella, per l'algoritmo A sono stati inseriti nel DB.

Ottimo post.

Non mi serve un sistema realtime.
Diciamo che posso anche fare a meno di preoccuparmi della blindatura del filesystem... di solito i cambiamenti ai file sono operazioni che faccio io a mano ed anche l'applicazione è avviata da me a mano
La mia applicazione è già ad un livello di astrazione un po' più alto: quando deve rifare una scansione, scansiona il filesystem tutto in un botto e salva tutto in un array, poi scarica l'intera tabella sul db e salva tutto in un array. Gli array sono di oggetti File, facilmente manipolabili. Il sistema di diff deve confrontare i due array e restituire un array di operazioni da eseguire (che si può vedere come una "patch"). Un altro componente si occuperà poi di tradurre queste differenze in query al database, ma questo mi sembra piuttosto facile da realizzare.
Ho già creato una classe FileList che costruisce una hashtable multipla di tutti i file presenti nell'array passatogli col costruttore, in base a path e hash.
Sul database sono già presenti più indici (anche se per ora non sono sfruttati)
Il numero di file più raggiungere al massimo qualche migliaio, quindi non ci sono particolari problemi per allocare tutti gli oggetti File necessari.


Gli algoritmi che hai postato sono un'ottima idea di partenza.
Io preferirei però avere un algoritmo su due livelli differenti:
- il primo livello rileva stupidamente le differenze tra filesystem e database e le memorizza
- il secondo livello prende le differenze generate dal primo livello e basandosi ancora sugli array di file cercare delle affinità tra i file modificati e quindi restituire una patch "intelligente"

Questa mia scelta è dettata dal fatto che ho già tentato di scrivere un algoritmo che faccia tutto in un solo colpo e mi sono trovato molto male, perché ho la sensazione che non posso essere sicuro al 100% della sua correttezza. Dividendo il compito in due parti posso controllarne singolarmente il funzionamento.

Ho deciso che ora resto sul Php, anche se a operare sul filesystem è molto lento. Mi permette di sperimentare più velocemente di come posso farlo in Java, visto che sono abituato a programmare avendo già progettato uno schema delle classi a priori. Però il calcolo dell'hash md5 l'ho delegato ad un programma scritto in C :)

[malocchio]

Ho trovato una nota che mi ero fatto nei vecchi tentativi di scrivere l'algoritmo. Considera alcuni possibili scenari e i relativi risultati che il sistema dovrebbe restituirmi.

a..z = path; 1..9 = content;
A1 > A2 A1-modified-2
A1 > B1 (A-moved-B)
A1 > A1 B1 A-copied-B
A1 > B2 A-deleted B-new
A1 > A2 B1 (A1-modified-2 A-copied-B)/(A-moved-B A2-new)
A1 > A2 B3 A1-modified-2 B-new
A1 > B1 C1 (A-deleted A-copied-B A-copied-C)/(A-moved-B A-copied-C)/(A-moved-B B-copied-C)
A1 B1 > A1 B1 C1
A1 B1 > C1
A1 indica un file con path+nome "A" e contenuto "1".
A sinistra del ">" ci sono i file salvati in precedenza nel db, a destra la situazione attuale del filesystem. Ancora più a destra stanno i messaggi che l'ipotetico sistema dovrebbe farmi leggere. Gli slash dividono le "alternative".
L'avevo creato per farmi un'idea dei casi che posso incontrare ed è ovviamente incompleto.