birdie

-module(birdie@internal@diff).
-compile([no_auto_import, nowarn_ignored, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-export([histogram/2]).
-export_type([diff_line/0, diff_line_kind/0, occurs/1]).
-moduledoc(false).

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

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

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

-file("src/birdie/internal/diff.gleam", 23).
-spec match_diff_lines(list(diff_line()), list(binary()), integer(), list(binary()), integer(), list(binary())) -> list(diff_line()).
-doc(false).
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",
                file => ~"src/birdie/internal/diff.gleam",
                module => ~"birdie/internal/diff",
                function => ~"match_diff_lines",
                line => 68
            });

        {[_ | _], _, []} ->
            erlang:error(#{
                gleam_error => panic,
                message => ~"unreachable",
                file => ~"src/birdie/internal/diff.gleam",
                module => ~"birdie/internal/diff",
                function => ~"match_diff_lines",
                line => 68
            })
    end.

-file("src/birdie/internal/diff.gleam", 176).
-spec sum_occurrences(occurs(LNS), occurs(LNS)) -> occurs(LNS).
-doc(false).
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",
                file => ~"src/birdie/internal/diff.gleam",
                module => ~"birdie/internal/diff",
                function => ~"sum_occurrences",
                line => 185
            })
    end.

-file("src/birdie/internal/diff.gleam", 152).
-spec histogram_add(gleam@dict:dict(LNG, occurs(LNG)), list(LNG), fun((integer(), list(LNG), list(LNG)) -> occurs(LNG)), list(LNG)) -> gleam@dict:dict(LNG, occurs(LNG)).
-doc(false).
histogram_add(Histogram, List, To_occurrence, Reverse_prefix) ->
    case List of
        [] ->
            Histogram;

        [First | Rest] ->
            _pipe = begin
                gleam@dict:upsert(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)
            end,
            histogram_add(_pipe, Rest, To_occurrence, [First | Reverse_prefix])
    end.

-file("src/birdie/internal/diff.gleam", 123).
-spec lowest_occurrence_common_item(list(LMY), list(LMY)) -> gleam@option:option({LMY, integer(), list(LMY), list(LMY), list(LMY), list(LMY)}).
-doc(false).
lowest_occurrence_common_item(One, Other) ->
    Histogram = begin
        _pipe = histogram_add(maps:new(), One, fun(_value, _value@1, _value@2) ->
            {one, _value, _value@1, _value@2}
        end, []),
        histogram_add(_pipe, Other, fun(_value@3, _value@4, _value@5) ->
            {other, _value@3, _value@4, _value@5}
        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).

-file("src/birdie/internal/diff.gleam", 202).
-spec do_pop_common_prefix(list(LOC), list(LOC), list(LOC)) -> {list(LOC), list(LOC), list(LOC)}.
-doc(false).
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.

-file("src/birdie/internal/diff.gleam", 217).
-spec pop_common_suffix(list(LOJ), list(LOJ)) -> {list(LOJ), list(LOJ), list(LOJ)}.
-doc(false).
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)}.

-file("src/birdie/internal/diff.gleam", 194).
-spec pop_common_prefix(list(LNW), list(LNW)) -> {list(LNW), list(LNW), list(LNW)}.
-doc(false).
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}.

-file("src/birdie/internal/diff.gleam", 76).
-spec lcs(list(LMU), list(LMU)) -> list(LMU).
-doc(false).
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 ->
            lists:append([Prefix, Suffix]);

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

-file("src/birdie/internal/diff.gleam", 16).
-spec histogram(binary(), binary()) -> list(diff_line()).
-doc(false).
histogram(One, Other) ->
    One_lines = gleam@string:split(One, ~"\n"),
    Other_lines = gleam@string:split(Other, ~"\n"),
    Lcs = lcs(One_lines, Other_lines),
    match_diff_lines([], Lcs, 1, One_lines, 1, Other_lines).