metamon

-module(metamon@generator@tree).
-compile([no_auto_import, nowarn_unused_vars, nowarn_unused_function, nowarn_nomatch, inline]).
-define(FILEPATH, "src/metamon/generator/tree.gleam").
-export([no_shrinks/0, shrinks_from_list/1, map_shrinks/2, append_shrinks/2, shrinks_take/2, shrinks_to_list/1, shrinks_find/2, singleton/1, unfold/2, from_list/2, map/2, bind/2, zip/2, outline/3, filter_shrinks/2, filter/2]).
-export_type([shrinks/1, shrink_step/1, tree/1]).

-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(
    " A lazy rose tree: a value paired with an on-demand stream of \"smaller\"\n"
    " alternatives. Generators in metamon return `Tree(a)` instead of bare\n"
    " values so shrinking is always available without separate plumbing.\n"
    "\n"
    " The lazy stream type `Shrinks(a)` is defined locally instead of using\n"
    " an external lazy-list library, keeping metamon's runtime dependencies\n"
    " limited to `gleam_stdlib`.\n"
).

-opaque shrinks(EIL) :: {shrinks, fun(() -> shrink_step(EIL))}.

-type shrink_step(EIM) :: done | {more, EIM, shrinks(EIM)}.

-type tree(EIN) :: {tree, EIN, shrinks(tree(EIN))}.

-file("src/metamon/generator/tree.gleam", 37).
?DOC(" An empty shrink stream.\n").
-spec no_shrinks() -> shrinks(any()).
no_shrinks() ->
    {shrinks, fun() -> done end}.

-file("src/metamon/generator/tree.gleam", 43).
?DOC(
    " Build a `Shrinks(a)` from a list. Useful when the shrink alternatives\n"
    " are statically known (e.g. integer halving).\n"
).
-spec shrinks_from_list(list(EIQ)) -> shrinks(EIQ).
shrinks_from_list(Items) ->
    case Items of
        [] ->
            {shrinks, fun() -> done end};

        [First | Rest] ->
            {shrinks, fun() -> {more, First, shrinks_from_list(Rest)} end}
    end.

-file("src/metamon/generator/tree.gleam", 52).
?DOC(" Map a function over every element of a `Shrinks(a)` lazily.\n").
-spec map_shrinks(shrinks(EIT), fun((EIT) -> EIV)) -> shrinks(EIV).
map_shrinks(Stream, F) ->
    {shrinks, fun() -> case (erlang:element(2, Stream))() of
                done ->
                    done;

                {more, Head, Tail} ->
                    {more, F(Head), map_shrinks(Tail, F)}
            end end}.

-file("src/metamon/generator/tree.gleam", 63).
?DOC(
    " Concatenate two `Shrinks(a)` streams. The right side is only consulted\n"
    " once the left is exhausted.\n"
).
-spec append_shrinks(shrinks(EIX), shrinks(EIX)) -> shrinks(EIX).
append_shrinks(Left, Right) ->
    {shrinks, fun() -> case (erlang:element(2, Left))() of
                done ->
                    (erlang:element(2, Right))();

                {more, Head, Tail} ->
                    {more, Head, append_shrinks(Tail, Right)}
            end end}.

-file("src/metamon/generator/tree.gleam", 92).
?DOC(" Force the first `n` elements of a stream into a list.\n").
-spec shrinks_take(shrinks(EJH), integer()) -> list(EJH).
shrinks_take(Stream, N) ->
    case N =< 0 of
        true ->
            [];

        false ->
            case (erlang:element(2, Stream))() of
                done ->
                    [];

                {more, Head, Tail} ->
                    [Head | shrinks_take(Tail, N - 1)]
            end
    end.

-file("src/metamon/generator/tree.gleam", 106).
?DOC(
    " Force the entire stream into a list. Use only on streams known to be\n"
    " finite — generator shrink streams generally are, but be careful with\n"
    " infinite expansions.\n"
).
-spec shrinks_to_list(shrinks(EJK)) -> list(EJK).
shrinks_to_list(Stream) ->
    case (erlang:element(2, Stream))() of
        done ->
            [];

        {more, Head, Tail} ->
            [Head | shrinks_to_list(Tail)]
    end.

-file("src/metamon/generator/tree.gleam", 115).
?DOC(
    " Find the first element satisfying `predicate`, or `Error(Nil)` if no\n"
    " such element exists in the (finite) stream.\n"
).
-spec shrinks_find(shrinks(EJN), fun((EJN) -> boolean())) -> {ok, EJN} |
    {error, nil}.
shrinks_find(Stream, Predicate) ->
    case (erlang:element(2, Stream))() of
        done ->
            {error, nil};

        {more, Head, Tail} ->
            case Predicate(Head) of
                true ->
                    {ok, Head};

                false ->
                    shrinks_find(Tail, Predicate)
            end
    end.

-file("src/metamon/generator/tree.gleam", 130).
?DOC(" A leaf tree with no shrink alternatives.\n").
-spec singleton(EJR) -> tree(EJR).
singleton(Value) ->
    {tree, Value, no_shrinks()}.

-file("src/metamon/generator/tree.gleam", 136).
?DOC(
    " Build a tree from a value and an `expand` function that produces direct\n"
    " child values. Each child is recursively expanded with the same function.\n"
).
-spec unfold(EJT, fun((EJT) -> list(EJT))) -> tree(EJT).
unfold(Value, Expand) ->
    {tree,
        Value,
        begin
            _pipe = shrinks_from_list(Expand(Value)),
            map_shrinks(_pipe, fun(_capture) -> unfold(_capture, Expand) end)
        end}.

-file("src/metamon/generator/tree.gleam", 145).
?DOC(" Build a tree from a value and a pre-computed list of sub-trees.\n").
-spec from_list(EJW, list(tree(EJW))) -> tree(EJW).
from_list(Value, Shrinks) ->
    {tree, Value, shrinks_from_list(Shrinks)}.

-file("src/metamon/generator/tree.gleam", 151).
?DOC(
    " Map a function over every value in the tree, preserving the shrink\n"
    " structure.\n"
).
-spec map(tree(EKA), fun((EKA) -> EKC)) -> tree(EKC).
map(Tree, F) ->
    {tree,
        F(erlang:element(2, Tree)),
        map_shrinks(
            erlang:element(3, Tree),
            fun(_capture) -> map(_capture, F) end
        )}.

-file("src/metamon/generator/tree.gleam", 160).
?DOC(
    " Monadic bind. Each value's continuation produces its own tree, and the\n"
    " returned tree shrinks both the outer (via the original shrinks) and\n"
    " the inner (via the continuation tree's shrinks). Outer shrinks come\n"
    " first to prefer simplifying the seed-driven structure before rerunning\n"
    " the continuation.\n"
).
-spec bind(tree(EKE), fun((EKE) -> tree(EKG))) -> tree(EKG).
bind(Tree, K) ->
    Inner = K(erlang:element(2, Tree)),
    Outer_shrinks = map_shrinks(
        erlang:element(3, Tree),
        fun(_capture) -> bind(_capture, K) end
    ),
    {tree,
        erlang:element(2, Inner),
        append_shrinks(Outer_shrinks, erlang:element(3, Inner))}.

-file("src/metamon/generator/tree.gleam", 184).
?DOC(
    " Combine two trees pairwise. Used to give independent generators a clean\n"
    " product shrink: shrink the left first, then the right. This preserves\n"
    " the \"shrink one component while holding the other\" property that makes\n"
    " counter-examples easier to read.\n"
).
-spec zip(tree(EKM), tree(EKO)) -> tree({EKM, EKO}).
zip(Left, Right) ->
    Left_shrinks = map_shrinks(
        erlang:element(3, Left),
        fun(L) -> zip(L, Right) end
    ),
    Right_shrinks = map_shrinks(
        erlang:element(3, Right),
        fun(R) -> zip(Left, R) end
    ),
    {tree,
        {erlang:element(2, Left), erlang:element(2, Right)},
        append_shrinks(Left_shrinks, Right_shrinks)}.

-file("src/metamon/generator/tree.gleam", 195).
?DOC(
    " Force the tree into a list of values up to `depth` levels deep, taking\n"
    " at most `breadth` shrinks per level. Used for inspection in tests.\n"
).
-spec outline(tree(EKR), integer(), integer()) -> list(EKR).
outline(Tree, Depth, Breadth) ->
    case Depth =< 0 of
        true ->
            [erlang:element(2, Tree)];

        false ->
            Direct = shrinks_take(erlang:element(3, Tree), Breadth),
            Nested = gleam@list:flat_map(
                Direct,
                fun(Child) -> outline(Child, Depth - 1, Breadth) end
            ),
            [erlang:element(2, Tree) | Nested]
    end.

-file("src/metamon/generator/tree.gleam", 80).
-spec filter_step(shrinks(EJE), fun((EJE) -> boolean())) -> shrink_step(EJE).
filter_step(Stream, Predicate) ->
    case (erlang:element(2, Stream))() of
        done ->
            done;

        {more, Head, Tail} ->
            case Predicate(Head) of
                true ->
                    {more, Head, filter_shrinks(Tail, Predicate)};

                false ->
                    filter_step(Tail, Predicate)
            end
    end.

-file("src/metamon/generator/tree.gleam", 73).
?DOC(" Lazily drop elements that fail `predicate`.\n").
-spec filter_shrinks(shrinks(EJB), fun((EJB) -> boolean())) -> shrinks(EJB).
filter_shrinks(Stream, Predicate) ->
    {shrinks, fun() -> filter_step(Stream, Predicate) end}.

-file("src/metamon/generator/tree.gleam", 172).
?DOC(
    " Drop tree nodes that fail `predicate`. The root is assumed to satisfy\n"
    " the predicate (callers must ensure this; otherwise the result has no\n"
    " meaningful \"current value\").\n"
).
-spec filter(tree(EKJ), fun((EKJ) -> boolean())) -> tree(EKJ).
filter(Tree, Predicate) ->
    Kept_shrinks = begin
        _pipe = erlang:element(3, Tree),
        _pipe@1 = filter_shrinks(
            _pipe,
            fun(Child) -> Predicate(erlang:element(2, Child)) end
        ),
        map_shrinks(_pipe@1, fun(_capture) -> filter(_capture, Predicate) end)
    end,
    {tree, erlang:element(2, Tree), Kept_shrinks}.