#include <boost/lexical_cast.hpp>
#include <boost/proto/proto.hpp>
#include <boost/mpl/assert.hpp>

#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
#include <cassert>
#include <tr1/functional>
#include <tr1/memory>

#include <boost/fusion/iterator.hpp>

using std::tr1::bind;
using std::tr1::placeholders::_1;
using std::tr1::shared_ptr;

namespace keyword {
  struct int_ {
    friend std::ostream& operator<<(std::ostream& sout, int_) {
      return sout << "int_";
    }
  };
  struct float_ {
    friend std::ostream& operator<<(std::ostream& sout, float_) {
      return sout << "float_";
    }
  };
  struct function {
    friend std::ostream& operator<<(std::ostream& sout, function) {
      return sout << "function";
    }
  };
  struct void_ {
    friend std::ostream& operator<<(std::ostream& sout, void_) {
      return sout << "void_";
    }
  };
}

class Domain;

template<typename Expr/*, typename Dummy = boost::proto::is_proto_expr*/>
struct Wrapper {
  BOOST_PROTO_EXTENDS(Expr, Wrapper<Expr>, Domain)
};

typedef Wrapper<boost::proto::terminal<int>::type> IntegerTerminal;

typedef Wrapper<boost::proto::terminal<keyword::int_>::type> IntTerminal;
typedef Wrapper<boost::proto::terminal<keyword::float_>::type> FloatTerminal;
typedef Wrapper<boost::proto::terminal<keyword::function>::type> FunctionTerminal;
typedef Wrapper<boost::proto::terminal<keyword::void_>::type> VoidTerminal;

// int_(<num>)
typedef boost::proto::function<
  IntTerminal,
  IntegerTerminal
  > IntRule;

// float_(<num>)
typedef boost::proto::function<
  FloatTerminal,
  IntegerTerminal
  > FloatRule;

typedef boost::proto::or_<
  IntRule,
  FloatRule
  > SimpleTypeRule;

struct TypeRule;

/// Define a rule for a list of types.
struct TypeList;
typedef boost::proto::comma<
  TypeList,
  TypeRule
  > TypeListListPart;

struct TypeList :
    boost::proto::or_<
  TypeRule,
  TypeListListPart
  > {};

// <type>(<list>)
typedef boost::proto::function<
  boost::proto::or_<
    VoidTerminal,
    TypeRule
    >,
  boost::proto::vararg<TypeRule>
  > FunctionTypeWithArgsRule;

// <type>()
typedef boost::proto::function<
  boost::proto::or_<
    VoidTerminal,
    TypeRule
    >
  > FunctionTypeWithoutArgsRule;

typedef boost::proto::or_<
  FunctionTypeWithoutArgsRule,
  FunctionTypeWithArgsRule
  > FunctionTypeRule;

#if 0
typedef FunctionTypeWithArgsRule FunctionTypeRule;
#endif

struct TypeRule : boost::proto::or_<
  SimpleTypeRule,
  FunctionTypeRule
  > {};

struct TypeAccessRule : TypeRule {};
struct FunctionTypeAccessRule : FunctionTypeRule {};

// The toy IR

struct Type {
  virtual std::string getName(void) const = 0;
  void print(std::ostream &out) const {
    out << getName();
  }
};

struct IntType : Type {
  size_t Size;
  IntType(size_t s) : Size(s) {}
  std::string getName(void) const {
    return "int" + boost::lexical_cast<std::string>(Size);
  }
};

struct FloatType : Type {
  size_t Size;
  FloatType(size_t s) : Size(s) {}
  std::string getName(void) const {
    return "float" + boost::lexical_cast<std::string>(Size);
  }
};

struct FunctionType : Type {
  shared_ptr<Type> ReturnType;
  std::vector<shared_ptr<Type> > ArgTypes;
  std::string getName(void) const {
    std::stringstream name;
    if (ReturnType) {
      name << ReturnType->getName() + "(";
    }
    else {
      name << "void(";
    }
    for (std::vector<shared_ptr<Type> >::const_iterator a = ArgTypes.begin(),
           aend = ArgTypes.end();
         a != aend;
         /* NULL */) {
      name << (*a)->getName();
      if (++a != aend) {
        name << ',';
      }
    }
    name << ')';
    return name.str();
  }

  FunctionType(shared_ptr<Type> type) : ReturnType(type) {}

  template<typename Sequence>
  FunctionType(shared_ptr<Type> type,
               Sequence range) 
      : ReturnType(type), ArgTypes(boost::fusion::begin(range),
                                   boost::fusion::end(range)) {} 
};

struct NameEqual : public std::binary_function<shared_ptr<Type>,
					       const std::string &,
					       bool> {
  bool operator()(shared_ptr<Type> t, const std::string &name) {
    return t->getName() == name;
  }
};

struct SymbolTable {
  typedef std::list<shared_ptr<Type> > TypeList;
  std::list<TypeList> table;

  shared_ptr<Type> lookup(const std::string &name) {
    TypeList::iterator v =
      std::find_if(table.back().begin(), table.back().end(),
		   bind(NameEqual(), _1, name));
    if (v == table.back().end()) {
      return shared_ptr<Type>();
    }
    return *v;
  }

  void addType(shared_ptr<Type> t) {
    table.back().push_back(t);
  }
};

// Return a null pointer to Type.
struct ConstructVoidType : boost::proto::callable {
  typedef shared_ptr<Type> result_type;
  result_type operator()(void) {
    return result_type();
  }
};

template<typename Arg>
std::string getName(Arg a, IntType *) {
  return "int" + boost::lexical_cast<std::string>(a);
}

template<typename Arg>
std::string getName(Arg a, FloatType *) {
  return "float" + boost::lexical_cast<std::string>(a);
}

template<typename Arg>
std::string getName(Arg a, FunctionType *) {
  std::stringstream name;
  if (a) {
    name << a->getName() << "()";
  }
  else {
    name << "void()";
  }
  return name.str();
}

template<typename Arg, typename Sequence>
std::string getName(Arg a, Sequence range, FunctionType *) {
  std::stringstream name;
  if (a) {
    name << a->getName() << "(";
  }
  else {
    name << "void(";
  }

  typedef typename boost::fusion::result_of::begin<Sequence>::type iterator;

  for (iterator i = begin(range), ie = end(range);
       i != ie;
       /* NULL */) {
    name << (*i)->getName();
    if ((i = next(i)) != ie) {
      name << ',';
    }
  }

  name << ")";
  return name.str();
}

template<
  typename SymbolType,
  typename Dummy = boost::proto::callable>
struct ConstructUnarySymbol : boost::proto::callable {
  typedef shared_ptr<SymbolType> result_type;

  template<typename Arg>
  result_type operator()(Arg a) {
    std::string name = getName(a, reinterpret_cast<SymbolType *>(0));
    result_type result(new SymbolType(a));
    if (name != result->getName()) {
      std::cerr << "Computed wrong name\n";
      throw;
    }
    return result;
  }
};

template<
  typename SymbolType,
  typename Dummy = boost::proto::callable>
struct ConstructBinarySymbol : boost::proto::callable {
  typedef shared_ptr<SymbolType> result_type;

  template<typename Arg1, typename Arg2>
  result_type operator()(Arg1 a1, Arg2 a2) {
    //boost::fusion::transform_view<Arg2, /* what to use here? */> ...
    std::string name = getName(a1, a2, reinterpret_cast<SymbolType *>(0));
    result_type result(new SymbolType(a1, a2));
    if (name != result->getName()) {
      std::cerr << "Computed wrong name\n";
      throw;
    }
    return result;
  }
};

struct LookupAndAddSymbol : boost::proto::callable {
  typedef shared_ptr<Type> result_type;

  result_type operator()(shared_ptr<SymbolTable> symtab,
                         result_type symbol) {
    result_type result = symtab->lookup(symbol->getName());
    if (!result) {
      symtab->addType(symbol);
      result = symbol;
    }
    else {
      symbol.reset();
    }
    return result;
  }
};

typedef boost::proto::when<
  VoidTerminal,
  ConstructVoidType()
  > VoidBuilder;

/// This is the grammar for integral types.
typedef boost::proto::when<
  IntRule,
  LookupAndAddSymbol(
    boost::proto::_data,
    ConstructUnarySymbol<IntType>(
      boost::proto::_value(boost::proto::_right)))
  > IntBuilder;

/// This is the grammar for floating point types.
typedef boost::proto::when<
  FloatRule,
  LookupAndAddSymbol(
    boost::proto::_data,
    ConstructUnarySymbol<FloatType>(
      boost::proto::_value(boost::proto::_right)))
  > FloatBuilder;

struct TypeBuilder;

/// This is the grammar for function types.
struct FunctionReturnTypeBuilder : boost::proto::or_<
  VoidBuilder,
  TypeBuilder
  > {};

struct FunctionTypeBuilder : boost::proto::or_<
  boost::proto::when<
    FunctionTypeWithoutArgsRule,
    LookupAndAddSymbol(
      boost::proto::_data,
      ConstructUnarySymbol<FunctionType>(
        FunctionReturnTypeBuilder(boost::proto::_left)))
    >,
  boost::proto::when<
    FunctionTypeWithArgsRule,
    LookupAndAddSymbol(
      boost::proto::_data,
      ConstructBinarySymbol<FunctionType>(
        FunctionReturnTypeBuilder(boost::proto::_left),
        // We really want a sequence of transformed expression operands here.
        // See ConstructBinarySymbol for a guess at how to use transform_view.
        boost::proto::functional::pop_front(boost::proto::_expr)))
    >
  > {};

#if 0
struct FunctionTypeBuilder : boost::proto::when<
  FunctionTypeWithArgsRule,
  LookupAndAddSymbol(
    boost::proto::_data,
    ConstructBinarySymbol<FunctionType>(
      FunctionReturnTypeBuilder(boost::proto::_left),
      boost::proto::functional::pop_front(boost::proto::_expr)))
  > {};
#endif

/// This is the grammar to construct types.
struct TypeBuilder : boost::proto::or_<
  IntBuilder,
  FloatBuilder,
  FunctionTypeBuilder
  > {};

struct Domain : boost::proto::domain<boost::proto::pod_generator<Wrapper > > {};

const VoidTerminal void_ = {{}};
const IntTerminal int_ = {{}};

template<typename Grammar, typename Expr>
void
checkMatch(const Expr &expr) {
  BOOST_MPL_ASSERT(( boost::proto::matches<Expr, Grammar> ));
}

template<typename Expr>
shared_ptr<Type> translate(const Expr &expr) {
  shared_ptr<SymbolTable> symtab(new SymbolTable);
  symtab->table.push_back(SymbolTable::TypeList());
  
  checkMatch<TypeBuilder>(expr);

  TypeBuilder trans;
  return trans(expr, 0, symtab);
}

int main(void)
{
  boost::proto::display_expr(
    void_()
  );

  boost::proto::display_expr(
    int_(32)()
  );

  boost::proto::display_expr(
    void_(int_(32), int_(64))
  );

  shared_ptr<Type> type = translate(
    void_()
  );

  type->print(std::cout);
  std::cout << '\n';

  type = translate(
    int_(32)()
  );

  type->print(std::cout);
  std::cout << '\n';

  type = translate(
    void_(int_(32), int_(64))
  );

  type->print(std::cout);
  std::cout << '\n';

  return 0;
}