RaresSubst

import Library._

object Substitution {

  def mayBeShadowedBy(bind: Bind, fieldNames: List[String], params: List[String]): Boolean =  {
    val shadow = fieldNames ::: params
    if (!shadow.contains(bind.x)) true else false
  }

  def subst(e: ExprC, nv: List[Bind]): ExprC = e match { // substitue with what cannot shadow
    case NumC(n) => NumC(n)
    case PlusC(l, r) => PlusC(subst(l, nv), subst(r, nv))
    case MultC(l, r) => MultC(subst(l, nv), subst(r, nv))
    case MinusC(l, r) => MinusC(subst(l, nv), subst(r, nv))
    case TrueC() => TrueC()
    case FalseC() => FalseC()
    case EqNumC(l, r) => EqNumC(subst(l, nv), subst(r, nv))

    // Implement the constructs below this line

    case IfC(c, t, e) => IfC(subst(c, nv), subst(t, nv), subst(e, nv))

    case FdC(param, body) =>
      val fdcNv = nv.filter(bind => bind.x != param) // `param` of lambda should not be shadowed
      FdC(param, subst(body, fdcNv))

    case LetC(x, e, body) =>
      val letcNv = nv.filter(bind => bind.x != x) // `x` defined in let should not be shadowed
      LetC(x, subst(e, nv), subst(body, letcNv))

    case AppC(l, r) =>
      AppC(subst(l, nv), subst(r, nv))

    case IdC(x) => (nv.find(bind => bind.x == x)) match {
      case Some(Bind(name, value)) => ValC(value)
      case _ => IdC(x)
    }

    case MsgC(e, method, args) =>
      MsgC(subst(e, nv), method, args.map(arg => subst(arg, nv)))

    case ObjectC(fields, methods) =>
    val fieldNames = fields.map(field => field.name)
    ObjectC(fields.map(field => FieldC(field.name, subst(field.expr, nv))),
            methods.map(method =>
              MethodC(method.name, method.params, subst(method.body, nv.filter(bind => mayBeShadowedBy(bind, fieldNames, method.params))))))

    case ValC(v) => ValC(v)
  }

}