New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

well defined copy eliding semantics #287

Open
thejoshwolfe opened this Issue Mar 28, 2017 · 21 comments

Comments

Projects
None yet
5 participants
@thejoshwolfe
Member

thejoshwolfe commented Mar 28, 2017

Accepted Proposal


Old Proposal:

Have well-defined rules for copy eliding, and we sometimes allow what looks like copying non-copyable objects.

  • During the semantic analysis of every expression, there is an additional field of provided context, which is the location to put the expression's result value.
  • A function can declare a non-copyable return type. In this case, the function gets an additional, secret parameter that is a writable pointer to where it should write its return value.
  • Here's how specific language constructs handle the result location:
    • A var or const declaration creates a location, and passes that location to the initializer expression, if any.
    • An assignment statement uses the address of the left hand side as the result location for the right hand side.
    • A function call or an operator that acts like a function (e.g. +, ~) creates a temporary storage location for each of its parameters/operands and provides that temporary storage as the result location when evaluating each parameter/operand expression.
    • The body of a function whose return type is copyable uses a special result location, such as a platform-specific register.
    • The body of a function whose return type is non-copyable uses the secret result location pointer parameter as the result location.
    • A return statement provides the function body's result location to the return expression.
    • For a function call where the function's return type is non-copyable, the function call expression's result location is passed as the function's secret return value pointer parameter.
    • For a function call where the function's return type is copyable, the result of the function is copied from where the function puts it (such as a platform-specific register) to the function call expression's result location.
    • A block or branching control structure forwards its result location to whatever sub-expression determines its result value.
    • A statement followed by a ; in a block gets a void result location.
    • A defer statement provides a void result location to its expression.
    • A struct, array, or enum initialization expression uses its result location in-place.
    • Automatic error and maybe coercion happen in-place.

Examples:

fn foo() -> u32 { // result location for function body is a special register
    bar(); // function call gets a void result location, so bar() must not return anything (see #219).
    var // varaible declaration gets a void result location.
        a : u32 // creates location for a u32
        = 1; // integer literal gets &a as result location
    const b // creates a location for a TBD type
        = baz(); // baz() gets &b as result location, and baz() determines the type of b
    a = ( // result location is &a
            b // result location is a temporary location of a TBD type provided by the + operator
        + // checks left and right types and produces the sum into &a, possibly doing automatic type coorsion first
            baz() // result location is a temporary location of a TBD type provided by the + operator
    );
    var array // creates a location for a TBD type
        = []u32 { // result location is &array, and now type of array is [TBD]u32.
            1, // result location is &array[0], and array.len is at least 1
            5, // result location is &array[1], and array.len is at least 2
        };
    1 // result location is the special register for the function body
}

struct BigStruct {
    a: [2]SubStruct,
    pub fn init(offset: u32) -> BigStruct { // result location is the secret parameter; let's call it result_location
        BigStruct { // result location is still result_location
            .a = []SubStruct { // result location is &result_location.a
                SubStruct { // result location is &result_location.a[0]
                    .x = offset + 0, // result location is &result_location.a[0].x
                    // (note elaboration on the + operator is omitted here. see above.)
                },
                SubStruct { // result location is &result_location.a[1]
                    .x = offset + 1, // result location is &result_location.a[1].x
                },
            },
        }
    }
}
struct SubStruct {
    x: u32,
}
fn main() {
    var a // creates a location for a TBD type
        = BigStruct.init(10); // result location secret parameter is &a
    // equivalent to:
    var b : BigStruct = undefined;
    b.a[0].x = 10 + 0;
    b.a[1].x = 10 + 1;

    var c // creates a location for a TBD type
        = if // result location is &c
        (
            something() // result location is a temporary location created by the if
        ) {
            BigStruct.init(100) // result location is &c
        } else {
            BigStruct.init(200) // result location is &c
        };
    // equivalent to:
    var d : BigStruct = undefined;
    if (something()) {
        d.a[0].x = 100 + 0;
        d.a[1].x = 100 + 1;
    } else {
        d.a[0].x = 200 + 0;
        d.a[1].x = 200 + 1;
    }

    var e // creates a location for a TBD type
        = if (something()) {
            a // ERROR: can't copy type BigStruct
        } else {
            b // ERROR: can't copy type BigStruct
        };
}

Relative to what #83 originally proposed, we've got relaxed restrictions on returning non-copyable types from a function. Previously returning non-copyable types required use of a named return value. So do we still need named return values?

Here's a usecase for named return values:

struct PluginRegistry {
    id_to_plugin: Hashtable(Id, &Plugin), // non-copyable
    pub fn init() -> (result: PluginRegistry) {
        result.id_to_plugin = Hashtable(Id, &Plugin).init();
        result.register(base_plugin.id, &base_plugin);
    }
    pub fn register(self: &PluginRegistry, id: Id, plugin: &Plugin) {
        self.id_to_plugin.put(id, plugin);
        plugin.on_register();
    }
}

We want to design PluginRegistry to use the constructor-like pattern where you can assign from init(), and we want to do something non-trivial with the object before we return it. In order to refer to the object, it has to be named; we wouldn't be able to call register() if we did a return PluginRegistry { ... } expression.

@thejoshwolfe

This comment has been minimized.

Member

thejoshwolfe commented Mar 28, 2017

Let me elaborate on a specific usecase:

fn foo() -> BigStruct {
    const a = BigStruct { ... }; // fine so far
    return a; // ERROR: cannot copy type BigStruct
}

The reason for this error is that at the time when you declared a, it created its own location as a local variable (or const, w/e). If the compiler were clever enough to look ahead and notice you were returning a, it could have used the secret result location pointer parameter as the storage location for a. Then the return would not be a copy, and it would work.

I'm hesitant to suggest that this rule be well-defined, because it's a bit more demanding of the compiler, and the rules for what is allowed and what's not allowed get more complicated as well. For example:

fn foo() -> BigStruct {
    const a = BigStruct { ... };
    if (something()) return a; // ERROR
    const b = BigStruct { ... };
    if (something()) return a; // ERROR
    if (something()) return b; // ERROR: but really if this were deleted, then all the errors go away.
    return a; // ERROR
}

However, one argument in favor of this idea is #286, which wants to refer to the return value of a block by name. Among the proposals in that issue, there is a simpler proposal, which is the one in this comment.

fn main() {
    const a : BigStruct = {
        const result = BigStruct{ ... };
        result.method();
        result // here's the "copy" that could be elided if the compiler notices
               // that this block only returns that local variable.
    };
}
@BarabasGitHub

This comment has been minimized.

Contributor

BarabasGitHub commented Jul 19, 2018

A function can declare a non-copyable return type. In this case, the function gets an additional, secret parameter that is a writable pointer to where it should write its return value.

Why not just be explicit about it and let the user provide a pointer to the function? Then everyone can clearly see it doesn't get copied and nobody has to wonder why you can 'copy' this non-copyable struct.

@thejoshwolfe

This comment has been minimized.

Member

thejoshwolfe commented Jul 19, 2018

That would require that the user declare the variable on a separate line and initialize it to undefined, and then the function signature doesn't really indicate that it's an output only parameter, and the function implementation could read from the pointer without getting a compile error.

That all definitely works ok, and it's what you do in C, but it seems more elegant to make the function look like it's returning the thing. However, I agree that the copy-or-not semantics are a little confusing when they're completely implicit, especially when the return type is generic. Then a single function can do and not do the secret pointer thing depending on the type parameters.

It is desirable that we only have one obvious way to return things from functions. But if under the hood there are actually multiple ways, we need to be careful that surprises don't break anything. For example, we need to be careful that this doesn't cause any aliasing footguns.

@andrewrk

This comment has been minimized.

Member

andrewrk commented Aug 31, 2018

Something like this is still planned, but this proposal is old enough now that it needs revisiting and reworking before it's ready to be implemented.

@ghost

This comment has been minimized.

ghost commented Aug 31, 2018

I don't believe named return types need/ should be part of this proposal because cpp has guaranteed copy elision as well and does not have named return types so it seems to be unnecessary.

It seems though as if cpp has cases where its not guaranteed (even cpp 17) so it might be worth investigating this before making a final judgement. My cpp is currently not good enough to easily judge the current state of copy elision in cpp.

@andrewrk

This comment has been minimized.

Member

andrewrk commented Oct 2, 2018

Here is my new proposal for guaranteed copy elision:

const Foo = struct {
    x: i32,
    ptr: *i32,

    fn init(z: i32) !Foo { // same function signature syntax
        try somethingThatCanFail(); // try still works
        @result() = Foo{ // new builtin function which is a reference to the return value
            .x = 1234,
            .ptr = undefined,
        };
        if (z == 0) return error.Bad;
        if (z == 1) {
            // this still works, but doesn't have guaranteed
            // copy elision semantics.
            return Foo { .x = 0, .ptr = undefined};
        }
        // in case of error inference, @result() refers to the bare value
        @result().ptr = &foo.x;
        return @result(); // returning @result() is guaranteed not to copy any memory
    }

    const Error = error{Bad};

    fn init2(z: i32) Error!Foo {
        @result() = Foo{
            .x = 1234,
            .ptr = undefined,
        };
        // since the result type is fully specified, we need to unwap to get the bare value
        const res = &(@result() catch unreachable);
        res.ptr = &foo.x;
        return @result();
    }
}

// works at global scope too
const foo = Foo.init(2);
test "pointer value correct" {
    assert(foo.ptr == &foo.x);
}

The followup proposal would be something like #591 (comment) where a field could be fixed, and not doing this @result() thing to avoid copying would give a compile error.

@winksaville

This comment has been minimized.

Contributor

winksaville commented Oct 2, 2018

What happens here:

if (z == 3) {
  var foo: Foo = undefined;
  foo.x = 456;
  foo.ptr = &foo.x;
  return foo;

I think this should generate a compiler error?

@winksaville

This comment has been minimized.

Contributor

winksaville commented Oct 2, 2018

(Note in the above I "fixed" the foo.ptr assignment).

Also, Is there a simple syntax to something like:

fn init3(v: i32) Foo {
    return @result() = Foo{
        .x = v,
        .ptr = &@result().x,
    }
}

(Sorry for the editing :( )

@winksaville

This comment has been minimized.

Contributor

winksaville commented Oct 2, 2018

I've edited both comments above, please view the comments; 1, 2 directly.

Sorry

@BarabasGitHub

This comment has been minimized.

Contributor

BarabasGitHub commented Oct 2, 2018

I never got the whole copy-elision hype. What is the advantage over fn init(z: i32, result: * !Foo) void or maybe fn init(z: i32, result: * Foo) !void ?

@ghost

This comment has been minimized.

ghost commented Oct 2, 2018

I'd want to see reason why it's necessary to add new syntax at all cause I'd still like to make the point that even cpp does not have such syntax (neither named return value, nor @return like thing).

@andrewrk

This comment has been minimized.

Member

andrewrk commented Oct 2, 2018

@BarabasGitHub It's semantically necessary if your struct fields have references to other struct fields. Your first example introduces new syntax; we don't currently have the concept of inferred error sets for parameter values. Your second example looks like this at the callsite (if we swap the param orders):

var result: Foo = undefined;
try result.init(123);

This is the null hypothesis to this proposal. It's not so bad.

One big downside is that if you have a struct that you've been returning something directly, and it's used in lots of places, and then you need to add a field that requires these semantics, you either have to heap allocate it, or change everything to accept a pointer parameter. It's infectious. For example, back when we had LockFreeQueue, it required a field to point to another one. And if you used it in any other struct, it forced you to heap allocate it or make the struct that you used it in init() with a pointer parameter.

@Hejsil

This comment has been minimized.

Member

Hejsil commented Oct 2, 2018

@BarabasGitHub I can come up with a few on the top of my head:

  • Keeping variables const when possible. If you only ever initialize a value, and after this, it is read-only, then having to do var a: T = undefined; a.init() hides the intent that a is const.
  • Results should be returned, and not passed in. Again, an "out" parameter hides intent, and make code harder to read.
@Hejsil

This comment has been minimized.

Member

Hejsil commented Oct 2, 2018

Also @andrewrk, does this apply to labeled blocks as well?

const a = blk: {
    @result() = Foo{
        .x = v,
        .ptr = &@result().x,
    };
    break :blk @result(); 
}
@andrewrk

This comment has been minimized.

Member

andrewrk commented Oct 2, 2018

That's a good question. I didn't consider it. I need to rework the proposal taking that into account.

@thejoshwolfe

This comment has been minimized.

Member

thejoshwolfe commented Oct 2, 2018

@BarabasGitHub

A parameter is input only, a return value is output only, and a parameter that is a pointer points to something that can be input or output or both. A pointer to const is input only, but a pointer to mutable memory doesn't encode the direction of data flow.

C# and other languages have the concept of an out parameter, which is effectively a named return value that you call with pass by reference semantics. This clearly communicates to the caller and the function implementor what must happen with the parameter.

  • It is an error if the function doesn't assign to the parameter on every code path through the function.
  • It is an error if the function tries to read from the parameter.
  • The caller can pass in an uninitialized variable and be guaranteed that the variable will be initialized once the function returns.

All of these guarantees are already in place for return values, although you might not think about them in these terms.

With the right compiler flags, you can dig up the old behavior of C where you don't have to return a value in all paths through a function. The result is that sometimes your return value is undefined. It's good that the compiler makes this an error. When passing an explicit pointer parameter that is intended to hold a return value, the compiler doesn't guarantee you initialize it on every code path.

@BarabasGitHub

This comment has been minimized.

Contributor

BarabasGitHub commented Oct 2, 2018

Alright, those are definitely good arguments. But then I wonder how to nicely handle multiple return values. That's something that annoys me in C and C++. Usually you end up with a struct, but that means you have to unpack it at the call site and thus make copies. (maybe that's something to discuss here though)

@andrewrk

This comment has been minimized.

Member

andrewrk commented Oct 2, 2018

That's a great point. Since tuples (#208) is one of the issues I want to solve in 0.4.0, I need to take those into account in this proposal as well. (Tuples is how multiple return values would work.)

@ghost

This comment has been minimized.

ghost commented Oct 2, 2018

That's something that annoys me in C and C++. Usually you end up with a struct

not so anymore https://skebanga.github.io/structured-bindings/

@BarabasGitHub

This comment has been minimized.

Contributor

BarabasGitHub commented Oct 2, 2018

Great. I'm glad there will have tuples in the language and that there's an idea for multiple return values.

andrewrk added a commit that referenced this issue Oct 9, 2018

@andrewrk

This comment has been minimized.

Member

andrewrk commented Nov 21, 2018

OK I'm back with an updated proposal. I'm confident about this one. So confident, in fact, that I'm going to accept it as the null hypothesis. Everyone is of course welcome to provide alternative proposals or point out flaws in this one that mean it should not be accepted.

Copy Elision Part 1, a prerequisite, is well underway in #1682. This proposal is for for Part 2 where we make it possible for functions to return large structs with no copying, guaranteed, and more importantly, to use the return value before returning it, e.g. calling a method on it.

I started typing up this complicated proposal and then changed my mind at the end, and here's where I've arrived, somewhere very close to what @thejoshwolfe originally proposed.

  • Zig will detect when all control flow paths end with return foo;, where foo is the same in all the return expressions, and is declared in a way that allows it to reference the return value. In this case the variable declaration will reference the return value rather than be a stack allocation. The detection doesn't have to be very advanced, just good enough that it's easy to get the detection to happen when you are trying to.
  • Introduce the ability to mark structs/unions as "nocopy", or perhaps even at a field level, where you can mark individual fields as "fixed" which means that they cannot be moved to a new address in memory, once initialized.
  • If a struct/union is "nocopy" and would get copied, it's a compile error. This makes up for lack of sophistication in the result value detection. The compile error would point to the part in the code where a copy happens, and you could then adjust the logic to avoid it. Note that LLVM optimizations do much more advanced copy elision detection; this proposal is discussing only what Zig has to do to guarantee no-copy semantics in certain situations.
  • This solves the question about blocks. They work the same way.
  • Tuples: No tuples. See the comment I'm about to post on that issue. (#208)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment