作者
Patrik Nyblom <pan(at)erlang(dot)org> , Fredrik Svahn <Fredrik(dot)Svahn(at)gmail>
状态
最终/R14A 已在 OTP R14A 版本中实现
类型
标准跟踪
创建时间
2009-11-28
Erlang 版本
OTP_R13B03

EEP 31:二进制操作和搜索模块 #

摘要 #

此 EEP 包含关于模块 binary 的已开发建议,该模块最初在 EEP 9 中提出。

EEP 9 提出了几个模块,并且部分被后来的 EEP(即 EEP 11)取代,但仍然包含尚未实现的有价值的建议。EEP 9 中剩余的模块将因此出现在单独的 EEP 中。此构造是与 EEP 9 的原始作者协商一致后进行的。

建议模块 binary 包含快速搜索算法以及一些在列表中已存在的二进制的常见操作(在 lists 模块中)。

动机 #

虽然 re 库中已经存在高效搜索,但在给定高效实现(即 Boyer-More 和 Aho-Corassick 算法)的情况下,专用搜索函数可以进一步加快二进制文件的搜索速度。单独搜索算法的另一个重要优点是易于程序员使用,因为建议的接口不需要了解正则表达式语法,并且不需要转义二进制文件中的特殊字符。值得注意的是,正则表达式经常用于简单的子字符串搜索或替换,而使用此建议的模块可以轻松完成。

二进制文件的分解通常通过使用位语法完成。然而,一些常见的操作作为普通函数非常有用,既是为了性能,也是为了支持更传统的函数式编程风格。

一些将列表转换为二进制文件和反向转换的操作如今在 erlang 模块中。现在存在的关于二进制文件的 BIF 对二进制文件中的零基与一基定位有不同的看法。例如,binary_to_list/3 使用一基,而 split_binary/2 使用零基。由于约定是使用零基,因此需要新的函数来将二进制文件转换为列表和反向转换。

二进制文件实际上是一种共享数据类型,小二进制文件通常以程序员无法简单控制的方式引用大二进制文件的部分。位串数据类型进一步使程序员难以轻松管理。因此,我还建议使用一些低级函数来检查二进制表示形式和克隆二进制文件,以确保最小表示形式。

由于在 guard 表达式中不允许匹配,因此我还建议将一个用于提取二进制文件部分的函数添加到 guard BIF 的集合中。这将与允许在 guard 中使用 element/2 函数一致。

基本原理 #

对于列表数据类型,有一个帮助库提供用于常见操作的函数,例如搜索和拆分列表。此 EEP 建议应为二进制文件创建类似的库函数集。许多建议的函数基于 erlang-questions 邮件列表中关于二进制文件的问题的答案,例如“如何将数字转换为二进制文件?”。因此,此 EEP 建议在 stdlib 中添加一个模块,即模块 binary,它将以高效的方式实现请求的功能。此模块的大部分内容将需要在本机代码(驻留在虚拟机中)中实现,因此建议的实现将在即将发布的 Erlang 版本中以“beta”功能的形式交付。

建议的功能如下

  • 用于在二进制文件中搜索、拆分和替换的功能。该功能在某些方面将与 Erlang 中已有的正则表达式库的功能重叠,但效率更高,并且具有更简单的接口。

  • 二进制文件的常见操作,它们在 stdlib 模块 lists 中已经有列表的对应项。虽然 lists 模块中的并非所有接口都适用于二进制文件,但许多接口都适用。此模块还为二进制文件的未来操作提供了一个很好的场所,这些操作不适用于列表,或者我们仍然不知道它们的需求。

  • 用于将列表转换为二进制文件和反向转换的函数。这些函数应具有一致的二进制文件零基索引视图。

  • 关于二进制文件内部表示的操作。有时需要此功能来避免由于二进制文件的共享性质而过度使用内存。由于对二进制文件进行操作时不会在拆分二进制文件时进行复制,因此程序可能会在不知不觉中(或至少无意中)通过在进程中保留看似少量的数据来保留对大型二进制文件的引用。二进制文件上许多操作的 O(1) 性质使得数据共享成为必要,但其影响有时会令人惊讶。另一方面,当拆分二进制文件时,O(n) 复杂性和即时内存爆炸会更加令人惊讶,因此需要保留当前行为。建议在此建议的模块中提供用于检查二进制文件共享性质和克隆二进制文件副本以避免共享影响的函数。

所有功能都将应用于面向字节的二进制文件,而不是位长度不是 8 的倍数的位串。提供给这些函数和由这些函数返回的所有二进制文件都应通过 is_binary/1 测试,否则将引发错误。

建议的模块参考 #

我建议以下功能(以 Erlang 手册页的摘录形式呈现)。有关接口的讨论可以在下面找到。

数据类型 #

cp()

表示编译后的搜索模式的不透明数据类型。保证为 tuple(),以允许程序将其与非预编译的搜索模式区分开来。

part() = {Pos,Length}

Start = int()
Length = int()

二进制文件中一部分(或范围)的表示形式。Start 是二进制文件() 中的一个零基偏移量,Length 是该部分的长度。作为此模块中函数的输入,允许使用负 Length 构建反向部分规范,以便二进制文件的部分从 Start + Length 开始,长度为 -Length。这对于引用二进制文件的最后 N 个字节非常有用,如 {size(Binary), -N}。此模块中的函数始终返回带有正 Length 的 part()。

导出 #

compile_pattern(Pattern) -> cp() #

类型

Pattern = binary() | [ binary() ]

构建表示搜索模式编译的内部结构,稍后将在 find、split 或 replace 函数中使用。返回的 cp() 保证为 tuple(),以允许程序将其与非预编译的搜索模式区分开来

当给出二进制文件列表时,它表示要搜索的替代二进制文件的集合。也就是说,如果 [<<"functional">>, <<"programming">>] 作为 Pattern 给出,这意味着“<<"functional">><<"programming">>”。模式是替代方案的集合;当只给出一个二进制文件时,该集合只有一个元素。

如果模式不是二进制文件或二进制文件的平面适当列表,则会引发 badarg 异常。

match(Subject, Pattern) -> Found | no #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = part()

match(Subject, Pattern, []) 相同。

match(Subject,Pattern,Options) -> Found | no #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = part()
Options = [ Option ]
Option = {scope, part()}

Subject 中搜索 Pattern 的第一次出现,并返回位置和长度。

该函数将为从 Subject 中最低位置开始的 Pattern 中的二进制文件返回 {Pos,Length}

示例

1> binary:find(<<"abcde">>, [<<"bcde">>,<<"cd">>],[]).
{1,4}

即使 <<"cd">><<"bcde">> 之前结束,<<"bcde">> 也先开始,因此是第一个匹配项。如果两个重叠的匹配项在同一位置开始,则返回最长的匹配项。

选项摘要

  • {scope, {Start, Length}}
    仅搜索给定的部分。返回值仍然具有来自 Subject 开头的偏移量。允许使用负 Length,如本手册的 TYPES 部分所述。

    如果未找到 Pattern 中的任何字符串,则返回找到的 part(),否则返回原子 no

    有关 Pattern 的描述,请参见 compile_pattern/1

    如果在选项中给出了 {scope, {Start,Length}},使得 Start 大于 Subject 的大小,Start + Length 小于零或 Start + Length 大于 Subject 的大小,则会引发 badarg 异常。

matches(Subject, Pattern) -> Found #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = [ part() ] | []

matches(Subject, Pattern, []) 相同。

matches(Subject,Pattern,Options) -> Found #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Found = [ part() ] | []
Options = [ Option ]
Option = {scope, part()}

工作方式类似于 match,但搜索 Subject 直到耗尽,并返回模式中存在的所有非重叠部分(按顺序)的列表。

第一个最长的匹配项优先于较短的匹配项,以下示例说明了这一点

1> binary:matches(<<"abcde">>, [<<"bcde">>,<<"bc">>>,<<"de">>],[]).
[{1,4}]

结果表明,选择了 <<"bcde">>> 而不是较短的匹配项 <<"bc">>(这将产生一个额外的匹配项 <<"de">>)。这对应于 posix 正则表达式(和像 awk 这样的程序)的行为,但不与 re(和 Perl)中的替代匹配一致,在 re(和 Perl)中,搜索模式中的词法顺序会选择哪个字符串匹配。

如果未找到模式中的任何字符串,则返回空列表。

有关 Pattern 的描述,请参见 compile_pattern/1,有关可用选项的描述,请参见 match/3

如果在选项中给出了 {scope, {Start,Length}},使得 Start 大于 Subject 的大小,Start + Length 小于零或 Start + Length 大于 Subject 的大小,则会引发 badarg 异常。

split(Subject,Pattern) -> Parts #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Parts = [ binary() ]

split(Subject, Pattern, []) 相同。

split(Subject,Pattern,Options) -> Parts #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Parts = [ binary() ]
Options = [ Option ]
Option = {scope, part()} | trim | global

基于 Pattern 将二进制文件拆分为二进制文件列表。如果未给出选项 global,则只有 PatternSubject 中的第一次出现才会导致拆分。

Subject 中实际找到的 Pattern 的部分不包含在结果中。

示例

1> binary:split(<<1,255,4,0,0,0,2,3>>, [<<0,0,0>>,<<2>>],[]).
[<<1,255,4>>, <<2,3>>]
2> binary:split(<<0,1,0,0,4,255,255,9>>, [<<0,0>>, <<255,255>>],[global]).
[<<0,1>>,<<4>>,<<9>>]

选项摘要

  • {scope, part()}
    工作方式与 binary:match/3binary:matches/3 相同。请注意,这只定义了搜索匹配字符串的范围,它不会在拆分之前剪切二进制文件。范围之前和之后的字节将保留在结果中。请参见下面的示例。

  • trim 删除结果中尾部的空部分(如 re:split/3 中的 trim 一样)

  • global
    重复拆分,直到 Subject 耗尽。从概念上讲,global 选项使 splitbinary:matches/3 返回的位置上工作,而通常在 binary:match/3 返回的位置上工作。

在拆分之前,scope 和分解二进制文件的区别的示例

1> binary:split(<<"banana">>,[<<"a">>],[{scope,{2,3}}]).
[<<"ban">>,<<"na">>]
2> binary:split(binary:part(<<"banana">>,{2,3}),[<<"a">>],[]).
[<<"n">>,<<"n">>]

返回类型始终是二进制列表,所有二进制文件都引用 Subject。这意味着 Subject 中的数据实际上不会被复制到新的二进制文件中,并且在分割结果不再被引用之前,Subject 不能被垃圾回收。

有关 Pattern 的描述,请参见 compile_pattern/1

replace(Subject,Pattern,Replacement) -> Result #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Replacement = binary()
Result = binary()

replace(Subject,Pattern,Replacement,[]) 相同。

replace(Subject,Pattern,Replacement,Options) -> Result #

类型

Subject = binary()
Pattern = binary() | [ binary() ] | cp()
Replacement = binary()
Result = binary()
Options = [ Option ]
Option = global | {scope, part()} | {insert_replaced, InsPos}
InsPos = OnePos | [ OnePos ]
OnePos = int() =< byte_size(Replacement)

通过将 Subject 中与 Pattern 匹配的部分替换为 Replacement 的内容,构造一个新的二进制文件。

如果要将导致替换的 Subject 的匹配子部分插入到结果中,则选项 {insert_replaced, InsPos} 将在将 Replacement 实际插入到 Subject 之前,将匹配部分插入到 Replacement 中的给定位置(或多个位置)。 示例

1> binary:replace(<<"abcde">>,<<"b">>,<<"[]">>,[{insert_replaced,1}]).
<<"a[b]cde">>
2> binary:replace(<<"abcde">>,[<<"b">>,<<"d">>],<<"[]">>,
                 [global,{insert_replaced,1}]).
<<"a[b]c[d]e">>
3> binary:replace(<<"abcde">>,[<<"b">>,<<"d">>],<<"[]">>,
                 [global,{insert_replaced,[1,1]}]).
<<"a[bb]c[dd]e">>
4> binary:replace(<<"abcde">>,[<<"b">>,<<"d">>],<<"[-]">>,
                 [global,{insert_replaced,[1,2]}]).
<<"a[b-b]c[d-d]e">>

如果 InsPos 中给出的任何位置大于替换二进制文件的大小,则会引发 badarg 异常。

选项 global{scope, part()} 的工作方式与 binary:split/3 相同。返回类型始终是二进制文件。

有关 Pattern 的描述,请参见 compile_pattern/1

longest_common_prefix(Binaries) -> int() #

类型

Binaries = [ binary() ]

返回列表 Binaries 中二进制文件最长公共前缀的长度。示例

1> binary:longest_common_prefix([<<"erlang">>,<<"ergonomy">>]).
2
2> binary:longest_common_prefix([<<"erlang">>,<<"perl">>]).
0

如果 Binaries 不是二进制文件的扁平列表,则会引发 badarg 异常。

longest_common_suffix(Binaries) -> int() #

类型

Binaries = [ binary() ]

返回列表 Binaries 中二进制文件最长公共后缀的长度。示例

1> binary:longest_common_suffix([<<"erlang">>,<<"fang">>]).
3
2> binary:longest_common_suffix([<<"erlang">>,<<"perl">>]).
0

如果 Binaries 不是二进制文件的扁平列表,则会引发 badarg 异常。

first(Subject) -> int() #

类型

Subject = binary()

以整数形式返回二进制文件的第一个字节。如果二进制文件长度为零,则会引发 badarg 异常。

last(Subject) -> int() #

类型

Subject = binary()

以整数形式返回二进制文件的最后一个字节。如果二进制文件长度为零,则会引发 badarg 异常。

at(Subject, Pos) -> int() #

类型

Subject = binary()
Pos = int() >= 0

以整数形式返回二进制文件 Subject 中位置 Pos(从零开始)处的字节。如果 Pos >= byte_size(Subject),则会引发 badarg 异常。

part(Subject, PosLen) -> binary() #

类型

Subject = binary()
PosLen = part()

提取由 PosLen 描述的二进制文件的部分。

可以使用负长度来提取二进制文件末尾的字节

1> Bin = <<1,2,3,4,5,6,7,8,9,10>>.
2> binary:part(Bin,{byte_size(Bin), -5)).
<<6,7,8,9,10>>

如果 PosLen 以任何方式引用二进制文件外部,则会引发 badarg 异常。

part(Subject, Pos, Len) -> binary() #

类型

Subject = binary()
Pos = int()
Len = int()

part(Subject, {Pos, Len}) 相同。

bin_to_list(Subject) -> list() #

类型

Subject = binary()

bin_to_list(Subject,{0,byte_size(Subject)}) 相同。

bin_to_list(Subject, PosLen) -> list() #

Subject = binary()
PosLen = part()

Subject 转换为 int() 列表,其中每个 int 表示一个字节的值。part() 表示要转换的 binary() 的哪个部分。 示例

1> binary:bin_to_list(<<"erlang">>,{1,3}).
"rla"
%% or [114,108,97] in list notation.

如果 PosLen 以任何方式引用二进制文件外部,则会引发 badarg 异常。

bin_to_list(Subject, Pos, Len) -> list() #

类型

Subject = binary()
Pos = int()
Len = int()

bin_to_list(Subject,{Pos,Len}) 相同。

list_to_bin(ByteList) -> binary() #

类型

ByteList = iodata() (see module erlang)

工作方式与 erlang:list_to_binary/1 完全相同,为了完整性而添加。

copy(Subject) -> binary() #

类型

Subject = binary()

copy(Subject, 1) 相同。

copy(Subject,N) -> binary() #

类型

Subject = binary()
N = int() >= 0

创建一个二进制文件,其中包含 Subject 的内容重复 N 次。

此函数始终会创建一个新的二进制文件,即使 N = 1 也是如此。通过在引用较大二进制文件的二进制文件上使用 copy/1,可以释放较大的二进制文件以进行垃圾回收。

注意! 通过故意复制单个二进制文件以避免引用更大的二进制文件,可能会创建比需要的更多的二进制数据,而不是释放更大的二进制文件以进行稍后的垃圾回收。 共享二进制数据通常是好的。 只有在特殊情况下,当小部分引用较大的二进制文件,并且较大的二进制文件在任何进程中都不再使用时,故意复制可能是一个好主意。

如果 N < 0,则会引发 badarg 异常。

referenced_byte_size(binary()) -> int() #

如果二进制文件引用了更大的二进制文件(通常描述为子二进制文件),则获取实际引用的二进制文件的大小可能很有用。 此函数可用于程序中以触发 copy/1 的使用。 通过复制二进制文件,可能会取消对原始的、可能较大的二进制文件的引用,而较小的二进制文件是对该二进制文件的引用。

示例

store(Binary, GBSet) ->
  NewBin =
      case binary:referenced_byte_size(Binary) of
          Large when Large > 2 * byte_size(Binary) ->
               binary:copy(Binary);
          _ ->
         Binary
      end,
  gb_sets:insert(NewBin,GBSet).

在此示例中,我们选择在将二进制内容插入 gb_set() 之前复制该内容,如果它引用的二进制文件的大小超过我们要保留的数据的两倍。 当然,何时复制的不同规则将适用于不同的程序。

只要二进制文件被拆分,就会发生二进制文件共享,这是二进制文件快速的根本原因,分解始终可以以 O(1) 的复杂度完成。 然而,在极少数情况下,这种数据共享是不可取的,因此,在优化内存使用时,此函数与 copy/1 一起使用可能很有用。

二进制文件共享示例

1> A = binary:copy(<<1>>,100).
<<1,1,1,1,1 ...
2> byte_size(A).
100
3> binary:referenced_byte_size(A)
100
4> <<_:10/binary,B:10/binary,_/binary>> = A.
<<1,1,1,1,1 ...
5> byte_size(B).
10
6> binary:referenced_byte_size(B)
100

注意! 二进制数据在进程之间共享。 如果另一个进程仍然引用较大的二进制文件,则复制此进程使用的部分只会消耗更多内存,并且不会释放较大的二进制文件以进行垃圾回收。 非常谨慎地使用这种侵入式功能,并且只有在检测到真正的问题时才使用。

encode_unsigned(Unsigned) -> binary() #

类型

Unsigned = int() >= 0

encode_unsigned(Unsigned,big) 相同。

encode_unsigned(Unsigned,Endianess) -> binary() #

类型

Unsigned = int() >= 0
Endianess = big | little

将正整数转换为二进制数字表示中最小的可能表示形式,可以是 big-endian 或 little-endian。

示例

1> binary:encode_unsigned(11111111,big).
<<169,138,199>>

decode_unsigned(Subject) -> Unsigned #

类型

Subject = binary()
Unsigned = int() >= 0

encode_unsigned(Subject,big) 相同。

decode_unsigned(Subject, Endianess) -> Unsigned #

类型

Subject = binary()
Endianess = big | little
Unsigned = int() >= 0

Subject 中正整数的二进制数字表示(big-endian 或 little-endian)转换为 Erlang int()。

示例

1> binary:decode_unsigned(<<169,138,199>>,big).
11111111

保护 BIF #

我建议将函数 binary:part/2binary:part/3 添加到保护测试中允许的 BIF 集合中。 由于保护 BIF 传统上放在 erlang 模块中,因此建议为保护 BIF 使用以下名称

erlang:binary_part/2
erlang:binary_part/3

它们的工作方式应与二进制模块中的对应函数完全相同。

接口设计讨论 #

与所有模块一样,关于实际接口的争论很多,有时比关于功能的争论还多。 在这种情况下,必须考虑许多参数。

  • 有效性 - 接口的构造应使得可以快速实现,并且可以以有效的方式编写使用该接口的代码。 不创建不必要的垃圾是一个参数,允许通用代码是另一个参数。

  • 参数顺序 - 我已选择将二进制主题作为所有适用调用的第一个参数。 将主题放在首位对应于 re 接口。 但是,lists 模块通常将主题作为最后一个参数。 我们可以改为这样做,但是不幸的是,lists:sublist/{2,3} 接口(对应于 part 函数)将主题放在首位,因此遵循 lists 的约定不仅会破坏与 re 的一致性,还会给我们一个通常不严格的接口。 不符合 lists 接口的效果是,使用该模块中的函数名称会导致混淆,因此应避免使用。

  • 函数命名 - 在此处命名函数时,我们需要考虑两个相关的模块。 模块 re 与搜索函数(matchreplace 等)相关,而 lists 模块与分解函数(firstlast 等)相关。

    当发现功能在概念和接口上都足够相似时,我基本上保留了 re 中的名称。 正则表达式的性质是小型可执行程序,对于此模块中的模式而言,二进制集合过多,无法使用函数名称 run 来实际进行搜索。 我们使用 matchmatches 而不是 run

    由于此模块比 re 更通用,因此像 compile 这样的函数名称实际上并不好。 re:compile 表示“编译正则表达式”,但 binary:compile 的含义是什么? 因此,预处理函数改为称为 compile_pattern

    lists 模块而言,参数顺序使我无法重用任何函数名称,除了 last,它在 lists 中只接受一个参数,并且没有真正的替代方案。

  • 选项或多个函数 - 我认为一个好的经验法则是不要使用更改函数返回类型的选项,如果我们在 match/3 中使用 global 选项而不是单独的 matches/3 函数,就会出现这种情况。

    对于搜索和分解函数,存在一组可管理的可能返回类型,这使我们可以遵循该经验法则。

    (不幸的是,在 re 中不能轻易遵循该规则,因为丰富的选项种类会产生不可管理的大量函数名称)。

性能 #

尽管分解函数实际上并不比使用位语法进行分解更快,但它们产生的垃圾比位语法略少。 由于它们不比位语法慢,因此它们在允许不同的编程风格方面也很有用。

匹配/替换/分割功能应该与 re 模块中类似的功能进行比较。实现方法必须经过选择,以使本模块的搜索函数比 re 更快,甚至可能显著更快。

参考实现 #

在最终包含在 R14A 之前,GitHub 开发分支上提供了参考实现。

版权 #

本文档根据知识共享署名 3.0 许可获得许可。