💻 computer science

Combining Example-Based and Rule-Based Program Transformations to Resolve Build Conflicts

Dit artikel introduceert BuCoR, een hybride tool die voor het oplossen van build-conflicten tijdens het samenvoegen van softwarebranches zowel vooraf gedefinieerde regels als voorbeeldgebaseerde transformaties combineert om automatisch en effectief oplossingen te genereren.

Oorspronkelijke auteurs: Sheikh Shadab Towqir, Fei He, Todd Mytkowicz, Na Meng

Gepubliceerd 2026-02-13

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Sheikh Shadab Towqir, Fei He, Todd Mytkowicz, Na Meng

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je samen met een vriend een groot, ingewikkeld legpuzzel maakt. Jullie werken allebei aan hetzelfde plaatje, maar op verschillende momenten en op verschillende manieren. Jij plakt een stukje in de hoek, en je vriend plakt een ander stukje in het midden. Als jullie later proberen jullie twee helften samen te voegen tot één groot plaatje, kan het gebeuren dat jullie stukken op elkaar liggen of niet goed passen. In de programmeerwereld noemen we dit een merge-conflict.

Meestal zijn dit kleine tekstproblemen ("Oh, jij hebt hier een puntje gezet, ik niet"). Maar soms zijn het bouwkwesties: de code die jullie samenvoegen, werkt niet meer als een geheel. Het programma crasht of kan niet worden gebouwd. Tot nu toe konden computers deze problemen wel zien, maar ze konden ze niet goed oplossen. Mensen moesten er urenlang naar zitten om het handmatig te fixen.

Deze paper introduceert BuCoR (BUild COnflict Resolver), een slimme nieuwe tool die dit probleem oplost door twee verschillende manieren van denken te combineren. Je kunt BuCoR zien als een super-architect die twee soorten hulpkrachten heeft:

1. De "Vind-En-Kopieer" Hulpkracht (BuCoR-E)

Stel je voor dat je in het verleden al eens een soortgelijk probleem had opgelost. Misschien heb je toen een muur verplaatst en heb je ook de ramen en de deur aangepast om dat te laten werken.

BuCoR-E kijkt naar de twee versies van jullie code (jouw versie en die van je vriend) en zoekt naar voorbeeldoplossingen.

Hoe het werkt: Het tooltje denkt: "Ah, in jouw versie heb je de naam van een kamer veranderd. Kijk eens, daar heb je ook de brievenbus en het postadres aangepast om dat te laten werken. Laten we datzelfde patroon kopiëren naar het nieuwe probleem!"
Het voordeel: Het is heel slim en creatief. Het kan complexe situaties oplossen die nog nooit eerder zijn gezien, zolang er maar een voorbeeld is in de code zelf.
De beperking: Als er in de code geen voorbeeld te vinden is van hoe zo'n probleem eerder is opgelost, kan deze hulpkracht niets doen.

2. De "Regel-En-Verstand" Hulpkracht (BuCoR-R)

Deze hulpkracht is een strenge, maar betrouwbare regelaar. Hij heeft een boekje met 16 vaste regels voor de meest voorkomende problemen.

Hoe het werkt: Hij denkt: "Oh, iemand heeft een klasse hernoemd en iemand anders gebruikt de oude naam. Regel nummer 3 zegt: 'Pas altijd de gebruikte naam aan naar de nieuwe naam'." Hij past deze standaardoplossing direct toe.
Het voordeel: Hij is razendsnel en werkt perfect voor de simpele, standaardproblemen die vaak voorkomen.
De beperking: Hij is een beetje star. Als het probleem heel raar of uniek is (buiten de 16 regels), weet hij geen raad en zegt hij: "Ik heb hier geen regel voor."

De Magische Combinatie

Het echte genie van BuCoR is dat het beide hulpkrachten tegelijk inzet.

Als er een standaardprobleem is, pakt de "Regel-hulpkracht" het snel op.
Als het probleem complex en uniek is, springt de "Vind-En-Kopieer-hulpkracht" in en zoekt naar slimme voorbeelden in de code.
Soms geven ze allebei een oplossing. Dan kiest BuCoR de beste optie, of laat het de menselijke programmeur kiezen.

Wat hebben ze ontdekt?

De onderzoekers hebben BuCoR getest op 88 echte, moeilijke bouwconflicten uit verschillende open-source projecten.

Het systeem slaagde erin om voor 74% van de conflicten een oplossing te bedenken.
Van die oplossingen was 52% volledig correct (d.w.z. het werkte precies zoals een mens het zou hebben gedaan).
De twee methoden vullen elkaar perfect aan: de regels dekken veel gevallen, maar de voorbeelden vinden de oplossingen voor de moeilijke, unieke situaties.

Waarom is dit belangrijk?

Voorheen moesten programmeuren urenlang zitten om te puzzelen waarom hun code niet werkte na het samenvoegen. BuCoR is als een slimme assistent die niet alleen ziet waar het misgaat, maar ook hoe het opgelost kan worden. Het combineert de snelheid van vaste regels met de creativiteit van het leren van voorbeelden.

Kortom: BuCoR maakt het samenvoegen van software minder een nachtmerrie en meer een simpele klik, zodat programmeuren zich kunnen focussen op het bouwen van geweldige nieuwe functies in plaats van het oplossen van oude ruzies.

Probleemstelling

Bij het samenvoegen (mergen) van softwarebranches in versiebeheersystemen zoals Git ontstaan vaak merge-conflicten. Deze conflicten zijn van twee aard:

Tekstuele conflicten: Overlappende wijzigingen in de broncode.
Build- en testconflicten: Wijzigingen die, hoewel ze tekstueel mogelijk samengevoegd kunnen worden, leiden tot compilatiefouten of testfalen in het samengevoegde resultaat.

Bestaande tools kunnen deze build-conflicten vaak detecteren, maar bieden weinig tot geen automatische ondersteuning voor het oplossen ervan. Bestaande oplossingen (zoals Gmerge en MrgBldBrkFixer) zijn beperkt tot simpele gevallen, zoals het hernoemen van symbolen. Ze falen bij complexere conflicten veroorzaakt door veranderingen in klassenhiërarchie, het toevoegen/verwijderen van methoden, of het wijzigen van parameterlijsten. Developers moeten deze conflicten vaak handmatig oplossen, wat tijdrovend en foutgevoelig is.

Methodologie: BuCoR

De auteurs introduceren BuCoR (BUild COnflict Resolver), een hybride tool die twee complementaire strategieën combineert om build-conflicten automatisch op te lossen: voorbeeldgebaseerde transformatie (BuCoR-E) en regelgebaseerde transformatie (BuCoR-R).

Het proces verloopt in vier fasen:

Conflictdetectie (Bucond):
BuCoR gebruikt een bestaande tool, Bucond, die statische analyse toepast op drie versies: de basisversie ( $b$ ), de linkerbranch ( $l$ ) en de rechterbranch ( $r$ ). Het modelleert deze als Program Entity Graphs (PEG) en detecteert conflicten door te kijken naar incompatibele bewerkingen (bijv. een methode hernoemen in $l$ terwijl $r$ een aanroep aan de oude naam toevoegt).
Grafische Constructie:
De tool genereert een naïef samengevoegde versie ( $A_m$ ) met git-merge en bouwt een vier-weg verbonden grafiek. Deze grafiek koppelt de PEG's van $b$ , $l$ , $r$ en $A_m$ aan elkaar. Dit stelt BuCoR in staat om de context van bewerkingen nauwkeurig te plaatsen en de structuur van de code te analyseren.
Strategie 1: Voorbeeldgebaseerde Transformatie (BuCoR-E):
- Principe: Veel build-conflicten ontstaan door een mismatch tussen een definitie (def) en een gebruik (use). BuCoR-E gaat ervan uit dat ontwikkelaars in de branches ( $l$ of $r$ ) al soortgelijke mismatches hebben opgelost bij eerdere build-fouten.
- Mijnproces: De tool zoekt in de branches naar voorbeeldbewerkingen (exemplar edits) die een definitie-aanpassing compenseren.
- Patrooninferentie: Uit deze voorbeelden worden transformatiepatronen afgeleid door onnodige context te verwijderen en afhankelijkheden (data- en controle-afhankelijkheden) te analyseren.
- Toepassing: Het gevonden patroon wordt gematcht met de context in de samengevoegde versie ( $A_m$ ). Als er een match is, wordt het patroon aangepast en toegepast om het conflict op te lossen. Dit werkt goed voor projectspecifieke of ongebruikelijke oplossingen.
Strategie 2: Regelgebaseerde Transformatie (BuCoR-R):
- Principe: Voor veel voorkomende conflicten bestaan er conventionele oplossingspatronen.
- Regelset: De auteurs hebben 16 specifieke regels gedefinieerd die veelvoorkomende conflicten behandelen (bijv. hernoemen van een klasse, toevoegen van een methode in een superklasse, verwijderen van imports).
- Toepassing: Als een conflict overeenkomt met een van deze 16 patronen, past BuCoR-R de corresponderende regel toe. Dit is effectief voor standaardscenario's waar geen specifieke voorbeelden in de branches te vinden zijn.

Belangrijkste Bijdragen

Hybride Aanpak: De eerste tool die voorbeeldgebaseerd leren (uit branches) combineert met regelgebaseerde transformaties voor het oplossen van build-conflicten.
Geavanceerde Voorbeeldmining (BuCoR-E): Een nieuwe methode die gebruik maakt van programmeer-afhankelijkheidsanalyse om transformatiepatronen te extraheren, context-matching uit te voeren en kandidaat-oplossingen te rangschikken.
Uitgebreide Regelset (BuCoR-R): Implementatie van 16 regels die verder gaan dan alleen symboolhernoeming, inclusief conflicten door hiërarchieveranderingen en entiteitstoevoeging/verwijdering.
Dataset en Evaluatie: Een systematische evaluatie op een dataset van 88 real-world build-conflicten uit 30 open-source Java-projecten, verdeeld over 21 verschillende conflicttypen.

Resultaten

De tool werd getest op 88 build-conflicten:

Dekking (Coverage): BuCoR genereerde voor 65 van de 88 conflicten (74%) ten minste één oplossing.
- BuCoR-E alleen: 28 oplossingen (32%).
- BuCoR-R alleen: 51 oplossingen (58%).
- Dit toont aan dat de twee strategieën elkaar aanvullen.
Nauwkeurigheid (Accuracy): Van de 79 gegenereerde oplossingen waren er 41 correct (52%).
- BuCoR-E had een nauwkeurigheid van 75% (21/28).
- BuCoR-R had een nauwkeurigheid van 39% (20/51).
Conclusie over strategieën: BuCoR-E is nauwkeuriger en beter in het oplossen van ongebruikelijke conflicten door projectspecifieke patronen na te bootsen. BuCoR-R heeft een hogere dekking en lost standaardconflicten sneller op, maar is minder nauwkeurig bij complexe scenario's.

Betekenis en Toekomstperspectief

Dit onderzoek toont aan dat een hybride aanpak effectief is voor het automatiseren van het oplossen van complexe build-conflicten, een gebied waar tot nu toe weinig geautomatiseerde ondersteuning voor bestond.

Innovatie: BuCoR gaat verder dan simpele tekstuele merges of symboolhernoeming door semantische consistentie te garanderen via dependency-analyse.
Toekomst: De auteurs plannen om de regelset van BuCoR-R uit te breiden en de mining-capaciteit van BuCoR-E te verbeteren, vooral in gevallen waar geen lokale voorbeelden in de branches beschikbaar zijn.
Impact: De tool en de dataset zijn open-source beschikbaar gesteld, wat de basis legt voor verdere ontwikkeling van intelligente merge-tools.

Samenvattend biedt BuCoR een robuust kader om de productiviteit van ontwikkelaars te verhogen en de softwarekwaliteit te verbeteren door automatische, contextbewuste oplossingen voor een breed scala aan build-fouten tijdens het merge-proces.