%---------------------------------------------------------------------------%
% vim: ft=mercury ts=4 sw=4 et
%---------------------------------------------------------------------------%
% Copyright (C) 1996-2012 The University of Melbourne.
% Copyright (C) 2014-2024 The Mercury team.
% This file may only be copied under the terms of the GNU General
% Public License - see the file COPYING in the Mercury distribution.
%---------------------------------------------------------------------------%
%
% File: prog_data.m.
% Main author: fjh.
%
% This module defines the types that represent the most frequently used parts
% of the parse trees of Mercury programs.
%
% The other prog_data_*.m modules define the other parts of the parse tree
% that are needed after the creation of the HLDS. prog_item.m defines
% the parts of the tree that are needed *only until* the creation of the HLDS.
%
%---------------------------------------------------------------------------%

:- module parse_tree.prog_data.
:- interface.

:- import_module mdbcomp.
:- import_module mdbcomp.prim_data.
:- import_module mdbcomp.sym_name.
:- import_module parse_tree.prog_item.

:- import_module char.
:- import_module cord.
:- import_module list.
:- import_module map.
:- import_module maybe.
:- import_module one_or_more.
:- import_module set.
:- import_module term.
:- import_module term_context.
:- import_module varset.

%---------------------------------------------------------------------------%
%
% Cons ids.
%

:- interface.

    % The representation of cons_ids below is a compromise. The cons_id
    % type must be defined here, in a submodule of parse_tree.m, because
    % it is a component of insts. However, after the program has been read in,
    % the cons_ids which can appear in user programs, namely
    %
    %   cons
    %   tuple_cons
    %   some_int_const
    %   float_const
    %   char_const
    %   string_const
    %   impl_defined_const
    %
    % may also be augmented by the other cons_ids, which can only be
    % generated by the compiler.
    %
    % The problem is that some of these compiler generated cons_ids
    % refer to procedures, and the natural method of identifying
    % procedures requires the types pred_id and proc_id, defined
    % in hlds_pred.m, which we don't want to import here.
    %
    % We could try to avoid this problem using two different types
    % for cons_ids, one defined here for use in the parse tree and one
    % defined in hlds_data.m for use in the HLDS. We could distinguish
    % the two by having the HLDS cons_id have a definition such as
    % cons_id ---> parse_cons_id(parse_cons_id) ; ...
    % or, alternatively, by making cons_id parametric in the type of
    % constants, and substitute different constant types (since all the
    % cons_ids that refer to HLDS concepts are constants).
    %
    % Using two different types requires a translation from one to the other.
    % While the runtime cost would be acceptable, the cost in code complexity
    % is not, since the translation isn't confined to make_hlds.m.
    % (I found this out the hard way.) This is especially so if
    % we want to use the tightest possible type in each case.
    % For example, while construct goals can involve all cons_ids,
    % deconstruct goals and switches can currently involve only the
    % cons_ids that can appear in parse trees.
    %
    % The solution we have chosen is to exploit the fact that pred_ids
    % and proc_ids are integers. Those types are private to hlds_pred.m,
    % but hlds_pred.m also contains functions for translating them to and
    % from the shrouded versions defined below. The next three types are
    % designed to be used in only two ways: for translation to their HLDS
    % equivalents by the unshroud functions in hlds_pred.m, and for
    % printing for diagnostics.
    %
:- type shrouded_pred_id
    --->    shrouded_pred_id(int).
:- type shrouded_proc_id
    --->    shrouded_proc_id(int).
:- type shrouded_pred_proc_id
    --->    shrouded_pred_proc_id(int, int).

:- type du_ctor
    --->    du_ctor(sym_name, arity, type_ctor).
            % Before post-typecheck, the type_ctor field is not meaningful.

:- type cons_id
    --->    du_data_ctor(du_ctor)
            % A data constructor for a discriminated union type. However,
            % note that before post-typecheck, tuples and characters
            % will ALSO have this cons_id. For tuples, they will have the form
            % `cons(du_ctor(unqualified("{}"), Arity, _))', while for
            % characters, this will be `cons(du_ctor(unqualified(Str), 0, _))'
            % where Str = term_io.quoted_char(Char).

    ;       tuple_cons(arity)
            % Tuples are represented by this cons_id after
            % resolve_unify_functor.m has been run as part of the
            % post-typecheck pass. Until then, they are represented as
            % cons(unqualified("{}"), ...).
            %
            % XXX Unfortunately, the above is not quite true. The utility
            % predicate type_constructors in type_util.m return the cons_ids
            % of a type, but it does not know what the current pass is.
            % When called on a tuple type, it can therefore either *always*
            % return cons(unqualified("{}"), ...), or it can *always* return
            % tuple_cons(Arity). It does the former, which means that any code
            % that deals with its output, directly or indirectly, which
            % certainly includes code that uses inst_match.m and probably
            % includes other modules as well, has to be prepared for this.
            %
            % XXX I (zs) also strongly suspect that while post-typecheck.m.
            % may replace occurrences of cons(unqualified("{}"), ...) in a
            % procedure's body goal with tuple_cons(Arity), it won't replace
            % similar occurrences in bound_functor in those procedures' mode
            % declarations.

    ;       closure_cons(shrouded_pred_proc_id)
            % Note that a closure_cons represents a closure, not just
            % a code address.
            % XXX We should have a pred_or_func field as well.

    ;       some_int_const(some_int_const)
    ;       float_const(float)
    ;       char_const(char)
    ;       string_const(string)

    ;       impl_defined_const(impl_defined_const_kind)

    ;       type_ctor_info_const(
                module_name,
                string,         % Name of the type constructor.
                int             % Its arity.
            )
    ;       base_typeclass_info_const(
                module_name,
                % Module name of instance declaration (not filled in
                % so that link errors result from overlapping instances).

                class_id,
                % Class name and arity.

                int,
                % Class instance.

                string
                % Encodes the type names and arities of the arguments
                % of the instance declaration.
            )

    ;       type_info_cell_constructor(type_ctor)
    ;       typeclass_info_cell_constructor

    ;       type_info_const(int)
    ;       typeclass_info_const(int)

    ;       ground_term_const(int, cons_id)

    ;       tabling_info_const(shrouded_pred_proc_id)
            % The address of the static structure that holds information
            % about the table that implements memoization, loop checking
            % or the minimal model semantics for the given procedure.

    ;       table_io_entry_desc(shrouded_pred_proc_id)
            % The address of a structure that describes the layout of the
            % answer block used by I/O tabling for declarative debugging.

    ;       deep_profiling_proc_layout(shrouded_pred_proc_id).
            % The Proc_Layout structure of a procedure. Its proc_static field
            % is used by deep profiling, as documented in the deep profiling
            % paper.

:- type some_int_const
    --->    int_const(int)
    ;       uint_const(uint)
    ;       int8_const(int8)
    ;       uint8_const(uint8)
    ;       int16_const(int16)
    ;       uint16_const(uint16)
    ;       int32_const(int32)
    ;       uint32_const(uint32)
    ;       int64_const(int64)
    ;       uint64_const(uint64).

:- func type_of_int_const(some_int_const) = int_type.
:- func type_name_of_int_const(some_int_const) = string.

:- type impl_defined_const_kind
    --->    idc_file        % $file
    ;       idc_line        % $line
    ;       idc_module      % $module
    ;       idc_pred        % $pred
    ;       idc_grade.      % $grade

:- func impl_defined_const_kind_to_str(impl_defined_const_kind) = string.

:- func cons_id_dummy_type_ctor = type_ctor.

    % Are the two cons_ids equivalent, modulo any module qualifications?
    %
:- pred equivalent_cons_ids(cons_id::in, cons_id::in) is semidet.

:- pred cons_id_is_const_struct(cons_id::in, int::out) is semidet.

:- implementation.

type_of_int_const(IntConst) = Type :-
    ( IntConst = int_const(_),    Type = int_type_int
    ; IntConst = uint_const(_),   Type = int_type_uint
    ; IntConst = int8_const(_),   Type = int_type_int8
    ; IntConst = uint8_const(_),  Type = int_type_uint8
    ; IntConst = int16_const(_),  Type = int_type_int16
    ; IntConst = uint16_const(_), Type = int_type_uint16
    ; IntConst = int32_const(_),  Type = int_type_int32
    ; IntConst = uint32_const(_), Type = int_type_uint32
    ; IntConst = int64_const(_),  Type = int_type_int64
    ; IntConst = uint64_const(_), Type = int_type_uint64
    ).

type_name_of_int_const(IntConst) = TypeName :-
    ( IntConst = int_const(_),    TypeName = "int"
    ; IntConst = uint_const(_),   TypeName = "uint"
    ; IntConst = int8_const(_),   TypeName = "int8"
    ; IntConst = uint8_const(_),  TypeName = "uint8"
    ; IntConst = int16_const(_),  TypeName = "int16"
    ; IntConst = uint16_const(_), TypeName = "uint16"
    ; IntConst = int32_const(_),  TypeName = "int32"
    ; IntConst = uint32_const(_), TypeName = "uint32"
    ; IntConst = int64_const(_),  TypeName = "int64"
    ; IntConst = uint64_const(_), TypeName = "uint64"
    ).

impl_defined_const_kind_to_str(IDCKind) = Str :-
    ( IDCKind = idc_file, Str = "$file"
    ; IDCKind = idc_line, Str = "$line"
    ; IDCKind = idc_module, Str = "$module"
    ; IDCKind = idc_pred, Str = "$pred"
    ; IDCKind = idc_grade, Str = "$grade"
    ).

cons_id_dummy_type_ctor = type_ctor(unqualified(""), -1).

equivalent_cons_ids(ConsIdA, ConsIdB) :-
    ( if
        ConsIdA = du_data_ctor(du_ctor(SymNameA, ArityA, _)),
        ConsIdB = du_data_ctor(du_ctor(SymNameB, ArityB, _))
    then
        ArityA = ArityB,
        (
            SymNameA = unqualified(Name),
            SymNameB = unqualified(Name)
        ;
            SymNameA = unqualified(Name),
            SymNameB = qualified(_, Name)
        ;
            SymNameA = qualified(_, Name),
            SymNameB = unqualified(Name)
        ;
            SymNameA = qualified(ModuleName, Name),
            SymNameB = qualified(ModuleName, Name)
        )
    else if
        ConsIdA = du_data_ctor(du_ctor(SymNameA, ArityA, _)),
        ConsIdB = tuple_cons(ArityB)
    then
        ArityA = ArityB,
        SymNameA = unqualified("{}")
    else if
        ConsIdA = tuple_cons(ArityA),
        ConsIdB = du_data_ctor(du_ctor(SymNameB, ArityB, _))
    then
        ArityA = ArityB,
        SymNameB = unqualified("{}")
    else
        ConsIdA = ConsIdB
    ).

cons_id_is_const_struct(ConsId, ConstNum) :-
    require_complete_switch [ConsId]
    (
        ConsId = type_info_const(ConstNum)
    ;
        ConsId = typeclass_info_const(ConstNum)
    ;
        ConsId = ground_term_const(ConstNum, _)
    ;
        ( ConsId = du_data_ctor(_)
        ; ConsId = tuple_cons(_)
        ; ConsId = closure_cons(_)
        ; ConsId = some_int_const(_)
        ; ConsId = float_const(_)
        ; ConsId = char_const(_)
        ; ConsId = string_const(_)
        ; ConsId = impl_defined_const(_)
        ; ConsId = type_ctor_info_const(_, _, _)
        ; ConsId = base_typeclass_info_const(_, _, _, _)
        ; ConsId = type_info_cell_constructor(_)
        ; ConsId = typeclass_info_cell_constructor
        ; ConsId = tabling_info_const(_)
        ; ConsId = table_io_entry_desc(_)
        ; ConsId = deep_profiling_proc_layout(_)
        ),
        fail
    ).

%---------------------------------------------------------------------------%
%
% Types.
%

:- interface.

    % This is how types are represented.
    %
    % One day we might allow types to take value parameters, as well as
    % type parameters.
    %
:- type type_defn
    --->    parse_tree_du_type(type_details_du)
    ;       parse_tree_sub_type(type_details_sub)
    ;       parse_tree_eqv_type(type_details_eqv)
    ;       parse_tree_solver_type(type_details_solver)
    ;       parse_tree_abstract_type(type_details_abstract)
    ;       parse_tree_foreign_type(type_details_foreign_generic).

:- type type_details_du
    --->    type_details_du(
                % The list of data constructors (function symbols) defined
                % by the type constructor.
                du_ctors            :: one_or_more(constructor),

                % Does the type constructor definition specify
                % a unification and/or comparison predicate for its instances?
                du_canonical        :: maybe_canonical,

                % Is any of the data constructors in du_ctors using the
                % direct_arg optimization, in which its representation is a
                % tagged pointer to a representation of its single argument
                % (which must be a *non*-tagged pointer to a heap cell)?
                % XXX TYPE_REPN This information should NOT be in type_defn
                % items, but in separate type_representation items.
                du_direct_arg       :: maybe(list(sym_name_arity))
            ).

:- type type_details_sub
    --->    type_details_sub(
                % The declared immediate supertype of this subtype.
                sub_supertype       :: mer_type,

                % The list of data constructors (function symbols) defined
                % by the type constructor. It must constitute a subset
                % of the set of data constructors of the supertype.
                sub_ctors           :: one_or_more(constructor)
            ).

:- type type_details_eqv
    --->    type_details_eqv(
                eqv_type            :: mer_type
            ).

    % XXX TYPE_REPN Once we transmit type representation information between
    % modules using specialized type_repn items, we should not need this type.
:- type type_details_abstract
    --->    abstract_type_general

    ;       abstract_type_fits_in_n_bits(int)
            % The abstract type is an enumeration type, requiring
            % the given number of bits to represent.
            % XXX TYPE_REPN The part about "is an enumeration type"
            % is a temporary limitation. In the future, we will also use this
            % for the abstract versions of other types that can fit in less
            % than one word, including builtin types such as int8.

    ;       abstract_dummy_type
            % The abstract type is a dummy type.

    ;       abstract_notag_type
            % The abstract type is a no_tag type.

    ;       abstract_subtype(type_ctor)
            % The abstract type is a subtype of this super type ctor.

    ;       abstract_solver_type.
            % An abstract solver type.

:- type type_details_solver
    --->    type_details_solver(
                solver_details      :: solver_type_details,
                solver_canonical    :: maybe_canonical
            ).

    % The `is_solver_type' type specifies whether a type is a "solver" type,
    % for which `any' insts are interpreted as "don't know", or a non-solver
    % type for which `any' is the same as `bound(...)'.
    %
:- type is_solver_type
    --->    non_solver_type
            % The inst `any' is always `bound' for this type.

    ;       solver_type.
            % The inst `any' is not always `bound' for this type
            % (i.e. the type was declared with `:- solver type ...').

    % The reason why we make LangType a parameter of type_details_foreign
    % is the fact that we need information about type names defined in
    % foreign languages in two kinds of circumstances.
    %
    % The first kind is when we are handling a single specific
    % `pragma foreign_type' item. In this case, we need to use a single type
    % to represent a declaration that could be for any foreign language.
    % In this case, we use type_details_foreign(generic_language_foreign_type),
    % which can represent a type name for any foreign language.
    %
    % The other kind is when we want to gather all the definitions for
    % a given type constructor in a given foreign language, such as C.
    % In this case, we use type_details_foreign(c_foreign_type), which
    % which can represent a type name only for the chosen foreign language.
    %
:- type type_details_foreign(LangType)
    --->    type_details_foreign(
                foreign_lang_type   :: LangType,
                foreign_canonical   :: maybe_canonical,
                foreign_assertions  :: foreign_type_assertions
            ).

:- type type_details_foreign_generic ==
    type_details_foreign(generic_language_foreign_type).

    % A generic_language_foreign_type represents a type that is
    % defined in a given foreign language using `pragma foreign_type'.
    %
:- type generic_language_foreign_type
    --->    c(c_foreign_type)
    ;       java(java_foreign_type)
    ;       csharp(csharp_foreign_type).

:- type c_foreign_type
    --->    c_type(
                string      % The C type name
            ).

:- type java_foreign_type
    --->    java_type(
                string      % The Java type name
            ).

:- type csharp_foreign_type
    --->    csharp_type(
                string      % The C# type name
            ).

:- type foreign_type_assertions
    --->    foreign_type_assertions(set(foreign_type_assertion)).

:- type foreign_type_assertion
    --->    foreign_type_can_pass_as_mercury_type
    ;       foreign_type_stable
    ;       foreign_type_word_aligned_pointer.

:- type constructor
    --->    ctor(
                % The ordinal number of the functor. The first functor
                % in a type definition has ordinal number 0.
                % A subtype's functors are numbered independently
                % from its supertypes and base type.
                cons_ordinal        :: uint32,

                % Existential constraints, if any.
                % It is an invariant that this will be no_exist_constraints
                % if the list of arguments is empty.
                cons_maybe_exist    :: maybe_cons_exist_constraints,

                % The cons_id should be cons(SymName, Arity, TypeCtor)
                % for user-defined types, and tuple_cons(Arity) for the
                % system-defined tuple types.
                cons_name           :: sym_name,

                cons_args           :: list(constructor_arg),

                % We precompute the number of arguments once, to save having
                % to recompute it many times later.
                cons_num_args       :: int,

                cons_context        :: prog_context
            ).

:- pred ctor_is_constant(constructor::in, string::out) is semidet.

:- pred ctors_are_all_constants(list(constructor)::in, list(string)::out)
    is semidet.

:- type maybe_cons_exist_constraints
    --->    no_exist_constraints
    ;       exist_constraints(cons_exist_constraints).

:- type cons_exist_constraints
    --->    cons_exist_constraints(
                % cons_existq_tvars cannot be empty.
                cons_existq_tvars   :: existq_tvars,
                cons_constraints    :: list(prog_constraint),

                % The unconstrained type variables in cons_existq_tvars
                % i.e. those tvars that do not appear in any constraint
                % in cons_constraints. These are in the same order
                % as they are in cons_existq_tvars.
                cons_unconstrained  :: existq_tvars,

                % The constrained type variables in cons_existq_tvars
                % i.e. those tvars that appear in at least one constraint
                % in cons_constraints. These are in the same order
                % as they are in cons_existq_tvars.
                cons_constrained    :: existq_tvars
            ).

:- type constructor_arg
    --->    ctor_arg(
                arg_field_name      :: maybe(ctor_field_name),
                arg_type            :: mer_type,
                arg_context         :: prog_context
            ).

:- type ctor_field_name
    --->    ctor_field_name(
                sym_name,           % The name of the field.
                prog_context        % The context of the name in the source.
            ).

:- pred get_ctor_arg_types(list(constructor_arg)::in, list(mer_type)::out)
    is det.

    % The arg_pos_width type and its components specify how much space
    % does a constructor argument occupy in the memory that represents
    % a term with that constructor, and where. This memory will usually be
    % in a heap cell, so this is what the discussion below assumes,
    % but see below for an exception.
    %
    % XXX ARG_PACK document the CellOffset fields.
    % `apw_full(ArgOnlyOffset)' indicates that the argument fully occupies
    % a single word, and this word is ArgOnlyOffset words after the first word
    % of the memory cell that starts storing visible arguments.
    % This means that e.g. if the first argument takes up a full word,
    % it will be at ArgOnlyOffset=0, even though the memory cell of the term
    % may contain a remote secondary tag, and type_infos and/or typeclass_infos
    % added by polymorphism.m, before it. (This is the meaning of "arg only"
    % offsets.)
    %
    % `apw_double(ArgOnlyOffset)' indicates that the argument occupies
    % two words, at arg only offsets ArgOnlyOffset and ArgOnlyOffset+1.
    % Currently, by default only double-precision floats may take two words,
    % but int64 and uint64 values may do so as well if the option
    % allow_double_word_ints is set.
    %
    % `apw_partial_first(ArgOnlyOffset, NumBits, Mask, Fill)' indicates
    % that the argument is the first of two or more sub-word-sized arguments
    % which share the same word at the offset ArgOnlyOffset. This argument
    % occupies the lowest NumBits bits in the word so no shifting is required
    % to access it. The other arguments can be masked out with the bit-mask
    % `Mask'. Mask will always have the least significant NumBits bits set
    % and all other bits clear. Fill indicates whether the argument should be
    % treated as an unsigned value (filled with zeroes) or as a signed value
    % (having the rest of the word filled with the sign bit when extracted).
    %
    % `apw_partial_shifted(ArgOnlyOffset, Shift, NumBits, Mask, Fill)'
    % indicates that the argument is one of two or more sub-word-size arguments
    % which share the same word at the offset ArgOnlyOffset, but it is
    % *not* the first, so Shift will be the non-zero number of bits
    % that the argument value is left-shifted by. The other fields have
    % the same meaning as for apw_partial_first.
    %
    % `apw_none_nowhere' and `apw_none_shifted(ArgOnlyOffset)' each represent
    % an argument whose type is a dummy type.
    %
    % Given a run of one or more consecutive dummy arguments, all arguments
    % in the run will have the same representation. If the run's immediate
    % neighbours on both sides are sub-word-sized, then the arguments
    % in the run will be all be apw_none_shifted; if either neighbouring
    % argument is missing, or if either is full word sized or larger,
    % then the arguments in the run will all be apw_none_nowhere.
    %
    % The exception mentioned above is that if a function symbol only has
    % a small number of small (subword-sized) arguments, then we try to fit
    % the representation of all the arguments next to the primary and local
    % secondary tags, *without* using a heap cell. In this case, all these
    % arguments will be represented by apw_partial_shifted with -1 as the
    % offset (both kinds), unless they are of a dummy type, in which case
    % their representation will be apw_none_shifted, also with -1 as offset.
    %
    % The EBNF grammar of possible sequences of representations of nonconstant
    % terms is:
    %
    % repn:
    %   :   ptag ptr_to_heap_cell
    %   |   ptag local_sectag (apw_none_shifted | apw_partial_shifted)+
    %
    % heap_cell
    %   :   remote_sectag_word? integral_cell_word_unit*
    %
    % integral_cell_word_unit
    %   :   apw_none_nowhere
    %   |   apw_full
    %   |   apw_double
    %   |   apw_partial_first (apw_none_shifted* apw_partial_shifted)+
    %
    % We wrap function symbols around the integer arguments mentioned above
    % to make the different integers harder to confuse with each other.

:- type fill_kind
    --->    fill_enum
    ;       fill_int8
    ;       fill_int16
    ;       fill_int32
    ;       fill_uint8
    ;       fill_uint16
    ;       fill_uint32
    ;       fill_char21.

:- pred fill_kind_string(fill_kind, string).
:- mode fill_kind_string(in, out) is det.
:- mode fill_kind_string(out, in) is semidet.

:- type double_word_kind
    --->    dw_float
    ;       dw_int64
    ;       dw_uint64.

:- pred double_word_kind_string(double_word_kind, string).
:- mode double_word_kind_string(in, out) is det.
:- mode double_word_kind_string(out, in) is semidet.

    % The type `ptag' holds a primary tag value.
    % It consists of 2 bits on 32 bit machines and 3 bits on 64 bit machines.
    % If we are not using primary tags to distinguish function symbols
    % from each other, the ptag will always be 0u8.
    %
:- type ptag
    --->    ptag(uint8).

:- type arg_only_offset
    --->    arg_only_offset(int).
            % The offset of the word from the first part of the memory cell
            % that contains arguments. In other words, the first argument word
            % is at offset 0, even if it is preceded in the memory cell
            % by a remote secondary tag, or by type_infos and/or
            % typeclass_infos added by polymorphism.
            %
            % Although the offset is almost always non-negative, there are
            % two negative values that are permitted for the offset.
            %
            % - The special negative value -1 means that the argument is
            %   stored in the heap cell in the same word as the remote
            %   secondary tag.
            %
            % - The special negative value -2 means that the argument is
            %   stored not in a heap cell, but in the same word as the
            %   primary tag.
            %
            % The arg_only_offsets of any remote secondary tags and of any
            % type_infos and/or typeclass_infos added by polymorphism are
            % not meaningful. They can be anything, because the
            % arg_only_offset is used only for the creation of RTTI data,
            % and that task takes as its input the arg_only_offsets of
            % only the actual arguments.
            % XXX The RTTI data would probably be more useful to the runtime
            % if it included cell_offsets instead of arg_only_offsets, since
            % for most purposes, the runtime actually needs the cell_offset,
            % and having it directly available would avoid the need to compute
            % *at runtime* the cell_offset from
            % - the arg_only_offset,
            % - the absence/presence of a remote secondary tag, and
            % - the number of type_infos and/or typeclass_infos.
            % However, changing this would require nontrivial bootstrapping.

:- type cell_offset
    --->    cell_offset(int).
            % The offset of the word from the start of the memory cell.
            % If the cell starts with N words containing remote secondary
            % tags, type_infos and/or typeclass_infos, then the first
            % actual argument will be at cell_offset N.

:- type arg_shift
    --->    arg_shift(int).
            % XXX Should be uint8, when shift amounts can be uint8.

:- type arg_num_bits
    --->    arg_num_bits(int).
            % XXX Should be uint8, when shift amounts can be uint8.

:- type arg_mask
    --->    arg_mask(int).
            % The mask is always set to be (2 ^ num_bits) - 1.

:- type arg_pos_width
    --->    apw_full(
                awf_ao_offset       :: arg_only_offset,
                awf_cell_offset     :: cell_offset
            )
    ;       apw_double(
                awd_ao_offset_start :: arg_only_offset,
                awd_cell_offset     :: cell_offset,
                awd_kind            :: double_word_kind
            )
    ;       apw_partial_first(
                % The word this starts may contain apw_partial_shifted
                % *and* apw_none_shifted.

                awpf_ao_offset      :: arg_only_offset,
                awpf_cell_offset    :: cell_offset,
                awpf_shift          :: arg_shift,
                awpf_num_bits       :: arg_num_bits,
                awpf_mask           :: arg_mask,
                awpf_fill           :: fill_kind
            )
    ;       apw_partial_shifted(
                awps_ao_offset      :: arg_only_offset,
                awps_cell_offset    :: cell_offset,
                awps_shift          :: arg_shift,
                awps_num_bits       :: arg_num_bits,
                awps_mask           :: arg_mask,
                awps_fill           :: fill_kind
            )
    ;       apw_none_shifted(
                % Like apw_partial_shifted, but this arg is of a dummy type.
                awns_ao_offset      :: arg_only_offset,
                awns_cell_offset    :: cell_offset
            )
    ;       apw_none_nowhere.
            % This arg is of a dummy type. It is not packed together
            % with any other argument, and occupies no space at all.

:- type arg_width
    --->    aw_none
    ;       aw_partial_word
    ;       aw_full_word
    ;       aw_double_word.

:- func arg_pos_width_to_width_only(arg_pos_width) = arg_width.

    % Is a given discriminated union type a subtype of another type?
    %
:- type maybe_subtype
    --->    not_a_subtype
    ;       subtype_of(mer_type).

    % The noncanon functor gives the user-defined unification and/or comparison
    % predicates for a noncanonical type, if they are known.
    %
    % The value noncanon_abstract represents a type whose definition uses the
    % syntax `where type_is_abstract_noncanonical' and has been read from an
    % .int2 file. This means we know that the type has a noncanonical
    % representation, but we don't know what the unification or comparison
    % predicates are.
    %
    % The value noncanon_subtype represents a subtype whose base type has
    % user-defined unification and/or comparison predicates. Subtypes cannot
    % have their own user-defined unification/comparison predicates.
    %
:- type maybe_canonical
    --->    canon
    ;       noncanon(noncanonical).

:- type noncanonical
    --->    noncanon_uni_cmp(equality_pred, comparison_pred)
    ;       noncanon_uni_only(equality_pred)
    ;       noncanon_cmp_only(comparison_pred)
    ;       noncanon_abstract(is_solver_type)
    ;       noncanon_subtype.

    % The `where' attributes of a solver type definition must begin
    % with
    %   representation is <<representation type>>,
    %   ground         is <<ground inst>>,
    %   any            is <<any inst>>,
    %   constraint_store is <<mutable(...) or [mutable(...), ...]>>
    %
:- type solver_type_details
    --->    solver_type_details(
                std_representation_type :: mer_type,
                std_ground_inst         :: mer_inst,
                std_any_inst            :: mer_inst,
                % XXX The item_mutable_info type is defined in prog_item.m.
                % The reference to that module here is undesirable.
                std_mutable_items       :: list(item_mutable_info)
            ).

    % An init_pred specifies the name of an impure user-defined predicate
    % used to initialise solver type values (the compiler will insert calls
    % to this predicate to convert free solver type variables to inst any
    % variables where necessary.)
    %
:- type init_pred == sym_name.

    % An equality_pred specifies the name of a user-defined predicate
    % used for equality on a type. See the chapter on them in the
    % Mercury Language Reference Manual.
    %
:- type equality_pred == sym_name.

    % The name of a user-defined comparison predicate.
    %
:- type comparison_pred == sym_name.

    % Parameters of type definitions.
    %
:- type type_param == tvar.

    % Use prog_type.type_to_ctor_and_args to convert a type to a qualified
    % type_ctor and a list of arguments. Use prog_type.construct_type to
    % construct a type from a type_ctor and a list of arguments.
    %
:- type mer_type
    --->    type_variable(tvar, kind)
            % A type variable.

    ;       defined_type(sym_name, list(mer_type), kind)
            % A type using a user defined type constructor.

    ;       builtin_type(builtin_type)
            % These are all known to have kind `star'.

    % The above three functors should be kept as the first three, since
    % they will be the most commonly used and therefore we want them to
    % get the primary tags on a 32-bit machine.

    ;       tuple_type(list(mer_type), kind)
            % Tuple types.

    ;       higher_order_type(
                % A type for higher-order values. The kind is always `star'.
                % For functions the return type is at the end of the list
                % of argument types.
                pred_or_func,
                list(mer_type),
                ho_inst_info,
                purity
            )

    ;       apply_n_type(tvar, list(mer_type), kind)
            % An apply/N expression. `apply_n(V, [T1, ...], K)'
            % would be the representation of type `V(T1, ...)' with kind K.
            % The list must be non-empty.

    ;       kinded_type(mer_type, kind).
            % A type expression with an explicit kind annotation.
            % (These are not yet used.)

:- type ground_type =< mer_type
    --->    defined_type(sym_name, list(ground_type), kind)
    ;       builtin_type(builtin_type)
    ;       tuple_type(list(ground_type), kind)
    ;       higher_order_type(pred_or_func, list(ground_type), ho_inst_info,
                purity)
    ;       apply_n_type(tvar, list(ground_type), kind)
    ;       kinded_type(ground_type, kind).

% We could use this subtype in the mercury_nb_type function symbol
% of mlds_type in mlds.m.
%
% :- type nb_mer_type =< mer_type
%   --->    type_variable(tvar, kind)
%   ;       defined_type(sym_name, list(mer_type), kind)
%   ;       tuple_type(list(mer_type), kind)
%   ;       higher_order_type(pred_or_func, list(mer_type), ho_inst_info,
%               purity)
%   ;       apply_n_type(tvar, list(mer_type), kind)
%   ;       kinded_type(mer_type, kind).

    % This type enumerates all of the builtin primitive types in Mercury.
    % If you add a new alternative then you may also need to update the
    % following predicates:
    %
    %     - parse_type_name.is_known_type_name_args/3
    %     - inst_check.check_inst_defn_has_matching_type/7
    %     - llds_out_data.output_type_ctor_addr/5
    %     - type_util.classify_type_ctor/2
    %
:- type builtin_type
    --->    builtin_type_int(int_type)
    ;       builtin_type_float
    ;       builtin_type_string
    ;       builtin_type_char.

:- type int_type
    --->    int_type_int
    ;       int_type_uint
    ;       int_type_int8
    ;       int_type_uint8
    ;       int_type_int16
    ;       int_type_uint16
    ;       int_type_int32
    ;       int_type_uint32
    ;       int_type_int64
    ;       int_type_uint64.

:- pred is_builtin_type_sym_name(sym_name::in) is semidet.

:- pred is_builtin_type_name(string::in) is semidet.

    % A table mapping the internal form of builtin types
    % to the user-visible type name. Note that this type name
    % may NOT be a valid library module name, due to the builtin
    % "character" type name differing from the name of the "char" module
    % in the library.
    %
:- pred builtin_type_name(builtin_type, string).
:- mode builtin_type_name(in, out) is det.
:- mode builtin_type_name(out, in) is semidet.

    % A table mapping the internal form of builtin integer types
    % to the name that is both
    %
    % - the user-visible type name, and
    % - the name of the module that provides operation on the type.
    %
:- pred int_type_module_name(int_type, string).
:- mode int_type_module_name(in, out) is det.
:- mode int_type_module_name(out, in) is semidet.

:- type type_term == term(tvar_type).

:- type tvar_type
    --->    type_var.

    % "tvar" is short for "type variable".
:- type tvar == var(tvar_type).
    % A set of type variables.
:- type tvarset == varset(tvar_type).

    % A renaming or a substitution on type variables.
:- type tvar_renaming == map(tvar, tvar).
:- type tsubst == map(tvar, mer_type).

:- type type_ctor
    --->    type_ctor(sym_name, arity).

:- type tvar_name_map == map(string, tvar).

    % existq_tvars is used to record the set of type variables which are
    % existentially quantified
    %
:- type existq_tvars == list(tvar).

    % Similar to varset.merge_subst but produces a tvar_renaming
    % instead of a substitution, which is more suitable for types.
    %
:- pred tvarset_merge_renaming(tvarset::in, tvarset::in, tvarset::out,
    tvar_renaming::out) is det.

    % As above, but behaves like varset.merge_subst_without_names.
    %
:- pred tvarset_merge_renaming_without_names(tvarset::in, tvarset::in,
    tvarset::out, tvar_renaming::out) is det.

:- implementation.

ctor_is_constant(Ctor, Name) :-
    Ctor = ctor(_Ordinal, MaybeExistConstraints, SymName, Args, Arity,
        _Context),
    MaybeExistConstraints = no_exist_constraints,
    Args = [],
    Arity = 0,
    Name = unqualify_name(SymName).

ctors_are_all_constants([], []).
ctors_are_all_constants([Ctor | Ctors], [Name | Names]) :-
    ctor_is_constant(Ctor, Name),
    ctors_are_all_constants(Ctors, Names).

get_ctor_arg_types(CtorArgs, CtorArgTypes) :-
    list.map(get_ctor_arg_type, CtorArgs, CtorArgTypes).

:- pred get_ctor_arg_type(constructor_arg::in, mer_type::out) is det.

get_ctor_arg_type(ctor_arg(_, Type, _), Type).

fill_kind_string(fill_enum, "fill_enum").
fill_kind_string(fill_int8, "fill_int8").
fill_kind_string(fill_int16, "fill_int16").
fill_kind_string(fill_int32, "fill_int32").
fill_kind_string(fill_uint8, "fill_uint8").
fill_kind_string(fill_uint16, "fill_uint16").
fill_kind_string(fill_uint32, "fill_uint32").
fill_kind_string(fill_char21, "fill_char21").

double_word_kind_string(dw_float, "dw_float").
double_word_kind_string(dw_int64, "dw_int64").
double_word_kind_string(dw_uint64, "dw_uint64").

arg_pos_width_to_width_only(ArgPosWidth) = ArgWidth :-
    (
        ArgPosWidth = apw_full(_, _),
        ArgWidth = aw_full_word
    ;
        ArgPosWidth = apw_double(_, _, _),
        ArgWidth = aw_double_word
    ;
        ( ArgPosWidth = apw_partial_first(_, _, _, _, _, _)
        ; ArgPosWidth = apw_partial_shifted(_, _, _, _, _, _)
        ),
        ArgWidth = aw_partial_word
    ;
        ( ArgPosWidth = apw_none_nowhere
        ; ArgPosWidth = apw_none_shifted(_, _)
        ),
        ArgWidth = aw_none
    ).

is_builtin_type_sym_name(SymName) :-
    SymName = unqualified(Name),
    builtin_type_name(_, Name).

is_builtin_type_name(Name) :-
    builtin_type_name(_, Name).

% Please keep this code in sync with int_type_module_name and
% classify_type_ctor_if_special.
%
% Note that we have to effectively inline int_type_module_name here
% to allow the compiler to see that the <out,in> mode is a switch,
% and not just a disjunction.
builtin_type_name(builtin_type_int(int_type_int),    "int").
builtin_type_name(builtin_type_int(int_type_int8),   "int8").
builtin_type_name(builtin_type_int(int_type_int16),  "int16").
builtin_type_name(builtin_type_int(int_type_int32),  "int32").
builtin_type_name(builtin_type_int(int_type_int64),  "int64").
builtin_type_name(builtin_type_int(int_type_uint),   "uint").
builtin_type_name(builtin_type_int(int_type_uint8),  "uint8").
builtin_type_name(builtin_type_int(int_type_uint16), "uint16").
builtin_type_name(builtin_type_int(int_type_uint32), "uint32").
builtin_type_name(builtin_type_int(int_type_uint64), "uint64").
builtin_type_name(builtin_type_float,  "float").
builtin_type_name(builtin_type_string, "string").
builtin_type_name(builtin_type_char,   "character").

% Please keep this code in sync with builtin_type_name and
% classify_type_ctor_if_special.
int_type_module_name(int_type_int,    "int").
int_type_module_name(int_type_int8,   "int8").
int_type_module_name(int_type_int16,  "int16").
int_type_module_name(int_type_int32,  "int32").
int_type_module_name(int_type_int64,  "int64").
int_type_module_name(int_type_uint,   "uint").
int_type_module_name(int_type_uint8,  "uint8").
int_type_module_name(int_type_uint16, "uint16").
int_type_module_name(int_type_uint32, "uint32").
int_type_module_name(int_type_uint64, "uint64").

tvarset_merge_renaming(TVarSetA, TVarSetB, TVarSet, Renaming) :-
    varset.merge_renaming(TVarSetA, TVarSetB, TVarSet, Renaming).

tvarset_merge_renaming_without_names(TVarSetA, TVarSetB, TVarSet, Renaming) :-
    varset.merge_renaming_without_names(TVarSetA, TVarSetB, TVarSet, Renaming).

%---------------------------------------------------------------------------%
%
% Kinds.
%

:- interface.

    % Note that we don't support any kind other than `star' at the moment.
    % The other kinds are intended for the implementation of constructor
    % classes.
    %
:- type kind
    --->    kind_star
            % An ordinary type.

    ;       kind_arrow(kind, kind)
            % A type with kind `A' applied to a type with kind `arrow(A, B)'
            % will have kind `B'.

    ;       kind_variable(kvar).
            % A kind variable. These can be used during kind inference;
            % after kind inference, all remaining kind variables will be
            % bound to `star'.

:- type kvar_type
    --->    kind_var.
:- type kvar ==  var(kvar_type).

    % The kinds of type variables. For efficiency, we only have entries
    % for type variables that have a kind other than `star'. Any type variable
    % not appearing in this map, which will usually be the majority of type
    % variables, can be assumed to have kind `star'.
    %
:- type tvar_kind_map == map(tvar, kind).

:- pred get_tvar_kind(tvar_kind_map::in, tvar::in, kind::out) is det.

    % Return the kind of a type.
    %
:- func get_type_kind(mer_type) = kind.

:- implementation.

get_tvar_kind(Map, TVar, Kind) :-
    ( if map.search(Map, TVar, Kind0) then
        Kind = Kind0
    else
        Kind = kind_star
    ).

get_type_kind(type_variable(_, Kind)) = Kind.
get_type_kind(defined_type(_, _, Kind)) = Kind.
get_type_kind(builtin_type(_)) = kind_star.
get_type_kind(higher_order_type(_, _, _, _)) = kind_star.
get_type_kind(tuple_type(_, Kind)) = Kind.
get_type_kind(apply_n_type(_, _, Kind)) = Kind.
get_type_kind(kinded_type(_, Kind)) = Kind.

%---------------------------------------------------------------------------%
%
% Type classes.
%

:- interface.

    % A class constraint represents a constraint that a given list of types
    % is a member of the specified type class. It is an invariant of this data
    % structure that the types in a class constraint do not contain any
    % information in their prog_context fields. This invariant is needed
    % to ensure that we can do unifications, map.lookups, etc., and get the
    % expected semantics. (This invariant now applies to all types, but is
    % especially important here.)
    %
    % Values of type prog_constraint are used as keys in several maps;
    % currently (december 2014) these are represented by the types
    % ancestor_constraints, constraint_proof_map and typeclass_info_varmap.
    % We cannot store the context of each constraint in here, since after
    % we have put a constraint into one of these maps with one context,
    % we wouldn't find it if searching for it with another context, which
    % would thus defeat the purpose of those maps (to find common uses
    % of the same constraint).
    %
:- type prog_constraint
    --->    constraint(
                constraint_class        :: class_name,
                constraint_arg_types    :: list(mer_type)
            ).

:- type univ_exist_constraints
    --->    univ_exist_constraints(
                % Universally quantified constraints.
                univ_constraints    :: list(prog_constraint),

                % Existentially quantified constraints.
                exist_constraints   :: list(prog_constraint)
            ).

    % A functional dependency on the variables in the head of a class
    % declaration. This asserts that, given the complete set of instances
    % of this class, the binding of the range variables can be uniquely
    % determined from the binding of the domain variables.
    %
    % XXX Both lists should be one_or_more(tvar).
    %
:- type prog_fundep
    --->    fundep(
                domain          :: list(tvar),
                range           :: list(tvar)
            ).

:- type class_name == sym_name.
:- type class_id
    --->    class_id(class_name, arity).

:- type class_interface
    --->    class_interface_abstract
    ;       class_interface_concrete(list(class_decl)).
            % XXX The class_decl type is defined in prog_item.m.
            % The reference to that module here is undesirable.

:- type abstract_class_interface =< class_interface
    --->    class_interface_abstract.

:- type instance_method
    --->    instance_method(
                instance_method_pf_name_arity   :: pred_pf_name_arity,
                instance_method_proc_def        :: instance_proc_def,

                % The context of the instance declaration.
                instance_method_decl_context    :: prog_context
            ).

:- type instance_proc_def
    --->    instance_proc_def_name(
                % defined using the `pred(...) is <Name>' syntax
                sym_name
            )
    ;       instance_proc_def_clauses(
                % defined using clauses
                % XXX The item_clause_info type is defined in prog_item.m.
                % The reference to that module here is undesirable.
                cord(item_clause_info)
            ).

:- type instance_body
    --->    instance_body_abstract
    ;       instance_body_concrete(list(instance_method)).

:- type abstract_instance_body =< instance_body
    --->    instance_body_abstract.

:- func prog_constraint_get_class(prog_constraint) = class_name.
:- func prog_constraint_get_arg_types(prog_constraint) = list(mer_type).

:- type maybe_class_method
    --->    is_not_a_class_method
    ;       is_a_class_method.

:- implementation.

prog_constraint_get_class(Constraint) = Constraint ^ constraint_class.
prog_constraint_get_arg_types(Constraint) = Constraint ^ constraint_arg_types.

%---------------------------------------------------------------------------%
%
% Insts and modes.
%

:- interface.

    % This is how instantiatednesses and modes are represented.
    %
    % Note that the inst of a variable at a given program point encodes
    % five different kinds of distinct but related kinds of information:
    %
    % 1     Is the program point reachable?
    %
    % 2     Which nodes of the type tree of the variable are bound?
    %
    % 3a    Of the nodes which are bound, which are unique or clobbered?
    %
    % 4     Of the nodes which are bound, which are known to be bound to
    %       only a subset of the function symbols of the type of the affected
    %       type tree node, and if so, what is the subset?
    %
    % 5     Of the nodes which are bound, and which correspond to a higher
    %       order type, what is the determinism and what are the modes
    %       of the arguments of that higher order value?
    %
    % And eventually, we would want it to consider a sixth:
    %
    % 3b:   Of the nodes which are free, which are aliased to nodes of
    %       other variables, and if so, which ones?
    %
    % Each one of those can be handled reasonably easily. The reason why code
    % dealing with insts tends to be quite complex is that you have to consider
    % *all possible combinations* of these factors, which usually leads to
    % an explosion of complexity.
    %
    % The term "ground" answers the second question for a given var at a given
    % program point: all the var's nodes are bound. The different meanings
    % of "ground" differ in what restrictions, if any, they impose on
    % the answers to the third, fourth and fifth questions. Just by combining
    % the answers to "do we care about each of those three kinds of
    % distinctions or not", we have 2^3=8 possible meanings of "ground".
    % And they are NOT quite independent; in code in which some function
    % symbols of a type have higher order arguments while other function
    % symbols do not, the answers to the fourth and fifth questions
    % are in effect coupled together.
    %
    % And "ground" does not answer the second question for a given var
    % *unless* you specify the program point. If you know that e.g.
    % an argument X in a predicate has initial inst i1 whose meaning is
    % "either f(ground), or g(ground), or h(free)", then the inst X
    % at the program point at the start of the predicate body is not ground.
    % But if execution reaches a program point where we know that X
    % can be bound to only f or g, then X must be a ground term
    % at that program point, *even if no part of it has been bound
    % since the execution of this call has started*.
    %
    % The first question is often the easiest to handle, in that its answer
    % depends only on the program point, and not the variable. Yet answers
    % to the fourth question for a variable at a program point can affect
    % whether a later program point is reachable or not (by affecting
    % which tests may succeed and which may not), and answers to the first
    % question affect all the others (since branches of e.g. disjunctions
    % whose endpoint is unreachable don't have to bind variables that are
    % bound by the other branches), so the first question cannot be considered
    % separately from the others either :-(
    %
    % The order of these function symbols now follows their frequency of
    % occurrence, with the most frequently occurring function symbols first.
    % The result of specifying --inst-statistics during the stage 2 of a
    % bootcheck and then summarizing the results with tools/inst_statistics
    % on 2023 July 18 was as follow:
    %
    % proc  ground                      30976049                72.63%
    % proc  free/0                       7559540                17.73%
    % proc  bound                        4017523                 9.42%
    % proc  defined                        89760                 0.21%
    % proc  constrained                     4310                 0.01%
    % proc  any                             1775                 0.00%
    % proc  abstract                           0                 0.00%
    % proc  free/1                             0                 0.00%
    % proc  inst_var                           0                 0.00%
    % proc  not_reached                        0                 0.00%
    %
    % table ground                        968139                58.70%
    % table bound                         551660                33.45%
    % table free/0                        108101                 6.55%
    % table defined                        10291                 0.62%
    % table not_reached                     9865                 0.60%
    % table constrained                     1287                 0.08%
    % table abstract                           0                 0.00%
    % table any                                0                 0.00%
    % table free/1                             0                 0.00%
    % table inst_var                           0                 0.00%
    %
    % The "proc" entries come from insts in goals' instmap_deltas, while
    % the "table" entries come from insts in the global inst tables.
    % In several of these tables, the keys are pairs of insts that are
    % input to an operation, with the associated value being the result
    % of that operation. Several operations are trivial, and therefore
    % not worth putting into the table, if one of the insts is free/0.
    % This effect is certainly partially responsible for the lower frequency
    % of occurrence of free/0 in inst tables compared to instmap_deltas.
    %
:- type mer_inst
    --->        ground(uniqueness, ho_inst_info)
                % The ho_inst_info holds extra information
                % about higher-order values.

    ;           free

    ;           bound(uniqueness, inst_test_results, list(bound_functor))
                % The list(bound_functor) must be sorted.

    ;           defined_inst(inst_name)
                % A defined_inst is possibly recursive inst whose value is
                % stored in the inst_table. This is used both for user-defined
                % insts and for compiler-generated insts.

    ;           constrained_inst_vars(set(inst_var), mer_inst)
                % Constrained_inst_vars is a set of inst variables that are
                % constrained to have the same uniqueness as and to match_final
                % the specified inst.

    ;           not_reached

    ;           any(uniqueness, ho_inst_info)
                % The ho_inst_info holds extra information
                % about higher-order values.

    ;           inst_var(inst_var).

:- inst mer_inst_is_bound for mer_inst/0
    --->        bound(ground, ground, ground).

% There are some more insts for mer_inst in inst_lookup.m.

    % Values of this type give the outcome of various tests on an inst,
    % if that information is available when the inst is constructed.
    % The purpose is to allow those tests to work in constant time,
    % not time that is linear, quadratic or worse in the size of the inst.
    %
    % We attach this information to bound insts, since the only practical
    % way to make an inst big is to use bound insts.
    %
    % We could extend the number of tests whose results we can record,
    % but we should do so only when we have a demonstrated need, and I (zs)
    % don't yet see the need for them. However, here is a list of the tests
    % whose results we can consider adding, together with the names of the
    % predicates that could use them.
    %
    % Does the inst contain a nondefault func mode?
    %   inst_contains_nondefault_func_mode
    %
    % Does the inst contain any part that is uniq or mostly_uniq?
    %   make_shared_inst
    %
:- type inst_test_results
    --->    inst_test_results(
                inst_result_groundness,
                inst_result_contains_any,
                inst_result_contains_inst_names,
                inst_result_contains_inst_vars,
                inst_result_contains_types,
                inst_result_type_ctor_propagated
            )
    ;       inst_test_no_results
            % Implies
            %   inst_result_groundness_unknown
            %   inst_result_contains_any_unknown
            %   inst_result_contains_inst_names_unknown
            %   inst_result_contains_inst_vars_unknown
            %   inst_result_contains_types_unknown
            %   inst_result_no_type_ctor_propagated
    ;       inst_test_results_fgtc.
            % Implies
            %   inst_result_is_ground
            %   inst_result_does_not_contain_any
            %   inst_result_contains_inst_names_known(set.init)
            %   inst_result_contains_inst_vars_known(set.init)
            %   inst_result_contains_types_known(set.init)
            %   inst_result_no_type_ctor_propagated
            % It also implies that the inst does not contain any
            % typed insts, constrained insts or higher order type insts,
            % and that no part of it is unique or mostly_unique.

    % Does the inst represent a ground term?
:- type inst_result_groundness
    --->    inst_result_is_not_ground
    ;       inst_result_is_ground
    ;       inst_result_groundness_unknown.

    % Does "any" appear anywhere inside the inst?
:- type inst_result_contains_any
    --->    inst_result_does_not_contain_any
    ;       inst_result_does_contain_any
    ;       inst_result_contains_any_unknown.

:- type inst_result_contains_inst_names
    --->    inst_result_contains_inst_names_known(set(inst_name))
            % All the inst_names inside the inst are given in the set.
            % This is not a guarantee that all the inst_names in the set
            % appear in the inst, but it is a guarantee that an inst_name
            % that appears in the inst will appear in the set.
    ;       inst_result_contains_inst_names_unknown.

:- type inst_result_contains_inst_vars
    --->    inst_result_contains_inst_vars_known(set(inst_var))
            % All the inst_vars inside the inst are given in the set.
            % This is not a guarantee that all the inst_vars in the set
            % appear in the inst, but it is a guarantee that an inst_var
            % that appears in the inst will appear in the set.
    ;       inst_result_contains_inst_vars_unknown.

:- type inst_result_contains_types
    --->    inst_result_contains_types_known(set(type_ctor))
            % All the type_ctors inside typed_inst nodes of the inst
            % are given in the set. This is not a guarantee that all the
            % type_ctors in the set appear in the inst, but it is a guarantee
            % that a type_ctor that appears in the inst will appear in the set.
    ;       inst_result_contains_types_unknown.

:- type inst_result_type_ctor_propagated
    --->    inst_result_no_type_ctor_propagated
            % The inst is not known to have had a type_ctor propagated
            % into it.
    ;       inst_result_type_ctor_propagated(type_ctor).
            % The inst has had the given type_ctor propagated into it.
            % The type_ctor must have arity 0, since otherwise the propagation
            % code wouldn't know what type to propagate into the arguments.
            % (We could record a full type being propagated into the inst,
            % complete with type_ctor arguments, but that couldn't be
            % pre-propagated in inst_user.m in vast majority of cases
            % in which the argument types are not available.)

:- type uniqueness
    --->        shared
                % There might be other references.

    ;           unique
                % There is only one reference.

    ;           mostly_unique
                % There is only one reference, but there might be more
                % on backtracking.

    ;           clobbered
                % This was the only reference, but the data has
                % already been reused.

    ;           mostly_clobbered.
                % This was the only reference, but the data has already
                % been reused; however, there may be more references
                % on backtracking, so we will need to restore the old value
                % on backtracking.

    % Was the lambda goal created with pred/func or any_pred/any_func?
    %
:- type ho_groundness
    --->    ho_ground
    ;       ho_any.

    % The ho_inst_info type gives extra information about `ground' and `any'
    % insts relating to higher-order values.
    %
:- type ho_inst_info
    --->    higher_order(pred_inst_info)
            % The inst is higher-order, and we have mode/determinism
            % information for the value.
    ;       none_or_default_func.
            % No extra information is available, or the inst is function
            % with the default mode.

    % higher-order predicate terms are given the inst
    %   `ground(shared, higher_order(PredInstInfo))' or
    %   `any(shared, higher_order(PredInstInfo))'
    % where the PredInstInfo contains the extra modes and the determinism
    % for the predicate. The higher-order predicate term itself cannot be free.
    % If it contains non-local variables with inst `any' then it must be
    % in the latter form, otherwise it may be in the former.
    %
    % Note that calling/applying a higher-order value that has the `any'
    % inst may bind that variable further, hence these values cannot safely
    % be called/applied in a negated context.
    %
:- type pred_inst_info
    --->    pred_inst_info(
                % Is this a higher-order func mode or a higher-order pred mode?
                pred_or_func,

                % The modes of the additional (i.e. not-yet-supplied) arguments
                % of the pred; for a function, this includes the mode of the
                % return value as the last element of the list.
                list(mer_mode),

                % The register type to use for each of the additional arguments
                % of the pred. This field is only needed when float registers
                % exist, and is only set after the float reg wrappers pass.
                arg_reg_type_info,

                % The determinism of the predicate or function.
                determinism
            ).

:- type arg_reg_type_info
    --->    arg_reg_types_unset     % Unneeded or simply unset yet.
    ;       arg_reg_types(list(ho_arg_reg)).

:- type ho_arg_reg
    --->    ho_arg_reg_r
    ;       ho_arg_reg_f.

:- type inst_ctor
    --->    inst_ctor(sym_name, arity).

:- type bound_functor
    --->    bound_functor(cons_id, list(mer_inst)).

:- type inst_var_type
    --->    inst_var_type.

:- type inst_var    == var(inst_var_type).
:- type inst_term   == term(inst_var_type).
:- type inst_varset == varset(inst_var_type).

:- type head_inst_vars == map(inst_var, mer_inst).
:- type inst_var_sub   == map(inst_var, mer_inst).

:- type inst_defn
    --->    eqv_inst(mer_inst).

    % An `inst_name' is used as a key for the inst_table.
    % It is either a user-defined inst `user_inst(Name, Args)',
    % or some sort of compiler-generated inst, whose name
    % is a representation of its meaning.
    %
    % For example, `merge_inst(InstA, InstB)' is the name used for the
    % inst that results from merging InstA and InstB using `merge_inst'.
    % Similarly `unify_inst(IsLive, InstA, InstB, IsReal)' is
    % the name for the inst that results from a call to
    % `abstractly_unify_inst(IsLive, InstA, InstB, IsReal)'.
    % And `ground_inst' and `any_inst' are insts that result
    % from unifying an inst with `ground' or `any', respectively.
    % `typed_inst' is an inst with added type information.
    % `typed_ground(Uniq, Type)' a equivalent to
    % `typed_inst(ground(Uniq, no), Type)'.
    % Note that `typed_ground' is a special case of `typed_inst',
    % and `ground_inst' and `any_inst' are special cases of `unify_inst'.
    % The reason for having the special cases is efficiency.
    %
:- type inst_name
    --->    user_inst(sym_name, list(mer_inst))
    ;       unify_inst(is_live, unify_is_real, mer_inst, mer_inst)
    ;       merge_inst(mer_inst, mer_inst)
    ;       ground_inst(inst_name, uniqueness, is_live, unify_is_real)
    ;       any_inst(inst_name, uniqueness, is_live, unify_is_real)
    ;       shared_inst(inst_name)
    ;       mostly_uniq_inst(inst_name)
    ;       typed_ground(uniqueness, mer_type)
    ;       typed_inst(mer_type, inst_name).

:- type unify_inst_info
    --->    unify_inst_info(is_live, unify_is_real, mer_inst, mer_inst).
:- type merge_inst_info
    --->    merge_inst_info(mer_inst, mer_inst).
:- type ground_inst_info
    --->    ground_inst_info(inst_name, uniqueness, is_live, unify_is_real).
:- type any_inst_info
    --->    any_inst_info(inst_name, uniqueness, is_live, unify_is_real).

    % NOTE: `is_live' records liveness in the sense used by mode analysis.
    % This is not the same thing as the notion of liveness used by code
    % generation. See compiler/notes/glossary.html.
    %
:- type is_live
    --->    is_live
    ;       is_dead.

    % Unifications of insts fall into two categories, "real" and "fake".
    % The "real" inst unifications correspond to real unifications,
    % and are not allowed to unify with `clobbered' insts (unless
    % the unification would be `det').
    % Any inst unification which is associated with some code that
    % will actually examine the contents of the variables in question
    % must be "real". Inst unifications that are not associated with
    % some real code that examines the variables' values are "fake".
    % "Fake" inst unifications are used for procedure calls in implied
    % modes, where the final inst of the var must be computed by
    % unifying its initial inst with the procedure's final inst,
    % so that if you pass a ground var to a procedure whose mode
    % is `free -> list_skeleton', the result is ground, not list_skeleton.
    % But these fake unifications must be allowed to unify with `clobbered'
    % insts. Hence we pass down a flag to `abstractly_unify_inst' which
    % specifies whether or not to allow unifications with clobbered values.
    %
:- type unify_is_real
    --->    real_unify
    ;       fake_unify.

:- type mode_ctor
    --->    mode_ctor(sym_name, arity).

:- type mode_defn
    --->    eqv_mode(mer_mode).

:- type mer_mode
    --->    from_to_mode(mer_inst, mer_inst)
    ;       user_defined_mode(sym_name, list(mer_inst)).

:- type from_to_insts
    --->    from_to_insts(mer_inst, mer_inst).

%---------------------------------------------------------------------------%
%
% Determinism.
%

:- interface.

    % The `determinism' type specifies how many solutions a given procedure
    % may have.
    %
:- type determinism
    --->    detism_det
    ;       detism_semi
    ;       detism_multi
    ;       detism_non
    ;       detism_cc_multi
    ;       detism_cc_non
    ;       detism_erroneous
    ;       detism_failure.

:- type can_fail
    --->    can_fail
    ;       cannot_fail.

:- type soln_count
    --->    at_most_zero
    ;       at_most_one
    ;       at_most_many_cc
            % "_cc" means "committed-choice": there is more than one logical
            % solution, but the pred or goal is being used in a context where
            % we are only looking for the first solution.
    ;       at_most_many.

:- pred determinism_components(determinism, can_fail, soln_count).
:- mode determinism_components(in, out, out) is det.
:- mode determinism_components(out, in, in) is det.

:- implementation.

determinism_components(detism_det,       cannot_fail, at_most_one).
determinism_components(detism_semi,      can_fail,    at_most_one).
determinism_components(detism_multi,     cannot_fail, at_most_many).
determinism_components(detism_non,       can_fail,    at_most_many).
determinism_components(detism_cc_multi,  cannot_fail, at_most_many_cc).
determinism_components(detism_cc_non,    can_fail,    at_most_many_cc).
determinism_components(detism_erroneous, cannot_fail, at_most_zero).
determinism_components(detism_failure,   can_fail,    at_most_zero).

%---------------------------------------------------------------------------%
%
% Purity.
%

:- interface.

    % Purity indicates whether a goal can have side effects or can depend on
    % global state. See purity.m and the "Purity" section of the Mercury
    % language reference manual.
:- type purity
    --->    purity_pure
    ;       purity_semipure
    ;       purity_impure.

    % Compare two purities.
    %
:- pred less_pure(purity::in, purity::in) is semidet.

    % Sort of a "maximum" for impurity.
    %
:- func worst_purity(purity, purity) = purity.

    % Sort of a "minimum" for impurity.
    %
:- func best_purity(purity, purity) = purity.

:- implementation.

less_pure(P1, P2) :-
    WP = worst_purity(P1, P2),
    WP \= P2.

    % worst_purity/3 could be written more compactly, but this definition
    % guarantees us a determinism error if we add to type `purity'. We also
    % define less_pure/2 in terms of worst_purity/3 rather than the other way
    % around for the same reason.
    %
worst_purity(purity_pure, purity_pure) = purity_pure.
worst_purity(purity_pure, purity_semipure) = purity_semipure.
worst_purity(purity_pure, purity_impure) = purity_impure.
worst_purity(purity_semipure, purity_pure) = purity_semipure.
worst_purity(purity_semipure, purity_semipure) = purity_semipure.
worst_purity(purity_semipure, purity_impure) = purity_impure.
worst_purity(purity_impure, purity_pure) = purity_impure.
worst_purity(purity_impure, purity_semipure) = purity_impure.
worst_purity(purity_impure, purity_impure) = purity_impure.

    % best_purity/3 is written as a switch for the same reason as
    % worst_purity/3.
    %
best_purity(purity_pure, purity_pure) = purity_pure.
best_purity(purity_pure, purity_semipure) = purity_pure.
best_purity(purity_pure, purity_impure) = purity_pure.
best_purity(purity_semipure, purity_pure) = purity_pure.
best_purity(purity_semipure, purity_semipure) = purity_semipure.
best_purity(purity_semipure, purity_impure) = purity_semipure.
best_purity(purity_impure, purity_pure) = purity_pure.
best_purity(purity_impure, purity_semipure) = purity_semipure.
best_purity(purity_impure, purity_impure) = purity_impure.

%---------------------------------------------------------------------------%
%
% Predicates.
%

:- interface.

    % The kinds of auxiliary predicates we may need to generate
    % to implement a mutable.
    %
    % The first group represent the public predicates, the predicates
    % that user programs may call. The usual (non-constant) kind of mutable
    % will have the standard get and set predicates, and if attached
    % to the I/O state, will have the I/O get and set predicates as well.
    % Constant mutables will have the constant get and set predicates instead
    % (see below).
    %
    % The second group represent the private predicates, the predicates
    % that user programs should not call (and which are not documented).
    % The unsafe get and set predicates may be needed to implement the other,
    % user-visible get and set predicates, and the lock and unlock predicates
    % have the same role. The initialization predicate is called by the
    % implementation itself at program startup, and it may need the help
    % of the preinit predicate.
    %
    % Note that we need a set predicate even for constant mutables.
    % The reason is that the init predicate needs to do two things:
    % execute arbitrary Mercury code (call functions etc) to generate
    % the initial (and for constant mutables, also final) value of the mutable,
    % and then store this value in persistent storage. However, even if
    % we could create an item that contains both Mercury code and backend
    % (e.g. C) code, which is currently not possible, this would require
    % the second part to be a foreign_proc goal. Such goals include a reference
    % to the predicate they implement. That predicate would be equivalent
    % to the set predicate.
    %
    % In these circumstances, avoiding the need for a set predicate
    % would require significant changes to the structures of items.
    % It is much simpler to use a predicate and give it a name that
    % makes it clear people that shouldn't use it.
    %
:- type mutable_pred_kind
    --->    mutable_pred_std_get
    ;       mutable_pred_std_set
    ;       mutable_pred_io_get
    ;       mutable_pred_io_set
    ;       mutable_pred_constant_get
    ;       mutable_pred_constant_secret_set

    ;       mutable_pred_unsafe_get
    ;       mutable_pred_unsafe_set
    ;       mutable_pred_lock
    ;       mutable_pred_unlock
    ;       mutable_pred_pre_init
    ;       mutable_pred_init.

:- type tabling_aux_pred_kind
    --->    tabling_aux_pred_stats
    ;       tabling_aux_pred_reset.

:- type solver_type_pred_kind
    --->    solver_type_to_ground_pred
    ;       solver_type_to_any_pred
    ;       solver_type_from_ground_pred
    ;       solver_type_from_any_pred.

%---------------------------------------------------------------------------%
%
% Goals.
%
%
% NOTE The representation of goals in the parse tree is defined in
% prog_item.m, because goals in the parse tree don't *themselves* survive
% being translated into HLDS. However, some of their *components* do survive.
% The following types define these components.
%

:- interface.

    % These type equivalences are for the types of program variables
    % and associated structures.
    %
:- type prog_var_type
    --->    prog_var_type.
:- type prog_var    == var(prog_var_type).
:- type prog_varset == varset(prog_var_type).
:- type prog_substitution == substitution(prog_var_type).
:- type prog_var_renaming == map(prog_var, prog_var).
:- type prog_term   == term(prog_var_type).

    % What to print when printing variable names.
    % You can get the effect of printing variable numbers only
    % by passing an empty varset, which effectively makes *all* variables
    % unnamed, but having an explicit option for this is more readable.
    %
    % XXX When we are printing variable names for developers in HLDS dumps,
    % there are no constraints on which of these values we want choose.
    % But in two other uses cases, there are restrictions.
    %
    % The first and more obvious such use case is when we are printing
    % error messages for users. Since users can't be expected to care about
    % variable numbers, or even know about them, the only viable choice
    % in that use case is print_name_only.
    %
    % The second and less obvious such use case is when we are generating
    % Mercury code to be put into .int* or .*opt files. In that case, we have
    % two conflicting interests.
    %
    % The first interest is that we don't want to put variable names into
    % such files if we can help it, because if we do, and the user changes
    % a variable name, we will have to recompile every other file that depends
    % on that .int* or .*opt file.
    %
    % The second interest is that sometimes we *do* have to put the variable
    % name into the .int* or .*opt file in exactly the same form as it has
    % in the .m file. The root cause of this is that if the type signature
    % of a predicate or function includes type variable T, then we document
    % the fact that the type_info for the type bound at runtime to that
    % type variable will be available in the body of a C foreign_proc that
    % implements that predicate or function in a variable named TypeInfo_for_T.
    % Most foreign_procs don't need this access, but the ones that do,
    % can't do without it.
    %
    % This fact has several effects.
    %
    % - We have to use print_name_only for the type variables in the
    %   signatures of predicates and functions that have foreign_procs.
    %
    % - If we don't know whether a predicate or function has foreign_procs,
    %   we still have to use print_name_only.
    %
    % - If we *do* know whether a predicate or function has foreign_procs,
    %   but we have to interoperate with code that doesn't, we still have
    %   to use print_name_only.
    %
    % - Pragmas that refer to type_infos in predicate and function signatures,
    %   such as type_spec pragmas, have to follow the same rules.
    %
    % - Since typeclass declarations contain declarations of method predicates
    %   and/or functions, they have to follow the same rules.
    %
    % - Instance declarations then have to follow the rules followed by
    %   typeclass declarations.
    %
    % - There may be more consequences, but this is where I (zs) have run
    %   out of the patience needed to track them down.
    %
    % This situation can be fixed in one (or both) of two ways.
    %
    % - The first way is to simplify change the convention for the names
    %   of type_info variables in foreign_procs. We could have an interim
    %   period where, if the relevant type signature contains type variables
    %   named e.g. K and V, in that order, then the type type_info for K
    %   would be available in *two* variables, named TypeInfo_for_K and
    %   TypeInfo_for_V_1, and similarly the type_info for V would be available
    %   in TypeInfo_for_V and TypeInfo_for_V_2. People could replace code
    %   that uses the first of these with code using the second, then
    %   we could stop defining the old variable names, and then we would be
    %   free of the compulsion to use print_name_only for all those item types
    %   listed above.
    %
    % - The second way is to change the compiler so that when matching
    %   variables from two different varsets that both represent the same
    %   conceptual signature, such as the signature of a predicate, we do
    %   so using variable numbers, not using variable names.
    %
    % The first seems easier.
    %
:- type var_name_print
    --->    print_name_only
    ;       print_name_and_num
    ;       print_num_only.

:- type prog_context == term_context.

:- type trace_expr(Base)
    --->    trace_base(Base)
    ;       trace_not(trace_expr(Base))
    ;       trace_op(trace_op, trace_expr(Base), trace_expr(Base)).

:- type trace_op
    --->    trace_or
    ;       trace_and.

:- type trace_compiletime
    --->    trace_flag(string)
    ;       trace_grade(trace_grade)
    ;       trace_trace_level(trace_trace_level).

:- type trace_grade
    --->    trace_grade_debug
    ;       trace_grade_ssdebug
    ;       trace_grade_prof
    ;       trace_grade_profdeep
    ;       trace_grade_par
    ;       trace_grade_trail
    ;       trace_grade_rbmm
    ;       trace_grade_llds
    ;       trace_grade_mlds
    ;       trace_grade_c
    ;       trace_grade_csharp
    ;       trace_grade_java.

:- type trace_trace_level
    --->    trace_level_shallow
    ;       trace_level_deep.

:- type trace_runtime
    --->    trace_envvar(string).

:- type trace_mutable_var
    --->    trace_mutable_var(
                trace_mutable_name      :: string,
                trace_state_var         :: prog_var
            ).

:- type atomic_component_state
    --->    atomic_state_var(prog_var)
    ;       atomic_var_pair(prog_var, prog_var).

:- pred parse_trace_grade_name(string, trace_grade).
:- mode parse_trace_grade_name(in, out) is semidet.
:- mode parse_trace_grade_name(out, in) is det.
:- mode parse_trace_grade_name(out, out) is multi.

:- pred valid_trace_grade_name(string::out) is multi.

    % Values of this type are part of the representation
    % of the disable_warnings scope.
:- type goal_warning
    --->    goal_warning_singleton_vars
    ;       goal_warning_repeated_singleton_vars
    ;       goal_warning_occurs_check
    ;       goal_warning_non_tail_recursive_calls
    ;       goal_warning_suspicious_recursion
    ;       goal_warning_no_solution_disjunct
    ;       goal_warning_unknown_format_calls.

:- implementation.

% If you update this, you also need to update the corresponding section
% of doc/reference_manual.texi.
parse_trace_grade_name("debug", trace_grade_debug).
parse_trace_grade_name("ssdebug", trace_grade_ssdebug).
parse_trace_grade_name("prof", trace_grade_prof).
parse_trace_grade_name("profdeep", trace_grade_profdeep).
parse_trace_grade_name("par", trace_grade_par).
parse_trace_grade_name("trail", trace_grade_trail).
parse_trace_grade_name("rbmm", trace_grade_rbmm).
parse_trace_grade_name("llds", trace_grade_llds).
parse_trace_grade_name("mlds", trace_grade_mlds).
parse_trace_grade_name("c", trace_grade_c).
parse_trace_grade_name("csharp", trace_grade_csharp).
parse_trace_grade_name("java", trace_grade_java).

valid_trace_grade_name(GradeName) :-
    parse_trace_grade_name(GradeName, _).

%---------------------------------------------------------------------------%
%
% Trailing and minimal model tabling analysis.
%

:- interface.

:- type trailing_status
    --->    trail_may_modify
    ;       trail_will_not_modify
    ;       trail_conditional.

:- type mm_tabling_status
    --->    mm_tabled_may_call
    ;       mm_tabled_will_not_call
    ;       mm_tabled_conditional.

%---------------------------------------------------------------------------%
%
% Parts of items that are needed beyond the construction of the HLDS.
%

:- interface.

    % What kind of promise does a promise item contain?
    %
:- type promise_type
    --->    promise_type_exclusive
            % A promise that given two disjuncts, at most one is true.

    ;       promise_type_exhaustive
            % A promise that given two disjuncts, at least one is true.

    ;       promise_type_exclusive_exhaustive
            % A promise that given two disjuncts, exactly one is true.

    ;       promise_type_true.
            % A promise that the given goal is true.

:- type type_and_mode
    --->    type_and_mode(mer_type, mer_mode).

:- type item_seq_num
    --->    item_seq_num(int)
            % This item was read in from a file, and the argument
            % specifies the position of this item in the sequence of items
            % read in from that file.
    ;       item_no_seq_num.
            % This item was not read in from a file.

%---------------------------------------------------------------------------%
%
% Module system.
%

:- interface.

:- type name_arity
    --->    name_arity(string, arity).

:- type sym_name_arity
    --->    sym_name_arity(sym_name, arity).

:- type sym_name_pred_form_arity
    --->    sym_name_pred_form_arity(sym_name, pred_form_arity).

:- type pf_sym_name_arity
    --->    pf_sym_name_arity(pred_or_func, sym_name, pred_form_arity).

    % This type is part of a family of related types, the rest of which are
    % in prog_item.m. Its name fits in with those types.
    %
:- type pred_pf_name_arity
    --->    pred_pf_name_arity(pred_or_func, sym_name, user_arity).

    % XXX ARITY While the concept of arity seems simple, it is not, because
    % the compiler has to juggle several different notions of arity.
    %
    % Consider a function declaration as simple as
    %
    %   :- func length(list(T)) = int.
    %
    % This function has three different arities for three different purposes.
    %
    % - It has one user visible argument, so if arity counts these, then
    %   its arity is 1.
    %
    % - Its initial form in the compiler adds the return value to the argument
    %   list, so if arity counts these, then its arity is 2.
    %
    % - The polymorphism transformation then adds a typeinfo arg for T,
    %   so if arity counts these as well, then its arity is 3.
    %
    % We might call these different kinds arities something like
    % "user arity", "pred form arity" and "extended arity" respectively.
    % (Better names welcome.)
    %
    % We should replace this single equivalence type with three separate
    % notag types, one for each of these kinds of arities, and all uses
    % of the plain just "arity" type should be replaced by these.
    % The user_arity and pred_form_arity types below are a start on this.
    %
    % XXX ARITY We should eventually replace these ints with uint16, since
    % an arity can never be negative, and we do not support arities higher
    % than "about 1000" according to the LIMITATIONS.md file. (The main reason
    % for the upper limit is that the abstract machine we use as the target
    % in LLDS grades has 1024 registers, some of which are needed for
    % purposes such as the semidet success indicator, and the type_info
    % and/or typeclass_info arguments added by polymorphism.)
:- type arity == int.
:- type user_arity
    --->    user_arity(int).
:- type pred_form_arity
    --->    pred_form_arity(int).

:- func arg_list_arity(list(T)) = pred_form_arity.

    % Given a predicate or function's *original* pred_form_arity,
    % and its *current* list of arguments (in the form of arg variables,
    % arg types, arg modes, etc), return the number of extra arguments
    % added to the original arguments.
    %
:- func num_extra_args(pred_form_arity, list(T)) = int.

    % Describes whether an item can be used without an explicit module
    % qualifier.
    %
:- type need_qualifier
    --->    must_be_qualified
    ;       may_be_unqualified.

    % Does a module contain the predicate main/2?
    %
:- type has_main
    --->    has_main
    ;       no_main.

%---------------------------------------------------------------------------%

:- implementation.

:- import_module int.

arg_list_arity(ArgList) = pred_form_arity(list.length(ArgList)).

num_extra_args(pred_form_arity(OrigNumArgs), Args) = NumExtraArgs :-
    list.length(Args, NumArgs),
    NumExtraArgs = NumArgs - OrigNumArgs.

%---------------------------------------------------------------------------%
:- end_module parse_tree.prog_data.
%---------------------------------------------------------------------------%
