birdie

-module(birdie@internal@diff).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch]).

-export([histogram/2]).
-export_type([diff_line/0, diff_line_kind/0, occurs/1]).

-type diff_line() :: {diff_line, integer(), binary(), diff_line_kind()}.

-type diff_line_kind() :: old | new | shared.

-type occurs(KCE) :: {one, integer(), list(KCE), list(KCE)} |
    {other, integer(), list(KCE), list(KCE)} |
    {both, integer(), list(KCE), list(KCE), list(KCE), list(KCE)}.

-spec match_diff_lines(
    list(diff_line()),
    list(binary()),
    integer(),
    list(binary()),
    integer(),
    list(binary())
) -> list(diff_line()).
match_diff_lines(Lines, Lcs, Line_one, One, Line_other, Other) ->
    case {Lcs, One, Other} of
        {[], [], []} ->
            lists:reverse(Lines);

        {[], [First | One@1], Other@1} ->
            _pipe = [{diff_line, Line_one, First, old} | Lines],
            match_diff_lines(
                _pipe,
                Lcs,
                Line_one + 1,
                One@1,
                Line_other,
                Other@1
            );

        {[], [], [First@1 | Other@2]} ->
            _pipe@1 = [{diff_line, Line_other, First@1, new} | Lines],
            match_diff_lines(
                _pipe@1,
                Lcs,
                Line_one,
                One,
                Line_other + 1,
                Other@2
            );

        {[First_common | _], [First_one | One@2], Other@3} when First_common =/= First_one ->
            _pipe@2 = [{diff_line, Line_one, First_one, old} | Lines],
            match_diff_lines(
                _pipe@2,
                Lcs,
                Line_one + 1,
                One@2,
                Line_other,
                Other@3
            );

        {[First_common@1 | _], One@3, [First_other | Other@4]} when First_common@1 =/= First_other ->
            _pipe@3 = [{diff_line, Line_other, First_other, new} | Lines],
            match_diff_lines(
                _pipe@3,
                Lcs,
                Line_one,
                One@3,
                Line_other + 1,
                Other@4
            );

        {[First_common@2 | Lcs@1], [_ | One@4], [_ | Other@5]} ->
            _pipe@4 = [{diff_line, Line_other, First_common@2, shared} | Lines],
            match_diff_lines(
                _pipe@4,
                Lcs@1,
                Line_one + 1,
                One@4,
                Line_other + 1,
                Other@5
            );

        {[_ | _], [], _} ->
            erlang:error(#{gleam_error => panic,
                    message => <<"unreachable"/utf8>>,
                    module => <<"birdie/internal/diff"/utf8>>,
                    function => <<"match_diff_lines"/utf8>>,
                    line => 65});

        {[_ | _], _, []} ->
            erlang:error(#{gleam_error => panic,
                    message => <<"unreachable"/utf8>>,
                    module => <<"birdie/internal/diff"/utf8>>,
                    function => <<"match_diff_lines"/utf8>>,
                    line => 65})
    end.

-spec sum_occurrences(occurs(KDL), occurs(KDL)) -> occurs(KDL).
sum_occurrences(One, Other) ->
    case {One, Other} of
        {{one, N, _, _}, {one, M, Before, After}} ->
            {one, N + M, Before, After};

        {{other, N@1, _, _}, {other, M@1, Before@1, After@1}} ->
            {other, N@1 + M@1, Before@1, After@1};

        {{one, N@2, Before_one, After_one},
            {other, M@2, Before_other, After_other}} ->
            {both, N@2 + M@2, Before_one, After_one, Before_other, After_other};

        {{both, N@2, Before_one, After_one, _, _},
            {other, M@2, Before_other, After_other}} ->
            {both, N@2 + M@2, Before_one, After_one, Before_other, After_other};

        {_, _} ->
            erlang:error(#{gleam_error => panic,
                    message => <<"unreachable: sum_occurrences"/utf8>>,
                    module => <<"birdie/internal/diff"/utf8>>,
                    function => <<"sum_occurrences"/utf8>>,
                    line => 182})
    end.

-spec histogram_add(
    gleam@dict:dict(KCZ, occurs(KCZ)),
    list(KCZ),
    fun((integer(), list(KCZ), list(KCZ)) -> occurs(KCZ)),
    list(KCZ)
) -> gleam@dict:dict(KCZ, occurs(KCZ)).
histogram_add(Histogram, List, To_occurrence, Reverse_prefix) ->
    case List of
        [] ->
            Histogram;

        [First | Rest] ->
            _pipe = (gleam@dict:update(
                Histogram,
                First,
                fun(Previous) ->
                    New_occurrence = To_occurrence(1, Reverse_prefix, Rest),
                    case Previous of
                        {some, Occurrence} ->
                            sum_occurrences(Occurrence, New_occurrence);

                        none ->
                            New_occurrence
                    end
                end
            )),
            histogram_add(_pipe, Rest, To_occurrence, [First | Reverse_prefix])
    end.

-spec lowest_occurrence_common_item(list(KCR), list(KCR)) -> gleam@option:option({KCR,
    integer(),
    list(KCR),
    list(KCR),
    list(KCR),
    list(KCR)}).
lowest_occurrence_common_item(One, Other) ->
    Histogram = begin
        _pipe = histogram_add(
            gleam@dict:new(),
            One,
            fun(Field@0, Field@1, Field@2) -> {one, Field@0, Field@1, Field@2} end,
            []
        ),
        histogram_add(
            _pipe,
            Other,
            fun(Field@0, Field@1, Field@2) -> {other, Field@0, Field@1, Field@2} end,
            []
        )
    end,
    gleam@dict:fold(Histogram, none, fun(Lowest, A, Occurs) -> case Occurs of
                {one, _, _, _} ->
                    Lowest;

                {other, _, _, _} ->
                    Lowest;

                {both, N, Before_one, After_one, Before_other, After_other} ->
                    case Lowest of
                        none ->
                            {some,
                                {A,
                                    N,
                                    Before_one,
                                    After_one,
                                    Before_other,
                                    After_other}};

                        {some, {_, M, _, _, _, _}} ->
                            case M =< N of
                                true ->
                                    Lowest;

                                false ->
                                    _pipe@1 = {A,
                                        N,
                                        Before_one,
                                        After_one,
                                        Before_other,
                                        After_other},
                                    {some, _pipe@1}
                            end
                    end
            end end).

-spec do_pop_common_prefix(list(KDV), list(KDV), list(KDV)) -> {list(KDV),
    list(KDV),
    list(KDV)}.
do_pop_common_prefix(Reverse_prefix, One, Other) ->
    case {One, Other} of
        {[First_one | One@1], [First_other | Other@1]} when First_one =:= First_other ->
            do_pop_common_prefix([First_one | Reverse_prefix], One@1, Other@1);

        {_, _} ->
            {Reverse_prefix, One, Other}
    end.

-spec pop_common_prefix(list(KDP), list(KDP)) -> {list(KDP),
    list(KDP),
    list(KDP)}.
pop_common_prefix(One, Other) ->
    {Reverse_prefix, One@1, Other@1} = do_pop_common_prefix([], One, Other),
    {lists:reverse(Reverse_prefix), One@1, Other@1}.

-spec pop_common_suffix(list(KEC), list(KEC)) -> {list(KEC),
    list(KEC),
    list(KEC)}.
pop_common_suffix(One, Other) ->
    {Suffix, Reverse_one, Reverse_other} = do_pop_common_prefix(
        [],
        lists:reverse(One),
        lists:reverse(Other)
    ),
    {Suffix, lists:reverse(Reverse_one), lists:reverse(Reverse_other)}.

-spec lcs(list(KCN), list(KCN)) -> list(KCN).
lcs(One, Other) ->
    {Prefix, One@1, Other@1} = pop_common_prefix(One, Other),
    {Suffix, One@2, Other@2} = pop_common_suffix(One@1, Other@1),
    case lowest_occurrence_common_item(One@2, Other@2) of
        none ->
            gleam@list:concat([Prefix, Suffix]);

        {some, {Item, _, Before_a, After_a, Before_b, After_b}} ->
            gleam@list:concat(
                [Prefix,
                    lcs(lists:reverse(Before_a), lists:reverse(Before_b)),
                    [Item],
                    lcs(After_a, After_b),
                    Suffix]
            )
    end.

-spec histogram(binary(), binary()) -> list(diff_line()).
histogram(One, Other) ->
    One_lines = gleam@string:split(One, <<"\n"/utf8>>),
    Other_lines = gleam@string:split(Other, <<"\n"/utf8>>),
    Lcs = lcs(One_lines, Other_lines),
    match_diff_lines([], Lcs, 1, One_lines, 1, Other_lines).