mutation.nct

//! Vec capacity management, initialized-prefix mutation, and destruction.

see ./index.nct
see ./errors.nct
see ./storage.nct

use /internal/mem.allocation_abort
use /internal/ptr.{drop_value_at_ptr, from_addr, pointee_size}
use /internal/ptr.{slice_from_raw_parts_value, store_value_to_ptr, take_value_at_ptr}
use /mem.try_grow_owned
use /ptr.addr

func try_reserve<T>(values: &+Vec<T>, additional: usize): void! {
    if additional == 0 {
        return
    }

    let values_len: usize = values.len
    if additional > 18446744073709551615 - values_len {
        return capacity_overflow()
    }

    let required_capacity: usize = values_len + additional
    let values_capacity: usize = values.capacity
    if values_capacity >= values_len {
        let spare_capacity: usize = values_capacity - values_len
        if additional <= spare_capacity {
            return
        }
    }

    let element_size: usize = pointee_size(values.ptr)
    if element_size == 0 {
        return unsupported()
    }
    if required_capacity > 18446744073709551615 / element_size {
        return capacity_overflow()
    }
    if values_len > 18446744073709551615 / element_size {
        return capacity_overflow()
    }

    let byte_capacity: usize = required_capacity * element_size
    try_grow_owned(&+values.storage, byte_capacity)?
    values.ptr = from_addr(addr(values.storage.bytes().ptr()))
    values.capacity = required_capacity
    return
}

func reserve<T>(values: &+Vec<T>, additional: usize): void {
    try_reserve(values, additional) catch allocation_error {
        return allocation_abort()
    }
    return
}

func clear<T>(values: &+Vec<T>): void {
    let element_size: usize = pointee_size(values.ptr)
    while values.len != 0 {
        let next_len: usize = values.len - 1
        values.len = next_len
        drop_value_at_ptr(values.ptr, next_len * element_size)
    }
    return
}

func truncate<T>(values: &+Vec<T>, requested_len: usize): void {
    while values.len > requested_len {
        let removed: T = pop(values) otherwise { return }
    }
    return
}

func pop<T>(values: &+Vec<T>): T? {
    if values.len == 0 {
        return none
    }
    let next_len: usize = values.len - 1
    values.len = next_len
    let element_size: usize = pointee_size(values.ptr)
    return take_value_at_ptr(values.ptr, next_len * element_size)
}

func try_push<T>(values: &+Vec<T>, value: T): void! {
    let old_len: usize = values.len
    try_reserve(values, 1)?
    let element_size: usize = pointee_size(values.ptr)
    let byte_offset: usize = old_len * element_size
    store_value_to_ptr(values.ptr, byte_offset, move value)
    values.len = old_len + 1
    return
}

func push<T>(values: &+Vec<T>, value: T): void {
    try_push(values, move value) catch allocation_error {
        return allocation_abort()
    }
    return
}

func try_insert<T>(values: &+Vec<T>, index: usize, value: T): void! {
    let old_len: usize = values.len
    if index > old_len {
        return index_out_of_bounds()
    }

    // No fallible operation is permitted after this point. The initialized
    // prefix remains unchanged if capacity growth fails.
    try_reserve(values, 1)?
    let element_size: usize = pointee_size(values.ptr)
    var hole: usize = old_len
    while hole > index {
        let source_index: usize = hole - 1
        let shifted: T = take_value_at_ptr(values.ptr, source_index * element_size)
        store_value_to_ptr(values.ptr, hole * element_size, move shifted)
        hole = source_index
    }
    store_value_to_ptr(values.ptr, index * element_size, move value)
    values.len = old_len + 1
    return
}

func insert<T>(values: &+Vec<T>, index: usize, value: T): void {
    try_insert(values, index, move value) catch insert_error {
        return allocation_abort()
    }
    return
}

func remove<T>(values: &+Vec<T>, index: usize): T? {
    let old_len: usize = values.len
    if index >= old_len {
        return none
    }

    let element_size: usize = pointee_size(values.ptr)
    let removed: T = take_value_at_ptr(values.ptr, index * element_size)
    var hole: usize = index
    while hole + 1 < old_len {
        let source_index: usize = hole + 1
        let shifted: T = take_value_at_ptr(values.ptr, source_index * element_size)
        store_value_to_ptr(values.ptr, hole * element_size, move shifted)
        hole = source_index
    }
    values.len = old_len - 1
    return move removed
}

instance Vec<T> {
    method &+self.reserve(additional: usize): void {
        reserve(self, additional)
        return
    }

    method &+self.try_reserve(additional: usize): void! {
        try_reserve(self, additional)?
        return
    }

    method &+self.clear(): void {
        clear(self)
        return
    }

    method &+self.truncate(requested_len: usize): void {
        truncate(self, requested_len)
        return
    }

    method &+self.retain<F>(predicate: F): void where F: &+func(&T): bool {
        var predicate_fn = move predicate
        let element_size: usize = pointee_size(self.ptr)
        let original_len: usize = self.len
        var read_index: usize = 0
        var write_index: usize = 0
        while read_index < original_len {
            let current: &T = &slice_from_raw_parts_value(self.ptr, original_len)[read_index]
            if predicate_fn(current) {
                if write_index != read_index {
                    let retained: T = take_value_at_ptr(self.ptr, read_index * element_size)
                    store_value_to_ptr(self.ptr, write_index * element_size, move retained)
                }
                write_index += 1
            } else {
                drop_value_at_ptr(self.ptr, read_index * element_size)
            }
            read_index += 1
        }
        self.len = write_index
        return
    }

    method &+self.push(value: T): void {
        push(self, move value)
        return
    }

    method &+self.try_push(value: T): void! {
        try_push(self, move value)?
        return
    }

    method &+self.insert(index: usize, value: T): void {
        insert(self, index, move value)
        return
    }

    method &+self.try_insert(index: usize, value: T): void! {
        try_insert(self, index, move value)?
        return
    }

    method &+self.remove(index: usize): T? {
        return remove(self, index)?
    }

    method &+self.pop(): T? {
        return pop(self)?
    }
}

drop Vec<T>(&+self) {
    clear(self)
    self.capacity = 0
    return
}