mergiraf — ett AST-orienterat verktyg för trevägssammanslagning i Git

Release of the mergiraf 0.4 project has been published, which develops a driver for Git with the implementation of three-way merging capabilities. Mergiraf supports resolving various types of merge conflicts and can be used for different programming languages and file formats. It can be called separately to handle conflicts arising from the standard Git workflow, or it can replace the merge handler in Git to extend the capabilities of commands such as merge, revert, rebase, and cherry-pick. The code is distributed under the GPLv3 license. The new version adds support for Python, TOML, Scala, and Typescript, as well as performance optimizations.

Below is a detailed description of the problems addressed by mergiraf:

Software is a striking example of an extremely complex system. Complex systems share one common property — they are COMPLEX — and you cannot expect the necessary complex behavior to emerge by itself, randomly. Instead, these systems evolve over time, step by step, and each mutation is carefully verified at each stage. Achieving this requires a well-defined structure and appropriate tools. The evolution of any complex system can be visualized as a directed tree, where the root represents an empty set of functions, and every node — except for the root — is the result of applying a mutation to its parent.

In the context of products, each node is called a 'version,' representing a specific set of features and anti-features. Any change to this set is considered a mutation, forming an edge in our directed acyclic graph. These features are inherently abstract; they do not directly reflect how physical systems operate, but rather demonstrate how rational agents perceive the utility of these systems. To translate ideas into real-world implementations, it is necessary to roll up your sleeves and dive into *sufficiently* low-level details, in a language that can express and explain exactly how everything works. In software development, these low-level details are typically represented by source code.

För att gradvis föra koden till ett tillstånd som uppvisar det önskade beteendet och dokumentera hur de nådde dit presenterar programmerarna sitt arbete i termer av snapshots och changesets. En snapshot representerar ett visst tillstånd av produkten med alla detaljer på låg nivå, medan en changeset betecknar övergången mellan snapshots. Vanligtvis genereras snapshots av enskilda changesets från deras föräldrar, så dessa snapshots märks nästan alltid med det som changesets som skapade dem gör, varför dessa termer ofta används omväxlande.

Ibland finns det snapshots som skapats från flera övergångar – sammanslagningar av commits. Dessa är svåra att arbeta med, så de undviks vanligtvis. Moderna versionshanteringssystem med öppen källkod, såsom Git, tillhandahåller ganska grundläggande funktioner för att hantera utvecklingsarbetsflöden. De tillåter utvecklare att organisera snapshots i riktade acykliska grafer, annotera dem med kommentarer och vid behov ändra deras ordning.

Denna funktionalitet gör det möjligt för utvecklare att skriva en semantiskt meningsfull historia för projektet, vilket är avgörande för felsökning och att besvara frågor som "Varför introducerades denna låg-nivå detalj (t.ex. en variabel)?", "Hur mycket procent av projektet bidrog jag till?", "Vem blev hackad med inbäddningar och när?", "Vilken låg-nivå ändring bröt denna funktion (även om det egentligen inte borde ha, vi har kollat allt!?)"

Versionshanterssystem kompletterar denna koncept med grenen - ett låg nivå begrepp som helt enkelt betyder en kontinuerlig del av projektets lågnivåhistoria, meningsfullt för utvecklaren. Grenar används vanligtvis för specifika funktionaliteter, och det kan ibland skapas flera grenar för olika kandidater för implementering av samma funktion. Genom att använda arbetsflöden med grening (som faktiskt är mainstream och standard inom utveckling, används överallt och allmänt), kan varje utvecklare effektivt hantera många konflikterande projektgrenar, var och en varierande i beredskapsgrad eller kvalitet. Detta gör det möjligt för utvecklare att kombinera resultaten av sina och andras arbeten utan att behöva skriva om allt manuellt varje gång.

Vanligtvis skapas en huvudgren som representerar den 'officiella' produkten, från vilken sidogrener grenas för varje funktion, som regelbundet (idealiskt - efter varje commit) synkroniseras med huvudgrenen, vilket gör att utvecklarna kan arbeta med den mest aktuella versionen av produkten och samtidigt implementera funktioner som de för tillfället utvecklar, och upptäcker problem som uppstår från andra utvecklares åtgärder så tidigt som möjligt.

Vid försök att kombinera funktionerna hos olika snapshotar (vilket bara är en fråga om att hitta en gemensam förfader och tillämpa changesets som skapas, sekventiellt ovanpå en annan, kallas denna åtgärd rebase, sammanslagning är nästan som rebase, bara strukturerar commit-grafen annorlunda vilket gör den svår att manipulera, så man undviker sammanslagningar till förmån för rebases) uppstår problem. Moderna versionshanteringssystem (VCS) använder interna algoritmer för att slå samman förändringar, som helt enkelt bryter ner filer i individuella rader, betraktar varje rad som ett tecken och filerna som deras sekvenser, och tillämpar algoritmer för att sammanfoga dem, som har sitt ursprung i bioinformatik.

Tyvärr har denna rad-för-rad-representation av koden inget att göra med dess innehåll. Dess enda fördel är att den är enkel och universell. Diskrepanser leder till konflikter, vilket ständigt skapar huvudvärk för utvecklare. Att lösa konflikter kräver att utvecklaren noggrant studerar båda versionerna av koden, inte bara de delar som markeras som "ändrade" eller "konflikterande" av den rad-för-rad-jämförelsealgoritmen, utan möjligtvis hela projektet.

Utvecklaren måste förstå ändringarna, manuellt skriva den sammanslagna koden och åtgärda alla avvikelser. Problemen blir fler när radverktyget felaktigt identifierar ändringar, vilket ofta händer vid stora förändringar, inklusive triviala som omformatering av koden. Om efterföljande ändringar inte kan tillämpas på den manuellt sammanslagna koden förvandlas situationen till en total mardröm. Trots de skrämmande fallen fungerar rad-algoritmen i de flesta fall, särskilt om utvecklarna aktivt försöker att inte skapa problem för den. Ett sätt att minimera sådana problem är att ställa krav på att källkoder bearbetas med kanonikaliseringsverktyg som black.

Självklart är den rätta lösningen på skrämmande fall (och faktiskt inte bara för dem, rad-algoritmen är en heuristik, och den kan enkelt leda till icke-fungerande kod, till exempel om en utvecklare har döpt om en variabel medan en annan under tiden har skrivit en bit ny kod som använder den variabeln, så kommer det inte att bli någon sammanslagnings-/omloceringkonflikt, men resultatet blir icke-fungerande) att använda en korrekt intern modell.

Trots att forskning inom detta område har pågått i nästan 30 år, och lett till skapandet av flera proprietära kommersiella produkter, har denna forskning fram till nyligen inte omvandlats till praktiskt tillämpliga produkter med öppen källkod. De flesta lösningar med öppen källkod började utvecklas i början av 2010-talet och var främst inriktade på programmeringsspråket Java.

Den mest framstående fria implementationen från den perioden, GumTree, skapades av en forskare med akademisk bakgrund, är skriven i Java, har sin egen abstrakta interna representation som föregår treesitter, och har backends både baserade på treesitter och andra verktyg för att parsa källkod till abstrakta representationer. Detta system kan bara generera (i form av en textlogg över händelser, det finns också ett API som kan enkelt anropas från vilket programmeringsspråk som helst som har bindningar till Java) och visualisera förändringar. Däremot är det odugligt för att slå samman förändringar eller för att visa de genererade diff-filerna från början (även om det troligtvis är möjligt att ladda upp diffs via API).

En yngre och mer praktiskt användbar implementation av difftastic är skriven i Rust, baserad på treesitter, och fokuserar på att generera markerade diffs i konsolen. Detta system är också inriktat på att visualisera diffs och syftar överhuvudtaget inte till att slå samman förändringar eller tillämpa patchar.

Nyligen har projektet mergiraf dykt upp och utvecklas aktivt. Detta verktyg, skrivet i Rust (tar upp 21 MiB!), är också baserat på treesitter, som redan har blivit en standard för parsers av kontextfria grammatik i utvecklingsverktyg, liksom LLVM har blivit för optimering av lågnivå instruktionrepresentationer. Till skillnad från konkurrenterna erbjuder mergiraf funktioner för automatisk konfliktlösning vid sammanslagningar istället för att generera diffs. Under huven använder mergiraf för att generera patchar en implementation av algoritmen som används i GumTree, och för att tillämpa — en implementation av algoritmen som används i spork, anpassad för treesitter-strukturer.

Tyvärr är serialisering av patchar till filer som senare kan tillämpas inte implementerad (men det är fullt möjligt att det kan genomföras genom att parsa loggar över händelser genererade av GumTree). Ett annat lovande sätt att använda skillnader kan vara att tillämpa skillnader inte genom patchar utan genom funktionaliteten för refaktorering av LSP-servrar, vilket kan hjälpa till med att upptäcka konflikter på projektens nivå. Visualisering stöds endast för konflikter.

Exempel på arbete: allmän förfader «base.py» (indrag med tabbar, överflödig rad i början) foo = 1 def main(): print(foo + 2 + 3) «a.py» (indrag fortfarande med tabbar, 2 överflödiga rader i början istället för en, för felsökningsutskrift används biblioteket icecream, klass «baz» tillagd: from icecream import ic foo = 1 def main(): ic(foo + 2 + 3) class baz: def __init__(self): «»»baz»»» «b.py» (variabeln «foo» omdöpt till «bar», bearbetad med «black» efter ändringar, som ett resultat är indrag med mellanslag och överflödiga rader borttagna): bar = 1 def main(): print(bar + 2 + 3) Anrop .\/mergiraf merge .\/base.py .\/a.py .\/b.py -x a.py -y b.py -s base.py -o .\/res.py ger följande resultat from icecream import ic bar = 1 def main(): ic(bar + 2 + 3) class baz: def __init__(self): «»»baz»»» (för felsökningsutskrift används biblioteket «icecream», variabeln «foo» har omdöpts till «bar», bearbetad med «black» efter ändringar, vilket resulterar i att indrag är med mellanslag och överflödiga rader har tagits bort, en blandning av tabbar och mellanslag för indrag, men i godkänt skick).

Här syns också verktygets brist. Dokumentstil konfigureras vanligtvis i filer med «.editorconfig», och globala stiländringar, som att byta tabbar till mellanslag och anta black-stil som det gjordes i «b.py», åtföljs vanligtvis av ändringar i «.editorconfig». Därför bör verktyget för att korrekt tillämpa sådana ändringar ha ett koncept för global stil «per standard» och kunna hämta inställningar från «.editorconfig».

Källa: opennet.ru