#include <map>
#include <set>
#include "AST.h"
#include "StringSet.h"
#include "code-util.h"
#include "optimize.h"
#include "types.h"
#include "streq.h"
#include "lower.h"
#include "string-utils.h"
#include <time.h>
#include <sys/time.h>

extern bool debug_defs;
#define debug_pure debug_defs

/* Always returns a positive integer unless a and b are both 0. */
int gcd(int a, int b)
{
  if (a < 0) a = -a;
  if (b < 0) b = -b;
  if (a > b)
    swap(b, a);
  /* 0 <= a <= b */
  if (a == 0)
    return b;
  if (a == 1 || b == 1 || a == b)
    return a;
  return gcd(b % a, a);
}

// Convert any int into a unique alphanumeric string.
string int2alpha(int i)
{
  if (i < 0)
    return string("9") + int2alpha(-i);
  else if (i < 26)
    return string("") + (char) ('A' + i);
  else if (i < 52)
    return string("") + (char) ('a' + i - 26);
  else if (i < 61)
    return string("") + (char) ('0' + i - 52);
  else
    return int2alpha(i / 61) + int2alpha(i % 61);
}

static int64 getMicrosecondTimeStamp(void) {
  int64 retval;
  struct timeval tv;
  if (gettimeofday(&tv, NULL)) {
      perror("gettimeofday");
      abort();
  }
  retval = ((int64)tv.tv_sec) * 1000000 + tv.tv_usec;
  return retval;
}

extern string compile_time(struct timeval *tv) {
    static int64 compile_starttime = -1;
    char timestr[20];
    int64 timeval;
    int mins;
    double secs;
    if (compile_starttime == -1) compile_starttime = getMicrosecondTimeStamp();
    if (tv) timeval = ((int64)tv->tv_sec) * 1000000 + tv->tv_usec;
    else timeval = getMicrosecondTimeStamp() - compile_starttime;
    mins = (int)(timeval/(1000000*60));
    secs = ((double)(timeval - ((int64)mins)*1000000*60))/1000000.0;
    sprintf(timestr,"%02i:%06.3f",mins,secs);
    return string(timestr);
}

// output tc compile status info
extern int compile_verbose_level;
extern void compile_status(int verbose_level, string message) {
  assert(verbose_level >= 0 && verbose_level <= 4);
  if (compile_verbose_level >= verbose_level) {
    cout << compile_time() << ": ";
    for (int i=1; i < verbose_level; i++) cout << "  ";
    cout << message << endl;
  }
}

// unique(p) always returns the same string for the same p but 
// unique(p) != unique(q) if p != q.
string &unique(void *p)
{
  static map_void_to_string m;
  string &r = m[p];
  if (r == "")
    return (r = string("<") + int2string(uniqueInt(p)) + string(">"));
  else
    return r;
}


// uniqueInt(p) always returns the same positive integer for the same p but 
// uniqueInt(p) != uniqueInt(q) if p != q.
int &uniqueInt(void *p)
{
  static map_void_to_int m;
  static int i = 0;
  int &r = m[p];
  if (r != 0)
    return r;
  else
    return (r = ++i);
}

/* Always return the same int for the same <v, w> pair.  Always return
   different results for <v, w> and <v, w'> if w != w'.  May or may not
   return the same result for <v, w> and <v', w'> if v != v'. */
int unique2(void *v, void *w)
{
  static map_void_to_int start;
  static map_void_void_to_int m;
  
  int &r = m[v][w];
  if (r > 0)
    return r;
  else
    return (r = ++(start[v]));
}

void appendWithCommaOperator(string &s, const string &o)
{
  string v = '(' + o + ')';
  s = (s == "") ? v : (s + ", " + v);
}

void appendWithSemicolon(string &s, const string &o)
{
  s = (s == "") ? o : (s + "; " + o);
}

Decl * getRectDomainMethodDecl(int arity, const string *name)
{
  return getRectDomainDecl(makeRectDomainType(arity))->environ()->
    lookupProper(name, Decl::Method);
}

Decl * getDomainMethodDecl(int arity, const string *name)
{
  return getDomainDecl(makeDomainType(arity))->environ()->
    lookupProper(name, Decl::Method);
}

string nameOfEnclosingMethod(const TreeNode *t)
{
  return *(enclosingMethod(t)->simpName()->ident());
}

TreeNode *enclosingMethod(const TreeNode *t)
{
  while (true)
    if (t == NULL || isMethodDeclNode(t) || isConstructorDeclNode(t))
      return (TreeNode *) t;
    else
      t = t->parent();
}

StatementNode *enclosingStmt(const TreeNode *t)
{
  while (true)
    if (t == NULL || t->isStatementNode())
      return (StatementNode *) t;
    else
      t = t->parent();
}

TreeNode *enclosingForeach(const TreeNode *t)
{
  while (true)
    if (t == NULL || isForEachStmtNode(t))
      return (TreeNode *) t;
    else
      t = t->parent();
}

TreeNode *enclosingDummy(const TreeNode *t)
{
  while (true)
    if (t == NULL || isDummyNode(t))
      return (TreeNode *) t;
    else
      t = t->parent();
}

#if 0
static void show_once(TreeNode *t)
{
  static set<TreeNode *> s;
  if (s.find(t) == s.end()) {
    s.insert(t);
    char x[40];
    sprintf(x, "%lx is:\n", (long) t);
    cout << endl << x << pseudocode(t) << endl;
  }
}
#endif

/* In the subtree rooted at t, return a list of all StatementNodes
   excluding t itself. */
llist<StatementNode *> *all_substmts(TreeNode *t)
{
#if 0
  static int recursion_count = 0;
  ++recursion_count;
  show_once(t);
  {
    char s[50];
    sprintf(s, "%4d all_substmts(%lx): children are\n", recursion_count,
	    (long) t);
    cout << s;
    foriter (p, t->allChildren(), TreeNode::ChildIter) {
      sprintf(s, "  %lx\n", (long) (*p));
      cout << s;
    }
  }
#endif
  llist<StatementNode *> *result = NULL;
  foriter (p, t->allChildren(), TreeNode::ChildIter) {
    if ((*p)->isStatementNode())
      push(result, static_cast<StatementNode *>(*p));
    result = extend(result, all_substmts(*p));
  }
#if 0
  {
    char s[50];
    sprintf(s, "%4d all_substmts(%lx): done\n", recursion_count, (long) t);
    cout << s;
  }
  --recursion_count;
#endif
  return result;
}

/* If a is an ancestor of b, return b.  Else return NULL.  Requires
   that the parent pointers on the AST are set correctly. */
TreeNode *isAncestor(TreeNode *a, TreeNode *b)
{
  if (a == b) return b;
  else if (b == NULL || b->parent() == NULL) return NULL;
  else return (isAncestor(a, b->parent()) ? b : NULL);
}

/* Return the first element of l that has a as an ancestor.
   Return NULL if no element of l has a as an ancestor. */
TreeNode *isAncestorOfAny(TreeNode *a, llist<TreeNode *> *l)
{
  if (l != NULL) {
    TreeNode *x = isAncestor(a, l->front());
    return (x == NULL) ? isAncestorOfAny(a, l->tail()) : x;
  }
  return NULL;
}

bool compareLists(const llist<treepair> *t, const llist<treepair> *u)
{
  return ((t == NULL) == (u == NULL)) &&
    (t == NULL ||
     (COMPARE(t->front().first, u->front().first) &&
      COMPARE(t->front().second, u->front().second) &&
      compareLists(t->tail(), u->tail())));
}

bool compareLists(const llist<TreeNode *> *t, const llist<TreeNode *> *u)
{
  return ((t == NULL) == (u == NULL))
    && (t == NULL
	|| COMPARE(t->front(), u->front())
	&& compareLists(t->tail(), u->tail()));
}

// Returns whether s appears in z, a list of n strings.
static bool strFind(const string& s, const char **z)
{
  static map< const char **, StringSet *, less< const char ** > > memo;
  StringSet *& S = memo[z];

  if (S == NULL) {
    S = new StringSet;
    while (*z) S->insert(*z++);
  }
  return (S->count(s) > 0);
} 

/* If t is a call to binary +, -, *, /, or %, then return the op (e.g., '+').
   Otherwise return '\0'. */
char arithCall(const TreeNode *t) 
{
  char *s = "+-*/%";

  if (isOFAN(t->child(0)) && isNameNode(t->child(0)->child(1))) {
    const TreeNode *namenode = t->child(0)->child(1);
    if (!namenode->qualifier()->absent()) return false;
    const string methodName = *namenode->ident();
    for (int i = 0; ; i++)
      if (s[i] == '\0'
	  || methodName.c_str()[0] == s[i] && methodName.c_str()[1] == '\0')
	return s[i];
  }
  return false;
}

bool isPointOrIntegralType(const TypeNode *t)
{
  return t->isPointType() || t->isIntegralType();
}

bool isTiOrNumericType(const TreeNode *x)
{
  assert(x->isExprNode());
  return isTiOrNumericType(((ExprNode *) x)->type());
}

bool isTiOrNumericType(const TypeNode *t)
{
  return (t->isArithType()
	  || t->isPointType()
	  || t->isDomainType()
	  || t->isRectDomainType()
	  || t->isTitaniumArrayType());
}


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

/*
   Terminology:

   A "side-effect free" method has no side effects that are visible
   to the callee.

   A pure method always returns the same value for the same arguments
   and is "side-effect free."

*/

static const char *PointStaticPureMethods[] = { "all", "direction", 0 };
static const char *RectDomainStaticPureMethods[] = { 0 };
static const char *DomainStaticPureMethods[] = { "toDomain", 0 };
static const char *GridStaticPureMethods[] = { 0 };

static const char *PointPureMethods[] = { "arity", "+", "-", "*", "/", "+=", "-=", "*=", "/=",
"<", ">", "<=", ">=", "==", "!=", "equals", "[]", "permute", 0 };

static const char *GridPureMethods[] = { "domain", "arity",
"translate", "restrict", "inject", "project", "slice", "permute", 
"isLocal", "creator", "regionOf", 0 };

static const char *RectDomainPureMethods[] = { "isRectangular",
"arity", "min", "max", "lwb", "upb", "boundingBox", "stride", "size", "isNull", "isNotNull", "isEmpty",
"contains", "accrete", "shrink", "permute", "border", "slice", "+", "-", "*", "/", "+=", "-=", "*=", "/=",
"<", ">", "<=", ">=", "==", "!=", "equals", "toString", 0 };

static const char *DomainPureMethods[] = { "isRectangular", "arity",
"min", "max", "lwb", "upb", "boundingBox", "size", "isNull", "isNotNull", "isEmpty",
"contains", "RectDomainList", "PointList", "+", "-", "*", "/", "+=", "-=", "*=", "/=", "<", ">", "<=",
">=", "==", "!=", "equals", "permute", "toString", "hashCode", 0 };

static const char *PureMethods[] = {
  "Math.abs", "Math.round", "Math.max", "Math.min", "Math.sin", "Math.cos",
  "Math.tan", "Math.asin", "Math.acos", "Math.atan", "Math.exp", "Math.log",
  "Math.sqrt", "Math.IEEEremainder", "Math.ceil", "Math.floor", "Math.rint",
  "Math.atan2", "Math.pow",

  "Ti.thisProc", "Ti.numProcs",

  0
};

static const char *SideEffectFreeMethods[] = {"Math.random", 0};

static bool methodNameFind(const TreeNode *t, const char *strs[])
{
  assert(isNameNode(t));
  return strFind(*t->ident(), strs);
}

// md is a MethodDeclNode or MethodSignatureNode. Returns true if the
// method is known to be pure or appears in the SideEffectFreeMethods list
bool isKnownSideEffectFree(const TreeNode *md)
{
  if (md == NULL)
    return false;
  if (isKnownPure(md))
    return true;
  string s = *md->decl()->container()->name() + '.' + *md->decl()->name();
  if (isInJavaLang(md->decl()->container()) && strFind(s, SideEffectFreeMethods))
    return true;
  return false;
}

bool isPureCallThatCannotFail(const TreeNode *t)
{
  if (t == NULL)
    return false;
  if (isMethodCallNode(t) && t->isPureFunction()) {
    char op = arithCall(t);
    if (op) {
      if (op == '/')
	return false; // could be division by 0
      else {
	TypeNode *t0, *t1;
	if ((t->method()->decl()->source()->flags() & Common::Static) == 0) {
	  // cout << PCODE(t);
	  // cout << ": not static, arity = " << t->args()->arity() << endl;
	  if (t->args()->arity() != 1)
	    return false;
	  t0 = t->method()->accessedObjectType();
	  t1 = t->args()->child(0)->type();
	} else {
	  // cout << PCODE(t);
	  // cout << ": static, arity = " << t->args()->arity() << endl;
	  if (t->args()->arity() != 2)
	    return false;
	  t0 = t->args()->child(0)->type();
	  t1 = t->args()->child(1)->type();
	}
	// cout << "types are ok: " <<
	//   (isTiOrNumericType(t0) && isTiOrNumericType(t1)) << endl;
	return (isTiOrNumericType(t0) && isTiOrNumericType(t1));
      }
    } else
      return true;
  } else if (isUnaryArithNode(t) || isBinaryArithNode(t) || isShiftNode(t) ||
	     isRelationNode(t) || isRelationNode(t) || isBitwiseNode(t) ||
	     isLogCondNode(t)) {
    return true;
  } else
    return false;
}

bool isMethodCallWhereinNoExceptionsCanBeThrown(const MethodCallNode *t)
{
  return t->isPureFunction() || isGridMethod(t);
}

bool canThrowCheckedException(const MethodDecl *d) {
  foriter (exc, d->methodType()->throws()->allTypes(), TreeNode::TypeIter) {
    Decl *excDecl = (*exc)->decl();
    if (!(isSubClass(excDecl, RuntimeExceptionDecl) ||
	  isSubClass(excDecl, ErrorDecl)))
      return true;
  }
  return false;
}

bool isSideEffectFreeAndCannotFail(const TreeNode *t)
{
  return (t == NULL) ?
    false :
    (isPureCallThatCannotFail(t) ||
     isPointArrayAccessNode(t) &&
     isIntLiteralInRange(t->index(), 1, t->array()->type()->tiArity()));
}

// method is a MethodDeclNode or MethodSignatureNode or
// ConstructorDeclNode
bool isKnownPure(const TreeNode *m)
{
  if (m == NULL)
    return false;
  string name = *m->decl()->container()->name();  
  if ((m->flags() & Common::Static) != 0) {
    if (isInSystemPackage(m->decl()->container(), "ti", "internal")) {
      if (name == "tiPoint")
	return methodNameFind(m->simpName(), PointStaticPureMethods);
      else if (name == "tiRectDomain")
	return methodNameFind(m->simpName(), RectDomainStaticPureMethods);
      else if (name == "tiDomain")
	return methodNameFind(m->simpName(), DomainStaticPureMethods);
      else if (name == "tiArray" || name == "tiArrayM1" ||
	       name == "tiJArray" || name == "tiArrayL")
	return methodNameFind(m->simpName(), GridStaticPureMethods);
    }
    else if (isInSystemPackage(m->decl()->container(), "java", "lang") ||
	     isInSystemPackage(m->decl()->container(), "ti", "lang")) {
      string s = *m->decl()->container()->name() + '.' + *m->decl()->name();
      bool r = strFind(s, PureMethods);
      return r;
    }
  }
  else {
    if (isInSystemPackage(m->decl()->container(), "ti", "internal")) {
      if (name == "tiPoint")
	return methodNameFind(m->simpName(), PointPureMethods);
      else if (name == "tiRectDomain")
	return methodNameFind(m->simpName(), RectDomainPureMethods);
      else if (name == "tiDomain")
	return methodNameFind(m->simpName(), DomainPureMethods);
      else if (name == "tiArray" || name == "tiArrayM1" ||
	       name == "tiJArray" || name == "tiArrayL")
	return methodNameFind(m->simpName(), GridPureMethods);
    }
  }
  return false;
}

bool isAnyGridMethod(const MethodCallNode *t)
{
  TreeNode *m = t->method();
  return isOFAN(m) && m->object()->type()->isTitaniumArrayType();
}

/* If methodName is non-empty then true iff t a call to a that
   particular grid method.  If methodName is empty then true iff t a
   call to any grid method. */
bool isGridMethod(const TreeNode *t, string methodName)
{
  if (methodName.empty())
    return isMethodCallNode(t) && isAnyGridMethod((MethodCallNode *) t);

  MethodCallNode *m;
  ObjectFieldAccessNode *o;

  return isMethodCallNode(t) && isAnyGridMethod(m = ((MethodCallNode *) t))
    && isOFAN(m->method())
    && ((o = ((ObjectFieldAccessNode *) m->method())))
    && (*(o->simpName()->ident()) == methodName);
}

/* Assumes isGridMethod(t) is true. */
bool isGridMethodMutating(const MethodCallNode *t)
{
  return !t->isPureFunction();
}


bool doesNotReadOrWriteNonArgs(const MethodCallNode *t)
{
  if (t == NULL)
    return false;
  const TreeNode *m = t->decl()->source();
  if (m == NULL)
    return false;
  string name = *m->decl()->container()->name();  
  if ((m->flags() & Common::Static) != 0) {
    if (isInSystemPackage(m->decl()->container(), "ti", "internal")) {
      if (name == "tiPoint")
	return methodNameFind(m->simpName(), PointStaticPureMethods);
      else if (name == "tiRectDomain")
	return methodNameFind(m->simpName(), RectDomainStaticPureMethods);
      else if (name == "tiDomain")
	return methodNameFind(m->simpName(), DomainStaticPureMethods);
      else if (name == "tiArray" || name == "tiArrayM1" ||
	       name == "tiJArray" || name == "tiArrayL")
	return methodNameFind(m->simpName(), GridStaticPureMethods);
    }
    else if (isInSystemPackage(m->decl()->container(), "java", "lang") ||
	     isInSystemPackage(m->decl()->container(), "ti", "lang")) {
      string s = *m->decl()->container()->name() + '.' + *m->decl()->name();
      bool r = strFind(s, PureMethods);
      return r;
    }
  }
  else {
    if (isInSystemPackage(m->decl()->container(), "ti", "internal")) {
      if (name == "tiPoint")
	return methodNameFind(m->simpName(), PointPureMethods);
      else if (name == "tiRectDomain")
	return methodNameFind(m->simpName(), RectDomainPureMethods);
      else if (name == "tiDomain")
	return methodNameFind(m->simpName(), DomainPureMethods);
      else if (name == "tiArray" || name == "tiArrayM1" ||
	       name == "tiJArray" || name == "tiArrayL")
	return methodNameFind(m->simpName(), GridPureMethods);
    }
  }
  return false;
}	  

/* True iff d is in the system package n1.n2. */
bool isInSystemPackage(const Decl *d, const string &n1, const string &n2) {
  Decl *d2 = d->container();
  Decl *d1 = d2->container();
  return (*d1->name() == n1 && *d2->name() == n2 &&
	  d1->container() == PackageDecl::System);
}

bool isInJavaLang(const Decl *d) {
  return isInSystemPackage(d, "java", "lang");
}

bool isInJavaIO(const Decl *d) {
  return isInSystemPackage(d, "java", "io");
}

bool isInLibrary(Decl *d) {
  const string name = d->fullName();
  return (hasPrefix(name, "java.") ||
	  hasPrefix(name, "ti.") ||
	  // Java 1.4 libraries.
	  hasPrefix(name, "com.") ||
	  hasPrefix(name, "javax.") ||
	  hasPrefix(name, "org.") ||
	  hasPrefix(name, "sun.") ||
	  hasPrefix(name, "sunw."));
}


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

bool isIntLiteralInRange(const TreeNode *t, int lo, int hi)
{
  while (isCastNode(t))
    t = t->opnd0();
  return (isPrimitiveLitNode(t) &&
	  (t->literal().kind() == Common::IntKind ||
	   t->literal().kind() == Common::ShortKind ||
	   t->literal().kind() == Common::LongKind) &&
	  t->literal().intValue() <= hi &&
	  t->literal().intValue() >= lo);
}

bool isConstantOrCastOfConstant(const TreeNode *t)
{
  return (isPrimitiveLitNode(t) ||
	  isCastNode(t) && isConstantOrCastOfConstant(t->opnd0()));
}

bool isNullOrCastOfNull(const TreeNode *t)
{
  return (isNullPntrNode(t) ||
	  isCastNode(t) && isNullOrCastOfNull(t->opnd0()));
}

bool isTrivialPointOrDomain(const TreeNode *t)
{
  return (isObjectNode(t) && isLocalOrParam(t->decl()) ||
	  isPointNode(t) || isDomainNode(t) ||
	  isCodeLiteralExprNode(t) &&
	  t->codeString() == callNoArgConstructor(((ExprNode *) t)->type()) ||
	  isCastNode(t) && isTrivialPointOrDomain(t->child(0)));
}

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

#define IS_NODE(FOO)					\
bool is ## FOO ## Node(const TreeNode *t)		\
{							\
  return (streq(t->oper_name(), #FOO "Node"));		\
}

IS_NODE(MethodCall)
IS_NODE(MethodCallAssign)
IS_NODE(Domain)
IS_NODE(Point)

// Return true if this is an object field access node that
// is accessing an instance (non-static) field of an immutable object.
bool isIIFAN(const TreeNode *t)
{
  return (isOFAN(t) && 
          t->object()->type()->isImmutable() &&
          isFieldDeclNode(t->simpName()->decl()->source()) &&
          !(t->simpName()->decl()->modifiers() & Common::Static));
}

bool isCodeLiteralFAN(const TreeNode *t)
{
  return (streq(t->oper_name(), "CodeLiteralFieldAccessNode"));
}

bool isOFAN(const TreeNode *t)
{
  return (streq(t->oper_name(), "ObjectFieldAccessNode"));
}  

bool isTypeFAN(const TreeNode *t)
{
  return  (streq(t->oper_name(), "TypeFieldAccessNode"));
}  

// return true iff this is a FAN which accesses a static field
bool isStaticFAN(const TreeNode *t) {
  return isTypeFAN(t) ||
    (isOFAN(t) && (t->simpName()->decl()->modifiers() & Common::Static));
}
bool isThisFAN(const TreeNode *t)
{
  return  (streq(t->oper_name(), "ThisFieldAccessNode"));
}  

bool isSFAN(const TreeNode *t)
{
  return  (streq(t->oper_name(), "SuperFieldAccessNode"));
}  

IS_NODE(ArrayInit)
IS_NODE(Return)
IS_NODE(ThisConstructorCall)
IS_NODE(SuperConstructorCall)
IS_NODE(Name)
IS_NODE(TypeName)
IS_NODE(This)
IS_NODE(Object)
IS_NODE(EmptyStmt)
IS_NODE(IfStmt)
IS_NODE(ForEachStmt)
IS_NODE(TitaniumArrayType)
IS_NODE(ObjectFieldAccess)
IS_NODE(ForEachPair)
IS_NODE(Reorder)
IS_NODE(UpdatePointBeforeStmt)
IS_NODE(HasNoOverlap)
IS_NODE(MethodDecl)
IS_NODE(ConstructorDecl)

bool isTreeListNode(const TreeNode *t) 
{
  return (streq(t->oper_name(), "*list*"));
}

IS_NODE(TemplateDecl)
IS_NODE(TemplateInstanceDecl)
IS_NODE(TemplateInstanceType)
IS_NODE(TemplateName)
IS_NODE(MethodSignature)

IS_NODE(CompileUnit)
IS_NODE(Block)
IS_NODE(Not)
IS_NODE(Complement)
IS_NODE(Goto)
IS_NODE(LabeledStmt)
IS_NODE(TryStmt)
IS_NODE(Finally)

IS_NODE(UnaryMinus)
IS_NODE(UnaryPlus)
bool isUnaryArithNode(const TreeNode *t) 
{
  return isUnaryPlusNode(t) || isUnaryMinusNode(t);
}

IS_NODE(Mult)
IS_NODE(Div)
IS_NODE(Rem)
IS_NODE(Plus)
IS_NODE(Minus)
bool isBinaryArithNode(const TreeNode *t) 
{
  return isMultNode(t) || isDivNode(t) || isRemNode(t) ||
    isPlusNode(t) || isMinusNode(t);
}

IS_NODE(LeftShiftLog)
IS_NODE(RightShiftLog)
IS_NODE(RightShiftArith)
bool isShiftNode(const TreeNode *t) 
{
  return isLeftShiftLogNode(t) || isRightShiftLogNode(t) ||
    isRightShiftArithNode(t);
}

IS_NODE(LT)
IS_NODE(GT)
IS_NODE(LE)
IS_NODE(GE)
bool isRelationNode(const TreeNode *t) 
{
  return isLTNode(t) || isGTNode(t) ||isLENode(t) || isGENode(t);
}

IS_NODE(EQ)
IS_NODE(NE)
IS_NODE(TitaniumArrayEQ)
bool isEqualityNode(const TreeNode *t) 
{
  return isEQNode(t) || isNENode(t);
}

IS_NODE(BitAnd)
IS_NODE(BitOr)
IS_NODE(BitXor)
bool isBitwiseNode(const TreeNode *t) 
{
  return isBitAndNode(t) || isBitOrNode(t) || isBitXorNode(t);
}

IS_NODE(Cand)
IS_NODE(Cor)
bool isLogCondNode(const TreeNode *t) 
{
  return isCandNode(t) || isCorNode(t);
}

bool isOmittedNode(const TreeNode *t) 
{
  return (streq(t->oper_name(), "-*-"));
}

IS_NODE(Cast)
IS_NODE(InstanceOf)
bool isDynamicTypeNode(const TreeNode *t) 
{
  return isCastNode(t) || isInstanceOfNode(t);
}

IS_NODE(FieldDecl)
IS_NODE(ClassDecl)
IS_NODE(InterfaceDecl)
IS_NODE(StaticInit)
IS_NODE(InstanceInit)
IS_NODE(CodeLiteralExpr)
IS_NODE(Allocate)
IS_NODE(AllocateSpace)
IS_NODE(AllocateArray)
IS_NODE(IBroadcast)
IS_NODE(VarDecl)
IS_NODE(Assign)
IS_NODE(Synchronized)
IS_NODE(Parameter)
IS_NODE(NullPntr)
IS_NODE(StringConcat)
IS_NODE(StringConcatAssign)
IS_NODE(StringLit)
IS_NODE(Assert)
IS_NODE(PrimitiveLit)
IS_NODE(PreIncr)
IS_NODE(PreDecr)
IS_NODE(PostIncr)
IS_NODE(PostDecr)
IS_NODE(ExpressionStmt)
IS_NODE(Dummy)
IS_NODE(SwitchBranch)
IS_NODE(For)
IS_NODE(Do)
IS_NODE(While)
IS_NODE(Break)
IS_NODE(Continue)

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

bool StatementNode::isStatementNode() const { return true; }

/////////////////////////////////////////////////////////////////////////////
// Kinds of variables, constants
/////////////////////////////////////////////////////////////////////////////

bool isConstant(const TreeNode *t)
{
  return t->isLitNode();
}

bool isFormalParamDecl(const Decl *d)
{
  return (d->category() == Decl::Formal);
}

bool isLocalVarDecl(const Decl *d)
{
  return (d->category() == Decl::LocalVar);
}

bool isFormalParam(const TreeNode *t)
{
  return ((isNameNode(t) && isFormalParamDecl(t->decl())) ||
	  (isObjectNode(t)) && isFormalParam(t->child(0)));
}

bool isLocalVar(const TreeNode *t)
{
  return ((isNameNode(t) && isLocalVarDecl(t->decl())) ||
	  (isObjectNode(t)) && isLocalVar(t->child(0)));
}

Decl *getDeclFromLocalOrFormal(const TreeNode *t)
{
  if (isNameNode(t))
    return t->decl();
  else
    return t->child(0)->decl();
}

IS_NODE(MultAssign)
IS_NODE(DivAssign)
IS_NODE(RemAssign)
IS_NODE(PlusAssign)
IS_NODE(MinusAssign)
IS_NODE(LeftShiftLogAssign)
IS_NODE(RightShiftLogAssign)
IS_NODE(RightShiftArithAssign)
IS_NODE(BitAndAssign)
IS_NODE(BitXorAssign)
IS_NODE(BitOrAssign)

IS_NODE(LazyOptimize)

bool TreeNode::isExprNode() const { return false; }
bool ExprNode::isExprNode() const { return true; }
bool isExprNode(const TreeNode *t) { return t->isExprNode(); }

bool TreeNode::isArrayAccessNode() const { return false; }
bool ArrayAccessNode::isArrayAccessNode() const { return true; }
bool isArrayAccessNode(const TreeNode *t) { return t->isArrayAccessNode(); }

IS_NODE(ArrayName)
IS_NODE(TitaniumArrayAccess)
IS_NODE(JavaArrayAccess)
IS_NODE(PointArrayAccess)
IS_NODE(SRArrayAccess)
IS_NODE(OSRArrayAccess)


IS_NODE(MonitorFetchClass)
IS_NODE(MonitorFetchInstance)
IS_NODE(MonitorLock)
IS_NODE(MonitorUnlock)

bool isMonitorFetchNode(const TreeNode *t) {
  return isMonitorFetchClassNode(t) || isMonitorFetchInstanceNode(t);
  }
bool isMonitorUseNode(const TreeNode *t) {
  return isMonitorLockNode(t) || isMonitorUnlockNode(t);
  }

IS_NODE(Catch)

///////////////////////////////////////////////////////////////////////////
bool isTrue(const TreeNode *t)
{
  return (isPrimitiveLitNode(t) &&
	  t->constantType() == Common::BoolKind &&
	  t->literal().boolValue());
}

bool isFalse(const TreeNode *t)
{
  return (isPrimitiveLitNode(t) &&
	  t->constantType() == Common::BoolKind &&
	  !t->literal().boolValue());
}

static bool allNOP(const TreeListNode *l)
{
  for (int i = l->arity(); --i >= 0; )
    if (!isNOP(l->child(i)))
      return false;
  return true;
}

bool isNOP(const TreeNode *t)
{
  return t->absent() || isEmptyStmtNode(t) ||
    (isBlockNode(t) && allNOP(t->stmts()));
}


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

bool isLHSofAssignNode(TreeNode *t)
{
  return isAssignNode(t->parent()) && t->parent()->opnd0() == t;
}

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

/* Do a DFS and return the first AllocateNode found. */
AllocateNode *AllocateNode::findAllocateNode()
{
  return this;
}

/* Do a DFS and return the first AllocateNode found. */
AllocateNode *TreeNode::findAllocateNode()
{
  foriter (c, allChildren(), ChildIter) {
    AllocateNode *subresult = (*c)->findAllocateNode();
    if (subresult != NULL)
      return subresult;
  }
  return NULL;
}