Elixir #29 – Decoding Bencode

W zeszłym tygodniu pokazałem jak można szyfrować dane do Bencode za pomocą Elixir. Dzisiaj skoncentruje się na rozszyfrowywaniu wartości. Jednak temat ciągu znaków jest dość obszerny i pewnie poświęcę temu osoby post.

Jak zawsze cały kod możecie pobrać z github. W porównaniu do poprzedniej wersji (z zeszłego tygodnia) nastąpiły dwie zmiany:

1. Zwracam wartości zgodnie z konwencją elixir {:ok, content}, {:error, msg}
2. Poprawiłem pipeline na normalne wykonanie funkcji po uwadze jednego z czytelników.

Dziś zaś zajmiemy się metodą decode/1. Podejście do implementacji mam takie samo – jedna metoda wejścia, wiele prywatnych metod rozmawiających między sobą. To się sprawdza.

Bitstring w skrócie

Za chwilę zobaczycie coś co wygląda tak << >> – to jest tak zwany bitstring. Jest o reprezentacja ciągu znaków jako zbioru bajtów. Na przykład:

"hallo" = <<?h,?a, ?l, ?l, ?o>>

Oj a co to jest znak zapytania ? Znak ? zwróci nam codepoint czyli numeryczną reprezentację danego znaku, dla ?a to będzie 97.

Czyli całe nasze hallo można by też zapisać:

<<104, 97, 108, 108, 111>>

To nam daje niezłe pole manewru, bo, << >> możemy prawie traktować tak samo jak listy.

Implementacja

Mając miejsce wejścia musimy rozdzielić rozszyfrowywanie na poszczególne typy danych (int, list, dic i string). To o czym musimy pamiętać to, to, że list i dic mogą zawierać kolejne elementy (więcej niż 1). To jest ważna informacja i na razie możemy ja trzymać w głowie.

defp do_decode(<<?i, tail::bytes>>), do: do_decode_int(tail, [])
defp do_decode(<<?l, tail::bytes>>), do: do_decode_list(tail, [])
defp do_decode(<<?d, tail::bytes>>), do: do_decode_dict(tail, %{})
defp do_decode(bin = <<x, ?:, _tail::bytes>>) when is_integer(x), do: do_decode_string(bin, [])

defp do_decode(_input) do

end

To co tutaj mamy to po prostu delegowanie rozszyfrowywania do konkretnych metod. Zwróćcie uwagę, że w większości biorę resztę tail::bytes a nie całość. A to z tego powodu, że mi informacja czy to lista czy nie nie będzie już potrzebna.

Wyjątkiem jest metoda która odpowiada za wybranie string – tam przekazuje cały string ale po tym jak go zweryfikuje czy to na pewno jest string (zaczyna się od liczby i potem ma :). Ostatnia funkcja to przechwycenie czegoś co nam nie pasuje nigdzie i zwrócenie nil.

Rozszyfrowywanie int

Integer jest najprostszym przypadkiem, ale zasada rozszyfrowywania jego jest wykorzystywana wszędzie indziej. Nasza liczba może być liczbą mniejszą od 10 jak i znacznie większą. To co wiemy to tylko tyle, że tail ją zawiera – w sensie zawiera liczbę którą chcemy wydostać. W takim momencie możemy wykorzystać rekurencje i bitstringi do tego by pobierać znak po znaku i gdzieś te znaki akumulować. Skoro robimy akumulacje z bistringów, które są stringami, to string raczej nie jest dobrym akumulatorem. Liczba też nie, bo jest ona jedna, jak mamy 123 i będziemy przechodzić kolejno po 1, 2 i 3. Sumowanie ich do akumulatora da zły wynik (6). Zaś by byśmy chcieli całą taką liczbę mieć. Najlepiej więc dodawać ją do listy:

defp do_decode_int(<<head, tail::bytes>>, acc), do: do_decode_int(tail, [head | acc])

To co to robi, to idzie przez wszystkie znaki i tworzy nam listę [ZNAK |reszta]. Czyli jak mamy 123 to kolejne kroki będą wyglądać tak:

1. 1 | []
2. 2 | [1]
3. 3 | [2 | [1]]
4. …

Jak widać nie jest to skomplikowane, jedynie musimy znaleźć moment wyjścia – a ze specyfikacji wiemy, że liczba kończy się wartością e, a więc:

defp do_decode_int(<<?e, tail::bytes>>, acc) do

end 

defp do_decode_int(<<head, tail::bytes>>, acc), do: do_decode_int(tail, [head | acc])

Mamy przygotowaną strategię wyjścia z rekurencji. Patrząc na nasze kroki przy 123, możemy stwierdzić, że do metody wyjścia trafimy po tym jak dodamy 3 do akumulatora. Czyli parametry wejścia dla metody wyjścią będą:

"e", [3,2,1]

By z listy zrobić liczbę wystarczy wykonać polecenie List.to_integer. Problem polega na tym, że nasza liczba wynikowa będzie 321 a nie 123. Więc zanim wykonamy połączenie musimy listę odwrócić. Pełny kod:

defp do_decode_int(<<?e, tail::bytes>>, acc) do
  val = acc |> Enum.reverse |> List.to_integer
  {val, tail} #for handling lists and dicts 
end 

defp do_decode_int(<<head, tail::bytes>>, acc), do: do_decode_int(tail, [head | acc])

Warto zwrócić uwagę na to, co robimy przy zwracaniu danych z rozszyfrowywania int – mianowicie zwracamy tuple – {wartość, reszta}. To ogólnie by zamienić tylko liczbę nie jest potrzebne. Moglibyśmy po prostu zostawić acc |> Enum.reverse |> List.to_integer i by było fajnie.

Problem polega na tym o czym wspomniałem na samym początku, listy i słowniki mogą mieć więcej liczb niż jedna. A skoro konwertujemy liczbę z dictionary, to potem musielibyśmy uciąć pozostały ciąg znaków zgodnie z tym co zostało przekonwertowane – ZAMIESZANIE z POMIESZANIEM. Dlatego też po prostu zwracamy sobie wartość i resztę znaków (tail).

Reszta kodu

Reszta kodu wygląda bardzo podobnie. W sensie jest stworzona na tych samych zasadach. Zachęcam was do spróbowania napisania sobie zamiany listy lub dictionary. Jak wam się to nie uda to na github znajdziecie mój kod.

Podsumowanie

Trochę mi zajęło rozpoznanie się jak to można by napisać. Jednak jak zacząłem korzystać z bitstring, szacun. Naprawdę fajnie i sprawnie to działa. Na tyle fajnie, że już wiem o czym będę chciał pisać przez kolejne tygodnie! :)

W szczególności, ze może to pokaże jak mogę napisać ten kod lepiej :) mam nadzieję.

Jakie macie spostrzeżenia?