Unicode.RangeSearch (Unicode v2.0.0)

Copy Markdown View Source

Builds compact search tables from codepoint ranges and performs binary search over them.

The Unicode property modules build their search tables at compile time from the range data returned by functions such as Unicode.GeneralCategory.categories/0. The tables are stored as module attributes so they are embedded in the compiled module as literals and shared, not copied, at runtime.

Two table shapes are supported:

  • A value table, built with new_value_table/1 from a map of value => ranges, returns the value associated with the range containing a codepoint via find/3.

  • A membership table, built with new_membership_table/1 from a list of ranges, answers whether a codepoint is within any range via member?/2.

Binary search over these tables replaces the very large generated guard clauses previously used for codepoint lookup, reducing compile time by an order of magnitude and lookup time by approximately 10x.

Summary

Types

membership_table()

A tuple of range starts and range ends.

range()

A codepoint range expressed as an inclusive 2-tuple.

value_table()

A tuple of range starts, range ends and the value for each range.

Functions

find(arg, codepoint, default)

Returns the value for the range containing a codepoint.

member?(arg, codepoint)

Returns whether any range in a membership table contains a codepoint.

new_membership_table(ranges)

Builds a membership table from a list of codepoint ranges.

new_value_table(range_map)

Builds a value table from a map of values to codepoint ranges.

Types

membership_table()

@type membership_table() :: {tuple(), tuple()}

A tuple of range starts and range ends.

range()

@type range() :: {non_neg_integer(), non_neg_integer()}

A codepoint range expressed as an inclusive 2-tuple.

value_table()

@type value_table() :: {tuple(), tuple(), tuple()}

A tuple of range starts, range ends and the value for each range.

Functions

find(arg, codepoint, default)

@spec find(value_table(), integer(), any()) :: any()

Returns the value for the range containing a codepoint.

Arguments

  • value_table is a table built with new_value_table/1.

  • codepoint is an integer codepoint.

  • default is the term returned when no range contains codepoint.

Returns

  • The value associated with the range containing codepoint, or default.

Examples

iex> table = Unicode.RangeSearch.new_value_table(%{lower: [{?a, ?z}], upper: [{?A, ?Z}]})
iex> Unicode.RangeSearch.find(table, ?A, :none)
:upper

member?(arg, codepoint)

@spec member?(membership_table(), integer()) :: boolean()

Returns whether any range in a membership table contains a codepoint.

Arguments

Returns

  • true if a range contains codepoint, otherwise false.

Examples

iex> table = Unicode.RangeSearch.new_membership_table([{?0, ?9}])
iex> Unicode.RangeSearch.member?(table, ?7)
true

new_membership_table(ranges)

@spec new_membership_table([range(), ...]) :: membership_table()

Builds a membership table from a list of codepoint ranges.

Arguments

  • ranges is a list of 2-tuple codepoint ranges.

Returns

Ranges whose bounds are not integers (for example, multi-codepoint emoji sequence ranges) are ignored. Overlapping and adjacent ranges are merged.

Examples

iex> table = Unicode.RangeSearch.new_membership_table([{?a, ?z}, {?0, ?9}])
iex> Unicode.RangeSearch.member?(table, ?x)
true
iex> Unicode.RangeSearch.member?(table, ?!)
false

new_value_table(range_map)

@spec new_value_table(%{required(any()) => [range(), ...]}) :: value_table()

Builds a value table from a map of values to codepoint ranges.

Arguments

  • range_map is a map with any term as the key and a list of 2-tuple codepoint ranges as the value.

Returns

Ranges whose bounds are not integers (for example, multi-codepoint emoji sequence ranges) are ignored. Raises ArgumentError if ranges associated with different values overlap, since the table cannot then return a single value for a codepoint.

Examples

iex> table = Unicode.RangeSearch.new_value_table(%{lower: [{?a, ?z}], upper: [{?A, ?Z}]})
iex> Unicode.RangeSearch.find(table, ?q, :none)
:lower
iex> Unicode.RangeSearch.find(table, ?5, :none)
:none