-module(gliff@internal@patience).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/gliff/internal/patience.gleam").
-export([diff/2]).
-export_type([match/0]).
-if(?OTP_RELEASE >= 27).
-define(MODULEDOC(Str), -moduledoc(Str)).
-define(DOC(Str), -doc(Str)).
-else.
-define(MODULEDOC(Str), -compile([])).
-define(DOC(Str), -compile([])).
-endif.
?MODULEDOC(false).
-type match() :: {match, integer(), integer(), binary()}.
-file("src/gliff/internal/patience.gleam", 48).
?DOC(false).
-spec count_occurrences(list(binary()), gleam@dict:dict(binary(), integer())) -> gleam@dict:dict(binary(), integer()).
count_occurrences(Lines, Acc) ->
case Lines of
[] ->
Acc;
[Line | Rest] ->
Count = case gleam_stdlib:map_get(Acc, Line) of
{ok, N} ->
N + 1;
{error, _} ->
1
end,
count_occurrences(Rest, gleam@dict:insert(Acc, Line, Count))
end.
-file("src/gliff/internal/patience.gleam", 64).
?DOC(false).
-spec index_lines(
list(binary()),
integer(),
gleam@dict:dict(binary(), integer())
) -> gleam@dict:dict(binary(), integer()).
index_lines(Lines, Idx, Acc) ->
case Lines of
[] ->
Acc;
[Line | Rest] ->
index_lines(Rest, Idx + 1, gleam@dict:insert(Acc, Line, Idx))
end.
-file("src/gliff/internal/patience.gleam", 33).
?DOC(false).
-spec find_unique(list(binary())) -> gleam@dict:dict(binary(), integer()).
find_unique(Lines) ->
Counts = count_occurrences(Lines, maps:new()),
Indexed = index_lines(Lines, 0, maps:new()),
gleam@dict:fold(
Counts,
maps:new(),
fun(Acc, Key, Count) -> case Count =:= 1 of
true ->
case gleam_stdlib:map_get(Indexed, Key) of
{ok, Idx} ->
gleam@dict:insert(Acc, Key, Idx);
{error, _} ->
Acc
end;
false ->
Acc
end end
).
-file("src/gliff/internal/patience.gleam", 113).
?DOC(false).
-spec insert_into_tails(
list({integer(), list(match())}),
match(),
list({integer(), list(match())})
) -> list({integer(), list(match())}).
insert_into_tails(Tails, M, Acc) ->
case Tails of
[] ->
lists:reverse([{erlang:element(3, M), [M]} | Acc]);
[{Tail_val, Seq} | Rest] ->
case erlang:element(3, M) =< Tail_val of
true ->
New_seq = case Acc of
[] ->
[M];
[{_, Prev_seq} | _] ->
[M | Prev_seq]
end,
lists:append(
lists:reverse([{erlang:element(3, M), New_seq} | Acc]),
Rest
);
false ->
insert_into_tails(Rest, M, [{Tail_val, Seq} | Acc])
end
end.
-file("src/gliff/internal/patience.gleam", 96).
?DOC(false).
-spec lis_loop(list(match()), list({integer(), list(match())})) -> list(match()).
lis_loop(Remaining, Tails) ->
case Remaining of
[] ->
case gleam@list:last(Tails) of
{ok, {_, Seq}} ->
lists:reverse(Seq);
{error, _} ->
[]
end;
[M | Rest] ->
New_tails = insert_into_tails(Tails, M, []),
lis_loop(Rest, New_tails)
end.
-file("src/gliff/internal/patience.gleam", 88).
?DOC(false).
-spec longest_increasing_subsequence(list(match())) -> list(match()).
longest_increasing_subsequence(Matches) ->
case Matches of
[] ->
[];
[Only] ->
[Only];
_ ->
lis_loop(Matches, [])
end.
-file("src/gliff/internal/patience.gleam", 168).
?DOC(false).
-spec slice(list(EXU), integer(), integer()) -> list(EXU).
slice(Items, From, To) ->
_pipe = Items,
_pipe@1 = gleam@list:drop(_pipe, From),
gleam@list:take(_pipe@1, To - From).
-file("src/gliff/internal/patience.gleam", 174).
?DOC(false).
-spec prepend_reversed(list(EXX), list(EXX)) -> list(EXX).
prepend_reversed(Items, Onto) ->
case Items of
[] ->
Onto;
[H | T] ->
prepend_reversed(T, [H | Onto])
end.
-file("src/gliff/internal/patience.gleam", 135).
?DOC(false).
-spec diff_between_anchors(
list(binary()),
list(binary()),
list(match()),
integer(),
integer(),
list(gliff@types:raw_edit())
) -> list(gliff@types:raw_edit()).
diff_between_anchors(Old, New, Anchors, Old_pos, New_pos, Acc) ->
case Anchors of
[] ->
Old_rest = gleam@list:drop(Old, Old_pos),
New_rest = gleam@list:drop(New, New_pos),
Tail_edits = gliff@internal@myers:diff(Old_rest, New_rest),
prepend_reversed(Tail_edits, Acc);
[{match, Old_idx, New_idx, Value} | Rest_anchors] ->
Old_before = slice(Old, Old_pos, Old_idx),
New_before = slice(New, New_pos, New_idx),
Gap_edits = gliff@internal@myers:diff(Old_before, New_before),
Acc1 = prepend_reversed(Gap_edits, Acc),
Acc2 = [{raw_equal, Value} | Acc1],
diff_between_anchors(
Old,
New,
Rest_anchors,
Old_idx + 1,
New_idx + 1,
Acc2
)
end.
-file("src/gliff/internal/patience.gleam", 181).
?DOC(false).
-spec compare_int(integer(), integer()) -> gleam@order:order().
compare_int(A, B) ->
case A < B of
true ->
lt;
false ->
case A =:= B of
true ->
eq;
false ->
gt
end
end.
-file("src/gliff/internal/patience.gleam", 75).
?DOC(false).
-spec find_matches(
gleam@dict:dict(binary(), integer()),
gleam@dict:dict(binary(), integer())
) -> list(match()).
find_matches(Old_unique, New_unique) ->
_pipe = gleam@dict:fold(
Old_unique,
[],
fun(Acc, Line, Old_idx) ->
case gleam_stdlib:map_get(New_unique, Line) of
{ok, New_idx} ->
[{match, Old_idx, New_idx, Line} | Acc];
{error, _} ->
Acc
end
end
),
gleam@list:sort(
_pipe,
fun(A, B) -> compare_int(erlang:element(2, A), erlang:element(2, B)) end
).
-file("src/gliff/internal/patience.gleam", 7).
?DOC(false).
-spec diff(list(binary()), list(binary())) -> list(gliff@types:raw_edit()).
diff(Old, New) ->
case {Old, New} of
{[], []} ->
[];
{[], _} ->
gleam@list:map(New, fun(Field@0) -> {raw_insert, Field@0} end);
{_, []} ->
gleam@list:map(Old, fun(Field@0) -> {raw_delete, Field@0} end);
{_, _} ->
Old_unique = find_unique(Old),
New_unique = find_unique(New),
Matches = find_matches(Old_unique, New_unique),
case Matches of
[] ->
gliff@internal@myers:diff(Old, New);
_ ->
Lis = longest_increasing_subsequence(Matches),
_pipe = diff_between_anchors(Old, New, Lis, 0, 0, []),
lists:reverse(_pipe)
end
end.
