class TransferBDD {

  private TransferResult compute(BooleanExpr expr, TransferParam<BDDRoute> p) {

    // TODO: right now everything is IPV4
    if (expr instanceof MatchIpv4) {
      p.debug("MatchIpv4");
      TransferReturn ret = new TransferReturn(p.getData(), factory.one());
      p.debug("MatchIpv4 Result: " + ret);
      return fromExpr(ret);
    }
    if (expr instanceof MatchIpv6) {
      p.debug("MatchIpv6");
      TransferReturn ret = new TransferReturn(p.getData(), factory.zero());
      return fromExpr(ret);
    }

    if (expr instanceof Conjunction) {
      p.debug("Conjunction");
      Conjunction c = (Conjunction) expr;
      BDD acc = factory.one();
      for (BooleanExpr be : c.getConjuncts()) {
        TransferResult r = compute(be, p.indent());
        acc = acc.and(r.getReturnValue().getSecond());
      }
      TransferReturn ret = new TransferReturn(p.getData(), acc);
      p.debug("Conjunction return: " + acc);
      return new TransferResult(ret, factory.zero());
    }

    if (expr instanceof Disjunction) {
      p.debug("Disjunction");
      Disjunction d = (Disjunction) expr;
      BDD acc = factory.zero();
      for (BooleanExpr be : d.getDisjuncts()) {
        TransferResult r = compute(be, p.indent());
        acc = acc.or(r.getReturnValue().getSecond());
      }
      TransferReturn ret = new TransferReturn(p.getData(), acc);
      p.debug("Disjunction return: " + acc);
      return new TransferResult(ret, factory.zero());
    }

    // TODO: thread the BDDRecord through calls
    if (expr instanceof ConjunctionChain) {
      p.debug("ConjunctionChain");
      ConjunctionChain d = (ConjunctionChain) expr;
      List<BooleanExpr> conjuncts = new ArrayList<>(d.getSubroutines());
      if (p.getDefaultPolicy() != null) {
        BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy());
        conjuncts.add(be);
      }
      if (conjuncts.isEmpty()) {
        TransferReturn ret = new TransferReturn(p.getData(), factory.one());
        return fromExpr(ret);
      } else {
        TransferResult result = new TransferResult(p.getData());
        TransferParam<BDDRoute> record = p;
        BDD acc = factory.zero();
        for (int i = conjuncts.size() - 1; i >= 0; i--) {
          BooleanExpr conjunct = conjuncts.get(i);
          TransferParam<BDDRoute> param =
              record
                  .setDefaultPolicy(null)
                  .setChainContext(TransferParam.ChainContext.CONJUNCTION)
                  .indent();
          TransferResult r = compute(conjunct, param);
          record = record.setData(r.getReturnValue().getFirst());
          acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond());
        }
        TransferReturn ret = new TransferReturn(record.getData(), acc);
        return result.setReturnValue(ret);
      }
    }

    if (expr instanceof FirstMatchChain) {
      p.debug("FirstMatchChain");
      FirstMatchChain chain = (FirstMatchChain) expr;
      List<BooleanExpr> chainPolicies = new ArrayList<>(chain.getSubroutines());
      if (p.getDefaultPolicy() != null) {
        BooleanExpr be = new CallExpr(p.getDefaultPolicy().getDefaultPolicy());
        chainPolicies.add(be);
      }
      if (chainPolicies.isEmpty()) {
        // No identity for an empty FirstMatchChain; default policy should always be set.
        throw new BatfishException("Default policy is not set");
      }
      TransferResult result = new TransferResult(p.getData());
      TransferParam<BDDRoute> record = p;
      BDD acc = factory.zero();
      for (int i = chainPolicies.size() - 1; i >= 0; i--) {
        BooleanExpr policyMatcher = chainPolicies.get(i);
        TransferParam<BDDRoute> param =
            record
                .setDefaultPolicy(null)
                .setChainContext(TransferParam.ChainContext.CONJUNCTION)
                .indent();
        TransferResult r = compute(policyMatcher, param);
        record = record.setData(r.getReturnValue().getFirst());
        acc = ite(r.getFallthroughValue(), acc, r.getReturnValue().getSecond());
      }
      TransferReturn ret = new TransferReturn(record.getData(), acc);
      return result.setReturnValue(ret);
    }

    if (expr instanceof Not) {
      p.debug("mkNot");
      Not n = (Not) expr;
      TransferResult result = compute(n.getExpr(), p);
      TransferReturn r = result.getReturnValue();
      TransferReturn ret = new TransferReturn(p.getData(), r.getSecond().not());
      return new TransferResult(ret, factory.zero());
    }

    if (expr instanceof MatchProtocol) {
      MatchProtocol mp = (MatchProtocol) expr;
      Set<RoutingProtocol> rps = mp.getProtocols();
      if (rps.size() > 1) {
        // Hack: Minesweeper doesn't support MatchProtocol with multiple arguments.
        List<BooleanExpr> mps = rps.stream().map(MatchProtocol::new).collect(Collectors.toList());
        return compute(new Disjunction(mps), p);
      }
      RoutingProtocol rp = Iterables.getOnlyElement(rps);
      Protocol proto = Protocol.fromRoutingProtocol(rp);
      if (proto == null) {
        p.debug("MatchProtocol(" + rp.protocolName() + "): false");
        TransferReturn ret = new TransferReturn(p.getData(), factory.zero());
        return fromExpr(ret);
      }
      BDD protoMatch = p.getData().getProtocolHistory().value(proto);
      p.debug("MatchProtocol(" + rp.protocolName() + "): " + protoMatch);
      TransferReturn ret = new TransferReturn(p.getData(), protoMatch);
      return fromExpr(ret);
    }

    if (expr instanceof MatchPrefixSet) {
      p.debug("MatchPrefixSet");
      MatchPrefixSet m = (MatchPrefixSet) expr;

      BDD r = matchPrefixSet(p.indent(), _conf, m.getPrefixSet(), p.getData());
      TransferReturn ret = new TransferReturn(p.getData(), r);
      return fromExpr(ret);

      // TODO: implement me
    } else if (expr instanceof MatchPrefix6Set) {
      p.debug("MatchPrefix6Set");
      TransferReturn ret = new TransferReturn(p.getData(), factory.zero());
      return fromExpr(ret);

    } else if (expr instanceof CallExpr) {
      p.debug("CallExpr");
      CallExpr c = (CallExpr) expr;
      String router = _conf.getHostname();
      String name = c.getCalledPolicyName();
      TransferResult r = CACHE.get(router, name);
      if (r != null) {
        return r;
      }
      RoutingPolicy pol = _conf.getRoutingPolicies().get(name);
      r =
          compute(
              pol.getStatements(),
              p.setCallContext(TransferParam.CallContext.EXPR_CALL).indent().enterScope(name));
      CACHE.put(router, name, r);
      return r;

    } else if (expr instanceof WithEnvironmentExpr) {
      p.debug("WithEnvironmentExpr");
      // TODO: this is not correct
      WithEnvironmentExpr we = (WithEnvironmentExpr) expr;
      // TODO: postStatements() and preStatements()
      return compute(we.getExpr(), p.deepCopy());

    } else if (expr instanceof MatchCommunitySet) {
      p.debug("MatchCommunitySet");
      MatchCommunitySet mcs = (MatchCommunitySet) expr;
      BDD c = matchCommunitySet(p.indent(), _conf, mcs.getExpr(), p.getData());
      TransferReturn ret = new TransferReturn(p.getData(), c);
      return fromExpr(ret);

    } else if (expr instanceof MatchCommunities) {
      p.debug("MatchCommunities");
      MatchCommunities mc = (MatchCommunities) expr;
      // we only handle the case where the expression being matched is just the input communities
      if (!mc.getCommunitySetExpr().equals(InputCommunities.instance())) {
        throw new BatfishException(
            "Matching for communities other than the input communities is not supported: " + mc);
      }
      BDD mcPredicate =
          mc.getCommunitySetMatchExpr()
              .accept(new CommunitySetMatchExprToBDD(), new Arg(this, p.getData()));
      TransferReturn ret = new TransferReturn(p.getData(), mcPredicate);
      return fromExpr(ret);

    } else if (expr instanceof BooleanExprs.StaticBooleanExpr) {
      BooleanExprs.StaticBooleanExpr b = (BooleanExprs.StaticBooleanExpr) expr;
      TransferReturn ret;
      switch (b.getType()) {
        case CallExprContext:
          p.debug("CallExprContext");
          BDD x1 = mkBDD(p.getCallContext() == TransferParam.CallContext.EXPR_CALL);
          ret = new TransferReturn(p.getData(), x1);
          return fromExpr(ret);
        case CallStatementContext:
          p.debug("CallStmtContext");
          BDD x2 = mkBDD(p.getCallContext() == TransferParam.CallContext.STMT_CALL);
          ret = new TransferReturn(p.getData(), x2);
          return fromExpr(ret);
        case True:
          p.debug("True");
          ret = new TransferReturn(p.getData(), factory.one());
          return fromExpr(ret);
        case False:
          p.debug("False");
          ret = new TransferReturn(p.getData(), factory.zero());
          return fromExpr(ret);
        default:
          throw new BatfishException(
              "Unhandled " + BooleanExprs.class.getCanonicalName() + ": " + b.getType());
      }

    } else if (expr instanceof MatchAsPath) {
      p.debug("MatchAsPath");
      MatchAsPath matchAsPathNode = (MatchAsPath) expr;
      BDD asPathPredicate = matchAsPath(p.indent(), _conf, matchAsPathNode.getExpr(), p.getData());
      TransferReturn ret = new TransferReturn(p.getData(), asPathPredicate);
      return fromExpr(ret);
    }

    throw new BatfishException("TODO: compute expr transfer function: " + expr);
  }

  public  TransferBDD(Graph g, Configuration conf, List<Statement> statements);

}