www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Possible to avoid downcasting?

reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
I have a function makeTree() that builds a binary tree of BaseNode:

	class BaseNode {
		BaseNode* left, right;
	}
	BaseNode makeTree() {
		auto node = new BaseNode(...);
		...
		return node;
	}

But I want to have the option of creating the tree with derived class
nodes instead of BaseNode.  One option is to pass a factory function to
makeTree():

	BaseNode makeBaseNode() { return new BaseNode(...); }
	BaseNode makeTree(BaseNode function() makeNode = makeBaseNode) {
		auto node = makeNode();
		...
		return node;
	}

	auto tree1 = makeTree(); // tree of BaseNodes

	class Derived : BaseNode { ... }
	auto tree2 = makeTree(() => new Derived); // tree of Derived nodes

So far so good.  But now I want to iterate over the trees, and I'd like
to be able to use information in the Derived node directly. But since
makeTree() returns BaseNode, the only way I can get at the Derived nodes
is to cast every node to Derived.  Furthermore, casting to Derived does
not change the types of .left and .right, so this cast has to be done
*every time*.

The other way to do this is to templatize:

	typeof(makeNode()) makeTree(Node)(Node function() makeNode)
		if (is(Node : BaseNode))
	{
		auto node = makeNode();
		...
		return node;
	}
	auto tree1 = makeTree!(() => new BaseNode);
	auto tree2 = makeTree!(() => new Derived);

This works, and returns a tree of BaseNode by default, or a tree of
Derived if invoked with makeTree!Derived().  However, it's not an
elegant solution, because it causes template bloat: makeTree is
instantiated every time I want a new node type, even though the function
body essentially doesn't even care what type the node is as long as it
derived from BaseNode.

Is there a template equivalent of inout functions, where you basically
say "the return type depends on the template parameter, but otherwise
the function body is identical, so don't bother creating a new
instantiation, just reuse the same function body"?


T

-- 
Only boring people get bored. -- JM
Dec 24 2019
next sibling parent JN <666total wp.pl> writes:
On Tuesday, 24 December 2019 at 19:52:44 UTC, H. S. Teoh wrote:

 So far so good.  But now I want to iterate over the trees, and 
 I'd like to be able to use information in the Derived node 
 directly.


How about using a visitor pattern to iterate over the nodes? 
That's how I'd solve it in a OOP context.
Dec 24 2019
prev sibling next sibling parent reply Adam D. Ruppe <destructionator gmail.com> writes:
On Tuesday, 24 December 2019 at 19:52:44 UTC, H. S. Teoh wrote:

 But I want to have the option of creating the tree with derived 
 class nodes instead of BaseNode.  One option is to pass a 
 factory function to makeTree():

 	BaseNode makeBaseNode() { return new BaseNode(...); }


You can also, if this is in the class, make it virtual and have 
the child classes return instances of themselves when overriding.


 Is there a template equivalent of inout functions, where you 
 basically say "the return type depends on the template 
 parameter, but otherwise the function body is identical, so 
 don't bother creating a new instantiation, just reuse the same 
 function body"?


But this is easy enough with traditional function techniques:

private void populate(Base b) { /* guts that only need to know 
base; most your makeTree function */ }

public T make(T)() {
    auto t = new T();
    populate(t);
    return t;
}


So now the templated section is reduced to really just the 
constructor call... and realistically the compiler can pretty 
easily inline that as well.

No cast, minimal duplication, easy to use on the outside.

(tbh i think sometimes we get so excited about D's cool features 
that we forget about the simple options we have too!)


speaking of cool features though


void populate(Object o) {
         import std.stdio;
         writeln(o);
}

// the lazy here....
T make(T)(lazy T t) {
         populate(t);
         return t;
}

class Foo {}

void main() {
         // means the new Foo down there is automatically 
lambdaized
         auto tree = make(new Foo);
}


which might be kinda fun.
Dec 24 2019
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, Dec 24, 2019 at 08:15:32PM +0000, Adam D. Ruppe via Digitalmars-d wrote:

 On Tuesday, 24 December 2019 at 19:52:44 UTC, H. S. Teoh wrote:

 But I want to have the option of creating the tree with derived
 class nodes instead of BaseNode.  One option is to pass a factory
 function to makeTree():
 
 	BaseNode makeBaseNode() { return new BaseNode(...); }


 
 You can also, if this is in the class, make it virtual and have the
 child classes return instances of themselves when overriding.


Good point.  But it doesn't solve the problem of the return type being
only the base class.



 Is there a template equivalent of inout functions, where you
 basically say "the return type depends on the template parameter,
 but otherwise the function body is identical, so don't bother
 creating a new instantiation, just reuse the same function body"?


 
 But this is easy enough with traditional function techniques:
 
 private void populate(Base b) { /* guts that only need to know base;
 most your makeTree function */ }
 
 public T make(T)() {
    auto t = new T();
    populate(t);
    return t;
 }
 
 
 So now the templated section is reduced to really just the constructor
 call... and realistically the compiler can pretty easily inline that
 as well.
 
 No cast, minimal duplication, easy to use on the outside.


[...]

That's a nice trick... except for the fatal wrinkle that populate() /
makeTree() needs to be recursive.  Sorry, I left out this
all-too-important detail.  Basically, it recursively builds the tree:

	class Base {
		Base* left, right;
	}
	class Derived : Base {}
	Base makeTree(...) {
		auto root = new Base;
		if (someCondition) {
			root.left = makeTree(...);
			root.right = makeTree(...);
		}
		return root;
	}

I can replace the 'new Base' call with a function/delegate that creates
Derived nodes instead, but how to fix the return type of makeTree
without templating the entire function?


T

-- 
It said to install Windows 2000 or better, so I installed Linux instead.
Dec 24 2019
prev sibling parent reply Steven Schveighoffer <schveiguy gmail.com> writes:
On 12/24/19 3:15 PM, Adam D. Ruppe wrote:

 // the lazy here....
 T make(T)(lazy T t) {
          populate(t);
          return t;
 }
 
 class Foo {}
 
 void main() {
          // means the new Foo down there is automatically lambdaized
          auto tree = make(new Foo);
 }


I see a bug ;)

-Steve
Dec 26 2019
parent Adam D. Ruppe <destructionator gmail.com> writes:
On Thursday, 26 December 2019 at 17:11:24 UTC, Steven 
Schveighoffer wrote:

 I see a bug ;)


oops indeed. but still
Dec 26 2019
prev sibling parent Steven Schveighoffer <schveiguy gmail.com> writes:
On 12/24/19 2:52 PM, H. S. Teoh wrote:

 I have a function makeTree() that builds a binary tree of BaseNode:
 
 	class BaseNode {
 		BaseNode* left, right;
 	}
 	BaseNode makeTree() {
 		auto node = new BaseNode(...);
 		...
 		return node;
 	}
 
 But I want to have the option of creating the tree with derived class
 nodes instead of BaseNode.  One option is to pass a factory function to
 makeTree():
 
 	BaseNode makeBaseNode() { return new BaseNode(...); }
 	BaseNode makeTree(BaseNode function() makeNode = makeBaseNode) {
 		auto node = makeNode();
 		...
 		return node;
 	}
 
 	auto tree1 = makeTree(); // tree of BaseNodes
 
 	class Derived : BaseNode { ... }
 	auto tree2 = makeTree(() => new Derived); // tree of Derived nodes
 
 So far so good.  But now I want to iterate over the trees, and I'd like
 to be able to use information in the Derived node directly. But since
 makeTree() returns BaseNode, the only way I can get at the Derived nodes
 is to cast every node to Derived.  Furthermore, casting to Derived does
 not change the types of .left and .right, so this cast has to be done
 *every time*.


If you *know* all the types are the same, you can use reinterpret 
casting instead of downcasting, which basically will avoid the runtime 
checks.

e.g.:

auto realNode = cast(Derived)(cast(void*)node);

Now, aside from that, D does support covariance on virtual functions. 
Which can make things more pleasant

So...

class BaseNode
{
    BaseNode _left;
    BaseNode _right;
    BaseNode left() { return _left; }
    BaseNode right() { return _right; }
}

class Derived : BaseNode
{
    override Derived left() { return cast(Derived)cast(void*)_left; }
    override Derived right() { return cast(Derived)cast(void*)_right; }
}

Now, if you know you have a Derived, the left and right properties turn 
into Derived as well.

-Steve
Dec 26 2019