Eine diff-Patch auf einen String/eine Datei anwenden

Question

Für eine offline-fähige Smartphone-App erstelle ich eine Einweg-Textsynchronisation für Xml-Dateien. Ich möchte, dass mein Server die Delta-/Unterschied (z.B. ein GNU-Diff-Patch) an das Zielgerät sendet.

Das ist der Plan:

Zeit = 0
Server: hat Version_1 der Xml-Datei (~800 KiB)
Client: hat Version_1 der Xml-Datei (~800 KiB)

Zeit = 1
Server: hat Version_1 und Version_2 der Xml-Datei (jeweils ~800 KiB)
        berechnet Delta dieser Versionen (=Patch) (~10 KiB) 
        sendet Patch an Client (~10 KiB übertragen)

Client: berechnet Version_2 aus Version_1 und Patch  <= das ist das Problem =>

Gibt es eine Ruby-Bibliothek, die diesen letzten Schritt ausführen kann, um einen Textpatch auf Dateien/Strings anzuwenden? Der Patch kann im erforderlichen Format vorliegen.

Vielen Dank für deine Hilfe!

(Ich verwende das Rhodes Cross-Platform Framework, das Ruby als Programmiersprache verwendet.)

Answer 1

Ihre erste Aufgabe besteht darin, ein Patch-Format zu wählen. Das schwerste Format für Menschen zu lesen (meiner bescheidenen Meinung nach) stellt sich als das einfachste Format heraus, das Software anwenden kann: das ed(1) Skript. Sie können mit einem einfachen /usr/bin/diff -e old.xml new.xml beginnen, um die Patches zu generieren; diff(1) wird zeilenorientierte Patches erzeugen, aber das sollte zum Einstieg in Ordnung sein. Das ed-Format sieht so aus:

36a
     #182349
.
34c
     #xxxxxx
.
20,23d

Die Zahlen sind Zeilennummern, Zeilennummernbereiche sind durch Kommas getrennt. Dann gibt es drei einzelne Buchstaben-Befehle:

• a: fügen Sie den nächsten Textblock an dieser Position hinzu.
• c: ändern Sie den Text an dieser Position in den folgenden Block. Dies entspricht einem d gefolgt von einem a Befehl.
• d: löschen Sie diese Zeilen.

Sie werden auch bemerken, dass die Zeilennummern im Patch von unten nach oben gehen, so dass Sie sich keine Sorgen darüber machen müssen, dass Änderungen die Zeilennummern in nachfolgenden Teilen des Patches durcheinanderbringen. Die tatsächlichen Textblöcke, die hinzugefügt oder geändert werden sollen, folgen den Befehlen als Sequenz von Zeilen, die durch eine Zeile mit einem einzelnen Punkt abgeschlossen sind (d.h. /^\.$/ oder patch_line == '.' je nach Präferenz). Zusammengefasst sieht das Format so aus:

[Zeilennummernbereich][Befehl]
[optionale Argumentzeilen...]
[Punkt-Terminator, wenn Argumente vorhanden sind]

Um einen ed Patch anzuwenden, laden Sie einfach die Zieldatei in ein Array (ein Element pro Zeile), analysieren den Patch mit einer einfachen Zustandsmaschine, rufen Array#insert auf, um neue Zeilen hinzuzufügen, und Array#delete_at, um sie zu entfernen. Es sollte nicht mehr als ein paar Dutzend Zeilen Ruby benötigen, um den Patcher zu schreiben, und es ist keine Bibliothek erforderlich.

Wenn Sie Ihr XML so anordnen können, dass es so aussieht:

bla bla

murmeln murmeln

anstatt:

bla blamurmeln murmeln

dann wird der oben beschriebene einfache zeilenorientierte Ansatz gut funktionieren; die zusätzlichen Zeilenumbrüche werden nicht viel Platz kosten, also wählen Sie zur einfachen Implementierung den einfacheren Weg zum Starten.

Es gibt Ruby-Bibliotheken zum Erzeugen von Diffs zwischen zwei Arrays (googlen Sie "ruby algorithm::diff" um zu beginnen). Durch die Kombination einer Diff-Bibliothek mit einem XML-Parser können Sie Patches erstellen, die auf Tags basieren, anstatt auf Zeilen, und das könnte besser zu Ihnen passen. Das Wichtige ist die Wahl des Patch-Formats, sobald Sie das ed Format gewählt haben (und die Weisheit des Patches, der von unten nach oben funktioniert, erkannt haben), fällt so ziemlich alles andere mit wenig Aufwand an seinen Platz.

Answer 2

Ich weiß, diese Frage ist fast fünf Jahre alt, aber ich werde trotzdem eine Antwort posten. Als ich nach einer Lösung gesucht habe, wie man in Ruby Patches für Strings erstellt und anwendet, konnte ich auch jetzt keine Ressourcen finden, die diese Frage zufriedenstellend beantworten. Deshalb zeige ich, wie ich dieses Problem in meiner Anwendung gelöst habe.

Patches erstellen

Ich gehe davon aus, dass du Linux verwendest oder anderweitig Zugriff auf das Programm diff durch Cygwin hast. In diesem Fall kannst du das ausgezeichnete Diffy gem verwenden, um ed-Skript-Patches zu erstellen:

patch_text = Diffy::Diff.new(old_text, new_text, :diff => "-e").to_s

Patches anwenden

Patches anzuwenden ist nicht ganz so einfach. Ich habe mich entschieden, meinen eigenen Algorithmus zu schreiben, um Verbesserungen in der Codeüberprüfung zu bitten und schließlich darauf zu bestehen, den unten stehenden Code zu verwenden. Dieser Code ist identisch mit der Antwort von 200_success, abgesehen von einer Änderung zur Verbesserung seiner Korrektheit.

require 'stringio'
def self.apply_patch(old_text, patch)
  text = old_text.split("\n")
  patch = StringIO.new(patch)
  current_line = 1

  while patch_line = patch.gets
    # Das Kommando abrufen
    m = %r{\A(?:(\d+))?(?:,(\d+))?([acd]|s/\.//)\Z}.match(patch_line)
    raise ArgumentError.new("Ungültiges ed-Kommando: #{patch_line.chomp}") if m.nil?
    first_line = (m[1] || current_line).to_i
    last_line = (m[2] || first_line).to_i
    command = m[3]

    case command
    when "s/.//"
      (first_line..last_line).each { |i| text[i - 1].sub!(/./, '') }
    else
      if ['d', 'c'].include?(command)
        text[first_line - 1 .. last_line - 1] = []
      end
      if ['a', 'c'].include?(command)
        current_line = first_line - (command=='a' ? 0 : 1) # Adds are 0-indexed, but Changes and Deletes are 1-indexed
        while (patch_line = patch.gets) && (patch_line.chomp! != '.') && (patch_line != '.')
          text.insert(current_line, patch_line)
          current_line += 1
        end
      end
    end
  end
  text.join("\n")
end