/**
 * Copyright (c) 2004-2005, Regents of the University of California
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * Redistributions of source code must retain the above copyright notice,
 * this list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution.
 *
 * Neither the name of the University of California, Los Angeles nor the
 * names of its contributors may be used to endorse or promote products
 * derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package avrora.core;

import java.util.*;

import avrora.core.ControlFlowGraph.Block;

/**
 * The <code>ProcedureMap</code> class represents a mapping from basic blocks to the procedures that contain
 * them. Built by the <code>ProcedureMapBuilder</code> class and accessible through the
 * <code>ControlFlowGraph.getProcedureMap()</code>, the <code>ProcedureMap</code>, the mapping is built by
 * first recognized static call sites and marking their target basic blocks as procedure entry points. Those
 * entrypoints are propagated through the control flow graph to all reachable basic blocks (ignoring call
 * edges). If a basic block is reachable through more than one procedure entry, it is considered shared.
 * <p/>
 * The result is a conservative approximation of which basic blocks are in which procedure. Given a basic
 * block, this class can look up the basic block which represents the entrypoint of that procedure. Also,
 * given the entrypoint of a procedure, the class can return a collection of the basic blocks that are
 * reachable from that entrypoint.
 * <p/>
 * Interrupt handlers are not considered the entrypoints of procedures.
 *
 * @author Ben L. Titzer
 * @see Program
 * @see ControlFlowGraph
 */
public class ProcedureMap {

    protected final HashSet<ControlFlowGraph.Block> entryPoints;
    protected final HashMap<ControlFlowGraph.Block, Object> entryMap;
    protected final HashMap<ControlFlowGraph.Block, Collection<Block>> procMap;

    ProcedureMap(HashSet<Block> ep, HashMap<Block, Object> em, HashMap<Block, Collection<Block>> pm) {
        entryPoints = ep;
        entryMap = em;
        procMap = pm;
    }

    /**
     * The <code>isInAnyProcedure()</code> method queries whether the specified basic block is reachable from
     * any procedure entry point in the program.
     *
     * @param b the basic block to query
     * @return true if this basic block is in one or more procedure; false otherwise
     */
    public boolean isInAnyProcedure(ControlFlowGraph.Block b) {
        return entryMap.get(b) != null;
    }

    /**
     * The <code>isSharedBetweenProcedures()</code> method queries whether the specified basic block is
     * reachable from more than one procedure entrypoint.
     *
     * @param b the basic block to query
     * @return true if this basic block is reachable from more than one procedure; false otherwise
     */
    public boolean isSharedBetweenProcedures(ControlFlowGraph.Block b) {
        Object o = entryMap.get(b);
        return o != null && !(o instanceof ControlFlowGraph.Block);
    }

    /**
     * The <code>getProcedureContaining()</code> method looks up the entrypoint of the procedure that contains
     * this basic block. If the block is not in any procedure, or if the block is shared by multiple
     * procedures, then this method returns null.
     *
     * @param b the basic block to find the procedure of
     * @return a reference to the unique <code>ControlFlowGraph.Block</code> instance that is the entrypoint
     *         of the procedure containing the specified basic block; null otherwise
     */
    public ControlFlowGraph.Block getProcedureContaining(ControlFlowGraph.Block b) {
        Object o = entryMap.get(b);
        if (o instanceof ControlFlowGraph.Block)
            return (ControlFlowGraph.Block)o;
        else
            return null;
    }

    /**
     * The <code>getProcedureBlocks()</code> method returns the collection of basic blocks contained in the
     * procedure with the specified entrypoint. If the block passed is not the entrypoint of any procedure,
     * this method will return null.
     *
     * @param entry the basic block representing the entrypoint of the procedure
     * @return a collection of the basic blocks contained in the procedure with the specified entrypoint
     */
    public Collection<Block> getProcedureBlocks(ControlFlowGraph.Block entry) {
        return procMap.get(entry);
    }

    /**
     * The <code>getProcedureEntrypoints()</code> method returns a collection of basic blocks that are
     * entrypoints of procedures in the control flow graph.
     *
     * @return a collection of basic blocks that are entrypoints to procedures
     */
    public Collection<ControlFlowGraph.Block> getProcedureEntrypoints() {
        return entryPoints;
    }
}
