-module(gliff@internal@myers).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/gliff/internal/myers.gleam").
-export([diff_with_budget/3, diff/2]).
-export_type([find_path_error/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 find_path_error() :: exhausted | budget_exceeded.
-file("src/gliff/internal/myers.gleam", 60).
?DOC(false).
-spec common_prefix(list(binary()), list(binary()), list(binary())) -> list(binary()).
common_prefix(A, B, Acc) ->
case {A, B} of
{[Ah | At], [Bh | Bt]} when Ah =:= Bh ->
common_prefix(At, Bt, [Ah | Acc]);
{_, _} ->
lists:reverse(Acc)
end.
-file("src/gliff/internal/myers.gleam", 86).
?DOC(false).
-spec common_suffix_loop(
list(binary()),
list(binary()),
integer(),
list(binary())
) -> list(binary()).
common_suffix_loop(A_rev, B_rev, Remaining, Acc) ->
case {Remaining, A_rev, B_rev} of
{0, _, _} ->
Acc;
{_, [Ah | At], [Bh | Bt]} when Ah =:= Bh ->
common_suffix_loop(At, Bt, Remaining - 1, [Ah | Acc]);
{_, _, _} ->
Acc
end.
-file("src/gliff/internal/myers.gleam", 71).
?DOC(false).
-spec common_suffix(list(binary()), list(binary()), integer(), integer()) -> list(binary()).
common_suffix(A, B, A_len, B_len) ->
Min_len = case A_len < B_len of
true ->
A_len;
false ->
B_len
end,
A_rev = lists:reverse(A),
B_rev = lists:reverse(B),
common_suffix_loop(A_rev, B_rev, Min_len, []).
-file("src/gliff/internal/myers.gleam", 33).
?DOC(false).
-spec trim_common(list(binary()), list(binary()), integer(), integer()) -> {list(gliff@types:raw_edit()),
list(binary()),
list(binary()),
list(gliff@types:raw_edit())}.
trim_common(Old, New, Old_len, New_len) ->
Prefix = common_prefix(Old, New, []),
Prefix_len = erlang:length(Prefix),
Old_rest = gleam@list:drop(Old, Prefix_len),
New_rest = gleam@list:drop(New, Prefix_len),
Old_rest_len = Old_len - Prefix_len,
New_rest_len = New_len - Prefix_len,
Suffix = common_suffix(Old_rest, New_rest, Old_rest_len, New_rest_len),
Suffix_len = erlang:length(Suffix),
Old_mid = gleam@list:take(Old_rest, Old_rest_len - Suffix_len),
New_mid = gleam@list:take(New_rest, New_rest_len - Suffix_len),
Prefix_edits = gleam@list:map(
Prefix,
fun(Field@0) -> {raw_equal, Field@0} end
),
Suffix_edits = gleam@list:map(
Suffix,
fun(Field@0) -> {raw_equal, Field@0} end
),
{Prefix_edits, Old_mid, New_mid, Suffix_edits}.
-file("src/gliff/internal/myers.gleam", 225).
?DOC(false).
-spec follow_diagonal(
gleam@dict:dict(integer(), binary()),
gleam@dict:dict(integer(), binary()),
integer(),
integer(),
integer(),
integer()
) -> {integer(), integer()}.
follow_diagonal(Old_arr, New_arr, Old_len, New_len, X, Y) ->
case (X < Old_len) andalso (Y < New_len) of
true ->
case {gleam_stdlib:map_get(Old_arr, X),
gleam_stdlib:map_get(New_arr, Y)} of
{{ok, Ov}, {ok, Nv}} when Ov =:= Nv ->
follow_diagonal(
Old_arr,
New_arr,
Old_len,
New_len,
X + 1,
Y + 1
);
{_, _} ->
{X, Y}
end;
false ->
{X, Y}
end.
-file("src/gliff/internal/myers.gleam", 326).
?DOC(false).
-spec emit_equals(
gleam@dict:dict(integer(), binary()),
integer(),
integer(),
list(gliff@types:raw_edit())
) -> list(gliff@types:raw_edit()).
emit_equals(Old_arr, From, To, Acc) ->
case From >= To of
true ->
Acc;
false ->
Last_idx = To - 1,
case gleam_stdlib:map_get(Old_arr, Last_idx) of
{ok, Val} ->
emit_equals(
Old_arr,
From,
Last_idx,
[{raw_equal, Val} | Acc]
);
{error, _} ->
Acc
end
end.
-file("src/gliff/internal/myers.gleam", 344).
?DOC(false).
-spec get_trace_at(list(gleam@dict:dict(integer(), integer())), integer()) -> gleam@dict:dict(integer(), integer()).
get_trace_at(Trace, Idx) ->
case gleam@list:drop(Trace, Idx) of
[V | _] ->
V;
[] ->
maps:new()
end.
-file("src/gliff/internal/myers.gleam", 351).
?DOC(false).
-spec get_v(gleam@dict:dict(integer(), integer()), integer()) -> integer().
get_v(V, K) ->
gleam@result:unwrap(gleam_stdlib:map_get(V, K), 0).
-file("src/gliff/internal/myers.gleam", 185).
?DOC(false).
-spec explore_diagonals(
gleam@dict:dict(integer(), binary()),
gleam@dict:dict(integer(), binary()),
integer(),
integer(),
integer(),
integer(),
gleam@dict:dict(integer(), integer())
) -> {ok, {gleam@dict:dict(integer(), integer()), boolean()}} | {error, nil}.
explore_diagonals(Old_arr, New_arr, Old_len, New_len, D, K, V) ->
case K > D of
true ->
{ok, {V, false}};
false ->
X = case K =:= - D of
true ->
get_v(V, K + 1);
false ->
case K =:= D of
true ->
get_v(V, K - 1) + 1;
false ->
Vkm1 = get_v(V, K - 1),
Vkp1 = get_v(V, K + 1),
case Vkm1 < Vkp1 of
true ->
Vkp1;
false ->
Vkm1 + 1
end
end
end,
Y = X - K,
{Final_x, Final_y} = follow_diagonal(
Old_arr,
New_arr,
Old_len,
New_len,
X,
Y
),
New_v = gleam@dict:insert(V, K, Final_x),
case (Final_x >= Old_len) andalso (Final_y >= New_len) of
true ->
{ok, {New_v, true}};
false ->
explore_diagonals(
Old_arr,
New_arr,
Old_len,
New_len,
D,
K + 2,
New_v
)
end
end.
-file("src/gliff/internal/myers.gleam", 146).
?DOC(false).
-spec find_path(
gleam@dict:dict(integer(), binary()),
gleam@dict:dict(integer(), binary()),
integer(),
integer(),
integer(),
integer(),
gleam@dict:dict(integer(), integer()),
list(gleam@dict:dict(integer(), integer())),
gliff@internal@budget:budget()
) -> {ok, list(gleam@dict:dict(integer(), integer()))} |
{error, find_path_error()}.
find_path(Old_arr, New_arr, Old_len, New_len, Max_d, D, V, Trace, B) ->
case D > Max_d of
true ->
{error, exhausted};
false ->
case gliff@internal@budget:tick(B) of
{error, _} ->
{error, budget_exceeded};
{ok, New_b} ->
case explore_diagonals(
Old_arr,
New_arr,
Old_len,
New_len,
D,
- D,
V
) of
{ok, {New_v, true}} ->
{ok, lists:reverse([New_v | Trace])};
{ok, {New_v@1, false}} ->
find_path(
Old_arr,
New_arr,
Old_len,
New_len,
Max_d,
D + 1,
New_v@1,
[New_v@1 | Trace],
New_b
);
{error, _} ->
{error, exhausted}
end
end
end.
-file("src/gliff/internal/myers.gleam", 308).
?DOC(false).
-spec find_prev_k(gleam@dict:dict(integer(), integer()), integer(), integer()) -> integer().
find_prev_k(Prev_v, K, D) ->
case K =:= - D of
true ->
K + 1;
false ->
case K =:= D of
true ->
K - 1;
false ->
Vkm1 = get_v(Prev_v, K - 1),
Vkp1 = get_v(Prev_v, K + 1),
case Vkm1 < Vkp1 of
true ->
K + 1;
false ->
K - 1
end
end
end.
-file("src/gliff/internal/myers.gleam", 256).
?DOC(false).
-spec backtrack_from(
list(gleam@dict:dict(integer(), integer())),
gleam@dict:dict(integer(), binary()),
gleam@dict:dict(integer(), binary()),
integer(),
integer(),
integer(),
list(gliff@types:raw_edit())
) -> list(gliff@types:raw_edit()).
backtrack_from(Trace, Old_arr, New_arr, D, X, Y, Acc) ->
case D < 0 of
true ->
Acc;
false ->
K = X - Y,
End_x = X,
case D =:= 0 of
true ->
emit_equals(Old_arr, 0, End_x, Acc);
false ->
Prev_v = get_trace_at(Trace, D - 1),
Prev_k = find_prev_k(Prev_v, K, D),
Prev_x = get_v(Prev_v, Prev_k),
Prev_y = Prev_x - Prev_k,
Mid_x = case Prev_k =:= (K - 1) of
true ->
Prev_x + 1;
false ->
Prev_x
end,
Acc1 = emit_equals(Old_arr, Mid_x, End_x, Acc),
Acc2 = case Prev_k =:= (K - 1) of
true ->
case gleam_stdlib:map_get(Old_arr, Prev_x) of
{ok, Val} ->
[{raw_delete, Val} | Acc1];
{error, _} ->
Acc1
end;
false ->
case gleam_stdlib:map_get(New_arr, Prev_y) of
{ok, Val@1} ->
[{raw_insert, Val@1} | Acc1];
{error, _} ->
Acc1
end
end,
backtrack_from(
Trace,
Old_arr,
New_arr,
D - 1,
Prev_x,
Prev_y,
Acc2
)
end
end.
-file("src/gliff/internal/myers.gleam", 244).
?DOC(false).
-spec backtrack(
list(gleam@dict:dict(integer(), integer())),
gleam@dict:dict(integer(), binary()),
gleam@dict:dict(integer(), binary()),
integer(),
integer()
) -> list(gliff@types:raw_edit()).
backtrack(Trace, Old_arr, New_arr, Old_len, New_len) ->
Trace_len = erlang:length(Trace),
Max_d = Trace_len - 1,
backtrack_from(Trace, Old_arr, New_arr, Max_d, Old_len, New_len, []).
-file("src/gliff/internal/myers.gleam", 355).
?DOC(false).
-spec list_to_dict(list(binary()), integer()) -> gleam@dict:dict(integer(), binary()).
list_to_dict(Items, Idx) ->
case Items of
[] ->
maps:new();
[H | T] ->
gleam@dict:insert(list_to_dict(T, Idx + 1), Idx, H)
end.
-file("src/gliff/internal/myers.gleam", 116).
?DOC(false).
-spec myers_shortest_edit(
list(binary()),
list(binary()),
integer(),
integer(),
gliff@internal@budget:budget()
) -> {list(gliff@types:raw_edit()), boolean()}.
myers_shortest_edit(Old, New, Old_len, New_len, B) ->
Max_d = Old_len + New_len,
Old_arr = list_to_dict(Old, 0),
New_arr = list_to_dict(New, 0),
V_init = maps:from_list([{1, 0}]),
case find_path(Old_arr, New_arr, Old_len, New_len, Max_d, 0, V_init, [], B) of
{ok, Trace} ->
{backtrack(Trace, Old_arr, New_arr, Old_len, New_len), true};
{error, exhausted} ->
{lists:append(
gleam@list:map(
Old,
fun(Field@0) -> {raw_delete, Field@0} end
),
gleam@list:map(
New,
fun(Field@0) -> {raw_insert, Field@0} end
)
),
false};
{error, budget_exceeded} ->
{lists:append(
gleam@list:map(
Old,
fun(Field@0) -> {raw_delete, Field@0} end
),
gleam@list:map(
New,
fun(Field@0) -> {raw_insert, Field@0} end
)
),
false}
end.
-file("src/gliff/internal/myers.gleam", 100).
?DOC(false).
-spec compute_diff(
list(binary()),
list(binary()),
gliff@internal@budget:budget()
) -> {list(gliff@types:raw_edit()), boolean()}.
compute_diff(Old, New, B) ->
Old_len = erlang:length(Old),
New_len = erlang:length(New),
case {Old_len, New_len} of
{0, 0} ->
{[], true};
{0, _} ->
{gleam@list:map(New, fun(Field@0) -> {raw_insert, Field@0} end),
true};
{_, 0} ->
{gleam@list:map(Old, fun(Field@0) -> {raw_delete, Field@0} end),
true};
{_, _} ->
myers_shortest_edit(Old, New, Old_len, New_len, B)
end.
-file("src/gliff/internal/myers.gleam", 12).
?DOC(false).
-spec diff_with_budget(
list(binary()),
list(binary()),
gliff@internal@budget:budget()
) -> {list(gliff@types:raw_edit()), boolean()}.
diff_with_budget(Old, New, B) ->
Old_len = erlang:length(Old),
New_len = erlang:length(New),
case {Old_len, New_len} of
{0, 0} ->
{[], true};
{0, _} ->
{gleam@list:map(New, fun(Field@0) -> {raw_insert, Field@0} end),
true};
{_, 0} ->
{gleam@list:map(Old, fun(Field@0) -> {raw_delete, Field@0} end),
true};
{_, _} ->
{Prefix, Old_mid, New_mid, Suffix} = trim_common(
Old,
New,
Old_len,
New_len
),
{Mid_edits, Complete} = compute_diff(Old_mid, New_mid, B),
{lists:append([Prefix, Mid_edits, Suffix]), Complete}
end.
-file("src/gliff/internal/myers.gleam", 7).
?DOC(false).
-spec diff(list(binary()), list(binary())) -> list(gliff@types:raw_edit()).
diff(Old, New) ->
{Edits, _} = diff_with_budget(Old, New, unlimited),
Edits.
