1/*  Part of SWI-Prolog
    2
    3    Author:        Jan Wielemaker
    4    E-mail:        J.Wielemaker@vu.nl
    5    WWW:           http://www.swi-prolog.org
    6    Copyright (c) 2008-2025, University of Amsterdam,
    7                             VU University
    8                             SWI-Prolog Solutions b.v.
    9    Amsterdam All rights reserved.
   10
   11    Redistribution and use in source and binary forms, with or without
   12    modification, are permitted provided that the following conditions
   13    are met:
   14
   15    1. Redistributions of source code must retain the above copyright
   16       notice, this list of conditions and the following disclaimer.
   17
   18    2. Redistributions in binary form must reproduce the above copyright
   19       notice, this list of conditions and the following disclaimer in
   20       the documentation and/or other materials provided with the
   21       distribution.
   22
   23    THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   24    "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   25    LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
   26    FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
   27    COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
   28    INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
   29    BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
   30    LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
   31    CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   32    LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
   33    ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   34    POSSIBILITY OF SUCH DAMAGE.
   35*/
   36
   37:- module(terms,
   38          [ term_hash/2,                % @Term, -HashKey
   39            term_hash/4,                % @Term, +Depth, +Range, -HashKey
   40            term_size/2,                % @Term, -Size
   41            term_variables/2,           % @Term, -Variables
   42            term_variables/3,           % @Term, -Variables, +Tail
   43            variant/2,                  % @Term1, @Term2
   44            subsumes/2,                 % +Generic, @Specific
   45            subsumes_chk/2,             % +Generic, @Specific
   46            cyclic_term/1,              % @Term
   47            acyclic_term/1,             % @Term
   48            term_subsumer/3,            % +Special1, +Special2, -General
   49            term_factorized/3,          % +Term, -Skeleton, -Subsitution
   50            mapargs/3,                  % :Goal, ?Term1, ?Term2
   51            mapsubterms/3,              % :Goal, ?Term1, ?Term2
   52            mapsubterms_var/3,          % :Goal, ?Term1, ?Term2
   53            foldsubterms/4,             % :Goal, +Term, +State0, -State
   54            foldsubterms/5,             % :Goal, +Term1, ?Term2, +State0, -State
   55            same_functor/2,             % ?Term1, ?Term2
   56            same_functor/3,             % ?Term1, ?Term2, -Arity
   57            same_functor/4              % ?Term1, ?Term2, ?Name, ?Arity
   58          ]).   59
   60:- meta_predicate
   61    mapargs(2,?,?),
   62    mapsubterms(2,?,?),
   63    mapsubterms_var(2,?,?),
   64    foldsubterms(3,+,+,-),
   65    foldsubterms(4,+,?,+,-).   66
   67:- autoload(library(rbtrees),
   68	    [ rb_empty/1,
   69	      rb_lookup/3,
   70	      rb_insert/4,
   71	      rb_new/1,
   72	      rb_visit/2,
   73	      ord_list_to_rbtree/2,
   74	      rb_update/5
   75	    ]).   76:- autoload(library(error), [instantiation_error/1]).   77
   78
   79/** <module> Term manipulation
   80
   81Compatibility library for term manipulation  predicates. Most predicates
   82in this library are provided as SWI-Prolog built-ins.
   83
   84@compat YAP, SICStus, Quintus.  Not all versions of this library define
   85        exactly the same set of predicates, but defined predicates are
   86        compatible.
   87*/
   88
   89%!  term_size(@Term, -Size) is det.
   90%
   91%   True if Size is the size in _cells_   occupied by Term on the global
   92%   (term) stack. A  _cell_  is  8   bytes.  The  calculation  does take
   93%   _sharing_ into account and handles _cycles_ correctly. For example:
   94%
   95%   ```
   96%   ?- A = a(1,2,3), term_size(A,S).
   97%   S = 4.
   98%   ?- A = a(1,2,3), term_size(a(A,A),S).
   99%   S = 7.
  100%   ?- term_size(a(a(1,2,3), a(1,2,3)), S).
  101%   S = 11.
  102%   ```
  103%
  104%   Note that small objects such as atoms  and small integers have a
  105%   size 0. Space is allocated for   floats, large integers, strings
  106%   and compound terms.
  107
  108term_size(Term, Size) :-
  109    '$term_size'(Term, _, Size).
  110
  111%!  variant(@Term1, @Term2) is semidet.
  112%
  113%   Same as SWI-Prolog =|Term1 =@= Term2|=.
  114
  115variant(X, Y) :-
  116    X =@= Y.
  117
  118%!  subsumes_chk(@Generic, @Specific)
  119%
  120%   True if Generic can be made equivalent to Specific without
  121%   changing Specific.
  122%
  123%   @deprecated Replace by subsumes_term/2.
  124
  125subsumes_chk(Generic, Specific) :-
  126    subsumes_term(Generic, Specific).
  127
  128%!  subsumes(+Generic, @Specific)
  129%
  130%   True  if  Generic  is  unified   to  Specific  without  changing
  131%   Specific.
  132%
  133%   @deprecated It turns out that calls to this predicate almost
  134%   always should have used subsumes_term/2.  Also the name is
  135%   misleading.  In case this is really needed, one is adviced to
  136%   follow subsumes_term/2 with an explicit unification.
  137
  138subsumes(Generic, Specific) :-
  139    subsumes_term(Generic, Specific),
  140    Generic = Specific.
  141
  142%!  term_subsumer(+Special1, +Special2, -General) is det.
  143%
  144%   General is the most specific term   that  is a generalisation of
  145%   Special1 and Special2. The  implementation   can  handle  cyclic
  146%   terms.
  147%
  148%   @compat SICStus
  149%   @author Inspired by LOGIC.PRO by Stephen Muggleton
  150
  151%       It has been rewritten by  Jan   Wielemaker  to use the YAP-based
  152%       red-black-trees as mapping rather than flat  lists and use arg/3
  153%       to map compound terms rather than univ and lists.
  154
  155term_subsumer(S1, S2, G) :-
  156    cyclic_term(S1),
  157    cyclic_term(S2),
  158    !,
  159    rb_empty(Map),
  160    lgg_safe(S1, S2, G, Map, _).
  161term_subsumer(S1, S2, G) :-
  162    rb_empty(Map),
  163    lgg(S1, S2, G, Map, _).
  164
  165lgg(S1, S2, G, Map0, Map) :-
  166    (   S1 == S2
  167    ->  G = S1,
  168        Map = Map0
  169    ;   compound(S1),
  170        compound(S2),
  171        functor(S1, Name, Arity),
  172        functor(S2, Name, Arity)
  173    ->  functor(G, Name, Arity),
  174        lgg(0, Arity, S1, S2, G, Map0, Map)
  175    ;   rb_lookup(S1+S2, G0, Map0)
  176    ->  G = G0,
  177        Map = Map0
  178    ;   rb_insert(Map0, S1+S2, G, Map)
  179    ).
  180
  181lgg(Arity, Arity, _, _, _, Map, Map) :- !.
  182lgg(I0, Arity, S1, S2, G, Map0, Map) :-
  183    I is I0 + 1,
  184    arg(I, S1, Sa1),
  185    arg(I, S2, Sa2),
  186    arg(I, G, Ga),
  187    lgg(Sa1, Sa2, Ga, Map0, Map1),
  188    lgg(I, Arity, S1, S2, G, Map1, Map).
  189
  190
  191%!  lgg_safe(+S1, +S2, -G, +Map0, -Map) is det.
  192%
  193%   Cycle-safe version of the  above.  The   difference  is  that we
  194%   insert compounds into the mapping table   and  check the mapping
  195%   table before going into a compound.
  196
  197lgg_safe(S1, S2, G, Map0, Map) :-
  198    (   S1 == S2
  199    ->  G = S1,
  200        Map = Map0
  201    ;   rb_lookup(S1+S2, G0, Map0)
  202    ->  G = G0,
  203        Map = Map0
  204    ;   compound(S1),
  205        compound(S2),
  206        functor(S1, Name, Arity),
  207        functor(S2, Name, Arity)
  208    ->  functor(G, Name, Arity),
  209        rb_insert(Map0, S1+S2, G, Map1),
  210        lgg_safe(0, Arity, S1, S2, G, Map1, Map)
  211    ;   rb_insert(Map0, S1+S2, G, Map)
  212    ).
  213
  214lgg_safe(Arity, Arity, _, _, _, Map, Map) :- !.
  215lgg_safe(I0, Arity, S1, S2, G, Map0, Map) :-
  216    I is I0 + 1,
  217    arg(I, S1, Sa1),
  218    arg(I, S2, Sa2),
  219    arg(I, G, Ga),
  220    lgg_safe(Sa1, Sa2, Ga, Map0, Map1),
  221    lgg_safe(I, Arity, S1, S2, G, Map1, Map).
  222
  223
  224%!  term_factorized(+Term, -Skeleton, -Substiution)
  225%
  226%   Is true when Skeleton is  Term   where  all subterms that appear
  227%   multiple times are replaced by a  variable and Substitution is a
  228%   list of Var=Value that provides the subterm at the location Var.
  229%   I.e., After unifying all substitutions  in Substiutions, Term ==
  230%   Skeleton. Term may be cyclic. For example:
  231%
  232%     ==
  233%     ?- X = a(X), term_factorized(b(X,X), Y, S).
  234%     Y = b(_G255, _G255),
  235%     S = [_G255=a(_G255)].
  236%     ==
  237
  238term_factorized(Term, Skeleton, Substitutions) :-
  239    rb_new(Map0),
  240    add_map(Term, Map0, Map),
  241    rb_visit(Map, Counts),
  242    common_terms(Counts, Common),
  243    (   Common == []
  244    ->  Skeleton = Term,
  245        Substitutions = []
  246    ;   ord_list_to_rbtree(Common, SubstAssoc),
  247        insert_vars(Term, Skeleton, SubstAssoc),
  248        mk_subst(Common, Substitutions, SubstAssoc)
  249    ).
  250
  251add_map(Term, Map0, Map) :-
  252    (   primitive(Term)
  253    ->  Map = Map0
  254    ;   rb_update(Map0, Term, Old, New, Map)
  255    ->  New is Old+1
  256    ;   rb_insert(Map0, Term, 1, Map1),
  257        assoc_arg_map(1, Term, Map1, Map)
  258    ).
  259
  260assoc_arg_map(I, Term, Map0, Map) :-
  261    arg(I, Term, Arg),
  262    !,
  263    add_map(Arg, Map0, Map1),
  264    I2 is I + 1,
  265    assoc_arg_map(I2, Term, Map1, Map).
  266assoc_arg_map(_, _, Map, Map).
  267
  268primitive(Term) :-
  269    var(Term),
  270    !.
  271primitive(Term) :-
  272    atomic(Term),
  273    !.
  274primitive('$VAR'(_)).
  275
  276common_terms([], []).
  277common_terms([H-Count|T], List) :-
  278    !,
  279    (   Count == 1
  280    ->  common_terms(T, List)
  281    ;   List = [H-_NewVar|Tail],
  282        common_terms(T, Tail)
  283    ).
  284
  285insert_vars(T0, T, _) :-
  286    primitive(T0),
  287    !,
  288    T = T0.
  289insert_vars(T0, T, Subst) :-
  290    rb_lookup(T0, S, Subst),
  291    !,
  292    T = S.
  293insert_vars(T0, T, Subst) :-
  294    functor(T0, Name, Arity),
  295    functor(T,  Name, Arity),
  296    insert_arg_vars(1, T0, T, Subst).
  297
  298insert_arg_vars(I, T0, T, Subst) :-
  299    arg(I, T0, A0),
  300    !,
  301    arg(I, T,  A),
  302    insert_vars(A0, A, Subst),
  303    I2 is I + 1,
  304    insert_arg_vars(I2, T0, T, Subst).
  305insert_arg_vars(_, _, _, _).
  306
  307mk_subst([], [], _).
  308mk_subst([Val0-Var|T0], [Var=Val|T], Subst) :-
  309    functor(Val0, Name, Arity),
  310    functor(Val,  Name, Arity),
  311    insert_arg_vars(1, Val0, Val, Subst),
  312    mk_subst(T0, T, Subst).
  313
  314
  315%!  mapargs(:Goal, ?Term1, ?Term2)
  316%
  317%   Term1 and Term2 have the  same   functor  (name/arity)  and for each
  318%   matching pair of arguments call(Goal, A1, A2) is true.
  319
  320mapargs(Goal, Term1, Term2) :-
  321    same_functor(Term1, Term2, Arity),
  322    mapargs_(1, Arity, Goal, Term1, Term2).
  323
  324mapargs_(I, Arity, Goal, Term1, Term2) :-
  325    I =< Arity,
  326    !,
  327    arg(I, Term1, A1),
  328    arg(I, Term2, A2),
  329    call(Goal, A1, A2),
  330    I2 is I+1,
  331    mapargs_(I2, Arity, Goal, Term1, Term2).
  332mapargs_(_, _, _, _, _).
  333
  334
  335%!  mapsubterms(:Goal, +Term1, -Term2) is det.
  336%!  mapsubterms_var(:Goal, +Term1, -Term2) is det.
  337%
  338%   Recursively map sub terms of Term1 into  subterms of Term2 for every
  339%   pair for which call(Goal,  ST1,   ST2)  succeeds.  Procedurably, the
  340%   mapping for each (sub) term pair `T1/T2` is defined as:
  341%
  342%     - If `T1` is a variable
  343%       - mapsubterms/3 unifies `T2` with `T1`.
  344%       - mapsubterms_var/3 treats variables as other terms.
  345%     - If call(Goal, T1, T2) succeeds we are done.  Note that the
  346%       mapping does not continue in `T2`.  If this is desired, `Goal`
  347%       must call mapsubterms/3 explicitly as part of its conversion.
  348%     - If `T1` is a dict, map all values, i.e., the _tag_ and _keys_
  349%       are left untouched.
  350%     - If `T1` is a list, map all elements, i.e., the list structure
  351%       is left untouched.
  352%     - If `T1` is a compound, use same_functor/3 to instantiate `T2`
  353%       and recurse over the term arguments left to right.
  354%     - Otherwise `T2` is unified with `T1`.
  355%
  356%   Both predicates are implemented using foldsubterms/5.
  357
  358mapsubterms(Goal, Term1, Term2) :-
  359    foldsubterms(map2(Goal), Term1, Term2, _, _).
  360mapsubterms_var(Goal, Term1, Term2) :-
  361    foldsubterms(map2_var(Goal), Term1, Term2, _, _).
  362
  363map2(Goal, Term1, Term2, _, _) :-
  364    nonvar(Term1),
  365    call(Goal, Term1, Term2).
  366
  367map2_var(Goal, Term1, Term2, _, _) :-
  368    call(Goal, Term1, Term2).
  369
  370%!  foldsubterms(:Goal3, +Term1, +State0, -State) is semidet.
  371%!  foldsubterms(:Goal4, +Term1, ?Term2, +State0, -State) is semidet.
  372%
  373%   The predicate foldsubterms/5 calls   call(Goal4, SubTerm1, SubTerm2,
  374%   StateIn, StateOut) for each subterm,  including variables, in Term1.
  375%   If this call fails, `StateIn`  and   `StateOut`  are  the same. This
  376%   predicate may be used to map  subterms   in  a term while collecting
  377%   state about the mapped subterms. The foldsubterms/4 variant does not
  378%   map the term.
  379
  380foldsubterms(Goal, Term1, State0, State) :-
  381    foldsubterms(fold1(Goal), Term1, _, State0, State).
  382
  383fold1(Goal, Term1, _Term2, State0, State) :-
  384    call(Goal, Term1, State0, State).
  385
  386foldsubterms(Goal, Term1, Term2, State0, State) :-
  387    call(Goal, Term1, Term2, State0, State),
  388    !.
  389foldsubterms(Goal, Term1, Term2, State0, State) :-
  390    is_dict(Term1),
  391    !,
  392    dict_pairs(Term1, Tag, Pairs1),
  393    fold_dict_pairs(Pairs1, Pairs2, Goal, State0, State),
  394    dict_pairs(Term2, Tag, Pairs2).
  395foldsubterms(Goal, Term1, Term2, State0, State) :-
  396    is_list(Term1),
  397    !,
  398    fold_some(Term1, Term2, Goal, State0, State).
  399foldsubterms(Goal, Term1, Term2, State0, State) :-
  400    compound(Term1),
  401    !,
  402    same_functor(Term1, Term2, Arity),
  403    foldsubterms_(1, Arity, Goal, Term1, Term2, State0, State).
  404foldsubterms(_, Term, Term, State, State).
  405
  406fold_dict_pairs([], [], _, State, State).
  407fold_dict_pairs([K-V0|T0], [K-V|T], Goal, State0, State) :-
  408    foldsubterms(Goal, V0, V, State0, State1),
  409    fold_dict_pairs(T0, T, Goal, State1, State).
  410
  411fold_some([], [], _, State, State).
  412fold_some([H0|T0], [H|T], Goal, State0, State) :-
  413    foldsubterms(Goal, H0, H, State0, State1),
  414    fold_some(T0, T, Goal, State1, State).
  415
  416foldsubterms_(I, Arity, Goal, Term1, Term2, State0, State) :-
  417    I =< Arity,
  418    !,
  419    arg(I, Term1, A1),
  420    arg(I, Term2, A2),
  421    foldsubterms(Goal, A1, A2, State0, State1),
  422    I2 is I+1,
  423    foldsubterms_(I2, Arity, Goal, Term1, Term2, State1, State).
  424foldsubterms_(_, _, _, _, _, State, State).
  425
  426
  427%!  same_functor(?Term1, ?Term2) is semidet.
  428%!  same_functor(?Term1, ?Term2, -Arity) is semidet.
  429%!  same_functor(?Term1, ?Term2, ?Name, ?Arity) is semidet.
  430%
  431%   True when Term1 and Term2  are  terms   that  have  the same functor
  432%   (Name/Arity). The arguments must be sufficiently instantiated, which
  433%   means either Term1 or Term2 must  be   bound  or both Name and Arity
  434%   must be bound.
  435%
  436%   If  Arity  is  0,  Term1  and  Term2   are  unified  with  Name  for
  437%   compatibility.
  438%
  439%   @compat SICStus
  440
  441same_functor(Term1, Term2) :-
  442    same_functor(Term1, Term2, _Name, _Arity).
  443
  444same_functor(Term1, Term2, Arity) :-
  445    same_functor(Term1, Term2, _Name, Arity).
  446
  447same_functor(Term1, Term2, Name, Arity) :-
  448    (   nonvar(Term1)
  449    ->  functor(Term1, Name, Arity, Type),
  450        functor(Term2, Name, Arity, Type)
  451    ;   nonvar(Term2)
  452    ->  functor(Term2, Name, Arity, Type),
  453        functor(Term1, Name, Arity, Type)
  454    ;   functor(Term2, Name, Arity),
  455        functor(Term1, Name, Arity)
  456    )