#include <boost/proto/proto.hpp>

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

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

// The toy IR
struct Base {
  virtual void print(std::ostream &) = 0;
};

class Variable : public Base {
  std::string name;

public:
  Variable(const std::string &n) : name(n) {};

  const std::string &getName(void) const {
    return name;
  }

  void print(std::ostream &out) {
    out << getName();
  }
};

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

struct SymbolTable {
  typedef std::list<shared_ptr<Variable> > VariableList;
  std::list<VariableList> table;

  shared_ptr<Variable> lookup(const std::string &name) {
    VariableList::iterator v =
      std::find_if(table.back().begin(), table.back().end(),
		   std::tr1::bind(NameEqual(), _1, name));
    if (v == table.back().end()) {
      std::cerr << "Did not find variable " << name << '\n';
      return shared_ptr<Variable>(new Variable(name + "_not_found"));
    }
    return *v;
  }

  void addVariable(shared_ptr<Variable> v) {
    table.back().push_back(v);
  }
};

inline std::ostream &operator<<(std::ostream &o,
				const SymbolTable::VariableList &vars)
{
  o << "scopeval(";
  for (SymbolTable::VariableList::const_iterator i = vars.begin(),
	 iend = vars.end();
       i != iend;
       /* NULL */) {
    o << (*i)->getName();
    if (++i != iend) {
      o << ", ";
    }
  }
  o << ")";
  return o;
}

class Add : public Base {
public:
  typedef shared_ptr<Base> child_ptr;

private:
  child_ptr left;
  child_ptr right;

public:
  Add(child_ptr l, child_ptr r) : left(l), right(r) {};

  void print(std::ostream &out) {
    out << "+ ";
    left->print(out);
    out << " ";
    right->print(out);
  }
};

class Assign : public Base {
public:
  typedef shared_ptr<Base> child_ptr;

private:
  child_ptr left;
  child_ptr right;

public:
  Assign(child_ptr l, child_ptr r) : left(l), right(r) {};

  void print(std::ostream &out) {
    out << "= ";
    left->print(out);
    out << " ";
    right->print(out);
  }
};

// Define grammar
struct ConstructExpressionGrammar;
struct ConstructStatementGrammar;
struct ConstructGrammar;

class Domain;

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

namespace keyword {
  struct scope {
    friend std::ostream& operator<<(std::ostream& sout, scope) {
      return sout << "scope";
    }
  };
}

// Convenience typedefs
typedef Wrapper<boost::proto::terminal<std::string>::type> Reference;
typedef boost::proto::plus<ConstructExpressionGrammar,
			   ConstructExpressionGrammar> AddRule;
typedef boost::proto::assign<ConstructExpressionGrammar,
			     ConstructExpressionGrammar> AssignRule;
typedef Wrapper<boost::proto::terminal<keyword::scope>::type> ScopeTerminal;
typedef Wrapper<boost::proto::terminal<SymbolTable::VariableList> >
ScopeValueTerminal;
typedef boost::proto::subscript<
  boost::proto::function<
    ScopeTerminal,
    ScopeValueTerminal
    >,
  ConstructStatementGrammar
  > ScopeRule;

// Semantic Actions

struct PassThroughUnary : boost::proto::callable {
  typedef shared_ptr<Base> result_type;
  
  result_type operator()(shared_ptr<Base> expr) {
    return expr;
  }
};

// Transform a one-operand node
template<typename NodeType,
	 typename Child = typename NodeType::child_ptr,
	 typename Dummy = boost::proto::callable>
struct ConstructUnary : boost::proto::callable {
  typedef shared_ptr<NodeType> result_type;
  
  result_type operator()(Child child) {
    return result_type(new NodeType(child));
  }
};

// Transform a two-operand node
template<typename NodeType,
	 typename Child = typename NodeType::child_ptr,
	 typename Dummy = boost::proto::callable>
struct ConstructBinary : boost::proto::callable {
  typedef shared_ptr<NodeType> result_type;

  result_type operator()(Child left, Child right) {
    return result_type(new NodeType(left, right));
  }
};

// Add a scope
struct AddScope : boost::proto::callable {
  typedef shared_ptr<SymbolTable> result_type;

  result_type operator()(shared_ptr<SymbolTable> symtab,
			 SymbolTable::VariableList &scope) {
    symtab->table.push_back(scope);
    return symtab;
  }
};

// Lookup a symbol
template<typename Dummy = boost::proto::callable>
struct LookupSymbol : boost::proto::callable {
  typedef shared_ptr<Variable> result_type;
  
  result_type operator()(shared_ptr<SymbolTable> symtab,
			 const std::string &name) {
    return symtab->lookup(name);
  }
};

// Grammar rules
struct ConstructExpressionGrammarCases {
  // The primary template matches nothing:
  template<typename Tag>
  struct case_ : boost::proto::not_<boost::proto::_> {};
};

template<>
struct ConstructExpressionGrammarCases::case_<boost::proto::tag::terminal>
  : boost::proto::or_<
  boost::proto::when<
    Reference,
    LookupSymbol<>(boost::proto::_data, boost::proto::_value)> > {};

template<>
struct ConstructExpressionGrammarCases::case_<boost::proto::tag::plus>
  : boost::proto::when<
  AddRule,
  ConstructBinary<
    Add,
    shared_ptr<Base> >(ConstructExpressionGrammar(boost::proto::_left),
		       ConstructExpressionGrammar(boost::proto::_right))> {};

struct ConstructExpressionGrammar :
  boost::proto::switch_<ConstructExpressionGrammarCases> {};

struct ConstructStatementGrammarCases {
  // The primary template matches nothing:
  template<typename Tag>
  struct case_ : boost::proto::not_<boost::proto::_> {};
};

template<>
struct ConstructStatementGrammarCases::case_<boost::proto::tag::assign>
  : boost::proto::when<
  AssignRule,
  ConstructBinary<
    Assign,
    shared_ptr<Base> >(ConstructExpressionGrammar(boost::proto::_left),
		       ConstructExpressionGrammar(boost::proto::_right))> {};

template<>
struct ConstructStatementGrammarCases::case_<keyword::scope>
  : boost::proto::when<
  ScopeRule,
  PassThroughUnary(ConstructStatementGrammar(
                     boost::proto::_right,
		     boost::proto::_state,
		     AddScope(boost::proto::_data,
			      boost::proto::_value(
			        boost::proto::_right(
			          boost::proto::_left)))))> {};

struct ConstructStatementGrammar :
  boost::proto::switch_<ConstructStatementGrammarCases> {};

// General IR grammar.
struct ConstructGrammar
  : boost::proto::or_<
  ConstructExpressionGrammar,
  ConstructStatementGrammar> {};

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

const ScopeTerminal scope = {{}};

template<typename Expr>
shared_ptr<Base> translate(const Expr &expr) {
  shared_ptr<SymbolTable> symtab(new SymbolTable);
  symtab->table.push_back(SymbolTable::VariableList());

  // Set up the global scope to resolve references to a, b and c.
  shared_ptr<Variable> av(new Variable("a"));
  shared_ptr<Variable> bv(new Variable("b"));
  shared_ptr<Variable> cv(new Variable("c"));

  symtab->addVariable(av);
  symtab->addVariable(bv);
  symtab->addVariable(cv);

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

int main(void)
{
  Reference a = {"a"};
  Reference b = {"b"};
  Reference c = {"c"};
  Reference d = {"d"};

  // Set up a 2nd scope level to resolve references to d.
  shared_ptr<Variable> dv(new Variable("d"));
  SymbolTable::VariableList localScope;
  localScope.push_back(dv);

  boost::proto::display_expr(
    a = a + c
  );

  boost::proto::display_expr(
    scope(boost::proto::lit(localScope)) [
      a = a + d
    ]
  );

  shared_ptr<Base> expr = translate(
    a = a + c
  );
 
  expr->print(std::cout);
  std::cout << '\n';
#if 0
  expr = translate(
    scope(boost::proto::lit(localScope)) [
      a = a + d
    ]
  );

  expr->print(std::cout);
  std::cout << '\n';
#endif

  return 0;
}