@RAD_BIN="$(RAD_BIN)" $(BIN_TEST_RUN)

export mod graph;

//! Construction authority for region-bound graphs with stable node identities.

//!

//! Typed opaque wrappers keep their payloads and links private. They check all

//! linked nodes before writing a payload, then mark the node complete. Payload

//! writes require the builder. Frozen readers require the published graph.

@test mod tests;

use std::lang::alloc;

/// Largest node count represented by a graph.

constant MAX_NODE_COUNT: u32 = 0xffffffff;

/// Exclusive authority to construct one graph.

export opaque record Builder: 'g {

    /// Unique identity shared by this graph's nodes.

    owner: &'g u8,

    /// Number of reserved node identities.

    count: u32,

    /// Number of nodes whose payloads are not complete.

    pending: u32,

}

/// Stable identity retained by a typed node wrapper.

export opaque record Node: 'g + Copy {

    /// Identity of the graph that owns this node.

    owner: &'g u8,

    /// Completion state controlled by the graph builder.

    initialized: &'g cell bool,

}

/// Shared authority to read a completed graph.

export opaque record Frozen: 'g + Copy {

    /// Identity of the graph that owns all published nodes.

    owner: &'g u8,

    /// Number of published node identities.

    count: u32,

}

/// Invalid access through a graph capability.

export union Error: Copy {

    /// The node belongs to a different graph.

    ForeignNode,

}

/// A graph that cannot yet be published.

export union FreezeError: 'g {

    /// Construction authority for the graph that still has pending nodes.

    Incomplete(Builder 'g),

}

/// Create an empty graph whose identity lives in the allocation session.

export fn new 'g (storage: &Session 'g) -> Builder 'g throws (alloc::AllocError) {

    let owner = try storage.new(0 as u8);

    return Builder 'g { owner: &*owner, count: 0, pending: 0 };

}

/// Reserve a stable node identity before its typed payload is complete.

/// Allocation failure leaves the builder unchanged.

export fn reserve 'g (builder: &mut Builder 'g, storage: &Session 'g) -> Node 'g

    throws (alloc::AllocError)

{

    if builder.count == MAX_NODE_COUNT {

        throw alloc::AllocError::OutOfMemory;

    }

    let initialized = try storage.new(false);

    let result = Node 'g { owner: builder.owner, initialized: &cell *initialized };

    set builder.count += 1;

    set builder.pending += 1;

    return result;

}

/// Check a node before reading or writing its typed payload during construction.

/// Typed wrappers must also check every node linked by a payload write.

export fn check 'g (builder: &Builder 'g, node: Node 'g) throws (Error) {

    if builder.owner <> node.owner {

        throw Error::ForeignNode;

    }

}

/// Mark a node complete after its typed payload and links are initialized.

/// Completing an initialized node leaves the pending count unchanged.

export fn complete 'g (builder: &mut Builder 'g, node: Node 'g) throws (Error) {

    try check(builder, node);

    if not *node.initialized {

        assert builder.pending > 0;

        set *node.initialized = true;

        set builder.pending -= 1;

    }

}

/// Return the number of reserved nodes that still need initialization.

export fn pending 'g (builder: &Builder 'g) -> u32 {

    return builder.pending;

}

/// Consume construction authority and publish the completed graph.

/// An incomplete graph returns its builder in the error for recovery.

export fn freeze 'g (builder: Builder 'g) -> Frozen 'g throws (FreezeError 'g) {

    if builder.pending <> 0 {

        throw FreezeError 'g::Incomplete(builder);

    }

    let case Builder 'g { owner, count, pending: _ } = builder

        else panic "freeze: invalid builder";

    return Frozen 'g { owner, count };

}

/// Check a node before reading its typed payload through a frozen graph.

export fn checkFrozen 'g (graph: &Frozen 'g, node: Node 'g) throws (Error) {

    if graph.owner <> node.owner {

        throw Error::ForeignNode;

    }

    assert *node.initialized;

}

/// Return the number of nodes in a frozen graph.

export fn len 'g (graph: &Frozen 'g) -> u32 {

    return graph.count;

}

//! Graph ownership, publication, and failure recovery tests.

use std::testing;

use std::lang::alloc;

/// Empty graphs can be published without node allocations.

@test fn testEmptyGraph() throws (testing::TestError) {

    static DATA: [u8; 64] = [0; 64];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as storage in {

        let builder = try! super::new(&storage);

        assert super::pending(&builder) == 0;

        let frozen = try! super::freeze(builder);

        assert super::len(&frozen) == 0;

    }

}

/// Node identities and completion counts survive repeated completion and freeze.

@test fn testNodeCompletion() throws (testing::TestError) {

    for count in [1 as u32, 2, 8, 64] {

        static DATA: [u8; 1024] = [0; 1024];

        let mut arena = alloc::new(&mut DATA[..]);

        use arena as storage in {

            let mut builder = try! super::new(&storage);

            let first = try! super::reserve(&mut builder, &storage);

            let mut nodes: [super::Node 'storage; 64] = [first; 64];

            for i in 1..count {

                set nodes[i] = try! super::reserve(&mut builder, &storage);

                for j in 0..i {

                    assert nodes[i] <> nodes[j];

                }

            }

            assert super::pending(&builder) == count;

            for i in 0..count {

                try! super::check(&builder, nodes[i]);

                try! super::complete(&mut builder, nodes[i]);

                assert super::pending(&builder) == count - i - 1;

                try! super::complete(&mut builder, nodes[i]);

                assert super::pending(&builder) == count - i - 1;

            }

            let frozen = try! super::freeze(builder);

            assert super::len(&frozen) == count;

            assert nodes[0] == first;

            for i in 0..count {

                try! super::checkFrozen(&frozen, nodes[i]);

            }

        }

    }

}

/// Builders in one session have separate ownership and completion authority.

@test fn testForeignNode() throws (testing::TestError) {

    static DATA: [u8; 128] = [0; 128];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as storage in {

        let mut first = try! super::new(&storage);

        let mut second = try! super::new(&storage);

        let a = try! super::reserve(&mut first, &storage);

        let b = try! super::reserve(&mut second, &storage);

        let mut rejected = false;

        try super::complete(&mut first, b) catch error {

            assert error == super::Error::ForeignNode;

            set rejected = true;

        };

        assert rejected;

        assert super::pending(&first) == 1;

        assert super::pending(&second) == 1;

        try! super::complete(&mut first, a);

        let frozen = try! super::freeze(first);

        set rejected = false;

        try super::checkFrozen(&frozen, b) catch error {

            assert error == super::Error::ForeignNode;

            set rejected = true;

        };

        assert rejected;

        try! super::complete(&mut second, b);

        let other = try! super::freeze(second);

        try! super::checkFrozen(&other, b);

    }

}

/// An incomplete freeze returns the sole builder for completion and retry.

@test fn testIncompleteFreezeRecovery() throws (testing::TestError) {

    static DATA: [u8; 128] = [0; 128];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as storage in {

        let mut builder = try! super::new(&storage);

        let first = try! super::reserve(&mut builder, &storage);

        let second = try! super::reserve(&mut builder, &storage);

        try! super::complete(&mut builder, first);

        try super::freeze(builder) catch error {

            let case super::FreezeError 'storage::Incomplete(recovered) = error else panic;

            let mut retry = recovered;

            assert super::pending(&retry) == 1;

            try! super::complete(&mut retry, second);

            let frozen = try! super::freeze(retry);

            assert super::len(&frozen) == 2;

            try! super::checkFrozen(&frozen, first);

            try! super::checkFrozen(&frozen, second);

            return;

        };

        throw testing::TestError::Failed;

    }

}

/// Exhausted identity storage does not add incomplete nodes to the builder.

@test fn testAllocationFailure() throws (testing::TestError) {

    for capacity in 0..9 {

        static DATA: [u8; 16] = [0; 16];

        let mut arena = alloc::new(&mut DATA[..capacity]);

        use arena as storage in {

            if let created = try? super::new(&storage) {

                let mut builder = created;

                let mut count: u32 = 0;

                while let node = try? super::reserve(&mut builder, &storage) {

                    try! super::complete(&mut builder, node);

                    set count += 1;

                }

                assert super::pending(&builder) == 0;

                let frozen = try! super::freeze(builder);

                assert super::len(&frozen) == count;

                assert count == capacity - 1;

            } else {

                assert capacity == 0;

            }

        }

        assert alloc::used(&arena) == capacity;

    }

}

export mod flow;

//! Owned control-flow topology for dataflow analysis.

use std::graph;

use std::lang::alloc;

use std::lang::il;

/// Largest successor count represented by a slice length.

constant MAX_SUCCESSORS: u32 = 0xffffffff;

/// Stable block identity and private successor storage.

export opaque record Block: 's + Copy {

    /// Graph capability identity.

    token: graph::Node 's,

    /// Block position in the function's dataflow tables.

    index: u32,

    /// Successors published when construction is complete.

    links: &'s cell &'s [Block 's],

}

/// Immutable topology whose storage belongs to the analysis session.

export opaque record Flow: 's + Copy {

    /// Shared authority for every block in the topology.

    frozen: graph::Frozen 's,

    /// Stable block handles in function order.

    blocks: &'s [Block 's],

}

/// Copy successor topology from valid IL into session-owned storage.

/// Instruction and switch tables must remain valid during this call.

export unsafe fn snapshot 's (blocks: &[il::Block], storage: &Session 's)

    -> Flow 's throws (alloc::AllocError)

{

    let mut builder = try graph::new(storage);

    let none: [Block 's; 0] = [];

    let empty: &'s [Block 's] = try storage.copy(&none[..]);

    if blocks.len == 0 {

        return Flow 's { frozen: try! graph::freeze(builder), blocks: empty };

    }

    let first = try reserve(&mut builder, 0, empty, storage);

    let entries = try storage.fill(first, blocks.len);

    for i in 1..blocks.len {

        set entries[i] = try reserve(&mut builder, i, empty, storage);

    }

    for block, i in blocks {

        let instructions: &[il::Instr] = block.instrs;

        let mut links = empty;

        if instructions.len > 0 {

            let term = &instructions[instructions.len - 1];

            match term {

                case il::Instr::Jmp { target, .. } => {

                    set links = try storage.fill(entries[*target], 1);

                },

                case il::Instr::Br { thenTarget, elseTarget, .. } => {

                    let targets = try storage.fill(entries[*thenTarget], 2);

                    set targets[1] = entries[*elseTarget];

                    set links = &targets[..];

                },

                case il::Instr::Switch { defaultTarget, cases, .. } => {

                    let cases: &[il::SwitchCase] = *cases;

                    if cases.len == MAX_SUCCESSORS {

                        throw alloc::AllocError::OutOfMemory;

                    }

                    let targets = try storage.fill(entries[*defaultTarget], cases.len + 1);

                    for item, j in cases {

                        set targets[j + 1] = entries[item.target];

                    }

                    set links = &targets[..];

                },

                else => {},

            }

        }

        try! define(&mut builder, entries[i], links);

    }

    return Flow 's { frozen: try! graph::freeze(builder), blocks: &entries[..] };

}

/// Reserve a block before its outgoing links are known.

fn reserve 's (builder: &mut graph::Builder 's, index: u32, empty: &'s [Block 's], storage: &Session 's)

    -> Block 's throws (alloc::AllocError)

{

    let links = try storage.new(empty);

    let token = try graph::reserve(builder, storage);

    return Block 's { token, index, links: &cell *links };

}

/// Complete a block after all successors have been checked.

fn define 's (builder: &mut graph::Builder 's, block: Block 's, links: &'s [Block 's])

    throws (graph::Error)

{

    try graph::check(builder, block.token);

    for successor in links {

        try graph::check(builder, successor.token);

    }

    set *block.links = links;

    try graph::complete(builder, block.token);

}

/// Borrow the successors of a published block.

export fn successors 's (flow: &Flow 's, index: u32) -> &'s [Block 's] {

    let block = flow.blocks[index];

    try! graph::checkFrozen(&flow.frozen, block.token);

    return *block.links;

}

/// Return the dataflow table position retained by a block identity.

export fn index 's (block: Block 's) -> u32 {

    return block.index;

}

use super::flow;

    unsafe {

        let topology = try flow::snapshot(blocks, storage);

        propagateLiveness(&topology, blockCount, liveIn, liveOut, defs, uses, words);

    }

fn propagateLiveness 'scratch (

    topology: &flow::Flow 'scratch,

    blockCount: u32,

        let mut b = blockCount;

            for successor in flow::successors(topology, b) {

                unionBlockLiveIn(flow::index(successor), liveIn, words, &mut liveOut[b * words..(b + 1) * words]);

use std::lang::gen::regalloc::flow;

/// Frozen topology owns successor tables and preserves cyclic block identities.

@test unsafe fn testOwnedFlowSnapshot() throws (testing::TestError) {

    let mut cases = [il::SwitchCase { value: 1, target: 1, args: &mut [] }];

    let mut first = [il::Instr::Switch { val: il::Val::Imm(0), defaultTarget: 0,

        defaultArgs: &mut [], cases: &mut cases[..] }];

    let mut second = [il::Instr::Jmp { target: 0, args: &mut [] }];

    let blocks = [block("first", &mut first[..]), block("second", &mut second[..])];

    static DATA: [u8; 2048] = [0; 2048];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as storage in {

        let frozen = try! flow::snapshot(&blocks[..], &storage);

        set cases[0].target = 0;

        set first[0] = il::Instr::Ret { val: il::Val::Imm(0) };

        set second[0] = il::Instr::Ret { val: il::Val::Imm(0) };

        let successors = flow::successors(&frozen, 0);

        assert successors.len == 2;

        assert flow::index(successors[0]) == 0;

        assert flow::index(successors[1]) == 1;

        let back = flow::successors(&frozen, 1);

        assert back.len == 1 and back[0] == successors[0];

    }

    alloc::reset(&mut arena);

    assert alloc::used(&arena) == 0;

}

/// Every incomplete allocation stage reports failure and permits arena disposal.

@test unsafe fn testFlowAllocationFailure() throws (testing::TestError) {

    let mut instructions = [il::Instr::Jmp { target: 0, args: &mut [] }];

    let blocks = [block("loop", &mut instructions[..])];

    let mut succeeded = false;

    for capacity in 0..257 {

        static DATA: [u8; 256] = [0; 256];

        let mut arena = alloc::new(&mut DATA[..capacity]);

        use arena as storage in {

            if let frozen = try? flow::snapshot(&blocks[..], &storage) {

                let links = flow::successors(&frozen, 0);

                assert links.len == 1 and flow::index(links[0]) == 0;

                set succeeded = true;

            } else {

                assert not succeeded;

            }

        }

        alloc::reset(&mut arena);

        assert alloc::used(&arena) == 0;

    }

    assert succeeded;

}

55199dd625f01384eae1694dba6d6c286292a12c466e40b968e8326bdf78f33e

lib/std/graph.rad

lib/std/lang/gen/regalloc/flow.rad

lib/std/graph/tests.rad

#!/bin/sh

# Require semantic rejection of one source fixture with its expected diagnostic.

set -eu

source=$1

expected=$(sed -n 's|^//! rejects: ||p' "$source")

test -n "$expected"

work=$(mktemp -d)

trap 'rm -rf "$work"' EXIT HUP INT TERM

set --

if grep -q '^//! session-support$' "$source"; then

    set -- -pkg std

    while IFS= read -r source_module; do

        set -- "$@" -mod "$source_module"

    done < test/support/std.lib

fi

set -- "$@" -pkg test -mod "$source" -entry test -dump il

for source_module in "${source%.rad}"/*.rad; do

    if [ -f "$source_module" ]; then

        set -- "$@" -mod "$source_module"

    fi

done

status=0

timeout 10 "${RAD_EMULATOR:-emulator}" -memory-size=385024 -data-size=348160 \

    -stack-size=1024 -run "${RAD_BIN:-bin/radiance.rv64.dev}" "$@" \

    >"$work/compiler.log" 2>&1 || status=$?

if [ "$status" -ne 1 ] || ! grep -F "$source:" "$work/compiler.log" | grep -Fq "error: $expected"; then

    cat "$work/compiler.log"

    echo "error: expected semantic rejection: $expected (exit $status)"

    exit 1

fi

#   - If `//! rejects: TEXT` appears, the compiler must reject the source with

#     that diagnostic. Crashes and timeouts are failures.

  if grep -q '^//! rejects: ' "$test"; then

    echo -n "test $test rejection ... "

    if sh test/reject "$test"; then

      echo "ok"

      passed=$((passed + 1))

    else

      echo "FAILED"

      failed=$((failed + 1))

    fi

    continue

  fi

test/support/std/graph.rad

export mod graph;

../../../lib/std/graph.rad

//! returns: 0

//! session-support

//! Graph construction authority is consumed before shared publication.

use std::graph;

use std::lang::alloc;

/// Complete two reserved identities and retain them through publication.

@default fn main() -> u32 {

    static DATA: [u8; 1024] = [0; 1024];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as storage in {

        let mut builder = try! graph::new(&storage);

        let first = try! graph::reserve(&mut builder, &storage);

        let second = try! graph::reserve(&mut builder, &storage);

        assert first <> second;

        assert graph::pending(&builder) == 2;

        try! graph::complete(&mut builder, first);

        try! graph::complete(&mut builder, second);

        let frozen = try! graph::freeze(builder);

        try! graph::checkFrozen(&frozen, first);

        try! graph::checkFrozen(&frozen, second);

        assert graph::len(&frozen) == 2;

    }

    return 0;

}

//! returns: 0

//! session-support

//! Typed cyclic graph construction and publication.

use std::graph;

use std::lang::alloc;

mod model;

/// Construct forward references, reject foreign links, and publish a cycle.

@default fn main() -> u32 {

    static DATA: [u8; 4096] = [0; 4096];

    let mut arena = alloc::new(&mut DATA[..]);

    use arena as storage in {

        let mut builder = try! graph::new(&storage);

        let first = try! model::reserve(&mut builder, &storage);

        let second = try! model::reserve(&mut builder, &storage);

        let third = try! model::reserve(&mut builder, &storage);

        let isolated = try! model::reserve(&mut builder, &storage);

        let mut other = try! graph::new(&storage);

        let foreign = try! model::reserve(&mut other, &storage);

        let mut rejected = false;

        try model::define(&mut builder, first, 99, foreign) catch error {

            assert error == graph::Error::ForeignNode;

            set rejected = true;

        };

        assert rejected;

        assert graph::pending(&builder) == 4;

        try! model::define(&mut builder, first, 10, second);

        try! model::define(&mut builder, second, 20, third);

        try! model::define(&mut builder, third, 30, first);

        try! model::define(&mut builder, isolated, 40, isolated);

        try! model::define(&mut builder, first, 11, second);

        let frozen = try! graph::freeze(builder);

        assert graph::len(&frozen) == 4;

        let a = try! model::read(&frozen, first);

        let b = try! model::read(&frozen, a.next);

        let c = try! model::read(&frozen, b.next);

        assert a.value + b.value + c.value == 61;

        assert c.next == first;

        let d = try! model::read(&frozen, isolated);

        assert d.value == 40 and d.next == isolated;

        set rejected = false;

        try model::read(&frozen, foreign) catch error {

            assert error == graph::Error::ForeignNode;

            set rejected = true;

        };

        assert rejected;

        try! model::define(&mut other, foreign, 50, foreign);

        let otherFrozen = try! graph::freeze(other);

        assert (try! model::read(&otherFrozen, foreign)).value == 50;

    }

    return 0;

}

//! Typed definitions whose links require graph construction authority.

use std::graph;

use std::lang::alloc;

/// Definition payload and its direct successor.

export record Value: 'g + Copy {

    /// Number stored by this definition.

    value: u32,

    /// Next definition in the graph.

    next: Definition 'g,

}

/// Initialization state of a definition slot.

union State: 'g + Copy {

    /// Reserved forward reference.

    Pending,

    /// Complete payload with a checked outgoing link.

    Ready(Value 'g),

}

/// Stable typed pointer to a definition controlled by one graph builder.

export opaque record Definition: 'g + Copy {

    /// Private identity used to check graph authority.

    token: graph::Node 'g,

    /// Payload that only the defining module can change.

    contents: &'g cell State 'g,

}

/// Allocate a forward reference without publishing an incomplete payload.

export fn reserve 'g (builder: &mut graph::Builder 'g, storage: &Session 'g)

    -> Definition 'g throws (alloc::AllocError)

{

    let contents = try storage.new(State 'g::Pending);

    let token = try graph::reserve(builder, storage);

    return Definition 'g { token, contents: &cell *contents };

}

/// Write a complete payload after checking the node and its outgoing link.

export fn define 'g (builder: &mut graph::Builder 'g, node: Definition 'g,

    value: u32, next: Definition 'g) throws (graph::Error)

{

    try graph::check(builder, node.token);

    try graph::check(builder, next.token);

    set *node.contents = State 'g::Ready(Value 'g { value, next });

    try graph::complete(builder, node.token);

}

/// Read a complete definition through its graph's shared authority.

export fn read 'g (frozen: &graph::Frozen 'g, node: Definition 'g)

    -> Value 'g throws (graph::Error)

{

    try graph::checkFrozen(frozen, node.token);

    let case State 'g::Ready(value) = *node.contents

        else panic "read: incomplete definition";

    return value;

}

//! session-support

//! rejects: conflicting borrow of 'builder'

use std::graph;

/// A live construction borrow prevents publication.

fn reuse 'g (builder: graph::Builder 'g) {

    let borrowed = &builder;