Aplicar un parche diff a una cadena/archivo

Question

Para una aplicación de teléfono inteligente con capacidad fuera de línea, estoy creando una sincronización de texto unidireccional para archivos Xml. Me gustaría que mi servidor envíe el delta/diferencia (por ejemplo, un parche diff de GNU) al dispositivo de destino.

Este es el plan:

Time = 0 
Server: has version_1 of Xml file (~800 kiB) 
Client: has version_1 of Xml file (~800 kiB) 

Time = 1 
Server: has version_1 and version_2 of Xml file (each ~800 kiB) 
     computes delta of these versions (=patch) (~10 kiB) 
     sends patch to Client (~10 kiB transferred) 

Client: computes version_2 from version_1 and patch <= this is the problem => 

¿Hay una biblioteca de Ruby que puede hacer esto último paso para aplicar un parche de texto en los archivos/cuerdas? El parche se puede formatear según lo requerido por la biblioteca.

Gracias por su ayuda!

(estoy usando el Rodas varias plataformas de Marco, que utiliza como lenguaje de programación de Ruby.)

Answer 1

Su primera tarea es elegir un formato de parche. El formato más difícil para los humanos para leer (en mi humilde opinión) resulta ser el formato más fácil de aplicar para el software: el script ed (1). Puede comenzar con un simple /usr/bin/diff -e old.xml new.xml para generar los parches; diff (1) producirá parches orientados a la línea, pero debería estar bien para empezar. El formato ed ve así:

36a 
    <tr><td class="eg" style="background: #182349;">&nbsp;</td><td><tt>#182349</tt></td></tr> 
. 
34c 
    <tr><td class="eg" style="background: #66ccff;">&nbsp;</td><td><tt>#xxxxxx</tt></td></tr> 
. 
20,23d 

Los números son números de línea, los intervalos de número de línea son separados por comas. A continuación hay tres comandos individuales de letras:

• un: añadir el siguiente bloque de texto en esa posición.
• c: cambie el texto en esta posición al siguiente bloque. Esto es equivalente a d seguido de un un comando.
• d: elimine estas líneas.

También notará que los números de línea en el parche van de abajo hacia arriba para que no tenga que preocuparse por los cambios que ensucian los números de las líneas en trozos posteriores del parche. Los fragmentos reales de texto que se agregarán o cambiarán seguirán los comandos como una secuencia de líneas terminadas por una línea con un único período (es decir, /^\.$/ o patch_line == '.' según su preferencia). En resumen, el formato es el siguiente:

[line-number-range][command] 
[optional-argument-lines...] 
[dot-terminator-if-there-are-arguments] 

Por lo tanto, la aplicación de un ed parche, todo lo que necesita hacer es cargar el archivo de destino en una matriz (un elemento por línea), analizar el parche usando una máquina de estado simple, llame al Array#insert para agregar nuevas líneas y Array#delete_at para eliminarlas. No debe tomar más de un par de docenas de líneas de Ruby para escribir el parche y no se necesita ninguna biblioteca.

Si usted puede arreglar su XML para salir de esta manera:

<tag> 
blah blah 
</tag> 
<other-tag x="y"> 
mumble mumble 
</other> 

en lugar de:

<tag>blah blah</tag><other-tag x="y">mumble mumble</other> 

entonces el enfoque orientado a simple línea anterior funcionará bien; los EOL extra no van a costar mucho espacio así que ve por una implementación fácil para comenzar.

Hay bibliotecas de Ruby para producir diffs entre dos matrices (google "ruby algorithm :: diff" para comenzar). La combinación de una biblioteca de diferencias con un analizador XML le permitirá producir parches basados ​​en etiquetas en lugar de en línea, y esto podría ser más conveniente. Lo importante es la elección de los formatos de parche, una vez que elija el formato ed (y se dé cuenta de la sabiduría del parche que funciona de abajo hacia arriba), entonces todo lo demás encajará prácticamente con el mínimo esfuerzo.

Answer 2

Sé que esta pregunta tiene casi cinco años, pero de todos modos voy a publicar una respuesta. Al buscar cómo crear y aplicar parches para cadenas en Ruby, incluso ahora, no pude encontrar ningún recurso que responda satisfactoriamente esta pregunta. Por ese motivo, mostraré cómo resolví este problema en mi aplicación.

Parches Hacer

Estoy asumiendo que usted está utilizando Linux, o bien tener acceso al programa diff través de Cygwin. En ese caso, puede utilizar la excelente Diffy joya para crear parches ed script:

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

aplicando parches

La aplicación de parches no es tan sencillo. Opté por escribir mi propio algoritmo, ask for improvements in Code Review, y finalmente decidí usar el siguiente código. Este código es idéntico al 200_success's answer a excepción de un cambio para mejorar su corrección.

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 
    # Grab the command 
    m = %r{\A(?:(\d+))?(?:,(\d+))?([acd]|s/\.//)\Z}.match(patch_line) 
    raise ArgumentError.new("Invalid ed command: #{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