-module(textmetrics@diff).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/textmetrics/diff.gleam").
-export([unified_options/2, with_context_lines/2, with_old_name/2, with_new_name/2, old_name/1, new_name/1, context_lines/1, myers/2, to_unified/2, patience/2]).
-export_type([unified_options_error/0, unified_options/0, myers_result/1, line_event/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(
" Diff algorithms over arbitrary lists.\n"
"\n"
" [`myers`](#myers) implements the O(ND) algorithm of Myers (1986)\n"
" and produces an optimal edit script.\n"
" [`patience`](#patience) implements Bram Cohen's patience diff over\n"
" `List(String)`, which often yields more readable diffs for source\n"
" code with moved blocks.\n"
" [`to_unified`](#to_unified) renders an edit script of strings in\n"
" the POSIX unified-diff format.\n"
).
-type unified_options_error() :: {context_lines_negative, integer()}.
-opaque unified_options() :: {unified_options, binary(), binary(), integer()}.
-type myers_result(DOV) :: {myers_result,
list(gleam@dict:dict(integer(), integer())),
integer(),
integer()} |
{gleam_phantom, DOV}.
-type line_event() :: {context_event, binary(), integer(), integer()} |
{delete_event, binary(), integer(), integer()} |
{insert_event, binary(), integer(), integer()}.
-file("src/textmetrics/diff.gleam", 37).
?DOC(
" Default constructor: `context_lines = 3`, matching POSIX\n"
" `diff -u3`.\n"
).
-spec unified_options(binary(), binary()) -> unified_options().
unified_options(Old_name, New_name) ->
{unified_options, Old_name, New_name, 3}.
-file("src/textmetrics/diff.gleam", 46).
?DOC(
" Override the context-line count. Returns\n"
" `Error(ContextLinesNegative(n))` when `n < 0`.\n"
).
-spec with_context_lines(unified_options(), integer()) -> {ok,
unified_options()} |
{error, unified_options_error()}.
with_context_lines(Options, N) ->
case N < 0 of
true ->
{error, {context_lines_negative, N}};
false ->
{ok,
{unified_options,
erlang:element(2, Options),
erlang:element(3, Options),
N}}
end.
-file("src/textmetrics/diff.gleam", 62).
?DOC(" Override the old-file label.\n").
-spec with_old_name(unified_options(), binary()) -> unified_options().
with_old_name(Options, Name) ->
{unified_options,
Name,
erlang:element(3, Options),
erlang:element(4, Options)}.
-file("src/textmetrics/diff.gleam", 71).
?DOC(" Override the new-file label.\n").
-spec with_new_name(unified_options(), binary()) -> unified_options().
with_new_name(Options, Name) ->
{unified_options,
erlang:element(2, Options),
Name,
erlang:element(4, Options)}.
-file("src/textmetrics/diff.gleam", 80).
?DOC(" Read the old-file label.\n").
-spec old_name(unified_options()) -> binary().
old_name(Options) ->
erlang:element(2, Options).
-file("src/textmetrics/diff.gleam", 85).
?DOC(" Read the new-file label.\n").
-spec new_name(unified_options()) -> binary().
new_name(Options) ->
erlang:element(3, Options).
-file("src/textmetrics/diff.gleam", 90).
?DOC(" Read the context-line count.\n").
-spec context_lines(unified_options()) -> integer().
context_lines(Options) ->
erlang:element(4, Options).
-file("src/textmetrics/diff.gleam", 186).
-spec follow_snake(
gleam@dict:dict(integer(), DQA),
gleam@dict:dict(integer(), DQA),
integer(),
integer(),
integer(),
integer()
) -> {integer(), integer()}.
follow_snake(Old_arr, New_arr, M, N, X, Y) ->
case (X < M) andalso (Y < N) of
false ->
{X, Y};
true ->
case {gleam_stdlib:map_get(Old_arr, X),
gleam_stdlib:map_get(New_arr, Y)} of
{{ok, Ax}, {ok, By}} ->
case Ax =:= By of
true ->
follow_snake(Old_arr, New_arr, M, N, X + 1, Y + 1);
false ->
{X, Y}
end;
{_, _} ->
{X, Y}
end
end.
-file("src/textmetrics/diff.gleam", 156).
-spec myers_d_step(
gleam@dict:dict(integer(), DPN),
gleam@dict:dict(integer(), DPN),
integer(),
integer(),
integer(),
integer(),
gleam@dict:dict(integer(), integer())
) -> {ok, {gleam@dict:dict(integer(), integer()), integer(), integer()}} |
{error, gleam@dict:dict(integer(), integer())}.
myers_d_step(Old_arr, New_arr, M, N, D, K, V) ->
case K > D of
true ->
{error, V};
false ->
V_minus = gleam@result:unwrap(gleam_stdlib:map_get(V, K - 1), -1),
V_plus = gleam@result:unwrap(gleam_stdlib:map_get(V, K + 1), -1),
From_above = (K =:= - D) orelse ((K /= D) andalso (V_minus < V_plus)),
X = case From_above of
true ->
V_plus;
false ->
V_minus + 1
end,
Y = X - K,
{Fx, Fy} = follow_snake(Old_arr, New_arr, M, N, X, Y),
New_v = gleam@dict:insert(V, K, Fx),
case (Fx >= M) andalso (Fy >= N) of
true ->
{ok, {New_v, Fx, Fy}};
false ->
myers_d_step(Old_arr, New_arr, M, N, D, K + 2, New_v)
end
end.
-file("src/textmetrics/diff.gleam", 125).
-spec myers_search(
gleam@dict:dict(integer(), DPC),
gleam@dict:dict(integer(), DPC),
integer(),
integer(),
integer(),
integer(),
gleam@dict:dict(integer(), integer()),
list(gleam@dict:dict(integer(), integer()))
) -> myers_result(DPC).
myers_search(Old_arr, New_arr, M, N, Max_d, D, V, Trace_acc) ->
Trace_acc_2 = [V | Trace_acc],
case D > Max_d of
true ->
{myers_result, Trace_acc_2, M, N};
false ->
case myers_d_step(Old_arr, New_arr, M, N, D, - D, V) of
{ok, {_, Fx, Fy}} ->
{myers_result, Trace_acc_2, Fx, Fy};
{error, Updated_v} ->
myers_search(
Old_arr,
New_arr,
M,
N,
Max_d,
D + 1,
Updated_v,
Trace_acc_2
)
end
end.
-file("src/textmetrics/diff.gleam", 254).
-spec walk_diag_back(
gleam@dict:dict(integer(), DQP),
integer(),
integer(),
integer(),
integer(),
list(textmetrics@edit:edit(DQP))
) -> {integer(), integer(), list(textmetrics@edit:edit(DQP))}.
walk_diag_back(Old_arr, X, Y, Lo_x, Lo_y, Acc) ->
case (X > Lo_x) andalso (Y > Lo_y) of
false ->
{X, Y, Acc};
true ->
case gleam_stdlib:map_get(Old_arr, X - 1) of
{ok, Item} ->
walk_diag_back(
Old_arr,
X - 1,
Y - 1,
Lo_x,
Lo_y,
[{equal, Item} | Acc]
);
{error, _} ->
{X, Y, Acc}
end
end.
-file("src/textmetrics/diff.gleam", 273).
-spec walk_origin_back(
gleam@dict:dict(integer(), DQU),
integer(),
integer(),
list(textmetrics@edit:edit(DQU))
) -> list(textmetrics@edit:edit(DQU)).
walk_origin_back(Old_arr, X, Y, Acc) ->
case (X > 0) andalso (Y > 0) of
false ->
Acc;
true ->
case gleam_stdlib:map_get(Old_arr, X - 1) of
{ok, Item} ->
walk_origin_back(
Old_arr,
X - 1,
Y - 1,
[{equal, Item} | Acc]
);
{error, _} ->
Acc
end
end.
-file("src/textmetrics/diff.gleam", 208).
-spec myers_backtrack(
gleam@dict:dict(integer(), DQF),
gleam@dict:dict(integer(), DQF),
list(gleam@dict:dict(integer(), integer())),
integer(),
integer(),
integer(),
list(textmetrics@edit:edit(DQF))
) -> list(textmetrics@edit:edit(DQF)).
myers_backtrack(Old_arr, New_arr, Trace, D, X, Y, Acc) ->
case D of
0 ->
walk_origin_back(Old_arr, X, Y, Acc);
_ ->
case Trace of
[V | Rest] ->
K = X - Y,
V_minus = gleam@result:unwrap(
gleam_stdlib:map_get(V, K - 1),
-1
),
V_plus = gleam@result:unwrap(
gleam_stdlib:map_get(V, K + 1),
-1
),
From_above = (K =:= - D) orelse ((K /= D) andalso (V_minus < V_plus)),
Prev_k = case From_above of
true ->
K + 1;
false ->
K - 1
end,
Prev_x = gleam@result:unwrap(
gleam_stdlib:map_get(V, Prev_k),
0
),
Prev_y = Prev_x - Prev_k,
{X2, Y2, Acc2} = walk_diag_back(
Old_arr,
X,
Y,
Prev_x,
Prev_y,
Acc
),
{Next_x, Next_y, Acc3} = case {X2 > Prev_x, Y2 > Prev_y} of
{true, _} ->
case gleam_stdlib:map_get(Old_arr, X2 - 1) of
{ok, Item} ->
{X2 - 1, Y2, [{delete, Item} | Acc2]};
{error, _} ->
{Prev_x, Prev_y, Acc2}
end;
{false, true} ->
case gleam_stdlib:map_get(New_arr, Y2 - 1) of
{ok, Item@1} ->
{X2, Y2 - 1, [{insert, Item@1} | Acc2]};
{error, _} ->
{Prev_x, Prev_y, Acc2}
end;
{false, false} ->
{Prev_x, Prev_y, Acc2}
end,
myers_backtrack(
Old_arr,
New_arr,
Rest,
D - 1,
Next_x,
Next_y,
Acc3
);
[] ->
walk_origin_back(Old_arr, X, Y, Acc)
end
end.
-file("src/textmetrics/diff.gleam", 371).
-spec count_occurrences(list(binary())) -> gleam@dict:dict(binary(), integer()).
count_occurrences(Lines) ->
gleam@list:fold(
Lines,
maps:new(),
fun(Acc, Line) -> gleam@dict:upsert(Acc, Line, fun(Opt) -> case Opt of
{some, C} ->
C + 1;
none ->
1
end end) end
).
-file("src/textmetrics/diff.gleam", 382).
-spec first_index_of(list(binary())) -> gleam@dict:dict(binary(), integer()).
first_index_of(Lines) ->
gleam@list:index_fold(
Lines,
maps:new(),
fun(Acc, Line, I) -> case gleam@dict:has_key(Acc, Line) of
true ->
Acc;
false ->
gleam@dict:insert(Acc, Line, I)
end end
).
-file("src/textmetrics/diff.gleam", 354).
-spec find_unique_pairs(list(binary()), list(binary())) -> list({integer(),
integer()}).
find_unique_pairs(Old, New) ->
Old_counts = count_occurrences(Old),
New_counts = count_occurrences(New),
New_index_of = first_index_of(New),
_pipe = gleam@list:index_fold(
Old,
[],
fun(Acc, Line, Oi) ->
case {gleam_stdlib:map_get(Old_counts, Line),
gleam_stdlib:map_get(New_counts, Line),
gleam_stdlib:map_get(New_index_of, Line)} of
{{ok, 1}, {ok, 1}, {ok, Ni}} ->
[{Oi, Ni} | Acc];
{_, _, _} ->
Acc
end
end
),
lists:reverse(_pipe).
-file("src/textmetrics/diff.gleam", 422).
-spec scan_predecessors(
gleam@dict:dict(integer(), {integer(), integer()}),
gleam@dict:dict(integer(), integer()),
integer(),
integer(),
integer(),
integer()
) -> {integer(), integer()}.
scan_predecessors(Arr, Dp, I, J, Best_len, Best_prev) ->
case J >= I of
true ->
{Best_len, Best_prev};
false ->
Pi = case gleam_stdlib:map_get(Arr, I) of
{ok, P} ->
P;
_ ->
{0, 0}
end,
Pj = case gleam_stdlib:map_get(Arr, J) of
{ok, P@1} ->
P@1;
_ ->
{0, 0}
end,
{_, Ni} = Pi,
{_, Nj} = Pj,
Dp_j = gleam@result:unwrap(gleam_stdlib:map_get(Dp, J), 0),
Candidate = Dp_j + 1,
case (Nj < Ni) andalso (Candidate > Best_len) of
true ->
scan_predecessors(Arr, Dp, I, J + 1, Candidate, J);
false ->
scan_predecessors(Arr, Dp, I, J + 1, Best_len, Best_prev)
end
end.
-file("src/textmetrics/diff.gleam", 404).
-spec build_lis_tables(
gleam@dict:dict(integer(), {integer(), integer()}),
integer(),
integer(),
gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), integer())
) -> {gleam@dict:dict(integer(), integer()),
gleam@dict:dict(integer(), integer())}.
build_lis_tables(Arr, N, I, Dp, Prev) ->
case I >= N of
true ->
{Dp, Prev};
false ->
{Best_len, Best_prev} = scan_predecessors(Arr, Dp, I, 0, 1, -1),
Dp2 = gleam@dict:insert(Dp, I, Best_len),
Prev2 = gleam@dict:insert(Prev, I, Best_prev),
build_lis_tables(Arr, N, I + 1, Dp2, Prev2)
end.
-file("src/textmetrics/diff.gleam", 453).
-spec find_max_dp(
gleam@dict:dict(integer(), integer()),
integer(),
integer(),
integer(),
integer()
) -> integer().
find_max_dp(Dp, N, I, Best_len, Best_idx) ->
case I >= N of
true ->
Best_idx;
false ->
V = gleam@result:unwrap(gleam_stdlib:map_get(Dp, I), 0),
case V > Best_len of
true ->
find_max_dp(Dp, N, I + 1, V, I);
false ->
find_max_dp(Dp, N, I + 1, Best_len, Best_idx)
end
end.
-file("src/textmetrics/diff.gleam", 472).
-spec reconstruct_lis(
gleam@dict:dict(integer(), {integer(), integer()}),
gleam@dict:dict(integer(), integer()),
integer(),
list({integer(), integer()})
) -> list({integer(), integer()}).
reconstruct_lis(Arr, Prev, Idx, Acc) ->
case Idx < 0 of
true ->
Acc;
false ->
Pair = case gleam_stdlib:map_get(Arr, Idx) of
{ok, P} ->
P;
_ ->
{0, 0}
end,
Prev_idx = gleam@result:unwrap(gleam_stdlib:map_get(Prev, Idx), -1),
reconstruct_lis(Arr, Prev, Prev_idx, [Pair | Acc])
end.
-file("src/textmetrics/diff.gleam", 509).
-spec has_changes(list(textmetrics@edit:edit(binary()))) -> boolean().
has_changes(Script) ->
case Script of
[] ->
false;
[{equal, _} | Rest] ->
has_changes(Rest);
_ ->
true
end.
-file("src/textmetrics/diff.gleam", 523).
-spec script_to_events(
list(textmetrics@edit:edit(binary())),
integer(),
integer(),
list(line_event())
) -> list(line_event()).
script_to_events(Script, Old_pos, New_pos, Acc) ->
case Script of
[] ->
lists:reverse(Acc);
[{equal, Line} | Rest] ->
script_to_events(
Rest,
Old_pos + 1,
New_pos + 1,
[{context_event, Line, Old_pos, New_pos} | Acc]
);
[{delete, Line@1} | Rest@1] ->
script_to_events(
Rest@1,
Old_pos + 1,
New_pos,
[{delete_event, Line@1, Old_pos, New_pos} | Acc]
);
[{insert, Line@2} | Rest@2] ->
script_to_events(
Rest@2,
Old_pos,
New_pos + 1,
[{insert_event, Line@2, Old_pos, New_pos} | Acc]
)
end.
-file("src/textmetrics/diff.gleam", 572).
-spec find_change_indices(
gleam@dict:dict(integer(), line_event()),
integer(),
integer(),
list(integer())
) -> list(integer()).
find_change_indices(Events_arr, N, I, Acc) ->
case I >= N of
true ->
Acc;
false ->
New_acc = case gleam_stdlib:map_get(Events_arr, I) of
{ok, {insert_event, _, _, _}} ->
[I | Acc];
{ok, {delete_event, _, _, _}} ->
[I | Acc];
_ ->
Acc
end,
find_change_indices(Events_arr, N, I + 1, New_acc)
end.
-file("src/textmetrics/diff.gleam", 598).
-spec merge_ranges_loop(
list({integer(), integer()}),
{integer(), integer()},
list({integer(), integer()})
) -> list({integer(), integer()}).
merge_ranges_loop(Remaining, Current, Acc) ->
case Remaining of
[] ->
lists:reverse([Current | Acc]);
[{Lo, Hi} | Rest] ->
{C_lo, C_hi} = Current,
case Lo =< (C_hi + 1) of
true ->
merge_ranges_loop(
Rest,
{C_lo, gleam@int:max(C_hi, Hi)},
Acc
);
false ->
merge_ranges_loop(Rest, {Lo, Hi}, [Current | Acc])
end
end.
-file("src/textmetrics/diff.gleam", 591).
-spec merge_ranges(list({integer(), integer()})) -> list({integer(), integer()}).
merge_ranges(Ranges) ->
case Ranges of
[] ->
[];
[First | Rest] ->
merge_ranges_loop(Rest, First, [])
end.
-file("src/textmetrics/diff.gleam", 615).
-spec slice_events(
gleam@dict:dict(integer(), line_event()),
integer(),
integer(),
list(line_event())
) -> list(line_event()).
slice_events(Events_arr, I, End, Acc) ->
case I >= End of
true ->
lists:reverse(Acc);
false ->
case gleam_stdlib:map_get(Events_arr, I) of
{ok, E} ->
slice_events(Events_arr, I + 1, End, [E | Acc]);
{error, _} ->
lists:reverse(Acc)
end
end.
-file("src/textmetrics/diff.gleam", 639).
-spec format_range(integer(), integer()) -> binary().
format_range(Start, Count) ->
case Count of
1 ->
erlang:integer_to_binary(Start);
_ ->
<<<<(erlang:integer_to_binary(Start))/binary, ","/utf8>>/binary,
(erlang:integer_to_binary(Count))/binary>>
end.
-file("src/textmetrics/diff.gleam", 652).
-spec old_start_count(list(line_event())) -> {integer(), integer()}.
old_start_count(Events) ->
Folded = gleam@list:fold(
Events,
{-1, 0},
fun(Acc, E) ->
{Start, Count} = Acc,
case E of
{context_event, _, Op, _} ->
case Start of
-1 ->
{Op, Count + 1};
_ ->
{Start, Count + 1}
end;
{delete_event, _, Op@1, _} ->
case Start of
-1 ->
{Op@1, Count + 1};
_ ->
{Start, Count + 1}
end;
{insert_event, _, _, _} ->
Acc
end
end
),
{S, C} = Folded,
case S of
-1 ->
case Events of
[{insert_event, _, Op@2, _} | _] ->
{gleam@int:max(0, Op@2 - 1), 0};
_ ->
{0, 0}
end;
_ ->
{S, C}
end.
-file("src/textmetrics/diff.gleam", 681).
-spec new_start_count(list(line_event())) -> {integer(), integer()}.
new_start_count(Events) ->
Folded = gleam@list:fold(
Events,
{-1, 0},
fun(Acc, E) ->
{Start, Count} = Acc,
case E of
{context_event, _, _, Np} ->
case Start of
-1 ->
{Np, Count + 1};
_ ->
{Start, Count + 1}
end;
{insert_event, _, _, Np@1} ->
case Start of
-1 ->
{Np@1, Count + 1};
_ ->
{Start, Count + 1}
end;
{delete_event, _, _, _} ->
Acc
end
end
),
{S, C} = Folded,
case S of
-1 ->
case Events of
[{delete_event, _, _, Np@2} | _] ->
{gleam@int:max(0, Np@2 - 1), 0};
_ ->
{0, 0}
end;
_ ->
{S, C}
end.
-file("src/textmetrics/diff.gleam", 646).
-spec compute_hunk_meta(list(line_event())) -> {integer(),
integer(),
integer(),
integer()}.
compute_hunk_meta(Events) ->
{Os, Oc} = old_start_count(Events),
{Ns, Nc} = new_start_count(Events),
{Os, Oc, Ns, Nc}.
-file("src/textmetrics/diff.gleam", 710).
-spec event_to_line(line_event()) -> binary().
event_to_line(E) ->
case E of
{context_event, Line, _, _} ->
<<<<" "/utf8, Line/binary>>/binary, "\n"/utf8>>;
{delete_event, Line@1, _, _} ->
<<<<"-"/utf8, Line@1/binary>>/binary, "\n"/utf8>>;
{insert_event, Line@2, _, _} ->
<<<<"+"/utf8, Line@2/binary>>/binary, "\n"/utf8>>
end.
-file("src/textmetrics/diff.gleam", 631).
-spec emit_hunk(list(line_event())) -> binary().
emit_hunk(Events) ->
{Os, Oc, Ns, Nc} = compute_hunk_meta(Events),
Header = <<<<<<<<"@@ -"/utf8, (format_range(Os, Oc))/binary>>/binary,
" +"/utf8>>/binary,
(format_range(Ns, Nc))/binary>>/binary,
" @@\n"/utf8>>,
Body = begin
_pipe = gleam@list:map(Events, fun event_to_line/1),
erlang:list_to_binary(_pipe)
end,
<<Header/binary, Body/binary>>.
-file("src/textmetrics/diff.gleam", 722).
-spec list_to_dict_loop(list(DTS), integer(), gleam@dict:dict(integer(), DTS)) -> gleam@dict:dict(integer(), DTS).
list_to_dict_loop(Items, I, Acc) ->
case Items of
[] ->
Acc;
[X | Rest] ->
list_to_dict_loop(Rest, I + 1, gleam@dict:insert(Acc, I, X))
end.
-file("src/textmetrics/diff.gleam", 718).
-spec list_to_dict(list(DTO)) -> gleam@dict:dict(integer(), DTO).
list_to_dict(Items) ->
list_to_dict_loop(Items, 0, maps:new()).
-file("src/textmetrics/diff.gleam", 101).
?DOC(
" Optimal edit script transforming `old` into `new`, computed by the\n"
" Myers (1986) O(ND) algorithm.\n"
"\n"
" The script's `cost` (Insert + Delete) equals `levenshtein_list`\n"
" of `old` vs `new` with substitution counted as one insert plus\n"
" one delete. Tie-breaking prefers earlier deletions over insertions,\n"
" matching GNU `diff(1)`.\n"
).
-spec myers(list(DOY), list(DOY)) -> list(textmetrics@edit:edit(DOY)).
myers(Old, New) ->
M = erlang:length(Old),
N = erlang:length(New),
case {M, N} of
{0, 0} ->
[];
{0, _} ->
gleam@list:map(New, fun(Item) -> {insert, Item} end);
{_, 0} ->
gleam@list:map(Old, fun(Item@1) -> {delete, Item@1} end);
{_, _} ->
Old_arr = list_to_dict(Old),
New_arr = list_to_dict(New),
Initial_v = gleam@dict:insert(maps:new(), 1, 0),
Max_d = M + N,
{myers_result, Trace, Fx, Fy} = myers_search(
Old_arr,
New_arr,
M,
N,
Max_d,
0,
Initial_v,
[]
),
Trace_count = erlang:length(Trace),
myers_backtrack(
Old_arr,
New_arr,
Trace,
Trace_count - 1,
Fx,
Fy,
[]
)
end.
-file("src/textmetrics/diff.gleam", 391).
-spec longest_increasing_subseq(list({integer(), integer()})) -> list({integer(),
integer()}).
longest_increasing_subseq(Pairs) ->
N = erlang:length(Pairs),
case N of
0 ->
[];
_ ->
Arr = list_to_dict(Pairs),
{Dp, Prev} = build_lis_tables(Arr, N, 0, maps:new(), maps:new()),
Best_idx = find_max_dp(Dp, N, 0, 0, 0),
reconstruct_lis(Arr, Prev, Best_idx, [])
end.
-file("src/textmetrics/diff.gleam", 549).
-spec build_hunks(list(line_event()), integer()) -> list(list(line_event())).
build_hunks(Events, Context_lines) ->
Events_arr = list_to_dict(Events),
N = erlang:length(Events),
Change_indices = begin
_pipe = find_change_indices(Events_arr, N, 0, []),
lists:reverse(_pipe)
end,
case Change_indices of
[] ->
[];
_ ->
Ranges = gleam@list:map(
Change_indices,
fun(I) ->
{gleam@int:max(0, I - Context_lines),
gleam@int:min(N - 1, I + Context_lines)}
end
),
Merged = merge_ranges(Ranges),
gleam@list:map(
Merged,
fun(Range) ->
{Lo, Hi} = Range,
slice_events(Events_arr, Lo, Hi + 1, [])
end
)
end.
-file("src/textmetrics/diff.gleam", 495).
?DOC(
" Render an edit script of strings in POSIX unified-diff format.\n"
"\n"
" When the script contains no `Insert` or `Delete` steps the output\n"
" is exactly the empty string.\n"
).
-spec to_unified(list(textmetrics@edit:edit(binary())), unified_options()) -> binary().
to_unified(Script, Options) ->
case has_changes(Script) of
false ->
<<""/utf8>>;
true ->
Header = <<<<<<<<"--- "/utf8, (erlang:element(2, Options))/binary>>/binary,
"\n+++ "/utf8>>/binary,
(erlang:element(3, Options))/binary>>/binary,
"\n"/utf8>>,
Events = script_to_events(Script, 1, 1, []),
Hunks = build_hunks(Events, erlang:element(4, Options)),
Body = begin
_pipe = gleam@list:map(Hunks, fun emit_hunk/1),
erlang:list_to_binary(_pipe)
end,
<<Header/binary, Body/binary>>
end.
-file("src/textmetrics/diff.gleam", 316).
-spec patience_segments(
list(binary()),
list(binary()),
list({integer(), integer()}),
list(list(textmetrics@edit:edit(binary())))
) -> list(textmetrics@edit:edit(binary())).
patience_segments(Old, New, Anchors, Acc) ->
case Anchors of
[] ->
Sub = case {Old, New} of
{[], []} ->
[];
{_, _} ->
patience(Old, New)
end,
lists:append(lists:reverse([Sub | Acc]));
[{Oi, Ni} | Rest] ->
{Seg_old, Anchor_and_after_old} = gleam@list:split(Old, Oi),
{Seg_new, Anchor_and_after_new} = gleam@list:split(New, Ni),
Sub@1 = patience(Seg_old, Seg_new),
case {Anchor_and_after_old, Anchor_and_after_new} of
{[Anchor_old | Rest_old], [_ | Rest_new]} ->
Anchor_step = [{equal, Anchor_old}],
New_anchors = gleam@list:map(
Rest,
fun(P) ->
{O, N} = P,
{(O - Oi) - 1, (N - Ni) - 1}
end
),
patience_segments(
Rest_old,
Rest_new,
New_anchors,
[Anchor_step, Sub@1 | Acc]
);
{_, _} ->
lists:append(lists:reverse([Sub@1 | Acc]))
end
end.
-file("src/textmetrics/diff.gleam", 295).
?DOC(
" Patience diff (Bram Cohen). Identifies anchor lines that are unique\n"
" in both inputs, computes the longest increasing subsequence of\n"
" those anchors, and recursively diffs the surrounding segments.\n"
" Falls back to [`myers`](#myers) at leaves where no unique anchors\n"
" exist. Operates on `List(String)`.\n"
).
-spec patience(list(binary()), list(binary())) -> list(textmetrics@edit:edit(binary())).
patience(Old, New) ->
case {Old, New} of
{[], []} ->
[];
{[], _} ->
gleam@list:map(New, fun(Item) -> {insert, Item} end);
{_, []} ->
gleam@list:map(Old, fun(Item@1) -> {delete, Item@1} end);
{_, _} ->
Pairs = find_unique_pairs(Old, New),
case Pairs of
[] ->
myers(Old, New);
_ ->
Anchors = longest_increasing_subseq(Pairs),
case Anchors of
[] ->
myers(Old, New);
_ ->
patience_segments(Old, New, Anchors, [])
end
end
end.
