www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 3869] New: Unreasonable error without line number: "recursive template expansion"

reply d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3869

           Summary: Unreasonable error without line number: "recursive
                    template expansion"
           Product: D
           Version: 2.040
          Platform: Other
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: DMD
        AssignedTo: nobody puremagic.com
        ReportedBy: Norbert Nemec-online.de



PST ---
The code below creates an unreasonable error without a line number. There is no
reason why this kind of finite recursion should not work. Simple workarounds
exist. In any case, the error message should contain a line number to help fix
the problem.

-----------
import std.stdio;

struct sum(A,B) {
    A a;
    B b;

    auto opAdd(T)(T a) { return .sum!(sum,T)(this,a); }
}


struct base {
    auto opAdd(T)(T a) { return .sum!(base,T)(this,a); }
}

void main() {
    base a,b,c;

    // first a few working examples
    writeln(typeid(a));       // base
    writeln(typeid(a+b));     // sum!(base,base).sum
    writeln(typeid(a+(b+c))); // sum!(base,sum!(base,base)).sum

    sum!(sum!(base,base),base) d;
    writeln(typeid(d));       // sum!(sum!(base,base),base).sum

    // the following produces
    //   Error: recursive template expansion for
    //   template argument sum!(base,base)
    writeln(typeid((a+b)+c)); // sum!(sum!(base,base),base).sum
}
------------

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 02 2010
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3869


Don <clugdbug yahoo.com.au> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |diagnostic
                 CC|                            |clugdbug yahoo.com.au



The missing line number is the only bug here; the rest is an enhancement
request. You have a recursive definition in sum.opAdd(). As soon as you do
anything which forces opAdd to be instantiated, the recursion is detected.

Here's a reduced test case for what you're doing:

struct sum(A) {
    auto blah(int a) { return .sum!(sum)(); }
}

sum!(int) z;

-------
A quick, incomplete patch to improve the error message slightly: Template.c
line 156.
(Doesn't help very much, since it only gives the line number of the template
which is being instantiated, whereas you might want the line which was
instantiating it).
In fact, this particular test case will compile OK if the error message is
removed. (still need to return 1 to fake a match). But that won't work in
general.

    if (t1)
    {
    /* if t1 is an instance of ti, then give error
     * about recursive expansions.
     */
    Dsymbol *s = t1->toDsymbol(sc);
    if (s && s->parent)
    {   TemplateInstance *ti1 = s->parent->isTemplateInstance();
        if (ti1 && ti1->tempdecl == tempdecl)
        {
        for (Scope *sc1 = sc; sc1; sc1 = sc1->enclosing)
        {
            if (sc1->scopesym == ti1)
            {
-            error("recursive template expansion for template argument %s",
t1->toChars());
+            error(s->loc, "recursive template expansion for template argument
%s", t1->toChars());
            return 1;    // fake a match
            }
        }
        }
    }

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 02 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3869


Stewart Gordon <smjg iname.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |smjg iname.com





 The missing line number is the only bug here; the rest is an enhancement
 request. You have a recursive definition in sum.opAdd(). As soon as you do
 anything which forces opAdd to be instantiated, the recursion is detected.


I don't follow you.

a+(b+c)

b+c instantiates base.opAdd!(base)
which instantiates sum!(base, base)
so b+c is of type sum!(base, base)

a+(b+c) instantiates base.opAdd!(sum!(base, base))
which instantiates sum!(base, sum!(base, base))


(a+b)+c

a+b instantiates base.opAdd!(base)
which instantiates sum!(base, base)
so a+b is of type sum!(base, base)

(a+b)+c instantiates sum!(base, base).opAdd!(base)
which instantiates sum!(sum!(base, base), base)

The only real difference is that sum.opAdd is instantiated at all.  Are you
claiming that, because it's a member of sum, instantiating sum within it is
illegal?  How have you reached that conclusion?


 Here's a reduced test case for what you're doing:
 
 struct sum(A) {
     auto blah(int a) { return .sum!(sum)(); }
 }
 
 sum!(int) z;


This is completely different.

sum!(int) instantiates sum!(sum!(int))
which instantiates sum!(sum!(sum!(int)))
and so on

This doesn't, or shouldn't, happen in the OP's testcase, because there's
nothing whatsoever to trigger an instantiation of sum!(sum!(base, base),
base).opAdd.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 02 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3869




PST ---
Don is partly correct:

The problem that I see is that "recursive template instantiation" is
interpreted and prohibited unnecessarily wide, so my "bug report" can actually
be understood as an "enhancement request".

The example code provided by Don is, however, fundamentally different from my
original case:

A function contained in a template is immediately instantiated together with
its containing template, even if it is not called. This leads to an infinite
loop. It could be avoided, but it would mean a significant conceptual change.

In my case, however, the problem was triggered by a template function contained
in a template. This inner template is only instantiated when needed, so it does
not produce an infinite loop. Simply relaxing the safety check in the compiler
should solve the problem.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 03 2010
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3869


Stewart Gordon <smjg iname.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |rejects-valid, spec



Thinking about it now, I think what actually happens is that DMD looks ahead at
the effect of continuing the sequence

sum!(base, base)
sum!(base, sum!(base, base))
sum!(base, sum!(base, sum!(base, base)))

just in case, in order to avoid eating up memory unboundedly and bringing the
system to its knees should this infinite sequence continue.

Trouble is I'm not sure that there's a general way to check in advance whether
the sequence continues, short of solving the halting problem.  But one possible
rule that would cover this case is that, if a template is defined within a
template, then to trigger an infinite recursion error the definition must
instantiate both the outer template and the inner template within this new
instance's scope.

The relevant bit of the spec doesn't forbid what you're doing, so technically
this is rejects-valid.  At the same time, it might be somewhere where the spec
wants looking at.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Mar 04 2010
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=3869


Maksim Zholudev <maximzms gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |maximzms gmail.com



PDT ---
*** Issue 5934 has been marked as a duplicate of this issue. ***

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
May 06 2011