syntax.hpp

Go to the documentation of this file.

#ifndef FUNC_SYNTAX_HPP
#define FUNC_SYNTAX_HPP

#include "func/global.hpp"
#include "func/lexer.hpp"
#include "func/gc.hpp"

class Expr;
class BiOpExpr;
class NumExpr;
class IntExpr;
class IdExpr;
class LambdaExpr;
class AtomExpr;
class IfExpr;
class AnyExpr;
class LetExpr;

enum ExprType : int {
  expr_biop, 
  expr_unop, 
  expr_num, 
  expr_int, 
  expr_id,  
  expr_lambda, 
  expr_atom, 
  expr_if, 
  expr_any, 
  expr_let, 
  expr_fn, 
};

class Environment : public GCObj {
  std::map<std::string, Expr*> variables;
  Environment *parent;
public:
  Lexer *lexer;
  std::vector<Expr*> ctx; 

  Environment(GCMain &gc, Lexer *lexer = nullptr, Environment *parent = nullptr)
    : GCObj(gc), lexer{lexer}, parent{parent}, variables() {}
  virtual ~Environment() {}

  bool contains(const std::string &name) const noexcept;

  const Expr *get(const std::string &name) const noexcept;

  const Expr *currentGet(const std::string &name) const noexcept;

  virtual void mark(GCMain &gc) noexcept override;

  std::map<std::string, Expr*> &getVariables() noexcept
    { return variables; }

  Environment *getParent() const noexcept { return parent; }
};

std::vector<Expr*>::iterator find(std::vector<Expr*> &vec, Expr *expr) noexcept;

template<typename T>
class StackFrameObj {
  Environment &env;
  T* expr;
public:
  StackFrameObj(Environment &env, T *expr = nullptr) noexcept
      : env{env}, expr{expr} {

    if (this->expr) env.ctx.push_back(dynamic_cast<Expr*>(expr));
  }
  
  ~StackFrameObj() {
    if (this->expr) {
      auto it = find(env.ctx, dynamic_cast<Expr*>(this->expr));
      if (it != env.ctx.end()) env.ctx.erase(it);
    }
  }
  
  /*\return Returns contained expression.
   */
  T* operator ->() const noexcept {
    return expr;
  }
  
  T* operator *() const noexcept {
    return expr;
  }
  
  bool operator ==(T *expr) const noexcept {
    return this->expr == expr;
  }

  bool operator ==(StackFrameObj<T> &obj) const noexcept {
    return this->expr == *obj;
  }

  bool operator !=(T *expr) const noexcept {
    return this->expr != expr;
  }

  bool operator !=(StackFrameObj<T> &obj) const noexcept {
    return this->expr != *obj;
  }
  
  StackFrameObj<T>& operator=(T *expr) noexcept {
    if (expr) env.ctx.push_back(dynamic_cast<Expr*>(expr));

    if (this->expr) {
      auto it = find(env.ctx, dynamic_cast<Expr*>(this->expr));
      if (it != env.ctx.end()) env.ctx.erase(it);
    }
  
    this->expr = expr; return *this;
  }
 
  StackFrameObj<T>& operator=(StackFrameObj<T> &obj) noexcept {
    *this = *obj;
    return *this;
  }
 
  operator bool() const {
    return expr != nullptr;
  }
};

class Expr : public GCObj {
  TokenPos pos;
  ExprType type;
protected:
  std::size_t depth;
  Expr *lastEval = nullptr;
public:
  Expr(GCMain &gc, ExprType type, const TokenPos &pos)
      : GCObj(gc), type{type}, pos(pos) {}

  virtual ~Expr() {}

  /*\return Returns a pre-calculated depth of the expresssion.
   */
  std::size_t getDepth() const noexcept { return depth; }

  bool hasLastEval() const noexcept { return lastEval != nullptr; }

  const TokenPos &getTokenPos() const noexcept { return pos; }

  virtual std::string toString() const noexcept { return std::string(); }

  ExprType getExpressionType() const noexcept { return type; }

  virtual Expr *eval(GCMain &gc, Environment &env) noexcept {
    return this;
  }

  Expr *evalWithLookup(GCMain &gc, Environment &env) noexcept;

  virtual Expr *replace(GCMain &gc, const std::string &name, Expr *expr) const noexcept {
    return const_cast<Expr*>(this);
  }

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept
    { return this == expr; }

  virtual std::vector<std::string> getIdentifiers() const noexcept {
    return std::vector<std::string>();
  }

  virtual void mark(GCMain &gc) noexcept override;

  virtual Expr *optimize(GCMain &gc) noexcept;
};

class BiOpExpr : public Expr {
  Operator op;
  Expr *lhs, *rhs;
public:
  BiOpExpr(GCMain &gc, Operator op, Expr *lhs, Expr *rhs)
    : Expr(gc, expr_biop, TokenPos(lhs->getTokenPos(), rhs->getTokenPos())),
      op(op), lhs{lhs}, rhs{rhs} {
    depth = 1 + lhs->getDepth() + rhs->getDepth();
  }

  BiOpExpr(GCMain &gc, const TokenPos &pos, Operator op, Expr *lhs, Expr *rhs)
    : Expr(gc, expr_biop, pos),
      op(op), lhs{lhs}, rhs{rhs} {
    depth = 1 + lhs->getDepth() + rhs->getDepth();   
  }

  virtual ~BiOpExpr() {}

  Operator getOperator() const noexcept { return op; }

  const Expr& getRHS() const noexcept { return *rhs; }

  const Expr& getLHS() const noexcept { return *lhs; }

  virtual std::string toString() const noexcept override {
    if (op == op_fn)
      return lhs->toString() + " " + rhs->toString();

    return "(" + lhs->toString()
      + " " + std::to_string(op) + " " + rhs->toString() + ")";
  }

  virtual void mark(GCMain &gc) noexcept override {
    if (isMarked(gc))
      return;

    markSelf(gc);
    if (lastEval) lastEval->mark(gc);
    lhs->mark(gc);
    rhs->mark(gc);
  }

  virtual Expr *eval(GCMain &gc, Environment &env) noexcept override;
  virtual Expr *replace(GCMain &gc, const std::string &name, Expr *expr) const noexcept override;

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;

  bool isAtomConstructor() const noexcept;

  bool isFunctionConstructor() const noexcept;

  const AtomExpr *getAtomConstructor() const noexcept;

  virtual std::vector<std::string> getIdentifiers() const noexcept override {
    std::vector<std::string> result = getLHS().getIdentifiers();
    for (std::string &id : getRHS().getIdentifiers())
      result.push_back(id);

    return result;
  }

  virtual Expr *optimize(GCMain &gc) noexcept override;

  BiOpExpr *optimize(GCMain &gc, std::vector<Expr*> &exprs) noexcept;
};

class UnOpExpr : public Expr {
  Operator op;
  Expr *expr;
public:
  UnOpExpr(GCMain &gc, const TokenPos &pos, Operator op, Expr *expr)
    : Expr(gc, expr_unop, pos), op{op}, expr{expr} {
    
    depth = 1 + expr->getDepth();
  }

  Operator getOperator() const noexcept { return op; }
  const Expr &getExpression() const noexcept { return *expr; }

  virtual void mark(GCMain &gc) noexcept override;

  virtual Expr *eval(GCMain &gc, Environment &env) noexcept override;
  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;

  virtual Expr *optimize(GCMain &gc) noexcept override;
  virtual UnOpExpr *optimize(GCMain &gc, std::vector<Expr*> &exprs) noexcept;
};

const Expr *assignExpressions(GCMain &gc, Environment &env,
    const Expr *thisExpr,
    const Expr *lhs, const Expr *rhs) noexcept;

class NumExpr : public Expr {
  double num;
public:
  NumExpr(GCMain &gc, const TokenPos &pos, double num)
      : Expr(gc, expr_num, pos), num{num} {
    depth = 1;
  }

  virtual ~NumExpr() {}

  double getNumber() const noexcept { return num; }

  virtual std::string toString() const noexcept override {
    return std::to_string(num);
  }

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;
};

class IntExpr : public Expr {
  std::int64_t num;
public:
  IntExpr(GCMain &gc, const TokenPos &pos, std::int64_t num)
      : Expr(gc, expr_int, pos), num{num} {
    depth = 1;
  }

  virtual ~IntExpr() {}

  std::int64_t getNumber() const noexcept { return num; }

  virtual std::string toString() const noexcept override {
    return std::to_string(num);
  }

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;
};


class IdExpr : public Expr {
  std::string id;
public:
  IdExpr(GCMain &gc, const TokenPos &pos, const std::string &id)
      : Expr(gc, expr_id, pos), id(id) {
    depth = 1;
  }

  virtual ~IdExpr() {}

  const std::string &getName() const noexcept { return id; }

  virtual std::string toString() const noexcept override {
    return id;
  }

  virtual Expr *eval(GCMain &gc, Environment &env) noexcept override;
  virtual Expr *replace(GCMain &gc, const std::string &name, Expr *expr) const noexcept override;

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;

  virtual std::vector<std::string> getIdentifiers() const noexcept override {
    std::vector<std::string> result;
    result.push_back(id);
    return result;
  }
};

class LambdaExpr : public Expr {
  std::string name;
  Expr* expr;
public:
  LambdaExpr(GCMain &gc, const TokenPos &pos, const std::string &name,
             Expr* expr)
      : Expr(gc, expr_lambda, TokenPos(pos, expr->getTokenPos())),
        name(name), expr(std::move(expr)) {
    depth = 1 + expr->getDepth();  
  }

  virtual ~LambdaExpr() {}

  const std::string &getName() const noexcept { return name; }
  const Expr& getExpression() const noexcept { return *expr; }

  virtual std::string toString() const noexcept override {
    return "\\" + name + " = "
      + expr->toString();
  }

  virtual void mark(GCMain &gc) noexcept override {
    if (isMarked(gc))
      return;

    markSelf(gc);
    if (lastEval) lastEval->mark(gc);
    expr->mark(gc);
  }

  /*\return Returns expression where getName() is replaced by expr.
   * \param gc
   * \param expr
   */
  Expr *replace(GCMain &gc, Expr *expr) const noexcept;
  virtual Expr *replace(GCMain &gc, const std::string &name, Expr *expr) const noexcept override;

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;

  virtual std::vector<std::string> getIdentifiers() const noexcept override {
    std::vector<std::string> result = expr->getIdentifiers();
    result.push_back(name);
    return result;
  }

  virtual Expr *optimize(GCMain &gc) noexcept override;
  virtual LambdaExpr *optimize(GCMain &gc, std::vector<Expr*> &exprs) noexcept;
};

class AtomExpr : public Expr {
  std::string id;
public:
  AtomExpr(GCMain &gc, const TokenPos &pos, const std::string &id)
      : Expr(gc, expr_atom, pos), id(id) {
    depth = 1;
  }

  virtual ~AtomExpr() {}

  const std::string &getName() const noexcept { return id; }

  virtual std::string toString() const noexcept override {
    return "." + id;
  }

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;
};

class IfExpr : public Expr {
  Expr *condition, *exprTrue, *exprFalse;
public:
  IfExpr(GCMain &gc, const TokenPos &pos, Expr *condition, Expr *exprTrue, Expr *exprFalse)
    : Expr(gc, expr_if, TokenPos(pos, exprFalse->getTokenPos())),
      condition{condition}, exprTrue{exprTrue}, exprFalse{exprFalse} {
    depth = 1 + condition->getDepth()
      + exprTrue->getDepth() + exprFalse->getDepth();
  }

  virtual ~IfExpr() {}

  const Expr& getCondition() const noexcept { return *condition; }

  const Expr& getTrue() const noexcept { return *exprTrue; }

  const Expr& getFalse() const noexcept { return *exprFalse; }

  virtual std::string toString() const noexcept override {
    return "if " + condition->toString() + " then "
      + exprTrue->toString() + " else " + exprFalse->toString();
  }

  virtual void mark(GCMain &gc) noexcept override {
    if (isMarked(gc))
      return;

    markSelf(gc);
    if (lastEval) lastEval->mark(gc);
    condition->mark(gc);
    exprTrue->mark(gc);
    exprFalse->mark(gc);
  }

  virtual Expr *eval(GCMain &gc, Environment &env) noexcept override;
  virtual Expr *replace(GCMain &gc, const std::string &name, Expr *expr) const noexcept override;

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;

  virtual std::vector<std::string> getIdentifiers() const noexcept override {
    std::vector<std::string> result = condition->getIdentifiers();
    for (std::string &id : exprTrue->getIdentifiers())
      result.push_back(id);
    for (std::string &id : exprFalse->getIdentifiers())
      result.push_back(id);

    return result;
  }

  virtual Expr *optimize(GCMain &gc) noexcept override;
  virtual Expr *optimize(GCMain &gc, std::vector<Expr*> &exprs) noexcept;
};

class AnyExpr : public Expr {
public:
  AnyExpr(GCMain &gc, const TokenPos &pos)
      : Expr(gc, expr_any, pos) {
    depth = 1;
  }
  virtual ~AnyExpr() {}

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;

  virtual std::string toString() const noexcept override {
    return std::string("_");
  }
};

class LetExpr : public Expr {
  std::vector<BiOpExpr*> assignments;
  Expr *body;
public:
  LetExpr(GCMain &gc, const TokenPos &pos, const std::vector<BiOpExpr*> &assignments, Expr *body)
    : Expr(gc, expr_let, TokenPos(pos, body->getTokenPos())),
      assignments(assignments), body{body} {
    depth = 1 + body->getDepth();
    for (BiOpExpr *expr : assignments) depth += expr->getDepth();
  }

  virtual ~LetExpr() {}

  const std::vector<BiOpExpr*> &getAssignments() const noexcept
    { return assignments; }

  const Expr &getBody() const noexcept { return *body; }

  virtual void mark(GCMain &gc) noexcept {
    if (isMarked(gc))
      return;

    markSelf(gc);
    if(lastEval) lastEval->mark(gc);
    for (BiOpExpr *expr : assignments)
      expr->mark(gc);

    body->mark(gc);
  }

  virtual Expr *eval(GCMain &gc, Environment &env) noexcept;
  virtual Expr *replace(GCMain &gc, const std::string &name, Expr *expr) const noexcept override;

  virtual std::vector<std::string> getIdentifiers() const noexcept override {
    std::vector<std::string> result = body->getIdentifiers();
    for (BiOpExpr *expr : assignments)
      for (std::string &id : expr->getIdentifiers())
        result.push_back(id);

    return result;
  }

  virtual bool equals(const Expr *expr, bool exact = false) const noexcept override;

  virtual std::string toString() const noexcept override {
    std::string result = "let ";
    auto &asgs = const_cast<std::vector<BiOpExpr*>&>(assignments);
    for (auto it = asgs.begin(); it != assignments.end(); ++it) {
      if (it != assignments.begin())
        result += "; ";

      result += (*it)->toString();
    }

    return result + " in " + body->toString();
  }

  virtual Expr *optimize(GCMain &gc) noexcept override;
  virtual Expr *optimize(GCMain &gc, std::vector<Expr*> &exprs) noexcept; 
};

class FunctionExpr : public Expr {
  std::string name;
  std::vector<std::pair<std::vector<Expr*>, Expr*>>  fncases;
public:
  FunctionExpr(GCMain &gc, const TokenPos &pos,
      const std::string &name,
      std::pair<std::vector<Expr*>, Expr*> fncase) noexcept;

  virtual ~FunctionExpr() {}

  void calcDepth() noexcept;

  bool addCase(std::pair<std::vector<Expr*>, Expr*> fncase) noexcept;

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

  std::vector<std::pair<std::vector<Expr*>, Expr*>> &getFunctionCases()
    noexcept { return fncases; }
  const std::vector<std::pair<std::vector<Expr*>, Expr*>> &getFunctionCases()
    const noexcept { return fncases; }

  virtual void mark(GCMain &gc) noexcept override;

  virtual Expr *eval(GCMain &gc, Environment &env) noexcept;

  virtual std::string toString() const noexcept override {
    return getName();
  }
};

Expr *reportSyntaxError(Lexer &lexer, const std::string &msg,
    const TokenPos &pos);

Expr *eval(GCMain &gc, Environment &env, Expr *expr) noexcept;

void breadthEval(GCMain &gc, Environment &env,
    StackFrameObj<Expr> &lhs, StackFrameObj<Expr> &rhs) noexcept;

#endif /* FUNC_SYNTAX_HPP */