rozdíl - diff

Tento článek je o obslužném programu. Obecné téma porovnávání souborů najdete v tématu Porovnání souborů . Rozdíly ve Wikipedii najdete v nápovědě: diff . Pro jiná použití, viz DIFF .
rozdíl
Původní autoři Douglas McIlroy
( AT&T Bell Laboratories )
Vývojáři Různí open-source a komerční vývojáři
První vydání Červen 1974 ; Před 47 lety ( 1974-06 )
Operační systém Unix , podobný Unixu , V , Plan 9 , Inferno
Plošina Cross-platform
Typ Příkaz

V práci na počítači , nástroj diff je porovnání dat nástroj, který vypočítává a zobrazuje rozdíly mezi obsahy souborů. Na rozdíl od pojmů upravovat vzdálenost používaných pro jiné účely je diff spíše orientovaný na řádky než na znaky, ale je to jako Levenshteinova vzdálenost v tom, že se pokouší určit nejmenší sadu vymazání a vložení, aby vytvořil jeden soubor z druhého. Tento nástroj zobrazuje změny v jednom z několika standardních formátů, takže lidé nebo počítače mohou změny analyzovat a použít je k opravě .

Rozdíl se obvykle používá k zobrazení změn mezi dvěma verzemi stejného souboru. Moderní implementace také podporují binární soubory . Výstup se nazývá „diff“ nebo oprava , protože výstup lze použít s programovou záplatou Unixu . Výstup podobných nástrojů pro porovnávání souborů se také nazývá „rozdíl“; stejně jako použití slova „ grep “ pro popis aktu vyhledávání, slovo diff se stalo obecným termínem pro výpočet rozdílu dat a jeho výsledků. Standard POSIX určuje chování obslužných programů „diff“ a „patch“ a jejich formáty souborů.

Dějiny

diff byl vyvinut na začátku 70. let minulého století na operačním systému Unix, který vzešel z Bell Labs v Murray Hill v New Jersey. První vydanou verzi dodanou s 5. edicí Unixu v roce 1974 napsali Douglas McIlroy a James Hunt . Tento výzkum byl publikován v dokumentu z roku 1976, který byl napsán společně s Jamesem W. Huntem, který vyvinul počáteční prototyp diffu . Algoritmus popsaný v tomto článku se stal známým jako Hunt – Szymanskiho algoritmus .

McIlroy práce předcházela a ovlivnil Steve Johnson 'srovnávacího programu je na GECOS a Mike Lesk je důkaz programu. Důkaz také pochází z Unixu a stejně jako diff produkuje změny řádek po řádku a dokonce používá úhlové závorky (">" a "<") pro prezentaci vkládání a odstraňování řádků ve výstupu programu. Tyto heuristiky používané v těchto raných aplikacích však byly považovány za nespolehlivé. Potenciální užitečnost nástroje diff vyprovokovala McIlroy k výzkumu a návrhu robustnějšího nástroje, který by mohl být použit v různých úlohách, ale dobře si vedl v omezení zpracování a velikosti hardwaru PDP-11 . Jeho přístup k problému vyplynul ze spolupráce také s jednotlivci z Bell Labs, včetně Alfreda Aho , Elliota Pinsona, Jeffreyho Ullmana a Harolda S. Stonea.

V kontextu Unixu se použití poskytovaného editoru řádků ed liší od přirozené schopnosti vytvářet strojově použitelné „editační skripty“. Tyto editační skripty, pokud jsou uloženy do souboru, mohou být spolu s původním souborem rekonstituovány ed do upraveného souboru jako celek. Tím se výrazně zmenšilo sekundární úložiště nutné k udržování více verzí souboru. McIlroy uvažoval o napsání postprocesoru pro diff, kde by bylo možné navrhnout a implementovat různé výstupní formáty, ale shledal, že je snazší a jednodušší mít diff zodpovědný za generování syntaxe a vstupu v obráceném pořadí přijímaného příkazem ed .

Koncem roku 1984 vytvořil Larry Wall samostatný nástroj, patch , který uvolnil svůj zdrojový kód na diskusních skupinách mod.sources a net.sources . Tento program zobecnil a rozšířil možnost upravovat soubory s výstupem z diffu .

Režimy v Emacsu také umožňují interaktivně převádět formát záplat a dokonce upravovat záplaty.

V diff ‚s první roky, nejčastější použití součástí porovnávání změny ve zdroji softwarového kódu a značek pro technickou dokumentaci, ověřuje programu ladění výkonu, porovnání filesystem výpisy a analyzování počítač assembleru. Výstup cílený na ed byl motivován k zajištění komprese pro posloupnost úprav provedených v souboru. Systém řízení zdrojového kódu (SCCS) a jeho schopnost archivovat revize se objevily na konci 70. let minulého století jako důsledek ukládání skriptů úprav z diff .

Algoritmus

Operace diffu je založena na řešení nejdelšího společného problému s podsekvencí .

V tomto problému jsou uvedeny dvě sekvence položek: 

a b c d f g h j q z

a b c d e f g i j k r x y z

a chceme najít nejdelší sekvenci položek, která je přítomna v obou původních sekvencích ve stejném pořadí. To znamená, že chceme najít novou sekvenci, kterou lze získat z první původní sekvence odstraněním některých položek a z druhé původní sekvence odstraněním dalších položek. Také chceme, aby tato sekvence byla co nejdelší. V tomto případě je 

a b c d  f  g  j  z

Z nejdelší společné subsekvence je jen malý krok k získání výstupu podobného diffu : pokud položka v subsekvenci chybí, ale je přítomna v první původní sekvenci, musela být odstraněna (jak je uvedeno níže značkami ' -' ). Pokud v podsekvenci chybí, ale je přítomna ve druhé původní sekvenci, musí být vložena (jak je označeno značkami „+“). 

e   h i   q   k r x y
+   - +   -   + + + +

Používání

diffPříkaz je vyvolán z příkazového řádku, prochází jí názvy dvou souborů: . Výstup příkazu představuje změny potřebné k transformaci původního souboru na nový soubor. diff original new

Pokud jsou původní a nové adresáře, pak bude diff spuštěn pro každý soubor, který existuje v obou adresářích. Možnost -r,, bude rekurzivně sestupovat ze všech odpovídajících podadresářů pro porovnávání souborů mezi adresáři.

Kterýkoli z příkladů v článku používá následující dva soubory, původní a nový :

V tomto tradičním výstupním formátu Aznamená přidané ,dpro smazané aCpro změněné . Čísla řádků původního souboru se zobrazí dříveA/d/Ca ty z nového souboru se zobrazí po. Méně než a větší než příznaky (na začátku linky, které jsou přidány, odstraněny nebo změněny) indikují, který soubor řádky se zobrazí v. Adiční řádky jsou přidány do původního souboru se objeví v novém souboru. Vymazávací řádky jsou odstraněny z původního souboru, aby v novém souboru chyběly.

Ve výchozím nastavení se nezobrazují řádky společné pro oba soubory. Řádky, které se přesunuly, se zobrazí jako přidané v novém umístění a odstraněné ze starého umístění. Některé nástroje diffu však zvýrazňují posunuté čáry.

Výstup variace

Upravit skript

Script ed lze stále generovány moderních verzích diff s -evolbou. Výsledný editační skript pro tento příklad je následující: 

24a

This paragraph contains
important new additions
to this document.
.
17c
check this document. On
.
11,15d
0a
This is an important
notice! It should
therefore be located at
the beginning of this
document!

.

Abychom mohli transformovat obsah původního souboru na obsah nového souboru pomocí ed , měli bychom k tomuto rozdílovému souboru připojit dva řádky, jeden řádek obsahující wpříkaz (write) a jeden obsahující qpříkaz (quit) (např. ). Zde jsme dali souboru diff název mydiff a transformace pak proběhne, když spustíme . printf "w\nq\n" >> mydiffed -s original < mydiff

Kontextový formát

Berkeley distribuce Unixu dělal bod z přidání formát kontext ( -c) a schopnost recurse na souborového adresářové struktury ( -r), přidejte tyto vlastnosti u 2,8 BSD, povolený v červenci 1981. kontextu formátu diff představila v Berkeley pomohl s rozvozem opravy pro zdrojový kód, které mohly být změněny minimálně.

V kontextovém formátu jsou všechny změněné řádky zobrazeny vedle nezměněných řádků před a za. Zahrnutí libovolného počtu nezměněných řádků poskytuje kontext opravy. Kontext skládá z linek, které se nezměnily mezi dvěma soubory a slouží jako referenční lokalizovat místo řady v upraveném souboru a najít zamýšlené umístění pro změnu mají být použity bez ohledu na to, zda se čísla řádku stále odpovídají. Kontextový formát přináší větší čitelnost pro lidi a spolehlivost při aplikaci patche a výstup, který je přijímán jako vstup do programu patchů . Toto inteligentní chování není možné s tradičním výstupem diff.

Počet nezměněných řádků uvedených výše a níže o změně kusu může být definován uživatelem, dokonce nulovou, ale tři řádky je obvykle výchozí. Pokud se kontext nezměněných čar v kusu překrývá se sousedním kusem, pak diff zabrání duplikaci nezměněných čar a sloučí hunky do jednoho kusu.

A " !" představuje změnu mezi řádky, které odpovídají dvěma souborům. A " +" představuje přidání řádku, zatímco prázdné místo představuje nezměněný řádek. Na začátku opravy jsou informace o souboru, včetně úplné cesty a časového razítka odděleného znakem tabulátoru. Na začátku každého kusu jsou čísla řádků, která platí pro odpovídající změnu v souborech. Číselný rozsah mezi sadami tří hvězdiček platí pro původní soubor, zatímco sady tří pomlček platí pro nový soubor. Rozsahy bloků určují počáteční a koncová čísla řádků v příslušném souboru.

Příkaz diff -c original newvytvoří následující výstup: 

*** /path/to/original	timestamp
--- /path/to/new	timestamp
***************
*** 1,3 ****
--- 1,9 ----
+ This is an important
+ notice! It should
+ therefore be located at
+ the beginning of this
+ document!
+
  This part of the
  document has stayed the
  same from version to
***************
*** 8,20 ****
  compress the size of the
  changes.

- This paragraph contains
- text that is outdated.
- It will be deleted in the
- near future.

  It is important to spell
! check this dokument. On
  the other hand, a
  misspelled word isn't
  the end of the world.
--- 14,21 ----
  compress the size of the
  changes.

  It is important to spell
! check this document. On
  the other hand, a
  misspelled word isn't
  the end of the world.
***************
*** 22,24 ****
--- 23,29 ----
  this paragraph needs to
  be changed. Things can
  be added after it.
+
+ This paragraph contains
+ important new additions
+ to this document.

Poznámka: Zde je výstup rozdílu zobrazen pomocí barev, které usnadňují jeho čtení. Obslužný program diff nevytváří barevný výstup; jeho výstupem je prostý text . Mnoho nástrojů však může zobrazit výstup pomocí barev pomocí zvýraznění syntaxe .

Jednotný formát

Sjednocen formát (nebo unidiff ) dědí technické zhodnocení provedené formátu kontextu, ale produkuje menší diferenciál s starý a nový text prezentován v bezprostředním sousedství. Sjednocený formát je obvykle vyvolán pomocí možnosti příkazového řádku " -u" . Tento výstup se často používá jako vstup do programu patch . Mnoho projektů specificky požaduje, aby „diffy“ byly předkládány ve sjednoceném formátu, což činí z unifikovaného formátu diff nejběžnější formát pro výměnu mezi vývojáři softwaru.

Sjednocené kontextové rozdíly byly původně vyvinuty Waynem Davisonem v srpnu 1990 (v unidiff, který se objevil ve svazku 14 comp.sources.misc). Richard Stallman přidal podporu unifikovaného diffu k nástroji diff GNU Project o měsíc později a tato funkce debutovala v GNU diff 1.15, vydaném v lednu 1991. GNU diff od té doby zobecnil kontextový formát, aby umožnil libovolné formátování diffů.

Formát začíná stejným dvouřádkovým záhlavím jako kontextový formát, kromě toho, že původnímu souboru předchází „---"a novému souboru předchází"+++". Následuje jeden nebo více změnových souborů, které obsahují řádkové rozdíly v souboru. Nezměněným kontextovým řádkům předchází mezerka, řádkům sčítání předchází znaménko plus a řádkům vymazání předchází znaménko mínus ."

Hunk začíná informacemi o rozsahu a bezprostředně za ním následují přidání řádků, odstranění řádků a libovolný počet kontextových řádků. Informace o rozsahu jsou obklopeny dvojitými znaménky a kombinují na jeden řádek to, co se objeví na dvou řádcích v kontextu ( výše ). Formát informačního řádku rozsahu je následující: 

@@ -l,s +l,s @@ optional section heading

Informace o rozsahu kusů obsahují dva rozsahy kusů. Rozsahu pro část původního souboru předchází symbol mínus a rozsahu pro nový soubor předchází symbol plus. Každý rozsah bloků má formát l, s, kde l je číslo počátečního řádku a s je počet řádků, na které se vztahuje změna bloku pro každý příslušný soubor. V mnoha verzích GNU diff může každý rozsah vynechat čárku a koncovou hodnotu s , přičemž v takovém případě je výchozí hodnota 1. Všimněte si, že jedinou opravdu zajímavou hodnotou je číslo řádku l prvního rozsahu; všechny ostatní hodnoty lze vypočítat z rozdílu.

Rozsah skladeb pro originál by měl být součtem všech kontextových a odstraněných (včetně změněných) řádků kusu. Rozsah skladeb pro nový soubor by měl být součtem všech kontextových a přidaných (včetně změněných) řádků řádků. Pokud informace o velikosti kusu neodpovídají počtu řádků v kusu, pak by rozdíl mohl být považován za neplatný a odmítnut.

Volitelně může za rozsahem hromádky následovat nadpis sekce nebo funkce, jejíž součástí je část. To je hlavně užitečné, aby byl rozdíl lépe čitelný. Při vytváření rozdílu pomocí GNU diff je nadpis identifikován shodou s regulárními výrazy .

Pokud je řádek upraven, je reprezentován jako odstranění a přidání. Jelikož se hromady původního a nového souboru objevují ve stejném kusu, takové změny by se objevily vedle sebe. K tomu v následujícím příkladu dochází: 

-check this dokument. On
+check this document. On

Příkaz diff -u original newvytvoří následující výstup: 

--- /path/to/original	timestamp
+++ /path/to/new	timestamp
@@ -1,3 +1,9 @@
+This is an important
+notice! It should
+therefore be located at
+the beginning of this
+document!
+
 This part of the
 document has stayed the
 same from version to
@@ -8,13 +14,8 @@
 compress the size of the
 changes.

-This paragraph contains
-text that is outdated.
-It will be deleted in the
-near future.
-
 It is important to spell
-check this dokument. On
+check this document. On
 the other hand, a
 misspelled word isn't
 the end of the world.
@@ -22,3 +23,7 @@
 this paragraph needs to
 be changed. Things can
 be added after it.
+
+This paragraph contains
+important new additions
+to this document.

Poznámka: Zde je výstup rozdílu zobrazen pomocí barev, které usnadňují jeho čtení. Obslužný program diff nevytváří barevný výstup; jeho výstupem je prostý text . Mnoho nástrojů však může zobrazit výstup pomocí barev pomocí zvýraznění syntaxe .

Všimněte si toho, že pro úspěšné oddělení názvů souborů od časových razítek je oddělovač mezi nimi znak tabulátoru. Toto je na obrazovce neviditelné a může být ztraceno, když jsou rozdíly kopírovány/vkládány z obrazovek konzoly/terminálu.

Existují určité úpravy a rozšíření formátů diff, které jsou používány a chápány určitými programy a v určitých kontextech. Například některé systémy pro řízení revizí - například Subversion - určují číslo verze, „pracovní kopii“ nebo jakýkoli jiný komentář namísto nebo kromě časového razítka v sekci záhlaví rozdílu.

Některé nástroje umožňují sloučení rozdílů pro několik různých souborů do jednoho pomocí záhlaví pro každý upravený soubor, který může vypadat nějak takto: 

Index: path/to/file.cpp

Zvláštní případ souborů, které nekončí novým řádkem, není zpracován. Obslužný program unidiff ani standard POSIX diff nedefinují způsob zpracování tohoto typu souborů. (Takové soubory skutečně nejsou „textovými“ soubory podle přísných definic POSIX.) Program opravy si není vědom ani odlišného výstupu specifického pro implementaci.

Implementace a související programy

Změny od roku 1975 zahrnují vylepšení základního algoritmu, přidání užitečných funkcí do příkazu a návrh nových výstupních formátů. Základní algoritmus je popsán v příspěvcích Rozdílný algoritmus O (ND) a jeho variace od Eugena W. Myerse a v Programu porovnávání souborů od Webba Millera a Myerse. Algoritmus byl nezávisle objeven a popsán v Algoritmech pro přibližné porovnávání řetězců , Esko Ukkonen . První edice programu diff byla navržena pro porovnání řádků textových souborů s očekáváním, že znak nového řádku ohraničuje řádky. V 80. letech 20. století vedla podpora binárních souborů k posunu v designu a implementaci aplikace.

GNU diff a diff3 jsou součástí balíčku diffutils s dalšími nástroji souvisejícími s diff a patch . V současné době existuje také balíček patchutils , který lze kombinovat, přeskupovat, porovnávat a opravovat kontextové a sjednocené rozdíly.

Formátovače a rozhraní front-end

Postprocesory sdiff a diffmk vykreslují seznamy rozdílů vedle sebe a aplikují značky změn na tištěné dokumenty. Oba byly vyvinuty jinde v Bell Labs v roce 1981 nebo dříve.

Diff3 porovnává jeden soubor se dvěma dalšími soubory sladěním dvou rozdílů. Původně byl navržen Paulem Jensenem, aby sladil změny provedené dvěma lidmi, kteří upravují společný zdroj. Používají ho také systémy řízení revizí, např. RCS , pro slučování .

Emacs má Ediff, který ukazuje změny, které by patch poskytoval v uživatelském rozhraní, které kombinuje možnosti interaktivních úprav a slučování souborů oprav.

Vim poskytuje vimdiff pro porovnání dvou až osmi souborů, přičemž rozdíly jsou zvýrazněny barevně. Zatímco historicky vyvolává program diff, moderní vim používá kód git 's fork knihovny xdiff (LibXDiff), který poskytuje vyšší rychlost a funkčnost.

GNU Wdiff je frontend pro diff, který zobrazuje slova nebo fráze, které se změnily v textovém dokumentu psaného jazyka, a to i za přítomnosti zalamování slov nebo různých šířek sloupců.

colordiff je Perl wrapper pro 'diff' a produkuje stejný výstup, ale s pěkným zvýrazněním 'syntaxe'.

Algoritmické deriváty

Nástroje, které porovnávají zdrojové soubory podle jejich syntaktické struktury, byly vytvořeny většinou jako nástroje výzkumu pro některé programovací jazyky; některé jsou k dispozici jako komerční nástroje. Mezi bezplatné nástroje, které provádějí rozdíl podporující syntaxi, navíc patří:

  • C ++: zograscope, AST-based.
  • HTML: Daisydiff, html-differ.
  • XML: xmldiffpatch od společnosti Microsoft a xmldiffmerge pro IBM.
  • JavaScript : astii (na bázi AST).
  • Vícejazyčný: Docela rozdíl (formátujte kód a pak rozdíl)

spiff je varianta diffu, která ignoruje rozdíly ve výpočtech s pohyblivou řádovou čárkou s chybami zaokrouhlení a mezerami , přičemž oba jsou pro srovnání zdrojového kódu obecně irelevantní. Bellcore napsal původní verzi. HPUX port je nejaktuálnější vydání veřejnosti. spiff nepodporuje binární soubory. spiff výstupy na standardní výstup ve standardním formátu diff a přijímá vstupy v programovacích jazycích C , Bourne , Fortran , Modula-2 a Lisp .

LibXDiff je knihovna LGPL, která poskytuje rozhraní pro mnoho algoritmů z roku 1998. Původně byl implementován vylepšený Myersův algoritmus s Rabinovým otiskem prstu (ke konečnému vydání roku 2008), ale vidlice git a libgit2 od té doby rozšířila úložiště o mnoho jeho vlastní. Jeden algoritmus nazvaný „histogram“ je obecně považován za mnohem lepší než původní Myersův algoritmus, a to jak v rychlosti, tak v kvalitě. Toto je moderní verze LibXDiff, kterou používá Vim.

Viz také

Další bezplatné nástroje pro porovnávání souborů

Reference

Další čtení

externí odkazy