Elixir bitstring contains sub-bitstring

Question

I'd like to check whether a long bitstring contains another bitstring within it. Something like:

if MyBitstringModule.contains(<<1, 2, 3, 4, 5>>, <<2, 3, 4>>) do
  # do stuff
end

If I had binaries instead, this would be really easy: I could use the =~ operator or String.contains?/2. However, both of those operate on binaries only and would therefore fail on bitstrings whose size is not divisible by 8.

The best I've come up with so far is a recursive pattern match like this (not actually working!), which seems like a kludge:

def contains(haystack, needle) when is_bitstring(haystack) and is_bitstring(needle) do
  needle_size = bit_size(needle)
  case haystack do
    <<>> -> false
    <<^needle::size(needle_size), _::bitstring>> -> true
    <<_::size(1), remainder::bitstring>> -> contains(remainder, needle)
  end
end

[Note that despite having more or less the same title, this is not actually a duplicate of this question—the linked question and its answer both deal with binaries only.]

EDIT: My test case above was bad, since both arguments are actually binaries. Better test cases are:

iex> contains(<<1, 2, 3, 4, 5, 1::size(1)>>, <<2, 3, 4>>)
true
iex> contains(<<1, 2, 3, 4, 5, 1::size(1)>>, <<4, 5, 1::size(1)>>)
true

Brett Beatty Brett Beatty · Accepted Answer · 2020-01-29T00:03:14

It worked for me adding the bitstring type to your true case

<<^needle::bitstring-size(needle_size), _::bitstring>> -> true

If you try matching on it directly

iex> needle = <<3, 4, 5>>
<<3, 4, 5>>
iex> needle_size = bit_size(needle)
24
iex> <<^needle::size(needle_size), _::bitstring>> = <<3, 4, 5>>
** (MatchError) no match of right hand side value: <<3, 4, 5>>
iex> <<^needle::bitstring-size(needle_size), _::bitstring>> = <<3, 4, 5>>
<<3, 4, 5>>

Elixir bitstring contains sub-bitstring

1 Answers