Almost-RERERE : optimizing automatic conflict resolution

This thesis deals with the optimization of Almost-RERERE, a tool that learns how to solve code conflicts from past experience and applies resolutions to conflicts not seen before. The concurrent development of applications requires the ability of reconciling conflicting updates to the code made independently. In this scenario, every integration test will require to manually resolve the same conflicts at every iteration. Thus the opportunity arises of supporting the resolution of merge conflicts automatically by learning the way in which developers fix them. The proposed approach is text-based, does not depend on the programming languages of the merged files and exploits a well-known and general language (search and replacement regular expressions) to encode conflict resolution rules. The synthesis of the resolution rules exploits a general-purpose string search and replacement algorithm which takes as input a series of examples, consisting of pairs describing the original string and the desired modified string and outputs a search pattern and a replacement expression. The method employs a Genetic Programming algorithm inspired by concepts of biological evolution such as reproduction, mutation, recombination, and selection. The computational complexity of this method causes long times for the synthesis of the rules even for small clusters, hence the need to improve the performance of the algorithm to allow its use in plausible code-base integration scenarios. Moreover the accuracy of the framework still has room for improvement, so there are approaches that can be analyzed to improve quality of the results. We present the method used to analyse, adapt, optimize and finally evaluate the performances of a new version of the GP algorithm against the original one and the improvements we applied to the framework which led to a gain in the final accuracy evaluation of the tool. The results of the enhancements with respect to the original baseline will be finally discussed by showing the results of our experiments over a large set of data extracted from open source repositories.

Questa tesi tratta l’ottimizzazione di Almost-RERERE, uno strumento che impara a risolvere i conflitti nel codice dall’esperienza passata e applica risoluzioni a conflitti mai visti prima. Lo sviluppo simultaneo di applicazioni richiede la capacità di riconciliare aggiornamenti contrastanti del codice effettuati in modo indipendente. In questo scenario, ogni test di integrazione richiede la risoluzione manuale dei conflitti; si presenta così l’opportunità di supportare automaticamente questo processo imparando il modo in cui gli sviluppatori li risolvono. L’approccio proposto è basato sul testo, non dipende dai linguaggi di programmazione dei file uniti e sfrutta un linguaggio noto e generale (ricerca e sostituzione di espressioni regolari) per codificare le regole di risoluzione. La sintesi delle regole sfrutta un algoritmo di ricerca e sostituzione di stringhe generico che prende come input una serie di esempi, costituiti da coppie che descrivono la stringa originale e la stringa modificata desiderata e genera un modello di ricerca e un’espressione di sostituzione. Il metodo utilizza un algoritmo di programmazione genetica ispirato a concetti di evoluzione biologica come riproduzione, mutazione, ricombinazione e selezione. La complessità computazionale di questo metodo causa tempi lunghi per la sintesi delle regole anche per piccoli cluster, da qui la necessità di migliorare le prestazioni dell’algoritmo per consentirne l’utilizzo in scenari plausibili di integrazione delle code-bases. Inoltre l’accuratezza del framework ha ancora margini di miglioramento, quindi ci sono approcci che possono essere analizzati per migliorare la qualità dei risultati. Presentiamo dunque il metodo utilizzato per analizzare, adattare, ottimizzare e infine valutare le prestazioni della nuova versione dell’algoritmo genetico rispetto a quella originale e i miglioramenti applicati al framework che hanno portato a un guadagno nella valutazione finale dell’accuratezza dello strumento. I risultati dei miglioramenti rispetto ai riferimenti della versione originale verranno infine discussi mostrando i risultati dei nostri esperimenti su un ampio set di dati estratti da repository open source.