#ifndef _CFG_H_
#define _CFG_H_

#include <cassert>
#include <iosfwd>
#include <set>
#include <vector>
#include "AST.h"
#include "InstancePool.h"
#include "llist.h"
#include "code-util.h"
#include "bitset.h"
#include "AliasInfos.h"

class CfgNode;

typedef set< CfgNode * > CFGset;

// a CFGExtent is a struct-like class that represents a subgraph of the CFG by 
// maintaining a pointer to an entry and exit node of some subgraph of a CFG
class CfgExtent {
public:
  CfgNode *entry;
  CfgNode *exit;
};

extern bool contains(const CFGset *l, const CfgNode *t);
extern CFGset *adjoin(CFGset *s, const CfgNode *t);

// EXPRESSION-LEVEL CFG NODES
// There are one of these nodes per AST node. They arrange the AST nodes
// into execution order. This usually means postorder. The CFG for
// an IfStmtNode, for example, will contain the test, then the true and false
// clauses down different branches, and then the IfStmtNode itself. The fact
// that the IfStmtNode itself gets executed last may seem surprising, but the
// IfStmtNode doesn't actually mean anything; it is its subexpressions that
// represent real computation. See titanium-doc/cfg.txt for all the details.

class CfgNode {
  // typedef map< TreeNode *, llist< CfgNode * > * > map_tree_to_CfgNodelist;
protected:
  TreeNode *ast_node;

  llist<CfgNode *> *_succ;
  llist<CfgNode *> *_pred;
  int visited;

  /* Set of predecessors of this which might consider
     this to be a non-standard exit. */
  CFGset *NSE;

  // map_tree_to_CfgNodelist *m;

public:
  int numPred;
  int numSucc;
  Bblock *bblock;

private:
  /* An integer ID intended to be unique among valid CfgNodes at any
   * given time. */
  int _nodeId;
  /* Current mapping of CfgNode IDs to CfgNodes. validNodes[0] is 
   * undefined, so that 0 can serve as the "null CFG node." */
  static vector<CfgNode*> validNodes;

  bool straightLineCodeToOutside(const CFGset *l) const;
  bool straightLineCodeToOutside(const CFGset *l, CFGset *seen) const;
  llist<CfgNode *> *filterNSE(const CFGset *l, bool *ignoredAny);

public:
  CfgNode (TreeNode *node);

  ~CfgNode() {
    delAllSucc();
    delAllPred();
    delete NSE;
  }
  void *operator new(size_t);      
  void operator delete(void *, size_t);

  /** Reset unique id assignment, so that subsequent CFG nodes start
   *  at nodeId() 1.  Allows us to keep the range of integers
   *  corresponding to CFG nodes within reasonable bounds. */
  static void reset ();

  /** The current maximum nodeId() value for a valid CFG node. */
  static int maxId ();

  /** The currently valid CFG node whose nodeId is ID. */
  static CfgNode* node (int id);

  TreeNode *astNode() const { return ast_node; }
  void nodeStatus(int v) { visited = v; }
  int nodeStatus() const { return visited; }
  int nodeId() const { return _nodeId; }
  void addSucc(CfgNode *n) { numSucc++; _succ = cons(n, _succ); }
  void addPred(CfgNode *n) { numPred++; _pred = cons(n, _pred); }
  void addPredNSE(CfgNode *n) { addPred(n); markNSE(n); }
  void markNSE(CfgNode *n) { NSE = adjoin(NSE, n); }
  /* True if this is a non-standard exit of n. */
  bool isNSE(CfgNode *n) const { return NSE->find(n) != NSE->end(); }
  void delSucc(CfgNode *n) { 
    numSucc--; 
    assert((_succ = remove(n, _succ)) != (llist<CfgNode *>*)-1 ); 
  }
  void delAllSucc() { numSucc = 0; free_all(_succ); _succ = NULL; }
  void delAllPred() { numPred = 0; free_all(_pred); _pred = NULL; }
  void delPred(CfgNode *n) { 
    numPred--; 
    assert((_pred = remove(n, _pred)) != (llist<CfgNode *>*)-1 ); 
  }
  ListIterator<CfgNode *> succIter() {
    return ListIterator<CfgNode *> (_succ);
  }
  ListIterator<CfgNode *> predIter() {
    return ListIterator<CfgNode *> (_pred);
  }
  ListIterator<CfgNode *> predIter(bool ignoreNSE, const CFGset *l, bool *i) {
    if (ignoreNSE)
      return ListIterator<CfgNode *> (filterNSE(l, i));
    else
      return predIter();
  }
  inline bool hasOneSuccessor() {
    ListIterator<CfgNode *> i = succIter();
    return (!i.isDone() && (i.next(), i.isDone()));
  }
  inline bool hasOnePredecessor() {
    ListIterator<CfgNode *> i = predIter();
    return (!i.isDone() && (i.next(), i.isDone()));
  }

  void print(ostream &os) const;
};


// BASIC BLOCKS
// The basic blocks collect individual CfgNodes together, in case the client
// is just interested in the overall pattern of control flow and doesn't need
// to iterate through every single AST node.

class Bblock {
protected:
  llist<Bblock *> *_preds;
  llist<Bblock *> *_succs;
  llist<CfgNode *> *_cfglist;
  int visited;
  Bitset *_defsOut;  // defs that reach out of the bblock.
  Bitset *_defsIn;   // union of incoming defs
  Bitset *_defs;     // defs in this bblock
  Bitset *_kills;    // defs killed by this bblock
  AliasInfos *_aliasesIn; // set of aliases at beg of bblock
  AliasInfos *_aliasesOut; // set of aliases at end of bblock
  
public:
  Bblock();

  ~Bblock() {
    free_all(_cfglist);
    free_all(_preds);
    free_all(_succs);

    delete _defsOut;
    delete _defsIn;
    delete _defs;
    delete _kills;
    delete _aliasesIn;
    delete _aliasesOut;
  }
  void *operator new(size_t);      
  void operator delete(void *, size_t);

  ListIterator<Bblock *> succIter() {
    return ListIterator<Bblock *>(_succs);
  }
  ListIterator<Bblock *>predIter() {
    return ListIterator<Bblock *>(_preds);
  }
  ListIterator<CfgNode *>cfgIter() {
    return ListIterator<CfgNode *>(_cfglist);
  }
  void nodeStatus(int v) { visited = v; }
  int nodeStatus() { return visited; }
  void addSucc(Bblock *b) { push(_succs, b); }
  void addPred(Bblock *b) { push(_preds, b); }
  void addCfg(CfgNode *c) { 
    _cfglist = extend(_cfglist, cons(c));
    c->bblock = this; 
  }
  Bitset *defs() { return _defs; }
  Bitset *kills() { return _kills; }
  Bitset *defsIn() { return _defsIn; }
  Bitset *defsOut() { return _defsOut; }
  AliasInfos *aliasesIn() { return _aliasesIn; }
  AliasInfos *aliasesOut() { return _aliasesOut; }  
  void setDefs(Bitset *defs) { _defs = defs; }
  void setKills(Bitset *kills) { _kills = kills; }
  void setDefsIn(Bitset *defs) { _defsIn = defs; }
  void setDefsOut(Bitset *defs) { _defsOut = defs; }
  void setAliasesIn(AliasInfos *ai) { _aliasesIn = ai; }
  void setAliasesOut(AliasInfos *ai) { _aliasesOut = ai; }  
  void print(ostream &os);
  int number;
  int defsize;
};


////////////////////////////////////////////////////////////////////////
//
// REUSABLE NODE STORAGE
//
// Repeatedly allocating and deleting graph nodes could be expensive
// and error-prone; instead we try to reuse nodes. We do this by
// allocating nodes from BufferPools, "pseudo-heaps" that store nodes
// of one type and can be reset to free all the nodes at once. A
// collection of BufferPools is a NodeStorage. Each method contains
// one NodeStorage.  Graph node classes have custom allocation
// operators that use corresponding buffer pools for managing instance
// memory.

// One of these objects exists for every method; used for storage reuse.
class NodeStorage {
public:
  // The pseudoconstructors need to know what the current NodeStorage object
  // to get nodes from is. This variable tells them; the client needs to set
  // it to the NodeStorage object for the current method.
  static NodeStorage *current;
 
  // use InstancePool instead of BufferPool to make sure our 
  // node destructors get called (to cleanup a big memory leak) 
  InstancePool< CfgNode > cfgHeap;
  InstancePool< Bblock > bblockHeap;

  void reset() {
    cfgHeap.reset();
    bblockHeap.reset();
  }
};

////////////////////////////////////////////////////////////////////////

llist<CfgNode *> *CfgNodesWithinSubtree(const llist<CfgNode *> *l,
					TreeNode *t);
int TraverseCfg(CfgNode *c, void action(CfgNode *));
int TraverseCfgExtents(CfgNode *from, CfgNode *to, 
		       void action(CfgNode *, void*), void* data);
int TraverseCfgScope(TreeNode *scope, void action(CfgNode *, void*), 
		     void* data);
void UnmarkCfg(CfgNode *c);
void UnmarkCfgExts(CfgNode *from, CfgNode *to);
void UnmarkBblocks(Bblock *b);
void traverseCfgBblock(CfgNode *c, Bblock *currBblock, CfgNode *lastCfg);
void TraverseBblocksIter(Bblock *b, bool action(Bblock *b));
void TraverseBblocks(Bblock *b, void action(Bblock *b));
void TraverseBblocksScope(TreeNode *scope, void action(Bblock *b));
CfgNode *LastMethodNode(TreeNode *p);
CFGset *copy(CFGset *s);
treeSet * list_to_set(llist<CfgNode *> *l);
const CFGuset * list_to_CFGuset(CFGusetFactory &U, llist<CfgNode *> *l);
void summarizeCFG(llist<CfgNode *> * l, ostream &os);
void summarizeCFG(const TreeNode *m, ostream &os);
void summarizeLoopCFG (TreeNode *m, ostream &os);
void pathsfrom(ostream &os, CfgNode *n, const treeSet *s = NULL);
void shortCFGnode(ostream &os, const CfgNode *n);
void shortCFGlist(ostream &os, ListIterator<CfgNode *> s);
void shortCFGset(CFGset *s, ostream &os);
void shortCFGuset(const CFGuset *s, ostream &os);
void PrintBblockAction(Bblock *b);
void setupBblocksMethod(TreeNode *method);
void setupUdMethod(TreeNode *method, bool computeDeps = false);

bool hasSelfPath(CfgNode *n, const treeSet *s);
bool must_come_from(const StatementNode *t, const treeSet &s);

#endif // !_CFG_H_