将差异补丁应用于字符串/文件

Question

对于一款支持离线功能的智能手机应用程序，我正在为 Xml 文件创建单向文本同步。我希望我的服务器将增量/差异（例如 GNU diff 补丁）发送到目标设备。

计划是这样的：

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 作为编程语言。）

Answer 1

您的第一个任务是选择补丁格式。人类最难阅读的格式（恕我直言）事实证明是软件最容易应用的格式：ed(1) 脚本。您可以从简单的 /usr/bin/diff -e old.xml new.xml 开始生成补丁； diff(1) 将产生面向行的补丁，但这应该可以开始。 ed 格式如下所示：

36a
    <tr><td class="eg" style="background: #182349;"> </td><td><tt>#182349</tt></td></tr>
.
34c
    <tr><td class="eg" style="background: #66ccff;"> </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]

因此，要应用 ed 补丁，您所需要做的就是将目标文件加载到数组中（每行一个元素），使用简单的方法解析补丁状态机，调用 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 Algorithm::diff”开始）。将 diff 库与 XML 解析器相结合可以让您生成基于标记而不是基于行的补丁，这可能更适合您。重要的是补丁格式的选择，一旦您选择了 ed 格式（并意识到补丁从下到上工作的智慧），那么其他一切几乎都会毫不费力地就位。

Answer 2

我知道这个问题已经快五年了，但无论如何我都会发布答案。当搜索如何在 Ruby 中制作和应用字符串补丁时，即使是现在，我也无法找到任何可以令人满意地回答这个问题的资源。因此，我将展示如何在我的应用程序中解决这个问题。

制作补丁

我假设您使用的是 Linux，或者可以通过 Cygwin 访问程序 diff。在这种情况下，您可以使用优秀的 Diffy gem 来创建 ed 脚本 补丁：

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

应用补丁

应用补丁并不那么简单。我选择编写自己的算法，请求代码审查方面的改进，并且最后决定使用下面的代码。此代码与 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) && (patch_line.chomp! != '.') && (patch_line != '.')
          text.insert(current_line, patch_line)
          current_line += 1
        end
      end
    end
  end
  text.join("\n")
end