Random stuff.

[polintos/scott/priv.git] / idlcomp / idlc.h

// idlc.h -- Definitions used throughout idlc. 
// A lot of this should probably be factored out into more specific headers.
//
// This software is copyright (c) 2006 Scott Wood <scott@buserror.net>.
// 
// This software is provided 'as-is', without any express or implied warranty.
// In no event will the authors or contributors be held liable for any damages
// arising from the use of this software.
// 
// Permission is hereby granted to everyone, free of charge, to use, copy,
// modify, prepare derivative works of, publish, distribute, perform,
// sublicense, and/or sell copies of the Software, provided that the above
// copyright notice and disclaimer of warranty be included in all copies or
// substantial portions of this software.

#ifndef IDLC_H
#define IDLC_H

// inttypes.h on OSX assumes it can use restrict, but C++ doesn't have it.
// Hopefully C++ will catch up to C soon...

#define restrict

#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>
#include <ctype.h>
#include <string>
#include <stack>
#include <list>
#include <map>
#include <vector>
#include <cstring>

#include "compileddef.h"

using std::list;
using std::stack;
using std::string;
using std::pair;
using std::map;
using std::vector;

int yylex();
int idl_lex();
#define cdl_lex idl_lex
void idl_error(const char *s);

#define cdl_error idl_error

void setup_idlparse();
void setup_cdlparse();

#ifdef __GNUC__
void yyerrorf(const char *s, ...) __attribute__((format(printf, 1, 2)));
void yyerrorfl(const char *file, int line, const char *s, ...)
__attribute__((format(printf, 3, 4)));
#else
void yyerrorf(const char *s, ...);
void yyerrorfl(const char *file, int line, const char *s, ...);
#endif

int idl_parse();
int cdl_parse();
int finish_lex();

extern int idl_debug, cdl_debug, curline, impl, num_err;
extern int current_pass;
extern FILE *yyin;
extern unsigned int enum_pos;
extern const char *cur_input_file;
extern int compiling_idl, compiling_cdl;
extern bool makedep;

struct InternalError
{
        // Location in the IDLC source of the BUG()
        const char *file;
        int line;
        
        InternalError(const char *file, int line) :
        file(file), line(line)
        {
        }
};

#define BUG() do { \
        throw InternalError(__FILE__, __LINE__); \
} while (0)

#undef assert

#define assert(x) do { \
        if (!(x)) BUG(); \
} while (0)

class Releasable {
public:
        mutable int count;
        
        virtual ~Releasable()
        {
        }
        
        Releasable(int COUNT) : count(COUNT)
        {
        }

        void release() const
        {
                if (count <= 0) {
                        fprintf(stderr, "Reference count is %d in release\n", count);
                        BUG();
                }   
                
                if (!--count)
                        delete this;
        }
};

class AutoReleasePool {
        list<const Releasable *> pool;

public:
        void add(const Releasable *obj)
        {
                pool.push_back(obj);
        }
        
        void clean()
        {
                for (list<const Releasable *>::iterator i = pool.begin();
                     i != pool.end(); ++i)
                {
                        const Releasable *obj = *i;
                        obj->release();
                }
                
                pool.clear();
        }
};

extern AutoReleasePool autorelease_pool;

template <typename T>
class RefCountable : public Releasable {
private:
        // RefCountable objects should never be assigned to,
        // as there could be references to the object remaining.
        // The private assignment operator prevents this, unless
        // a subclass defines its own assigment operator (don't
        // do that).
        void operator =(const RefCountable &rc)
        {
                BUG();
        }

        RefCountable(const RefCountable &rc) : Releasable(1)
        {
                BUG();
        }
        
public:
        RefCountable() : Releasable(1)
        {
                // Normally, this wouldn't be automatic, but this is what most
                // things in IDLC are going to want, and it elimanates problems
                // with needing to cast the return type of autorelease().
                //
                // The automatic autorelease() means that all refcountable objects
                // must be allocated with "new", not on the stack, as global
                // data, or as a class member.
                
                autorelease();
        }
        
        virtual ~RefCountable()
        {
        }

        const T *retain() const
        {
                if (count <= 0) {
                        fprintf(stderr, "Reference count is %d in retain\n", count);
                        BUG();
                }   
                
                count++;
                return static_cast<const T *>(this);
        }

        T *retain()
        {
                if (count <= 0) {
                        fprintf(stderr, "Reference count is %d in retain\n", count);
                        BUG();
                }   
                
                count++;
                return static_cast<T *>(this);
        }
        
        const T *autorelease() const
        {
                autorelease_pool.add(static_cast<Releasable *>(this));
                return static_cast<T *>(this);
        }

        T *autorelease()
        {
                autorelease_pool.add(static_cast<Releasable *>(this));
                return static_cast<T *>(this);
        }
        
        // This is only here because C++ obnoxiously requires it to
        // be just because it's "called" from code excluded with an
        // if (0) in a template.  No code is ever generated that calls
        // it, but it still must exist.
        
        bool operator < (const RefCountable &rc)
        {
                BUG();
        }
};

// T must be RefCountable
template<typename T, bool compare_ptrs = true>
class Ref {
        // STL containers like to use const on the items they
        // contain; the mutable allows such containers to hold
        // pointers to non-const data.  For truly const Refs,
        // make T const, as in StringRef.  Unfortunately,
        // it cannot be done in a more fine-grained manner,
        // AFAICT.

public: 
        mutable T *data;
        
public:
        Ref()
        {
                data = NULL;
        }

        Ref(T *data) : data(data)
        {
                if (data)
                        data->retain();
        }
        
        Ref(Ref &le) : data(le.data)
        {
                if (data)
                        data->retain();
        }

        Ref &operator =(const Ref &le)
        {
                // The retain must come first, in case both Refs are the same
                if (le.data)
                        le.data->retain();
                if (data)
                        data->release();

                data = le.data;
                
                return *this;
        }

        Ref &operator =(T *new_data)
        {
                // The retain must come first, in case both Refs are the same
                if (new_data)
                        new_data->retain();
                if (data)
                        data->release();

                data = new_data;
                
                return *this;
        }
        
        ~Ref()
        {
                if (data)
                        data->release();
        }
        
        operator T *() const
        {
                return data;
        }
        
        operator T &() const
        {
                return *data;
        }
        
        T *operator *() const
        {
                return data;
        }

        T *operator ->() const
        {
                return data;
        }
        
        bool operator == (const Ref &le) const
        {
                if (compare_ptrs)
                        return data == le.data;
                else
                        return *data == *le.data;
        }

        bool operator != (const Ref &le) const
        {
                if (compare_ptrs)
                        return data != le.data;
                else
                        return *data != *le.data;
        }

        bool operator < (const Ref &le) const
        {
                if (compare_ptrs)
                        return reinterpret_cast<intptr_t>(data) < 
                               reinterpret_cast<intptr_t>(le.data);
                else
                        return *data < *le.data;
        }
};

class String : public string, public RefCountable<String> {
public:
        // Origin of the string, if from the IDL file.
        // Otherwise, fill both values with zero.

        const char *file;
        int line;
        int token;

        String(const char *s = "") : string(s)
        {
                file = "";
                line = 0;
                token = 0;
        }

        String(const String &s) : string(s)
        {
                file = s.file;
                line = s.line;
                token = s.token;
        }

        String(const char *s, const char *file, int line, int token) :
               string(s), file(file), line(line), token(token)
        {}
};

extern String **yylval_string;
typedef Ref<const String, false> StringRef;

/* If a StrList is used for a namespace-qualified identifier, and
   said identifier begins with ".." (i.e. starts from the root
   namespace), the leading ".." is represented by a zero-length
   String. 
   
   Note that list doesn't have a virtual destructor, so all deletions
   should happen through either RefCountable or the wrapper List
   class. */

class StrList : public list<StringRef>, public RefCountable<StrList> {
public:
        StrList()
        {
        }
        
        // Parse a flat String into a StrList, using the specified delimeter.
        StrList(const String *input, char delimiter = '.');

        // Turn a StrList into a flat String, using the specified delimiter.
        String *flatten(const char *delimiter = ".");
};

typedef Ref<StrList> StrListRef;

// ConList is like StrList, but with constant initializers

class Datum;

struct Con {
        union {
                int64_t icon;
                uint64_t ucon;
                StrList *dcon;
                
                // FIXME: handle platforms with weird floating point endianness
                double fcon;
                
                char data[8];
        } con;
        
        // TOK_ICON, TOK_UCON, TOK_FCON, TOK_BOOL, TOK_DCON, 
        // TOK_INVALID, or TOK_NONE
        // Constants are stored as signed (ICON) unless too
        // large to fit in a signed 64-bit integer.  Additional size and
        // signedness checks are mode when down casting to a smaller size
        // to fit into a particular datum; such constants will have a
        // value of zero.
        //
        // TOK_NONE is valid for maybeconst and size.  TOK_INVALID
        // indicates a previously detected error; don't emit any further
        // errors due to this constant.
        //
        // TOK_DCON is used for symbolic constants, whose value may
        // not yet be known.
        
        int type;
};

extern Con *yylval_con;

struct ConInit {
        StringRef str;
        Con con;

        ConInit(const String *str, Con &con) : str(str), con(con)
        {
        }

        ConInit(const ConInit &coninit)
        {
                *this = coninit;
        }
};

class ConList : public list<ConInit>, public RefCountable<ConList> {};
typedef Ref<ConList> ConListRef;

// Like StrList, but is a list of possibly namespace-qualified identifiers.
class IDList : public list<StrListRef>, public RefCountable<IDList> {};
typedef Ref<IDList> IDListRef;


class NameSpace;
class LangCallback;

typedef Ref<NameSpace> NameSpaceRef;

// This is incremented when a chain of symbols is traversed to reset
// detection of already-visited symbols.  It is assumed that this
// will not have to happen billions of times.

extern int traversal;

class Symbol : public RefCountable<Symbol> {
        NameSpace *ns;
        
        void init()
        {
                ns = NULL;
                external = false;
                priv = false;
                lang_priv = NULL;
        }
        
public:
        StringRef name;

        // Symbol was loaded externally
        bool external;
        
        // If set, the symbol is private, and will not be available
        // for lookups except those made directly in the context of
        // the containing namespace.  Private symbols do not get
        // outputted.  They are used to implement imports of specific
        // symbols (as aliases), rather than entire namespaces.
        
        bool priv;
        
        // Reserved for language binding use.
        Releasable *lang_priv;

        Symbol()
        {
                init();
        }
        
        Symbol(const String *_name) : name(_name)
        {
                init();
        }

        virtual ~Symbol();

        NameSpace *get_ns() const
        {
                return ns;
        }

        const String *get_name() const
        {
                return name;
        }
        
        // If append is non-NULL, it is appended to non-user namespaces,
        // to facilitate a language binding that cannot place nested types
        // in the same language construct as the actual interface.  The
        // recommended suffix is "_ns", which is a reserved ending in the
        // IDL.  No suffix is placed on the final component of the name,
        // even if it is a non-user namespace.  The not_last field is used
        // to detect whether it is the final component; it is only used
        // internally, and should always be false when called externally.
        //
        // This function does *NOT* add a null first element to indicate
        // that the name is fully qualified.  If you need that, you have
        // to add it yourself (call 'push_front(new String(""))' on the
        // result).
        
        StrList *get_fq_name(const char *append = NULL,
                             bool not_last = false) const;
        
        virtual void lookup_imports()
        {
        }
        
        virtual void lookup_chain()
        {
        }

        virtual void lookup_misc()
        {
        }
        
        virtual void final_analysis()
        {
        }

        // These two methods must be implemented by all IDL symbols, but are
        // not needed in CDL symbols (and therefore are not pure virtual).

        virtual void output(const char *root)
        {
        }

        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL)
        {
        }
        
        // Find and return the topmost symbol other than a user namespace
        // containing this symbol.  If this symbol's parent is a user
        // namespace, it returns itself.  May not be called on the
        // toplevel namespace.
        
        Symbol *find_toplevel_type();

        // Get the true type of the symbol, regardless of whether it is an
        // alias.
        
        virtual Symbol *get_concrete_sym(bool follow_typedefs = true)
        {
                return this;
        }
        
        friend class NameSpace;
};

typedef Ref<Symbol> SymbolRef;

class SymList : public list<SymbolRef>, public RefCountable<SymList> {};
typedef Ref<SymList> SymListRef;

struct SymbolNotFound {
};

struct DuplicateSymbol {
};

struct InvalidArgument {
};

struct UserError {
};

class NameSpace : public virtual Symbol {
protected:
        // Filesystem path to the external symbol storage, or NULL
        // if not an import namespace.
        //
        // Import namespaces are read-only namespaces which are created
        // for the importation of externally-declared symbols.  One is
        // initially created for each "mount point" specified by the user;
        // whenever such a namespace is searched, it checks the external
        // storage, and if the lookup succeeds, the symbol is loaded and
        // added to the namespace.  Failed lookups could be cached with a
        // special BadSymbol or some such, as the imported namespace is
        // assumed to be constant, but I don't think such an optimization
        // is worthwhile, at least at this point.
        
        StringRef path;

        // Load a symbol from external storage, constructing the relevant type
        // of object, and adding it to this namespace.  Only called for
        // import namespaces.

        Symbol *load(const String *symname);

        typedef map<StringRef, SymbolRef> tbl_type;
        tbl_type tbl;
        
        list<StrListRef> import_strs;
        list<NameSpaceRef> imports;

public:
        // This is a counter for generating unique names for anonymous
        // members of the namespace.
        int anon;
        
        NameSpace() : anon(0)
        {
        }
        
        virtual ~NameSpace();
        
        // Return a description of the type of namespace, for
        // error messages.
        virtual const char *description()
        {
                return "namespace";
        }

        virtual void output(const char *root);

        typedef tbl_type::const_iterator const_iterator;
        typedef tbl_type::value_type value_type;

        // Derived classes can throw InvalidArgument if you give them
        // a type of Symbol that they don't accept; see their comments
        // for more details.  Unfortunately, this cannot be done
        // with static type-checking, as there are places that know
        // they've been given a namespace that can accept a particular
        // type of symbol, but they don't know exactly what kind of
        // namespace it is.  C++'s type system is not sufficient to
        // express this (at least not while retaining any semblance
        // of sanity).

        // DuplicateSymbol is thrown if sym already exists in this namespace.
        virtual void add(Symbol *sym, bool from_import)
        {
                if (path && !from_import)
                        throw InvalidArgument();
                
                if (path)
                        sym->external = true;
                
                if (!sym->name.data)
                        BUG();

                pair<const_iterator, bool> ret = tbl.insert(value_type(sym->name, sym));
                
                if (ret.second)
                        sym->ns = this;
                else {
                        throw DuplicateSymbol();
                }
        }

        // Add the symbol to this namespace, handling duplicate symbols by
        // printing an error and throwing a UserError().  This should not be
        // done in the symbol's constructor, as the parent may not accept
        // the symbol until it is fully constructed (the RTTI information
        // changes, and in general partially constructed objects shouldn't
        // be exposed to the rest of the system).

        void add_user(Symbol *sym);

        // Like add_user, but used by the import code.  Duplicate
        // symbols result in internal errors, and the add is done with
        // from_import set to true.  InvalidArgument results in an error
        // message and a reraise as UserError.
        //
        // All conditions checked by the parent namespace's add() method
        // (such as constness of data) must be satisfied prior to calling
        // add_import().  On the other hand, add_import() must be called
        // before any recursive importation is done which could
        // conceivably try to import the current symbol (thus causing
        // infinite recursion).

        void add_import(Symbol *sym, const char *filename);

        // SymbolNotFound is thrown if sym is not in this namespace.
        virtual void del(Symbol *sym)
        {
                if (sym->ns != this)
                        throw SymbolNotFound();

                sym->ns = NULL;
                int ret = tbl.erase(sym->name);
                assert(ret != 0);
        }

private:        
        Symbol *lookup_noex_noimport(const String *symname)
        {
                const_iterator ret = tbl.find(symname);
                
                if (ret != tbl.end())
                        return (*ret).second;
                
                return NULL;
        }

public:
        Symbol *lookup_noex(const String *symname, bool priv_ok = false)
        {
                Symbol *ret = NameSpace::lookup_noex_noimport(symname);

                if (path && !ret)
                        ret = load(symname);
                
                if (ret && !priv_ok && ret->priv)
                        return NULL;
        
                return ret;
        }

        Symbol *lookup(const String *symname, bool priv_ok = false)
        {
                Symbol *ret = lookup_noex(symname, priv_ok);
                
                if (!ret)
                        throw SymbolNotFound();
                
                return ret;
        }
        
        // Like lookup_noex, but also checks imported namespaces,
        // and returns the namespace containing the match rather
        // than the match itself.
        
        NameSpace *search(const String *name, Symbol *exclude);
        
        void add_search(StrList *ns)
        {
                import_strs.push_back(ns);
        }

        // Return a string containing case information manglement.
        // See input.cc for more information.

        static const String *mangle(const String *name);

        const String *get_path()
        {
                return path;
        }
        
        // Import all members of this namespace.  A no-op if not an import
        // namespace.  
        void import_all();
        
        // As import_all, but also recursively applies to any sub-namespaces.
        void import_all_recursive();
        
        const_iterator begin()
        {
                return tbl.begin();
        }

        const_iterator end()
        {
                return tbl.end();
        }

        virtual void lookup_imports();

        virtual void lookup_chain()
        {
                for (const_iterator i = begin(); i != end(); ++i) {
                        Symbol *sym = (*i).second;
                        sym->lookup_chain();
                }
        }

        virtual void lookup_misc()
        {
                for (const_iterator i = begin(); i != end(); ++i) {
                        Symbol *sym = (*i).second;
                        sym->lookup_misc();
                }
        }

        virtual void final_analysis()
        {
                for (const_iterator i = begin(); i != end(); ++i) {
                        Symbol *sym = (*i).second;
                        sym->final_analysis();
                }
        }
};


extern NameSpaceRef cur_nspace;
extern list<NameSpaceRef> nspace_stack;
        
typedef std::vector<StringRef> StringVec;

string *stringvec_to_path(StringVec &stringvec, const char *prepend);

// lookup_sym and lookup_type throw UserError on user error
// The context namespace is required for the proper
// set of namespaces to be searched.

Symbol *lookup_sym(NameSpace *topns, StrList *name, NameSpace *ctx,
                   Symbol *exclude = NULL);

class Def {
        const char *self;   // Pointer to the type-specific struct
        int self_len;       // Length of the type-specific struct
        
protected:
        CompiledDefHeader hdr;

        // sym is the symbol from which to get the path/name, and
        // is_dir is true if it should be "name/.self" rather than 
        // "name".
        void output_self(const char *dir, Symbol *sym, bool is_dir);

public:
        Def(const char *self, int self_len, CompiledDefHeader::Type type) :
        self(self), self_len(self_len)
        {
                hdr.magic = CompiledDefHeader::magic_normal;
                hdr.type = type;
        }
        
        virtual ~Def()
        {
        }
        
        // Specific types may override this to output extra data
        // to the .self file without having to reopen the file.
        //
        // Returns false on error.
        
        virtual bool output_extra(FILE *f)
        {
                return true;
        }
};

// Internal context struct used by input.cc to avoid passing
// lots of parameters around
struct ImportContext;

// This represents an actual IDL namespace {}, rather than
// a derived namespace such as a Struct or Interface.

class UserNameSpace : public NameSpace, public Def {
public:
        CompiledNameSpace def;
        StringRef mountpoint_name;

        UserNameSpace(const String *name = NULL) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::NameSpace)
        {
                mountpoint_name = get_fq_name()->flatten();
                def.length = mountpoint_name->length();
        }

        virtual void output(const char *root);
        bool output_extra(FILE *f);
        
        static void declare_import(const char *path);

        static UserNameSpace *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);
};

typedef Ref<UserNameSpace> UserNameSpaceRef;
extern UserNameSpaceRef toplevel, cdl_toplevel;
extern UserNameSpace *output_ns;

class Type : public virtual Symbol {
public:
        Type()
        {
        }
        
        virtual ~Type()
        {
        }
        
        virtual int get_default_bf_size()
        {
                // Only allow types in bitfields that explicitly
                // support it.
                
                return -1;
        }
};

typedef Ref<Type> TypeRef;

// ctx can be NULL if basic_types_only is true
Type *lookup_type(StrList *sl, NameSpace *ctx, bool basic_types_only = false);

class BasicType : public Type, public Def {
public:
        CompiledBasicType def;
        bool complete;
        
        BasicType(const String *name) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::BasicType)
        {
                complete = false;
                memset(&def, 0, sizeof(def));
        }

        void init(CompiledBasicType &DEF)
        {
                assert(!complete);
        
                def = DEF;
                complete = true;
        }

        static BasicType *declare(const String *name, NameSpace *parent,
                                  CompiledBasicType &DEF)
        {
                BasicType *bt = new BasicType(name);
                bt->init(DEF);
        
                if (parent)
                        parent->add_user(bt);

                return bt;
        }

        virtual void output(const char *root);

        static BasicType *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);
};

static inline bool is_array(CompiledBasicType &bt)
{
        return bt.array.bounds[0] || bt.array.bounds[1];
}

static inline bool is_array(CompiledBasicType *bt)
{
        return is_array(*bt);
}

typedef Ref<Datum> DatumRef;

class Array : public RefCountable<Array>
{
        NameSpace *lookup_ctx;
        DatumRef datums[2];

        // lower is [0], upper is [1]
        StrListRef dcons[2];
        
        // Strings for error reporting on each constant.  If the constant
        // is symbolic, then this is the fully qualified symbol name. 
        // Otherwise, it is the numerical value converted to a string.  In
        // each case, the file/line shall correspond to where the array
        // bound was specified.
        
        StringRef strs[2];
        
public:
        Con cons[2];

        // ca is not valid until after final_analysis() is called.
        CompiledArray ca;

        Array(NameSpace *LOOKUP_CTX);
        void set_bound(Con &con, int bound);
        void final_analysis();

        void set_unbounded();
};

typedef Ref<Array> ArrayRef;

class Datum : public Symbol, public Def {
        StrListRef type_name;
        SymbolRef type_sym;
        StringRef type_fq_name;

        StrListRef const_val_name;
        SymbolRef const_val_sym;
        DatumRef const_val;

        bool basic;      // Datum is of a BasicType
        bool complete;
        bool const_init; // Datum's constant has been initialized; this is
                         // true after a successful verify_const().
        CompiledBasicType *cbt;

        int chain_traversed;

        // Recursively retrieve the actual value of a const datum
        // initialized with another named const datum.  Returns
        // the "end" of an infinite loop, if one is found.  Once
        // the full infinite loop has been printed, UserError is
        // thrown.

        Datum *resolve_constant_chain();

        void init_const_early(Con *con);
        
        void use_anon_type(const CompiledBasicType &CBT)
        {
                def.basictype = CBT;
                cbt = &def.basictype;
                basic = true;
                type = NULL;
                def.type.length = 0;
        }
        
        void process_type();
        
        void set_array(Array *ARRAY)
        {
                if (ARRAY)
                        array = ARRAY;
        }

public:
        ArrayRef array;
        CompiledDatum def;
        TypeRef type;

        int con_type;    // Used to store the TOK_[IUF]CON of the Con struct
                         // for type checking once the type is known.

        Datum(const String *name) :
        Symbol(name), 
        Def((const char *)&def, sizeof(def), CompiledDefHeader::Datum)
        {
                complete = false;
                const_init = false;
                chain_traversed = 0;
                memset(&def, 0, sizeof(def));
        }

        void init(StrList *type, Array *ARRAY, Con *con = NULL);
        void init(CompiledBasicType &cbt, Array *ARRAY, Con *con = NULL);

        static Datum *declare(const String *name, NameSpace *parent,
                              StrList *type, Array *ARRAY,
                              Con *con = NULL)
        {
                assert(parent);
                
                Datum *d = new Datum(name);
                d->init(type, ARRAY, con);

                parent->add_user(d);
                return d;
        }

        static Datum *declare(const String *name, NameSpace *parent,
                              CompiledBasicType &type, 
                              Array *ARRAY, Con *con = NULL)
        {
                assert(parent);
        
                Datum *d = new Datum(name);
                d->init(type, ARRAY, con);

                parent->add_user(d);
                return d;
        }
        
        void set_inline()
        {
                def.flags.field.Inline = 1;
        }
        
        bool is_inline()
        {
                return def.flags.field.Inline;
        }
        
        void set_immutable()
        {
                def.flags.field.Immutable = 1;
        }
        
        bool is_immutable()
        {
                return def.flags.field.Immutable;
        }

        // Returns true if the constant was acceptable, false otherwise (an
        // error is also output to the user in this case).
        
        bool verify_const();

        virtual void lookup_chain()
        {
                assert(complete);

                if (const_val_name)
                        const_val_sym = lookup_sym(toplevel, const_val_name, get_ns());

                if (type_name) {
                        assert(!basic);
                        type_sym = lookup_type(type_name, get_ns(), true);
                        if (!type_sym)
                                type_sym = lookup_sym(toplevel, type_name, get_ns());
                } else {
                        assert(basic);
                }
        }

        virtual void lookup_misc()
        {
                if (def.flags.field.Const) {
                        if (!const_init) {
                                assert(def.flags.field.Const);
        
                                traversal++;
                                Datum *d = resolve_constant_chain();
                                assert(!d);
                        }
                
                        assert(const_init);
                } else {
                        process_type();
                }
        }
        
        virtual void final_analysis();

        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static Datum *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);

        uint64_t get_ucon(const String *err_str)
        {
                if (!def.flags.field.Const) {
                        yyerrorfl(err_str->file, err_str->line, 
                                  "\"%s\" is not a const Datum.\n",
                                  get_fq_name()->flatten()->c_str());
                        throw UserError();
                }
                
                assert(const_init);
                return def.ucon;
        }

        bool is_array()
        {
                return ::is_array(def.basictype);
        }
};

template<typename T>
bool output_list(T *sym, FILE *f);

class BitField : public NameSpace, public Type, public Def {
        list<DatumRef> entries;

        void add_elem(Datum *d);

public:
        CompiledBitField def;
        int cur_pos;

        BitField(const String *name) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::BitField)
        {
                memset(&def, 0, sizeof(def));
        }

        void init(int bits, NameSpace *parent)
        {
                if (bits < 0 || bits > 64) {
                        yyerrorf("\"%s\" has invalid bitfield size %d", 
                                 name->c_str(), bits);

                        bits = bits < 0 ? 0 : 64;
                }
        
                def.bits = bits;
        }

        static BitField *declare(const String *name, NameSpace *parent,
                                 int bits)
        {
                assert(parent);
                
                BitField *bf = new BitField(name);
                bf->init(bits, parent);
        
                parent->add_user(bf);
                return bf;
        }

        // Only integral Datums, Enums, and BitFields can be added.

        void add(Symbol *sym, bool from_import);

        virtual const char *description()
        {
                return "bitfield";
        }

        virtual void lookup_misc()
        {
                NameSpace::lookup_misc();
        }
        
        virtual void final_analysis()
        {
                // FIXME: check total size of elements
        
                NameSpace::final_analysis();
        }

        int get_default_bf_size()
        {
                return def.bits;
        }

        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static BitField *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);

        typedef list<DatumRef>::const_iterator entries_iterator;
        typedef list<DatumRef>::const_reverse_iterator entries_reverse_iterator;

        entries_iterator entries_begin()
        {
                return entries.begin();
        }

        entries_iterator entries_end()
        {
                return entries.end();
        }

        entries_reverse_iterator entries_rbegin()
        {
                return entries.rbegin();
        }

        entries_reverse_iterator entries_rend()
        {
                return entries.rend();
        }
};

class Struct;
typedef Ref<Struct> StructRef;
extern StructRef System_VStruct;

// FIXME: typedefed superstructs
class Struct : public NameSpace, public Type, public Def {
        list<DatumRef> entries;
        StructRef super;
        SymbolRef supersym;
        StrListRef supername;
        bool attrs_resolved;

        // 0 = unknown, 1 = yes, 2 = no
        int plain_data;
        
        void add_elem(Datum *d);

        void resolve_attrs()
        {
                if (attrs_resolved)
                        return;
                
                if (super && !super->attrs_resolved)
                        super->resolve_attrs();
                
                if (super && super->def.flags.field.Virtual)
                        def.flags.field.Virtual = 1;
                
                attrs_resolved = true;
        }
        
public:
        CompiledStruct def;
        
        // This is not maintained by the generic code, but can be
        // used by language bindings to cache the result of the
        // summation. 
        
        int chainlen;
        
        Struct(const String *name) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::Struct)
        {
                memset(&def, 0, sizeof(def));
                attrs_resolved = 0;
        }
        
        void init(StrList *SUPERNAME)
        {
                supername = SUPERNAME;
        }

        static Struct *declare(const String *name, NameSpace *parent,
                               StrList *SUPERNAME)
        {
                assert(parent);
        
                Struct *st = new Struct(name);
                st->init(SUPERNAME);

                parent->add_user(st);
                return st;
        }
        
        void set_virtual()
        {
                def.flags.field.Virtual = 1;
        }

        void set_inline()
        {
                def.flags.field.Inline = 1;
        }

        bool is_virtual()
        {
                return def.flags.field.Virtual;
        }

        bool is_inline()
        {
                return def.flags.field.Inline;
        }
        
        // Only Datums and Types can be added.

        void add(Symbol *sym, bool from_import);

        virtual const char *description()
        {
                return "struct";
        }
        
        Struct *get_super()
        {
                assert(current_pass >= 4);
                return super;
        }

        virtual void lookup_chain()
        {
                if (supername) {
                        supersym = lookup_sym(toplevel, supername, get_ns());
                        assert(supersym);
                }

                NameSpace::lookup_chain();
        }

private:
        void lookup_super()
        {
                if (supersym && !super) {
                        super = dynamic_cast<Struct *>(supersym->get_concrete_sym());
                
                        if (!super) {
                                const String *str = supername->back();
                                yyerrorfl(str->file, str->line,
                                          "\"%s\" is not a struct.",
                                          supersym->get_fq_name()->flatten()->c_str());
                        }
                        
                        def.flags.field.Super = 1;
                        super->lookup_super();
                        
                        if (super->is_virtual())
                                set_virtual();
                }
                
                if (is_virtual() && !supersym && !super) {
                        assert(System_VStruct);
                        if (this != System_VStruct) {
                                def.flags.field.Super = 1;
                                super = System_VStruct;
                        }
                }
        }
        
public:
        virtual void lookup_misc()
        {
                lookup_super();

                if (is_virtual() && def.guid[0] == 0 && def.guid[1] == 0)
                        yyerrorfl(name->file, name->line,
                                  "Virtual struct \"%s\" is missing a GUID.",
                                  get_fq_name()->flatten()->c_str());

                NameSpace::lookup_misc();
        }
        
        virtual void final_analysis()
        {
                // FIXME: check for infinite loops in struct inheritance

                resolve_attrs();
                NameSpace::final_analysis();
        }

        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static Struct *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);

        typedef list<DatumRef>::const_iterator entries_iterator;

        entries_iterator entries_begin()
        {
                return entries.begin();
        }

        entries_iterator entries_end()
        {
                return entries.end();
        }

        void set_guid(uint64_t guid[2])
        {
                if (def.guid[0] || def.guid[1])
                        yyerrorf("\"%s\" already has a GUID.",
                                 get_fq_name()->flatten()->c_str());
        
                def.guid[0] = guid[0];
                def.guid[1] = guid[1];
        }

        // A struct is "plain data" if it contains no object references,
        // no non-inline arrays or structs, and no inline non-plain structs.
        bool is_plain_data();
};

class Param : public Symbol, public Def {
        StrListRef type_name;
        StringRef type_fq_name;

        bool basic;      // Datum is of a BasicType
        bool complete;
        
        ArrayRef array;

        void use_named_type(BasicType *bt)
        {
                assert(!bt || bt->def.flags.field.TypeDef);
                
                basic = false;

                type_fq_name = type->get_fq_name()->flatten();
                def.type.length = type_fq_name->length();
        }
        
        void use_anon_type(const CompiledBasicType &cbt)
        {
                def.basictype = cbt;
                basic = true;
                type = NULL;
        }

        void set_array(Array *ARRAY)
        {
                if (ARRAY)
                        array = ARRAY;
        }

public:
        CompiledParam def;
        TypeRef type;

        Param(const String *name) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::Param)
        {
                memset(&def, 0, sizeof(def));
        }

        void init(StrList *TYPE, CompiledParam::Flags flags, Array *ARRAY)
        {
                type_name = TYPE;
                def.flags = flags;
                set_array(ARRAY);
        }

        static Param *declare(const String *name, NameSpace *parent,
                              StrList *TYPE, CompiledParam::Flags flags,
                              Array *ARRAY);

        virtual void lookup_misc()
        {
                type = lookup_type(type_name, get_ns());
        }
        
        virtual void final_analysis()
        {
                BasicType *bt = dynamic_cast<BasicType *>(type->get_concrete_sym());

                if (bt && !bt->def.flags.field.TypeDef) {
                        use_anon_type(bt->def);
                } else {
                        use_named_type(bt);

                        Struct *str = dynamic_cast<Struct *>(*type);
                        if (str && str->is_inline())
                                set_inline();
                        
                        if (!str && is_inline()) {
                                yyerrorfl(name->file, name->line,
                                          "\"%s\" is static but not a struct.",
                                          get_fq_name()->flatten()->c_str());
                        }
                }
        
                if (array) {
                        array->final_analysis();
                        def.basictype.array = array->ca;
                } else {
                        def.basictype.array.bounds[0] = 0;
                        def.basictype.array.bounds[1] = 0;
                }
        }

        void set_inline()
        {
                def.flags.field.Inline = 1;
        }

        bool is_inline()
        {
                return def.flags.field.Inline;
        }
        
        bool is_in()
        {
                return def.flags.field.In;
        }

        bool is_out()
        {
                return def.flags.field.Out;
        }

        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static Param *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);
        
        bool is_array()
        {
                return ::is_array(def.basictype);
        }
};

typedef Ref<Param> ParamRef;

class Method : public NameSpace, public Def {
        list<ParamRef> entries;

        void add_elem(Param *p);

public:
        CompiledMethod def;
        
        Method(const String *name) :
        Symbol(name), 
        Def((const char *)&def, sizeof(def), CompiledDefHeader::Method)
        {
                memset(&def, 0, sizeof(def));
        }

        void set_async()
        {
                def.flags.field.Async = 1;
        }
        
        bool is_async()
        {
                return def.flags.field.Async;
        }
        
        static Method *declare(const String *name, NameSpace *parent);

        void add(Symbol *sym, bool from_import);

        virtual const char *description()
        {
                return "method";
        }

        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static Method *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);

        typedef list<ParamRef>::const_iterator entries_iterator;

        entries_iterator entries_begin()
        {
                return entries.begin();
        }

        entries_iterator entries_end()
        {
                return entries.end();
        }
};

typedef Ref<Method> MethodRef;

class Interface;
typedef Ref<Interface> InterfaceRef;

extern InterfaceRef System_Object;

// FIXME: typedefed superinterfaces
class Interface : public NameSpace, public Type, public Def {
        list<MethodRef> methods;
        list<InterfaceRef> supers;
        IDListRef supernames;

        void add_elem(Method *m);

        // This is like Symbol::traversed[], but used internally by the
        // for_each_super function to ensure that common ancestors are only
        // visited once.
        
        int traversed_all_supers;
        static int all_supers_traversal;
        
public:
        typedef void (*callback)(Interface *i, void *arg);
        
private:
        template<callback cb>
        void for_each_super_internal(void *arg)
        {
                for (supers_iterator i = supers_begin(); i != supers_end(); ++i) {
                        Interface *iface = *i;
                        
                        if (iface->traversed_all_supers < all_supers_traversal) {
                                iface->traversed_all_supers = all_supers_traversal;
                                cb(iface, arg);
                                iface->for_each_super_internal<cb>(arg);
                        }
                }
        }

        // All interfaces in the map and vector are supers of this
        // interface, and thus retained that way, so plain pointers
        // can be used here.

        typedef map<Interface *, int> chain_map_type;
        typedef chain_map_type::value_type chain_valtype;
        typedef chain_map_type::const_iterator chain_iter;

        chain_map_type super_to_chain_map;

private:
        int num_chains;
        vector<Interface *> chain_heads;

public: 
        int super_to_chain(Interface *iface, bool must_find_it = true)
        {
                chain_iter ret = super_to_chain_map.find(iface);
                
                if (ret == super_to_chain_map.end()) {
                        assert(!must_find_it);
                        return -1;
                }

                return (*ret).second;
        }

        Interface *get_chain_head(int chain)
        {
                return chain_heads[chain];
        }

        int get_num_chains()
        {
                return num_chains;
        }
        
private:        
        void set_chain(Interface *iface, int chain)
        {
                pair<chain_iter, bool> ret = 
                        super_to_chain_map.insert(chain_valtype(iface, chain));
                assert(ret.second);
        }
        
        // This is the inner depth-first search, which terminates
        // at each level upon finding that the node it had previously
        // recursed into found an unchained node.
        
        void pick_chain(Interface *iface, int chain)
        {
                assert(super_to_chain(iface, false) == -1);
                chain_heads.push_back(iface);
        
                do {
                        set_chain(iface, chain);
                        
                        if (iface->supers.empty())
                                break;
                        
                        iface = iface->supers.front();
                } while (super_to_chain(iface, false) == -1);
        }

        // This is the outer breadth-first-search, making sure every
        // super is assigned to a chain.

        void sort_chains()
        {
                list<Interface *> bfs;
                num_chains = 0;

                bfs.push_back(this);
                
                while (!bfs.empty()) {
                        Interface *iface = bfs.front();
                        bfs.pop_front();
                
                        for (supers_iterator i = iface->supers_begin();
                             i != iface->supers_end(); ++i)
                                bfs.push_back(*i);
                
                        if (super_to_chain(iface, false) == -1)
                                pick_chain(iface, num_chains++);
                }
        }

public:
        // Do not call after lookup_misc
        void add_super(Interface *i)
        {
                assert(current_pass != 1);
        
                supers.push_back(i);
                def.num_supers++;
        }

        CompiledInterface def;
        
        Interface(const String *name) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::Interface)
        {
                memset(&def, 0, sizeof(def));
                traversed_all_supers = 0;
        }
        
        void init(IDList *SUPERNAMES)
        {
                supernames = SUPERNAMES;
        }

        static Interface *declare(const String *name, NameSpace *parent, 
                                  IDList *SUPERNAMES)
        {
                assert(parent);

                Interface *i = new Interface(name);
                i->init(SUPERNAMES);
                
                parent->add_user(i);
                return i;
        }
        
        // Only Methods, Types, and const BasicType Datums can be added.

        void add(Symbol *sym, bool from_import);

        virtual const char *description()
        {
                return "interface";
        }

private:
        void add_object_super()
        {
                assert(System_Object);
                if (this != System_Object && supers.empty())
                        add_super(System_Object);
        }

public: 
        virtual void lookup_misc()
        {
                if (def.guid[0] == 0 && def.guid[1] == 0)
                        yyerrorfl(name->file, name->line,
                                  "Interface \"%s\" is missing a GUID.",
                                  get_fq_name()->flatten()->c_str());
        
                if (supernames) {
                        for (IDList::iterator i = supernames->begin(); 
                             i != supernames->end(); ++i)
                        {
                                Symbol *sym = lookup_sym(toplevel, *i, get_ns());
                                Interface *iface = 
                                        dynamic_cast<Interface *>(sym->get_concrete_sym());
                                
                                if (!iface) {
                                        const String *str = (*i)->back();
                                        yyerrorfl(str->file, str->line,
                                                  "\"%s\" is not an interface.\n",
                                                  sym->get_fq_name()->flatten()->c_str());
        
                                        throw UserError();
                                }
                                
                                add_super(iface);
                        }
                }
                
                add_object_super();
                NameSpace::lookup_misc();
        }
        
        virtual void final_analysis()
        {
                // FIXME: check for infinite loops in inheritance
        
                sort_chains();
                NameSpace::final_analysis();
        }
        
        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static Interface *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);

        typedef list<MethodRef>::const_iterator methods_iterator;
        typedef list<InterfaceRef>::const_iterator supers_iterator;

        supers_iterator supers_begin()
        {
                assert(current_pass != 1);
                return supers.begin();
        }

        supers_iterator supers_end()
        {
                return supers.end();
        }
        
        bool supers_empty()
        {
                assert(current_pass != 1);
                return supers.empty();
        }

        methods_iterator methods_begin()
        {
                return methods.begin();
        }

        methods_iterator methods_end()
        {
                return methods.end();
        }
        
        template<callback cb>
        void for_each_super(void *arg)
        {
                assert(current_pass >= 4);
        
                all_supers_traversal++;
                for_each_super_internal<cb>(arg);
        }

        void finalize_class_iface()
        {
                add_object_super();
                sort_chains();
        }
        
        void set_guid(uint64_t guid[2])
        {
                if (def.guid[0] || def.guid[1])
                        yyerrorf("\"%s\" already has a GUID.",
                                 get_fq_name()->flatten()->c_str());
        
                def.guid[0] = guid[0];
                def.guid[1] = guid[1];
        }
};

class IFaceList : public list<InterfaceRef>,
                  public RefCountable<IFaceList> {};

class Enum : public NameSpace, public Type, public Def {
        list<DatumRef> entries;

        void add_elem(Datum *d);

public:
        unsigned int next_val;
        CompiledEnum def;

        Enum(const String *name) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::Enum),
        next_val(0)
        {
                memset(&def, 0, sizeof(def));
        }

        void init(int bits)
        {
                if (bits < 0 || bits > 64) {
                        yyerrorf("\"%s\" has invalid enum size %d", 
                                 name->c_str(), bits);

                        bits = bits < 0 ? 0 : 64;
                }
        
                def.bits = bits;
        }

        static Enum *declare(const String *name, NameSpace *parent,
                             int bits)
        {
                assert(parent);
                
                Enum *e = new Enum(name);
                e->init(bits);
                
                parent->add_user(e);
                return e;
        }

        // Only const unsigned integer BasicType Datums are allowed.

        void add(Symbol *sym, bool from_import);

        virtual const char *description()
        {
                return "enumeration";
        }

        int get_default_bf_size()
        {
                return def.bits;
        }

        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static Enum *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);

        typedef list<DatumRef>::const_iterator entries_iterator;

        entries_iterator entries_begin()
        {
                return entries.begin();
        }

        entries_iterator entries_end()
        {
                return entries.end();
        }
};

class Alias : public Symbol, public Def {
        bool lookup_begun;
        
        struct Cycle {
                Alias *end;
                
                Cycle(Alias *END) : end(END)
                {
                }
        };

public:
        CompiledAlias def;
        
        SymbolRef real_sym;
        StringRef sym_fq_name;
        StrListRef sym_name;
        
        Alias(const String *name) :
        Symbol(name),
        Def((const char *)&def, sizeof(def), CompiledDefHeader::Alias)
        {
                memset(&def, 0, sizeof(def));
                lookup_begun = false;
        }
        
        void init(StrList *symname, bool is_private)
        {
                sym_name = symname;
                priv = is_private;
        }

        static Alias *declare(const String *name, NameSpace *parent,
                              StrList *symname, bool is_private = false)
        {
                assert(parent);
                Alias *a = new Alias(name);
                a->init(symname, is_private);

                parent->add_user(a);
                return a;
        }
        
        void resolve_chain()
        {       
                if (!real_sym) {
                        if (lookup_begun) {
                                yyerrorfl(name->file, name->line,
                                          "Alias loop defining \"%s\"",
                                          get_fq_name()->flatten()->c_str());
                        
                                throw Cycle(this);
                        }
                        
                        lookup_begun = true;
                        
                        try {
                                real_sym = lookup_sym(toplevel, sym_name, get_ns(), this);
                        }
                        
                        catch (Cycle &c) {
                                yyerrorfl(name->file, name->line, "   ...referenced by \"%s\"",
                                          get_fq_name()->flatten()->c_str());

                                if (c.end == this)
                                        throw UserError();

                                throw c;
                        }
                }
        }

        virtual Symbol *get_concrete_sym(bool follow_typedefs = true)
        {
                resolve_chain();
                return real_sym->get_concrete_sym(follow_typedefs);
        }

        virtual void lookup_chain()
        {
                get_concrete_sym(true);
        }

        virtual void lookup_misc()
        {
                real_sym = real_sym->get_concrete_sym(false);
                sym_fq_name = real_sym->get_fq_name()->flatten();
                
                def.length = sym_fq_name->length();
        }

        virtual void output(const char *root);
        bool output_extra(FILE *f);

        static Alias *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);
};

class TypeDef : public Alias {
public:
        TypeDef(const String *name) : Alias(name)
        {
                memset(&def, 0, sizeof(def));
                hdr.type = CompiledDefHeader::TypeDef;
        }
        
        static TypeDef *declare(const String *name, NameSpace *parent,
                                StrList *symname)
        {
                assert(parent);
                TypeDef *td = new TypeDef(name);
                td->init(symname, false);
                
                parent->add_user(td);
                return td;
        }

        virtual Symbol *get_concrete_sym(bool follow_typedefs = true)
        {
                if (follow_typedefs) {
                        resolve_chain();
                        return real_sym->get_concrete_sym(follow_typedefs);
                }
                
                return this;
        }

        static TypeDef *import(ImportContext &ctx);
        virtual void output_lang(LangCallback *lcb, int arg = 0, void *arg2 = NULL);
};

NameSpace *add_nspace(StrList *name, bool push);
void pop_nspace();

// Declare an instance of "type" in "ns" for each element of "ids".
// This function will report any errors, but not throw UserError.

void declare_data(NameSpace *ns, StrList *ids, StrList *type,
                  Array *array, StrList *attr);
void declare_aliases(NameSpace *ns, StrList *ids, StrList *type,
                     bool is_typedef);
void declare_basictypes(NameSpace *ns, StrList *ids,
                        BasicType *type, bool is_typedef);

// You'd think they'd have standard functions to do this these days.
// All I could find that come close are the network-byte-order
// functions, and they're no-ops on big-endian machines.

static inline uint32_t swap32(uint32_t in, bool swap)
{
        if (swap)
                return ((in & 0x000000ff) << 24) |
                       ((in & 0x0000ff00) <<  8) |
                       ((in & 0x00ff0000) >>  8) |
                       ((in & 0xff000000) >> 24);
        
        return in;
}

static inline uint64_t swap64(uint64_t in, bool swap)
{
        if (swap)
                return (((uint64_t)swap32((uint32_t)in, true)) << 32) |
                       swap32((uint32_t)(in >> 32), true);

        return in;
}

struct File {
        FILE *f;
        
        File()
        {
                f = NULL;
        }
        
        File(FILE *F)
        {
                f = F;
        }
        
        File *operator =(FILE *F)
        {
                f = F;
                return this;
        }
        
        ~File()
        {
                if (f)
                        fclose(f);
        }
        
        operator FILE *()
        {
                return f;
        }
};

// Verify that a prospective new import (or output namespace)
// does not overlap an existing import.  Returns the conflicting
// import, or NULL if none found.

NameSpace *check_for_imports(NameSpace *ns);

#endif