www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Overzealous recursive template expansion protection?

reply Gareth Charnock <gareth.charnock gmail.com> writes:
I've been trying to correctly implement the interpreter 
patten/expression templates in D (for reference this is a summary of the 
C++ interpreter patten can be found here 
http://www.drdobbs.com/184401627). I've run into a problem and I'm not 
sure if it's a compiler bug or not. The testcase is:

struct BinaryOp(L,string op,R) {
	pragma(msg,"Instansiating " ~ typeof(this).stringof);
	BinaryOp!(typeof(this),s,R1) opBinary(string s,R1)(R1 r) {
		pragma(msg,"Instansiating BinaryOp.opBinary ~L.stringof ~ op ~ 
R1.stringof);
		return typeof(return)();
	}
}

struct Leaf {
	BinaryOp!(typeof(this),s,R) opBinary(string s,R)(R r) {
		pragma(msg,"Instansiating leaf.opBinary(" ~ R.stringof ~ ")");
		return typeof(return)();
	}
};

void main() {
	Leaf v1,v2,v3;
	pragma(msg,"");
	pragma(msg,"======= This Compiles ======");
	v1*(v2*v3);
	pragma(msg,"");
	pragma(msg,"======= This Doesn't ======");
  	(v1*v2)*v3;
}
Output:
======= This Compiles ======
Instansiating BinaryOp!(Leaf,s,Leaf)
Instansiating leaf.opBinary(Leaf)
Instansiating BinaryOp!(Leaf,s,BinaryOp!(Leaf,s,Leaf))
Instansiating leaf.opBinary(BinaryOp!(Leaf,s,Leaf))

======= This Doesn't ======
Error: recursive template expansion for template argument 
BinaryOp!(Leaf,s,Leaf)

I've tracked the problem down to the return type of BinaryOp.opBinary. 
Clearly putting BinaryOp!(typeof(this),...) would be a Bad Thing in the 
main template body but opBinary is a template that may or may not be 
instantiated so it shouldn't automatically lead to runaway 
instantiation. It seems the compiler is a little bit overzealous in 
making sure that such runaway instantiations do not happen.

Is this a bug? Should I file it? Here's what I think a minimal test case 
might look like:

struct A(T1) {
	void templateFunc(T2)(T2 a) {
		 alias A!(typeof(this)) error;
	}
}


void main() {
	 A!int a;
	 a.templateFunc!int(0);
}
Nov 02 2010
parent reply "Robert Jacques" <sandford jhu.edu> writes:
On Tue, 02 Nov 2010 22:03:47 -0400, Gareth Charnock  
<gareth.charnock gmail.com> wrote:

 I've been trying to correctly implement the interpreter  
 patten/expression templates in D (for reference this is a summary of the  
 C++ interpreter patten can be found here  
 http://www.drdobbs.com/184401627). I've run into a problem and I'm not  
 sure if it's a compiler bug or not. The testcase is:

 struct BinaryOp(L,string op,R) {
 	pragma(msg,"Instansiating " ~ typeof(this).stringof);
 	BinaryOp!(typeof(this),s,R1) opBinary(string s,R1)(R1 r) {
 		pragma(msg,"Instansiating BinaryOp.opBinary ~L.stringof ~ op ~  
 R1.stringof);
 		return typeof(return)();
 	}
 }

 struct Leaf {
 	BinaryOp!(typeof(this),s,R) opBinary(string s,R)(R r) {
 		pragma(msg,"Instansiating leaf.opBinary(" ~ R.stringof ~ ")");
 		return typeof(return)();
 	}
 };

 void main() {
 	Leaf v1,v2,v3;
 	pragma(msg,"");
 	pragma(msg,"======= This Compiles ======");
 	v1*(v2*v3);
 	pragma(msg,"");
 	pragma(msg,"======= This Doesn't ======");
   	(v1*v2)*v3;
 }
 Output:
 ======= This Compiles ======
 Instansiating BinaryOp!(Leaf,s,Leaf)
 Instansiating leaf.opBinary(Leaf)
 Instansiating BinaryOp!(Leaf,s,BinaryOp!(Leaf,s,Leaf))
 Instansiating leaf.opBinary(BinaryOp!(Leaf,s,Leaf))

 ======= This Doesn't ======
 Error: recursive template expansion for template argument  
 BinaryOp!(Leaf,s,Leaf)

 I've tracked the problem down to the return type of BinaryOp.opBinary.  
 Clearly putting BinaryOp!(typeof(this),...) would be a Bad Thing in the  
 main template body but opBinary is a template that may or may not be  
 instantiated so it shouldn't automatically lead to runaway  
 instantiation. It seems the compiler is a little bit overzealous in  
 making sure that such runaway instantiations do not happen.

 Is this a bug? Should I file it? Here's what I think a minimal test case  
 might look like:

 struct A(T1) {
 	void templateFunc(T2)(T2 a) {
 		 alias A!(typeof(this)) error;
 	}
 }


 void main() {
 	 A!int a;
 	 a.templateFunc!int(0);
 }


I'm going to lean on the side of this being a compiler bug (so please  
file), as there are multiple workarounds without logically changing  
anythings

Here's one:

struct BinaryOp(alias L,string op, R) {
	pragma(msg,"Instansiating ", typeof(this).stringof);
	BinaryOp!(BinaryOp,s~"",R1) opBinary(string s, R1)(R1 r) {
		pragma(msg,"Instansiating BinaryOp.opBinary", L.stringof, " ", op,"  
",R1.stringof);
		return typeof(return)();
	}
}

struct Leaf {
	BinaryOp!(Leaf,s~"",R) opBinary(string s,R)(R r) {
		pragma(msg,"Instansiating leaf.opBinary(", R.stringof,  ")");
		return typeof(return)();
	}
};

And here's another

struct BinaryOp(L,string op, R) {
	pragma(msg,"Instansiating ", typeof(this).stringof);
	BinaryOp!(BinaryOp,s,R1) opBinary(string s, R1)(R1 r) {
		pragma(msg,"Instansiating BinaryOp.opBinary", L.stringof, " ", op,"  
",R1.stringof);
		return typeof(return)();
	}
}

struct Leaf {
	BinaryOp!(Leaf,s~"",R) opBinary(string s,R)(R r) {
		pragma(msg,"Instansiating leaf.opBinary(", R.stringof,  ")");
		return typeof(return)();
	}
};

In general, when passing template value parameters to another template,  
I'd recommend performing a no-op on them (i.e. ~"" or +0), since sometimes  
they're passed as N or op instead of 10 or "+". Also, your can use the  
template name inside it to refer to that instance's type (i.e. you don't  
have to use typeof(this)).
Nov 02 2010
parent Gareth Charnock <gareth.charnock gmail.com> writes:
On 03/11/10 03:21, Robert Jacques wrote:

 struct BinaryOp(L,string op,R) {
      pragma(msg,"Instansiating " ~ typeof(this).stringof);
      BinaryOp!(typeof(this),s,R1) opBinary(string s,R1)(R1 r) {
          pragma(msg,"Instansiating BinaryOp.opBinary ~L.stringof ~ op ~
 R1.stringof);
          return typeof(return)();
      }
 }

 struct Leaf {
      BinaryOp!(typeof(this),s,R) opBinary(string s,R)(R r) {
          pragma(msg,"Instansiating leaf.opBinary(" ~ R.stringof ~ ")");
          return typeof(return)();
      }
 };

 void main() {
      Leaf v1,v2,v3;
      pragma(msg,"");
      pragma(msg,"======= This Compiles ======");
      v1*(v2*v3);
      pragma(msg,"");
      pragma(msg,"======= This Doesn't ======");
        (v1*v2)*v3;
 }
 Output:
 ======= This Compiles ======
 Instansiating BinaryOp!(Leaf,s,Leaf)
 Instansiating leaf.opBinary(Leaf)
 Instansiating BinaryOp!(Leaf,s,BinaryOp!(Leaf,s,Leaf))
 Instansiating leaf.opBinary(BinaryOp!(Leaf,s,Leaf))

 ======= This Doesn't ======
 Error: recursive template expansion for template argument
 BinaryOp!(Leaf,s,Leaf)


Thanks, the workaround seems to work. I've reported the bug:

http://d.puremagic.com/issues/show_bug.cgi?id=5160
Nov 03 2010