AI e software open source: un aiuto alla risoluzione dei conflitti nei progetti distribuiti

L’apertura del codice open source favorisce modalità di sviluppo collaborative, in cui un’intera comunità di sviluppatori contribuisce alla creazione, manutenzione ed evoluzione del software. I progetti open source sono il luogo in cui gli sviluppatori collaborano tra loro e con la comunità degli utenti finali per sviluppare applicazioni innovative.

Quando lo stesso programma viene modificato da più programmatori possono però sorgere incongruenze dovute a modifiche incompatibili dello stesso blocco di codice. Questo evento è chiamato conflitto.

Il progetto ALMOST-RERERE (REuse REcorded REsolutions) del Dipartimento di Elettronica Informazione e Bioingegneria del Politecnico di Milano ha realizzato uno strumento di intelligenza artificiale per la risoluzione semiautomatica dei conflitti e lo ha integrato in Git, il sistema per il controllo delle versioni (Version Control System, VCS) di GitHub. Quest’ultima è la più grande piattaforma che ospita progetti open source è GitHub e nel momento in cui questo articolo è scritto accoglie oltre 73 milioni di sviluppatori appartenenti a oltre 4 milioni di organizzazioni e attivi su più di 200 milioni di progetti.

L’Europa post Privacy Shield: è l’open source la via per uscire dal colonialismo digitale

Il sistema per il controllo delle versioni e la risoluzione dei conflitti

Lo sviluppo di applicazioni complesse e di grandi dimensioni richiede la distribuzione della programmazione tra più sviluppatori. Perciò il cuore di una piattaforma per progetti open source collaborativi è il sistema per il controllo delle versioni (Version Control System, VCS). Un VCS permette a più sviluppatori di lavorare contemporaneamente allo stesso codice sorgente.

Per supportare lo sviluppo distribuito, i VCS offrono funzioni per condividere il codice, tenere traccia delle modifiche e identificare i conflitti causati dall’unione (merge) di versioni concorrenti. Quando il VCS segnala un conflitto, uno degli sviluppatori coinvolti deve risolverlo manualmente, riconciliando tra di loro le modifiche incompatibili. Questa attività rende l’integrazione del codice un’attività lunga e dispendiosa.

La risoluzione dei conflitti è anche un’attività ripetitiva perché conflitti simili o identici si ripresentano spesso ad ogni nuova iterazione. Uno studio su progetti software open source [Nguyen2013] ha rilevato che la ripetitività di piccole modifiche può essere molto elevata (fino al 70%) e può richiedere di risolvere più volte molti conflitti simili durante l’integrazione. Una recente indagine su 2.731 progetti open source ha permesso una caratterizzazione molto accurata dei conflitti [Ghiotto2018]. Oltre la metà dei blocchi di codice in conflitto ha dimensioni limitate (5 righe o meno) e spesso (nell’87% dei casi) il conflitto è risolto sfruttando codice già presente nelle versioni fuse. Ciò è confermato anche da un recente studio dello sviluppo distribuito del browser Microsoft Edge, da cui emerge che i conflitti si verificano nella gran parte delle integrazioni (80,4%), che i blocchi conflittuali piccoli (da 1 a 2 LOC) rappresentano quasi un terzo del totale e che le risoluzioni manuali tendono a seguire schemi ripetitivi [MS2021].

Questi dati suggeriscono la possibilità di applicare metodi basati sull’intelligenza artificiale per apprendere le regole con cui gli sviluppatori umani risolvono i conflitti combinando i segmenti di codice esistenti per poi applicare tali regole a nuovi conflitti nello stesso o in altri progetti.

Tabella 1.Dieci delle più grandi progetti su GitHub per numero di Commits e di svilupatori.

Il progetto ALMOST-RERERE

Il progetto ALMOST-RERERE ha sviluppato un metodo per consentire a un sistema VCS di apprendere come risolvere autonomamente nuovi conflitti grazie alla conoscenza dei conflitti risolti in precedenza dai programmatori.

L’idea chiave è analizzare le risoluzioni dei conflitti prodotte dagli sviluppatori in passato per creare regole applicabili automaticamente a conflitti futuri. Quando in un progetto il primo conflitto è risolto manualmente, il blocco di codice conflittuale e la risoluzione creata dal programmatore sono elaborati per derivare una regola di risoluzione (Conflict Resolution Rule — CRR). Quindi viene creato un primo gruppo di conflitti simili (Conflict Cluster — CC) e la regola è associata a tale gruppo. Un CC contiene conflitti con struttura simile che possono essere risolti allo stesso modo. Quando si verifica un nuovo conflitto, lo si confronta con i gruppi esistenti. Se la somiglianza con i conflitti di uno o più gruppi già formati è superiore a una certa soglia, si usa la regola CRR del gruppo con la massima somiglianza per generare la risoluzione automatica. Poi il conflitto è aggiunto al gruppo e l’algoritmo di generazione delle regole è eseguito di nuovo per tenere conto della conoscenza contenuta nel nuovo conflitto e derivare una regola più precisa. Se invece non si trova un gruppo di conflitti sufficientemente simili a quello nuovo, si interpella l’utente che deve fornire una risoluzione manuale, da cui si genera una nuova coppia (CC, CRR).

I risultati del progetto ALMOST-RERERE

Il gruppo di ricerca del Dipartimento di Elettronica Informazione e Bioingegneria del Politecnico di Milano ha lavorato per oltre due anni al problema della risoluzione semiautomatica dei conflitti nei progetti open source distribuiti. I risultati conseguiti, codificati in un sistema chiamato ALMOST-RERERE che estende la piattaforma VCS Git, possono essere riassunti come segue.

• L’obbiettivo della risoluzione semiautomatica di conflitti nei progetti distribuiti è stato formalizzato come un problema di apprendimento automatico e affrontato con le tecniche dell’Intelligenza Artificiale più idonee per questa classe di problemi.
• L’apprendimento automatico delle modalità di risoluzione di un conflitto è stato affrontato in due passi:
  • Il primo passo identifica nella storia del progetto i conflitti simili a quello da risolvere. A questo scopo si è definito un algoritmo di clustering in grado di raggruppare conflitti simili in gruppi (CC) e di assegnare un nuovo conflitto al gruppo che contiene gli esempi più simili. Un CC include conflitti risolvibili nello stesso modo.
  • Una volta raggruppati i conflitti simili, un algoritmo genetico [Bartoli2019] crea automaticamente le regole di risoluzione (CRR) per i conflitti di ciascun CC. Una CRR è un micro-programma (più precisamente un’espressione regolare di ricerca e sostituzione) sintetizzato a partire da un insieme di risoluzioni di conflitti specificate come coppie <stato precedente, stato successivo>. Lo stato precedente esprime la porzione di codice interessata da modifiche inconsistenti mentre lo stato successivo rappresenta la versione del codice da cui sono state eliminate le inconstenze. Una CCR codifica le modifiche da apportare al codice sorgente per trasformare lo stato iniziale inconsistente in uno stato finale in cui le inconsistenze sono risolte.
• La tecnica di Intelligenza Artificiale progettata è implementata nel sistema ALMOST RERERE, che estende le funzionalità di Git VCS (vedi Figura 1). ALMOST RERERE risolve conflitti simili a quelli osservati nelle iterazioni precedenti e può essere usato durante il processo di sviluppo per velocizzare la risoluzione dei conflitti con regole che diventano sempre più precise man mano che lo sviluppo dell’applicazione progredisce.
• L’efficacia di ALMOST RERERE è stata valutata su 21 progetti open source. Si sono estratti 44.282 blocchi di codice conflittuali e si sono usati 12.891 conflitti di dimensioni ridotte (fino a 6 LOC) per derivare le regole CRR. Si sono sfruttate le risoluzioni manuali fornite dagli sviluppatori presenti nell’archivio storico del VCS per valutare l’accuratezza del sistema. I risultati dimostrano che ALMOST RERERE può sintetizzare una risoluzione per oltre il 43% dei conflitti (oltre il 70% se si considerano i conflitti che hanno almeno un conflitto simile nella storia precedente) e può riprodurre esattamente la stessa soluzione che gli sviluppatori umani hanno applicato nel 44% dei casi (53% per conflitti che interessano una sola riga di codice).

Figura 1: l’architettura di ALMOST-RERERE

La Figura 1 mostra l’architettura di Almost Rerere, che comprende quattro componenti principali: Submission Manager, Cluster Manager, CRR Generator e Conflict Resolver. Il Submission Manager estende Git e orchestra l’elaborazione di un comando di unione (merge) o salvataggio (commit) emesso dallo sviluppatore. Il Cluster Manager implementa l’algoritmo che assegna un conflitto a un cluster esistente o nuovo. Il CRR Generator realizza il metodo per la generazione delle regole di risoluzione ed è attivato ogni volta si aggiunge un conflitto a un cluster. Infine, il Conflict Resolver è invocato quando si verifica un nuovo conflitto. Cerca il cluster con il più alto indice di somiglianza, estrae la regola CRR associata, la applica e restituisce il risultato come possibile risoluzione al conflitto.

Il codice del progetto è disponibile come open source nel repositorio GitHub

Bibliografia

[EC2021] European Commission DG CONNECT, Study about the impact of open source software and hardware on technological independence, competitiveness and innovation in the EU economy, 06 September 2021, https://digital-strategy.ec.europa.eu/en/library/study-about-impact-open-source-software-and-hardware-technological-independence-competitiveness-and

[RedHat] Cosa significa open source? https://www.redhat.com/it/topics/open-source/what-is-open-source

[OSS20-23] Communication to the Commission, Open Source Software Strategy 2020 – 2023

Think Open https://ec.europa.eu/info/sites/default/files/en_ec_open_source_strategy_2020-2023.pdf

[MITD2021] Ministero per l’innovazione tecnologica e la transizione digitale, Il valore dell’open source per un’Europa digitale indipendente e competitiva, 27 settembre 2021, https://innovazione.gov.it/notizie/articoli/il-valore-dell-open-source-per-un-europa-digitale-indipendente-e-competitiva/

[Nguyen2013] H. A. Nguyen, A. T. Nguyen, T. T. Nguyen, T. N. Nguyen, and H. Rajan, “A study of repetitiveness of code changes in software evolution,” in Proceedings of the 28th IEEE/ACM International Conference on Automated Software Engineering, ser. ASE’13. Piscataway, NJ, USA: IEEE Press, 2013, pp. 180–190.

[Ghiotto2018] G. Ghiotto, L. Murta, M. Barros, and A. Van Der Hoek, “On the nature of merge conflicts: a study of 2,731 open source java projects hosted by github,” IEEE Transactions on Software Engineering, vol. 46, no. 8, pp. 892–915, 2018.

[MS2021] R. Pan, V. Le, N. Nagappan, S. Gulwani, S. Lahiri, and M. Kaufman, “Can program synthesis be used to learn merge conflict resolutions? an empirical analysis,” in 2021 IEEE/ACM 43rd International Conference on Software Engineering (ICSE). IEEE, 2021, pp. 785–796.

[Bartoli2019] A. Bartoli, A. De Lorenzo, E. Medvet, and F. Tarlao, “Automatic search-and-replace from examples with coevolutionary genetic programming,” IEEE transactions on cybernetics, 2019.