Preserve backing capacity in slice ranges

dee95968ebbc34ae4674a5b576baf5f0c7b8f055b2fa45b36c2aca09c2cfe41c
Alexis Sellier committed ago 1 parent 56a00753
lib/std/lang/lower.rad +14 -2
663 663
    elemType: resolver::Type,
664 664
}
665 665
666 666
/// Result of resolving a slice range to a data pointer and element count.
667 667
record SliceRangeResult: Copy {
668 +
    /// Register holding the first element address.
668 669
    dataReg: il::Reg,
670 +
    /// Number of elements in the range.
669 671
    count: il::Val,
672 +
    /// Available capacity from the first element address.
673 +
    capacity: il::Val,
670 674
}
671 675
672 676
/////////////////////////////
673 677
// Function Lowering State //
674 678
/////////////////////////////
4961 4965
    let baseReg = emitValToReg(self, baseVal);
4962 4966
4963 4967
    // Extract data pointer and container length.
4964 4968
    let mut dataReg = baseReg;
4965 4969
    let mut containerLen: il::Val = undefined;
4970 +
    let mut capacity: il::Val = undefined;
4966 4971
    if let cap = info.capacity { // Slice from array.
4967 4972
        set containerLen = il::Val::Imm(cap as i64);
4973 +
        set capacity = containerLen;
4968 4974
    } else { // Slice from slice.
4969 4975
        set dataReg = loadSlicePtr(self, baseReg);
4970 4976
        set containerLen = loadSliceLen(self, baseReg);
4977 +
        set capacity = loadSliceCap(self, baseReg);
4971 4978
    }
4972 4979
4973 4980
    // Compute range bounds.
4974 4981
    let mut startVal: il::Val = il::Val::Imm(0);
4975 4982
    if let start = range.start {
5010 5017
            dst: lenReg,
5011 5018
            a: endVal,
5012 5019
            b: startVal,
5013 5020
        });
5014 5021
        set count = il::Val::Reg(lenReg);
5022 +
        if capacity == endVal {
5023 +
            set capacity = count;
5024 +
        } else {
5025 +
            set capacity = emitTypedBinOp(self, il::BinOp::Sub, il::Type::W32, capacity, startVal);
5026 +
        }
5015 5027
    }
5016 -
    return SliceRangeResult { dataReg, count };
5028 +
    return SliceRangeResult { dataReg, count, capacity };
5017 5029
}
5018 5030
5019 5031
/// Lower a slice range expression into a slice header value.
5020 5032
unsafe fn lowerSliceRange(
5021 5033
    self: &mut FnLowerer,
5026 5038
    let info = resolver::sliceRangeInfoFor(self.low.resolver, sliceNode) else {
5027 5039
        throw LowerError::MissingMetadata;
5028 5040
    };
5029 5041
    let r = try resolveSliceRangePtr(self, container, range, info);
5030 5042
    return try buildSliceValue(
5031 -
        self, info.itemType, info.mutable, il::Val::Reg(r.dataReg), r.count, r.count
5043 +
        self, info.itemType, info.mutable, il::Val::Reg(r.dataReg), r.count, r.capacity
5032 5044
    );
5033 5045
}
5034 5046
5035 5047
/// Lower an address-of (`&x`) expression.
5036 5048
unsafe fn lowerAddressOf(self: &mut FnLowerer, node: *ast::Node, addr: ast::AddressOf) -> il::Val throws (LowerError) {
test/tests/array.slice.openstart.ril +1 -1
6 6
    unreachable;
7 7
  @guard#pass2
8 8
    reserve %3 16 8;
9 9
    store w64 %1 %3 0;
10 10
    store w32 %2 %3 8;
11 -
    store w32 %2 %3 12;
11 +
    store w32 4 %3 12;
12 12
    blit %0 %3 16;
13 13
    ret %0;
14 14
}
test/tests/slice.range.capacity.bounds.rad added +14 -0
1 +
//! returns: 133
2 +
//! Slice range bounds use length even when capacity is larger.
3 +
4 +
/// Preserve a dynamic range bound.
5 +
fn bound(value: u32) -> u32 {
6 +
    return value;
7 +
}
8 +
9 +
@default fn main() -> i32 {
10 +
    let storage: [i32; 4] = [10, 20, 30, 40];
11 +
    let prefix = &storage[..1];
12 +
    let invalid = &prefix[..bound(2)];
13 +
    return invalid.len as i32;
14 +
}
test/tests/slice.range.capacity.rad added +58 -0
1 +
//! returns: 0
2 +
//! Slice ranges retain the backing capacity after their start offset.
3 +
4 +
/// Allocator interface used by append.
5 +
record Allocator: Copy {
6 +
    /// Allocation callback.
7 +
    func: unsafe fn(*unsafe mut opaque, u32, u32) -> *mut opaque,
8 +
    /// Callback context.
9 +
    ctx: *unsafe mut opaque,
10 +
}
11 +
12 +
/// Reject allocation when append must use existing storage.
13 +
unsafe fn rejectAlloc(ctx: *unsafe mut opaque, size: u32, alignment: u32) -> *mut opaque {
14 +
    panic "rejectAlloc: unexpected allocation";
15 +
}
16 +
17 +
/// Check dynamic range bounds and nested slice capacity.
18 +
fn checkRange(storage: *mut [i32], start: u32, end: u32) {
19 +
    let cap = storage.cap;
20 +
    let part: *mut [i32] = &mut storage[start..end];
21 +
    assert part.len == end - start;
22 +
    assert part.cap == cap - start;
23 +
    let empty = &mut part[..0];
24 +
    assert empty.len == 0;
25 +
    assert empty.cap == part.cap;
26 +
}
27 +
28 +
@default unsafe fn main() -> i32 {
29 +
    static storage: [i32; 4] = [10, 20, 30, 40];
30 +
    let empty = &mut storage[..0];
31 +
    assert empty.len == 0;
32 +
    assert empty.cap == 4;
33 +
    let prefix = &storage[..2];
34 +
    assert prefix.len == 2;
35 +
    assert prefix.cap == 4;
36 +
    let middle = &storage[1..2];
37 +
    assert middle.len == 1;
38 +
    assert middle.cap == 3;
39 +
    assert middle[0] == 20;
40 +
    let tail = &storage[2..];
41 +
    assert tail.len == 2;
42 +
    assert tail.cap == 2;
43 +
    let end = &storage[4..4];
44 +
    assert end.len == 0;
45 +
    assert end.cap == 0;
46 +
    checkRange((&mut storage[..2]) as *mut [i32], 1, 2);
47 +
    checkRange((&mut storage[..]) as *mut [i32], 4, 4);
48 +
    let mut items: *mut [i32] = &mut storage[1..1];
49 +
    let allocator = Allocator { func: rejectAlloc, ctx: &mut storage as *unsafe mut opaque };
50 +
    items.append(50, allocator);
51 +
    items.append(60, allocator);
52 +
    items.append(70, allocator);
53 +
    assert items.len == 3;
54 +
    assert items.cap == 3;
55 +
    assert items[0] == 50;
56 +
    assert items[2] == 70;
57 +
    return 0;
58 +
}
test/tests/slice.range.ril +38 -31
1 1
fn w64 $sliceRange(w64 %0, w64 %1, w32 %2, w32 %3) {
2 2
  @entry0
3 3
    load w64 %4 %1 0;
4 4
    load w32 %5 %1 8;
5 +
    load w32 %6 %1 12;
5 6
    br.ult w32 %5 %2 @guard#trap1 @guard#pass2;
6 7
  @guard#trap1
7 8
    ebreak;
8 9
    unreachable;
9 10
  @guard#pass2
15 16
    br.ult w32 %3 %2 @guard#trap5 @guard#pass6;
16 17
  @guard#trap5
17 18
    ebreak;
18 19
    unreachable;
19 20
  @guard#pass6
20 -
    mul w64 %6 %2 4;
21 -
    add w64 %7 %4 %6;
22 -
    sub w32 %8 %3 %2;
23 -
    reserve %9 16 8;
24 -
    store w64 %7 %9 0;
25 -
    store w32 %8 %9 8;
26 -
    store w32 %8 %9 12;
27 -
    blit %0 %9 16;
21 +
    mul w64 %7 %2 4;
22 +
    add w64 %8 %4 %7;
23 +
    sub w32 %9 %3 %2;
24 +
    sub w32 %10 %6 %2;
25 +
    reserve %11 16 8;
26 +
    store w64 %8 %11 0;
27 +
    store w32 %9 %11 8;
28 +
    store w32 %10 %11 12;
29 +
    blit %0 %11 16;
28 30
    ret %0;
29 31
}
30 32
31 33
fn w64 $sliceRangeOpenEnd(w64 %0, w64 %1, w32 %2) {
32 34
  @entry0
33 35
    load w64 %3 %1 0;
34 36
    load w32 %4 %1 8;
37 +
    load w32 %5 %1 12;
35 38
    br.ult w32 %4 %2 @guard#trap1 @guard#pass2;
36 39
  @guard#trap1
37 40
    ebreak;
38 41
    unreachable;
39 42
  @guard#pass2
40 -
    mul w64 %5 %2 4;
41 -
    add w64 %6 %3 %5;
42 -
    sub w32 %7 %4 %2;
43 -
    reserve %8 16 8;
44 -
    store w64 %6 %8 0;
45 -
    store w32 %7 %8 8;
46 -
    store w32 %7 %8 12;
47 -
    blit %0 %8 16;
43 +
    mul w64 %6 %2 4;
44 +
    add w64 %7 %3 %6;
45 +
    sub w32 %8 %4 %2;
46 +
    sub w32 %9 %5 %2;
47 +
    reserve %10 16 8;
48 +
    store w64 %7 %10 0;
49 +
    store w32 %8 %10 8;
50 +
    store w32 %9 %10 12;
51 +
    blit %0 %10 16;
48 52
    ret %0;
49 53
}
50 54
51 55
fn w64 $sliceRangeOpenStart(w64 %0, w64 %1, w32 %2) {
52 56
  @entry0
53 57
    load w64 %3 %1 0;
54 58
    load w32 %4 %1 8;
59 +
    load w32 %5 %1 12;
55 60
    br.ult w32 %4 %2 @guard#trap1 @guard#pass2;
56 61
  @guard#trap1
57 62
    ebreak;
58 63
    unreachable;
59 64
  @guard#pass2
60 -
    reserve %5 16 8;
61 -
    store w64 %3 %5 0;
62 -
    store w32 %2 %5 8;
63 -
    store w32 %2 %5 12;
64 -
    blit %0 %5 16;
65 +
    reserve %6 16 8;
66 +
    store w64 %3 %6 0;
67 +
    store w32 %2 %6 8;
68 +
    store w32 %5 %6 12;
69 +
    blit %0 %6 16;
65 70
    ret %0;
66 71
}
67 72
68 73
fn w64 $sliceRangeFull(w64 %0, w64 %1) {
69 74
  @entry0
70 75
    load w64 %2 %1 0;
71 76
    load w32 %3 %1 8;
72 -
    reserve %4 16 8;
73 -
    store w64 %2 %4 0;
74 -
    store w32 %3 %4 8;
75 -
    store w32 %3 %4 12;
76 -
    blit %0 %4 16;
77 +
    load w32 %4 %1 12;
78 +
    reserve %5 16 8;
79 +
    store w64 %2 %5 0;
80 +
    store w32 %3 %5 8;
81 +
    store w32 %4 %5 12;
82 +
    blit %0 %5 16;
77 83
    ret %0;
78 84
}
79 85
80 86
fn w64 $sliceArray(w64 %0, w64 %1) {
81 87
  @entry0
82 88
    mul w64 %2 1 4;
83 89
    add w64 %3 %1 %2;
84 90
    sub w32 %4 3 1;
85 -
    reserve %5 16 8;
86 -
    store w64 %3 %5 0;
87 -
    store w32 %4 %5 8;
88 -
    store w32 %4 %5 12;
89 -
    blit %0 %5 16;
91 +
    sub w32 %5 4 1;
92 +
    reserve %6 16 8;
93 +
    store w64 %3 %6 0;
94 +
    store w32 %4 %6 8;
95 +
    store w32 %5 %6 12;
96 +
    blit %0 %6 16;
90 97
    ret %0;
91 98
}