Premessa. Non so se questa piccola scoperta che ho fatto di recente sia già documentata da qualche parte su Internet. Non ne ho mai sentito parlare, ma mi sembra strano che nessun’altro ci abbia pensato prima. Comunque, ci sono arrivato da solo e questo è sufficiente per scriverne sul blog.

Mi sembra inutile rimarcare il fatto che uno dei problemi che assilla chi scrive software per professione è la protezione dalle copie. In più, se programmate con .NET avete anche il problema di proteggere le applicazioni dalla decompilazione. Ovviamente i due problemi sono collegati, perchè se volete proteggere una applicazione con qualche meccanismo software (ad es. la lettura delle caratteristiche della macchina su cui il cliente installa la sua copia) occorre evitare che una semplice decompilazione + ricompilazione possa permettere ad un hacker neanche troppo esperto di bypassare la vostra protezione.

Non si tratta certo di problemi nati con .NET. Una quindicina di anni fa campavo sviluppando tool per programmatori con la mia azienda personale – la SoftWhale, dove “Whale” = “Balena” per chi non lo sapesse – e uno dei miei prodotti più gettonati era NOWAY, un programma che crittografava gli eseguibili MS-DOS proteggendoli quindi dalla decompilazione (un problema molto sentito da chi lavorava in Clipper) e permetteva di lanciarli solo sui computer per i quali la software house forniva al cliente dei codici di sblocco. NOWAY era scritto in puro Assembly 8086 e non è sopravvissuto al passaggio da MS-DOS a Windows.

In commercio esistono molti tool per .NET che servono a risolvere questi problemi, incluso obfuscator, compilatori “nativi” e chiavi hardware. Se volete proteggere la vostra IP (Intellectual Property) dovreste darci una occhiata approfondita.Per nostra fortuna, in Code Architects scriviamo soprattutto applicazioni Enterprise che non richiedono questo tipo di protezione, quindi non ho mai approfondito la questione. Immagino che questi tool facciano bene il loro lavoro, e li testerò se e quando avremo la necessità di farlo.

Se però (a) scrivete perlopiù applicazioni Windows Forms, (b) non vendete software pacchettizzato ed eseguite direttamente voi le installazioni presso il cliente, e (c) fate anche assistenza post-vendita, allora è possibile ottenere la protezione dalla decompilazione e dalle copie illegali con un meccanismo davvero molto semplice.

Cominciamo scrivendo una semplice applicazione Windows Forms. In questo esempio uso VB2005 ma ovviamente la tecnica si applica a qualsiasi linguaggio .NET.

Imports System.Reflection

Friend Module Module1

   <STAThread()> _

   Public Sub Main()

      ' in this demo we call the secret routine both directly and via reflection

      ' just to prove that either method works

       MySecretCode("Direct call")

       GetType(Module1).InvokeMember("MySecretCode", BindingFlags.InvokeMethod, _

          Nothing, Nothing, New Object() {"Reflection call"})

   End Sub

   Public Sub MySecretCode(ByVal title As String)

#If Not COPYPROTECT Then

      ' here goes all the code that you want to protect from decompilation

      MessageBox.Show("Running secret code!", title)

      ' ...

#End If

   End Sub

End Module

Poichè la variabile di compilazione COPYPROTECT non è definita, il codice nel metodo MySecretCode è incluso nell’eseguibile come se il blocco #IF non esistesse. In questo esempio proteggo un solo metodo, ma in una applicazione reale dovreste ripetere il procedimento con tutti i metodi che contengono del codice critico, magari dove implementate gli algoritmi più interessanti oppure dove controllate che l’utente abbia la licenza di eseguire il programma sul computer in questione. È importante che tutti i blocchi #IF... #ENDIF siano completamente contenuti in singoli metodi, ovvero che non capiti mai che uno di questi blocchi contenga le keyword Sub o Function (o le corrispettive End Sub o End Function). Per lo stesso motivo, potete utilizzare il meccanismo anche con le Property ma solo se utilizzate i blocchi #IF all’interno del blocco Get o Set. I blocchi #IF non devono assolutamente includere field, definizioni di eventi, o altro. 

Per completare la preparazione è opportuno definire una nuova configurazione per la soluzione. Dal menù Build selezionate il comando Configuration Manager, dalla combobox in alto a sinistra selezionate <New> e create una configurazione chiamata CopyProtected, che copia le impostazioni iniziali dalla configurazione Release.

Dopo esservi accertati che la nuova configurazione è quella attiva, create una costante condizionale di compilazione chiamata COPYPROTECT e impostata al valore True. In C# questa costante si crea dalla pagina Build delle proprietà di progetto, mentre in VB2005 dovete cliccare sul pulsante Advanced Compile Options che trovate nella pagina Compile:

Grazie a questa nuova configurazione, potete passare facilmente dalla versione normale (ossia Release) a quella copy-protected. Compilando l’applicazione in entrambe le configurazioni, avrete due eseguibili con lo stesso nome (ad es. Project1.exe) e contenenti gli stessi metadati (perchè le #IF sono sempre all’interno dei metodi e non includono campi, proprietà, o altro). L’esempio che segue presume che abbiate compilato una applicazione che si chiama Project1, che NON è firmata con uno strong name.

Preparate il setup, se necessario, utilizzando la versione Release, ma ricordatevi anche di memorizzare separatamente (ad es. su una chiavetta USB) l’eseguibile ottenuto in configurazione copy-protected e l’utility NGEN fornita con .NET Framework. Infine, recatevi presso il vostro cliente e seguite accuratamente la semplice procedura:

1) Lanciate il setup della applicazione, o più banalmente utilizzate XCOPY per copiare tutti i file sul disco rigido del cliente. In questo esempio supporremo che l’installazione sia avvenuta nella directory c:\myapp e che quindi il file eseguibile sia c:\myapp\Project1.exe.

2) Aprite una finestra di comandi, navigate nella directory che contiene l’esegubile e lanciate NGEN per creare una immagine in codice nativo della applicazione. Il comportamento di default di NGEN è OK, quindi non preoccupatevi troppo delle varie opzioni. (Lasciate aperta questa finestra, perchè vi servirà presto.)

3) Aprite una seconda finestra di comandi, navigate nella directory c:\windows\assembly\NativeImages_v2.0.50727_32\nomeassembly, dove nomeassembly è il nome dell’EXE ma senza l’estensione (Project1 in questo esempio). Noterete che in questa directory contiene una sottodirectory il cui nome è una stringa di caratteri esadecimali (nel mio esempio ho ottenuto d37032afe4f6f44588d52ca99d7bb1e5). Questa directory contiene un eseguibile dal nome nomeassembly.ni.exe (Project1.ni.exe nel nostro esempio), che contiene la versione compilata (senza IL e quindi non decompilabile) dell’eseguibile completo.

4) Dal prompt della seconda finestra dei comandi, con un comando COPY o MOVE spostate il file <nomeassembly>.ni.exe su qualche altra directory del disco rigido, ad esempio:
     MOVE d37032afe4f6f44588d52ca99d7bb1e5\Project1.ni.exe c:\
Questa operazione serve ad evitare che questo eseguibile sia cancellato dalla successiva invocazione di NGEN. Lasciate aperta anche questa seconda finestra dei comandi.

5) Sovrascrivete il file c:\myapp\Project1.exe con la versione copy-protected che avete sulla chiavetta USB.

6) Dalla prima finestra di comandi lanciate nuovamente NGEN, questa volta sulla versione copy-protected. Se questo programma venisse eseguito ora probabilmente andrebbe in errore o comunque non funzionerebbe bene, perchè alcune parti del codice non sono presenti, quindi NON lo mandate in esecuzione.

7) Dalla seconda finestra dei comandi, eseguite un comando DIR e noterete che la directory creata precedentemente (d37032afe4f6f44588d52ca99d7bb1e5, in questo esempio) è stata sostituita oppure è stata affiancata da un’altra directory dal nome random. (Nell’esempio che sto eseguendo mentre scrivo queste note è stata creata una directory di nome 9990426218ec334e9d3d62f41cb9a255.) Questa nuova directory contiene una nuova versione di Project1.ni.exe, che corrisponde alla versione in codice nativo dell'’eseguibile incompleto.

8) Sempre dalla seconda finestra dei comandi, copiate la copia precedente di Project1.ni.exe (salvata al punto #4) sulla nuova copia, ad esempio con questo comando:
     MOVE c:\project1.ni.exe 9990426218ec334e9d3d62f41cb9a255
rispondendo Yes alla domanda se intendiamo sovrascrivere il file Project1.ni.exe.

Fatto! Ora potete staccare la chiavetta USB e lasciare sul disco rigido del vostro cliente solo l'assembly "copy-protected" (in versione IL) e l'assembly completo (solo in versione compilata in modo nativo e quindi non decompilabile). Per quanto può sembrare incredibile, l'applicazione funziona correttamente e mostra le due message box Ma se provate a usare ILDASM o Reflector per sbirciare dentro il metodo MySecretCode (e qualsiasi altro metodo il cui interno è racchiuso con un #IF Not COPYPROTECT) troverete che il metodo è vuoto!

Ovviamente neanche Reflector riesce a decompilare alcunchè, visto che proprio manca il codice IL. Nè aiuta usare ILDASM sull’eseguibile Project1.ni.exe, perchè l’unica cosa che si ottiene è visualizzare un manifest senza codice IL:

Come può funzionare questa piccola magia? La spiegazione è semplice: quando lanciate un qualsiasi eseguibile .NET, per prima cosa il CLR va a controllare se vi è una “native image” che corrisponde esattamente a quella applicazione, e la corrispondenza viene cercata confrontando il nome della applicazione e la sua firma (la stringona esadecimale). Se esiste una immagine nativa, quella viene lanciata al posto dell’eseguibile. La condizione però perchè tutto il codice funzioni correttamente è che i metadati coincidano anch’essi, altrimenti troppe funzioni del CLR non funzionerebbero a dovere (il garbage collector, tanto per citarne il più importante). Nel nostro caso noi abbiamo creato due eseguibili con gli stessi metadati (ecco perchè è importante che i blocchi #IF non devono eliminare alcun metodo, campo, o proprietà), e siamo riusciti a mantenere sul disco rigido la versione IL “incompleta” mentre mandiamo in esecuzione la versione nativa “completa”.

Oltre a proteggere dalla decompilazione, molto simpaticamente questo meccanismo protegge anche dalle copie illegali. Infatti, se provate a spostare tutti i file (compreso l’eseguibile Project1.ni.exe) su un’altro computer, è praticamente certo che l'applicazione NON funzionerà correttamente. Da quel che ho potuto capire, questo accade perchè il nome della directory creata da NGEN – ovvero la “firma” di un particolare eseguibile – dipende anche da qualche informazione di sistema e quindi varia da macchina a macchina.

Per quanto interessante, questa tecnica ha alcune limitazioni abbastanza serie:

A) Se si intende proteggere una DLL peer Windows Forms l'assembly non deve essere segnato con uno strong name. Il motivo è che nel manifest degli assembly che referenziano una DLL con strong-name viene memorizzato anche l'hash dell'assembly in questione, e questo è un valore che cambia quando si compila la versione copy-protected. Quindi, visto che la DLL non può avere uno strong-name, neanche gli EXE che usano la DLL possono averlo, il che rappresenta una limitazione notevole. Questo limite non esiste per le applicazioni ASP.NET.

B) Se avviene un errore in una applicazione ASP.NET protetta oppure si modifica il Web config in qualsiasi modo, l'applicazione smette di funzionare. Il problema si risolve con un IISRESET.

C) Se avviene qualche modifica sostanziale all’hardware o al software di sistema – ad es. la sostituzione della CPU, l’aggiunta di memoria, l'upgrade del sistema operativo, ecc. – il .NET Framework non può più usare l’immagine nativa e lancerà l’eseguibile normale, che ovviamente non funzionerà bene perchè alcune porzioni di codice mancano. In quel caso occorre ripetere l’installazione e tutto il procedimento descritto sopra. È importante quindi mettere in guardia il vostro cliente dai rischi che corre facendo questi upgrade durante la notte, il fine settimana, o mentre siete in vacanza alle Bahamas.

Per mitigare il problema potete almeno fare in modo che l’applicazione mostri un chiaro messaggio di errore quando l’immagine nativa non è aggiornata e il CLR torna ad usare l’eseguibile “incompleto”. Per fare questo è sufficiente avere una istruzione MessageBox.Show in un blocco #IF COPYPROTECT (senza il Not), ad es:

Friend Module Module1
    Public Sub Main()     

#If COPYPROTECT Then

        MessageBox.Show("This app requires reinstallation. Please contact tech support.")

        Exit Sub

#End If

        ' Here the real application begins

        ' ...

    End Sub

End Module

Per quanto ne so, Microsoft non ha mai documentato quali modifiche al sistema disabilitano l’immagine nativa creata con NGEN, quindi non posso essere più preciso su questo punto. Se qualcuno conosce qualche articolo che spiega questi casi, lo menzioni nei commenti.

Per il resto, ho fatto un po’ di prove, sembra che tutto quanto fili liscio e che la tecnica non abbia altre controindicazioni. Se vi imbattete in qualche problema, fatemelo sapere.

In genere mi piace molto la possibilità di estendere all’infinito la potenza delle mie applicazioni semplicemente aggiungendo un reference a qualche assembly che contiene le funzioni o i controlli che mi servono. Mi piace molto meno il fatto di dover distribuire numerose DLL con i miei eseguibili. In questo articolo illustrerò una tecnica per comprimere tutte (o quasi) le DLL satelliti di una applicazione Windows Forms e “fonderle” con l’eseguibile principale.

Tutti i file che vi servono sono contenuti in questo ZIP, che contiene l’utility AsmZip.exe (che si lancia dalla riga di comando) e due file sorgenti, Unzipper.cs e Unzipper.vb. Copiate l’utility AsmZip in una directory presente nel path di sistema, per poterla richiamare facilmente.

I passi da seguire
Ecco i passi necessari per implementare questa tecnica.

1) Aggiungere il file Unzipper.vb o Unzipper.cs al progetto principale della vostra applicazione, rispettivamente se lavorate in Visual Basic o Visual C#.

2) Nella procedura Main, aggiungete una istruzione che inizializza la classe AssemblyUnzipper (contenuta nel file sorgente aggiunto al punto precedente):
       ' (Visual Basic 2005)
       CodeArchitects.AssemblyUnzipper.Initialize()
       // Visual C# 2005
       CodeArchitects.AssemblyUnzipper.Initialize();
È di fondamentale importanza che questo codice sia eseguito prima di ogni altra istruzione del programma, in particolare prima di mostrare un form che contiene al suo interno dei controlli di cui non volete distribuire le DLL. Se lavorate in VB e l’applicazione ha un form di partenza (e quindi non avete a disposizione la procedura Main), dovete inserire queste istruzioni nel costruttore statico del form di partenza:
      Shared Sub New()
        CodeArchitects.AssemblyUnzipper.Initialize()
       End Sub

3) compilate la soluzione, ovviamente in Release mode visto che utilizzerete questa tecnica poco prima di consegnare l’eseguibile al vostro cliente.

4) aprite una finestra con il prompt dei comandi nella directory di output del programma, e lanciate l’utility AsmZip in questo modo:
             AsmZip main.exe *.dll
dove main.exe è il nome dell’eseguibile principale. Il comando precedente comprime *tutte* le DLL nella directory e mette i dati compressi in coda al file main.exe. Per comprimere solo alcune DLL tra quelle presenti nella directory dovete specificarne i nomi, come in questo esempio:
             AsmZip main.exe CodeArchitects*.dll Microsoft*.dll
(Ci possono essere dei buoni motivi per non comprimere alcune DLL usate dalla applicazione, come spiego più avanti.)

5) a questo punto potete cancellare tutte le DLL che avete compresso, perchè l’applicazione – grazie alla classe AssemblyUnzipper - è in grado di trovarle da sola in coda al proprio eseguibile, di decomprimerle, e di caricarle in memoria.

I vantaggi
Prima di procedere ad una spiegazione più dettagliata di come funziona questa tecnica, proverò a riassumere i suoi vantaggi:

a) deployment semplificato: dovete distribuite un minor numero di file (spesso il solo EXE principale)
b) applicazioni più robuste: non vi è il rischio che il cliente renda il programma inutilizzabile cancellando inavvertitamente una DLL
c) minore occupazione su disco (tutte le DLL sono compresse e accodate all'EXE principale)
d) la possibilità di “nascondere” i vostri piccoli segretucci, ad esempio quali controlli di terze parti avete utilizzato nella applicazione.
e) un maggior grado di protezione: il codice nelle DLL compresse non può essere decompilato, perlomeno non senza avere estratto e decompresso i singoli eseguibili.

È evidente che gli ultimi due punti non costituiscono una vera barriera per un programmatore anche solo un po’ esperto, se è davvero intenzionato a sapere quali DLL avete usato e a decompilarle. Per ottenere queste informazioni un hacker dovrà soltanto decompilare l’EXE principale, capire come funziona la classe AssemblyUnzipper, e scrivere un programmino che ne ripete il funzionamento ma salva su disco gli assembly compressi. In definitiva, questa tecnica permette di nascondere il vostro sorgente e le vostre DLL alla prima occhiata, ma non potete certo considerarla una tecnica di protezione dal reverse engineering.

L’utility AsmZip usa la classe GZipStream per comprimere le DLL originarie, quindi il grado di compressione che si può raggiungere con questa tecnica non è paragonabile a quello ottenibile con WinZip o WinRar, ma è comunque più che sufficiente, come mostra la figura.

Come funziona
Questa tecnica si basa sull’evento AssemblyResolve dell’oggetto AppDomain, che scatenato quando il .NET Framework deve caricare un assembly richiesto dalla applicazione. Gestendo opportunamente questo evento potete mettere in pratica tante piccole “magie” che non sarebbero possibili in alcun altro modo. Ad esempio, potreste caricare gli assembly satelliti di una applicazione da uno share di rete oppure da un campo blob di un database.

La classe AssemblyUnzipper, invece, usa questo evento per cercare l’assembly richiesto da uno stream compresso che è stato accodato all’eseguibile del programma principale.
      // the handler for AssemblyResolve event
      static Assembly CurrentDomain_AssemblyResolve(object sender, ResolveEventArgs e)
      {
         // find the assembly with given name, cause error if not found
         AssemblyInfo info = null;
         if ( AsmInfos.TryGetValue(e.Name, out info) )
            return ExtractAssembly(info);
         // signal error
         Debug.WriteLine("Failed to uncompress assembly " + info.Name);
         return null;
      }
Ciascun oggetto AssemblyInfo tiene traccia di dove, nel file EXE, è memorizzato ciascuna DLL compressa. Il dictionary AsmInfos permette di trovare subito le informazioni associate ad una DLL con un certo nome; questo dictionary è creato nel metodo Initialize, alla partenza del programma, e viene poi usato ogni volta che l’applicazione richiede una DLL.

Non spiegherò nel dettaglio come funziona il codice, perchè il sorgente è commentato in modo adeguato, sia nella versione VB che C#.

I limiti
Ho provato questa tecnica con numerose applicazioni Windows Form, senza alcun problema. Il limite principale deriva dal fatto che gli assembly caricati in questo modo hanno la proprietà Location nulla, ma se non utilizzate reflection per esplorare le proprietà degli assembly non ve ne accorgerete neanche. Ad esempio, se la vostra applicazione carica gli assembly dinamicamente da una certa directory, magari per esplorarne gli attributi, è evidente che quel codice non può funzionare se le DLL sono state compresse e cancellate. In tal caso dovrete evitare di processare queste DLL con AsmZip.

La classe AssemblyUnzipper funziona solo con applicazioni Windows Forms. Da quanto ne so, è possibile utilizzare l’evento AssemblyResolve anche con applicazioni ASP.NET, ma non è possibile usare la mia classe in quel contesto. In realtà, i problemi che questa tecnica risolve non sono molto sentiti in ambito ASP.NET, quindi non credo che abbia senso preparare una versione per applicazioni di quel tipo.

L'unico altro limite è che questa tecnica funziona con le DLL, ma non con l'EXE principale. Se avete un EXE di grosse dimensioni che richiamo poche piccole DLL, il vantaggio che ne potete ricavare è molto limitato. In tal caso, potete comunque raggiungere il massimo grado di compressione "complessiva" spostando i form dall’eseguibile principale in una DLL, e comprimendo poi tale DLL con AsmZip. In teoria, l’EXE di partenza dovrebbe contenere solo lo splash screen (se ne avete uno), e poi dovrebbe caricare il form principale dalla DLL che contiene l’applicazione vera e propria. In questo modo è spesso possibile ottenere un fattore di compressione complessivo superiore al 60 per cento.

Nota: nella prima implementazione di questa tecnica ero riuscito a comprimere anche l'EXE. In tal caso accodavo poi tutti i dati compressi a un piccolo eseguibile "stub" che aveva il solo compito di fare partire l'eseguibile vero e proprio. Dopo alcune prove, però, mi sono reso conto che i problemi che si venivano a creare erano superiori ai vantaggi, per cui ho deciso di utilizzare il metodo descritto in questo articolo.

Per anni gli americani ci hanno inflitto (e afflitto con) una serie infinita di programmi per il baseball, di cui sinceramente a noi italiani non ce ne potrebbe frega' de meno. Questa volta si fanno perdonare con una piccolo programmino per seguire la propria squadra del cuore durante il campionato del mondo. Non l'ho ancora installato, ma dalla descrizione si direbbe ben fatto, è localizzato in oltre una dozzina di lingue, può funzionare come RSS reader, e altre cosucce ancora. Lo potete scaricare da questa pagina.

Siamo alla quarta puntata dedicata alla libreria CAPermutations, uno dei progetti a cui dedico il mio (poco) tempo libero. Trovate le puntate precedenti (nell'ordine) in questo, questo, e quest'altro post. Ancora un volta, ricordo che la libreria è liberamente utilizzabile nei propri programmi, purchè siano freeware e no-profit.

In questi giorni ho provato ad utilizzare le capacità combinatorie di CAPermutation per risolvere un problema combinatorio decisamente complesso, quello della enumerazione dei quadrati magici di ordine N. Per chi non lo sapesse, un quadrato magico è una griglia di NxN celle, ciascuna contenente un numero intero naturale compreso tra 1 e N*N (senza ripetizioni), in modo che la somma dei numeri lungo le N righe, le N colonne, e le due diagonali sia sempre uguale a un numero detto costante magica, il cui valore è pari a N * (N * N + 1) / 2. Ad esempio, la figura seguente mostra il primo dei quadrati magici di ordine 4 (corrispondente alla costante magica 34).

Questi quadrati si chiamano "magici" perchè nel Medioevo ad essi venivano attribuite delle proprietà, per l'appunto, magiche. Quadrati di ordine 3 e 4 si trovano spesso nascosti in dipinti e incisioni, ed esiste un bel po' di narrativa su questo tema - scientifica, mistica, e numerologica. Ma sembra che addirittura i primi a usare questi quadrati siano stati i Cinesi, almeno una decina secoli prima dell'era cristiana. Inutile dire che tramite Google potete trovare un sacco di riferimenti interessanti, incluso siti interamente dedicati all'argomento (ad es. Grogono Magic Squares)

Nel XXI secolo l'interesse per l'aspetto magico di questi quadrati è ovviamente molto scemato - anche se sicuramente esisteranno dei fanatici numerologi che non si sono accorti dei secoli che passano - mentre resta sicuramente l'interesse dal punto di vista computazionale. Come molti problemi di matematica ricreativa, la enumerazione di tali quadrati non ha alcuna applicazione pratica, eppure vi assicuro che se sapete impostare correttamente un programma di questo tipo allora siete in grado di risolvere anche una classe di problemi complessi di ottimizzazione molto più pratici e utili. A me sicuramente questo tipo di "ginnastica mentale" è servita tantissimo in mille progetti più commerciali.

Riducendo il problema all'osso, si tratta di trovare una permutazione dei numeri 1,2,.... N*N in grado di soddisfare il critero della somma costante lungo le righe, le colonne, e le diagonali. Ma già con i quadrati di ordine 4 si vede subito che occorre lavorare con ben 20,922,789,888,000 permutazioni, ovvero il fattoriale di 16. Incrementando N di una sola unità il numero cresce di ben 741,354,768,000 volte, e diventa pari a 15,511,210,043,330,985,984,000,000, ovvero oltre 15 milioni di miliardi di miliardi di combinazioni da analizzare!!! Un personal computer deve lavorare per alcune ore (e fare girare un programma super-ottimizzato) per arrivare alla conclusione che ci sono esattamente 68,826,306 quadrati magici di ordine 5, se si scartano le riflessioni e le rotazioni. A tutt'oggi il numero dei quadrati magici di ordine 6 è sconosciuto, e il loro numero è stato solo stimato. In altre parole, scrivete un programma per contare i quadrati magici di ordine 6 e passerete alla storia!

Lo scopo di questo articolo è, molto più mestamente e modestamente, mostrare come utilizzare la libreria CAPermutations per risolvere il problema dei quadrati magici di ordine 3, 4, e 5. E' anche pronto a risolvere il problema di ordine 6, ma probabilmente dovreste lasciare acceso il vostro PC per qualche secolo o millennio per poter davvero contare tutte le soluzioni. A dire il vero, io non ho neanche provato a enumerare tutte le soluzioni di ordine 5, che potrebbe richiedere anche un giorno o due di CPU.

E' abbastanza facile ereditare dalla classe Permutations<int> e imporre che i vincoli del problema siano rispettati ogni volta che viene aggiunto un numero alla grigia. Ecco la prima parte della classe:

public class MagicSquares : Permutations<int>
{
   // these fields are initialized by the constructor
   public readonly int Side;
   public readonly bool DiscardDerivates = true;
   private readonly int Length;
   private readonly int MagicSum;

   // these arrays contain the row/col corresponding to a given index
   public int[] IndexRow;
   public int[] IndexCol;

   // these fields are used by the filter method to keep track of how many elements are on each row, column, diagonal
   int[] rowCount;
   int[] colCount;
   int mainDiagCount;
   int secDiagCount;

   // these fields are used by the filter method and keep track of sums along rows, columns, and diagonals
   int[] rowSums;
   int[] colSums;
   int mainDiagSum;
   int secDiagSum;

   // the constructor 
   public MagicSquares(int side, bool discardDerivates) : base( CreateIndices(1, side*side), side*side, PermutationKind.Permutations, 1)
   {
      this.Side = side;
      this.DiscardDerivates = discardDerivates;
      this.Length = side * side;
      this.MagicSum = side * ( side * side + 1 ) / 2;
   }

Invece di generare tutte le permutazioni e poi scartare quelle che non vanno bene, il programma controlla per quanto possibile che i vincoli siano rispettati di volta in volta, ovvero cerca di potare l'albero delle soluzioni il prima possibile, in modo da scartare la maggior parte delle sequenze che non possono portare mai a dei risultati. Per questo motivo, i numeri sono posizionati sulla griglia secondo un ordine particolare, che dipende dalla dimensione del quadrato. Ad esempio, nel caso dell'ordine 4, sono prime sistemate i numeri nelle caselle d'angolo (perchè in questo modo è possibile scartare subito rotazioni e riflessioni), poi si completa la prima riga (riga 0), poi l'ultima riga (riga 3), poi la prima colonna e l'ultima colonna (colonna 0 e colonna 3), e infine le caselle non ancora riempite in riga 1 e 2. Per determinare quale ordine seguire, la classe utilizza due array, IndexRow e IndexCol, in modo che l'elemento IndexRow[n] contiene il numero di riga della N-simo numero posto sulla griglia, e IndexCol[n] la sua colonna. Per inizializzare questi array e le altre variabili usate durente il backtracking si fa l'override del metodo OnInitialize:

// init the fields and counters used by the filter method

protected override PermutationResult OnInitialize()
{
   // init index*** fields
   IndexRow = new int[Length];
   IndexCol = new int[Length];

   // but next, refill the same arrays again with sequences optimized for each value of Side
   // it is essential that the first four elements are the four corners, in this order
   // top-left, top-right, bottom-left, bottom-right
   if ( Side == 3 )
   {
      // optimized case when side = 3
      IndexRow = new int[] { 0, 0, 2, 2, 1, 0, 1, 1, 2};
      IndexCol = new int[] { 0, 2, 0, 2, 1, 1, 0, 2, 1};
   }
   else if ( Side == 4 )
   {
      // optimized case when side = 4
      // four corners + row 0 + row 3 + col 0 + col 3 + row 1 + row 2
      IndexRow = new int[] { 0, 0, 3, 3, 0, 0, 3, 3, 1, 2, 1, 2, 1, 1, 2, 2};
      IndexCol = new int[] { 0, 3, 0, 3, 1, 2, 1, 2, 0, 0, 3, 3, 1, 2, 1, 2};
   }
   else if ( Side == 5 )
   {
      // optimized case when side = 5
      // four corners + main diag + sec diag + row 1 + col 1 + col 3 + row 4 + row 2 + col 2 + row 1 + row 3
      IndexRow = new int[] { 0, 0, 4, 4, 1, 2, 3, 1, 3, 0, 0, 0, 2, 4, 2, 4, 4, 2, 2, 1, 3, 1, 1, 3, 3};
      IndexCol = new int[] { 0, 4, 0, 4, 1, 2, 3, 3, 1, 1, 2, 3, 1, 1, 3, 3, 2, 0, 4, 2, 2, 0, 4, 0, 4};
   }
   else if ( Side == 6 )
   {
      // optimized case when side = 6
      // four corners + row 0 + row 5 + col 1 + col 4 + main diag + sec diag + row 2 + row 3 + col 0 + col 5 + row 1 + row 4
      IndexRow = new int[] { 0, 0, 5, 5, 0, 0, 0, 0, 5, 5, 5, 5, 1, 2, 3, 4, 1, 2, 3, 4, 2, 3, 2, 3, 2, 2, 3, 3, 1, 4, 1, 4, 1, 1, 4, 4 };
      IndexCol = new int[] { 0, 5, 0, 5, 1, 2, 3, 4, 1, 2, 3, 4, 1, 1, 1, 1, 4, 4, 4, 4, 2, 3, 3, 2, 0, 5, 0, 5, 0, 0, 5, 5, 2, 3, 2, 3 };
   }
   else
   { 
      // unsupported side
      throw new Exception("Unsupported Side value");
   }

   // init other values used by the filter
   rowCount = new int[Length];
   colCount = new int[Length];
   mainDiagCount = 0;
   secDiagCount = 0;
   // initialize ***sum fields
   rowSums = new int[Side];
   colSums = new int[Side];
   mainDiagSum = 0;
   secDiagSum = 0;
   // signal it's ok to proceed
   return PermutationResult.Proceed;
}

Il metodo di filtro deve controllare se la permutazione parziale appena generata dalla classe base soddisfa i vincoli. Invece però di contare ogni volta le somme lungo righe, colonne e diagonali, il programma conserva le somme parziali nelle variabili ***Sums, mentre nelle variabili ***Count conserva il numero di celle riempite lungo le stesse righe, colonne e diagonali. Una permutazione viene scartata quando il numero appena aggiunto completa una riga, colonna, o diagonale ma la somma dei numeri su quella riga, colonna o diagonale non corrisponde alla costante magica. In alcuni casi, pero', è possibile scartare un numero anche se non completa una riga, colonna o diagonale: questo avviene quando la somma dei valori lungo la riga, colonna o diagonale è già superiore alla costante magica. Per controllare e scartare le permutazioni occorre fare l'override del metodo OnNewPermutations:

protected override PermutationResult OnNewPermutation(int[] permutation, int level)
{
   // this is the element just added
   int number = permutation[level];
   // evaluate row and col of the element just added
   int row = IndexRow[level];
   int col = IndexCol[level];
   // detect whether the number is on the main or secondary diagonal
   bool onMainDiag = ( row == col );
   bool onSecDiag = ( row == ( Side - 1 - col ) );

   // check sum of value along the current row
   if ( rowCount[row] == Side - 1 )
   {
      // if the element completes a row, the sum along the row must be equal to the magic sum
      if ( rowSums[row] + number != MagicSum )
         return PermutationResult.Backtrack;
   }
   else
   {
      // if the element doesn't complete a row, the sum along the row must less than magic sum
      if ( rowSums[row] + number >= MagicSum )
         return PermutationResult.Backtrack;
   }

   // check sum of values along the current column
   if ( colCount[col] == Side - 1 )
   {
      // if the element completes a column, the sum along the column must be equal to the magic sum
      if ( colSums[col] + number != MagicSum )
         return PermutationResult.Backtrack;
   }
   else
   {
      // if the element completes a column, the sum along the column must be less than the magic sum
      if ( colSums[col] + number >= MagicSum )
         return PermutationResult.Backtrack;
   }

   // if the element is on the primary diagonal
   if ( onMainDiag )
   {
      if ( mainDiagCount == Side - 1 )
      {
         // if the element completes the diagonal, the sum along the diagonal must be equal to the magic sum
         if ( mainDiagSum + number != MagicSum )
            return PermutationResult.Backtrack;
      }
      else
      {
         // if the element doesn't complete the diagonal, the sum must be less than the magic sum
         if ( mainDiagSum + number >= MagicSum )
            return PermutationResult.Backtrack;
      }
   }

   // if the element is on the secondary diagonal
   if ( onSecDiag )
   {
      if ( secDiagCount == Side - 1 )
      {
         // if the element completes the diagonal, the sum along the diagonal must be equal to the magic sum
         if ( secDiagSum + number != MagicSum )
            return PermutationResult.Backtrack;
      }
      else
      {
         // if the element doesn't complete the diagonal, the sum must be less than the magic sum
         if ( secDiagSum + number >= MagicSum )
            return PermutationResult.Backtrack;
      }
   }

   // if we get here, the permutation is ok and we can update partial sums
   rowCount[row]++;
   rowSums[row] += number;
   colCount[col]++;
   colSums[col] += number;
   if ( onMainDiag )
   {
      mainDiagCount++;
      mainDiagSum += number;
   }
   if ( onSecDiag )
   {
      secDiagCount++;
      secDiagSum += number;
   }

   // signal that new permutation is ok
   return PermutationResult.Proceed;
}

In realtà si potrebbe scrivere del codice ancora più ottimizzato, che sia in grado di scartare una permutazione anche quando manca un solo elemento per completare una riga, colonna o diagonale - basta controllare che la differenza tra la somma corrente e la costante magica corrisponde a un numero non ancora utiizzato - ma non ho voluto complicare troppo il codice. L'ultima cosa che resta da fare è l'override del metodo OnBacktrack, per aggiornare i vari vettori quando in fase di backtracking un numero viene tolto dalla griglia:

protected override PermutationResult OnBacktrack(int[] permutation, int level)
{
   // this is the element to be removed
   int number = permutation[level];
   // evaluate row and col of the element 
   int row = IndexRow[level];
   int col = IndexCol[level];
   // detect whether the number is on the main or secondary diagonal
   bool onMainDiag = ( row == col );
   bool onSecDiag = ( row == ( Side - 1 - col ) );
   // updates counters and return 
   rowCount[row]--;
   rowSums[row] -= number;
   colCount[col]--;
   colSums[col] -= number;
   if ( onMainDiag )
   {
      mainDiagCount--;
      mainDiagSum -= number;
   }
   if ( onSecDiag )
   {
      secDiagCount--;
      secDiagSum -= number;
   }
   return PermutationResult.Backtrack;
}

Il programma completo - che include anche il codice per scartare rotazioni e riflessioni - è disponibile in sorgente a questo link: MagicSquares.zip (70.2 KB). Lo zippone comprende anche le versioni più recenti dei programmi che ho mostrato nei precedenti articoli, il tutto in un unico progetto Visual Studio 2005.

UPDATE: dopo aver messo online questo articolo ho modificato leggermente la libreria CAPermutations, e il link ora punta alla versione aggiornata. Tutto quanto scritto nel post originario resta valido, eccetto che i metodi in override restituiscono un enumerativo anzichè un booleano.

Nel primo e nel secondo post di questa serie ho introdotto la libreria CAPermutations e ho mostrato come sia in grado di risolvere alcuni problemi combinatori classici, tipo la generazione di anagrammi e il problema delle regine e amazzoni. In questo articolo mostrerò alcune altre feature molto interessanti di questa libreria e le userò per realizzare un semplice - ma potente e super-efficiente - programma per lo sviluppo di sistemi Totocalcio.

Prima di tutto un veloce ripasso. Come ho mostrato nei precedenti esempi, il costruttore della classe Permutations riceve in input i seguenti argomenti, tutti opzionali eccetto il primo:
1. l’array degli elementi da permutare
2. il numero di elementi che dovranno apparire nella permutazione
3. un enumerativo che indica se desideriamo listare le permutazioni o le combinazioni degli elementi
4. il numero massimo di occorrenze di ciascun elemento
5. l’indirizzo di un metodo di filtro

Ecco ad esempio il codice che permette di generare tutte le parole di cinque lettere e contenenti esclusivamente i caratteri A-G, dove ciascun carattere non può comparire più di due volte:

char[] elements = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
Permutations<char> perms = new Permutations<char>(elements, 5, PermutationKind.Permutations, 2);
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

In aggiunta ai dati che si passano al costruttore, è però possibile impostare numerosi altri campi della classe dopo averla istanziata. In particolare, la classe espone gli array MinOccurrences e MaxOccurrences, che permettono di impostare il numero minimo e massimo di occorrenze di ciascun elemento nel risultato finale. Per default, tutti gli elementi del vettore MinOccurrences sono impostati a zero e tutti gli elementi di MaxOccurrences sono uguali al valore del 4° argomento passato al costruttore – il che di fatto significa che non imponiamo alcun vincolo specifico al numero di occorrenze - ma dopo aver creato una istanza di Permutations è possibile modificare questi array per imporre delle condizioni particolari.

Ad esempio, possiamo affinare il codice precedente specificando che i caratteri ‘A’ e ‘E’ devono essere sempre presenti e anzi possono comparire fino a tre volte, mentre il carattere ‘B’ può comparire al massimo una volta:

char[] elements = { 'A', 'B', 'C', 'D', 'E', 'F', 'G' };
Permutations<char> perms = new Permutations<char>(elements, 5, PermutationKind.Permutations, 2);
perms.MinOccurrences[0] = 1; // 0 = index of char 'A' in the elements array
perms.MaxOccurrences[0] = 3;
perms.MaxOccurrences[1] = 1; // 1 = index of char 'B' in the elements array
perms.MinOccurrences[4] = 1; // 4 = index of char 'E' in the elements array
perms.MaxOccurrences[4] = 3;
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

L’oggetto Permutation espone anche il vettore MaxConsecutiveOccurrences, che indica per ciascun elemento quante occorrenze consecutive possono trovarsi nel risultato. Quindi ad ad esempio possiamo scartare AABCD ma accettare ABACD usando questo codice:

// aggiungere a tutti i vincoli precedenti...
perms.MaxConsecutiveOccurrences = new int[] {1, 1, 1, 1, 1, 1, 1};
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

A cosa può servire impostare il numero massimo di occorrenze consecutive? Ad esempio, se i caratteri A-G rappresentano altrettante città, l’output del codice precedente rappresente tutti i percorsi possibili che potete seguire per visitarne alcune di esse (massimo 5), ripassando se necessario fino a tre volte per A oppure E, oppure fino a due volte per tutte le altre città eccetto B. Visto che le permutazioni rappresentano un tratto di viaggio, occorre scartare le tratte che cominciano e terminano nella stessa città, cosa che si fa appunto impostando pari a 1 il valore di MaxConsecutiveOccurrences per tutti gli elementi.

Così formulato, l’esempio può sembrare poco realistico, ma nel settore dei problemi combinatoriali imporre un limite massimo alle occorrenze consecutive può essere molto utile. Ad esempio, nella stesura di un orario scolastico di solito si impone che un professore non possa occupare la stessa aula per più di due ore oppure che gli alunni di una determinata classe non possano occupare un laboratorio per più di un numero stabilito di ore. Vedremo anche tra un attimo che i vettori MinOccurrences, MaxOccurrences, e MaxConsecutiveOccurrences saranno molto utili nella preparazione di un programma per lo sviluppo dei sistemi di totocalcio.

Una feature molto potente della classe Permutations è la possibilità di indicare esattamente quali elementi si possono trovare in determinate posizioni del risultato. Tornando a considerare l’esempio precedente, potremmo voler imporre che il nostro viaggio tra le città A-G possa cominciare e terminare solo dalle città A, D e E, perchè sono le uniche che sono servite da un aereoporto. Una possibile soluzione al problema è di impostare un metodo di callback che scarta tutte le permutazioni che non soddisfano questa condizione, ma è molto più facile agire sul campo ValidIndices della classe Permutations. Questo campo è un vettore di vettori di tipo T (dove T è il tipo parametro della classe generica Permutations), quindi occorre modificare l’elemento con indice 0 (che contiene gli indici validi che può assumere l’elemento nella prima posizione del risultato) e l’elemento 4 (che contiene gli indici validi che può assumere il quinto e ultimo elemento del risultato).

// aggiungere a tutti i vincoli precedenti...
//
// indica che il primo e ultimo elemento della soluzione
// deve essere scelto tra A,D,E, che nel vettore elements
// si trovano agli indici 0,3,4
perms.ValidIndices[0] = new int[] { 0, 3, 4 };
perms.ValidIndices[4] = new int[] { 0, 3, 4 };
foreach ( char[] chars in perms )
   Console.WriteLine(new string(chars));

Passiamo ora ad una applicazione pratica “seria”, benchè dedicata al gioco del Totocalcio. Attualmente il Totocalcio non è più un gioco molto popolare, ma quelli di voi con più di vent’anni si ricorderanno sicuramente la rivoluzione che il personal computer portò nel mondo degli scommettitori “professionali”. Improvvisamente era possibile impostare, sviluppare e ridurre un sistema di Totocalcio comodamente a casa propria, e magari stampare pure le schedine su una apposita stampante. Ricordo numerose software house che negli anni ’80 avevano a catalogo programmi di questo tipo, e per molti sviluppatori questo tipo di software ha rappresentato una grande fonte di reddito.

Certo, resta valida la ovvia considerazione che se un programmatore trovasse davvero la “sistema perfetto” per azzeccare il 13 (anzi il 14, visto che da qualche anno si gioca su 14 partite...) allora potrebbe fare molti più soldi giocando il sistema perfetto egli stesso, piuttosto che vendere il software. Ma questo è un dettaglio: quello che è importante in questa sede è che lo sviluppo di sistemi di Totocalcio (ma anche di altri giochi simili, come il Totip e il TotoGol) rappresenta un irresistibile banco di prova per chi si diletta di calcolo combinatorio.

La figura seguente mostra la videata principale (nonchè l’unica ) del programma per lo sviluppo di sistemi Totocalcio che potete scaricare in sorgente da questo link: SistemaTotocalcio.zip (55.56 KB). Il file contiene anche la nuova versione della libreria CAPermutations (che è stata finalmente arricchita dai commenti XML dei vari metodi e campi) e delle altre demo già mostrate dei post precedenti. Ricordo che la libreria è usabile liberamente nei propri programmi freeware e no-profit ma potete contattarmi se volete utilizzarla in altri contesti.

Un breve disclaimer prima di continuare: spero sia chiaro che la mia intenzione non è di creare un programma professionale per lo sviluppo di sistemi, anche perchè ce ne sono di ottimi in giro. Il mio unico obiettivo è di mostrare come risolvere il problema combinatorio legato a questo gioco utilizzando la libreria CAPermutations.

Come vedete, il programma permette di impostare il pronostico sulle 14 partite, e una serie di vincoli, tra cui il numero minimo, massimo e massimo consecutivo dei tre segni.

Lo scommettitore dovrebbe impostare i 14 pronostici indicando come primo simbolo (il simbolo principale) il risultato più probabile; come secondo simbolo un risultato prevedibile ma non quanto il simbolo principale; come terzo simbolo quello che lo scommettitore considera una vera e propria sorpresa. Agendo sui controlli nel gruppo “Varianti e sorprese” lo scommettitore può dosare in un certo senso il grado di “imprevedibilità” su cui vuole puntare. È evidente, ad esempio, che se impostando un valore alto come numero minimo di varianti o di sorprese, si ottiene di ridurre notevolmente il numero di colonne dello sviluppo (e quindi la probabilità di vincere) ma in compenso si punta ai risultati meno prevedibili e quindi che potenzialmente potrebbero dare una vincita più alta della media.

Vediamo ora una breve descrizione di come funziona il programma dietro le quinte. Lo sviluppo di un sistema di Totocalcio si riduce in un certo senso a creare tutte le permutazioni dei simboli 1, 2, e X. Per comodità, internamente il programma non permuta questi caratteri ma più semplicemente le cifre 0 (corrispondente al segno ’1’), 1 (corrispondente al ’2’) e 2 (corrispondente al simbolo ’X). Il programma non deve creare davvero tutte le permutazioni delle triple ‘12X’, ma solo le permutazioni che rispondono ai pronostici delle partite, cosa che il codice fa assegnando valori adeguati agli elementi del vettore ValidIndices. Ad esempio, per specificare che per la quarta partita i simboli validi sono sono 1 e X (vedi figura) il codice esegue qualcosa del genere:

perms.ValidIndices[3] = new int[] { 0, 2 };

mentre per la quinta partita (il cui pronostico è ‘1X2’) il codice è il seguente:

perms.ValidIndices[3] = new int[] { 0, 2, 1 };

(notate quindi che è anche possibile impostare sequenze di indici non crescenti).

Grazie alla presenza dei campi ValidIndices, MinOccurrences, MaxOccurrences, e MaxConsecutiveOccurrences, la maggior parte dei vincoli legati allo sviluppo del sistema sono di fatto implementati dalla classe Permutations. Gli unici vincoli che la classe base non risolve sono quello sul numero minimo e massimo di segni principali, varianti, e sorprese, ma anche questi vincoli si implementano facilmente.

Infatti, la classe Permutations espone il vettore Indices, che per ciascuna partita indica la posizione in ValidIndices del simbolo inserito nella soluzione. Quindi contare quante varianti sono presenti nella soluzione corrente significa contare – nel metodo di filtro - quanti elementi pari a 1 sono presenti nel vettore Indices. E contare quante sorprese vi sono corrisponde a contare gli elementi del vettore pari a 2.

Se a questo punto non riuscite più a seguire la mia descrizione non vi preoccupate: il problema non è affatto banale e la cosa migliore da fare è studiare il sorgente della classe SistemaTotocalcio. Questa classe eredita da Permutations<int> e aggiunge un paio di vettori che conservano il valore minimo e massimo di segni principali, varianti e sorprese:

public class SistemaTotocalcio : Permutations<int>
{
   const int NumPartite = 14;

   // valori usati per il filtro del sistema
   public int[] MinVarianti = new int[3];
   public int[] MaxVarianti = new int[3];

   // questo è il numero di varianti (privato, perchè usato solo dal filtro)
   // varianti[0] sono le principali, varianti[1] le varianti, varianti[2] le sorprese
   private int[] Varianti = new int[3];

   // il costruttore non ha argomenti
   public SistemaTotocalcio()
      : base( new int[] { 0, 1, 2}, NumPartite, PermutationKind.Permutations, NumPartite)
   {
      // imposta il valore max di varianti (modificabile in seguito dal client)
      for ( int i = 0; i <= 2; i++ )
         this.MaxVarianti[i] = NumPartite;

      // tutti gli altri array sono correttamente inizializzati
   }

   // ... (continua)....

Quando parte il computo delle permutazioni – ovvero delle colonne generate dallo sviluppo del sistema – occorre inizializzare il vettore Varianti, che viene usato poi dal filtro. Questo si ottiene facendo l’override del metodo OnInitialize, che è chiamato al momento opportuno dalla classe Permutations. Questo metodo deve restituire PermutationResult.Proceed se i dati in input sono OK, oppure PermutationResult.Cancel se vi è un problema e l'enumerazione non deve neanche partire:

   // override del metodo per validare i dati e
   // inizializzare i valori usati dal filtro
   protected override PermutationResult OnInitialize()
   {
      // inizializza l'array Varianti e indica che si può proseguire
      this.Varianti = new int[3];
      return PermutationResult.Proceed
   }

Poichè la classe SistemaTotocalcio eredita da Permutations, per filtrare le permutazioni man mano che vengono generate non si usa un metodo di callback, ma si deve fare l’override del metodo protetto OnNewPermutation. Come ho spiegato sopra, il controllo sul numero minimo, massimo e massimo consecutivo dei segni lo fa la classe base Permutations, quindi nel filtro dobbiamo solo controllare il valore minimo e massimo dei segni principali, delle varianti e delle sorprese.

   // il filtro, sotto forma di override

   protected override PermutationResult OnNewPermutation(int[] colonna, int partita)
   {
      // questo è l'indice usato per questa partita (0=princ, 1=variante, 2=sorpresa)
      int index = base.Indices[partita];
      // esci se vi sono già troppe varianti di questo tipo
      if ( Varianti[index] >= MaxVarianti[index] )
         return PermutationResult.Backtrack;

      // aggiornal il contatore delle varianti di questo tipo
      Varianti[index]++;
      // restituisci false se il numero di varianti è minore del minimo
      // e non potrebbe diventare mai pari o maggiore del
      // minimo perchè non ci sono sufficienti partite da analizzare
      int rimaste = 13 - partita;
      if ( Varianti[0] + rimaste < MinVarianti[0] || Varianti[1] + rimaste < MinVarianti[1]
         || Varianti[2] + rimaste < MinVarianti[2] )
      {
         // ripristina il valore precedente prima di restituire false
         Varianti[index]--;
         return PermutationResult.Backtrack;
      }

      // restituisci di procedere se tutti i vincoli sono soddisfatti
      return PermutationResult.Proceed;
   }

Ricordo che il filtro viene chiamato ogni volta che la classe base prova a mettere un simbolo per la partita N-esima nel risultato (ossia nel vettore colonna), scegliendolo però tra i simboli validi specificati in ValidIndices[partita]. Invece di ricalcolare il numero di segni principali, varianti e sorprese ad ogni chiamata del metodo OnNewPermutations, la classe SistemaTotocalcio tiene traccia di questi valori nel vettore Varianti, dove Varianti[0] è il numero dei segni principali, Varianti[1] delle varianti, e Varianti[2] delle soprese.

Per mantenere sempre aggiornato questo vettore è necessario che i suoi elementi siano aggiornato in fase di backtracking, ovvero quando la classe base “toglie” un simbolo sistemato precedentemente. La classe SistemaTotocalcio implementa il backtracking facendo l’override del metodo protetto OnBacktrack:

   // backtracking 
   protected override PermutationResult OnBacktrack(int[] colonna, int partita)
   {
      // questo è l'indice usato per questa partita (0=princ, 1=variante, 2=sorpresa)
      int index = base.Indices[partita];
      // ripristina il contatori di Varianti ed esci
      Varianti[index]--;
      return PermutationResult.Backtrack;
   }
} // fine della classe SistemaTotocalcio

In definitiva, grazie alla classe Permutations è stato possibile risolvere un problema combinatorio davvero complesso con appena una ventina di istruzioni eseguibili!

La cosa a mio avviso davvero notevole è che, nonostante il fatto che la classe Permutations sia molto generica e sia in grado di risolvere problemi combinatori anche molto differenti tra loro, le prestazioni che si ottengono sono eccezionali. Sul mio desktop, un Pentium D a 2.80GHz, le 4.782.969 colonne di un sistema integrale di 14 triple senza alcun vincolo viene sviluppato interamente in meno di un secondo! Ed ovviamente, più vincoli imponiamo più veloce è lo sviluppo, perchè l'albero delle permutazioni viene "potato" prima di arrivare ad analizzare la 14-esima colonna. La figura mostra ad esempio un sistema 6 triple e 6 doppie con qualche vincolo che sviluppa 701 colonne in soli 2 millisecondi!

Nei fatti il programma è così veloce che una opzione del menu Sistema permette di attivare il ricalcolo automatico, un po’ come in Excel: ogni volta che modificate un pronostico o un vincolo, il programma è in grado di ricalcolare il sistema che ne risulta, ed eventualmente mostrarne le prime N colonne. Se avete un computer veloce non vi accorgerete neanche del ritardo.

Il mio primo programma per lo sviluppo dei sistema era scritto in assembly Z80, girava su Sinclair ZX Spectrum e generava circa 700 colonne al secondo. E ci vollero un paio di settimane, per il debug e il fine tuning, per arrivare a quel risultato che per i tempi era di tutto rispetto.

Al confronto, questa versione è implementata in un linguaggio di alto livello, ha richiesto mezz'ora per l'algoritmo vero e proprio (è stato più faticoso creare l'interfaccia utente) eppure è oltre settemila volte più veloce. Certo, un Pentium D non si può paragonare a uno Z80, ma un parte del merito è proprio nelle tecniche di potatura che ho affinato in questi anni e che ho cablato nella classe Permutations.

UPDATE: dopo aver messo online questo articolo ho modificato leggermente la libreria CAPermutations, e il link ora punta alla versione aggiornata. Tutto quanto scritto nel post originario resta valido, eccetto che il metodo di callback restituisce un enumerativo anzichè un booleano.

Nel mio precedente post ho introdotto la nuova libreria CAPermutations, a cui sto lavorando nel tempo libero. In questi giorni ho potenziato la libreria e modificato leggermente la sintassi del costruttore. Nel post originale trovate una piccola nota sulle differenze rispetto alla versione originale.

In questo articolo descriverò invece la feature più potente della libreria CAPermutations, ovvero la possibilità di impostare dei criteri di selezione delle varie permutazioni. In pratica, è possibile fornire alla libreria l'indirizzo di un metodo di callback: questo metodo viene chiamato mentre viene generata una nuova permutazione, e quindi il programma client ha la possibilità di scartare le permutazioni che non interessano. La cosa interessante è che la routine di callback viene chiamata non soltanto quando la permutazione è stata completata, ma anche durante le fasi intermedie. Supponiamo ad esempio di voler calcolare le permutazioni dei numeri 1-9 ma con la condizione che il numero N non si trovi in posizione N-esima. Ovviamente possiamo generare le 9! permutazioni dei numeri in questione e poi scartare quelli che non soddisfano la condizione, ma il metodo di callback permette di accellerare notevolmente i tempi di elaborazione: infatti non ha senso provare per poi scartare i milioni di permutazioni che presentano la cifra 1 al primo posto, ma è molto più efficiente dire "non farlo!" nel momento il cui la classe Permutations prova a generare la prima permutazione errata, dicendole in pratica di saltare tutte le permutazioni di quel tipo.

Ecco un programma Visual Basic che risolve il problema delle permutazioni di questo tipo:

Sub GeneratePermutations() 
   ' generate permutations of digits 1-5
   Dim elements() As Integer = {1, 2, 3, 4, 5}
   Dim permutations As New Permutations(Of Integer)(elements, 5, PermutationKind.Permutations, 1, AddressOf PermutationFilter)
   For Each perm() As Integer In permutations
      Dim sb As New System.Text.StringBuilder
      For Each n As Integer In perm
         sb.Append(n)
      Next
      Console.WriteLine(sb.ToString)
   Next
End Sub

Private Function PermutationFilter(ByVal permutation() As Integer, ByVal level As Integer, ByVal backtracking As Boolean) As PermutationResult
   ' this is the element just added
   Dim number As Integer = permutation(level)
   ' backtrack if the element is equal to its position
   If number <> (level + 1) Then Return PermutationResult.Proceed Else Return PermutationResult.Backtrack
End Function

La procedura di callback, detta anche procedura di filtro, accetta tre argomenti e restituisce un enumerativo PermutationResult. Il primo argomento è il vettore che rappresenta la permutazione che è stata costruita fino a quel momento; il secondo argomento rappresenta il livello di costruzione della permutazione, ovvero l'indice zero-based dell'elemento che è stato appena aggiunto prima di chiamare il metodo di callback. Il terzo argomento è False se la permutazione è stata costruita, True se siamo in fase di backtrack (vedi dopo). Il metodo deve restituire il valore PermutationResult.Proceed se la permutazione può essere accettata, PermutationResult.Backtrack se deve essere scartata. Vi sono altri possibili valori di ritorno, ma li vedremo meglio in altri articoli di questa serie.

La possibilità di effettuare backtracking, ovvero di tornare indietro sui suoi passi se il metodo di callback restituisce PermutationResult.Backtrack, aumenta enormemente il potenziale della libreria e le permette di risolvere problemi combinatoriali molto complessi. Ecco ad esempio una classe che risolve il famoso problema delle regine, ovvero come sistemare N regine su una scacchiera N*N in modo che non si diano scacco a vicenda. Si tratta di un classico problema combinatorio su cui, prima dell'avvento dei computer, si sono arrovellati dei geni come Gauss e altri famosi matematici. Per una introduzione molto sintetica al problema, date una occhiata a questa pagina oppure googlate per "queens' problem" (virgolette incluse).

Questo problema corrisponde a trovare una permutazione dei numeri 1-N, dove ogni elemento P(n) della permutazione rappresenta la colonna in cui posizionare la regina della riga N. Il solo fatto di richiedere permutazioni delle cifre 1-N (dove ogni elemento della permutazioni può apparire una sola volta) assicura che le regine si trovino su colonne oltre che su righe separate. Di fatto quindi, il metodo di callback deve soltanto tenere traccia di quali diagonali (principali e secondarie, ovvero quelle in direzione NO-SE e quelle in direzione NE-SO) sono occupate dalle regine poste sulla scacchiera fino a quel momento. Ecco il codice C# di una classe che calcola tutte le soluzioni del problema, con N qualsiasi:

Con qualche piccola aggiunta alla procedura di callback è anche possibile risolvere il problema delle amazzoni (o delle super-regine) dove una amazzone è una regina con super-poteri che è anche in grado di muoversi come un cavallo. Queste sono le sole righe che occorre aggiungere nel punto segnato da un commento nel listato della classe:

         // additional tests for the amazons' problem
         if ( Kind == ProblemKind.Amazons )
         {
            // check the cells in previous row
            if ( row > 0 && ( columns[row - 1] == col - 2 || columns[row - 1] == col + 2 ) )
               return PermutationResult.Backtrack;
            // check cells two rows above
            if ( row > 1 && ( columns[row - 2] == col - 1 || columns[row - 2] == col + 1 ) )
               return PermutationResult.Backtrack;
         }

Ho preparato un programma che permette di risolvere il problema delle regine e delle amazzoni con N compreso tra 4 e 20. In aggiunta alle feature appena descritte, il programma è anche in grado di scartare le riflessioni e le rotazioni, per ottenere quelle che si definiscono le soluzioni base del problema. Grazie alla classe Permutations, con una manciata di istruzioni è stato possibile risolvere un problema combinatorio davvero complesso. E il tutto in modo super-efficiente: sul mio computer il problema delle regine di ordine 12 è risolto in circa 1.5 secondi, per trovare tutte le 1787 soluzioni base.

Questo è il link al sorgente del programma delle regine e amazzoni, che contiene anche la versione aggiornata della libreria CAPermutations e del programma per generare anagrammi: QueensProblem.zip (37.25 KB)

UPDATE: dopo aver messo online questo articolo ho modificato leggermente la libreria CAPermutations, e il link ora punta alla versione aggiornata. Tutto quanto scritto nel post originario resta valido, eccetto che il terzo argomento da passare al costruttore è ora un enumerativo anzichè un booleano.

Da quando ho potuto mettere le mani su un computer sono sempre stato affascinato dai problemi combinatoriali. In prima approssimazione, un problema combinatoriale prevede la scelta di una (o più) permutazioni o combinazioni di N elementi in modo da soddisfare alcuni vincoli. E' facile intuire che molti problemi si risolvono solo grazie a tecniche combinatoriali:

• La generazione di tutti gli anagrammi di una parola richiede la generazione di tutte le permutazioni possibili dei suoi caratteri, per poi scegliere tra le parole ottenute quelle di senso compiuto
• Un programma per generare sistemi di Totocalcio, Lotto, Totip e simili richiedono la generazione di tutte le colonne possibili, da cui vengono poi scelte quelle che soddisfano alcuni requisiti (tipo numero minimo e massimo di segni, ecc.)
• Un programma per determinare l'orario scolastico, oppure più in generale, per stabilire turni di lavoro richiede di generare tutte le possibili assegnazioni (persona,turno) per poi scegliere quelle che soddisfano i vincoli impostati dall'utente
• Molti problemi matematici si basano sulla generazione di tutte le possibili permutazioni o combinazioni di N elementi, ad esempio la generazione degli quadrati magici di ordine N oppure la risoluzione del famoso problema delle regine (ovvero: come sistemare N regine su una scacchiera N*N in modo che nessuna dia scacco ad un'altra)
• Lo stesso vale per molti giochi di tipo enigmistico, come ad esempio il Sodoku oppure le parole crociate.
• Il problema dello zaino: abbiamo N oggetti di peso o ingombro differenti da trasportare in uno zaino che ha una capacità (come peso o volume) massima pari a un certo valore: quali oggetti scegliere in modo che la capacità dello zaino sia sfruttata al massimo, in modo cioè che la somma dei volumi o dei pesi degli oggetti scelti sia la più vicina possibile (ma non superiore) alla capacità dello zaino? Se pensate che invece di uno zaino avete a che fare con un container, vedete che il problema ha delle implicazioni pratiche non indifferenti
• Il modo migliore per tagliare sagome bidimensionali da una superficie piana si determina provando i diversi modi di combinare le varie sagome in modo da minimizzare il materiale non utilizzato (si pensi ad esempio al problema di tagliare in modo ottimale le pelli di una sedia o un divano a partire dal pellame a disposizione ed evitando i punti in cui il pellame non è utilizzabile o presenta imperfezioni)
• Il percorso ottimale per andare dalla località A alla località B in trenoo aereo può essere risolto combinando i vari percorsi intermedi, in modo da ridurre la distanza complessiva, il costo complessivo dei biglietti, il numero delle coincidenze aeree o ferroviarie, oppure ancora il tempo speso aspettando tali coincidenze. (Pensate ad esempio a come prenotate un viaggio con Expedia.)
• La generazione di permutazioni e combinazioni è anche alla base di numerose tecniche di "attacco" per scardinare alcuni sistemi di sicurezza. Ad esempio, i programmi che tentano di trovare le password per un sito funzionano combinando le parole in un dizionario che contiene le parole e nomi propri più comuni.

Potrei continuare con altri esempi, ma credo che sia chiaro il fatto che le tecniche combinatorie possono essere utili in moltissimi casi. Per saperne di più, non dovete fare altro che gogglare un po' su termini come "permutations" o "combinations" e scoprirete un sacco di cose interessanti. (La ricerca per "permutations" restituisce circa 10 milioni di hit, quella per "combinations" oltre 137 milioni!).

In questi anni ho scritto numerosi programmi che richiedevano la generazione di permutazioni o combinazioni di elementi simili. Forse il primo programma di questo tipo è stato un generatore di sistemi per il totocalcio che girava su Sinclair Spectrum. Uno dei più recenti è stato il Sodoku Solver che risolve automaticamente gli schemi di Sodoku più complessi in qualche frazione di secondo, direttamente dal vostro broswer. Nei vent'anni intercorsi tra questi due programmi, ho usato tecniche combinatoriali per ottimizzare la soluzione di alcuni problemi come quelli citati sopra.

Una delle cose più intriganti di un problema combinatoriale è il fatto che anche problemi abbastanza semplici richiedono spesso soluzioni complesse dal punto di vista computazionale, e soprattutto richiedono tanto tempo di CPU a meno di non ottimizzare al meglio l'algoritmo. Le possibili permutazioni di 10 oggetti distinti è pari al fattoriale di 10, ovvero 1*2*3*4*5*6*7*8*9*10 = 3.628.800. Disporre i numeri 1-16 su una griglia 4x4 per vedere quali combinazioni generano un quadrato magico (ossia un quadrato in cui la somma lungo le righe, colonne, e diagonali è costante) richiede l'analisi di 20mila miliardi di posizioni, e cosi' via. Per riuscire a risolvere questi problemi in tempi accettabili si richiede spesso di ottimizzare il codice al massimo e di trovare delle tecniche di "potatura" in modo da poter scartare interi gruppi di soluzioni prima di doverle analizzare una a una. Anche in questo modo, la risoluzione di un quadrato magico di ordine 5 può richiedere alcuni giorni anche sulle CPU più performanti. Per avere una idea di quante varianti vi siano per questi problemi combinatoriali, date una occhiata al sito The Combinatorial Object Server.

Ogni problema combinatoriale è una storia a sè stante, nel senso che il codice per trovare le soluzioni di uno schema di Sodoku è molto diverso dal codice per generare l'orario scolastico ottimale o per trovare il tragitto aereo migliore. D'altra parte, queste applicazioni hanno anche molti tratti in comune. In particolare, la parte che genera le varie permutazioni o combinazioni di elementi è spesso simile. Non uguale, ma simile. Quello che cambia in ciascun caso sono le routine che controllano se una combinazione è valida o meno, oppure le funzioni che procedono alla "potatura" degli alberi delle soluzioni. Alla fine ho pensato: perchè non estrapolare l'algoritmo di generazione delle combinazioni in modo da poterlo riutilizzare in occasioni differenti? Il risultato è la libreria CAPermutations, ovvero l'oggetto di questo articolo e di alcuni altri post che seguiranno.

La libreria in questione contiene solo una classe, Permutations, che però già in questa prima versione è in grado di risolvere la maggior parte dei problemi citati in precedenza. Per i problemi non particolarmente complessi, utilizzare questa libreria è davvero semplice: si crea una istanza della classe e si passa al costruttore un vettore contenente tutti gli elementi da permutare, poi si entra in un ciclo For Each che permette di enumerare tutte le possibili permutazioni. La classe Permutations usa i generics, in modo da accettare e restituire un array tipizzato contenente gli elementi che devono essere (o che sono stati) combinati:

' generate all the permutation of the characters A,B,C,D
Dim elements() As Char = {"A"c, "B"c, "C"c, "D"c}
Dim perms As New Permutations(Of Char)(elements)
For Each chars() As Char In perms
   ' create and display the string obtained by concatenating the characters in the result
   Console.Write(New String(chars) & ", ")
Next

Il codice C# è altrettanto semplice:

// generate all the permutation of the characters A,B,C,D
char elements[] = {"A"c, "B"c, "C"c, "D"c};
Permutations<Char> permutations = New Permutations<Char>(elements);
foreach ( char[] chars in perms )
{
   // create and display the string obtained by concatenating the characters in the result
   Console.Write(new string(chars) + ", ");
}

Ecco il risultato che appare nella finestra di console, ovvero tutte le possibili permutazioni degli N elementi forniti in input:

Invece di un loop For Each potete anche usare il metodo GetAllPermutations, che restituisce in un colpo solo tutte le pemutazioni. Poichè ogni permutazione è un vettore di tipo T (dove T è definito al momento di istanziare la classe generica Permutations), allora il risultato di questo metodo è un jagged array di tipo T, ovvero un vettore dove ciascun elemento è a sua volta un vettore di tipo T.

' VB
Dim results()() As Char = perms.GetAllPermutations()

// C#
char[][] results = perms.GetAllPermutations();

La classe Permutations è anche in grado di determinare le permutazioni di un gruppo di K elementi presi dall'insieme di N elementi forniti in input, con K <= N . Per ottenere tali permutazioni basta passare al costruttore un secondo argomento, pari al numero K di elementi che devono apparire nel risultato:

La classe Permutations permette di risolvere una numerosa classe di problemi combinatori e statistici. Ad esempio, se A,B,C,D rappresentano 4 città, l'insieme delle permutazioni rappresentano tutti i possibili percorsi che uniscono le città e che non ripassano mai da una città: un programma può facilmente analizzare questi percorsi per trovare quello che richiede meno tempo o ha un costo minore. Se invece gli elementi rappresentano possibili azioni - ad esempio, l'azione di sistemare una pedina su una determinata casella delle scacchiera - allora l'insieme delle permutazioni permette di stabilire quale sequenza di azioni tra quelle possibili permettono di ottenere il risultato migliore (ad esempio, vincere una partita di tris). E' importante notare che il risultato non conterrà due elementi uguali, il che è corretto perchè non vogliamo visitare due volte la stessa città e non possiamo sistemare due pedine nella stessa casella.

La classe Permutations permette anche di generare le combinazioni di K oggetti presi da un universo di N oggetti, come al solito con K <= N. L'unica differenza tra permutazioni e combinazioni è che con queste ultime l'ordine è ininfluente, quindi ad esempio la soluzione ABC è considerata equivalente a ACB, BAC, BCA, CAB, e CBA perchè quello che conta sono gli elementi che compaiono nel risultato e non il loro ordine. Le combinazioni permettono di risolvere tipi di problemi differenti da quelli visti finora. Per esempio, le combinazioni degli elementi {Giuseppe,Francesco,Marco,Piero,Gianni,MariaTeresa} con K=2 potrebbero servire per generare il calendario della prima serie di partite di un torneo di tennis a cui partecipano sei membri del team di Code Architects, in modo che ciascuna persona si batta una volta contro tutte le altre. In questo caso occorre usare le combinazioni perchè non occorre disputare la partita Francesco-Giuseppe se si è già giocata la partita Giuseppe-Francesco. (In altre parole, l'ordine degli elementi è ininfluente.)

Per generare combinazioni anzichè permutazioni, è sufficiente passare un valore enumerativo PermutationKind come terzo argomento al costruttore della classe Permutations. Ecco ad esempio come generare le partite del torneo:

Dim elements() As String = {"Giuseppe", "Francesco", "Marco", "Piero", "Gianni", "MariaTeresa"}
Dim perms As New Permutations(Of String)(elements, 2, PermutationKind.Combinatio )  ' anzichè PermutationKind.Permutations
For Each elem() As String In perms
   ' each element in the result is an array with two elements
   Console.WriteLine("{0} - {1}", elem(0), elem(1))
Next

Ed ecco il risultato che appare nella console window.

Fin quì niente di particolarmente eccitante, visto che è facile ottenere lo stesso risultato con qualche ciclo innestato di C# o VB, soprattutto se i valori di K e N sono costanti. Con K o N variabili occorre prevedere degli array che gestiscono gli indici dei vari loop, ma è un codice alla portata di tutti.

Le cose cominciano a diventare interessanti quando l'insieme degli elementi contiene elementi uguali, che non possono quindi essere considerati distinti quando si generano le permutazioni o le combinazioni. L'esempio classico è la generazione di anagrammi: il numero totale di anagrammi della parola "case" è 23, dato dal numero di pemutazioni possibili di 4 lettere (=1*2*3*4) meno uno per evitare di conteggiare la parola originale. D'altra parte, il numero di anagrammi della parola "casa" è soltanto 11, perchè la parola originale contiene due lettere uguali e quindi il numero di permutazioni distinte che è possibile creare è pari a 12, non 24. Questo particolare inizia a complicare non poco la struttura di un programma C# o VB che risolve il problema specifico, ma la classe Permutations rimuove automaticamente le ripetizioni dal risultato:

Ecco il codice nell'evento Click nel pulsante "Show anagrams" del programma demo:

' prepare to generate all permutations of all the characters in the word
Dim chars() As Char = txtWords.Text.ToCharArray()
Dim permutations As New Permutations(Of Char)(chars)
lstAnagrams.Items.Clear()
For Each chrs() As Char In permutations
   Dim anagram As String = New String(chrs)
   ' don't include the original word in the result
   If anagram <> txtWords.Text Then lstAnagrams.Items.Add(anagram)
Next
lblMessage.Text = String.Format("Found {0} anagrams", lstAnagrams.Items.Count)

Come ho fatto notare prima, nella maggior parte dei casi quando chiediamo le permutazioni o combinazioni di un gruppo di elementi non vogliamo che lo stesso elemento compaia più volte. Ad esempio, se un elemento rappresenta la posizione di una regina posta sulla scacchiera, l'elemento non puo' comparire più di una volta perchè una casella non puo' contenere più pezzi. Altri problemi combinatori però non hanno questa limitazione. Se ad esempio stiamo calcolando tutte le possibili permutazioni di due dadi, dovremo includere anche i risultati in cui vi sia un doppio uno, un doppio due, ecc. Per ottenere questo risultato occorre specificare un valore maggiore di 1 come quarto argomento del costruttore della classe Permutations:

' get all the possible permutations of two dice
Dim elements() As Integer = {1, 2, 3, 4, 5, 6}
' we pass 2 as fourth argument because we accept that the same value can appear twice
Dim perms As New Permutations(Of Integer)(elements, 2, PermutationKind.Permutations , 2)
For Each dice() As Integer In perms
   Console.WriteLine("{0} {1}", dice(0), dice(1))
Next

In una prima versione della libreria avevo usato un booleano per indicare se le ripetizioni erano ammesse o meno, ma usare un intero ha il vantaggio di permettere una maggiore flessibilità. Ad esempio, è possibile generare tutte le permutazioni di tre dadi in cui lo stesso valore compare al massimo due volte:

Dim perms As New Permutations(Of Integer)(elements, 3, PermutationKind.Permutations, 2)

Queste prime note dpvrebbero essere sufficienti per cominciare a utilizzare la libreria CAPermutations, ma le sue possibilità sono di gran lunga superiori e fornirò qualche altro esempio nei prossimi giorni, man mano che ne creo. Nel frattempo, potete scaricare la libreria e il piccolo programma demo visibile nella figura da questo link: PermutationsDemo1.zip (23.15 KB)

Una ultima, importante nota: questa versione della libreria CAPermutations è disponibile come DLL compilata e può essere usata esclusivamente nei programmi freeware o no-profit. Se avete dubbi su questa forma di licenza o se avete la necessità di utilizzarla in applicazioni commerciali, contattatemi via email.

MsgHookX è una DLL ActiveX che permette ai programmatori VB6 di eseguire un subclassing intra-applicazione sicuro ed efficiente, ossia di intercettare qualsiasi messaggio che Windows invia a un controllo o finestra della applicazione corrente. Scrissi questa DLL diversi anni fa, ai tempi del VB5, e l'ho utilizzata in alcuni libri e articoli usciti nel frattempo. Questa DLL era disponibile sul vecchio sito VB2TheMax, ma non è sopravvissuta quando il sito è diventato .NET-2-The-Max e decidemmo di scartare tutti i contenuti relativi al vecchio VB6.

Beh, se devo giudicare dalle tante mail che continuo a ricevere dai lettori, si direbbe che gli sviluppatori VB6 continuano a voler subclassare i loro controlli e le loro finestre. Per questa ragione ho deciso di rendere MsgHookX nuovamente disponibile, sul sito americano a questo URL. Ecco un breve sommario di quello che la DLL è in grado di fare:

• subclassing sicuro: può essere usata nella IDE e in break mode, senza rischiare alcun crash di sistema.
• fornisce gli eventi BeforeMessage e AfterMessage, per una programmazione semplice di tipo event-driven
• è anche in grado di notificare l'arrivo dei messaggi attraverso l'interfaccia secondaria IMsgHookEvents, per fornire prestazioni migliore e un debugging più facile (in alcuni casi gli eventi sono inibiti nella IDE di VB6)
• alta flessibilità: potete decidere di chiamare la window procedure originale dall'evento/metodo BeforeMessage e opzionalmente di annullare l'elaborazione di default del messaggio. Potete anche visualizzare e modificare il valore che il messaggio sta per restituire al sistema operativo.
• La type library della DLL include la definizione di oltre 300 costante simboliche, che definiscono i messaggi Windows più comuni, in modo da non dover ricorrere all'API Viewer per includere le definizioni nella proprie applicazioni.

Ora la mia domanda è: ma quando, quando, quando vi deciderete a passare a .NET ?

Per il progetto sul quale stò lavorando c'era la necessità di produrre un PDF sulla base di un report HTML abbastanza complesso, con griglie, immagini, CSS interni all'HTML stesso o in file esterni linkati. Abbiamo provato per giorni ad usare un certo prodotto commerciale piuttosto famoso che fa tutto ciò, ma richiedendo di creare account Windows particolari, configurare in modo appropriato addirittura i browser che stà sul server, creare varie cartelle, configurare l'apertura di porte particolari ecc. ecc. Insomma, bisogna dedicare un server a questo tool, e anche così bisogna perdere del tempo per sistemare il tutto. Stanchi di queste difficoltà per il test e il deployment, ieri mi sono messo a cercare un'alternativa. Risultato :ABCpdf! Questo componente fa davvero tutto quello che ci serve, in modo ottimale a quanto sembra per ora, e la sua installazione e utilizzo sono di una semplicità disarmante: basti dire che in poco più di un'ora ho scaricato e installato il prodotto, mi sono visto un paio di loro esempi, ho riscritto il servizio di generazione di PDF e ho testato che funzionava bene...
Insomma, forse l'altro componente sarà anche in grado di svolgere compiti più complessi (fa da vero e proprio server PDF, mettendo in coda le richieste e smaltendole in modo asincrono), ma se non avete necessità di gestire carichi davvero enormi, e non avete un server da dedicarci, ABCpdf è molto veloce e può fare al caso vostro. Tra l'altro, il componente è gratuito se mettete sul sito un link al produttore (altrimenti c'è una licenza di prova di 30 giorni oltre i quali si dovrà comprare la licenza commerciale)!

Colgo l'occasione di questo post per segnalare anche che nel blog in inglese ho appena pubblicato un nuovo estratto dal mio libro, che mette a confronto le varie tecnologie MS per gestire le transazioni distribuite e non all'interno di applicazioni .NET: transazioni ADO.NET, COM+/SWC e System.Transactions. Il tutto in modo piuttosto conciso (del resto è solo una delle tante cose che introduco nel capitolo 3, riguardanti i fondamenti della progettazione del sito), non è certamente intesa come una trattazione esausitva ma credo possa dare velocemente un'idea delle varie possibilità a chi ancora non ci ha avuto a che fare.

Sto riorganizzando la mia collection di MP3 e mi sono trovato nella necessità di rinominare un numero davvero enorme di file. Ci sono molte utility sul mercato che permettono di farlo (e che sono anche in grado di usare i tag MP3 per rinominare i file), ma ho pensato che tanto valeva scriverne una io. Tanto, grazie alle regex il compito non sarebbe stato difficile. E infatti in qualche minuto ho tirato fuori il seguente codice. Come vedete, la maggior parte delle istruzioni servono a estrarre e validare gli argomenti dalla riga di comando:

Imports System.Text.RegularExpressions
Imports System.IO

Module Renx

   Function Main(ByVal args() As String) As Integer
      Console.WriteLine("RENX (C) Francesco Balena / Code Architects Srl")

      Dim recurse As Boolean = False
      Dim renameMode As Boolean = False
      Dim oldNamePattern As String = Nothing
      Dim newNamePattern As String = Nothing

      ' analyze each argument
      For Each arg As String In args
         Select Case arg.ToLower()
            Case "/s", "-s"
               recurse = True
            Case "/r", "-r"
               renameMode = True
            Case "/h", "-h"
               Return ShowHelp(0)
            Case Else
               If oldNamePattern Is Nothing Then
                  oldNamePattern = "^" & arg & "$"
               ElseIf newNamePattern Is Nothing Then
                  newNamePattern = arg
               Else
                  Return ShowHelp(1)
               End If
         End Select
      Next

      ' check that we have both mandatory arguments
      If oldNamePattern Is Nothing OrElse newNamePattern Is Nothing Then
         Return ShowHelp(1)
      End If
      ' create the regex and check that pattern syntax is ok
      Dim reSearch As Regex
      Try
         reSearch = New Regex(oldNamePattern, RegexOptions.IgnoreCase)
         ' test the replace pattern as well
         Dim tmp As String = reSearch.Replace("a dummy string", newNamePattern)
      Catch ex As Exception
         Console.WriteLine("SYNTAX ERROR: {0}", ex.Message)
         Return 3
      End Try
      Console.WriteLine()

      ' iterate over all files in current directory (and its subdirectories, if recurse mode)
      Dim searchOpt As SearchOption = SearchOption.TopDirectoryOnly
      If recurse Then searchOpt = SearchOption.AllDirectories

      Dim parsedFilesCount As Integer = 0
      Dim renamedFilesCount As Integer = 0
      Dim errorsCount As Integer = 0
      For Each oldFile As String In Directory.GetFiles(Directory.GetCurrentDirectory(), "*.*", searchOpt)
         parsedFilesCount += 1
         ' the regex applies to name only
         Dim oldName As String = Path.GetFileName(oldFile)
         Dim ma As Match = reSearch.Match(oldName)
         If ma.Success Then
            ' this is the new name
            Dim newName As String = ma.Result(newNamePattern)
            Console.WriteLine(oldFile)
            Console.Write(" => {0}", newName)
            renamedFilesCount += 1
            ' proceed with rename only if not in simulation mode
            If renameMode Then
               Try
                  Dim dirName As String = Path.GetDirectoryName(oldFile)
                  Dim newFile As String = Path.Combine(dirName, newName)
                  File.Move(oldFile, newFile)
               Catch ex As Exception
                  Console.Write(" -- ERROR: {0}", ex.Message)
                  errorsCount += 1
               End Try
            End If
            Console.WriteLine()
         End If
      Next

      ' Display a report
      If renameMode Then
         Console.WriteLine("Summary: {0} parsed files, {1} renamed files, {2} errors", parsedFilesCount, renamedFilesCount, errorsCount)
      Else
         Console.WriteLine("Summary: {0} parsed files, {1} files affected", parsedFilesCount, renamedFilesCount)
         Console.WriteLine()
         Console.WriteLine("NOTE: Running in simulation mode. Specify the /R option to actually rename files.")
      End If
      ' Return an error code
      If errorsCount = 0 Then
         Return 0
      Else
         Return 2
      End If
   End Function

   Function ShowHelp(ByVal exitCode As Integer) As Integer
      Console.WriteLine()
      Console.WriteLine("Syntax: RENX <oldnamepattern> <newnamepattern> [/R] [/S] [/H]")
      Console.WriteLine(" oldnamepattern : regex that selects the files to be renamed")
      Console.WriteLine(" newnamepattern : regex that specifies how files must be renamed")
      Console.WriteLine(" /R : rename files")
      Console.WriteLine(" /S : iterate over subdirectories")
      Console.WriteLine(" /H : display this help")
      Console.WriteLine("NOTE: By default the program runs in simulation mode, and just displays how files would be renamed.")
      Console.WriteLine(" You must specify the /R option to actually rename the files.")
      Return exitCode
   End Function

End Module

Al minimo, la utility RENX richiede due argomenti: una regex che individua quali file nella directory corrente (e nelle sue subdirectory, se si specifica l'opzione /S) devono essere rinominati, e una regex che specifica come rinominare i file che soddisfano la prima regex. La potenza di RENX sta nel fatto che la regex che individua i file può (anzi, deve) specificare uno o più gruppi di caratteri, che vengono poi riutilizzati nella seconda regex. Supponiamo ad esempio che abbia una directory con i seguenti file

        01 Speak to Me.mp3
        02 On the Run.mp3
        03 Time.mp3
        04 The Great Gig in the Sky.vbr
        05 Money.mp3
        06 Us and Them.mp3
        07 Any Colour You Like.vbr
        08 Brain Damage.mp3
        09 Eclipse.vb3

e li voglia rinominare in questo modo:

        01 - Speak to Me - The Dark Side of the Moon.mp3
        02 - On the Run - The Dark Side of the Moon.mp3
        03 - Time - The Dark Side of the Moon.mp3
        04 - The Great Gig in the Sky - The Dark Side of the Moon.vbr
        05 - Money - The Dark Side of the Moon.mp3
        06 - Us and Them - The Dark Side of the Moon.mp3
        07 - Any Colour You Like - The Dark Side of the Moon.vbr
        08 - Brain Damage - The Dark Side of the Moon.mp3
        09 - Eclipse - The Dark Side of the Moon.vbr

Ecco allora come invocare RENX per effettuare la trasformazione:

        RENX "(\d\d) (.+?)(\..+)"    "${1} - ${2} - The Dark Side of the Moon${3}"

Notate che la prima regex crea tre gruppi racchiudendo dei caratteri tra parentesi: (\d\d) fa il match con due cifre, mentre (.+?) fa il match con il nome del file, e infine (\..+) fa il match con l'estensione del file, punto incluso. Il secondo argomento puo' riordinare a piacere queste tre quantità, usando la sintassi ${N}, dove N è il numero d'ordine del gruppo individuato dalla prima regex, ed è quindi in grado di inserire un trattino dopo il numero del brano e il nome dell'album dopo il titolo del brano.

Data la pericolosità del comando di rename, per default il comando RENX *non* effettua il rename e si limita a mostrare come i file sarebbero rinominati. Per effettuare effettivamente il rename occorre specificare l'opzione /R:

        RENX "(\d\d) (.+?)(\..+)"    "${1} - ${2} - The Dark Side of the Moon${3}" /R

Questo è tutto. Avete il sorgente e potete estendere l'utility come preferite (magari per trasformarla in un programma Windows Forms), e potete anche effettuare il download della versione in binario da questo link: Renx.zip (5.51 KB)

Ciao a tutti, 
   vi riporto di seguito il calendario ufficiale dei prossimi webcast architetturali tenuti da Maurizio, Pierre, me ed altri. Il primo appuntamento e' domani. Illustrero' le novita' della rinnovata versione dell'Enterprise Library di Patterns & Practices per poi proseguire fino a giugno con una nutrita serie di argomenti e approfondimenti su tecnologie reali.

Ho già parlato in questo blog di CodeWall.NET, un tool per la protezione degli eseguibili .NET 2.0 dalla decompilazione, a cui io e Vito Plantamura stiamo lavorando da un paio di mesi. Finalmente abbiamo una beta robusta e funzionante, e non vediamo l'ora di metterla online.

Date le finalità del prodotto, non è un mistero il fatto che abbiamo passato la maggior parte del tempo per implementare tutte le tecniche "anti-sprotezione" di nostra conoscenza, incluso alcune davvero esoteriche. E' un vero peccato non poterle descrivere nei dettagli, per motivi che dovrebbero essere evidenti. Comunque, qualche cosa la posso comunque raccontare.

Uno dei punti deboli di praticamente tutti i meccanismi di protezione di questo tipo è che, se un "cracker" trova il modo per sproteggere UN SOLO eseguibile protetto, egli è in grado di scrivere uno script o un tool in grado di sproteggere TUTTI gli eseguibili protetti, la qual cosa sarebbe ovviamente un vero disastro per noi e per i nostri clienti. Per ovviare a questo serissimo problema, ogni copia di CodeWall.NET è unica. Non solo utilizza una chiave differente, ma contiene anche un algoritmo di decifratura leggermente differente. Questo accorginmento rende l'attacco mediante script virtualmente impossibile.

Ecco un'altra tecnica che abbiamo adottato per rendere la protezione più robusta. Le applicazioni protette con CodeWall.NET possono contenere delle stringhe criptate, che saranno riportate in chiaro solo in fase di esecuzione, e solo se l'assembly "gira" sotto CodeWall.NET. Questo significa che se anche qualcuno riuscisse a estrarre un assembly dall'eseguibile protetto, dovrebbe capire come funziona il decrypt delle stringhe e poi decrittare le stringhe una a una. Attenzione, perchè non solo è possibile criptare le stringhe in questo modo: è anche possibile criptare nomi di classi e di metodi, quindi se queste stringhe non sono decrittate correttamente il programma non funzionerebbe affatto.

Ovviamente, il loader di CodeWall.NET è scritto in codice unmanaged, in modo da NON essere decompilabile con Reflector, Anakrino, o ILDASM. Un malintenzionato particolarmente motivato potrebbe usare un disassembler "classico", ma poi gli toccherebbe decifrare migliaia di opcode assembly "nativo", il che non è proprio alla portata di tutti. Purtroppo, pero', l'uso del codice unamanged limita l'utilizzo di CodeWall.NET ai soli eseguibili Win32 (Windows Forms e Console) che girano in modalità full-trust. Non possiamo quindi supportare appliczioni ASP.NET e neanche applicazioni ClickOnce, a meno che questi ultimi non girino appunto in full-trust mode.

Non abbiamo ancora stabilito il prezzo di listino di CodeWall.NET, ma prevediamo che si aggirerà sui 250 dollari (circa 200 euro) e quasi certamente ci sarà uno sconto per il periodo del lancio. A breve speriamo di mettere una versione "trial" disponibile sul sito. Nel frattempo, se avete domande lasciate pure un commento.

Windows Communication Foundation (WCF) e Windows WorkflowFoundation possono essere utilizzati in un ambiente di produzione.

Ulteriori dettagli qui:

http://msdn.microsoft.com/winfx/getthebeta/golive/default.aspx

BIT e informazioni qui:

http://www.windowsworkflow.net

http://windowscommunication.net

Oggi mi sono imbattuto in un nuovo attributo del .NET Framework che mi era sfuggito durante le mie precedenti esplorazioni. Si tratta di SuppressIldasmAttribute, che si può applicare a livello di assembly

<Assembly: System.Runtime.CompilerServices.SuppressIldasm()>

Come il suo nome lascia intendere, questo attributo impedisce di usare ILDASM per disassemblare l'eseguibile. Se provate a farlo, vi beccate infatti il seguente messaggio di errore:

Eccezionale! Proprio quello che ci voleva per proteggere i nostri sorgente da occhi indiscreti, giusto? Peccato che questo attributo è riconosciuto solo da ILDASM e non da Reflector e simili decompilatori, che invece riescono a tradurre anche questi eseguibili in sorgente, senza batter ciglio. Insomma un attributo molto promettente ma assolutamente inutile. Morale della storia: per proteggere i frutti del vostro lavoro, usate un obfuscator o - meglio ancora - aspettate anche qualche settimana per il nostro CodeWall.NET.

Ai primi anni '90 avevo una piccola software house tutta mia, di nome Softwhale (chi è bravo con l'inglese apprezzerà il gioco di parole, spero ). Già da allora il mio pallino era scrivere tool per sviluppatori, ed avevo realizzato alcuni prodotti niente affatto male, tra cui dSwapper (una utility che abbatteva il limite dei 640K per i programmi Ms-Dos), Batch Wizard (un compilatore per file batch, che molte software house italiane hanno usato per creare procedure di installazione intelligenti), e QBKIT (una libreria di 700+ nuove funzioni per QuickBasic, incluso menu e finestre 3D). Ma uno dei maggiori successi di quegli anni fu NOWAY , un piccolo tool scritto in Assembly - come la gran parte del software che scrivevo allora - in grado di crittografare gli eseguibili Ms-Dos per evitarne il reverse engineering. All'epoca, infatti, la maggior parte dei gestionali erano scritti in Clipper, e vi erano sul mercato un paio di decompilatori in grado di ricostruire il sorgente originale, con tanti saluti alla proprietà intellettuale. L'altra caratteristica notevole di Noway era la possibilità di "legare" un eseguibile ad una macchina, in modo da proteggere dalla diffusione di copie pirata.

Come vedete, dopo una decina di anni il mondo del software ha fatto passi da gigante, ma alcune cose non sono cambiate. Anche oggi i linguaggi .NET permettono una produttività incredibile - come e più del Clipper negli anni '90 - e soffrono del medesimo difetto: chiunque può decompilare gli assembly .NET con strumenti come Reflector, e scoprire in pochi minuti un algoritmo che vi ha impegnato per settimane o mesi. Non è un caso che alcune software house hanno deciso di rinunciare ai benefici del .NET Framework pur di evitare che ciò accada.

Un paio di mesi fa stavo facendo qualche esperimento con il .NET Framework 2.0 e ho avuto una piccola illuminazione, ovvero una tecnica che permette di crittografare un assembly e di riportarlo in chiaro "al volo", al momento di caricarlo in memoria. Non intendo dilungarmi sui dettagli di questa tecnica, ma l'effetto è particolarmente interessante: poichè l'assembly su disco è sempre in forma cifrata, non è possibile decompilarlo in alcun modo, neanche con ILDASM. Insomma, mi sono detto, questo potrebbe diventare il Noway per .NET! Ecco la storia che si ripete

Ovviamente, tra una idea e un prodotto finito passa del tempo. Prima di tutto occorreva risolvere alcuni punti potenzialmente deboli del meccanismo. Ad esempio, un hacker abbastanza in gamba potrebbe eseguire il trace del programma per capire cosa succede al caricamento, oppure potrebbe aspettare che l'assembly sia caricato "in chiaro" in memoria e salvarlo facendo un dump della memoria stessa. Sono tecniche forse fuori dalla portata di un programmatore .NET "medio" ma non di un hacker che si rispetti.

Io non sono un hacker e soprattutto non ho le conoscenze che servono per "blindare" un programma di questo tipo, quindi la cosa più saggia da fare era rivolgersi a qualcuno che queste cose le sa fare. E non credo di conoscere nessuno più indicato di Vito Plantamura, ovvero quello che io considero il "Mark Russinovich italiano". Vito non è un hacker nel senso deteriore del termine, ma conosce i meandri di Windows meglio di qualunque altro programmatore italiano io abbia conosciuto. Se volete avere una idea di cosa è in grado di fare, date una occhiata alla sua home page. Tra le tante cose che ha fatto, c'è anche BugChecker, un "clone" nientedimeno di SoftICE, un tool che fa sembrare un giocattolo il debugger di Visual Studio. Vito è nel team di Code Architects e tra non molto potrete leggerlo su questo blog o altrove su questo sito.

Comunque, in questi mesi le ricerche e gli esperimenti sono continuate ed ora siamo vicini alla fase beta vera e propria. Qualche ora fa abbiamo "battezzato" il nuovo prodotto come CodeWall.NET, seguendo il suggerimento di un gentilissimo partecipante alla WPC (dove avevamo mostrato la prima versione in anteprima). La versione 1.0 supporta soltanto applicazioni Windows Forms ed è in grado di comprimere tutti gli assembly di una solution in un unico file compresso, che quindi si puo' scaricare più velocemente. L'applicativo deve girare in modalità full-trust e quindi al momento non supportiamo ClickOnce. Se tutto va bene il prodotto finale dovrebbe essere disponibile verso i primi di gennaio.

Devo essere sincero: abbiamo rimuginato per mesi prima di decidere di rilasciare un prodotto per la protezione degli assembly .NET. Chiunque nel settore informatico sa perfettamente che non esiste la protezione inviolabile. Per quanto sia possibile blindare un eseguibile è sempre possibile arrivare a scardinare la protezione. E' una questione di abilità dell'hacker e di tempo necessario. Oppure, se si preferisce, di quanti soldi una azienda è disposta a spendere per appropriarsi dei segreti dei propri concorrenti, assoldando se necessario qualche ragazzino particolarmente versato per queste attività.

Se è vero che qualsiasi eseguibile può essere sprotetto - disponendo di tempo e denaro in abbondanza - ciò non significa che non dobbiamo neanche tentare di rendere la vita più complicata a chi vuole rubare il nostro lavoro. E' un po' lo stesso ragionamento che facciamo quando chiudiamo a chiave casa prima di uscire: sappiamo perfettamente che un malintenzionato davvero motivato - disponendo di tempo e della attrezzatura giusta - è in grado di fare saltare qualsiasi porta blindata, ma sappiamo anche che la nostra serratura potrebbe scoraggiarlo. E magari speriamo inconsciamente che il malintenzionato sposti la sua attenzione su qualche obiettivo più accessibile.

Il compito di strumenti come CodeWall.NET è di alzare la security bar tra il nostro codice e l'hacker di turno, o il cracker come sarebbe più corretto chiamare questi individui. Noi crediamo che con tutte le tecniche che abbiamo implementato - e che non possiamo discutere pubblicamente per ovvii motivi - renderemo la vita molto, ma molto difficile a questi figuri. Abbiamo passato ore e giorni a discutere su come il programma potrebbe essere attaccato e quindi siamo passati a realizzare una contromisura adeguata. In teoria anche gli assembly protetti con CodeWall.NET sono sproteggibili, ma in pratica servirà qualcuno molto bravo e con un bel po' di tempo a disposizione...

A questo punto, però, mi interessa davvero la vostra opinione. Quando realmente sentite l'esigenza di un prodotto come CodeWall.NET? e quanto i suoi limiti potrebbero indurvi a NON utilizzarlo? Lasciate pure i vostri commenti, please.

Che settimana!

Sono tornato a casa venerdi sera, dopo cinque giorni pieni di WPC. Ero cosi cotto che ho dormito in aereo tutto il tempo, ma ovviamente ne valeva la pena. Nonostante qualche problema tecnico - dovuto al fatto che qualche giorno prima della conf il mio Dell mi ha abbandonato e ho dovuto portare tutto su un altro notebook - le mie sessioni sono andate bene, come pure tutte quelle del team di CA.

Stamattina finalmente (per modo di dire) si torna al lavoro. La prima cosa da fare è mandare i sorgenti delle demo allo staff della WPC, per farle mettere online. Provo a zippare il tutto e arrivo a 7-8 mega di roba. Il motivo è che nello zippone sono inclusi tutti i file prodotti dalla compilazione (exe, dll, obj, ecc.), di cui si puo' fare a meno quando si mandano i sorgenti. E' la solita storia, che si ripete ogni volta che devo mandare il codice per un articolo, una conferenza, o anche semplicemente quando devo passarlo a un amico via email.

Questa volta, però, invece di rimuovere manualmente ogni file, decido di investire 2 minuti (due minuti davvero, non è un modo di dire), per scrivere una piccola utility command line che fa il lavoro per me. Grazie a un overload di Directory.GetDirectories aggiunto a .NET 2.0, è possibile ottenere in un sol colpo tutte le directory in un albero di directory, quindi si tratta semplicemente di cancellare tutti i folder di nome "obj" e "bin". Se la cancellazione fallisce viene mostrato un messaggio di errore: questo puo' accadere se un eseguibile è in esecuzione e non può essere cancellato.

Imports System.IO

Module Module1
   Sub Main(ByVal args() As String)
      ' Use current directory if no argument has been specified
      Dim rootDir As String = Directory.GetCurrentDirectory()
      If args.Length > 0 Then rootDir = args(0)
      ' Read all the folder names in the specified directory tree
      Dim dirNames() As String = Directory.GetDirectories(rootDir, "*.*", SearchOption.AllDirectories)
      Dim errors As Integer = 0

      ' Delete all the BIN and OBJ subdirectories
      For Each dir As String In dirNames
         Dim dirName As String = Path.GetFileName(dir).ToLower()
            If dirName = "bin" OrElse dirName = "obj" Then
               Try
                  Console.Write("Deleting {0} ...", dir)
                  Directory.Delete(dir, True)
                  Console.WriteLine("DONE")
               Catch ex As Exception
                  Console.WriteLine()
                  Console.WriteLine(" ERROR: {0}", ex.Message)
                  errors += 1
               End Try
            End If
         Next

         Console.WriteLine()
         If errors = 0 Then
            Console.WriteLine("All directories were removed successfully")
         Else
            Console.WriteLine("{0} directories couldn't be removed", errors )
         End If
     End Sub
End Module

Mi capita spesso di dover copiare pezzi di un testo sotto forma di commento nei miei sorgenti. Non è una operazione difficile, però è pur sempre una perdita di tempo, perchè spesso non si può semplicemente eseguire il copia e incolla e poi il comando Edit-Comment Selection perchè - almeno in VB - l'editor di Visual Studio cerca di interpretare il testo come codice e quindi ne rovina la formattazione. A questo si aggiunge il fatto che spesso sono costretto a rivedere tutte le andate-a-capo nel testo per evitare righe troppo lunghe, perchè i listati che appaiono nei libri non possono essere più lunghi di N caratteri (tipicamente 92 caratteri, per i libri Microsoft Press). Insomma, una bella seccatura.

Oggi ho deciso di porre fine a questa perdita di tempo, scrivendo una macro che faccia questo lavoro al mio posto. E' un piccolo modo per aumentare la produttività e concentrarsi sulle cose davvero importanti. Se anche a voi piacciono i listati ordinati, sono certo che la troverete utile.

La prima difficoltà in cui mi sono imbattuto è il fatto che, per qualche arcano motivo, il metodo Clipboard.GetObjectData restituisce sempre Nothing quando lo si chiama da una macro, quindi non è possibile usare quel metodo per leggere il contenuto della clipboard. Per qualche minuto ho accarezzato l'idea di lavorare direttamente con le API oppure di scrivere una DLL che eseguisse questo compito, poi ho trovato la classica soluzione a-ha!:

' Retrieve the text in the clipboard

Dim tb As New TextBox

tb.Multiline = True

tb.WordWrap = False

tb.ScrollBars = ScrollBars.Both

tb.Paste()

Dim text As String = tb.Text

Questo codice funziona quasi sempre bene. Ogni tanto, però, ho notato che il metodo Paste fallisce con un messaggio di errore un po' criptico: "Class already exists". Non riesco a spiegarmi il motivo...e tutto sommato non voglio neanche saperlo. Ho notato però che tutto funziona bene se l'editor delle macro è chiuso, quindi nell'uso normale non ci dovrebbero essere problemi. Se però incappate una volta in questo errore, da quel momento in poi la macro andrà sempre in errore. L'unico modo per evitarlo è uscire e rientrare Visual Studio. Come ho detto, accade solo durante lo sviluppo delle macro, quindi non è un problema davvero fastidioso.

Ecco il sorgente completo della macro che esegui il paste del contenuto corrente della clipboard sotto forma di commento:

Ieri ho postato una macro che converte i field in properties. Qualche minuto fa ho rivisto il codice per supportare anche i campi marcati con readonly. Se applicate la macro a tali campi, otterrete (ovviamente!) delle proprietà a sola lettura. In VS2005 potreste anche modificare la stringa assegnata alla variabile repPatternReadonly per generare proprietà con un blocco set privato, in modo da avere una proprietà a sola lettura se vista dall'esterno della classe ma assegnabile dal codice che gira nella classe stessa.

Una cosa che mi stupisce sempre molto è vedere come molti programmatori passino ore a discutere se sia più produttivo VB o C# o Java - magari discettando sulle feature relativamente "minori" del proprio linguaggio - e poi non conoscano a fondo proprio il tool con cui passano la maggior parte del tempo, ovvero l'IDE in cui scrivono e testano il codice. In particolare, ci sono decine e decine di feature di Visual Studio che nella maggior parte dei casi sono sconosciute ai più. Dopo tanti anni, capita anche a me di scoprirne continuamente di nuove.

Il modo migliore per aumentare la produttività con Visual Studio è imparare a scrivere delle macro per automatizzare i compiti più ripetitivi. Certo, ci sono sul mercato tantissimi add-in - anche freeware - che permettono di automatizzare dei compiti ripetitivi, ma capita raramente che facciano esattamente quello che vogliamo. Se volete davvero padroneggiare Visual Studio, occorre proprio rimboccarsi le maniche e imparare a scrivere un po' di macro. Nei casi più semplici, potete semplicemente usare il registratore di macro e modificare poi il codice generato.

Ad esempio, io spesso nei miei prototipi di classe uso dei campi pubblici, ma quando poi occorre scrivere del codice "di produzione" passo un sacco di tempo a convertire il campo in una variabile privata "wrappata" da una proprietà pubblica. Per capirci, parto con questo codice nel prototipo:

Alcuni sample recuperabili via Internet per provare e studiare VSTO (Visual Studio Tools for Office - pronunciato VISTO) per Outlook potrebbero dare problemi di compilazione. Io ho scaricato ad esempio questi sample da msdn.microsoft.com e ho dovuto apportare le seguenti modifiche nell'evento di startup utilizzando il metodo protetto GetPrimaryControl per sistemare il tutto:

Prima della modifica:

private void ThisApplication_Startup(object sender, System.EventArgs e)
{
   // Initialize the event tracker object.
  _eventTracker = new EventTracker(this);
  // Create custom menu items.
  CreateMenu();
}

Dopo la modifica, utilizzando il metodo GetPrimaryControl:

Ero partito, tempo fa, con un post in cui parlavo di grafi navigazionali inseriti in un file xml e dati "in pasto" a UIPAB. La mia intenzione era di far partire una possibile discussione sulla base della mia esperienza (e leggere la vostra) in fatto di disaccoppiamento della UI dal resto dell'applicazione, poi ho pensato che sarebbe stato meglio scrivere qualcosa di più sostanzioso per dare una base più consistente di riflessione. L'articolo è online e lo trovate al seguente link

Link all'articolo "UIPAB2 e l'arte di disaccoppiare le GUI"

mi piacerebbe sapere quanti di voi utilizzano questo application block, se qualcuno lo ha customizzato aggiungendo delle features utili e tutto quello che vi viene in mente rispetto all'argomento. Ritengo che non sia affatto banale progettare uno strato di presentation "realmente" disaccoppiato dagli altri strati quindi mi interessa conoscere le problematiche incontrate (eventualmente superate) e dare, se possibile, qualche suggerimento in proposito, oltre naturalmente a ciò che ho scritto nell'articolo sperando che vi sia utile.

Buona lettura!

Quasi per caso oggi ho scoperto questo sito che è una vera miniera d'oro. Si tratta di How-to-Select Guides (http://www.howtoselectguides.com) e contiene una serie di guide professionali (e l'enfasi è davvero meritata) che spiegano come scegliere un tool di sviluppo di un certo tipo. I documenti non si limitano a descrivere i vari prodotti esistenti, ma spiegano anche quali sono le feature più importanti in quel particolare settore (data grid, charting, report) e mettono poi a confronto i prodotti specifici. Guardate ad esempio a colpo d'occhio come sono confrontate le librerie per generare PDF.

Oggi ho letto per intero la loro guida agli obfuscator ed è fatta benissimo. Non per niente, tutte le guide in questione sono scritte da autori professionisti come Mike Gunderloy e Don Kiely, che hanno una reputazione da difendere e non scrivono fesserie. Tanto per dirne una, spiegano anche quando non usare un prodotto del genere e includono anche prodotti freeware quando ve ne sono.

Oltre alla guida sugli offuscatori, attualmente sono disponibili solo la guida ai vari tipi di licenza di Visual Studio e e la succitata guida alle librerie PDF. Però sono già in preparazione molte altre guide. Un ulteriore conferma della serietà con cui è fatto il sito è che per ciascuna delle future guide è menzionata la data in cui sarà disponibile, e fino ad ora sembra che le deadline passate sono state rispettate. Ci sono anche dei forum pubblici, quindi i lettori e le case produttrici hanno la possibilità di rettificare quanto scritto.

Il sito è una idea di Mike Schinkel, il fondatore di XTras, una nota azienda che distribuisce tool per programmatori. Eppure non ci sono pubblicità di Xtras sul sito, e ho notato che sono recensiti anche molti prodotti che non sono nel catalogo di Xtras. Quando si dice che la classe non è acqua  Spero che abbia il successo che si merita!

Il nostro Sodoku online continua ad andare molto forte, a giudicare dal traffico che sta generando e dal fatto che, se provate a fare una ricerca su Google.it per la parola sodoku è sempre al primo posto o comunque tra le prime posizioni. Ma la cosa più gratificante, per quanto mi riguarda, è che in molti hanno deciso di scaricare il sorgente del programma Win32, per studiarselo. Ad occhio e croce a tutt'oggi il programma è stato scaricato da alcune migliaia di persone.

Qualcuno dei più intrepidi ha anche deciso di modificarlo per i propri scopi. Ad esempio, Roberto Giacomelli lo ha riscritto in C# modificando l'algoritmo per usare la ricorsione (leggete il suo post sull'argomento). Michele Ciboddo ha invece lasciato il programma in VB ma lo ha migliorato risolvendo un bug e soprattutto estendendolo alle griglie 16x16. Ecco un frammento della sua mail:

Per cercare di capire meglio il codice del SodokuSolver, ho provato a modificarlo aumentando le celle. Sono passato da 9x9 a 16x16 con sezioni di 4x4. In pratica è un sodoku esadecimale (le cifre ammesse vanno da 1 a G invece che da 0 a F). Il gioco funziona anche in questa modalità anche se ho dovuto abbassare a 20000 il terzo parametro del metodo FindSolutions per non impallare il computer. Quando ci sono troppe soluzioni l’occupazione della ram va alle stelle. Ho notato che il programma (anche l’originale) segnala “nessuna soluzione” quando lo schema ha una sola soluzione possibile. Nelle spiegazioni comunque la soluzione viene riportata. Ho risolto passando 0 come secondo parametro di FindSolutions invece di 1.

Ecco qui il sorgente modificato e il nuovo eseguibile: SodokuSolver16x16.zip (351.71 KB)

Ho anche corretto in bug nella mia versione originale, che può essere scaricata da questa pagina.

E' uscita la versione 2.0 di Google Desktop Search. Le varie novità le trovate elencate in questa pagina. Ci sono diverse cose interessanti, ma la mia preferita è in assoluto l'integrazione della ricerca direttamente all'interno di Outlook. Per chi come me non archivia o cancella mai i messaggi (a parte lo spam ovviamente ) e di tanto in tanto gli serve cercare tra la posta anche di 5 anni fa, questo strumento è essenziale! Si lo so anche anche la precedente versione permetteva di cercare tra le e-mail dalla sua interfaccia su browser, ma così è ancora più comodo. Altra cosa eccezionale sono i miglioramenti alla Deskbar: ora c'è il Quick Find, ovvero una popup che si apre con i risultati trovati direttamente mentre scrivete, aggiornati ad ogni carattere inserito - cliccando sul risultato vi verrà ovviamente aperto il programma per aprirlo. Buona ricerca a tutti.

Segnalo alcuni tool che possono essere molto utili per fare il capacity planning (o sizing, o dimensionamento) nelle prime fasi di un progetto - quando ancora si hanno solo delle stime piuttosto vaghe del carico di lavoro del sistema.

• L'HP SharePoint 2003 Sizing and Configuration Tool permette di stimare il dimensionamento di un sistema WSS o SPS. Aggiornatissimo e soprattutto molto completo: fornisce tanti dettagli e addirittura mostra quale dovrebbe essere l'hardware (naturalmente con macchine HP!):
  
  
  
  Integrare i documenti di analisi e architettura con questi dettagli fa sempre colpo sul cliente
  
• Per chi lavora con Active Directory c'è invece l'Active Directory Sizer Tool. Ormai vecchio, suggerisce configurazioni con hardware di 5 anni fa (!), ma può tornare utile per stimare RAM e spazio su hard disk.
  
• Sul sito Dell si trovano altri tool per SQL Server e Exchange, che però non ho mai provato personalmente.

Come al solito non esistono formule magiche e universali, e il tutto deve essere integrato con test e benchmark a manina in laboratorio, ma devo dire che questi tool aiutano sempre.

Anzi, se ne conoscete altri e avete avuto esperienze di utilizzo fateci sapere con un commento!

Come preannunciavo nel mio precedente post, mi sono messo al lavoro su una utility in grado di computare le principali metriche software su programmi Visual Basic .NET (versione 2003). Non è stato troppo complicato, soprattutto perchè ho deciso di scrivere un tool da linea di comando anzichè un programma con una bella interfaccia utente.

Il programma lavora su un file sorgente .vb alla volta, e mostra le seguenti informazioni:
  - numero totale di righe di codice, di righe di commenti, e di righe vuote, espresse anche come percentuale sul totale (a livello di file, tipo, e metodo)
  - numero di tipi per file
  - numero di metodi per ciascun tipo
  - numero di exit point in ciascun metodo
  - indice ciclomatico di ciascun metodo
  - massimo livello di nidificazione di if,loop, ecc. in ciascun metodo

Ovviamente non ho resistito alla curiosità di usare CodeMetrics su sè stesso. I risultati li potete vedere nella figura: solo 138 istruzioni eseguibili, tutto sommate davvero poche per un programmino che risolve un problema non banale. Potenza delle regular expression!

Cos'altro ho potuto scoprire? Ad esempio, che tutti i metodi hanno un solo exit point, hanno un livello di nidificazione massimo non superiore a 2, e un indice ciclomatico massimo di 2 (a parte un metodo, il cui I.C. è 12, a causa di una Select Case complessa). Quindi anche se ho scritto pochi commenti (appena il 10% del totale di righe di codice), posso quindi concludere che questo codice dovrebbe essere facilmente manutenibile. Forse non è vero, però questo è quello che dicono le cifre ufficiali!

Non vi resta che scaricarlo, provarlo con i vostri programmi VB.NET, e farmi sapere cosa ne pensate: CodeMetricsVB v0.9.zip (4.89 KB)

Tenete presente che è una version "alpha" e che potrebbe fallire in qualche caso. Ad esempio la procedura di parsing non funziona bene con i tipi nidificati e con le istruzioni If..Then...Else su un'unica riga. Una delle prime aggiunte in programma è la possibilità di estrarre statistiche di un intero progetto VB e di calcolare i valori medi e massimi di alcuni indici. Se avete altri suggerimenti, lasciate pure un commento. Tempo permettendo scriverò anche una versione C#.

Fino a non molti anni fa ero abbastanza refrattario a meccanismi e tool che misurassero in qualche modo le caratteristiche e la leggibilità del codice. Erano i tempi di VB6, quando era davvero difficile scrivere del codice "pulito", non disponendo ad esempio di ereditarietà e di gestione strutturata degli errori. Ma il motivo principale per il mio disinteresse per le metriche del software derivava soprattutto dal fatto che scrivevo codice in quasi totale solitudine, e quando interagivo con altri sviluppatori era a livello binario di componenti e interfacce. Io non andavo a mettere il naso nel loro codice e viceversa.

Le cose sono cambiate da quando esiste Code Architects, dove si lavora in team e spesso occorre uniformare gli stili degli sviluppatori che lavorano sullo stesso progetto. Viene allora naturale voler confrontare, ad esempio, la quantità dei commenti che ciascuno inserisce nel proprio codice, oppure la lunghezza e la complessità "media" dei singoli metodi. Allora ho cominciato ad interessarmi a questo argomento, e uno dei risultati di questo interesse è stato il libro Practical Guidelines and Best Practices for the Microsoft Visual Basic .NET and Visual C# Developer, un titolo chilometrico per una raccolta di 735 regole, il cui scopo è di rendere il codice più leggibile, efficiente, e scalabile possibile. (Per la cronaca, la versione italiana, nella traduzione di Natale Fino, appare con il titolo più "umano" Microsoft .NET Framework: Regole di stile e Best Practice... fine dei consigli per gli acquisti! )

Ovviamente il problema di misurare in qualche modo la complessità del codice esiste da sempre, e molti illustri scienziati hanno definito con esattezza alcuni indici in grado di fornire un valore il più oggettivo possibile per tale complessità. Il significato di alcuni indici è evidente: numero di classi e metodi, numero totale di righe nel programma, numero medio di istruzioni nei metodi, numero medio di metodi per classe, quantità di commenti e percentuale sulle righe totali, ecc. Altre quantità abbastanza interessanti sono la profondità massima dell'inheritance tree delle classi del programma, il numero di classi che derivano da una classe base, il numero di classi esterne da cui l'applicazione dipende, e così via. Sono tutte quantità interessanti, ma che alla fine non forniscono un quadro reale della complessità del programma e della leggibilità del codice - a parte forse la quantità di commenti, che è un indicatore prezioso di quanto facilmente il codice potrà essere manutenuto e aggiornato in futuro.

Tra gli indici più importanti e realmente utili vi è sicuramente l'indice ciclomatico, che indica quanti sono i percorsi possibili all'interno di un metodo. Ad esempio, se un metodo contiene un blocco di istruzioni sequenziali il suo indice ciclomatico è 1; se invece contiene un blocco If o If...Else allora ha un indice ciclomatico pari a 2; se invece contiene un Select Case (VB) o switch (C#) con N blocchi case, allora il suo indice ciclomatico è pari a N se il blocco contiene il blocco Case Else (VB) o default (C#), oppure N+1 se tale blocco non c'è. Il calcolo diventa più complesso quando i blocchi condizionali sono nidificati: un metodo con un blocco If che contiene al suo interno un altro blocco If (con o senza Else) ha un indice ciclomatico pari a 3, perchè sono possibili tre differenti percorsi di esecuzione; se un Select/switch con clausola Case Else/default ha N blocchi Case ciascuno dei quali contiene un blocco If, l'indice ciclomatico sale a N*2, e così via.

L'indice ciclomatico assume una importanza significativa al momento del test del codice. Se un metodo ha indice ciclomatico pari a 3 significa che dovrò preparare almeno tre test per controllare che funzioni bene in tutti i casi. (Ovviamente, in realtà dovrei prepararne un numero maggiore, in quanto occorre di solito controllare le condizioni al limite.) Chi utilizza la metodologia Test Drive Development (TDD) e lavora con NUnit o simile, dovrebbe essere molto sensibile a questo tema, che si preannuncia ancora più importante con il rilascio di Team System, che integrerà questi strumenti all'interno di Visual Studio.

Incidentalmente, l'indice ciclomatico è legato anche al refactoring. Infatti, un metodo con un alto indice ciclomatico dovrebbe essere rifattorizzato per suddividerlo in metodi più semplici. In generale il refactoring è sempre vantaggioso se migliora la leggibilità del codice, ma lo è anche di più se suddividendo un metodo lungo in metodi più semplici si riesce anche a ridurre l'indice ciclomatico complessivo (e quindi il numero di test da effettuare).

Un altro indice abbastanza importante, almeno per il mio stile di codifica, è il numero di exit point di un metodo. Maggiore è questo valore, maggiore è lo sforzo necessario per testare e modificare il codice nel metodo. Idealmente, infatti, tutti i metodi dovrebbero avere un solo exit point, in modo da poter facilmente inserire, se serve, una istruzione per il tracing. Un altro motivo per conoscere questo valore è che in futuro potrei voler modificare il valore di ritorno prima di uscire dal metodo, ad esempio per assicurarmi che la stringa restituita sia in minuscolo, che un numero sia positivo, o che un oggetto non sia Nothing/null.

Quando finalmente si è convinti che avere tutte queste informazioni sul proprio codice non è proprio una perdita di tempo, ci si deve scontrare con la realtà. Nel mondo .NET non esistono molti tool in grado di fornire queste informazioni. Ci sono molti prodotti commerciali, qualche freeware e qualche progetto open source, ma non sono riuscito a trovare un unico prodotto che faccia al caso mio, soprattutto per VB.NET (in C# le cose vanno meglio, come al solito). Ecco quello che ho trovato finora con una ricerca via Google. In molti casi si tratta di prodotti che fanno anche altro (tipicamente, refactoring) oltre a calcolare metriche. Il costo in dollari si riferisce alla versione single-user.

Ecco alcuni tool che lavorano direttamente a livello di Intermediate Language (IL):

vil (freeware): http://www.1bot.com/
NDepend (open source): http://smacchia.chez.tiscali.fr/NDepend.html
Reflector.CodeMetrics (free Reflector add-in): http://projectdistributor.net/Projects/Project.aspx?projectId=42

Questi invece lavorano sui sorgenti C# (alcuni anche con Java):
 
devMetrics ($75): http://www.anticipatingminds.com/Content/Products/devMetrics/devMetrics.aspx
C# Refactory ($99): http://www.xtreme-simplicity.net/index.cfm?pageID=3&htmlpage=CSharpRefactory.html
RSM ($199): http://msquaredtechnologies.com/m2rsm/index.htm
C#-Metrics ($250): http://www.semanticdesigns.com/Products/Metrics/CSharpMetrics.html
dotEasy (open source, alpha version): http://www.doteasy.addr.com/
Source Monitor (freeware): http://www.campwoodsw.com/index.html

Questi sono gli unici che analizzano i sorgenti VB.NET:

Project Analyzer ($199): http://www.aivosto.com/project/project.html
Essential Project Manager (prezzo non precisato): http://www.powersoftware.com/epm/

Il problema dei tool che lavorano direttamente sugli assembly compilati (anzichè sui sorgenti) è che non possono calcolare esattamente le metriche che riguardano la leggibilità del codice, ad es. la quantità di commenti e il numero di statement per metodo. Ma soprattutto, il problema è che i compilatori VB e C# producono un codice IL con un numero maggiore di confronti e salti di quelli presenti nel sorgente, quindi l'indice ciclomatico calcolato da questi tool è sempre superiore a quello reale. Tutti questi tool supportano gli indici più comuni, anche se non mi pare - a leggere la documentazione - che ce ne sia uno che mostri il numero di exit point di un metodo. La maggior parte sono tool a riga di comando, quindi non hanno una bellissima interfaccia utente ma hanno il vantaggio di poter essere integrati nel proprio processo di build.

Alla fine, ho pensato che scrivere un tool in grado di calcolare gli indici che realmente mi interessano non dovrebbe essere troppo complicato, almeno se si ha una sufficiente padronanza delle regular expression. Quindi ho deciso di mettermi al lavoro sul un piccolo tool tutto mio. Se tutto va bene, tra qualche giorno posto sul blog i miei risultati.

Nel frattempo, se avete dimestichezza con strumenti del genere - sia tra quelli citati sopra che altri che non ho trovato nelle mie ricerche - lasciate pure un commento, please!

Mentre aspetto la risposta al sesto quizzettino :) (lo trovate come decimo commento al post precedente) ..

Lo sapevate che l'infrastruttura del ResourceManager è estendibile ? , cioè che potete far si che le risorse non siano caricate dagli assembly satellity ma da un qualunque altro storage di vostro piacimento ? .. behh io lo so da poco :) :  tutto è cominciato quando ho approfondito il significato del costruttore più complesso della classe ResourceManager il quale accetta come ultimo parametro un Type di nome usingResourceSet.

La documentazione fa capire vagamente che quella è la via per estendere l'infrastruttura di .NET preposta al reperimento delle risorse a runtime. Per fortuna ho trovato questo post http://weblogs.asp.net/cnagel/archive/2003/07/06/9751.aspx in cui è spiegato come fare (ed è fornito anche del codice di esempio). L'implementazione che si può scaricare dal post che vi ho linkato prevede di andare a reperire le risorse da un database.
Nell'implementazione mia la classe che derivo da ResourceManager vi fa scegliere se andare per la strada standard o usare uno storage alternativo che è un file XML (lo si decide in base al costruttore usato).

La cosa "carina" è che mi metto in ascolto delle modifiche al file XML e quando questo è modificato invalido la cache del ResurceManager così che alla prossima richiesta le risorse sono caricate fresche (chiamate la Dispose quando "avete finito" o il ResourceManage non va giù perchè un suo metodo si è sottoscritto alla notifica della modifica del file).

Un paio di settimane fa annunciavo in questo post la pubblicazione di una applicazione ASP.NET in grado di risolvere un qualsiasi schema di Sodoku, mediante un semplice algoritmo di backtracking. Da allora ho ricevuto un buon numero di richieste di pubblicare il sorgente, quindi appena ho avuto un oretta libera ho ripulito il codice per renderlo presentabile e ho aggiunto un po' di commenti. Ho anche creato una applicazione Windows Forms con una interfaccia utente più che decorosa, che ha tutte le feature della versione online e in più la possibilità di salvare e ricaricare degli schemi di Sodoku.

Potete scaricare l'intero progetto VB.NET 2003 da questo link, oppure solo l'eseguibile Windows da quest'altro link. Con il sorgente troverete un piccolo articolo in formato Word che spiega come funziona l'algoritmo.

Potete redistribuire sia il codice che l'eseguibile a chi volete, purchè non modificate il logo della azienda e il testo di copyright. Se usate il codice in un vostro programma, per piacere menzionate l'origine del codice e inserite un link a questo post.

Buon divertimento con il Sodoku! Per quanto mi riguarda, dopo aver scritto un programma che risolve il gioco in una frazione di secondo, buona parte dell'interesse si è dissolto. Niente a che vedere con le parole crociate senza schema della cara vecchia Settimana Enigmistica... fossi mai riuscito a completarne una!

UPDATE: Michele Giboddo mi ha segnalato un bug nel programma, che segnala erroneamente "nessuna soluzione" quando invece lo schema ha esattamente una soluzione. Per maggiori informazioni leggete questo post. I link al sorgente ed eseguibile in questa pagina puntano già alla versione corretta.

Un'altra versione aggiornata a .NET 2.0 della straordinaria tecnologia User Interface Application Block e' stata rilasciata. In passato era più che altro un buon esempio ed un ottimo punto di partenza per organizzare un po' più seriosamente i propri progetti e applicazioni di bassa e media complessità avvalendosi di tecniche di organizzazione di grafi navigazionali esterni alla propria applicazione (per qualsiasi approfondimento "in lingua" leggete gli articoli pubblicati su dotnet2themax da Fabio Carucci). Questa volta, a quanto pare, la soluzione proposta sembra decisamente più impegnativa ed elaborata. Infatti il suo nome, in questa rinnovata versione, è Composite UI Application Block ed è indirizzata principalmente a problematiche di tipo Windows Based (la precedente prevedeva anche il web) di una certa complessità. I requisiti minimi sono VB.NET o C#, .NET Framework 2.0 e ovviamente Windows Forms. L'architettura e gli oggetti disponibili sono aumentati arricchendosi di una serie di building block pronti per essere utilizzati in applicazioni reali tanto che esistono già dei prodotti commerciali che ne fanno largamente uso (http://www.microsoft.com/serviceproviders/solutions/ccf.mspx).

Sono sicuro che su questo stesso sito vedrete apparire presto articoli in lingua italiana. Come Code Architects siamo già da tempo attivi su questo fronte includendo spesso questa tecnologia nei nostri piani (abbiamo prodotto anche applicazioni webform over http con questa tecnologia), prototipi, consulenze e quant'altro. Per approfondimenti, nel frattempo, vi consiglio di seguire il seguente link per la Community Technical Preview ufficiale MSDN: http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dnpag2/html/CABCTP.asp

Enjoy :)
Giuseppe Dimauro

Mike Swanson durante un weekend ha scritto un interessantissimo plug-in per Adobe Illustrator per esportare documenti Illustrator in formato XAML. Il risultato ottenibile da Illustrator a XAMLPad (non senza limiti però – leggere le note) è straordinario:

Benchè Mike sia un dipendente Microsoft, il tutto non è supportato in alcun modo direttamente da Microsoft. Si tratta semplicemente di un progetto personale scritto per puro sfizio durante i ritagli di tempo da Mike.

Il blog di Mike è il seguente: http://blogs.msdn.com/mswanson/default.aspx
Il tutto è scaricabile da qui: http://www.mikeswanson.com/XAMLExport/

Vi vorrei segnalare due interessanti software freeware che ho installato da un po', dopo averli visti usare da Renato G. di Microsoft Italia (che quindi ringrazio )mentre ero lì da loro per una consulenza.

Il primo è Maxthon, un browser con molte caratteristiche simpatiche tra le quali il multi-tab, apertura dei link tramite brag&drop sulla barra dell'indirizzo, un lettore RSS integrato (riesce anche ad avvertirvi in automatico, mentre navigate, se nella pagina corrente è disponibile un feed da registrare), supporto per skin e plug-in, un popup-blocker veramente potente (blocca pubblicità che finora non mi bloccava nessun'altro, incluse quelle flash embedded), integrazione sulla toolbar di molti motori di ricerca, associazione di azioni a particolari sequenze con il mouse (ad es. tenere premuto il tasto destro e muovere il mouse verso il basso corrisponde ad uno scroll di pagina, tasto destro e sinistra = torna a pagina precedente)!!! Il fatto che poi lo usasse un dipendente Microsoft non è strano o "riprovevole" perchè Maxthon usa il motore di IE, e fa da "wrapper" per aggiungere tutte queste funzionalità. Anche Dave Massy, un PM di IE ammette che usa e che gli piace Maxthon, e conferma che molte delle funzionalità di Maxthon sono anche supportate e documentate direttamente da Microsoft, essendo ereditate dal loro engine.

Per quanto mi riguarda, ho installato già da un bel po' FireFox perchè trovo molto comodo il multi-tab, ma molte pagine mi vengono caricate male...non so se sia a causa di HTML scritto male o altro, ma vedersi una pagina caricata a metà non è proprio comodo. Alla fine non posso pretendere che i miliardi di pagine web esistenti vengano corrette per essere visualizzate correttamente in browser dalla manica meno larga rispetto ad IE, mi basta vederle bene, quindi preferisco IE, e quindi Maxthon! Posso usare FireFox per vedere come si comportano le MIE pagina, e correggerle di conseguenza se è il caso, ma per la navigazione mi sa che non fa per me...

L'altro tool è meno funzionalmente utile, e più scenico a dire il vero...ma perchè no? Aqua Dock è una toolbar animata che si installa lungo uno dei bordi del desktop e vi permette di lanciare le vostre applicazioni preferite. Una sorta di Quick Launch Bar, ma con uno stile OS X (modificabile comunque tramite altre skin) e con varie animazioni che la fanno scomparire e ingrandiscono le incone al passaggio del mouse. Se poi aggiungete un link ad una cartella o un disco fisso, cliccando la relativa icone e tenendo premuto per un secondo si aprirà un menù che vi permetterà di navigare quella cartella e tutte le sotto cartelle, evitandovi ad esempio di aprire nuove finestre di Gestione Risorse per andare a trovare un file sotto My Documents o altri folder di utilizzo comune. E' leggera da scaricare, e merita un'occhiata

Un Web Service che ha scelto il DataSet come formato di scambio dati è un pessimo esempio di interoperabilità. Esso in realtà non è utlizzabile da client non .NET (se non in forma de-tipizzata lavorando a livello di XML).

Come fare però se la nostra applicazione usa già internamente i DataSet e si vogliono pubblicare alcuni dei suoi servizi come Web Services ? Occorre travasare in qualche modo i dati avanti e indietro nei due formati: i dataset sono convertiti in oggetti tipizzati che sono restituiti dal Web Service; parimenti, un oggetto tipizzato ricevuto da un Web Service, viene convertito in un Dataset prima di essere passato ai livelli sottostanti dell'applicazione.

Fortunatamente la cosà puo' essere automatizzata e generalizzata sfruttando le similutidini tra la rappresentazione XML dei dataset, così come è restituita dai metodi ReadXml/WriteXml ed il formato con cui il serializzatore XML rappresenta proprietà e metodi pubblici delle classi.

Occorre prima di ciò però affrontare ancora un altro problema: come generare tali classi tipizzate ? Escludendo l'ipotesi di farlo manualmente esistono due soluzioni : a) usare il tool XSD b) creare un proprio generatore di codice che genera il codice delle classi tipizzate basandosi sullo schema del Dataset. Per avere il pieno controllo sul codice generato ho percorso la seconda alternativa ottenendo la seguente classe (ai volenterosi l'uso di CodeDom per fare la stessa cosa :) ) :

using System;
using System.Text ;
using System.Data ;

namespace ds2ws {
 public class GenerateTypedClass    {
  private GenerateTypedClass() {}

  public static string Go(DataSet p_ds,string p_rootnamespace) {
   StringBuilder l_sb = new StringBuilder ();
   pf_emitDSEnterBlock(p_ds,l_sb,p_rootnamespace);
   foreach(DataTable l_dt in p_ds.Tables) {
      if(l_dt.ParentRelations.Count >1) throw new Exception ("Table " + l_dt.TableName 
         + " has more than one incoming relation");                 
      if(l_dt.ParentRelations.Count ==0) 
         pf_EmitArrayContainer(l_dt,l_sb); 
   } 

   foreach(DataTable l_dt in p_ds.Tables) {
      if(l_dt.ParentRelations.Count >1) throw new Exception ("Table " + l_dt.TableName + " has more than one incoming relation"); 
      if(l_dt.ParentRelations.Count ==0) pf_EmitTable(l_dt,l_sb);
   } 
   l_sb.Append (c_ExitBlock);             
   l_sb.Append (c_ExitBlock);             
   return l_sb.ToString ();
 }

 private static void pf_EmitArrayContainer(DataTable p_dt, StringBuilder p_sb) {
  p_sb.Append (c_MemberList.Replace("%dsname%",p_dt.DataSet.DataSetName).Replace("%tablename%",p_dt.TableName.Replace(' ','_')));
 }

 private static void pf_EmitTable(DataTable p_dt, StringBuilder p_sb) {
   p_sb.Append (c_TableEnterBlock.Replace("%dsname%",p_dt.DataSet.DataSetName).Replace("%tablename%",p_dt.TableName.
      Replace(' ','_')).Replace("%namespace%",p_dt.DataSet.Namespace)); 
   foreach(DataColumn l_column in p_dt.Columns) 
      p_sb.Append (c_Property.Replace("%columnname%",l_column.ColumnName.Replace (' ','_'))
       .Replace("%datatype%",l_column.DataType.Name)); 

   foreach(DataRelation l_rel in p_dt.ChildRelations) 
      pf_EmitArrayContainer(l_rel.ChildTable ,p_sb);
   p_sb.Append (c_ExitBlock); 
   foreach(DataRelation l_rel in p_dt.ChildRelations) 
      pf_EmitTable(l_rel.ChildTable ,p_sb);
} 

static string c_DSEnterBlock = @"
using System;
namespace %rootnamespace%.WS {
using System.Xml.Serialization;
[System.Xml.Serialization.XmlTypeAttribute(Namespace=""%namespace%"")]
[System.Xml.Serialization.XmlRootAttribute(Namespace=""%namespace%"", IsNullable=false)]
public class %dsname% {" 
+ Environment.NewLine
+ @" private string m_version; public string Version { get { return m_version;} set { m_version=value; }}" + Environment.NewLine 
+ Environment.NewLine ;

static string c_TableEnterBlock = @"[System.Xml.Serialization.XmlTypeAttribute(Namespace=""%namespace%"")]
   public class %dsname%%tablename% {"+ Environment.NewLine ;

static string c_ExitBlock = @"}" + Environment.NewLine ;

static string c_Property = @"private %datatype% m_%columnname%; public %datatype% %columnname% { get { return m_%columnname%;} set 
   { m_%columnname%=value; }}" + Environment.NewLine ;

static string c_MemberList =@"[System.Xml.Serialization.XmlElementAttribute(""%tablename%"", typeof(%dsname%%tablename%))] 
   public %dsname%%tablename%[] %dsname%%tablename%Items;" + Environment.NewLine ;

private static void pf_emitDSEnterBlock(DataSet p_ds, StringBuilder p_sb,string p_rootnamespace) {
   p_sb.Append (c_DSEnterBlock.Replace("%dsname%",p_ds.DataSetName).Replace("%namespace%",p_ds.Namespace).Replace("%
      rootnamespace%",p_rootnamespace));             
}
}
}

Il metodo di entrata ha nome Go. Riceve un Dataset ed una stringa che rappresenta il namespace all'interno del quale deve essere creata la classe tipizzata. Del dataset è evidentemente rilevante la sua struttura e non i dati eventualemnte contenuti.

Salvato come file la stringa restituita dal metodo GO ed incluso tale file nel progetto, andiamo a vedere come travasare i dati da un dataset alla sua classe tipizzata corrispondente e viceversa: