/* aux-code.cc: Code-generation-related implementations.		*/

#include <iostream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <time.h>
#include <sys/types.h>
#include <dirent.h>
#include "utils.h"
#include "AST.h"
#include "ClassDecl.h"
#include "CodeContext.h"
#include "CfHeader.h"
#include "CfSource.h"
#include "CtExternal.h"
#include "CtObjectDescriptor.h"
#include "ctBox.h"
#include "FieldDecl.h"
#include "MethodDecl.h"
#include "aux-code.h"
#include "aux-debug.h"
#include "code.h"
#include "code-assign.h"
#include "code-util.h"
#include "compiler.h"
#include "code-grid.h"
#include "decls.h"
#include "delimit.h"
#include "errors.h"
#include "interface.h"
#include "is-main.h"
#include "lower.h"
#include "nullify-local.h"
#include "string-utils.h"
#include "lgMacro.h"
#include "code-call.h"
#include "CfLayout.h"

/* Set this to true if you want BlockNode::codeGen to void all */
/* its children (kludge).   Put an */
/*     extern bool voidResultsOfBlockStatements; */
/* in your code to get to it. */
bool voidResultsOfBlockStatements = false;

extern string tlib_include_dir;

extern void db_print_environ(Environ *);

string FieldDecl::cFieldName() const
{
  return MANGLE_FIELD(+, *name(), container()->cType());
}

string cFieldName(Decl *decl)
{
  assert( decl->category() == Decl::Field );
  return static_cast< FieldDecl & >( *decl ).cFieldName();
}

Decl *visibleMethod(Decl *meth, ClassDecl *cl)
{
    foriter (decl, cl->environ()->allProperDecls(), EnvironIter)
      if ((decl->category() & Decl::Method) &&
	  (decl->name() == meth->name()) &&
	  (decl->type()->methodsConflict(meth->type())))
	return &*decl;
    
    /* NOT REACHED */
    fatal_error("");
    return NULL;
}

void emitInstanceMethods(ClassDecl *cl, ClassDecl *outer,
			 void (*outputFun)(MethodDecl &, ostream&), ostream& os)
{
    if (cl) {
	if (cl != ObjectDecl)
	    emitInstanceMethods(cl->superClass(), outer, outputFun, os);
	
	foriter (decl, cl->environ()->allProperDecls(), EnvironIter)
	    if ((decl->category() == Decl::Method) &&
		!(decl->modifiers() & (Common::Static | Common::Final)) &&
		(decl->container() == cl) &&
		(!(*decl).overrides())) {
		Decl *visibleDecl = visibleMethod(&*decl, outer);
		(*outputFun)(static_cast<MethodDecl&>(*visibleDecl), os);
	    }
    }
}

// Emit new instance fields introduced by this class, not inherited
// from an ancestral superclass.
void emitNovelInstanceFields(ClassDecl *cl, FieldPrinter outputFun, CfCode& os)
{
    foriter (decl, cl->environ()->allProperDecls(), EnvironIter)
	if (decl->category() == Decl::Field &&
	    !(decl->modifiers() & Common::Static) &&
	    (decl->container() == cl))
	    (*outputFun)(static_cast<FieldDecl&>(*decl), os);
}

// Emit all instance fields, including those inherited from an
// ancestral superclass.
void emitInstanceFields(ClassDecl *cl, FieldPrinter outputFun, CfCode& os)
{
    if (cl) {
	if (cl != ObjectDecl)
	    emitInstanceFields(cl->superClass(), outputFun, os);

	emitNovelInstanceFields(cl, outputFun, os);
    }
}

void emitStaticMethods(ClassDecl *cl, void (*outputFun)(Decl *, ostream&), ostream& os)
{
    foriter (decl, cl->environ()->allProperDecls(), EnvironIter) {
	if (decl->category() & Decl::Method) {
	    if ((decl->name() == cl->name()) ||
		((decl->modifiers() & Common::Static))) {
		(*outputFun)(&*decl, os);
	    }
	}
    }
}

void emitStaticFields(ClassDecl &cl, FieldPrinter outputFun, CfCode &os)
{
  foriter (decl, cl.environ()->allProperDecls(), EnvironIter)
    if ((decl->category() == Decl::Field)
	&& (decl->modifiers() & Common::Static)) {
      Decl * const container = decl->container();
      if (container == &cl || container->category() != Decl::Interface)
	(*outputFun)(static_cast< FieldDecl & >(*decl), os);
    }
}

void methodDecl(MethodDecl &decl, CfCode &os)
{
    const TypeNode &type = *decl.type();
    const TypeNode &container = *decl.container()->asType();
    const TypeListNode &params = *type.paramTypes();
    const bool immCtor = container.isImmutable()
      && decl.category() & Decl::Constructor;

    const TypeNode * const thisType = decl.thisType();
    const TypeNode &returnType = immCtor
	? *thisType
	: *decl.type()->returnType();
    
    vector< string > formals;
    if (thisType && !immCtor) {
	formals.push_back( thisType->cType() );
	os.add( thisType->cType() );
    }
    
    for (int i = 0; i < params.arity(); i++) {
	formals.push_back( params.child(i)->cType() );
	os.add( params.child(i)->cType() );
    }

    os.add( returnType.cType() );

    // DOB: skip declaration for certain special native methods
    // which are implemented using macros/inline fns
    const string methodName = *decl.name();
    if ((methodName == "emptyDomain" || methodName == "makeDomain")
        && isDomainOrtiDomainType(container)) return;

    os << "extern " << returnType.cType()
       << ' ' << decl.cMethodNameStatic()
       << "(" << delimit( formals ) << ");\n";
}

// C Type declaration for a method
string cMethodTypeString(const MethodDecl &method)
{
    TypeListNode *params = method.type()->paramTypes();
    const TypeNode * const thisType = method.thisType();
    vector< string > formals;
    
    if (thisType)
	formals.push_back( thisType->cType() );
    
    for (int i=0; i<params->arity(); i++)
	formals.push_back( params->child(i)->cType() );
    
    return method.type()->returnType()->cType()
	+ "(*)(" + delimit( formals ) + ')';
}

void staticFieldDecl(FieldDecl &fld, CfCode& os)
{
    os.add( fld.cType() );
    os << fld.type()->cType() << ' ' << fld.cFieldName() << ";\n";
}
static int fieldCompEquals = 1;
static void fieldComp(FieldDecl &fld, CfCode& os)
{
  string const comb = (fieldCompEquals?" && ":" || ");
  string const neg = (fieldCompEquals?"":"!");
  if (fld.type()->isPrimitive()) {
    os << comb << neg << "(s1." << fld.cFieldName() << " == s2." << fld.cFieldName() << ")";
  } else if (fld.type()->isTitaniumArrayType()) {
    os << comb << neg << callGridMethod(*fld.type(), "equals", 
       "(s1." + fld.cFieldName() + ", s2." + fld.cFieldName() + ")");
  } else if (fld.type()->isReference()) {
    // TODO: perhaps we should be calling Object.equals() here?
    os << comb << neg << lgMacro("EQUAL", *fld.type()) 
       << "(s1." << fld.cFieldName() << ", s2." << fld.cFieldName() << ")";
  } else if (fld.type()->isImmutable()) {
    MethodDecl *eqm = NULL;
    string const *op = intern(fieldCompEquals?"==":"!=");
    foriter (decl, 
             fld.type()->decl()->environ()->lookupFirstProper(op, Decl::Method),
             EnvironIter) {
      MethodDeclNode *mdn = dynamic_cast<MethodDeclNode *>(decl->source());
      MethodTypeNode *mtn = mdn->decl()->methodType();
      if (mtn->paramTypes()->arity() == 1 && 
          (mtn->paramTypes()->child(0)->typeIdentNM(fld.type()) ||
           fld.type()->isPointType() || fld.type()->isRectDomainType())) {
        assert(mdn->returnType()->typeIdentNM(theBoolType));
        assert((mdn->flags() & Common::Public) && 
               (mdn->flags() & (Common::Sglobal|Common::Abstract)) == 0);
        eqm = (MethodDecl*)&*decl; break;
      }
    }
    string eqmethod;
    if (eqm)
      eqmethod = eqm->cMethodNameStatic();
    else { // default comparison
      if (fieldCompEquals) eqmethod = MANGLE_CLASS_EQUALS(+, fld.type()->cType());
      else                 eqmethod = MANGLE_CLASS_NEQUALS(+, fld.type()->cType()); 
    }

    os << comb << eqmethod << "(s1." << fld.cFieldName() 
       << ", s2." << fld.cFieldName() << ")";
  } else {
    fatal_error("unknown type in default immutable equals operator");
  }
}

void externStaticFieldDecl(FieldDecl &fld, CfCode& os)
{
    os << "extern ";
    staticFieldDecl(fld, os);
}

void tableDefn(MethodDecl &method, ostream& os)
{
    if (method.modifiers() & Common::Abstract)
	os << 0;
    else
	os << method.cMethodNameStatic();
    os << ",\n";
}

extern string stringifyTypeFlags(ClassDecl *cl) {
  Common::Modifiers m = cl->modifiers();
  string s = "";

  if (m & Common::Public)    s = s + (s.size()?" | ":"") + "typeflag_Public";
  if (m & Common::Private)   s = s + (s.size()?" | ":"") + "typeflag_Private";
  if (m & Common::Protected) s = s + (s.size()?" | ":"") + "typeflag_Protected"; 
  if (m & Common::Final)     s = s + (s.size()?" | ":"") + "typeflag_Final";     
  if (m & Common::Immutable) s = s + (s.size()?" | ":"") + "typeflag_Immutable"; 
  if (m & Common::Strictfp)  s = s + (s.size()?" | ":"") + "typeflag_Strictfp";  
  if (m & Common::Abstract)  s = s + (s.size()?" | ":"") + "typeflag_Abstract";
 
  if (s.size()) return string("(TypeFlags)( ") + s + " )"; 
  return "typeflag_None";
}

bool implements (Decl* aClass, Decl* interface);

void emitDefinitions(ClassDecl &cl, CfHeader &hFile, CfSource &cFile )
{
    // For some reason, Object lists Object as its superclass.  :-(
    ClassDecl * const super = (&cl == ObjectDecl ? 0 : cl.superClass());
    
    const string superDescName = super ? super->cDescriptorName() : string("");
/*
    const CtType &superDescType = super
	? static_cast< const CtType & >(super->cDescriptorType())
	: static_cast< const CtType & >(CtObjectDescriptor::classHeader);
*/
    
    const CtType &classDescType = cl.cDescriptorType();
    const string classDescName = cl.cDescriptorName();
    const string classStaticFieldsStructName = cl.cStaticFieldsStructName();
    const CtType &className    = cl.cType();
    const string nullifier     = cl.cNullifyLocalName();
    const string typeFlags = stringifyTypeFlags(&cl);
    
    const bool isImmutable = cl.asType()->isImmutable();

    string newInstance = "NULL";

    if (!isImmutable) {
       /* look for a public, zero-argument constructor */
       foriter (decl, cl.environ()->lookupFirstProper(cl.name(), Decl::Constructor), EnvironIter) {
           if ((decl->modifiers() & Common::Public) && 
              decl->source()->params()->arity() == 0) 
           newInstance = decl->cMethodNameStatic();
       }
    }

    // Other classes upon which we depend
    {
	cl.includeSupers( hFile );
	
	cl.includeSelf( cFile );
	cl.includeRequirements( cFile );
    }

    // Instance fields
    className.define( hFile );

    // Class descriptor
    {
	classDescType.define( hFile );
	hFile << "extern " << classDescType << ' ' << classDescName << ";\n";

	classDescType.define( cFile );
	const char *interfaceList = cl.emitInterfaceList( cFile );
	cFile << classDescType << ' ' << classDescName << " = {\n"
              << "  { &" << JavaLangClassDecl->cDescriptorName() << " },\n"
	      << "  NULL,\n";

	if (isImmutable) {
	    cFile << "  Value,\n"
                  << "  " << typeFlags << ",\n"
		  << "  sizeof( " << className << " ),\n";
	} else {
	    cFile << "  Class,\n"
                  << "  " << typeFlags << ",\n"
		  << "  " << interfaceList << ",\n";
            cFile << "  (void (**)())" << cl.cIntfMTName() << ",\n";
	    if (super)
		cFile << "  &" << superDescName << ",\n";
	    else
		cFile << "  0,\n";
	    
	    cFile << "  sizeof( " << className << " ),\n"
		  << "  " << nullifier << ",\n"
                  << "  " << newInstance << ",\n";
	    
	    emitInstanceMethods(&cl, &cl, tableDefn, cFile);
	}
	cFile << "};\n\n";
    }

    // Interface Method Table
    if (!isImmutable) {
	hFile << "extern void (*" << cl.cIntfMTName() + "[])();\n\n";

	EmitIntfMT(cl, cFile);
    }

    // Static fields
    {
      hFile << "struct " << classDescName << "_static_fields_struct {\n"
	    << "#ifdef HAVE_MONITORS\n"
	    << "  tic_monitor_t monitor;\n"
	    << "#endif /* HAVE_MONITORS */\n";
      emitStaticFields(cl, staticFieldDecl, hFile);

      // some linkers choke if we try to declare struct variables with zero size,
      // so make sure we have at least one byte in here:
      hFile << "char _pad; /* padding to prevent zero-size structs */\n";

      hFile << "};\n";
      
      hFile << "extern struct " << classDescName << "_static_fields_struct " 
	    << "STATIC_DEF(" << classStaticFieldsStructName << ");\n";

      cFile << "struct " << classDescName << "_static_fields_struct " 
	    << "STATIC_DEF(" << classStaticFieldsStructName << ");\n";
      
    }

    // Generate an equals method
    if (isImmutable) {
        hFile << "extern int " << MANGLE_CLASS_EQUALS(<<, className) << "("
	      << cl.asType()->cType() << ", "
	      << cl.asType()->cType() << ");\n";
        hFile << "extern int " << MANGLE_CLASS_NEQUALS(<<, className) << "("
	      << cl.asType()->cType() << ", "
	      << cl.asType()->cType() << ");\n";
        fieldCompEquals = 1; 
	cFile << "int " << MANGLE_CLASS_EQUALS(<<, className) << "("
	      << cl.asType()->cType() << " s1, "
	      << cl.asType()->cType() << " s2) {\n"
	      << "return (1";
	emitInstanceFields(&cl, fieldComp, cFile);
	cFile << ");\n"
	      << "}\n";
        fieldCompEquals = 0; 
	cFile << "int " << MANGLE_CLASS_NEQUALS(<<, className) << "("
	      << cl.asType()->cType() << " s1, "
	      << cl.asType()->cType() << " s2) {\n"
	      << "return (0";
	emitInstanceFields(&cl, fieldComp, cFile);
	cFile << ");\n"
	      << "}\n";
    }

    // Local field nullifier, used when cloning
    {
	hFile << "void " << nullifier << "(" << className << " *);\n";
	cFile << "void " << nullifier << "(" << className << " *"
	      << MANGLE_THIS_VAR(<<) << ") {\n";
	emitInstanceFields( &cl, fieldNullifyLocal, cFile );
	cFile << "}\n";
    }

   // detect & warn about local field nullification on clone()
   if (!cl.asType()->isImmutable() && implements(&cl, CloneableDecl)) {
     bool containsLPs = false;
     foriter (field, cl.environ()->allDecls( Decl::Field ), EnvironIter) {
       const FieldDecl &fieldDecl = static_cast< FieldDecl & >( *field );
       if (fieldDecl.containsEmbeddedLocals()) containsLPs = true;
     }
     if (containsLPs) 
       cl.source()->warning("local-field-clone") 
                << "Class " << cl.errorName()
                << " contains local fields and implements Cloneable.\n"
                << "  Local fields will be nullified by Object.clone()\n";
   }

}


template< class Iterator >
static void declareAll( CfCode &os, Iterator begin, const Iterator end )
{
    while (begin < end) {
	TreeNode *method = *begin++;
	if (!method->absent()) {
	    MethodDecl &decl = static_cast< MethodDecl & >(*method->decl());
	    assert( decl.category() & (Decl::Constructor | Decl::Method) );	    
	    methodDecl( decl, os );
	}
    }
    os << '\n';
}

template< class Container > inline
static void declareAll( CfCode &os, const Container &container )
{
    ::declareAll( os, container.begin(), container.end() );
}

extern void resetPerFileTempCounters() { 
    // this function resets counters used to generate unique temporary names
    // we do this when starting each source file to 
    // prevent a change in one source file propagate insignificant naming changes into
    // other source files, thus reducing recompilation of unchanged source files

    // reset the temporary counter in ExprNode
    ExprNode::resetTemporary();
    MonitorFetchNode::resetGenerator();

    // reset the temporary count in code-alloc.cc
    extern int initTempNum;
    initTempNum = 0;

    // reset the temporary count in code-foreach.cc
    extern void reset_foreach_counters();
    reset_foreach_counters();

    // reset the local variable temporary count in code-decl.cc
    extern int VarDeclTempNum;
    VarDeclTempNum = 0;
  }

TiPragma CompileUnitNode::pragma() { return _pragma; }

void ClassDeclNode::codeGen()
{
//    voidResultsOfBlockStatements = true;
    
    resetPerFileTempCounters(); // reset temp counters when starting each source file to 
                                // prevent spurious recompilation of unchanged source files

    bool hasNatives = false;

    const CtType &longName = decl()->cType();
    const string classStaticFieldsStructName = decl()->cStaticFieldsStructName();

    // PR587 - disable bounds checking on ti.* libraries 
    TreeNode *cun = parent(); 
    while (!isCompileUnitNode(cun)) cun = cun->parent();

    string cun_defines = "";
    if (((CompileUnitNode*)cun)->pragma().force_nobcheck ) 
      cun_defines += "#define BOUNDS_CHECKING 0\n";

    if (((CompileUnitNode*)cun)->pragma().no_srcpos ) 
      cun_defines += "#define TI_NO_SRCPOS\n";

    CfHeader hFile( longName );    
    CfSource cFile( longName, cun_defines );

    hFile << "\n/* ***** " << decl()->fullName() << " generated header file ***** */\n\n";
    cFile << "\n/* ***** " << decl()->fullName() << " generated source file ***** */\n\n";

    emitDefinitions(*decl(), hFile, cFile);

    // group members according to where their code goes
    vector< TreeNode * > fields, methods;
	
    foriter (member, members () -> allChildren (), ChildIter) {
	TreeNode * const node = *member;
	vector< TreeNode * > *category = 0;
	    
	if (isFieldDeclNode(node)) {
	    const FieldDeclNode * const fieldDecl =
		static_cast< const FieldDeclNode * >( node );
	    if (fieldDecl->decl()->modifiers() & Static)
	        category = 0; // field inits already lowered into static initializer
	    else
		category = &fields;
	} else if (isStaticInitNode(node))
	    category = 0;
	else if (!node->absent()) {
	    category = &methods;
	    if (node->decl()->modifiers() & Native)
	      hasNatives = true;
	}

	if (category) category->push_back( node );
    }

    // forward declare the string table, currently of unknown size
    cFile.declare( cFile );

    // now put each bit of code in its proper place

#if 0 // object instance initializers are handled by lowering now  
    TypeNode &type = *decl()->asType();
    // first, object instance initializers
    // this needs to be externally visible to support constructor inlining
    cFile << "\n/* Object instance field initializer */\n";
    if (type.isImmutable()) {
      hFile << "\nextern void " << decl()->cInitFieldsName()
	          << "(" << decl()->cType() << " *" << ");\n";
      cFile << "void " << decl()->cInitFieldsName()
	          << "(" << decl()->cType() << " *" << MANGLE_THIS_VAR(<<) << ")\n";
      }
    else {
      const CtType &rawType = decl()->cType();
      const CtType &boxedType = ctBox( rawType, true ); 
      hFile << "\nextern void " << decl()->cInitFieldsName()
	          << "(" << boxedType << ");\n";
      cFile << "void " << decl()->cInitFieldsName()
	          << "(" << boxedType << " " << MANGLE_THIS_VAR(<<) << ")\n";
      }
    {
	CodeContext subcontext( cFile );
	EncapsulateInits(fields)->emitStatement(subcontext);
    }
    cFile << '\n';
#endif

    hFile << "extern void " << MANGLE_CLASS_INIT(<<, longName) << "();\n";
    cFile << "static void " << MANGLE_CLASS_BUILDST(<<, longName) << "();\n";
    cFile << "\n/* --- " << decl()->fullName() << " Class Initializer --- */\n\n";
    cFile << "#undef __TI_CURRENT_FUNCTION__\n";
    cFile << "#define __TI_CURRENT_FUNCTION__ \"" << decl()->fullName() << ".<clinit>\"\n";
    cFile << "void " << MANGLE_CLASS_INIT(<<, longName) << "() {\n";
    cFile << "TI_BEGIN_FUNCTION\n";
    {
	CodeContext subcontext( cFile );
 
   #if 0
     /* PR809: It's unsafe to init the class object monitor here, because static initializers 
          running concurrently on other threads may be using it. Luckily, this is completely
          unnecessary anyhow thanks to automatic clearing of static storage, and the fact that
          monitor_init just nullifies the monitor pointer.
      */
	subcontext << "#ifdef HAVE_MONITORS\n"
		   << "monitor_init( &STATIC_REF(" 
		   << classStaticFieldsStructName << ", monitor ));\n"
                   << "if (MYBOXPROC == 0) "
		   << "monitor_init( &" << decl()->cDescriptorName() << ".class_object.monitor);\n"
		   << "#endif /*HAVE_MONITORS*/\n";
   #endif
	subcontext << MANGLE_CLASS_BUILDST(<<, longName) << "();\n";
        subcontext << "if (MYBOXPROC == 0) "
                   << decl()->cDescriptorName() << ".class_name = java_string_build_8(\""
                   << decl()->fullName() << "\");\n";
        subcontext << "if (MYBOXPROC == 0) "
                   << "ti_register_class((type_header*)&" << decl()->cDescriptorName() << ");\n";

        // must precede explicit class inits for library Integer.TYPE field
        subcontext << "TO_GLOBALB_STATIC( STATIC_REF(" << classStaticFieldsStructName << ","
                   << MANGLE_FIELD(<<, string("class"), longName) << "), 0, "
                   << "&(" << decl()->cDescriptorName() << ".class_object));" << endCline;

	// Static inits have already been encapsulated into child 0 in lowering.
	(static_cast<BlockNode*>(members()->child(0)->block()))->emitStatement(subcontext);
    }
    cFile << "}\n\n";

    if (hasNatives && !isDomainOrtiDomainType(*decl()->asType()))
	cFile << "\n\n#include \"" << decl()->cNativeName() << "\"\n";

    cFile << '\n';

    declareAll( hFile, methods );
    codeGenAll( cFile, methods );

    cFile << "\n/* --- " << decl()->fullName() << " Class String-table builder --- */\n\n";
    cFile << "#undef __TI_CURRENT_FUNCTION__\n";
    cFile << "#define __TI_CURRENT_FUNCTION__ \"" << decl()->fullName() << ".<string_table_builder>\"\n";
    cFile << "static void " << MANGLE_CLASS_BUILDST(<<, longName) << "() {\n";
    cFile << "TI_BEGIN_FUNCTION\n";
    {
      CodeContext context( cFile );
      cFile.internAll( context );
    }
    cFile << "}\n\n";
}

const string locComment(TreeNode *t)
{
  static SourcePosn prevPosition;
  const SourcePosn position = t->position();
  
  if (!position.unknown()
      && (position.file != prevPosition.file
	  || position.posn != prevPosition.posn)) {
    prevPosition = position;
    return "/* " + position.asString() + " */ ";
  }
  return "";
}


				/* TreeNode */

void TreeNode::codeGen()
{
}

void TreeNode::codeGen( CfSource & )
{
  undefined( "codeGen( CfSource & )" );
}

void TreeNode::codeGen( CodeContext &context )
{
  foriter (p, allChildren(), ChildIter)
    (*p)->codeGen( context );
}


void CompileUnitNode::codeGen()
{
  if (selectedForCodeGen(false))
    foriter (type, types()->allChildren(), ChildIter)
      if ((*type)->selectedForCodeGen(false))
	(*type)->codeGen();
}

bool CompileUnitNode::selectedForCodeGen(bool force_libs) const
{
  const TreeNode &pack = *package();

  if (pack.absent())
    return true;
  else {
    const string name = pack.decl()->fullName();
    if (name == "ti.internal") return false;
    else if (codeGen_libs || force_libs) return true;
    else if (isInLibrary(pack.decl())) return false;
    else return true;
  }
}


bool TemplateDeclNode::selectedForCodeGen( bool ) const
{
  return false;
}


bool ClassDeclNode::selectedForCodeGen(bool) const
{
  if (decl()->fullName().find("ti.domains.tiPoint") == 0) return false;
  else return true;
}

bool TitaniumArrayTypeNode::selectedForCodeGen(bool force_libs) const
{
  if (codeGen_libs || force_libs) return true;

  // don't regenerate those which appear in tlib.java
  if (elementType()->isPrimitive() && tiArity() <= 3) return false;  
  if (elementType()->isPointType() && tiArity() == 1) return false;
  if (elementType()->isRectDomainType() && tiArity() == 1) return false;

  return true;
}

extern char *currentFilename;  // used for -dumpast switch
extern string tcCompilerFlags;

static void findDependencies();
static llist<ClassDecl *> *libraryOrder = NULL;
static llist<ClassDecl *> *userOrder = NULL;

void backend()
{
    extern void createDomains_h();
    extern void initPolys();

    findDependencies();

    initPolys();

    CreateIntfMethods();
    // Generate the .c and .h files for each class
    compile_status(1,"Code generation & optimization...");
    foreach (f, llist<CompileUnitNode *>, *allFiles) {
      currentFilename = (char *)((*f)->ident()->c_str());
      if ((*f)->selectedForCodeGen(false)) 
         compile_status(2, string("generating/optimizing: ") + currentFilename);
      (*f)->codeGen();
    }

#if 0
    foreach (instance, llist<TreeNode *>, *templateEnv.allInstances())
      {
	const TreeNode &node = **instance;
	Decl &decl = *node.decl();
	TypeNode &type = *decl.asType();
	type.codeGen();
      }
#endif

      compile_status(1,"Generating ti-main...");
      // Generate a main.c file that pulls all together

      string s;
      string filebase = (codeGen_main ? "main" : "tlib");
      CfSource mainFile("ti-"+filebase, "#define TI_NO_SRCPOS\n"); // ensure correct startup barrier tracing

      compile_status(2,"Generating static data and class initializers...");
      foreach (f, llist<CompileUnitNode *>, *allFiles) {
	TreeNode *const pack = (*f)->package();
	if (!pack->absent() && pack->decl()->fullName() == "ti.internal")
	  continue;
	   
        if (!(*f)->selectedForCodeGen(false)) continue;
 
	// Spit out include directives
	foriter (type, (*f)->types()->allChildren(), TreeNode::ChildIter)
	  if ((isClassDeclNode(*type) || isInterfaceDeclNode(*type))
	      && (*type)->selectedForCodeGen(false)) // filter out tiPoint[1..MAX_TIARITY]
	    (*type)->decl()->includeSelf( mainFile );
      }

    if (codeGen_main) {
      mainFile << "#include \"ti-main.h\"\n";

      string quoted_tcCompilerFlags = tcCompilerFlags;
      string tcbuildFlags;
      if (getenv("TCBUILD_FLAGS")) tcbuildFlags = getenv("TCBUILD_FLAGS");

      // quote anything that would cause problems in a C string
      for (string::size_type i = tcbuildFlags.find_first_of("\'\"\\") ;
           i != string::npos;
           i = tcbuildFlags.find_first_of("\'\"\\", i+1)) {
        tcbuildFlags.insert(i,"\\");
        i++;
      } 
      for (string::size_type i = quoted_tcCompilerFlags.find_first_of("\'\"\\") ;
           i != string::npos;
           i = quoted_tcCompilerFlags.find_first_of("\'\"\\", i+1)) {
        quoted_tcCompilerFlags.insert(i,"\\");
        i++;
      } 

      /* embed a uniqueID in each executable - this forces ti-main to get recompiled
         despite caching (so the compiletime stamp is always correct) and provides
         an easy way to differentiate two similar executables that might otherwise be copies
      */
      char uniqueID[255];
      uniqueID[0] = '\0';
      srand((int)time(NULL));
      for (int i=0; i<8; i++) { // 8 pseudorandom bytes
        char temp[4];
        sprintf(temp,"%02x", (rand()&0xFF));
        strcat(uniqueID, temp);
      }

      /* these variables must be nonstatic, otherwise craycc will optimize
       * them away and they won't be embedded in the compiled application
       * must be extern or non-const or AIX linker will optimize them away
       * DOB: use TI_IDENT() instead, which is tuned for all the compiler subtleties
       */
      mainFile << "int titaniumCompilerMajorVersion = " << tcMajorVersion << ";\n"
	       << "int titaniumCompilerMinorVersion = " << tcMinorVersion << ";\n"
        "TI_IDENT(titaniumCompilerWhatString, \"" << tcWhatString << "\");\n"
        "TI_IDENT(identVersion, \"$TitaniumVersion: " << tcMajorVersionStr << "." << tcMinorVersionStr << " $\");\n"
        "TI_IDENT(identTcbuildFlags, \"$TitaniumTcbuildFlags: " << tcbuildFlags << " $\");\n"
        "TI_IDENT(identCompilerFlags, \"$TitaniumCompilerFlags: " << quoted_tcCompilerFlags << " $\");\n"
        "const char *tcCompilerFlags = \"" << quoted_tcCompilerFlags << "\";\n"
        "TI_IDENT(identCompileTime, \"$TitaniumCompileTime: \"__DATE__ \" \" __TIME__\" $\");\n"
        "TI_IDENT(identUniqueID, \"$TitaniumUniqueID: " << uniqueID << " $\");\n"
	"\n\n";
    }

      ostringstream staticDataAlloc;
      ostringstream libraryClassInit, userClassInit;
      staticDataAlloc << "\n\n#define ALL_STATICS(FN) \\\n";

      // Call class initialization functions
      // We ensure that user initializers run after library initializers
      // We also ensure that library and user initializers each run in topological order
      // of dependencies
      // This is still not quite the Java class initialization semantics

      foreach (d, llist<ClassDecl *>, *libraryOrder) {
	if ((*d)->source()->selectedForCodeGen(false)) {
	  ClassDecl &decl = **d;
	  staticDataAlloc << " FN("
			  << "struct " << decl.cDescriptorName() << "_static_fields_struct"
			  << ", " 
			  << decl.cStaticFieldsStructName() 
			  << ") \\\n";
	  libraryClassInit << "  " << MANGLE_CLASS_INIT(<<, decl.cType()) << "();\n";
	}
      }

      foreach (d, llist<ClassDecl *>, *userOrder) {
	if ((*d)->source()->selectedForCodeGen(false)) {
	  ClassDecl &decl = **d;
	  staticDataAlloc << " FN("
			  << "struct " << decl.cDescriptorName() << "_static_fields_struct"
			  << ", " 
			  << decl.cStaticFieldsStructName() 
			  << ") \\\n";
	  userClassInit << "  " << MANGLE_CLASS_INIT(<<, decl.cType()) << "();\n";
	}
      }

      mainFile << staticDataAlloc.str() << "\n\n\n";

      mainFile << "\nvoid ti_"<<filebase<<"_staticinit() {\n";
      mainFile << "  STATIC_INIT(ALL_STATICS);\n";
      mainFile << "}\n\n";

    if (codeGen_libs) {
      mainFile << "void ti_tlib_classinit() {\n";
      mainFile << "  ti_trace_enterregion(\"tlib-init\");\n";
      mainFile << "  value_desc_init();\n"; // needs to precede library init because of Integer.TYPE
      mainFile << "  _TI_INIT_MRAD_EMPTY_CACHE();\n"; // needs to precede library init to ensure correct MRAD.emptyDomain()
      mainFile << "\n  /* Run library class initializers */\n";
      mainFile << libraryClassInit.str();
      mainFile << "  ti_trace_leaveregion(\"tlib-init\");\n";
      mainFile << "}\n";
    } else {
      mainFile << "void ti_tlib_staticinit();\n";
      mainFile << "void ti_tlib_classinit();\n";
    }

    if (codeGen_main) {
      mainFile << "\n\nvoid ti_main(int argc, char **argv) {\n";
      /* Debug information */
      emitStackDebugInformation(mainFile);
      mainFile <<
	"  init_memory_tally();\n"
	"  gp_trace_open();\n";

      mainFile << "\n  /* Initialize static storage */\n";
      if (!codeGen_libs) mainFile << "  ti_tlib_staticinit();\n"; /* pickup tlib init */
      mainFile << "  ti_"<<filebase<<"_staticinit();\n";
      mainFile << "\n  /* Run library class initializers */\n";
      mainFile << "  ti_tlib_classinit();\n"; /* pickup tlib init */
      mainFile << "\n  /* Run user class initializers */\n";
      mainFile << userClassInit.str();
      mainFile << "\n";

      const MethodDecl &mainMethod = **mainMethods.begin();

      // post-init gc so we start with a clean slate
      mainFile << "  ti_gc();\n";

      // pause processes after initialization
      mainFile << "  ti_set_srcpos(\"_STARTUP\",0);\n"
               << "  barrier();\n"
	       << "  " << mainMethod.cMethodNameStatic()
	       << "(java_strings_build(argc - 1, argv + 1));\n"
               << "  ti_set_srcpos(\"_STARTUP\",0);\n"
	       << "  barrier();\n"
	       << "  gp_trace_close();\n"
	       << "  print_memory_tally();\n"
	       << "}\n";

      /* Debug information */
      emitStaticDebugInformation(mainFile, mainMethod);
    }
    
    // Create arrays.h and arrays.c
    compile_status(2,"Instantiating Titanium arrays...");
    instantiateArrays();
    
    // Create type headers
    if (!codeGen_libs && tlib_include_dir.size()) { // init the tlib include cache
        compile_status(2,"Scanning library type headers...");
        DIR *d = opendir(tlib_include_dir.c_str());
        if (!d) perror("opendir");
        else {
          struct dirent *de;
          while ((de = readdir(d)) != NULL) {
            CfLayout::tlib_include_files.insert(string(de->d_name));
          }
          if (closedir(d)) perror("closedir");
        }
    }
    compile_status(2,"Creating novel type headers...");
    CtType::elaborateAll();

    if (CfLayout::tlib_include_files.count("domains.h") == 0) {
      // Create domains.h
      compile_status(2,"Generating domains.h...");
      createDomains_h();
    }
}

/* The following is an overview of the algorithm for ordering static inits:

1. Create a weighted graph of dependencies between classes and methods. The
following result in dependencies:
  * In a static initializer:
    - A static field access results in a very strong dependency (100) between 
      the current class and the target class
    - An object field access results in a very weak dependency (5) between the
      current class and the target class
    - A method call results in a strong dependency (20) between the current 
      class and the target method, and a very weak dependency (5) between the 
      current class and the target class
    - An allocation results in a very weak dependency (2) on the target type
      (this is mainly because the allocation is always followed by a call to
       a constructor, which results in the method call dependencies above)
    - A string literal node results in a very strong dependency (50) on the
      String class
  * In a method/constructor:
    - A static field access results in a very strong dependency (100) between 
      the current method and the target class
    - An object field access results in a very weak dependency (5) between the
      current method and the target class
    - A method call results in a strong dependency (20) between the current 
      method and the target method, and a very weak dependency (5) between the 
      current method and the target class
    - An allocation results in a very weak dependency (2) on the target type
      (this is mainly because the allocation is always followed by a call to
       a constructor, which results in the method call dependencies above)
    - A string literal node results in a very strong dependency (100) on the 
      enclosing class and a very strong dependency (50) on the String class
  * Abstract methods
    - A weak dependency (8) between the method and its implementers is added
      (currently, this is only done for abstract methods, but if necessary, it
       is reasonable to do the same with normal methods and their overriders)

2. Find the SCCs of the dependency graph.

3. For any SCC containing more than a single type:
   a. Remove all edges of the minimum weight remaining in the graph
   b. Recursively do step 2-3

4. Initialize the types in topological order of their SCCs.

The code still enforces that all library initializers occur before any user
initializers. The dependencies and their weights are heuristics, though, so it
could break later on with the addition of more classes. In that case, the
heuristics can be tweaked, and as a last resort, manually provided
dependencies can be used, with very high edge weights. But for now, it all
seems to work fine.

See PR285 for more discussion on this issue. */

typedef set< Decl *, less< Decl * > > DeclSet;
typedef pair< Decl *, int > DeclInt;
typedef set< DeclInt > DeclIntSet;

const int MaxEdgeWeight = 500;

DeclIntSet *Decl::initDepends() {
  invalidOperation("initDepends");
  return NULL;
}

void Decl::initDepends(Decl *, int) {
  invalidOperation("initDepends");
}

DeclIntSet *Decl::dependsOnInit() {
  invalidOperation("dependsOnInit");
  return NULL;
}

void Decl::dependsOnInit(Decl *, int) {
  invalidOperation("dependsOnInit");
}

void ClassDecl::initDepends(Decl *d, int i) {
  if (d != this) {
    _initDependencies.insert(DeclInt(d, i));
    d->dependsOnInit(this, i);
  }
}

void ClassDecl::dependsOnInit(Decl *d, int i) {
  if (d != this) {
    _dependenciesOnInit.insert(DeclInt(d, i));
  }
}

void MethodDecl::initDepends(Decl *d, int i) {
  if (d != this) {
    _initDependencies.insert(DeclInt(d, i));
    d->dependsOnInit(this, i);
  }
}

void MethodDecl::dependsOnInit(Decl *d, int i) {
  if (d != this) {
    _dependenciesOnInit.insert(DeclInt(d, i));
  }
}

void TreeNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  for (int i = 0; i < arity(); i++)
    child(i)->findInitDependencies(cd, allTypes, allDecls);
}

void CompileUnitNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  TreeNode *const pack = package();
  if ((!pack->absent() && pack->decl()->fullName() == "ti.internal") ||
      !selectedForCodeGen(false))
    return;
  types()->findInitDependencies(cd, allTypes, allDecls);
}

void TemplateDeclNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  return;
}

void ClassDeclNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  allTypes->insert(decl());
  allDecls->insert(decl());
  members()->findInitDependencies(decl(), allTypes, allDecls);
}

void InterfaceDeclNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  allTypes->insert(decl());
  allDecls->insert(decl());
  members()->findInitDependencies(decl(), allTypes, allDecls);
}

void MethodDeclNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  allDecls->insert(decl());
  TreeNode::findInitDependencies(decl(), allTypes, allDecls);
}

void MethodSignatureNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  // add weak dependencies from abstract method to implementers
  if (!(flags() & (Native | CompilerGenerated))) {
    allDecls->insert(decl());
    foreach (d, MethodSet, *decl()->overriders())
      decl()->initDepends(*d, 8);
  }
}

void ConstructorDeclNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  allDecls->insert(decl());
  TreeNode::findInitDependencies(decl(), allTypes, allDecls);
}

void FieldDeclNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  return;
}

void InstanceInitNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  return;
}

void ObjectFieldAccessNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  if ((decl()->modifiers() & Static) && (decl()->category() == Decl::Field)) {
    // add very strong dependency on container for static field
    cd->initDepends(simpName()->decl()->container(), 100);
    return;
  } else if (decl()->category() != Decl::Field) {
    cd->initDepends(simpName()->decl(), 20);
    allDecls->insert(decl());
  }
  // add very weak dependency on container type
  cd->initDepends(simpName()->decl()->container(), 5);
}

void TypeFieldAccessNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  if (decl()->category() != Decl::Field) {
    cd->initDepends(simpName()->decl(), 20);
    // add very weak dependency on container type
    cd->initDepends(simpName()->decl()->container(), 5);
    allDecls->insert(decl());
  } else {
    // add very strong dependency on container for static field
    cd->initDepends(simpName()->decl()->container(), 100);
  }
}

void AllocateSpaceNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  // add very weak dependency on target type
  cd->initDepends(dtype()->decl(), 2);
}

void StringLitNode::findInitDependencies(Decl *cd, DeclSet *allTypes, DeclSet *allDecls) {
  if (cd->category() & (Decl::Method | Decl::Constructor))
    // add very strong dependency on container
    cd->initDepends(cd->container(), 100);
  // add strong dependency on java.lang.String
  cd->initDepends(StringDecl, 50);
}

static void sccDfsForward(Decl *cd, DeclSet *scc, DeclSet *seen, llist<Decl *> *&lst, int ignore) {
  if (seen->find(cd) != seen->end())
    return;
  else if (scc->find(cd) == scc->end())
    return;
  seen->insert(cd);
  foreach (d, DeclIntSet, *cd->initDepends()) {
    if ((*d).second > ignore)
      sccDfsForward((*d).first, scc, seen, lst, ignore);
  }
  lst = cons(cd, lst);
}

static void sccDfsBackward(Decl *cd, DeclSet *scc, DeclSet *lst, DeclSet *seen, int ignore, int &minEdgeWeight) {
  if (seen->find(cd) != seen->end())
    return;
  else if (scc->find(cd) == scc->end())
    return;
  seen->insert(cd);
  lst->insert(cd);
  foreach (d, DeclIntSet, *cd->dependsOnInit()) {
    if ((*d).second > ignore) {
      if ((*d).second < minEdgeWeight) minEdgeWeight = (*d).second;
      sccDfsBackward((*d).first, scc, lst, seen, ignore, minEdgeWeight);
    } 
  }
}

static int numTypes(DeclSet *ds, Decl *&res) {
  int i = 0;
  foreach (d, DeclSet, *ds) {
    if ((*d)->category() & (Decl::Class | Decl::Interface)) {
      i++;
      res = *d;
    }
  }
  return i;
}

static void handleScc(DeclSet *scc, int ignore, DeclSet *all) {
  llist<Decl *> *fres = NULL;
  DeclSet *seen = new DeclSet();
  foreach (d, DeclSet, *scc)
    sccDfsForward(*d, scc, seen, fres, ignore);
  seen->clear();
  for (llist<Decl *> *crnt = fres; crnt != NULL; crnt = crnt->tail()) {
    DeclSet *newScc = new DeclSet();
    int minEdgeWeight = MaxEdgeWeight;
    sccDfsBackward(crnt->front(), scc, newScc, seen, ignore, minEdgeWeight);
    Decl *d;
    int i = numTypes(newScc, d);
    if (i == 1) {
      if ((d->category() & (Decl::Class | Decl::Interface)) &&
	  all->find(d) != all->end()) {
	if (isInLibrary(d))
	  libraryOrder = cons((ClassDecl *) d, libraryOrder);
	else
	  userOrder = cons((ClassDecl *) d, userOrder);
      }
    } else if (i > 1) {
      handleScc(newScc, minEdgeWeight, all);
    }
    delete newScc;
  }
  delete fres;
  delete seen;
}

static void findDependencies() {
  DeclSet *allTypes = new DeclSet();
  DeclSet *allDecls = new DeclSet();
  foreach (f, llist<CompileUnitNode *>, *allFiles)
    (*f)->findInitDependencies(NULL, allTypes, allDecls);
  handleScc(allDecls, 0, allTypes);
}