mutations

ast_children([]) :- !.

ast_children([b(_, _, _) | Cs]) :-
    !,
    ast_children(Cs).

ast_children([IdList | Cs]) :-
    is_id_list(IdList),
    ast_children(Cs).

ast_depth(Ast, Depth) :-
    ast_depth(Ast, 0, Depth), !.

ast_depth(b(Node, _, _), Depth, FinalDepth) :-
    Node =.. [_], !, % Node without any children.
    FinalDepth is Depth + 1.

ast_depth(b(Node, _, _), Depth, FinalDepth) :-
    Node =.. [_Name, Value],
    Value \= b(_,_,_), \+ is_list(Value),
    !, % if Value is not wrapped in b/3 and not a list, it is a value type such as integer(7).
    FinalDepth is Depth + 1.

ast_depth(b(Node, _, _), Depth, FinalDepth) :- !,
    Node =.. [Name, Child|Rest],
    NewDepth is Depth + 1,
    % Special case for constructs which have an identifier list for children.
    ((node_info(Name, _, [FirstChildType | _]), is_ids_type(FirstChildType))
    -> ast_depth(Rest, NewDepth, FinalDepth) % Use one of the other children.
    ; ast_depth(Child, NewDepth, FinalDepth)).

ast_depth([Node | _], Depth, FinalDepth) :-
    % Special case for constructs like general_product which have a list of children.
    ast_depth(Node, Depth, FinalDepth).

ast_types([], [], []) :- !.

ast_types([b(_, T, _) | Cs], [T | Rs], [T | Ts]) :-
    !,
    ast_types(Cs, Rs, Ts).

ast_types([IdList | Cs], [Ids | Rs], [Ids | Ts]) :-
    is_id_list(IdList),
    !,
    ast_types(Cs, Rs, Ts).

bast_node_split(b(Node, Type, Infos), Node, Name, Type, Infos, Children) :-
    Node =.. [Name | NodeChildren],
    % Value nodes do not have a b/3 structure around their values.
    % Things like b(integer(7), _, _) should display as having no children.
    (ast_children(NodeChildren) -> Children = NodeChildren; Children = []).

bounds_for_desired_node(Desired, Depth, _, Depth, Depth) :-
    % Leaves only go to the bottom.
    fuzztypes:is_leaf_node(Desired),
    !.

bounds_for_desired_node(Desired, Depth, _, Depth, Depth) :-
    % primitive types act as leaves too.
    fuzztypes:primitive_type(Desired),
    !.

bounds_for_desired_node(Desired, Depth, RootType, Lower, Upper) :-
    inner_node_lower_bound(Desired, RootType, Lower),
    Upper is Depth - 1. % Cannot be a leaf.

change_children(Node, [], Node) :- !.

change_children(Node, NewChildren, NewNode) :-
    Node =.. [Name|_],
    NewNode =.. [Name|NewChildren].

children_after_mutate_([], _, _, _, Env, Env, []).

children_after_mutate_([M|Ms], Children, Types, Depth, Env, NewEnv, [New|Mutated]) :-
    reuse_or_mutate(Types, Children, M, Depth, Env, InterEnv, New, RemTypes, RemChildren),
    children_after_mutate_(Ms, RemChildren, RemTypes, Depth, InterEnv, NewEnv, Mutated).

children_after_mutation(Children, Types, MutationTypes, Depth, Env, NewEnv, MutatedChildren) :-
    children_after_mutate_(MutationTypes, Children, Types, Depth, Env, NewEnv, MutatedChildren).

children_and_types(b(integer(_), _, _), [], []) :- !.

children_and_types(b(real(_), _, _), [], []) :- !.

children_and_types(b(string(_), _, _), [], []) :- !.

children_and_types(b(identifier(_), _, _), [], []) :- !.

children_and_types(Ast, Children, ChildTypes) :-
    bast_node_split(Ast, _, Name, Type, _, Children),
    node_info(Name, Type, RawChildTypes), % Only needed for id list validation.
    ast_types(Children, RawChildTypes, ChildTypes).

ensure_proper_node(nat_set, integer_set('NAT')) :- !.

ensure_proper_node(nat1_set, integer_set('NAT1')) :- !.

ensure_proper_node(natural_set, integer_set('NATURAL')) :- !.

ensure_proper_node(natural1_set, integer_set('NATURAL1')) :- !.

ensure_proper_node(int_set, integer_set('INT')) :- !.

ensure_proper_node(integer_set, integer_set('INTEGER')) :- !.

ensure_proper_node(N, N).

filter_idlist_children([], _, []) :- !.

filter_idlist_children(Children, RootNode, FilteredChildren) :-
    node_info(RootNode, _, ChildTypes), !,
    filter_idlist_children_(ChildTypes, Children, FilteredChildren).

filter_idlist_children_([], [], []) :- !.

filter_idlist_children_([IdListType|Ts], [_|Cs], Fs) :-
    \+ var(IdListType), IdListType =.. [ids | _], !,
    filter_idlist_children_(Ts, Cs, Fs).

filter_idlist_children_([_|Ts], [C|Cs], [C|Fs]) :-
    filter_idlist_children_(Ts, Cs, Fs).

fuzz_ast_with_subast(SubAst, Depth, SubAstDepth, RootType, Env, NewEnv, Ast) :-
    bast_node_split(SubAst, _, Name, Type, _, _),
    RemDepth is Depth - SubAstDepth + 1,
    (fuzztypes:primary_type(Name), TargetNode = Name
    ; node_by_name(Name, TargetNode)),
    random_path_between_nodes(RootType, TargetNode:Type, RemDepth, Env, Path),
    reverse(Path, PathToRoot),
    fuzz_with_parents_and_siblings(PathToRoot, SubAst, SubAstDepth, Env, NewEnv, Ast).

fuzz_list_or_node(MutationType, D, Env, NewEnv, New) :-
    \+ var(MutationType),
    MutationType = [WrappedType],
    !, % Special case: Generate list of nodes.
    fuzzer:fuzz_list(WrappedType, D, Env, NewEnv, New).

fuzz_list_or_node(MutationType, D, Env, NewEnv, New) :-
    % No children of same type available, generate new one.
    (is_ids_type(MutationType) ->
    fuzzer:fuzz_1_value_type(MutationType, Env, IdsValueType),
    fuzzer:fuzz_value(IdsValueType, Env, NewEnv, New)
    ; fuzzer:fuzz(D, MutationType, Env, NewEnv, New)).

fuzz_or_mutate(Ast, DesiredSubnode, Env, NewEnv, NewAst) :-
    strip_pos(Ast, Rhs), % Remove LHS if it is only additional POs. Fails if none exist.
    !,
    fuzz_or_mutate_(Rhs, DesiredSubnode, Env, NewEnv, NewAst).

fuzz_or_mutate_(Ast, DesiredSubnode, Env, NewEnv, MutatedAst) :-
    mutate_ast(Ast, Env, DesiredSubnode, NewEnv, MutatedAst), % Fails if not possible.
    !.

fuzz_or_mutate_(Ast, DesiredSubnode, Env, NewEnv, MutatedAst) :-
    Ast = b(_, Type, _),
    bf_env:has_option(size, Env, Depth), % TODO: get clean environment when fuzzing new stuff.
    fuzz_with_inner_node(DesiredSubnode, Depth, Type, Env, InterEnv, Fuzzed),
    bf_env:has_option(conjuncts_max, Env, Max),
    (Max == 1 -> MutatedAst = Fuzzed, NewEnv = InterEnv
    ; bf_env:has_option(conjuncts_min, Env, Min),
    NewMin is Min - 1, % We already have one conjunct.
    random(NewMin, Max, Num),
    (Num is 0 -> MutatedAst = Fuzzed, NewEnv = InterEnv
    ;
    fuzz_n_conjuncts(Num, Depth, InterEnv, NewEnv, Conjuncts),
    MutatedAst = b(conjunct(Fuzzed, Conjuncts), Type, []))),
    !.

fuzz_siblings(SiblingInfos, Depth, Env, NewEnv, Siblings) :-
    % Note:
    % fuzz_siblings_/5 is a helper that sorts the SiblingInfos.
    % One element in the infos is assumed to have a bound AST already, the others
    % only have a type-var pair where the var will be bound to a generated Ast.
    % Here, those vars are collected into the list `Asts` and they correspond to the
    % respective element in the list `Types` on the same position.
    % The existing Ast is disregarded in those lists and only present in the `Siblings` list.
    % The Siblings list contains the needs sibling-ASTs in the correct order,
    % however only the already existent AST is bound, the other elements are the free
    % variables from the Asts list. Those will be bound by the fuzz_children/5 call.
   
    % Sketch of what happens:
    % SiblingInfos = [type1-Ast1, type2-Ast2, type3-b(some_ast), type4-Ast4]
    % fuzz_siblings_/5 gives us:
    % Types = [type1, type2, type4]
    % Asts = [Ast1, Ast2, Ast4]
    % Siblings = [Ast1, Ast2, b(some_ast), Ast4]
    % fuzz_children/5 is called over the Types and Asts lists and generates
    % a list of ASTs which corresponds to the Types list.
    % type1 <-> Ast1 = b(ast1)
    % type2 <-> Ast2 = b(ast2)
    % type4 <-> Ast4 = b(ast4)
    % Hence we get Asts = [b(ast1), b(ast2), b(ast4)]
    % and thus also Siblings = [b(ast1), b(ast2), b(some_ast), b(ast4)].
    fuzz_siblings_(SiblingInfos, Types, Asts, Siblings),
    fuzzer:fuzz_children(Types, Depth, Env, NewEnv, Asts).

fuzz_siblings_([], [], [], []).

fuzz_siblings_([Type-Ast|SiblingInfo], [Type | GenTypes], [Ast | GenAsts], [Ast | Siblings]) :-
    var(Ast), % Only fuzz siblings that are yet to be generated.
    !,
    fuzz_siblings_(SiblingInfo, GenTypes, GenAsts, Siblings).

fuzz_siblings_([Type-Ast|SiblingInfo], [Type | GenTypes], [AstList | GenAsts], [Perm | Siblings]) :-
    \+ var(Type), Type = [_],
    !, % If type is wrapped in a list, we need to generate a list of such-typed Asts
    % and put the existing Ast into it (as Ast is ground in this clause).
    FullAstList = [Ast|AstList],
    random_permutation(FullAstList, Perm),
    fuzz_siblings_(SiblingInfo, GenTypes, GenAsts, Siblings).

fuzz_siblings_([_-Ast|SiblingInfo], GenTypes, GenAsts, [Ast|Siblings]) :-
    % Ast exists already; put it onto result set but don't make it part of the generated siblings.
    fuzz_siblings_(SiblingInfo, GenTypes, GenAsts, Siblings).

fuzz_with_inner_node(DesiredNode, Depth, RootType, Env, NewEnv, Result) :-
    % Core idea is to generate a sub-ast from the desired node, then build
    % the parent and siblings around it.
    bounds_for_desired_node(DesiredNode, Depth, RootType, LowerBound, UpperBound),
    NotIncludedUpperBound is UpperBound + 1,
    random(LowerBound, NotIncludedUpperBound, InnerDepth),
    SubAstDepth is Depth - InnerDepth + 1, % Need position counted in reverse from top.
    fuzzer:fuzz_node(DesiredNode, SubAstDepth, Env, InterEnv, SubAst),
    fuzz_ast_with_subast(SubAst, Depth, SubAstDepth, RootType, InterEnv, NewEnv, Ast),
    repair_used_ids('BanditFuzz Mutator', Ast, Result).

fuzz_with_parents_and_siblings([], SubAst, _, Env, Env, SubAst) :- !.

fuzz_with_parents_and_siblings([Name-ParentType|Path], SubAst, SubDepth, Env, NewEnv, Ast) :-
    % If parent type is wrapped in a list, this indicates that we are supposed to
    % be part of a list-valued child of the parent.
    (\+var(ParentType), ParentType = [TrueParentType], ! ; ParentType = TrueParentType),
    node_info(Name, TrueParentType, ChildrenTypes),
    % If subast is wrapped in a list, it means this node contains a list-valued
    % child and the subast is supposed to be part of this list.
    (SubAst = [SubAst2], SubAst2 = b(_, UnwrappedSubAstType, _), SubAstType = [UnwrappedSubAstType]
    ; SubAst = SubAst2, SubAst2 = b(_, SubAstType, _)),
    % Choose random child to be current node.
    length(ChildrenTypes, ChildrenCount),
    length(Children, ChildrenCount), % List with unbound variables corresponding to children by position.
    maplist(pair, ChildrenTypes, Children, ChildrenPairs), % List of ChildType-Child pairs.
    random_member_bt(MemberType-SubAst2, ChildrenPairs), % Binds one of the children to SubAst.
    safe_type_unification(MemberType, SubAstType), % Ensure no pred types unify with unbound variables.
    % Fuzz random siblings.
    ParentDepth is SubDepth + 1,
    restrict_env_if_needed(Name, ParentDepth, Env, LocalEnv, Changed),
    fuzz_siblings(ChildrenPairs, SubDepth, LocalEnv, LocalInterEnv, Siblings),
    restore_available_nodes_when_changed(Changed, Env, LocalInterEnv, InterEnv),
    % Set-up parent node.
    ParentNode =.. [Name|Siblings],
    fuzzer:prepare_info(ParentNode, TrueParentType, ParentInfo),
    Parent = b(ParentNode, TrueParentType, ParentInfo),
    % If type is list, indicate so in recursion.
    (\+var(ParentType), ParentType = [_], !, Parent2 = [Parent] ; Parent2 = Parent),
    fuzz_with_parents_and_siblings(Path, Parent, ParentDepth, InterEnv, NewEnv, Ast).

has_n_matching_nodes(Ast, Subnode, Leaf, N) :-
    (replacement_disallowed(Ast, Subnode)
    -> N = 0
    ; has_n_matching_nodes([Ast], Subnode, Leaf, 0, N)).

has_n_matching_nodes([], _, _, N, N).

has_n_matching_nodes([Ast|Rest], SubnodeInfo, Leaf, CurrCount, N) :-
    is_list(Ast), % Special case.
    !,
    has_n_matching_nodes(Ast, SubnodeInfo, Leaf, CurrCount, InterCount),
    has_n_matching_nodes(Rest, SubnodeInfo, Leaf, InterCount, N).

has_n_matching_nodes([Ast|Rest], SubnodeInfo, Leaf, CurrCount, N) :-
    replacement_disallowed(Ast, SubnodeInfo), !,
    has_n_matching_nodes(Rest, SubnodeInfo, Leaf, CurrCount, N).

has_n_matching_nodes([AST|Rest], Subnode:Type, Leaf, CurrCount, N) :-
    bast_node_split(AST, _, RootNode, AstType, _, Children),
    ( (type_and_leaf_match(Leaf, Children, AstType, Type), RootNode \= Subnode)
    -> NewCount is CurrCount + 1
    ; NewCount = CurrCount),
    filter_idlist_children(Children, RootNode, FilteredChildren),
    append(FilteredChildren, Rest, NewRest),
    has_n_matching_nodes(NewRest, Subnode:Type, Leaf, NewCount, N).

has_places_for_subnode(AST, SubnodeName, N) :-
    % Subnode type?
    (node_by_name(SubnodeName, Subnode), !),
    has_type(Subnode, SubnodeType),
    (is_leaf_node(SubnodeName) -> Leaf = leaf; Leaf = nonleaf),
    has_n_matching_nodes(AST, Subnode:SubnodeType, Leaf, N),
    N > 0.

inner_node_lower_bound(Node, RootType, 1) :-
    node_info(Node, NodeType, _),
    % If root is pred, then we cannot use nodes that are dynamic in type.
    (RootType \== pred -> NodeType = RootType; NodeType == pred),
    !.

inner_node_lower_bound(_, _, 2).

is_id_list([]) :- !.

is_id_list([b(identifier(_), _, _) | Ids]) :-
    is_id_list(Ids).

is_ids_type(Type) :-
    var(Type), !, fail.

is_ids_type(ids) :- !.

is_ids_type(ids(_)).

mutate_ast(AST, Env, DesiredSubnode, NewEnv, Result) :-
    has_places_for_subnode(AST, DesiredSubnode, N),
    % Get random natural number in [1, N].
    UpperLimit is N+1,
    random(1, UpperLimit, Place),
    replace_nth_match(AST, Env, DesiredSubnode, Place, MutatedAST, NewEnv),
    repair_used_ids('BanditFuzz Mutator', MutatedAST, Result).

pair(First, Second, First-Second).

qfuzz_with(DesiredNode, Ast) :-
    N = 4,
    bf_env:env(E),
    fuzz_with_inner_node(DesiredNode, N, pred, E, _, Ast).

random_member_bt(Element, List) :-
    random_permutation(List, Perm),
    member(Element, Perm).

random_path_between_nodes(StartType, _:EndType, 1, _, []) :-
    safe_type_unification(StartType, EndType),
    !.

random_path_between_nodes(StartType, EndNode, Length, Env, [Name-[StartType]|Path]) :-
    \+ var(StartType), StartType = [NestedStartType],
    !, % Special case: We want a list of children.
    random_path_between_nodes(NestedStartType, EndNode, Length, Env, [Name-StartType|Path]).

random_path_between_nodes(StartType, EndNode, Length, Env, [Name-StartType|Path]) :-
    Length > 1,
    % Disallow parents of target node if necessary.
    findall(P, disallowed_child(P, Length, EndNode), NonParents),
    disallow_nodes(NonParents, Env, InterEnv),
    bf_env:allowed_nodes(InterEnv, StartType, Nodes),
    random_member_bt(Node:StartType, Nodes),
    Node =.. [Name|Children],
    random_member_bt(ChildType, Children),
    \+ is_ids_type(ChildType), % Don't path into id lists for quantifiers or else; might be variable though.
    % TODO: What about list types?
    RemainingLength is Length - 1,
    random_path_between_nodes(ChildType, EndNode, RemainingLength, Env, Path).

replace_nth_match(AST, Env, SubnodeName, N, MutatedAST, NewEnv) :-
    node_info(SubnodeName, SubnodeType, _),
    (is_leaf_node(SubnodeName) -> Leaf=leaf; Leaf=nonleaf),
    StartCount = 0,
    replace_nth_match_(AST, (SubnodeName, SubnodeType, Leaf), StartCount, _, N,
    Env, NewEnv, MutatedAST), !.

replace_nth_match_([Ast|Asts], SubnodeInfo, CurrN, OutN, N, Env, NewEnv, Mutates) :-
    !,
    replace_nth_match_in_ast_list([Ast|Asts], SubnodeInfo, CurrN, OutN, N, Env, NewEnv, Mutates).

replace_nth_match_(AST, SubnodeInfo, CurrN, OutN, N, Env, NewEnv, Mutated) :-
    bast_node_split(AST, Node, NodeName, Type, Infos, Children),
    SubnodeInfo = (SubnodeName, SubnodeType, Leaf),
    ( (type_and_leaf_match(Leaf, Children, Type, SubnodeType), NodeName \= SubnodeName)
    -> NewCount is CurrN + 1
    ; NewCount = CurrN),
    (NewCount == N ->
    replace_root_node(AST, SubnodeInfo, Env, NewEnv, Mutated), OutN = -1
    ; (
    children_and_types(AST, Children, ChildTypes),
    maplist(pair, Children, ChildTypes, TypedChildren),
    replace_nth_match_in_children(TypedChildren, SubnodeInfo, NewCount, OutN, N,
    Env, NewEnv, MutatedChildren),
    change_children(Node, MutatedChildren, MutatedNode),
    Mutated = b(MutatedNode, Type, Infos))).

replace_nth_match_in_ast_list([], _, C, C, _, Env, Env, []).

replace_nth_match_in_ast_list([Ast|Asts], SubnodeInfo, CurrN, OutN, N, Env, NewEnv, [Mutate|Mutates]) :-
    replace_nth_match_(Ast, SubnodeInfo, CurrN, InterN, N, Env, EnvInter, Mutate),
    replace_nth_match_in_ast_list(Asts, SubnodeInfo, InterN, OutN, N, EnvInter, NewEnv, Mutates).

replace_nth_match_in_children([], _, C, C, _, Env, Env, []).

replace_nth_match_in_children([C-IdListType|Cs], Subnode, CurrIn, CurrOut, N, Env, NewEnv, [C|Ms]) :-
    \+ var(IdListType), IdListType =.. [ids | _], !,
    replace_nth_match_in_children(Cs, Subnode, CurrIn, CurrOut, N, Env, NewEnv, Ms).

replace_nth_match_in_children([C-_|Cs], Subnode, CurrIn, CurrOut, N, Env, NewEnv, [C|Ms]) :-
    replacement_disallowed(C, Subnode), !,
    replace_nth_match_in_children(Cs, Subnode, CurrIn, CurrOut, N, Env, NewEnv, Ms).

replace_nth_match_in_children([C-_|Cs], Subnode, CurrIn, CurrOut, N, Env, NewEnv, [M|Ms]) :-
    replace_nth_match_(C, Subnode, CurrIn, InterOut, N, Env, EnvInter, M),
    replace_nth_match_in_children(Cs, Subnode, InterOut, CurrOut, N,
    EnvInter, NewEnv, Ms).

replace_root_node(AST, SubnodeInfo, Env, NewEnv, b(Mutated, NewType, Info)) :-
    ast_depth(AST, Depth),
    AST = b(_, _, Info),
    children_and_types(AST, Children, ChildTypes),
    SubnodeInfo = (SubnodeName, NewType, _),
    fuzztypes:node_info(SubnodeName, NewType, SubnodeChildTypes),
    children_after_mutation(Children, ChildTypes, SubnodeChildTypes, Depth, Env, NewEnv,
    MutatedChildren),
    PreparedNode =.. [SubnodeName|MutatedChildren],
    ensure_proper_node(PreparedNode, Mutated).

replacement_disallowed(Ast, Node) :-
    ast_depth(Ast, Level),
    bast_node_split(Ast, _, RootNodeName, _, _, _),
    disallowed_child(RootNodeName, Level, Node).

reuse_or_mutate([], _, MutationType, D, Env, NewEnv, New, [], []) :- !,
    fuzz_list_or_node(MutationType, D, Env, NewEnv, New),
    !.

reuse_or_mutate([T|Ts], [C|Cs], MutationType, _, Env, Env, C, Ts, Cs) :-
    types_unify(T, MutationType), % Need to ensure that pure variables don't unify with ids
    !. % Same type, keep.

reuse_or_mutate([T|Ts], [C|Cs], MutationType, _, Env, NewEnv, NewC, Ts, Cs) :-
    is_ids_type(T),
    is_ids_type(MutationType),
    !, % Non-unifying ID-type.
    reuse_or_mutate_idlist(T, MutationType, C, Env, NewEnv, NewC).

reuse_or_mutate([T|Ts], [C|Cs], MutationType, D, Env, NewEnv, Mutated, [T|NewTs], [C|NewCs]) :-
    % MutationType \= T,
    reuse_or_mutate(Ts, Cs, MutationType, D, Env, NewEnv, Mutated, NewTs, NewCs).

reuse_or_mutate_cross_prod([], _, E, E, []) :- !.

reuse_or_mutate_cross_prod([T | Ts], IdList, Env, NewEnv, [Id | Ids]) :- !,
    reuse_or_mutate_id(IdList, T, Id, Env, InterEnv, RemIds),
    reuse_or_mutate_cross_prod(Ts, RemIds, InterEnv, NewEnv, Ids).

reuse_or_mutate_id([], T, Id, Env, NewEnv, []) :- !,
    new_id_probability(Env, OldProba),
    with_id_probability(Env, 1, LocalEnv),
    fuzzer:fuzz_value(identifier:T, LocalEnv, LocalNewEnv, Id),
    with_id_probability(LocalNewEnv, OldProba, NewEnv).

reuse_or_mutate_id([Id | Ts], T, Id, Env, Env, Ts) :- !,
    Id = b(identifier(_), IdType, _),
    types_unify(IdType, T), !.

reuse_or_mutate_id([UnfitId | Ts], T, Id, Env, NewEnv, [UnfitId | RemIds]) :- !,
    reuse_or_mutate_id(Ts, T, Id, Env, NewEnv, RemIds).

reuse_or_mutate_idlist(ids(_), ids, IdList, Env, Env, IdList) :- !. % Mutation type is less restrictive.

reuse_or_mutate_idlist(_, ids(B), IdList, Env, NewEnv, NewIdList) :-
    fuzzer:safe_cross_prod_of(Env, B, BTypes),
    reuse_or_mutate_cross_prod(BTypes, IdList, Env, NewEnv, NewIdList).

safe_type_unification(T1, T2) :-
    T1 == pred, !, T2 == pred.

safe_type_unification(_, T2) :-
    T2 == pred, !, fail. % We know already that T1 \== pred.

safe_type_unification(T1, T2) :-
    var(T1), T2 \== pred, T1 = T2, !.

safe_type_unification(T, T).

type_and_leaf_match(leaf, [], Type1, Type2) :-
    safe_type_unification(Type1, Type2).

type_and_leaf_match(nonleaf, [_|_], Type1, Type2) :-
    safe_type_unification(Type1, Type2).

types_unify(Type1, Type2) :-
    unifies_as_ids_type(Type1, Type2), !.

types_unify(Type1, Type2) :-
    \+ is_ids_type(Type1),
    \+ is_ids_type(Type2),
    safe_type_unification(Type1, Type2).

unifies_as_ids_type(Type1, Type2) :-
    is_ids_type(Type1),
    is_ids_type(Type2),
    % Note: ids(A) can only unify with ids(A), not ids and not ids(B) for B \= A.
    (Type1 = Type2).