Diff

Den här artikeln handlar om filjämförelseverktyget. För versionsjämförelser av redigeringar på wikin, se  Wikipedia:Versionsjämförelse .

I datoranvändning är  diff ett filjämförelseverktyg som visar skillnaden mellan två filer. Detta program skriver ut rad för rad ändringarna som gjorts i filen (för textfiler). Moderna implementeringar stöder även binär . Utdata från verktyget kallas "diff", eller, vanligare, en patch eftersom den kan appliceras med patchprogrammet . Utdata från andra filjämförelseverktyg kallas också ofta för "diff".

Historik

Diff-verktyget utvecklades i början av 1970-talet för Unix -operativsystemet , som var ett arbete av AT&T Bell Labs , i Murray Hill, New Jersey. Den slutliga versionen, distribuerad med Unix 5 1974, skrevs helt av Douglas McIlroy .

McIlroys arbete föregicks och påverkades av Steve Johnsons GECOS-jämförelseprogram och Mike Lesks bevisprogram. Bevis har också sitt ursprung i Unix och gjorde, liksom diff, rad för rad ändringar och använde till och med vinkelparenteser (">" och "<") för att representera radinfogningar och raderingar i programutdata. Heuristiken som användes i dessa tidiga tillämpningar ansågs dock vara opålitliga. Jämförelseverktygets potentiella användbarhet provocerade McIlroy att undersöka och utveckla ett mer robust verktyg som kunde användas i en mängd olika uppgifter men som skulle fungera väl inom bearbetnings- och storleksbegränsningarna för PDP-11-hårdvaran. Hans inställning till problemet var resultatet av samarbete med personer på Bell Labs, inklusive Alfred Aho, Elliot Pinson, Jeffrey Ullman och Harold S. Stone.

Algoritm

Driften av diff bygger på att hitta den längsta gemensamma subsekvensen ( LCS-problem) .  Till exempel finns det två sekvenser av element:

       abcdfghjqz

       abcdefgijkrxyz

och du måste hitta den längsta sekvensen av element som presenteras i båda sekvenserna i samma ordning. Detta innebär att det är nödvändigt att hitta en ny sekvens, som kan erhållas från den första sekvensen genom att ta bort vissa element eller från den andra sekvensen genom att ta bort andra element. I det här fallet kommer sekvensen att vara

       abcdfgjz

Efter att ha fått den största vanliga sekvensen är det bara ett litet steg kvar innan man får en diff-liknande utdata:

       ehikqrxy
       + - + + - + + +

Användning

diff anropas från kommandoraden med namnen på två filer som argument: diff original new . Utdata från kommandot är de ändringar som måste göras i källfilens original för att få den nya filen ny. Om original och ny är kataloger, kommer diff automatiskt att tillämpas på varje fil som finns i båda katalogerna. Alla exempel i den här artikeln använder följande två filer, original och ny :

original:

Denna del av dokumentet
förblev oförändrad
från version till version. Om en
det är ingen förändring i henne
ska inte visas.
Annars hjälper det inte
slutsatsen av det optimala 
produceras
ändringar.

Denna paragraf innehåller
föråldrad text.
Det kommer att tas bort
snart.

Det här dokumentet
behöver vara
stavnings kontroll.
Å andra sidan, felet
med ett ord - inte världens ände.
Resten av stycket
kräver inga ändringar.
Ny text kan
lägg till i slutet av dokumentet.

ny:

Detta är en viktig anmärkning!
Därför borde det
vara lokaliserad
i början av detta
dokumentera!

Denna del av dokumentet
förblev oförändrad
från version till version. Om en
det är ingen förändring i henne
ska inte visas.
Annars hjälper det inte
slutsatsen av det optimala 
mängden information.
 
Det här dokumentet
behöver vara
stavnings kontroll.
Å andra sidan, felet
med ett ord - inte världens ände.
Resten av stycket
kräver inga ändringar.
Ny text kan
lägg till i slutet av dokumentet.

Denna paragraf innehåller
viktiga tillägg
för detta dokument.

Kommandot diff original new producerar följande normala diff-utgång :

0a1.6
 > Detta är en viktig anmärkning!
 > Därför borde det
 > vara lokaliserad
 > i början av detta
 > dokument!
 >
 8.14c14
 < volym producerad
 < ändras.
 <
 < Denna paragraf innehåller
 < föråldrad text.
 < Det kommer att raderas
 < inom en snar framtid.
 ---
 > mängd information.
 17c17
 < måste göras
 ---
 > måste göras
 24a25.28
 >
 > Denna paragraf innehåller
 > viktiga tillägg
 > för detta dokument.

I detta traditionella utdataformat betyder a tillagd (från engelskan  add ), d betyder raderad , c betyder ändrad . Bokstäverna a, d eller c föregås av källfilens radnummer, följt av målfilens radnummer. Varje rad som har lagts till, tagits bort eller ändrats föregås av vinkelparenteser .

Som standard anges inte radnummer som är gemensamma för käll- och målfiler. Rader som flyttas visas som tillagda på sin nya plats och tas bort från sin tidigare plats.

Alternativ

De flesta olika implementeringar har varit oförändrade utåt sedan 1975. Ändringar inkluderar förbättringar av huvudalgoritmen, tillägg av nya kommandonycklar, nya utdataformat. Den grundläggande algoritmen beskrivs i An O(ND) Difference Algorithm and its Variations av Eugene W. Myers och A File Comparison Program av Webb Miller och Myers . Algoritmen upptäcktes oberoende och beskrevs i Algorithms for Approximate String Matching av E. Ukkonen . De första versionerna av diff-programmet utformades för att jämföra rader med textfiler med hjälp av tecknet newline som radavgränsare. På 1980-talet ledde stöd för binära filer till förändringar i hur programmet fungerade och implementerades.

Redigera skript

Redigera skript kan genereras av moderna versioner av diff med alternativet -e . Resultatet för vårt exempel kommer att se ut så här:

24a

Denna paragraf innehåller
viktiga tillägg
för detta dokument.
.
17c
behöver vara
.
8,14c
mängden information.
.
0a
Detta är en viktig anmärkning!
Därför borde det
vara lokaliserad
i början av detta
dokumentera!

.

För att använda det resulterande skriptet för att konvertera den ursprungliga filen till det nya filtillståndet måste vi lägga till två rader i slutet av skriptet: en innehåller kommandot w (skriv), den andra - q (avslut). Till exempel så . Här har vi döpt diff-filen till mydiff . Omvandlingen kommer att ske när vi ger kommandot . printf "w\nq\n" >> mydiffed -s original < mydiff

Kontextformat

BSD version 2.8 (släppt i juli 1981) introducerade kontextformatet ( -c ) och möjligheten att rekursivt gå igenom filsystemets katalogträd ( -r ).

I kontextformat visas ändrade linjer tillsammans med opåverkade linjer före och efter det ändrade fragmentet. Att infoga valfritt antal opåverkade rader ger kontext för patchen. Kontexten , som består av opåverkade rader, fungerar som en referens för att bestämma platsen för fragmentet som modifieras i målfilen, även om radnumren för de modifierade raderna i käll- och målfilerna inte stämmer överens. Kontextformatet är mer läsbart för människor och mer tillförlitligt när en patch appliceras, och utdata tas som indata till patchprogrammet .

Antalet opåverkade rader före och efter det modifierade fragmentet kan ställas in av användaren och till och med vara noll, men är vanligtvis tre rader som standard. Om kontexten för de opåverkade linjerna i ett fragment överlappar ett intilliggande fragment, kommer diff att undvika att kopiera de opåverkade linjerna och slå samman de intilliggande fragmenten till ett.

Utdata från det nya originalkommandot diff -c är:

*** /sökväg/till/original ''tidsstämpel''
 --- /sökväg/till/ny ''tidsstämpel''
***************
*** 1,3 ****
--- 1,9 ---- 
+ Detta är en viktig anmärkning! 
+ Så det borde 
+ finnas 
+ i början av detta 
+ dokument! 
+
  Denna del av dokumentet
  förblev oförändrad
  från version till version. Om en
***************
*** 5,20 ****
  ska inte visas.
  Annars hjälper det inte
  slutsatsen av det optimala
! producerad volym 
! ändringar. 
! 
! Denna paragraf innehåller 
! föråldrad text. 
! Han kommer att tas bort 
! snart.
  
  Det här dokumentet
! behöver vara
  stavnings kontroll.
  Å andra sidan, felet
  med ett ord - inte världens ände.
--- 11.20 ----
  ska inte visas.
  Annars hjälper det inte
  slutsatsen av det optimala
! mängden information.
  
  Det här dokumentet
! behöver vara
  stavnings kontroll.
  Å andra sidan, felet
  med ett ord - inte världens ände.
***************
*** 22,24 ****
--- 22.28 ----
  kräver inga ändringar.
  Ny text kan
  lägg till i slutet av dokumentet.
++ 
Detta stycke innehåller 
viktiga tillägg 
för detta dokument.

Universellt format

Det universella formatet (eller unidiff ) innehåller de tekniska förbättringar som gjorts av kontextformatet, men gör skillnaden mellan gammal och ny text på ett mer kortfattat sätt. Det universella formatet anropas vanligtvis med kommandoradsalternativet " -u " . Denna utgång används ofta som en patch för program. Många projekt kräver specifikt att "diffs" skickas till dem i ett generiskt format, vilket gör det generiska formatet till det vanligaste utbytet mellan mjukvaruutvecklare.

Universella kontextdifferenser utvecklades först av Wayne Davison i augusti 1990 ( unidiff visas i kapitel 14 i comp.sources.misc). Stallman lade till stöd för universellt format till GNU -projektets diff-verktyg en månad senare, och denna funktionalitet debuterade i GNU diff 1.15, släppt i januari 1991. GNU diff har sedan dess generaliserat kontextformatet för att tillåta godtycklig formatering av diffar.

En fil i generiskt format börjar med samma två rader som kontextformatet, förutom att originalfilen börjar med " --- " och den nya filen börjar med " +++ ". De följs av ett eller flera ändrade utdrag som innehåller rad för rad ändringar av filerna. Rader utan ändringar börjar med ett mellanslag, tillagda rader börjar med ett plustecken, raderade rader börjar med ett minustecken.

Fragmentet börjar med intervallinformation och följs omedelbart av tillagda rader, raderade rader och valfritt antal kontextrader. Områdesinformationen omges av dubbla @ -tecken och sammanfogas på en enda rad, i motsats till två linjer i ( kontextformat ). Områdesinformation har följande format:

@@ -l,s +l,s @@ valfri avsnittsrubrik

Räckviddsinformation består av två delar. Delen för den ursprungliga filen börjar med ett minus och delen för den nya filen börjar med ett plus. Varje del har formatet l, s , där l  är numret på raden vi börjar med, och s  är antalet rader som har ändrats i det aktuella fragmentet för var och en av filerna (det vill säga i första fallet är detta summan av utdataraderna som börjar med ett mellanslag och med ett minus, i det andra - rader som börjar med ett mellanslag och med ett plus). I många versioner av GNU diff kan kommatecken och efterföljande s utelämnas från varje område. I det här fallet är s standard till 1. Observera att det enda användbara värdet för endast l  är radnumret för det första intervallet, de andra värdena kan beräknas från diff.

Områdesfragmentet för originalfilen måste vara summan av alla sammanhang och raderade (inklusive ändrade) rader i fragmentet. Områdesfragmentet för den nya filen måste inkludera summan av alla sammanhang och tillagda (inklusive modifierade) rader i fragmentet.

Ett intervallfragment kan föregås av rubriken för den sektion eller funktion som fragmentet är en del av. Detta är vanligtvis användbart för att läsa själva utdraget. När du skapar en diff med GNU, bestäms diff-huvudet av det reguljära uttrycket .

Om en rad har ändrats visas den som både borttagen och tillagd. Eftersom de raderade och tillagda raderna finns i intilliggande fragment, visas dessa rader bredvid varandra . Till exempel:

-kolla detta dokument. På
+kolla detta dokument. På

Kommandot diff -u original new kommer att producera följande utdata:

--- /path/to/original ''timestamp'' 
+++ /path/to/new ''timestamp'' 
@@ -1.3 +1.9 @@ 
+Detta är en viktig anmärkning! 
+Därför bör det 
+finnas 
i +början av detta 
+dokument! 
+
 Denna del av dokumentet
 förblev oförändrad
 från version till version. Om en
@@ -5,16 +11,10 @@
 ska inte visas.
 Annars hjälper det inte
 slutsatsen av det optimala
- volymen av 
gjorda ändringar. 
- 
-Det här stycket innehåller 
föråldrad text. 
-Det kommer att tas bort 
-inom en snar framtid. 
+ mängd information.
 
 Det här dokumentet
- måste göras 
+ måste göras
 stavnings kontroll.
 Å andra sidan, felet
 med ett ord - inte världens ände.
@@ -22,3 +22,7 @@
 kräver inga ändringar.
 Ny text kan
 lägg till i slutet av dokumentet.
++ 
Detta stycke innehåller 
+viktiga tillägg 
+för detta dokument.

Observera att flikar används för att korrekt separera filnamn från tidsstämplar. Detta är osynligt på skärmen och kan gå förlorat när du kopierar/klistrar in från konsolen.

Det finns flera modifieringar och tillägg till olika format som olika program använder och förstår. Till exempel anger vissa versionskontrollsystem , som Subversion , versionsnumret, "arbetsexemplar" eller någon annan kommentar utöver tidsstämpeln i diffens rubrik.

Vissa program låter dig skapa diffar för flera olika filer och slå samman dem till en, med hjälp av en rubrik för varje ändrad fil, som kan se ut ungefär så här:

Index: sökväg/till/fil.cpp

Den speciella typen av filer som inte slutar med en ny rad stöds inte. Varken unidiff-verktyget eller POSIX diff-standarden anger hur sådana filer hanteras (i själva verket är filer av den här typen inte "text" i POSIX -definitionen ).

Patchprogrammet vet ingenting om implementeringen av den speciella utmatningen av diff-kommandot.

Se även

• cmp
• komm
• diff3
• Kompare
• kdiff3 Arkiverad 29 december 2020 på Wayback Machine
• smälta samman
• Jämför Microsoft-filer
• rsync
• tkdiff
• wdiff  - omslag för diff för att jämföra filer med ord
• WinMerge
• xdelta - diff för binära filer
• deltakodning
• Största vanliga följden
• Levenshtein avstånd
• Versionskontrollsystem

Länkar

• GNU-diffutils-paketet Arkiverat 11 juni 2007 på Wayback Machine inkluderar diff. Distribueras under GNU General Public License .
• diffutils för Win32 Arkiverad 12 juni 2007 på Wayback Machine  - en del av GnuWin32
• Onlinegränssnitt till diff Arkiverad 14 september 2017 på Wayback Machine  (ryska)
• C# diff-algoritm Arkiverad 15 juni 2007 på Wayback Machine  — Källkod för diff-algoritmen och dess C# -varianter