radiance · commit

resolver: Initialize active ownership state

d3a86b214d8493da46b920eaf31b90750f64c1affaa1b43f981fd9256ecd9f0c

Symbol and loop slots are initialized before their active counts
increase. Express that invariant with non-optional symbol pointers
and initialize only active slots to avoid redundant stores and checks.

Assisted-by: Codex:gpt-6-astra

Alexis Sellier committed 15 days ago 1 parent 76d18fbc

lib/std/lang/resolver.rad +20 -16

    /// Use the value as an assignment target.
    Place,
}

/// Per-control-flow-path ownership state.
/// Read only the initialized symbol prefix below `len`.
record LinearEnv: Copy {
    /// Symbols tracked on this control-flow path.
    symbols: [?*mut Symbol; MAX_LINEAR_BINDINGS],
    /// Symbol pointers. Entries below `len` are initialized and not optional.
    symbols: [*mut Symbol; MAX_LINEAR_BINDINGS],
    /// Bit set for each binding that remains available.
    available: u64,
    /// Number of entries in `symbols`.
    /// Number of initialized entries in `symbols`.
    len: u32,
    /// Whether this control-flow path has terminated.
    terminated: bool,
}

/// Function-local exact-use checker state.
/// Read loop arrays only at indices below `loopDepth`.
/// `enterLinearLoop` initializes each slot before it increases `loopDepth`.
record LinearChecker: Copy {
    /// Resolver that owns the symbols and diagnostics.
    resolver: *mut Resolver,
    /// Binding count at entry to each active loop.
    loopMarks: [u32; MAX_LINEAR_LOOP_DEPTH],

}

/// Find a tracked binding by symbol identity.
fn findLinearBinding(env: *LinearEnv, sym: *mut Symbol) -> ?u32 {
    for i in 0..env.len {
        if let bound = env.symbols[i]; bound == sym {
        if env.symbols[i] == sym {
            return i;
        }
    }
    return nil;
}

    start: u32,
) throws (ResolveError) {
    if not env.terminated {
        for i in start..env.len {
            if linearBindingAvailable(env, i) {
                let sym = env.symbols[i] else panic "finishLinearScope: missing symbol";
                let sym = env.symbols[i];
                let case SymbolData::Value { type: ty, .. } = sym.data
                    else panic "finishLinearScope: expected value symbol";
                if isLinear(ty) {
                    throw emitError(
                        checker.resolver,

    }
    assert left.len == right.len, "joinLinearBranches: scope mismatch";
    let mut result = left;
    for i in 0..left.len {
        if linearBindingAvailable(&left, i) <> linearBindingAvailable(&right, i) {
            let sym = left.symbols[i] else panic "joinLinearBranches: missing symbol";
            let sym = left.symbols[i];
            let case SymbolData::Value { type: ty, .. } = sym.data
                else panic "joinLinearBranches: expected value symbol";
            if isLinear(ty) {
                throw emitError(
                    checker.resolver,

    checker: *mut LinearChecker,
    env: *mut LinearEnv,
) throws (ResolveError) {
    for i in 0..env.len {
        if linearBindingAvailable(env, i) {
            let sym = env.symbols[i] else panic "finishLinearExit: missing symbol";
            let sym = env.symbols[i];
            let case SymbolData::Value { type: ty, .. } = sym.data
                else panic "finishLinearExit: expected value symbol";
            if isLinear(ty) {
                throw emitError(
                    checker.resolver,

    }
    try finishLinearScope(checker, env, start);
}

/// Push a repeated-control-flow boundary.
/// Initialize all loop state at this depth before increasing `loopDepth`.
fn enterLinearLoop(checker: *mut LinearChecker, env: *LinearEnv) {
    assert checker.loopDepth < MAX_LINEAR_LOOP_DEPTH, "linear loop nesting overflow";
    let depth = checker.loopDepth;
    set checker.loopMarks[depth] = env.len;
    set checker.loopAvailable[depth] = env.available;

    let mark = checker.loopMarks[depth];
    let entryAvailable = checker.loopAvailable[depth];
    for i in 0..mark {
        let bit = (1 as u64) << (i as u64);
        if (env.available & bit) <> (entryAvailable & bit) {
            let sym = env.symbols[i] else panic "checkLinearLoopBackEdge: missing symbol";
            let sym = env.symbols[i];
            throw emitError(
                checker.resolver,
                node,
                ErrorKind::LinearBranchMismatch(sym.name),
            );

    if checker.loopHasNaturalExit[depth] or checker.loopBreakSeen[depth] {
        let expected = checker.loopExitAvailable[depth];
        for i in 0..mark {
            let bit = (1 as u64) << (i as u64);
            if (env.available & bit) <> (expected & bit) {
                let sym = env.symbols[i] else panic "checkLinearLoopBreak: missing symbol";
                let sym = env.symbols[i];
                throw emitError(
                    checker.resolver,
                    node,
                    ErrorKind::LinearBranchMismatch(sym.name),
                );

            }
            case ast::ProngArm::Else => {}
        }
        if prong.guard <> nil {
            for i in bindingsStart..branch.len {
                let sym = branch.symbols[i] else panic "checkLinearMatch: missing symbol";
                let sym = branch.symbols[i];
                let case SymbolData::Value { type: ty, .. } = sym.data
                    else panic "checkLinearMatch: expected value symbol";
                if isLinear(ty) {
                    throw emitError(checker.resolver, prongNode, ErrorKind::LinearDiscard);
                }

    params: *mut [*ast::Node],
    body: *ast::Node,
) throws (ResolveError) {
    let mut checker = LinearChecker {
        resolver: self,
        loopMarks: [0; MAX_LINEAR_LOOP_DEPTH],
        loopAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
        loopExitAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
        loopHasNaturalExit: [false; MAX_LINEAR_LOOP_DEPTH],
        loopBreakSeen: [false; MAX_LINEAR_LOOP_DEPTH],
        loopMarks: undefined,
        loopAvailable: undefined,
        loopExitAvailable: undefined,
        loopHasNaturalExit: undefined,
        loopBreakSeen: undefined,
        loopDepth: 0,
    };
    let mut env = LinearEnv {
        symbols: [nil; MAX_LINEAR_BINDINGS],
        symbols: undefined,
        available: 0,
        len: 0,
        terminated: false,
    };
    if let receiverNode = receiver {

795	795		/// Use the value as an assignment target.
796	796		Place,
797	797		}
798	798
799	799		/// Per-control-flow-path ownership state.
	800	+	/// Read only the initialized symbol prefix below `len`.
800	801		record LinearEnv: Copy {
801		-	/// Symbols tracked on this control-flow path.
802		-	symbols: [?*mut Symbol; MAX_LINEAR_BINDINGS],
	802	+	/// Symbol pointers. Entries below `len` are initialized and not optional.
	803	+	symbols: [*mut Symbol; MAX_LINEAR_BINDINGS],
803	804		/// Bit set for each binding that remains available.
804	805		available: u64,
805		-	/// Number of entries in `symbols`.
	806	+	/// Number of initialized entries in `symbols`.
806	807		len: u32,
807	808		/// Whether this control-flow path has terminated.
808	809		terminated: bool,
809	810		}
810	811
811	812		/// Function-local exact-use checker state.
	813	+	/// Read loop arrays only at indices below `loopDepth`.
	814	+	/// `enterLinearLoop` initializes each slot before it increases `loopDepth`.
812	815		record LinearChecker: Copy {
813	816		/// Resolver that owns the symbols and diagnostics.
814	817		resolver: *mut Resolver,
815	818		/// Binding count at entry to each active loop.
816	819		loopMarks: [u32; MAX_LINEAR_LOOP_DEPTH],

7438	7441		}
7439	7442
7440	7443		/// Find a tracked binding by symbol identity.
7441	7444		fn findLinearBinding(env: LinearEnv, sym: mut Symbol) -> ?u32 {
7442	7445		for i in 0..env.len {
7443		-	if let bound = env.symbols[i]; bound == sym {
	7446	+	if env.symbols[i] == sym {
7444	7447		return i;
7445	7448		}
7446	7449		}
7447	7450		return nil;
7448	7451		}

7483	7486		start: u32,
7484	7487		) throws (ResolveError) {
7485	7488		if not env.terminated {
7486	7489		for i in start..env.len {
7487	7490		if linearBindingAvailable(env, i) {
7488		-	let sym = env.symbols[i] else panic "finishLinearScope: missing symbol";
	7491	+	let sym = env.symbols[i];
7489	7492		let case SymbolData::Value { type: ty, .. } = sym.data
7490	7493		else panic "finishLinearScope: expected value symbol";
7491	7494		if isLinear(ty) {
7492	7495		throw emitError(
7493	7496		checker.resolver,

7542	7545		}
7543	7546		assert left.len == right.len, "joinLinearBranches: scope mismatch";
7544	7547		let mut result = left;
7545	7548		for i in 0..left.len {
7546	7549		if linearBindingAvailable(&left, i) <> linearBindingAvailable(&right, i) {
7547		-	let sym = left.symbols[i] else panic "joinLinearBranches: missing symbol";
	7550	+	let sym = left.symbols[i];
7548	7551		let case SymbolData::Value { type: ty, .. } = sym.data
7549	7552		else panic "joinLinearBranches: expected value symbol";
7550	7553		if isLinear(ty) {
7551	7554		throw emitError(
7552	7555		checker.resolver,

7565	7568		checker: *mut LinearChecker,
7566	7569		env: *mut LinearEnv,
7567	7570		) throws (ResolveError) {
7568	7571		for i in 0..env.len {
7569	7572		if linearBindingAvailable(env, i) {
7570		-	let sym = env.symbols[i] else panic "finishLinearExit: missing symbol";
	7573	+	let sym = env.symbols[i];
7571	7574		let case SymbolData::Value { type: ty, .. } = sym.data
7572	7575		else panic "finishLinearExit: expected value symbol";
7573	7576		if isLinear(ty) {
7574	7577		throw emitError(
7575	7578		checker.resolver,

7642	7645		}
7643	7646		try finishLinearScope(checker, env, start);
7644	7647		}
7645	7648
7646	7649		/// Push a repeated-control-flow boundary.
	7650	+	/// Initialize all loop state at this depth before increasing `loopDepth`.
7647	7651		fn enterLinearLoop(checker: mut LinearChecker, env: LinearEnv) {
7648	7652		assert checker.loopDepth < MAX_LINEAR_LOOP_DEPTH, "linear loop nesting overflow";
7649	7653		let depth = checker.loopDepth;
7650	7654		set checker.loopMarks[depth] = env.len;
7651	7655		set checker.loopAvailable[depth] = env.available;

7669	7673		let mark = checker.loopMarks[depth];
7670	7674		let entryAvailable = checker.loopAvailable[depth];
7671	7675		for i in 0..mark {
7672	7676		let bit = (1 as u64) << (i as u64);
7673	7677		if (env.available & bit) <> (entryAvailable & bit) {
7674		-	let sym = env.symbols[i] else panic "checkLinearLoopBackEdge: missing symbol";
	7678	+	let sym = env.symbols[i];
7675	7679		throw emitError(
7676	7680		checker.resolver,
7677	7681		node,
7678	7682		ErrorKind::LinearBranchMismatch(sym.name),
7679	7683		);

7701	7705		if checker.loopHasNaturalExit[depth] or checker.loopBreakSeen[depth] {
7702	7706		let expected = checker.loopExitAvailable[depth];
7703	7707		for i in 0..mark {
7704	7708		let bit = (1 as u64) << (i as u64);
7705	7709		if (env.available & bit) <> (expected & bit) {
7706		-	let sym = env.symbols[i] else panic "checkLinearLoopBreak: missing symbol";
	7710	+	let sym = env.symbols[i];
7707	7711		throw emitError(
7708	7712		checker.resolver,
7709	7713		node,
7710	7714		ErrorKind::LinearBranchMismatch(sym.name),
7711	7715		);

7785	7789		}
7786	7790		case ast::ProngArm::Else => {}
7787	7791		}
7788	7792		if prong.guard <> nil {
7789	7793		for i in bindingsStart..branch.len {
7790		-	let sym = branch.symbols[i] else panic "checkLinearMatch: missing symbol";
	7794	+	let sym = branch.symbols[i];
7791	7795		let case SymbolData::Value { type: ty, .. } = sym.data
7792	7796		else panic "checkLinearMatch: expected value symbol";
7793	7797		if isLinear(ty) {
7794	7798		throw emitError(checker.resolver, prongNode, ErrorKind::LinearDiscard);
7795	7799		}

8376	8380		params: mut [ast::Node],
8377	8381		body: *ast::Node,
8378	8382		) throws (ResolveError) {
8379	8383		let mut checker = LinearChecker {
8380	8384		resolver: self,
8381		-	loopMarks: [0; MAX_LINEAR_LOOP_DEPTH],
8382		-	loopAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
8383		-	loopExitAvailable: [0; MAX_LINEAR_LOOP_DEPTH],
8384		-	loopHasNaturalExit: [false; MAX_LINEAR_LOOP_DEPTH],
8385		-	loopBreakSeen: [false; MAX_LINEAR_LOOP_DEPTH],
	8385	+	loopMarks: undefined,
	8386	+	loopAvailable: undefined,
	8387	+	loopExitAvailable: undefined,
	8388	+	loopHasNaturalExit: undefined,
	8389	+	loopBreakSeen: undefined,
8386	8390		loopDepth: 0,
8387	8391		};
8388	8392		let mut env = LinearEnv {
8389		-	symbols: [nil; MAX_LINEAR_BINDINGS],
	8393	+	symbols: undefined,
8390	8394		available: 0,
8391	8395		len: 0,
8392	8396		terminated: false,
8393	8397		};
8394	8398		if let receiverNode = receiver {