SourceForge.net Logo

[Release b]
<t4m_bug_expandfunctype>
Tue Jun  8 21:04:16 WEST 2004

In the current release of tendra4minix (a), after fixing <t4m_bug_templ_dflt>,
the compilation of the file templ_dflt_i.C,

template <class T> void g(T e, int d = T(0)) {}
template <class T> void f(T t) { g(t, t); }
int main() { f(1); return 0; }

produces these errors

"templ_dflt_i.C", line 2: Error:
  [ISO 14.7.1]: In instantiation of template 'f < int >' (at line 3).
  [ISO 5.4]: Illegal conversion from type 'int' to type 'T'.
  [ISO 5.2.3]: Can't perform this conversion using a function-style cast.

"templ_dflt_i.C", line 2: Error:
  [ISO 14.7.1]: In instantiation of template 'f < int >' (at line 3).
  [ISO 8.5]: In initialization of 'd'.
  [ISO 5.4]: Illegal conversion from type 'T' to type 'int'.
  [ISO 8.5]: Can't perform this conversion by initialization.

Both errors are ERR_expr_cast_invalid, generated (but not reported) near the
end of the function cast_exp [cast.c], in the part that reads "/* No other  
conversions are allowed */". The first error is being reported in the calling
function apply_nary [operator.c], in the case lex_cast, which is being
invoked by copy_exp [copy.c], which in turn is being called by expand_exp
[token.c]. The second error is being reported in the function init_error
[initialise.c], which is invoked by init_general [initialise.c] when an error
occurs in the previous call to init_assign [initialise.c], which is the
function that calls cast_exp [cast.c] (through convert_assign [assign.c]).
Both invocations, that of expand_exp and that of init_general, are made during
an invocation of the function expand_func_type [token.c], called by expand_type
[token.c], and both happen during the analysis of the default argument in an
invocation of the template function 'g' in the file templ_dflt_i.C. See below
a detailed call tree.

The error disappears when we remove the default argument from the declaration
of the template function 'g', but also, which is more strange, it disappears
when we use an explicit instantiation in the call to the function 'g',

template <class T> void g(T e, int d = T(0)) {}
template <class T> void f(T t) { g<T>(t, t); }
int main() { f(1); return 0; }

This is because things are done in a completely different way in this case;
the function instance_func [instance.c] is called on 'g' with [T := T] during
the analysis of the template function 'f'. In the case that fails
(templ_dflt_i.C) the call to instance_func on 'g' is done during the execution
of copy_template [instance.c] for the instance 'f<int>'.

But this distinction between orders of instantiation is not the key to
understand what is happening. What is happening is simply that initializers for
default arguments are being processed during the expansion of the types in the
template function declaration. This choice is questionable, to say the least.

The problem in templ_dflt_i.C happens because expand_func_type [token.c] tries
to expand the initializer for the default argument when either this initializer
or its type depend on a template parameter. And this expansion must not be
made when the parameter T has not been bound yet. Let's trace a call tree
in order to understand what is happening. We start at the invocation of
copy_template [instance.c], which is the function in charge of instantiating
the definition of templates; in this case, 'template <class T> void f<T>(T)'
is being instantiated with [T := int]. We will unfold the call tree in several
stages,

copy_template, force = 0, id = void f<int>(int), ds = 23068807
  copy_exp, 65 = exp_sequence_tag
    copy_exp, 84 = exp_location_tag
      copy_exp, 0 = exp_identifier_tag
      copy_exp: returning
    copy_exp: returning
    copy_exp, 84 = exp_location_tag
      copy_exp, 80 = exp_op_tag
        apply_unary, 205 = lex_discard
          copy_exp, 80 = exp_op_tag
            apply_unary, 123 = lex_void
              copy_exp, 81 = exp_opn_tag
                apply_nary, 342 = lex_func_Hop
                  copy_func_exp, 0 = exp_identifier_tag [*]
                    ...
                  copy_func_exp: returning
                  copy_exp_list
                    ...
                  copy_exp_list: returning
                  make_func_exp, 0 = exp_identifier_tag [**]
                    ...
                  make_func_exp: returning
                apply_nary: returning
              copy_exp: returning 22 = exp_func_id_tag
            apply_unary: returning
          copy_exp: returning 22 = exp_func_id_tag
        apply_unary: returning
      copy_exp: returning 22 = exp_func_id_tag
    copy_exp: returning 84 = exp_location_tag
  copy_exp: returning 65 = exp_sequence_tag
  copy_template, force = 0, id = void g<int>(int, int = 0), ds = 23068807
    copy_exp, 65 = exp_sequence_tag
      copy_exp, 84 = exp_location_tag
        copy_exp, 0 = exp_identifier_tag
        copy_exp: returning
      copy_exp: returning
    copy_exp: returning
  copy_template: returning, id_storage(id) = 23085223
copy_template: returning, id_storage(id) = 23068839

The errors are produced during the execution of copy_func_exp [copy.c] (marked
with [*] in the call tree above), which copies the function expression
'g<T>'. Then, copy_exp_list [copy.c] copies the arguments '(t, t)' of the
application, and finally make_func_exp [function.c] (marked with [**] in the
call tree above) rebuilds the application 'g<T>(t, t)'. In the call tree
above, two invocations of expand_type [token.c] are made to expand the type of
the template function 'g'. The first invocation, made at the beginning of
copy_func_exp [copy.c], ends in a call to cast_exp [cast.c] that fails (it is
the first error that's generated), followed by a call to init_general
[initialise.c] that also fails (it is the second error that's generated); both
fail for the same reason: the template parameter 'T' is still unbound, and thus
no cast is possible. The second call to expand_type [token.c] is made in the
function copy_id [redeclare.c], called from instance_func [instance.c], called
from deduce_args [instance.c], called from resolve_call [overload.c], called
from make_func_exp [function.c] (marked with [**] in the call tree above), but
this time cast_exp [cast.c] succeeds.

The following is the call subtree that starts at copy_func_exp [copy.c] (marked
with [*] in the call tree above), where the wrong call to expand_type [token.c]
is made,

copy_func_exp, 0 = exp_identifier_tag
  expand_type, template <class T> void (T, int), 14 = type_templ_tag, rec = 1
    expand_templ_type, template <class T> void (T, int), rec = 1
      expand_type, void (T, int), 8 = type_func_tag, rec = 1
        expand_func_type, void (T, int), rec = 1
          expand_type, t = void, 3 = type_top_tag, rec = 1
          expand_type: returning void, 3 = type_top_tag
          expand_type, t = T, 13 = type_token_tag, rec = 1
          expand_type: returning T, 13 = type_token_tag
          expand_type, t = int, 1 = type_integer_tag, rec = 1
          expand_type: returning int, 1 = type_integer_tag
          /* expanded = 0 */
          depends_on_exp, 81 = exp_opn_tag, use = 0
          depends_on_exp: returning 1
          /* Needs expansion */
          /* Expand remaining items */
          copy_id, id = e
            expand_type, t = T, 13 = type_token_tag, rec = 1
            expand_type: returning T, 13 = type_token_tag
          copy_id: returning
          copy_id, id = d
            expand_type, t = int, 1 = type_integer_tag, rec = 1
            expand_type: returning int, 1 = type_integer_tag
          copy_id: returning
          expand_exp, 81 = exp_opn_tag, rec = 1, stmt = 0
            copy_exp, 81 = exp_opn_tag
              expand_type, t = T, 13 = type_token_tag, rec = 1
              expand_type: returning T, 13 = type_token_tag
              apply_nary, 185 = lex_cast
                copy_exp_list
                  copy_exp, 4 = exp_int_lit_tag
                    expand_type, t = int, 1 = type_integer_tag, rec = 1
                    expand_type: returning int, 1 = type_integer_tag
                    expand_nat, 0
                    expand_nat: returning 0
                  copy_exp: returning
                copy_exp_list: returning
                cast_exp, t = T, 4 = exp_int_lit_tag, cast = 15
                  expand_type, t = T, 13 = type_token_tag, rec = 0
                  expand_type: returning T, 13 = type_token_tag
                  ERR_expr_cast_invalid
                cast_exp: returning 44 = exp_cast_tag
              apply_nary: returning
            copy_exp: returning, 44 = exp_cast_tag
          expand_exp: returning, 44 = exp_cast_tag
          init_general
            init_assign
              cast_exp
                expand_type, t = T, 13 = type_token_tag, rec = 0
                expand_type: returning T, 13 = type_token_tag
                ERR_expr_cast_invalid
              cast_exp: returning
            init_assign: returning
          init_general: returning
          destroy_general
            init_default
            init_default: returning
          destroy_general: returning
        expand_func_type: returning void (T, int)
      expand_type: returning void (T, int)
    expand_templ_type: returning template <class T> void (T, int)
  expand_type: returning template <class T> void (T, int)
copy_func_exp: returning

Note the many calls to expand_type [token.c] on the argument 'T' that occur in
this tree. There is one at the beginning of expand_func_type [token.c] for the
purposes of copying the types of the parameters; then there is another inside
copy_id [redeclare.c]; another one during the execution of the copy_exp
[copy.c] that is called at the end of expand_exp [token.c]; and yet another one
inside cast_exp [cast.c]. All of them fail to expand the token 'T' (remember
that the formal parameters of a token are also tokens in its body, and they are
evaluated (i. e., projected) with the same function that is used to apply
tokens to arguments, named apply_*_token in C, and *_apply_token in TDF, see
page 9 of "A Guide to TDF" for some comments in this regard). All fail because
the token 'T' has not been bound to the type 'int' yet; this is done later,
during the execution of make_func_exp [function.c].

The following is the call subtree that starts at make_func_exp [function.c]
(marked with [**] in the call tree above), where the correct call to
expand_type [token.c] is made,

make_func_exp [function.c], 0 = exp_identifier_tag
  resolve_call [overload.c], id = template <class T> void g(T, int = T(0))
    deduce_args [instance.c], id = template <class T> void g(T, int = T(0))
      deduce_param [instance.c], t = T, s = int
        eq_type_qual [chktype.c], t = T, s = int, qu = 0
          eq_type_aux [chktype.c]
          eq_type_aux: returning 0
          unify_types [chktype.c]
            unify_type [chktype.c]
              define_type_token [tokdef.c], id = T, t = int, qual = 0
              define_type_token: returning 1
            unify_type: returning 1
          unify_types: returning 1
        eq_type_qual: returning 1
      deduce_param: returning 1
      inst_func_deduce [instance.c]
        instance_func [instance.c]
          copy_id [redeclare.c]
            expand_type [token.c], template <class T> void (T, int)
              expand_templ_type, template <class T> void (T, int)
                expand_type, void (T, int), 8 = type_func_tag, rec = 1
                  expand_func_type, void (T, int), rec = 1
                    expand_type, t = void, 3 = type_top_tag, rec = 1
                    expand_type: returning void, 3 = type_top_tag
                    expand_type, t = T, 13 = type_token_tag, rec = 1
                    expand_type: returning int, 1 = type_integer_tag
                    expand_type, t = int, 1 = type_integer_tag, rec = 1
                    expand_type: returning int, 1 = type_integer_tag
                    /* expanded = 1 */
                    /* Expand remaining items */
                    copy_id, id = e
                      expand_type, t = T, 13 = type_token_tag, rec = 1
                      expand_type: returning int, 1 = type_integer_tag
                    copy_id: returning
                    copy_id, id = d
                      expand_type, t = int, 13 = type_integer_tag, rec = 1
                      expand_type: returning int, 1 = type_integer_tag
                    copy_id: returning
                    expand_exp, 81 = exp_opn_tag, rec = 1, stmt = 0
                      copy_exp, 81 = exp_opn_tag
                        expand_type, t = T, 13 = type_token_tag, rec = 1
                        expand_type: returning int, 1 = type_integer_tag
                        apply_nary, 185 = lex_cast
                          copy_exp_list
                            copy_exp, 4 = exp_int_lit_tag
                              expand_type, t = int, 1 = type_integer_tag, rec=1
                              expand_type: returning int, 1 = type_integer_tag
                              expand_nat, 0
                              expand_nat: returning 0
                            copy_exp: returning
                          copy_exp_list: returning
                          cast_exp, t = int, 4 = exp_int_lit_tag, cast = 15
                          cast_exp: returning 4 = exp_int_lit_tag
                        apply_nary: returning
                      copy_exp: returning, 4 = exp_int_lit_tag
                    expand_exp: returning 0, 4 = exp_int_lit_tag
                    init_general
                      init_assign
                        cast_exp, t = int, 4 = exp_int_lit_tag, cast = 0
                        cast_exp: returning 4 = exp_int_lit_tag
                      init_assign: returning
                    init_general: returning
                    destroy_general
                      init_default
                      init_default: returning
                    destroy_general: returning
                  expand_func_type: returning void (int, int)
                expand_type: returning void (int, int), 8 = exp_func_type
              expand_templ_type: returning void (int, int)
            expand_type: returning void (int, int)
          copy_id: returning
        instance_func: returning
      inst_func_deduce: returning
    deduce_args: returning
  resolve_call: returning
  use_func_id, id = void g<int>(int, int = 0), ds = 23068800, expl = 1
    define_template, id = void g<int>(int, int = 0), ds = 23068803, expl = 0
    define_template: returning, ds = 23068807
  use_func_id: returning, dspec = 23068807
  cast_args, id = void g<int>(int, int = 0), ds = 23068807
    ...
  cast_args: returning
make_func_exp: returning

The subtree rooted at the invocation of expand_type [token.c] on the type
'template <class T> void (T, int)' is similar in both traces, but in the second
trace (corresponding to make_func_exp [function.c]) the token 'T' gets
successfully expanded to the type 'int' (note the call to define_type_token
[tokdef.c] near the beginning of the subtree).

We could fix this problem modifying the function cast_exp [cast.c] to test
whether the token 'T' is free in the type of the default argument. We would
change

    /* Find the operand type */
    s = DEREF_type ( exp_type ( a ) ) ;
    ns = TAG_type ( s ) ;

    /* Check for template types */
    if ( ns == type_token_tag && is_templ_type ( s ) ) {
	e = cast_templ_type ( t, a, cast ) ;
	return ( e ) ;
    }

for

    /* Find the operand type */
    s = DEREF_type ( exp_type ( a ) ) ;
    ns = TAG_type ( s ) ;

    /* Check for template types */
    if ( ns == type_token_tag ) {
	IDENTIFIER sid = DEREF_id ( type_token_tok ( s ) ) ;
	TOKEN tok = DEREF_tok ( id_token_sort ( sid ) ) ;
	if ( ( in_template_decl && is_templ_param ( sid ) )
	    || !is_bound_tok ( tok, 0 ) ) {
	    e = cast_templ_type ( t, a, cast ) ;
	    return ( e ) ;
	}
    }

(It would be necessary to do the same for the other similar conditionals inside
cast_exp [cast.c].) However, although it works, this solution is not general
enough. The following file (templ_dflt_b.C),

template <class T> class H {
  T h;
public:
  H(const T &t) : h(t) {}
};
template <class T> void g(const H<T> &e = H<T>(0)) {}
template <class T> void f(T t) { g(H<T>(t)); }
int main() { f(1); return 0; }

produces the error

"templ_dflt_b.C", line 7: Error:
  [ISO 14.7.1]: In instantiation of template 'f < int >' (at line 8).
  [ISO 13.3.1.3]: None of the overloaded constructors 'H < T >::H' is viable for given call.

This time, the function apply_nary [operator.c] (called on the operator 146 =
lex_static_Hcast from copy_exp (exp_opn_tag), called from expand_exp [token.c],
called from expand_func_type [token.c]), calls convert_constr [construct.c] and
the overload resolution for the constructor H<T>::H fails because 'T' is free.

The previous example suggests that, at least, we should prevent the expansion
of default arguments in the function expand_func_type [token.c] in those
cases where there are free template parameters either in the type or in the
default argument of a function parameter.

We will modify the function expand_templ_type [token.c] so that it invokes
the function expand_func_type [token.c] directly in the case of template
functions (without going through expand_type [token.c]), passing a flag that
indicates whether expand_func_type [token.c] needs to expand the default
arguments of the function. In detail,

[ ] Add the prototype

static TYPE expand_func_type PROTO_S ( ( TYPE, int, int ) ) ;

    before the definition of the function expand_templ_type [token.c].

[ ] In the function expand_templ_type [token.c], change

    } else {
	/* Other template types */
	s = expand_type ( s, rec ) ;
    }

    for

    } else if ( IS_type_func ( s ) ) {
	/* Template functions */
	s = expand_func_type ( s, rec, IS_NULL_tok ( sort ) ) ;
    } else {
	/* Other template types */
	s = expand_type ( s, rec ) ;
    }

    so that expand_func_type [token.c] receives a flag which tells whether all
    template parameters have already been bound.

[ ] Add the new boolean parameter to the definition of expand_func_type
    [token.c],

static TYPE expand_func_type
    PROTO_N ( ( t, rec, all_bound ) )
    PROTO_T ( TYPE t X int rec X int all_bound )

[ ] In the body of expand_func_type [token.c], change the conditional

	    if ( !IS_NULL_exp ( e ) ) {
		/* Copy default argument */

    for

	    if ( !IS_NULL_exp ( e ) && all_bound ) {
		/* Copy default argument */

[ ] Finally, in the function expand_type [token.c], change

	case type_func_tag : {
	    /* Function types */
	    if ( rec ) t = expand_func_type ( t, rec ) ;
	    break ;
	}

    for

	case type_func_tag : {
	    /* Function types */
	    if ( rec ) t = expand_func_type ( t, rec, 1 ) ;
	    break ;
	}

    in order to preserve the execution path for non-template function types.

Are we breaking something using this solution? A possible source of problems
is that situation in which expand_type is invoked on a template function
type where some template parameters are free and some are bound: none of the
default arguments will be copied. It is improbable that such situation may
happen, since the spec X3J16/96-0225 WG21/N1043 allows partial specializations
only of template classes, never of template functions (_temp.class.spec_,
14.5.4). On the other hand, explicit specialization of template functions may
not have default arguments (_temp.expl.spec_, 14.7.3, paragrah 3). Using
specific examples, I have checked that these restrictions are correctly
enforced in the function bind_templ_spec [instance.c], and they are reported
as the errors ERR_temp_decl_func and ERR_temp_class_spec_darg.

Finally, another option could be to adapt one by one all functions like
cast_exp [cast.c] and convert_constr [construct.c] that can not deal with
free tokens. We would do it in the way that was detailed above for cast_exp.