Weird behaviour with struct constructors

Question

I've written a basic Node struct in D, designed to be used as a part of a tree-like structure. The code is as follows:

import std.algorithm: min;

alias Number = size_t;

struct Node {
    private {
        Node* left, right, parent;
        Number val;
    }

    this(Number n) {val = n;}

    this(ref Node u, ref Node v) {
       this.left = &u;
       this.right = &v;
       val = min(u.val, v.val);
       u.parent = &this;
       v.parent = &this;
    }

}

Now, I wrote a simple function which is supposed to give me a Node (meaning a whole tree) with the argument array providing the leaves, as follows.

alias Number = size_t;

Node make_tree (Number[] nums) {
    if (nums.length == 1) {
         return Node(nums[0]);
    } else {
        Number half = nums.length/2;
        return Node(make_tree(nums[0..half]), make_tree(nums[half..$]));
    }
}

Now, when I try to run it through dmd, I get the following error message:

Error: constructor Node.this (ulong n) is not callable using argument types (Node, Node)

This makes no sense to me - why is it trying to call a one-argument constructor when given two arguments?

Answer 1

The problem has nothing to do with constructors. It has to do with passing by ref. The constructor that you're trying to use

this(ref Node u, ref Node v) {...}

accepts its arguments by ref. That means that they must be lvalues (i.e. something that can be on the left-hand side of an assignment). But you're passing it the result of a function call which does not return by ref (so, it's returning a temporary, which is an rvalue - something that can go on the right-hand side of an assignment but not the left). So, what you're trying to do is illegal. Now, the error message isn't great, since it's giving an error with regards to the first constructor rather than the second, but regardless, you don't have a constructor which matches what you're trying to do. At the moment, I can think of 3 options:

1. Get rid of the ref on the constructor's parameters. If you're only going to be passing it the result of a function call like you're doing now, having it accept ref doesn't help you anyway. The returned value will be moved into the function's parameter, so no copy will take place, and ref isn't buying you anything. Certainly, assigning the return values to local variables so that you can pass them to the constructor as it's currently written would lose you something, since then you'd be making unnecessary copies.

2. Overload the constructor so that it accepts either ref or non-ref. e.g.

   void foo(ref Bar b) { ... }
   void foo(Bar b) { foo(b); } //this calls the other foo
   

   In general, this works reasonably well when you have one parameter, but it would be a bit annoying here, because you end up with an exponential explosion of function signatures as you add parameters. So, for your constructor, you'd end up with

   this(ref Node u, ref Node v) {...}
   this(ref Node u, Node v) { this(u, v); }
   this(Node u, ref Node v) { this(u, v); }
   this(Node u, Node v) { this(u, v); }
   

   And if you added a 3rd parameter, you'd end up with eight overloads. So, it really doesn't scale beyond a single parameter.

3. Templatize the constructor and use auto ref. This essentially does what #2 does, but you only have to write the function once:

   this()(auto ref Node u, auto ref Node v) {...}
   

   This will then generate a copy of the function to match the arguments given (up to 4 different versions of it with the full function body in each rather than 3 of them just forwarding to the 4th one), but you only had to write it once. And in this particular case, it's probably reasonable to templatize the function, since you're dealing with a struct. If Node were a class though, it might not make sense, since templated functions can't be virtual.

So, if you really want to be able to pass by ref, then in this particular case, you should probably go with #3 and templatize the constructor and use auto ref. However, personally, I wouldn't bother. I'd just go with #1. Your usage pattern here wouldn't get anything from auto ref, since you're always passing it two rvalues, and your Node struct isn't exactly huge anyway, so while you obviously wouldn't want to copy it if you don't need to, copying an lvalue to pass it to the constructor probably wouldn't matter much unless you were doing it a lot. But again, you're only going to end up with a copy if you pass it an lvalue, since an rvalue can be moved rather than copied, and you're only passing it rvalues right now (at least with the code shown here). So, unless you're doing something different with that constructor which would involve passing it lvalues, there's no point in worrying about lvalues - or about the Nodes being copied when they're returned from a function and passed into the constructor (since that's a move, not a copy). As such, just removing the refs would be the best choice.