/**
  *  \file type_rep.cpp
  *  \brief Type Representation
  *
  *  This represents a C++ type. "Type" is the object you'll hand
  *  around, right now it is implemented as a simple flat string-based
  *  representation.
  *
  *  \author Stefan Reuther
  */

INTERFACE:

#include <string>
#include <vector>

#include "ptree_nodes.h"

class Abstract_scope;
class Type_symbol;

/*
  Possible types:
    fundamental types ([us\epsilon][ihljcfdebwv])
    const T -> "C<T>"
    volatile T -> "V<T>"
    restrict T (why not) -> "N<T>"
    pointer-to-T -> "P<T>"
    reference-to-T -> "R<T>"
    function(T1,T2,T3)-returning-TR -> "F<T1><T2><T3>_<TR>"
    array[dimension]-of-T -> "A<n><T>"
    pointer-to-member-of-T-which-has-type-TM -> "M<TM><T>"
    pointer-to-member-function(T1,T2,T3)-returning-TR-of-T -> "MF<T1><T2><T3>_<TR><T>
    class/struct/union "Q<len><name>"
    template arg "T<nn>"
    enum "Q<len><name>"
    ... -> "E"
  Names: as in C++: foo::bar::x
 */

enum Storage_class_specifier {
    s_None,
    s_Auto,
    s_Parameter,
    s_Register,
    s_Static,
    s_Extern,
    s_Mutable,                  // implies member
    s_Member                    // this one can't be specified in source
};

enum Function_specifier {
    f_None     = 0,
    f_Inline   = 1,
    f_Virtual  = 2,
    f_Explicit = 4,
    f_Abstract = 8
};
typedef int Function_specifier_set;

/** Throwaway type representation.
    In the future, this should probably be replaced by a proper dynamic data
    structure which allows easier representation of some subtleties.

    How gcc does it: every type has a "main variant", of these we have
    sub-variants (cv-qualified types) which are created on demand. In
    addition, we have derived types (ref/ptr/array) for each. */
class Type {
    std::string code;
    int qualifiers;
    friend class Function_type_maker;
 public:
    enum Qualifier {
        q_Const,                ///< "const"
        q_Volatile,             ///< "volatile"
        q_Restrict              ///< "restrict"
    };
    enum Kind {
        k_Fundamental,
        k_Pointer   = 'P',
        k_Reference = 'R',
        k_Function  = 'F',
        k_Array     = 'A',
        k_Member    = 'M',      // member pointer or member function pointer
        k_Userdef   = 'Q',
        k_Ellipsis  = 'E',
        k_Template  = 'T',
        k_Nothing   = 'O'       // no type, i.e. ctor or operator
    };
    static const int ignore_qual = 0;

    bool is_qualified(Qualifier q) const { return qualifiers & (1 << q); }
    bool is_qualified() const            { return qualifiers != 0; }
    void add_qualifier(Qualifier q)      { qualifiers |= (1 << q); }
    void remove_qualifier(Qualifier q)   { qualifiers &= ~(1 << q); }
    bool is_valid() const { return code.length() != 0; }

    void copy_qualifiers(const Type& other) { qualifiers |= other.qualifiers; }

    const std::string& get_encoded_type() const { return code; }

    Type get_unqualified_type() const { return Type(code); }

    bool operator==(const Type& rhs) const { return rhs.code == code && ((rhs.qualifiers ^ qualifiers) & ~ignore_qual) == 0; }
    bool operator!=(const Type& rhs) const { return rhs.code != code || ((rhs.qualifiers ^ qualifiers) & ~ignore_qual) != 0; }

    bool is_more_qualified_than(const Type& other) const { return (qualifiers & ~other.qualifiers) != 0; }
    bool is_same_qualified_as(const Type& other) const { return ((qualifiers ^ other.qualifiers) & ~ignore_qual) == 0; }
    bool is_same_unqualified_type(const Type& other) const { return code == other.code; }
};

class Function_type_maker {
    std::string types;
};

/* built-in types */
extern Type int_type, uint_type, short_type, ushort_type, long_type,
    ulong_type, llong_type, ullong_type, char_type, schar_type,
    uchar_type, float_type, double_type, ldouble_type, bool_type,
    wchar_type, void_type, ctor_type;

/* aliases there-to */
extern Type ptrdiff_type, size_type;

typedef std::vector<Type> Type_vector;

IMPLEMENTATION:

#include <sstream>
#include <cctype>
#include <ptree.h>
#include "ptree_util.h"
#include "except.h"
#include "scope.h"
#include "typedef.h"
#include "symbol_table.h"
#include "enum.h"
#include "class.h"
#include "symbol_name.h"

using namespace Opencxx;

/* 3.9.2 [basic.compound]
   - array of TYPE
   - function
   - pointers [dcl.ptr]
   - references [dcl.ref]
   - class [class]
   - union [class.union]
   - enum [dcl.enum]
   - member pointer [dcl.mptr] */

/** Create an empty, invalid type.
    \post !Type().is_valid() */
PUBLIC
Type::Type()
    : code(), qualifiers(0)
{ }

/** Create a type containing the specified encoded signature. This is
    used to construct types internally and should not be called by
    user code. Still public for flexibility. */
PUBLIC
Type::Type(std::string encoded)
    : code(encoded), qualifiers(0)
{
    while (code.length()) {
        if (code[0] == 'C') {
            add_qualifier(q_Const);
            code.erase(0, 1);
        } else if (code[0] == 'V') {
            add_qualifier(q_Volatile);
            code.erase(0, 1);
        } else if (code[0] == 'N') {
            add_qualifier(q_Restrict);
            code.erase(0, 1);
        } else
            break;
    }
}

PRIVATE
Type::Type(std::string code, int qualifiers)
    : code(code), qualifiers(qualifiers)
{ }

/** Create type symbol for type with mangled name /name/. */
PUBLIC static Type
Type::get_named_type(std::string name)
{
    std::ostringstream s;
    s << name.length();
    return Type("Q" + s.str() + name);
}

/** Return kind of this type. */
PUBLIC Type::Kind
Type::get_kind() const
{
    using namespace std;
    if (code.length() && isupper(code[0]))
        return Kind(code[0]);
    else
        return k_Fundamental;
}

/** Internal: construct a new type. "prefix" is the new prefix (a Kind
    maybe) */
PRIVATE std::string
Type::encode_qualifiers(std::string prefix) const
{
    if (is_qualified(q_Const))
        prefix.append("C");
    if (is_qualified(q_Volatile))
        prefix.append("V");
    if (is_qualified(q_Restrict))
        prefix.append("N");
    return prefix + code;
}

/** Create pointer type (pointer-to-this). */
PUBLIC inline Type
Type::make_pointer_type() const
{
    return Type(encode_qualifiers("P"));
}

/** Create reference type (reference-to-this). */
PUBLIC inline Type
Type::make_reference_type() const
{
    return Type(encode_qualifiers("R"));
}

/** Create array type (array[dimension]-of-this). */
PUBLIC Type
Type::make_array_type(Ptree* dimension) const
{
    /* FIXME: we currently ignore dimensions */
    return Type(encode_qualifiers("A"));
}

/** Create member type (member-membertype-of-this).
    let c = classtype
        m = membertype
    then "m c::*" is c.make_member_type(m) */
PUBLIC Type
Type::make_member_type(Type membertype) const
{
    return Type(membertype.encode_qualifiers(encode_qualifiers("M")));
}

/** Given a type "reference-to-T", "pointer-to-T" or "array-of-T",
    return the T. */
PUBLIC Type
Type::get_basis_type() const
{
    assert(get_kind() == k_Reference || get_kind() == k_Pointer || get_kind() == k_Array);
    return Type(code.substr(1));
}

/** Returns this type with reference removed. That is, a variable declared
    as type T denotes an lvalue of type T.sans_reference(). */
PUBLIC Type
Type::sans_reference() const
{
    if (get_kind() == k_Reference)
        return get_basis_type();
    else
        return *this;
}

PUBLIC Type
Type::sans_array() const
{
    if (get_kind() == k_Array)
        return get_basis_type().sans_array();
    else
        return *this;
}

/** Given a type "pointer-to-member-of-CLASS-which-has-type-T", return CLASS. */
PUBLIC Type
Type::get_class_type() const
{
    assert(get_kind() == k_Member);
    std::string mem_type = eat_type(code.substr(1));
    return Type(code.substr(1, code.length() - 1 - mem_type.length()));
}

/** Given a type "pointer-to-member-of-CLASS-which-has-type-T", return T. */
PUBLIC Type
Type::get_member_type() const
{
    assert(get_kind() == k_Member);
    return Type(eat_type(code.substr(1)));
}

/** Given a type "function returning T", return T. */
PUBLIC Type
Type::get_return_type() const
{
    assert(get_kind() == k_Function);
    std::string r = code.substr(1);
    while (r.length() && r[0] != '_')
        r = eat_type(r);
    return Type(r.substr(1));
}

/** Given a function type, return its signature. The signature is an
    opaque string which encodes the parameters. */
PUBLIC std::string
Type::get_function_signature() const
{
    assert(get_kind() == k_Function);
    std::string r = code.substr(1);
    while (r.length() && r[0] != '_')
        r = eat_type(r);
    return code.substr(0, code.length() - r.length());
}

/** Given a type "function(a0,a1,a2...) returning T", return a_i. */
PUBLIC Type
Type::get_function_arg(int n) const
{
    assert(get_kind() == k_Function);
    std::string r = code.substr(1);
    while (n--)
        r = eat_type(r);
    return Type(r.substr(0, r.length() - eat_type(r).length()));
}

/** Given a type "function(a0..a_n-1)", return n. */
PUBLIC int
Type::get_num_function_args() const
{
    assert(get_kind() == k_Function);
    std::string r = code.substr(1);
    int n = 0;
    while (r.length() && r[0] != '_')
        r = eat_type(r), ++n;
    return n;
}

/** Given type "N'th template argument", return N. */
PUBLIC int
Type::get_template_argindex() const
{
    assert(get_kind() == Type::k_Template);
    int n = 0;
    for (std::string::size_type i = 1; i < code.length(); ++i)
        n = 10*n + code[i]-'0';
    return n;
}

/** Given a string <Type>NNN, return NNN. */
PRIVATE static std::string
Type::eat_type(std::string s)
{
    using namespace std;        // for ctype macros
    std::string::size_type n = 0;
    while (n < s.length()) {
        switch(s[n]) {
         case 'C':
         case 'V':
         case 'N':
         case 'P':
         case 'R':
         case 'A':
         case 's':
         case 'u':
            /* these all have syntax "<char><rest-of-type>" */
            ++n;
            break;
         case 'M':
            /* M<TM><T> */
            return eat_type(eat_type(s.substr(n+1)));
         case 'Q':
            {
                int add = 0;
                ++n;
                while (n < s.length() && isdigit(s[n]))
                    add = 10*add + s[n++] - '0';
                n += add;
                assert(n < s.length());
                return s.substr(n);
            }
         case 'T':
            /* T<n> */
            while (++n < s.length() && isdigit(s[n]))
                ++n;
            return s.substr(n);
         case 'F':
            /* F<T>..._<TR> */
            {
                std::string r = s.substr(n+1);
                while (r.length() && r[0] != '_')
                    r = eat_type(r);
                return eat_type(r.substr(1));
            }
         case 'i':              // int
         case 'h':              // half == short
         case 'l':              // long
         case 'j':              // long long
         case 'c':              // char
         case 'f':              // float
         case 'd':              // double
         case 'e':              // extended == long double
         case 'b':              // bool
         case 'w':              // wchar_t
         case 'v':              // void
         case 'E':              // ...
         case 'O':              // ctor return type
            return s.substr(n+1);
         default:
            goto exit_loop;
        }
    }
 exit_loop:
    compile_error("internal error: got an invalid type");
}

/** Return a human-readable description of this type. */
PUBLIC std::string
Type::get_human_readable_type() const
{
    std::string text;
    if (is_qualified(q_Const))
        text += "const ";
    if (is_qualified(q_Volatile))
        text += "volatile ";
    if (is_qualified(q_Restrict))
        text += "restrict ";
    switch (get_kind()) {
     case k_Fundamental:
        return text + "fundamental type " + code;
     case k_Pointer:
        return text + "pointer to " + get_basis_type().get_human_readable_type();
     case k_Reference:
        return text + "reference to " + get_basis_type().get_human_readable_type();
     case k_Function:
        {
            int n = get_num_function_args();
            if (n) {
                text += "function taking (";
                for (int i = 0; i < n; ++i) {
                    if (i)
                        text += ", ";
                    text += get_function_arg(i).get_human_readable_type();
                }
                text += ")";
            } else {
                text += "function without args";
            }
            return text + " returning " + get_return_type().get_human_readable_type();
        }
     case k_Array:
        return text + "array of " + get_basis_type().get_human_readable_type();
     case k_Member:
        return text + "pointer to member of " + get_class_type().get_human_readable_type()
            + " of type " + get_member_type().get_human_readable_type();
     case k_Userdef:
        return text + "user-defined " + code.substr(1);
     case k_Ellipsis:
        return text + "ellipsis";
     case k_Nothing:
        return text + "nothing";
     case k_Template:
        return text + "template arg " + code;
     default:
        assert(0);
    }
}

/******************************* Accessors *******************************/

/** True iff this type is void. */
PUBLIC inline bool
Type::is_void() const
{
    return code.length() && code[0] == 'v';
}

/** True iff this type is a floating-point type. */
PUBLIC inline bool
Type::is_float() const
{
    return code.length() && (code[0] == 'd' || code[0] == 'e' || code[0] == 'f');
}

/** True iff this type is an integral type. */
PUBLIC bool
Type::is_int() const
{
    return code.length() && get_kind() == k_Fundamental && !is_float() && !is_void();
}

/** True iff this type is complete. 3.9p6 */
PUBLIC bool
Type::is_complete() const
{
    if (is_void())
        return false;
    if (get_kind() == k_Userdef)
        return get_type_symbol()->get_status() == Symbol::st_Defined;
    return true;
}

/** Object types, 3.9p9. "An object type is a type that is not a
    function type, not a reference type, and not a reference type" */
PUBLIC bool
Type::is_object_type() const
{
    if (is_void() || get_kind() == k_Function || get_kind() == k_Reference)
        return false;
    return true;
}

/** Arithmetic types, 3.9.1p8. "Integral and floating types are
    collectively called arithmetic types". */
PUBLIC bool
Type::is_arithmetic_type() const
{
    return is_float() || is_int();
}

/** Scalar types, 3.9p10. "Arithmetic types, enumeration types,
    pointer types and pointer to member types, and cv-qualified
    versions of these types are collectively called scalar types." */
PUBLIC bool
Type::is_scalar_type() const
{
    switch (get_kind()) {
     case k_Userdef:
        return is_enum_type();
     case k_Pointer:
     case k_Member:
        return true;
     case k_Fundamental:
        return is_arithmetic_type();
     default:
        return false;
    }
}

/** True if type is POD (3.9p10). */
PUBLIC bool
Type::is_pod() const
{
    if (!is_valid())
        return false;
    switch (get_kind()) {
     case k_Userdef:
        if (Class_symbol* cs = dynamic_cast<Class_symbol*>(get_type_symbol()))
            return cs->is_pod();
        else
            return true;
     case k_Pointer:
     case k_Member:
        return true;
     case k_Fundamental:
        return is_arithmetic_type();
     case k_Array:
        return get_basis_type().is_pod();
     default:
        return false;
    }
}

PUBLIC bool
Type::is_aggregate() const
{
    if (!is_valid())
        return false;
    switch (get_kind()) {
     case k_Array:
        return true;
     case k_Userdef:
        if (Class_symbol* cs = dynamic_cast<Class_symbol*>(get_type_symbol()))
            return cs->is_aggregate();
        else
            return true;
     default:
        return false;
    }
}

/** Compound types, 3.9.2. "Compound types can be constructed in the
    following ways: arrays [...], functions [...], pointers [...],
    references [...], classes [...], unions [...], enumerations [...],
    pointers to non-static class members [...]". Essentially, anything
    that's not fundamental. */
PUBLIC inline bool
Type::is_compound_type() const
{
    return get_kind() != k_Fundamental;
}

PUBLIC bool
Type::is_enum_type() const
{
    return (get_kind() == k_Userdef && get_type_symbol()->get_kind() == Symbol::k_Enum);
}

PUBLIC bool
Type::is_class_type() const
{
    return (get_kind() == k_Userdef && get_type_symbol()->get_kind() != Symbol::k_Enum);
}

/** Given a user-defined type, return the corresponding Type_symbol. */
PUBLIC Type_symbol*
Type::get_type_symbol() const
{
    assert(get_kind() == k_Userdef);

    std::string::size_type s = code.find_first_not_of("0123456789", 1);
    Type_symbol* sym = dynamic_cast<Type_symbol*>(Symbol_table::get_instance().get_symbol(code.substr(s)).tag);
    assert(sym);

    return sym;
}

/** Return this type, with qualifier /q/ added. */
PUBLIC inline Type
Type::with_qualifier(Type::Qualifier q) const
{
    return Type(code, qualifiers | (1 << q));
}

/** When this is "function-taking-args-a,b,c", return
    "function-taking-args-t,a,b,c". This is needed to make
    surrogate-functions for overloading. */
PUBLIC inline Type
Type::with_first_arg(Type t) const
{
    assert(get_kind() == k_Function);
    Type t2 = *this;
    t2.code.insert(1, t.encode_qualifiers(""));
    return t2;
}

/** Return this type, with the qualifiers from /other/ added. */
PUBLIC inline Type
Type::with_qualifiers(const Type& other) const
{
    return Type(code, qualifiers | other.qualifiers);
}

/** Integral promotions, 4.5. Returns the type after integral
    promotions, with cv-qualifiers removed.
    This also "expands" enums. */
PUBLIC Type
Type::get_promoted_integer() const
{
    if (!code.length())
        return Type();

    /* An rvalue of type char, signed char, unsigned char, short int,
     * or unsigned short int can be converted to an rvalue of type int
     * if int can represent all the values of the source type;
     * other-wise, the source rvalue can be converted to an rvalue of
     * type unsigned int. */
    // MACHINE: I assume they all fit into an int
    if (code == "c" || code == "sc" || code == "uc" || code == "h" || code == "uh")
        return int_type;

    /* An rvalue of type wchar_t (3.9.1) or an enumeration type (7.2)
     * can be converted to an rvalue of the first of the following
     * types that can represent all the values of its underlying type:
     * int, unsigned int, long, or unsigned long. */
    // MACHINE: I assume that wchar_t is uint, and that all enums fit into int
    if (code == "w")
        return uint_type;

    if (code[0] == 'Q') {
        Type_symbol* sym = get_type_symbol();
        if (sym->get_kind() == Symbol::k_Enum)
            return int_type;
    }

    /* An rvalue for an integral bit-field (9.6) can be converted to
     * an rvalue of type int if int can represent all the values of
     * the bit-field; otherwise, it can be converted to unsigned int
     * if unsigned int can rep-resent all the values of the
     * bit-field. If the bit-field is larger yet, no integral
     * promotion applies to it. If the bit-field has an enumerated
     * type, it is treated as any other value of that type for
     * promotion purposes. */
    // we better do that when really reading the bitfield

    /* An rvalue of type bool can be converted to an rvalue of type
     * int, with false becoming zero and true becoming one. */
    if (code == "b")
        return int_type;

    return *this;
}

/** True iff this type can be qualification-converted to /t/. 4.4. */
PUBLIC bool
Type::is_qualification_convertible_to(Type t) const
{
    Kind k = get_kind();
    if ((k != k_Pointer && k != k_Member && k != k_Reference) || k != t.get_kind())
        return false;

    if (k != k_Member) {
        /* 4.4p1: T cv1* => T cv2* if cv1 < cv2
                  T cv1& => T cv2& */
        if (t.get_basis_type().is_more_qualified_than(get_basis_type())
            && t.get_basis_type().is_same_unqualified_type(get_basis_type()))
            return true;
    } else {
        /* 4.4p2: T X::* cv1 => T X::* cv2 if cv1 < cv2 */
        if (t.get_class_type() == get_class_type()
            && t.get_member_type().is_more_qualified_than(get_member_type())
            && t.get_member_type().is_same_unqualified_type(get_member_type()))
            return true;
    }

    /* might be similar:
         *this is  cv1,0 P0 to cv1,1 P1 to ... cv1,n T
         t     is  cv2,0 P0 to cv2,1 P1 to ... cv2,n T

         Pi is either "pointer" or "pointer to member of X"

         cvi,0 are the cv-qualifiers of *this resp. t and can be
         ignored

         \forall j>0: cv1,j <= cv2,j                      [0]

         \forall j>0: cv1,j == cv2,j                      [1]
                   || \forall 0<k<j: const \in cv2,k      [2] */

    bool had_const = true;
    Type t1 = *this, t2 = t;
    while (1) {
        Kind k1 = t1.get_kind(), k2 = t2.get_kind();
        if (k1 != k2)
            return false;       // types are dissimilar
        if (k1 == k_Member) {
            if (t1.get_class_type() != t2.get_class_type())
                return false;
            t1 = t1.get_member_type();
            t2 = t2.get_member_type();
        } else if (k1 == k_Pointer || k1 == k_Reference) {
            t1 = t1.get_basis_type();
            t2 = t2.get_basis_type();
        } else {
            break;
        }
        if (t1.is_same_qualified_as(t2)) {
            /* same qualifiers */
            if (!t2.is_qualified(q_Const))
                had_const = false;           // [2] can't be true any longer
        } else if (t1.is_more_qualified_than(t2)) {
            /* [0] is false, removing qualifiers won't work */
            return false;
        } else if (!had_const) {
            /* [1] is false, and [2] too -> can't work */
            return false;
        }
    }

    /* when we're here, the types are similar so far, we just have to
       check the basis type. */
    return t1.is_same_unqualified_type(t2);
}

/*************************** Fundamental Types ***************************/

#define DECLARE_FUNDAMENTAL(name,type,encoding) Type name(encoding)

// 3.9.1 [basic.fundamental]
DECLARE_FUNDAMENTAL(int_type, int, "i");
DECLARE_FUNDAMENTAL(uint_type, unsigned int, "ui");
DECLARE_FUNDAMENTAL(short_type, short, "h");
DECLARE_FUNDAMENTAL(ushort_type, unsigned short, "uh");
DECLARE_FUNDAMENTAL(long_type, long, "l");
DECLARE_FUNDAMENTAL(ulong_type, unsigned long, "ul");
DECLARE_FUNDAMENTAL(llong_type, long long, "j");
DECLARE_FUNDAMENTAL(ullong_type, unsigned long long, "uj");
DECLARE_FUNDAMENTAL(char_type, char, "c");
DECLARE_FUNDAMENTAL(schar_type, signed char, "sc");
DECLARE_FUNDAMENTAL(uchar_type, unsigned char, "uc");
DECLARE_FUNDAMENTAL(float_type, float, "f");
DECLARE_FUNDAMENTAL(double_type, double, "d");
DECLARE_FUNDAMENTAL(ldouble_type, long double, "e");
DECLARE_FUNDAMENTAL(bool_type, bool, "b");
DECLARE_FUNDAMENTAL(wchar_type, wchar_t, "w");
DECLARE_FUNDAMENTAL(void_type, void, "v");
DECLARE_FUNDAMENTAL(ctor_type, _, "O");

Type size_type = uint_type, ptrdiff_type = int_type;

/** Attempt to parse /tree/ as a type-qualifier. Modifies /type/ accordingly.
    Returns true iff it actually was a type-qualifier. */
bool
parse_qualifier(Ptree* tree, Type& type)
{
    switch (tree->What()) {
     case CONST:
        if (type.is_qualified(Type::q_Const))
            compile_error("multiple `const' not allowed [dcl.type p1]");
        type.add_qualifier(Type::q_Const);
        return true;
     case VOLATILE:
        if (type.is_qualified(Type::q_Volatile))
            compile_error("multiple `volatile' not allowed [dcl.type p1]");
        type.add_qualifier(Type::q_Volatile);
        return true;
     case RESTRICT:
        /* C99 allows this, 6.7.3p4 */
        type.add_qualifier(Type::q_Restrict);
        return true;
     default:
        return false;
    }
}

/****************************** Type_reader ******************************/

/** Private class encapsulating the logic of reading a type
    (type-specifier-seq in standard terms). */
class Type_reader {
    /* Idea: some keywords may appear combined, so we gather their
       frequencies. A simple bitfield doesn't do it because "long" may
       appear twice. Hence we allocate one octal digit per keyword.
       "void"/"bool"/"wchar_t" can only appear once; so we make a
       shortcut for them. */
    enum {
        iInt        = 01,
        iUnsigned   = 010,
        iShort      = 0100,
        iLong       = 01000,
        iSigned     = 010000,
        iFloat      = 0100000,
        iDouble     = 01000000,
        iChar       = 010000000,
    };
    long             mask;        ///< Multi-set of keywords encountered so far.
    Type             user_type;   ///< Scratchspace.
    Type*            builtin;     ///< When a "simple" one-keyword type was seen, this points to that type.
    Type             qualifiers;  ///< Qualifiers gathered so far.
    Ptree*           user_id;     ///< Identifier, if seen.
    Abstract_scope*  scope;       ///< Scope to look up names in.
    
    bool             is_type_declaration;
    Ptree*           name_for_anon;

    Type result;
 public:
    Type get_result() const { return result; }
};

PUBLIC
Type_reader::Type_reader(Abstract_scope* scope, Ptree* tree,
                         bool is_type_declaration,
                         Ptree* name_for_anon)
    : mask(0), builtin(0), user_id(0), scope(scope),
      is_type_declaration(is_type_declaration),
      name_for_anon(name_for_anon)
{
    user_id = read_type(tree);
    if (user_id) {
        if (builtin)
            compile_error("malformed type: identifier + built-in type");

        Symbol_name sym_name(user_id, scope, false);
        if (Symbol_pair p = sym_name.lookup_for_use(false)) {
            if (p.untag->get_kind() == Symbol::k_Typedef) {
                user_type = dynamic_cast<Typedef_symbol*>(p.untag)->get_type();
                builtin = &user_type;
            } else if (Type_symbol* ts = dynamic_cast<Type_symbol*>(p.untag)) {
                user_type = ts->get_type();
                builtin = &user_type;
            } else
                compile_error("name `" + std::string(tree->ToString()) + "' is not a type");
        } else {
            compile_error("name `" + std::string(tree->ToString()) + "' is not defined");
        }
    }

    if (mask && builtin)
        compile_error("Invalid combination of type names");

    /* mask now contains all encountered words. */
    switch (mask) {
     case 0:
        if (builtin)
            result = *builtin;
        else
            compile_error("Missing type name");
        break;
     case iInt:
     case iSigned + iInt:
     case iSigned:
        result = int_type;
        break;
     case iUnsigned:
     case iUnsigned + iInt:
        result = uint_type;
        break;
     case iShort:
     case iShort + iInt:
     case iSigned + iShort:
     case iShort + iShort + iInt:
        result = short_type;
        break;
     case iUnsigned + iShort:
     case iUnsigned + iShort + iInt:
        result = ushort_type;
        break;
     case iLong:
     case iLong + iInt:
     case iSigned + iLong:
     case iSigned + iLong + iInt:
        result = long_type;
        break;
     case iUnsigned + iLong:
     case iUnsigned + iLong + iInt:
        result = ulong_type;
        break;
     case iLong + iLong:
     case iLong + iLong + iInt:
     case iSigned + iLong + iLong:
     case iSigned + iLong + iLong + iInt:
        result = llong_type;
        break;
     case iUnsigned + iLong + iLong:
     case iUnsigned + iLong + iLong + iInt:
        result = ullong_type;
        break;
     case iChar:
        result = char_type;
        break;
     case iUnsigned + iChar:
        result = uchar_type;
        break;
     case iSigned + iChar:
        result = schar_type;
        break;
     case iFloat:
        result = float_type;
        break;
     case iDouble:
        result = double_type;
        break;
     case iLong + iDouble:
        result = ldouble_type;
        break;
     default:
        compile_error("invalid combination of type names");
    }

    /* this happens for `typedef T& x; const x i;', 8.3.2p1 */
    if (result.get_kind() != Type::k_Reference)
        result.copy_qualifiers(qualifiers);
}

/** Read one piece of a type. Input is a weird heap of
    - class/enum specifiers
    - reserved words ("void" et al)
    - user-defined names
    This assimilates the list as far as possible, and returns a pointer
    to the user-defined name, if seen. That is, if the return value is
    null, the list consisted of reserved words and class/enum entirely. */
Ptree*
Type_reader::read_type(Ptree*const tree)
{
    int kind = tree->What();

    if (!tree->IsLeaf() && tree->Car()->Eq("typename")) {
        /* typename NAME */
        if (tree->Length() != 2)
            compile_error("expected identifier after `typename'");
        return tree->Second();
    } else if (kind == ntClassSpec) {
        /* class [name] [body] */
        if (builtin)
            compile_error("class-spec not allowed here");

        Default_class_adder adder;
        user_type = parse_class(tree, scope, name_for_anon, is_type_declaration, adder)->get_type();
        builtin = &user_type;
        return 0;
    } else if (kind == ntEnumSpec) {
        /* enum [name] [body] */
        if (builtin)
            compile_error("enum-spec not allowed here");
        user_type = parse_enum(tree, scope, name_for_anon);
        builtin = &user_type;
        return 0;
    } else if (!tree->IsLeaf()) {
        /* it is a list. Either it contains reserved words plus one
           user-defined identifier, or it is itself a user-defined id. */
        bool had_rw = false;
        Ptree* ptr = 0;
        for (Ptree* p = tree; p; p = p->Cdr()) {
            Ptree* r = read_type(p->Car());
            if (!r) {
                had_rw = true;
            } else if (ptr) {
                /* more than one non-reserved word. The whole thing
                   must be a name */
                // don't assert here in case this is in a sizeof or operator
                // assert(!had_rw);
                if (had_rw)
                    compile_error("a weird type you gave me here");
                return tree;
            } else {
                ptr = r;
                if (p->Cdr() && !p->Second()->IsLeaf() && p->Second()->Car()->Eq('<'))
                    /* template */
                    return tree;
            }
        }
        return ptr;
    } else {
        if (parse_qualifier(tree, qualifiers)) {
            /* nothing */
        } else if (kind == VOID) {
            if (builtin)
                compile_error("`void' not allowed here");
            builtin = &void_type;
        } else if (kind == BOOLEAN) {
            if (builtin)
                compile_error("`bool' not allowed here");
            builtin = &bool_type;
        } else if (kind == WCHAR_T) {
            if (builtin)
                compile_error("`wchar_t' not allowed here");
            builtin = &wchar_type;
        } else {
            unsigned long now = 0;
            switch (tree->What()) {
             case INT:      now = iInt;      break;
             case UNSIGNED: now = iUnsigned; break;
             case SHORT:    now = iShort;    break;
             case LONG:     now = iLong;     break;
             case SIGNED:   now = iSigned;   break;
             case FLOAT:    now = iFloat;    break;
             case DOUBLE:   now = iDouble;   break;
             case CHAR:     now = iChar;     break;
             default:
                return tree;
            }
            /* no word may appear more than twice */
            if (now && (mask & (7*now)) == 2*now)
                compile_error(std::string("`") + tree->ToString() + "' not allowed here");
            mask += now;
        }
        return 0;
    }
}

/** Parse a type.
    \param tree       a parse tree
    \param scope      active scope
    \param name_for_anon if the type is an anonymous class, this will
                      be its name
    \param is_type_declaration if this is a type declaration (i.e.
                      "struct x;"). These have different scoping
                      rules for C combatability.

    This function should not assert-fail on types it doesn't understand.
    OpenC++ often needs us to parse into the blue, so maybe what we get
    isn't actually a type.

    type-specifier ::= simple-type-specifier
                     | class-specifier
                     | enum-specifier
                     | elaborated-type-specifier
                     | cv-qualifier */
Type
parse_type(Ptree* tree, Abstract_scope* scope,
           Ptree* name_for_anon,
           bool is_type_declaration)
{
    if (!tree) {
        return ctor_type;
    } else {
        Type_reader r(scope, tree, is_type_declaration, name_for_anon);
        return r.get_result();
    }
}

/*************************** Function_type_maker ***************************/

/** \class Function_type_maker
    \brief Helper class to construct function types. */

/** Start making a function type. */
PUBLIC
Function_type_maker::Function_type_maker()
    : types("F")
{
}

/** Add a parameter of type /t/ to the function. */
PUBLIC void
Function_type_maker::add_parameter(Type t)
{
    if (t.get_kind() == Type::k_Function)
        /* 13p3.3: function arguments of type "function" are actually
           "pointer to function" */
        t = t.get_unqualified_type().make_pointer_type();
    else if (t.get_kind() == Type::k_Array)
        /* 13p3.4: function arguments of type "array of X" are actually
           "pointer to X" */
        t = t.get_unqualified_type().get_basis_type().make_pointer_type();
    else
        /* 13p3.5: qualifiers don't matter */
        t = t.get_unqualified_type();

    types = t.encode_qualifiers(types);
}

/** Add ellipsis pseudo-type to the function. */
PUBLIC void
Function_type_maker::add_ellipsis()
{
    types.append("E");
}

/** Given a type T, return type function-taking-args-so-far-returning-T */
PUBLIC Type
Function_type_maker::make_function_type(Type return_type) const
{
    return return_type.encode_qualifiers(types + "_");
}

/****************** Function / Storage Class Specifiers ******************/

/** Parse a type-specifier.
    \param tree      one keyword
    \param scs       [in/out] storage class specifier
    \param fs        [in/out] function specifier
    \return true iff this was a valid specifier; parameters modified
    accordingly. */
bool
parse_specifier(Ptree* tree, Storage_class_specifier* scs, Function_specifier_set* fs)
{
    Storage_class_specifier this_scs = s_None;
    Function_specifier      this_fs  = f_None;

    /* 7.1.1p1: At most one storage-class-specifier shall appear in a given
       decl-specifier-seq. */
    /* no similar requirement exists for function specifiers; function
       specifiers can also be combined ("inline virtual" etc.) */
    switch(tree->What()) {
     case STATIC:
        this_scs = s_Static;
        break;
     case AUTO:
        this_scs = s_Auto;
        break;
     case REGISTER:
        this_scs = s_Register;
        break;
     case EXTERN:
        this_scs = s_Extern;
        break;
     case MUTABLE:
        this_scs = s_Mutable;
        break;
     case INLINE:
        this_fs = f_Inline;
        break;
     case VIRTUAL:
        this_fs = f_Virtual;
        break;
     case EXPLICIT:
        this_fs = f_Explicit;
        break;
     default:
        // HACK, because OpenC++ doesn't do it
        if (tree->Eq("explicit")) {
            this_fs = f_Explicit;
            break;
        }
        return false;
    }
    if (this_scs) {
        if (*scs != s_None)
            compile_error("Multiple storage class specifiers in one declaration not allowed, 7.1.1p1");
        *scs = this_scs;
    } else {
        *fs |= this_fs;
    }
    return true;
}

/** Parse a list of storage class/function specifiers into their
    representation.
    \param tree parse tree
    \param scs  [in/out] storage class specifier so far
    \param fs   [in/out] function specifier set so far */
void
parse_specifiers(Ptree* tree,
                 Storage_class_specifier* scs,
                 Function_specifier_set* fs)
{
    if (!tree) {
        /* empty */
    } else if (tree->IsLeaf()) {
        if (!parse_specifier(tree, scs, fs))
            compile_error(std::string("Unknown function/storage class specifier `") + tree->ToString() + "'");
    } else {
        for (Ptree* p = tree; p; p = p->Cdr())
            parse_specifiers(p->Car(), scs, fs);
    }
}

/** Get name of a Storage_class_specifier. */
const char*
get_storage_specifier_name(Storage_class_specifier x)
{
    static const char*const data[] = {
        "none",
        "auto",
        "parameter",
        "register",
        "static",
        "extern",
        "mutable",
        "member"
    };
    return data[x];
}

/** Convert Function_specifier_set to string. */
std::string
get_function_specifier_name(Function_specifier_set s)
{
    std::string data;
    if (s & f_Inline)
        data += " inline";
    if (s & f_Virtual)
        data += " virtual";
    if (s & f_Explicit)
        data += " explicit";
    if (s & f_Abstract)
        data += " abstract";
    if (data.length())
        return data.substr(1);
    else
        return std::string("none");
}

/** Handy helper: make an unary function type
    (function-taking-ARG-and-returning-RET). */
Type
make_unary_function_type(Type arg, Type ret)
{
    Function_type_maker ftm;
    ftm.add_parameter(arg);
    return ftm.make_function_type(ret);
}

Type
make_binary_function_type(Type arg, Type brg, Type ret)
{
    Function_type_maker ftm;
    ftm.add_parameter(arg);
    ftm.add_parameter(brg);
    return ftm.make_function_type(ret);
}