@Test public void testMergeComposed_RemoveSourceConstraint_AddSourceConstraint_no_merge() { BDDSourceManager mgr = BDDSourceManager.forSources( PKT, ImmutableSet.of("a", "b", "c", "d"), ImmutableSet.of("a", "b")); checkState( !mgr.isValidValue().isOne(), "manager needs to have nontrivial isValidValue constraint"); RemoveSourceConstraint remove = new RemoveSourceConstraint(mgr); AddSourceConstraint add = new AddSourceConstraint(mgr, "a"); assertNull(mergeComposed(remove, add)); }
public static @Nullable Transition mergeComposed(Transition t1, Transition t2) { if (t1 == ZERO || t2 == ZERO) { return ZERO; } if (t1 == IDENTITY) { return t2; } if (t2 == IDENTITY) { return t1; } if (t1 instanceof Constraint && t2 instanceof Constraint) { BDD bdd1 = ((Constraint) t1).getConstraint(); BDD bdd2 = ((Constraint) t2).getConstraint(); return constraint(bdd1.and(bdd2)); } if (t1 instanceof Constraint && t2 instanceof Branch) { BDD constraintBdd = ((Constraint) t1).getConstraint(); Branch branch = (Branch) t2; BDD guard = ((Branch) t2).getGuard(); if (!constraintBdd.andSat(guard)) { return compose(t1, branch.getFalseBranch()); } if (!constraintBdd.diffSat(guard)) { return compose(t1, branch.getTrueBranch()); } } if (t1 instanceof Constraint && t2 instanceof EraseAndSet) { BDD constraintBdd = ((Constraint) t1).getConstraint(); EraseAndSet eas = (EraseAndSet) t2; BDD eraseVars = eas.getEraseVars(); if (constraintBdd.exist(eraseVars).equals(constraintBdd)) { return eraseAndSet(eraseVars, constraintBdd.and(eas.getSetValue())); } } if (t1 instanceof Constraint && t2 instanceof RemoveSourceConstraint) { BDD constraintBdd = ((Constraint) t1).getConstraint(); BDDSourceManager mgr = ((RemoveSourceConstraint) t2).getSourceManager(); BDDFiniteDomain<String> finiteDomain = mgr.getFiniteDomain(); return compose( constraint(constraintBdd.and(finiteDomain.getIsValidConstraint())), eraseAndSet(finiteDomain.getVar(), constraintBdd.getFactory().one())); } if (t1 instanceof EraseAndSet && t2 instanceof Constraint) { EraseAndSet eas = (EraseAndSet) t1; BDD vars = eas.getEraseVars(); BDD value = eas.getSetValue(); BDD constraint = ((Constraint) t2).getConstraint(); return eraseAndSet(vars, value.and(constraint)); } if (t1 instanceof EraseAndSet && t2 instanceof EraseAndSet) { EraseAndSet eas1 = (EraseAndSet) t1; EraseAndSet eas2 = (EraseAndSet) t2; BDD vars1 = eas1.getEraseVars(); BDD vars2 = eas2.getEraseVars(); BDD val1 = eas1.getSetValue(); BDD val2 = eas2.getSetValue(); if (vars1.equals(vars2)) { return eas2; } else if (vars1.exist(vars2).equals(vars1)) { return eraseAndSet(vars1.and(vars2), val1.and(val2)); } else { return eraseAndSet(vars1.and(vars2), val1.exist(vars2).and(val2)); } } if (t1 instanceof RemoveSourceConstraint && t2 instanceof AddSourceConstraint) { RemoveSourceConstraint remove = (RemoveSourceConstraint) t1; AddSourceConstraint add = (AddSourceConstraint) t2; BDDSourceManager mgr = remove.getSourceManager(); if (!mgr.isValidValue().isOne()) { return null; } checkState( mgr.getFiniteDomain().getVar() == add.getSourceManager().getFiniteDomain().getVar(), "all source managers should have the same BDDInteger"); BDDInteger var = mgr.getFiniteDomain().getVar(); return eraseAndSet(var, add.getSourceBdd()); } return null; }
Transitions { public static @Nullable Transition mergeComposed(Transition t1, Transition t2) { if (t1 == ZERO || t2 == ZERO) { return ZERO; } if (t1 == IDENTITY) { return t2; } if (t2 == IDENTITY) { return t1; } if (t1 instanceof Constraint && t2 instanceof Constraint) { BDD bdd1 = ((Constraint) t1).getConstraint(); BDD bdd2 = ((Constraint) t2).getConstraint(); return constraint(bdd1.and(bdd2)); } if (t1 instanceof Constraint && t2 instanceof Branch) { BDD constraintBdd = ((Constraint) t1).getConstraint(); Branch branch = (Branch) t2; BDD guard = ((Branch) t2).getGuard(); if (!constraintBdd.andSat(guard)) { return compose(t1, branch.getFalseBranch()); } if (!constraintBdd.diffSat(guard)) { return compose(t1, branch.getTrueBranch()); } } if (t1 instanceof Constraint && t2 instanceof EraseAndSet) { BDD constraintBdd = ((Constraint) t1).getConstraint(); EraseAndSet eas = (EraseAndSet) t2; BDD eraseVars = eas.getEraseVars(); if (constraintBdd.exist(eraseVars).equals(constraintBdd)) { return eraseAndSet(eraseVars, constraintBdd.and(eas.getSetValue())); } } if (t1 instanceof Constraint && t2 instanceof RemoveSourceConstraint) { BDD constraintBdd = ((Constraint) t1).getConstraint(); BDDSourceManager mgr = ((RemoveSourceConstraint) t2).getSourceManager(); BDDFiniteDomain<String> finiteDomain = mgr.getFiniteDomain(); return compose( constraint(constraintBdd.and(finiteDomain.getIsValidConstraint())), eraseAndSet(finiteDomain.getVar(), constraintBdd.getFactory().one())); } if (t1 instanceof EraseAndSet && t2 instanceof Constraint) { EraseAndSet eas = (EraseAndSet) t1; BDD vars = eas.getEraseVars(); BDD value = eas.getSetValue(); BDD constraint = ((Constraint) t2).getConstraint(); return eraseAndSet(vars, value.and(constraint)); } if (t1 instanceof EraseAndSet && t2 instanceof EraseAndSet) { EraseAndSet eas1 = (EraseAndSet) t1; EraseAndSet eas2 = (EraseAndSet) t2; BDD vars1 = eas1.getEraseVars(); BDD vars2 = eas2.getEraseVars(); BDD val1 = eas1.getSetValue(); BDD val2 = eas2.getSetValue(); if (vars1.equals(vars2)) { return eas2; } else if (vars1.exist(vars2).equals(vars1)) { return eraseAndSet(vars1.and(vars2), val1.and(val2)); } else { return eraseAndSet(vars1.and(vars2), val1.exist(vars2).and(val2)); } } if (t1 instanceof RemoveSourceConstraint && t2 instanceof AddSourceConstraint) { RemoveSourceConstraint remove = (RemoveSourceConstraint) t1; AddSourceConstraint add = (AddSourceConstraint) t2; BDDSourceManager mgr = remove.getSourceManager(); if (!mgr.isValidValue().isOne()) { return null; } checkState( mgr.getFiniteDomain().getVar() == add.getSourceManager().getFiniteDomain().getVar(), "all source managers should have the same BDDInteger"); BDDInteger var = mgr.getFiniteDomain().getVar(); return eraseAndSet(var, add.getSourceBdd()); } return null; } }
Transitions { public static @Nullable Transition mergeComposed(Transition t1, Transition t2) { if (t1 == ZERO || t2 == ZERO) { return ZERO; } if (t1 == IDENTITY) { return t2; } if (t2 == IDENTITY) { return t1; } if (t1 instanceof Constraint && t2 instanceof Constraint) { BDD bdd1 = ((Constraint) t1).getConstraint(); BDD bdd2 = ((Constraint) t2).getConstraint(); return constraint(bdd1.and(bdd2)); } if (t1 instanceof Constraint && t2 instanceof Branch) { BDD constraintBdd = ((Constraint) t1).getConstraint(); Branch branch = (Branch) t2; BDD guard = ((Branch) t2).getGuard(); if (!constraintBdd.andSat(guard)) { return compose(t1, branch.getFalseBranch()); } if (!constraintBdd.diffSat(guard)) { return compose(t1, branch.getTrueBranch()); } } if (t1 instanceof Constraint && t2 instanceof EraseAndSet) { BDD constraintBdd = ((Constraint) t1).getConstraint(); EraseAndSet eas = (EraseAndSet) t2; BDD eraseVars = eas.getEraseVars(); if (constraintBdd.exist(eraseVars).equals(constraintBdd)) { return eraseAndSet(eraseVars, constraintBdd.and(eas.getSetValue())); } } if (t1 instanceof Constraint && t2 instanceof RemoveSourceConstraint) { BDD constraintBdd = ((Constraint) t1).getConstraint(); BDDSourceManager mgr = ((RemoveSourceConstraint) t2).getSourceManager(); BDDFiniteDomain<String> finiteDomain = mgr.getFiniteDomain(); return compose( constraint(constraintBdd.and(finiteDomain.getIsValidConstraint())), eraseAndSet(finiteDomain.getVar(), constraintBdd.getFactory().one())); } if (t1 instanceof EraseAndSet && t2 instanceof Constraint) { EraseAndSet eas = (EraseAndSet) t1; BDD vars = eas.getEraseVars(); BDD value = eas.getSetValue(); BDD constraint = ((Constraint) t2).getConstraint(); return eraseAndSet(vars, value.and(constraint)); } if (t1 instanceof EraseAndSet && t2 instanceof EraseAndSet) { EraseAndSet eas1 = (EraseAndSet) t1; EraseAndSet eas2 = (EraseAndSet) t2; BDD vars1 = eas1.getEraseVars(); BDD vars2 = eas2.getEraseVars(); BDD val1 = eas1.getSetValue(); BDD val2 = eas2.getSetValue(); if (vars1.equals(vars2)) { return eas2; } else if (vars1.exist(vars2).equals(vars1)) { return eraseAndSet(vars1.and(vars2), val1.and(val2)); } else { return eraseAndSet(vars1.and(vars2), val1.exist(vars2).and(val2)); } } if (t1 instanceof RemoveSourceConstraint && t2 instanceof AddSourceConstraint) { RemoveSourceConstraint remove = (RemoveSourceConstraint) t1; AddSourceConstraint add = (AddSourceConstraint) t2; BDDSourceManager mgr = remove.getSourceManager(); if (!mgr.isValidValue().isOne()) { return null; } checkState( mgr.getFiniteDomain().getVar() == add.getSourceManager().getFiniteDomain().getVar(), "all source managers should have the same BDDInteger"); BDDInteger var = mgr.getFiniteDomain().getVar(); return eraseAndSet(var, add.getSourceBdd()); } return null; } private  Transitions(); }
Transitions { public static @Nullable Transition mergeComposed(Transition t1, Transition t2) { if (t1 == ZERO || t2 == ZERO) { return ZERO; } if (t1 == IDENTITY) { return t2; } if (t2 == IDENTITY) { return t1; } if (t1 instanceof Constraint && t2 instanceof Constraint) { BDD bdd1 = ((Constraint) t1).getConstraint(); BDD bdd2 = ((Constraint) t2).getConstraint(); return constraint(bdd1.and(bdd2)); } if (t1 instanceof Constraint && t2 instanceof Branch) { BDD constraintBdd = ((Constraint) t1).getConstraint(); Branch branch = (Branch) t2; BDD guard = ((Branch) t2).getGuard(); if (!constraintBdd.andSat(guard)) { return compose(t1, branch.getFalseBranch()); } if (!constraintBdd.diffSat(guard)) { return compose(t1, branch.getTrueBranch()); } } if (t1 instanceof Constraint && t2 instanceof EraseAndSet) { BDD constraintBdd = ((Constraint) t1).getConstraint(); EraseAndSet eas = (EraseAndSet) t2; BDD eraseVars = eas.getEraseVars(); if (constraintBdd.exist(eraseVars).equals(constraintBdd)) { return eraseAndSet(eraseVars, constraintBdd.and(eas.getSetValue())); } } if (t1 instanceof Constraint && t2 instanceof RemoveSourceConstraint) { BDD constraintBdd = ((Constraint) t1).getConstraint(); BDDSourceManager mgr = ((RemoveSourceConstraint) t2).getSourceManager(); BDDFiniteDomain<String> finiteDomain = mgr.getFiniteDomain(); return compose( constraint(constraintBdd.and(finiteDomain.getIsValidConstraint())), eraseAndSet(finiteDomain.getVar(), constraintBdd.getFactory().one())); } if (t1 instanceof EraseAndSet && t2 instanceof Constraint) { EraseAndSet eas = (EraseAndSet) t1; BDD vars = eas.getEraseVars(); BDD value = eas.getSetValue(); BDD constraint = ((Constraint) t2).getConstraint(); return eraseAndSet(vars, value.and(constraint)); } if (t1 instanceof EraseAndSet && t2 instanceof EraseAndSet) { EraseAndSet eas1 = (EraseAndSet) t1; EraseAndSet eas2 = (EraseAndSet) t2; BDD vars1 = eas1.getEraseVars(); BDD vars2 = eas2.getEraseVars(); BDD val1 = eas1.getSetValue(); BDD val2 = eas2.getSetValue(); if (vars1.equals(vars2)) { return eas2; } else if (vars1.exist(vars2).equals(vars1)) { return eraseAndSet(vars1.and(vars2), val1.and(val2)); } else { return eraseAndSet(vars1.and(vars2), val1.exist(vars2).and(val2)); } } if (t1 instanceof RemoveSourceConstraint && t2 instanceof AddSourceConstraint) { RemoveSourceConstraint remove = (RemoveSourceConstraint) t1; AddSourceConstraint add = (AddSourceConstraint) t2; BDDSourceManager mgr = remove.getSourceManager(); if (!mgr.isValidValue().isOne()) { return null; } checkState( mgr.getFiniteDomain().getVar() == add.getSourceManager().getFiniteDomain().getVar(), "all source managers should have the same BDDInteger"); BDDInteger var = mgr.getFiniteDomain().getVar(); return eraseAndSet(var, add.getSourceBdd()); } return null; } private  Transitions(); static Transition branch(BDD guard, Transition thn, Transition els); static Transition compose(Transition... transitions); static @Nullable Transition mergeComposed(Transition t1, Transition t2); static Transition constraint(BDD bdd); static Transition eraseAndSet(BDD var, BDD value); static Transition eraseAndSet(BDDInteger var, BDD value); @Deprecated static Transition or(); static Transition or(Transition... transitions); static Transition addLastHopConstraint(
      @Nullable LastHopOutgoingInterfaceManager mgr,
      String sendingNode,
      String sendingIface,
      String recvNode,
      String recvIface); static Transition addNoLastHopConstraint(
      @Nullable LastHopOutgoingInterfaceManager mgr, String recvNode, String recvIface); static Transition addOutgoingOriginalFlowFiltersConstraint(
      BDDOutgoingOriginalFlowFilterManager mgr); static Transition addOriginatingFromDeviceConstraint(BDDSourceManager mgr); static Transition addSourceInterfaceConstraint(BDDSourceManager mgr, String iface); static Transition removeNodeSpecificConstraints(
      String node,
      @Nullable LastHopOutgoingInterfaceManager lastHopMgr,
      BDDOutgoingOriginalFlowFilterManager originalFlowFilterMgr,
      BDDSourceManager sourceMgr); @VisibleForTesting static Transition removeOutgoingInterfaceConstraints(
      BDDOutgoingOriginalFlowFilterManager mgr); @VisibleForTesting static Transition removeSourceConstraint(BDDSourceManager mgr); static Transition reverse(Transition transition); }
Transitions { public static @Nullable Transition mergeComposed(Transition t1, Transition t2) { if (t1 == ZERO || t2 == ZERO) { return ZERO; } if (t1 == IDENTITY) { return t2; } if (t2 == IDENTITY) { return t1; } if (t1 instanceof Constraint && t2 instanceof Constraint) { BDD bdd1 = ((Constraint) t1).getConstraint(); BDD bdd2 = ((Constraint) t2).getConstraint(); return constraint(bdd1.and(bdd2)); } if (t1 instanceof Constraint && t2 instanceof Branch) { BDD constraintBdd = ((Constraint) t1).getConstraint(); Branch branch = (Branch) t2; BDD guard = ((Branch) t2).getGuard(); if (!constraintBdd.andSat(guard)) { return compose(t1, branch.getFalseBranch()); } if (!constraintBdd.diffSat(guard)) { return compose(t1, branch.getTrueBranch()); } } if (t1 instanceof Constraint && t2 instanceof EraseAndSet) { BDD constraintBdd = ((Constraint) t1).getConstraint(); EraseAndSet eas = (EraseAndSet) t2; BDD eraseVars = eas.getEraseVars(); if (constraintBdd.exist(eraseVars).equals(constraintBdd)) { return eraseAndSet(eraseVars, constraintBdd.and(eas.getSetValue())); } } if (t1 instanceof Constraint && t2 instanceof RemoveSourceConstraint) { BDD constraintBdd = ((Constraint) t1).getConstraint(); BDDSourceManager mgr = ((RemoveSourceConstraint) t2).getSourceManager(); BDDFiniteDomain<String> finiteDomain = mgr.getFiniteDomain(); return compose( constraint(constraintBdd.and(finiteDomain.getIsValidConstraint())), eraseAndSet(finiteDomain.getVar(), constraintBdd.getFactory().one())); } if (t1 instanceof EraseAndSet && t2 instanceof Constraint) { EraseAndSet eas = (EraseAndSet) t1; BDD vars = eas.getEraseVars(); BDD value = eas.getSetValue(); BDD constraint = ((Constraint) t2).getConstraint(); return eraseAndSet(vars, value.and(constraint)); } if (t1 instanceof EraseAndSet && t2 instanceof EraseAndSet) { EraseAndSet eas1 = (EraseAndSet) t1; EraseAndSet eas2 = (EraseAndSet) t2; BDD vars1 = eas1.getEraseVars(); BDD vars2 = eas2.getEraseVars(); BDD val1 = eas1.getSetValue(); BDD val2 = eas2.getSetValue(); if (vars1.equals(vars2)) { return eas2; } else if (vars1.exist(vars2).equals(vars1)) { return eraseAndSet(vars1.and(vars2), val1.and(val2)); } else { return eraseAndSet(vars1.and(vars2), val1.exist(vars2).and(val2)); } } if (t1 instanceof RemoveSourceConstraint && t2 instanceof AddSourceConstraint) { RemoveSourceConstraint remove = (RemoveSourceConstraint) t1; AddSourceConstraint add = (AddSourceConstraint) t2; BDDSourceManager mgr = remove.getSourceManager(); if (!mgr.isValidValue().isOne()) { return null; } checkState( mgr.getFiniteDomain().getVar() == add.getSourceManager().getFiniteDomain().getVar(), "all source managers should have the same BDDInteger"); BDDInteger var = mgr.getFiniteDomain().getVar(); return eraseAndSet(var, add.getSourceBdd()); } return null; } private  Transitions(); static Transition branch(BDD guard, Transition thn, Transition els); static Transition compose(Transition... transitions); static @Nullable Transition mergeComposed(Transition t1, Transition t2); static Transition constraint(BDD bdd); static Transition eraseAndSet(BDD var, BDD value); static Transition eraseAndSet(BDDInteger var, BDD value); @Deprecated static Transition or(); static Transition or(Transition... transitions); static Transition addLastHopConstraint(
      @Nullable LastHopOutgoingInterfaceManager mgr,
      String sendingNode,
      String sendingIface,
      String recvNode,
      String recvIface); static Transition addNoLastHopConstraint(
      @Nullable LastHopOutgoingInterfaceManager mgr, String recvNode, String recvIface); static Transition addOutgoingOriginalFlowFiltersConstraint(
      BDDOutgoingOriginalFlowFilterManager mgr); static Transition addOriginatingFromDeviceConstraint(BDDSourceManager mgr); static Transition addSourceInterfaceConstraint(BDDSourceManager mgr, String iface); static Transition removeNodeSpecificConstraints(
      String node,
      @Nullable LastHopOutgoingInterfaceManager lastHopMgr,
      BDDOutgoingOriginalFlowFilterManager originalFlowFilterMgr,
      BDDSourceManager sourceMgr); @VisibleForTesting static Transition removeOutgoingInterfaceConstraints(
      BDDOutgoingOriginalFlowFilterManager mgr); @VisibleForTesting static Transition removeSourceConstraint(BDDSourceManager mgr); static Transition reverse(Transition transition); static final Transition IDENTITY; static final Transition ZERO; }