std.mem.copy does not work if slices overlap

[andrewrk]

Zig's current implementation of std.mem.copy is this:

/// Copy all of source into dest at position 0.
/// dest.len must be >= source.len.
/// The memory areas must not overlap.
pub fn copy(comptime T: type, dest: []T, source: []const T) {
    for (source) |s, i| dest[i] = s;
}

"The memory areas must not overlap" is a pretty lame restriction, especially since the single branch it takes to make it work either way is a low cost. So this could be:

/// Copy all of source into dest at position 0.
/// dest.len must be >= source.len.
pub fn copy(comptime T: type, dest: []T, source: []const T) {
    if (usize(dest.ptr) < usize(source.ptr) or
        usize(source.ptr) + source.len <= usize(dest.ptr))
    {
        for (source) |s, i| dest[i] = s;
    } else {
        for (source) |s, i| dest[source.len - i] = source[source.len - i];
    }
}

If we want to have another function, copyAssumeNoOverlap with this branch optimized away, that's fine. We'd still need to add that assert though:

/// Copy all of source into dest at position 0.
/// dest.len must be >= source.len.
/// The memory areas must not overlap.
pub fn copyAssumeNoOverlap(comptime T: type, dest: []T, source: []const T) {
    assert(usize(dest.ptr) < usize(source.ptr) or usize(source.ptr) + source.len <= usize(dest.ptr));
    for (source) |s, i| dest[i] = s;
}

Now here's the problem:

• usize(slice.ptr) does not work at compile time
• std.mem.copy should work at compile time

At compile time we still have this concept of overlapping memory, but the way we want to check for overlapping memory doesn't work.

[raulgrell]

The implementation you provided above has a couple of bugs that hadn't surfaced due to my limited testing - it's based off the snippet I sent in IRC, right?

This is what I have for now:

pub fn copy(comptime T: type, dest: []T, source: []const T) -> []T {
    @setDebugSafety(this, false);
    assert(dest.len >= source.len);
    for (source) |s, i| dest[i] = s;
    return dest;
}

pub fn move(comptime T: type, dest: []T, src: []const T) -> []T {
    assert(dest.len >= source.len);
    // Same address
    if (dest.ptr == src.ptr) return dest;
    
    // No overlap
    if (usize(src.ptr) + (src.len * @sizeOf(T)) <= usize(dest.ptr)
            or usize(dest.ptr) + (dest.len * @sizeOf(T)) <= usize(src.ptr)) {
        // Safe to @memcopy, mem.copy or whatever
        return copy(T, dest, src);
    }

    // Overlapping buffers, determine direction
    if (usize(dest.ptr) < usize(src.ptr)) {
        for (src) |s, i| dest[i] = s;
    } else {
        for (src) |s, i| dest[src.len - i - 1] = src[src.len - i - 1]; 
    }
    return dest;
}

[kyle-github]

The C standard (or is it POSIX?) specifications note that it is forbidden for the ranges to overlap in memcpy and they can in memmove. This is highly annoying so I am happy to see that Zig is attempting to do this right.

[andrewrk]

I think this may actually be solved by #476 - add noalias for slices. Then the compiler does the assertion, and the code works at compile-time.

[shawnl]

The root problem is described in #5553. This is just a symptom.

[andrewrk]

This was solved by #14040. The new semantics of @memcpy assert the slices do not overlap, and it works at compile-time. Meanwhile, std.mem.copy is renamed to std.mem.copyForwards and is defined to do exactly that, with no other restrictions.