radiance · commit

lib/std/lang/lower.rad +55 -2

/// Maximum number of `catch` clauses per `try`.
constant MAX_CATCH_CLAUSES: u32 = 32;

// Slice Layout
//
// A slice is a fat pointer consisting of a data pointer and length.
// `{ ptr: u32, len: u32 }`.
// A slice is a fat pointer consisting of a data pointer, a length and a capacity.
// `{ ptr: u32, len: u32, cap: u32 }`.

/// Slice data pointer offset.
constant SLICE_PTR_OFFSET: i32 = 0;
/// Offset of slice length in slice data structure.
constant SLICE_LEN_OFFSET: i32 = resolver::PTR_SIZE as i32;

    emit(self, il::Instr::Unreachable);

    try switchToAndSeal(self, passBlock);
}

/// Return whether two IL values are known `u32` immediates satisfying `a <= b`.
fn isLtEq(a: il::Val, b: il::Val) -> bool {
    if a == b {
        return true;
    }
    if a == il::Val::Imm(0) {
        return true;
    }
    let case il::Val::Imm(aa) = a else {
        return false;
    };
    let case il::Val::Imm(bb) = b else {
        return false;
    };
    if aa < 0 or bb < 0 {
        return false;
    }
    return aa <= bb;
}

/// Emit an `ebreak` when `a < b` holds.
fn emitTrapIfLt(
    self: *mut FnLowerer,
    typ: il::Type,
    a: il::Val,
    b: il::Val
) throws (LowerError) {
    let trapBlock = try createBlock(self, "guard#trap");
    let passBlock = try createBlock(self, "guard#pass");

    try emitBrCmp(self, il::CmpOp::Ult, typ, a, b, trapBlock, passBlock);
    try switchToAndSeal(self, trapBlock);

    emit(self, il::Instr::Ebreak);
    emit(self, il::Instr::Unreachable);

    try switchToAndSeal(self, passBlock);
}

/// Emit a conditional branch. Uses fused compare-and-branch for simple scalar
/// comparisons, falls back to separate comparison plus branch otherwise.
fn emitCondBranch(
    self: *mut FnLowerer,
    cond: *ast::Node,

    let mut endVal = containerLen;
    if let end = range.end {
        set endVal = try lowerExpr(self, end);
    }

    // Runtime slice bounds checks for dynamic range expressions.
    if not isLtEq(startVal, containerLen) {
        try emitTrapIfLt(self, il::Type::W32, containerLen, startVal);
    }
    if not isLtEq(endVal, containerLen) {
        try emitTrapIfLt(self, il::Type::W32, containerLen, endVal);
    }
    if startVal <> il::Val::Imm(0) and endVal <> containerLen and not isLtEq(startVal, endVal) {
        try emitTrapIfLt(self, il::Type::W32, endVal, startVal);
    }

    // If the start value is known to be zero, the count is just the end
    // value. Otherwise, we have to compute it.
    let mut count = endVal;

    // Only compute range offset and count if the start value is not

    let lenVal = try lowerExpr(self, args[1]);
    let mut capVal = lenVal;
    if args.len == 3 {
        set capVal = try lowerExpr(self, args[2]);
    }
    if not isLtEq(lenVal, capVal) {
        try emitTrapIfLt(self, il::Type::W32, capVal, lenVal);
    }
    return try buildSliceValue(self, item, mutable, ptrVal, lenVal, capVal);
}

/// Lower a `try` expression.
fn lowerTry(self: *mut FnLowerer, node: *ast::Node, t: ast::Try) -> il::Val throws (LowerError) {

lib/std/lang/resolver.rad +1 -1

    if let endNode = range.end {
        if let val = constSliceIndex(self, endNode) {
            set endVal = val;
        }
    }
    if let val = startVal; val >= length {
    if let val = startVal; val > length {
        throw emitError(self, site, ErrorKind::SliceRangeOutOfBounds);
    }
    if let val = endVal; val > length {
        throw emitError(self, site, ErrorKind::SliceRangeOutOfBounds);
    }

lib/std/lang/resolver/tests.rad +1 -1

        let program = "let xs: [u8; 2] = [1, 2]; let slice = &xs[..3];";
        let result = try resolveProgramStr(&mut a, program);
        try expectErrorKind(&result, super::ErrorKind::SliceRangeOutOfBounds);
    } {
        let mut a = testResolver();
        let program = "let xs: [u8; 2] = [1, 2]; let slice = &xs[2..];";
        let program = "let xs: [u8; 2] = [1, 2]; let slice = &xs[3..];";
        let result = try resolveProgramStr(&mut a, program);
        try expectErrorKind(&result, super::ErrorKind::SliceRangeOutOfBounds);
    } {
        let mut a = testResolver();
        let program = "let xs: [u8; 4] = [1, 2, 3, 4]; let slice = &xs[3..2];";

test/tests/array.slice.openend.ril +5 -0

fn w64 $sliceOpenEnd(w64 %0, w64 %1, w32 %2) {
  @entry0
    br.ult w32 4 %2 @guard#trap1 @guard#pass2;
  @guard#trap1
    ebreak;
    unreachable;
  @guard#pass2
    mul w64 %3 %2 4;
    add w64 %4 %1 %3;
    sub w32 %5 4 %2;
    reserve %6 16 8;
    store w64 %4 %6 0;

test/tests/array.slice.openstart.ril +5 -0

fn w64 $sliceOpenStart(w64 %0, w64 %1, w32 %2) {
  @entry0
    br.ult w32 4 %2 @guard#trap1 @guard#pass2;
  @guard#trap1
    ebreak;
    unreachable;
  @guard#pass2
    reserve %3 16 8;
    store w64 %1 %3 0;
    store w32 %2 %3 8;
    store w32 %2 %3 12;
    blit %0 %3 16;

test/tests/builtin.sliceof.invalid.cap.rad added +10 -0

1	+	//! returns: 133
2	+	//! Test @sliceOf runtime validation for len > cap.
3	+
4	+	@default fn main() -> i32 {
5	+	let mut arr: [i32; 4] = [10, 20, 30, 40];
6	+	let ptr: *i32 = &arr[0];
7	+	let slice: *[i32] = @sliceOf(ptr, 4, 3);
8	+
9	+	return slice.len as i32;
10	+	}

test/tests/slice.basic.ril +5 -0

    ret %0;
}

fn w64 $sliceOfWithCap(w64 %0, w64 %1, w32 %2, w32 %3) {
  @entry0
    br.ult w32 %3 %2 @guard#trap1 @guard#pass2;
  @guard#trap1
    ebreak;
    unreachable;
  @guard#pass2
    reserve %4 16 8;
    store w64 %1 %4 0;
    store w32 %2 %4 8;
    store w32 %3 %4 12;
    blit %0 %4 16;

test/tests/slice.empty.suffix.rad added +30 -0

1	+	//! returns: 0
2	+
3	+	fn checkArraySuffix() {
4	+	let xs: [u8; 3] = [10, 20, 30];
5	+	let empty = &xs[xs.len..xs.len];
6	+
7	+	assert empty.len == 0;
8	+	}
9	+
10	+	fn checkSliceSuffix() {
11	+	let xs: [u8; 3] = [10, 20, 30];
12	+	let slice: *[u8] = &xs[..];
13	+	let empty = &slice[slice.len..slice.len];
14	+
15	+	assert empty.len == 0;
16	+	}
17	+
18	+	fn checkStringSuffix() {
19	+	let text = "abc";
20	+	let empty = &text[text.len..text.len];
21	+
22	+	assert empty.len == 0;
23	+	}
24	+
25	+	@default fn main() -> i32 {
26	+	checkArraySuffix();
27	+	checkSliceSuffix();
28	+	checkStringSuffix();
29	+	return 0;
30	+	}

test/tests/slice.range.bounds.check.rad added +14 -0

1	+	//! returns: 133
2	+	//! Test dynamic slice range bounds checking with runtime EBREAK.
3	+
4	+	fn id(n: u32) -> u32 {
5	+	return n;
6	+	}
7	+
8	+	@default fn main() -> i32 {
9	+	let xs: [i32; 3] = [1, 2, 3];
10	+	let slice: *[i32] = &xs[..];
11	+	let bad = &slice[id(4)..id(4)];
12	+
13	+	return bad.len as i32;
14	+	}

test/tests/slice.range.dynamic.rad added +42 -0

1	+	//! returns: 0
2	+
3	+	fn id(n: u32) -> u32 {
4	+	return n;
5	+	}
6	+
7	+	@default fn main() -> i32 {
8	+	let xs: [u8; 5] = [10, 20, 30, 40, 50];
9	+	let slice: *[u8] = &xs[..];
10	+
11	+	let start = id(1);
12	+	let end = id(4);
13	+	let mid = &slice[start..end];
14	+
15	+	assert mid.len == 3;
16	+	assert mid[0] == 20;
17	+	assert mid[1] == 30;
18	+	assert mid[2] == 40;
19	+
20	+	let suffixStart = id(2);
21	+	let suffix = &slice[suffixStart..];
22	+
23	+	assert suffix.len == 3;
24	+	assert suffix[0] == 30;
25	+	assert suffix[1] == 40;
26	+	assert suffix[2] == 50;
27	+
28	+	let prefixEnd = id(3);
29	+	let prefix = &slice[..prefixEnd];
30	+
31	+	assert prefix.len == 3;
32	+	assert prefix[0] == 10;
33	+	assert prefix[1] == 20;
34	+	assert prefix[2] == 30;
35	+
36	+	let emptyStart = id(slice.len);
37	+	let emptyEnd = id(slice.len);
38	+	let empty = &slice[emptyStart..emptyEnd];
39	+
40	+	assert empty.len == 0;
41	+	return 0;
42	+	}

test/tests/slice.range.order.check.rad added +14 -0

1	+	//! returns: 133
2	+	//! Test dynamic slice range ordering check with runtime EBREAK.
3	+
4	+	fn id(n: u32) -> u32 {
5	+	return n;
6	+	}
7	+
8	+	@default fn main() -> i32 {
9	+	let xs: [i32; 3] = [1, 2, 3];
10	+	let slice: *[i32] = &xs[..];
11	+	let bad = &slice[id(2)..id(1)];
12	+
13	+	return bad.len as i32;
14	+	}

test/tests/slice.range.ril +25 -0

fn w64 $sliceRange(w64 %0, w64 %1, w32 %2, w32 %3) {
  @entry0
    load w64 %4 %1 0;
    load w32 %5 %1 8;
    br.ult w32 %5 %2 @guard#trap1 @guard#pass2;
  @guard#trap1
    ebreak;
    unreachable;
  @guard#pass2
    br.ult w32 %5 %3 @guard#trap3 @guard#pass4;
  @guard#trap3
    ebreak;
    unreachable;
  @guard#pass4
    br.ult w32 %3 %2 @guard#trap5 @guard#pass6;
  @guard#trap5
    ebreak;
    unreachable;
  @guard#pass6
    mul w64 %6 %2 4;
    add w64 %7 %4 %6;
    sub w32 %8 %3 %2;
    reserve %9 16 8;
    store w64 %7 %9 0;


fn w64 $sliceRangeOpenEnd(w64 %0, w64 %1, w32 %2) {
  @entry0
    load w64 %3 %1 0;
    load w32 %4 %1 8;
    br.ult w32 %4 %2 @guard#trap1 @guard#pass2;
  @guard#trap1
    ebreak;
    unreachable;
  @guard#pass2
    mul w64 %5 %2 4;
    add w64 %6 %3 %5;
    sub w32 %7 %4 %2;
    reserve %8 16 8;
    store w64 %6 %8 0;


fn w64 $sliceRangeOpenStart(w64 %0, w64 %1, w32 %2) {
  @entry0
    load w64 %3 %1 0;
    load w32 %4 %1 8;
    br.ult w32 %4 %2 @guard#trap1 @guard#pass2;
  @guard#trap1
    ebreak;
    unreachable;
  @guard#pass2
    reserve %5 16 8;
    store w64 %3 %5 0;
    store w32 %2 %5 8;
    store w32 %2 %5 12;
    blit %0 %5 16;

205	205		/// Maximum number of `catch` clauses per `try`.
206	206		constant MAX_CATCH_CLAUSES: u32 = 32;
207	207
208	208		// Slice Layout
209	209		//
210		-	// A slice is a fat pointer consisting of a data pointer and length.
211		-	// `{ ptr: u32, len: u32 }`.
	210	+	// A slice is a fat pointer consisting of a data pointer, a length and a capacity.
	211	+	// `{ ptr: u32, len: u32, cap: u32 }`.
212	212
213	213		/// Slice data pointer offset.
214	214		constant SLICE_PTR_OFFSET: i32 = 0;
215	215		/// Offset of slice length in slice data structure.
216	216		constant SLICE_LEN_OFFSET: i32 = resolver::PTR_SIZE as i32;

2089	2089		emit(self, il::Instr::Unreachable);
2090	2090
2091	2091		try switchToAndSeal(self, passBlock);
2092	2092		}
2093	2093
	2094	+	/// Return whether two IL values are known `u32` immediates satisfying `a <= b`.
	2095	+	fn isLtEq(a: il::Val, b: il::Val) -> bool {
	2096	+	if a == b {
	2097	+	return true;
	2098	+	}
	2099	+	if a == il::Val::Imm(0) {
	2100	+	return true;
	2101	+	}
	2102	+	let case il::Val::Imm(aa) = a else {
	2103	+	return false;
	2104	+	};
	2105	+	let case il::Val::Imm(bb) = b else {
	2106	+	return false;
	2107	+	};
	2108	+	if aa < 0 or bb < 0 {
	2109	+	return false;
	2110	+	}
	2111	+	return aa <= bb;
	2112	+	}
	2113	+
	2114	+	/// Emit an `ebreak` when `a < b` holds.
	2115	+	fn emitTrapIfLt(
	2116	+	self: *mut FnLowerer,
	2117	+	typ: il::Type,
	2118	+	a: il::Val,
	2119	+	b: il::Val
	2120	+	) throws (LowerError) {
	2121	+	let trapBlock = try createBlock(self, "guard#trap");
	2122	+	let passBlock = try createBlock(self, "guard#pass");
	2123	+
	2124	+	try emitBrCmp(self, il::CmpOp::Ult, typ, a, b, trapBlock, passBlock);
	2125	+	try switchToAndSeal(self, trapBlock);
	2126	+
	2127	+	emit(self, il::Instr::Ebreak);
	2128	+	emit(self, il::Instr::Unreachable);
	2129	+
	2130	+	try switchToAndSeal(self, passBlock);
	2131	+	}
	2132	+
2094	2133		/// Emit a conditional branch. Uses fused compare-and-branch for simple scalar
2095	2134		/// comparisons, falls back to separate comparison plus branch otherwise.
2096	2135		fn emitCondBranch(
2097	2136		self: *mut FnLowerer,
2098	2137		cond: *ast::Node,

4770	4809		let mut endVal = containerLen;
4771	4810		if let end = range.end {
4772	4811		set endVal = try lowerExpr(self, end);
4773	4812		}
4774	4813
	4814	+	// Runtime slice bounds checks for dynamic range expressions.
	4815	+	if not isLtEq(startVal, containerLen) {
	4816	+	try emitTrapIfLt(self, il::Type::W32, containerLen, startVal);
	4817	+	}
	4818	+	if not isLtEq(endVal, containerLen) {
	4819	+	try emitTrapIfLt(self, il::Type::W32, containerLen, endVal);
	4820	+	}
	4821	+	if startVal <> il::Val::Imm(0) and endVal <> containerLen and not isLtEq(startVal, endVal) {
	4822	+	try emitTrapIfLt(self, il::Type::W32, endVal, startVal);
	4823	+	}
	4824	+
4775	4825		// If the start value is known to be zero, the count is just the end
4776	4826		// value. Otherwise, we have to compute it.
4777	4827		let mut count = endVal;
4778	4828
4779	4829		// Only compute range offset and count if the start value is not

5984	6034		let lenVal = try lowerExpr(self, args[1]);
5985	6035		let mut capVal = lenVal;
5986	6036		if args.len == 3 {
5987	6037		set capVal = try lowerExpr(self, args[2]);
5988	6038		}
	6039	+	if not isLtEq(lenVal, capVal) {
	6040	+	try emitTrapIfLt(self, il::Type::W32, capVal, lenVal);
	6041	+	}
5989	6042		return try buildSliceValue(self, item, mutable, ptrVal, lenVal, capVal);
5990	6043		}
5991	6044
5992	6045		/// Lower a `try` expression.
5993	6046		fn lowerTry(self: mut FnLowerer, node: ast::Node, t: ast::Try) -> il::Val throws (LowerError) {

5176	5176		if let endNode = range.end {
5177	5177		if let val = constSliceIndex(self, endNode) {
5178	5178		set endVal = val;
5179	5179		}
5180	5180		}
5181		-	if let val = startVal; val >= length {
	5181	+	if let val = startVal; val > length {
5182	5182		throw emitError(self, site, ErrorKind::SliceRangeOutOfBounds);
5183	5183		}
5184	5184		if let val = endVal; val > length {
5185	5185		throw emitError(self, site, ErrorKind::SliceRangeOutOfBounds);
5186	5186		}

966	966		let program = "let xs: [u8; 2] = [1, 2]; let slice = &xs[..3];";
967	967		let result = try resolveProgramStr(&mut a, program);
968	968		try expectErrorKind(&result, super::ErrorKind::SliceRangeOutOfBounds);
969	969		} {
970	970		let mut a = testResolver();
971		-	let program = "let xs: [u8; 2] = [1, 2]; let slice = &xs[2..];";
	971	+	let program = "let xs: [u8; 2] = [1, 2]; let slice = &xs[3..];";
972	972		let result = try resolveProgramStr(&mut a, program);
973	973		try expectErrorKind(&result, super::ErrorKind::SliceRangeOutOfBounds);
974	974		} {
975	975		let mut a = testResolver();
976	976		let program = "let xs: [u8; 4] = [1, 2, 3, 4]; let slice = &xs[3..2];";

1	1		fn w64 $sliceOpenEnd(w64 %0, w64 %1, w32 %2) {
2	2		@entry0
	3	+	br.ult w32 4 %2 @guard#trap1 @guard#pass2;
	4	+	@guard#trap1
	5	+	ebreak;
	6	+	unreachable;
	7	+	@guard#pass2
3	8		mul w64 %3 %2 4;
4	9		add w64 %4 %1 %3;
5	10		sub w32 %5 4 %2;
6	11		reserve %6 16 8;
7	12		store w64 %4 %6 0;

1	1		fn w64 $sliceOpenStart(w64 %0, w64 %1, w32 %2) {
2	2		@entry0
	3	+	br.ult w32 4 %2 @guard#trap1 @guard#pass2;
	4	+	@guard#trap1
	5	+	ebreak;
	6	+	unreachable;
	7	+	@guard#pass2
3	8		reserve %3 16 8;
4	9		store w64 %1 %3 0;
5	10		store w32 %2 %3 8;
6	11		store w32 %2 %3 12;
7	12		blit %0 %3 16;

34	34		ret %0;
35	35		}
36	36
37	37		fn w64 $sliceOfWithCap(w64 %0, w64 %1, w32 %2, w32 %3) {
38	38		@entry0
	39	+	br.ult w32 %3 %2 @guard#trap1 @guard#pass2;
	40	+	@guard#trap1
	41	+	ebreak;
	42	+	unreachable;
	43	+	@guard#pass2
39	44		reserve %4 16 8;
40	45		store w64 %1 %4 0;
41	46		store w32 %2 %4 8;
42	47		store w32 %3 %4 12;
43	48		blit %0 %4 16;

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	+	br.ult w32 %5 %2 @guard#trap1 @guard#pass2;
	6	+	@guard#trap1
	7	+	ebreak;
	8	+	unreachable;
	9	+	@guard#pass2
	10	+	br.ult w32 %5 %3 @guard#trap3 @guard#pass4;
	11	+	@guard#trap3
	12	+	ebreak;
	13	+	unreachable;
	14	+	@guard#pass4
	15	+	br.ult w32 %3 %2 @guard#trap5 @guard#pass6;
	16	+	@guard#trap5
	17	+	ebreak;
	18	+	unreachable;
	19	+	@guard#pass6
5	20		mul w64 %6 %2 4;
6	21		add w64 %7 %4 %6;
7	22		sub w32 %8 %3 %2;
8	23		reserve %9 16 8;
9	24		store w64 %7 %9 0;

15	30
16	31		fn w64 $sliceRangeOpenEnd(w64 %0, w64 %1, w32 %2) {
17	32		@entry0
18	33		load w64 %3 %1 0;
19	34		load w32 %4 %1 8;
	35	+	br.ult w32 %4 %2 @guard#trap1 @guard#pass2;
	36	+	@guard#trap1
	37	+	ebreak;
	38	+	unreachable;
	39	+	@guard#pass2
20	40		mul w64 %5 %2 4;
21	41		add w64 %6 %3 %5;
22	42		sub w32 %7 %4 %2;
23	43		reserve %8 16 8;
24	44		store w64 %6 %8 0;

30	50
31	51		fn w64 $sliceRangeOpenStart(w64 %0, w64 %1, w32 %2) {
32	52		@entry0
33	53		load w64 %3 %1 0;
34	54		load w32 %4 %1 8;
	55	+	br.ult w32 %4 %2 @guard#trap1 @guard#pass2;
	56	+	@guard#trap1
	57	+	ebreak;
	58	+	unreachable;
	59	+	@guard#pass2
35	60		reserve %5 16 8;
36	61		store w64 %3 %5 0;
37	62		store w32 %2 %5 8;
38	63		store w32 %2 %5 12;
39	64		blit %0 %5 16;