Блог

Для автономного приложения для смартфонов я создаю одностороннюю синхронизацию текста для XML-файлов. Я бы хотел, чтобы мой сервер отправил дельту / разницу (например, исправление различий GNU) на целевое устройство.

Таков план:

 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 =>
  

Существует ли библиотека Ruby, которая может выполнить этот последний шаг, чтобы применить текстовое исправление к файлам / строкам? Исправление может быть отформатировано в соответствии с требованиями библиотеки.

Спасибо за вашу помощь!

(Я использую кроссплатформенный фреймворк Rhodes, который использует Ruby в качестве языка программирования.)

Ваша первая задача — выбрать формат исправления. Самый сложный формат для чтения людьми (ИМХО) оказывается самым простым форматом для программного обеспечения: сценарий ed(1). Вы можете начать с простого /usr/bin/diff -e old.xml new.xml способа генерации исправлений; diff (1) создаст исправления, ориентированные на строки, но для начала этого должно быть достаточно. Формат ed выглядит следующим образом:

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

Числа представляют собой номера строк, диапазоны номеров строк разделяются запятыми. Затем есть три команды из одной буквы:

• a: добавьте следующий блок текста в эту позицию.
• c: измените текст в этой позиции на следующий блок. Это эквивалентно d, за которым следует команда a.
• d: удалите эти строки.

Вы также заметите, что номера строк в исправлении идут снизу вверх, поэтому вам не нужно беспокоиться об изменениях, которые испортят номера строк в последующих частях исправления. Фактические фрагменты текста, которые необходимо добавить или изменить, следуют за командами в виде последовательности строк, заканчивающихся строкой с одной точкой (т.е. /^.$/ или patch_line == '.' в зависимости от ваших предпочтений). В итоге формат выглядит следующим образом:

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

Итак, чтобы применить исправление редактирования, все, что вам нужно сделать, это загрузить целевой файл в массив (по одному элементу на строку), проанализировать исправление с помощью простого конечного автомата, вызвать Array#insert для добавления новых строк и Array#delete_at для их удаления. Для написания исправления на Ruby не должно занимать более пары десятков строк, и никакая библиотека не требуется.

Если вы можете упорядочить свой XML так, чтобы он отображался следующим образом:

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

вместо:

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

тогда приведенный выше простой подход, ориентированный на строку, будет работать нормально; дополнительные EOL не будут занимать много места, поэтому для начала перейдите к простой реализации.

Существуют библиотеки Ruby для создания различий между двумя массивами (для начала загуглите «алгоритм ruby::diff»). Объединение библиотеки различий с анализатором XML позволит вам создавать исправления, основанные на тегах, а не на строках, и это может подойти вам больше. Важным моментом является выбор форматов исправлений, как только вы выберете формат ed (и осознаете мудрость исправления, работающего снизу вверх), тогда все остальное в значительной степени становится на свои места без особых усилий.

Я знаю, что этому вопросу почти пять лет, но я все равно собираюсь опубликовать ответ. При поиске того, как создавать и применять исправления для строк в Ruby, даже сейчас я не смог найти никаких ресурсов, которые удовлетворительно отвечали бы на этот вопрос. По этой причине я покажу, как я решил эту проблему в своем приложении.

Создание исправлений

Я предполагаю, что вы используете Linux или у вас есть доступ к программе diff через Cygwin. В этом случае вы можете использовать отличный драгоценный камень Diffy для создания исправлений для отредактированных скриптов:

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

Применение исправлений

Применение исправлений не так просто. Я решил написать свой собственный алгоритм, запросить улучшения в Code Review и, наконец, остановиться на использовании приведенного ниже кода. Этот код идентичен ответу 200_success за исключением одного изменения, улучшающего его корректность.

 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) amp;amp; (patch_line.chomp! != '.') amp;amp; (patch_line != '.')
          text.insert(current_line, patch_line)
          current_line  = 1
        end
      end
    end
  end
  text.join("n")
end