/*
 * (c) 2022 Petr Ročkai <code@fixp.eu>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

#pragma once
#include "types.hpp"
#include <vector>

/* This file provides a basic read-only access to a ‹bast› program. The program
 * is encoded as a list of basic blocks, where each block has a «label», a list
 * of «instructions» and a list of «successors». Physically, the program is
 * stored as a sequence of opcodes, where an opcode can be:
 *
 *  • a «label» (‹block_label›), which identifies the beginning of a basic
 *    block, and is also used as the identifier in successor lists,
 *  • «instructions» which encode the operations to be performed on the operand
 *    stack by that given basic block,
 *  • «successors» (‹block_next›) which encode control flow (which is always
 *    direct and unconditional).
 *
 * Each basic block begins with a label, followed by zero or more instructions,
 * followed by zero or more successors. The basic block ends at the next label.
 * Instructions are not allowed between ‹block_next› and ‹block_label›.
 *
 * Labels are numbers and form a contiguous sequence (they can be directly used
 * as indices into the list of blocks). */

namespace bast
{
    struct program;

    /* Helper class to indicate a span of indices (used to delimit basic
     * blocks). */

    struct span
    {
        int begin, end;
        span( int s, int e ) : begin( s ), end( e ) {}
    };

    /* The ‹block› class is a view into the program, restricted to a single
     * block. Iterating a ‹block› yields opcodes which are part of the block
     * (excluding the label, but including successors). */

    struct block
    {
        struct iterator;

        iterator begin() const;
        iterator end() const;

    private:
        friend program;
        const program &p;
        span s;

        block( const program &p, span s ) : p( p ), s( s ) {}
    };

    /* Programs are stored in memory as a compact sequence of opcodes + a cache
     * of basic block boundaries so that jumps can be resolved in constant
     * time. Program rewriting is done by constructing a new program (see
     * ‹builder›) – mutation is not supported.
     *
     * The entry point of a program is always at label 0. Linear iteration
     * through blocks is not supported – the only way to work with a program is
     * to follow its structure.
     *
     * TBD We might want to cache the number of successors and give ‹block› a
     * constant-time interface to skip instructions and only iterate the
     * successor list. */

    struct program
    {
        bast::block block( types::label id ) const
        {
            return bast::block( *this, label[ id.v ] );
        }

        std::vector< word > code;
        std::vector< span > label;
    };

    struct block::iterator /* boring */
    {
        iterator( const program &p, int b, int e ) : p( p ), s( b, e ) {}
        word operator*() { return p.code[ s.begin ]; }
        iterator &operator++() { ++ s.begin; return *this; }
        bool operator==( iterator o ) const { return s.begin == o.s.begin; }
        bool operator!=( iterator o ) const { return !( *this == o ); }

    private:
        const program &p;
        span s;
    };

    block::iterator block::begin() const { return iterator( p, s.begin, s.end ); }
    block::iterator block::end()   const { return iterator( p, s.end,   s.end ); }
}