V: Bug in recursive merging of arrays (or similar)

[elimisteve]

$ v doctor
OS: linux, Debian GNU/Linux 9 (stretch)
Processor: 2 cpus, 64bit, little endian, Intel(R) Core(TM) i7-7820HQ CPU @ 2.90GHz
CC version: cc (Debian 6.3.0-18+deb9u1) 6.3.0 20170516
--------------------------------------------------------------------------------------------------------------------------------------------------------------
vroot: /home/user/django_projects/v
vexe: /home/user/django_projects/v/v
vexe mtime: 2020-09-22 11:52:50
is vroot writable: true
V full version: V 0.1.29 624f22e.89b460b
--------------------------------------------------------------------------------------------------------------------------------------------------------------
Git version: git version 2.11.0
Git vroot status: 0.1.21-4984-g89b460b8
.git/config present: true
/var/tmp/tcc status: master 5e73982e
thirdparty/tcc: N/A
--------------------------------------------------------------------------------------------------------------------------------------------------------------

What did you do?

$ v run 01_05_MergeSort-vbug.v 3 4 2 1

where 01_05_MergeSort-vbug.v contains

import os

fn main() {
    ints := os.args[1..].map(it.int())
    println(not_merge_sort(ints))
}

fn not_merge_sort(nums []int) []int {
    if nums.len <= 1 {
        return nums
    }
    half := nums.len / 2
    left := nums[..half]
    right := nums[half..]
    mut sorted := not_merge_sort(left)
    sorted << not_merge_sort(right)
    return sorted
}

What did you expect to see?

[3, 4, 2, 1]

What did you see instead?

$ v run 01_05_MergeSort-vbug.v 3 4 2 1
*** Error in `/home/user/django_projects/algorithms/01_05_MergeSort-vbug': realloc(): invalid pointer: 0x0000654ab452b6d8 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x70bfb)[0x78a0f1c36bfb]
/lib/x86_64-linux-gnu/libc.so.6(+0x76fc6)[0x78a0f1c3cfc6]
/lib/x86_64-linux-gnu/libc.so.6(realloc+0x219)[0x78a0f1c417d9]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0xdc12)[0x654ab2e38c12]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0xbf6a)[0x654ab2e36f6a]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0xccd1)[0x654ab2e37cd1]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0x1e1c3)[0x654ab2e491c3]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0x1e1a9)[0x654ab2e491a9]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0x1e0a8)[0x654ab2e490a8]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0x23f6a)[0x654ab2e4ef6a]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf1)[0x78a0f1be62e1]
/home/user/django_projects/algorithms/01_05_MergeSort-vbug(+0x1a6a)[0x654ab2e2ca6a]
======= Memory map: ========
654ab2e2b000-654ab2e58000 r-xp 00000000 ca:10 1494066                    /home/user/django_projects/algorithms/01_05_MergeSort-vbug
654ab3057000-654ab3058000 r--p 0002c000 ca:10 1494066                    /home/user/django_projects/algorithms/01_05_MergeSort-vbug
654ab3058000-654ab3059000 rw-p 0002d000 ca:10 1494066                    /home/user/django_projects/algorithms/01_05_MergeSort-vbug
654ab4527000-654ab4548000 rw-p 00000000 00:00 0                          [heap]
78a0f19af000-78a0f19c5000 r-xp 00000000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
78a0f19c5000-78a0f1bc4000 ---p 00016000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
78a0f1bc4000-78a0f1bc5000 r--p 00015000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
78a0f1bc5000-78a0f1bc6000 rw-p 00016000 ca:03 261684                     /lib/x86_64-linux-gnu/libgcc_s.so.1
78a0f1bc6000-78a0f1d5b000 r-xp 00000000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
78a0f1d5b000-78a0f1f5b000 ---p 00195000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
78a0f1f5b000-78a0f1f5f000 r--p 00195000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
78a0f1f5f000-78a0f1f61000 rw-p 00199000 ca:03 290985                     /lib/x86_64-linux-gnu/libc-2.24.so
78a0f1f61000-78a0f1f65000 rw-p 00000000 00:00 0 
78a0f1f65000-78a0f1f68000 r-xp 00000000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
78a0f1f68000-78a0f2167000 ---p 00003000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
78a0f2167000-78a0f2168000 r--p 00002000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
78a0f2168000-78a0f2169000 rw-p 00003000 ca:03 290988                     /lib/x86_64-linux-gnu/libdl-2.24.so
78a0f2169000-78a0f2181000 r-xp 00000000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
78a0f2181000-78a0f2380000 ---p 00018000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
78a0f2380000-78a0f2381000 r--p 00017000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
78a0f2381000-78a0f2382000 rw-p 00018000 ca:03 291000                     /lib/x86_64-linux-gnu/libpthread-2.24.so
78a0f2382000-78a0f2386000 rw-p 00000000 00:00 0 
78a0f2386000-78a0f2489000 r-xp 00000000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
78a0f2489000-78a0f2688000 ---p 00103000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
78a0f2688000-78a0f2689000 r--p 00102000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
78a0f2689000-78a0f268a000 rw-p 00103000 ca:03 290989                     /lib/x86_64-linux-gnu/libm-2.24.so
78a0f268a000-78a0f26ad000 r-xp 00000000 ca:03 290981                     /lib/x86_64-linux-gnu/ld-2.24.so
78a0f2890000-78a0f2894000 rw-p 00000000 00:00 0 
78a0f28ac000-78a0f28ad000 rw-p 00000000 00:00 0 
78a0f28ad000-78a0f28ae000 r--p 00023000 ca:03 290981                     /lib/x86_64-linux-gnu/ld-2.24.so
78a0f28ae000-78a0f28af000 rw-p 00024000 ca:03 290981                     /lib/x86_64-linux-gnu/ld-2.24.so
78a0f28af000-78a0f28b0000 rw-p 00000000 00:00 0 
7fff221dc000-7fff221fd000 rw-p 00000000 00:00 0                          [stack]
7fff222be000-7fff222c1000 r--p 00000000 00:00 0                          [vvar]
7fff222c1000-7fff222c3000 r-xp 00000000 00:00 0                          [vdso]
Aborted

[elimisteve]

I get the expected output when I replace

    left := nums[..half]
    right := nums[half..]

with

    left := nums[..half].clone()
    right := nums[half..].clone()

[ntrel]

Reduced:

mut a := [1, 2]
a = a[1..]
a << 3