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

use std::graph;

use std::lang::alloc;

use std::lang::il::published;

/// Zero-state owner for authority over one flow topology.

export record Permission {}

/// Stable block identity and private successor storage.

export opaque record Block: 'storage + 'permission + Copy {

    /// Graph capability identity.

    token: graph::Node 'storage,

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

    index: u32,

    /// Successors published when construction is complete.

    links: &'storage cell 'permission &'storage [Block 'storage 'permission],

}

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

export opaque record Flow: 'storage + 'permission + Copy {

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

    frozen: graph::Frozen 'storage,

    /// Stable block handles in function order.

    blocks: &'storage [Block 'storage 'permission],

}

/// Copy published successor topology into session-owned graph storage.

export fn snapshot 'input 'storage 'permission (

    blocks: &[published::Block 'input],

    storage: &Session 'storage,

    permission: &'permission mut Permission,

) -> Flow 'storage 'permission throws (alloc::AllocError) {

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

    let none: [Block 'storage 'permission; 0] = [];

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

    if blocks.len == 0 {

        return Flow 'storage 'permission {

            frozen: try! graph::freeze(builder),

            blocks: empty,

        };

    }

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

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

    for i in 1..blocks.len {

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

    }

    for block, i in blocks {

        let instructions = block.instructions;

        let mut links = empty;

        if instructions.len > 0 {

            let targets = published::successors(&instructions[instructions.len - 1]);

            if targets.len > 0 {

                let successors = try storage.fill(entries[targets[0]], targets.len);

                for j in 1..targets.len {

                    set successors[j] = entries[targets[j]];

                }

                set links = &successors[..];

            }

        }

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

    }

    return Flow 'storage 'permission {

        frozen: try! graph::freeze(builder),

        blocks: &entries[..],

    };

}

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

fn reserve 'storage 'permission (

    builder: &mut graph::Builder 'storage,

    index: u32,

    empty: &'storage [Block 'storage 'permission],

    storage: &Session 'storage,

    permission: &'permission mut Permission,

) -> Block 'storage 'permission throws (alloc::AllocError) {

    let links = try storage.new(empty);

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

    return Block 'storage 'permission {

        token,

        index,

        links: &cell 'permission *links,

    };

}

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

fn define 'storage 'permission (

    builder: &mut graph::Builder 'storage,

    block: Block 'storage 'permission,

    links: &'storage [Block 'storage 'permission],

    permission: &'permission mut Permission,

) 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 'storage 'permission (

    flow: &Flow 'storage 'permission,

    index: u32,

    permission: &'permission mut Permission,

) -> &'storage [Block 'storage 'permission] {

    let block = flow.blocks[index];

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

    let authority: 'loan = &*permission, links = &*block.links in {

        return *links;

    }

}

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

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

    return block.index;

}