001package org.clafer.ir.analysis;
002
003import java.util.HashMap;
004import java.util.HashSet;
005import java.util.Map;
006import java.util.Map.Entry;
007import java.util.Set;
008import org.clafer.ir.IrCard;
009import org.clafer.ir.IrIntExpr;
010import org.clafer.ir.IrIntVar;
011import org.clafer.ir.IrModule;
012import org.clafer.ir.IrRewriter;
013import org.clafer.ir.IrSetExpr;
014import org.clafer.ir.IrSetVar;
015import static org.clafer.ir.Irs.*;
016
017/**
018 *
019 * @author jimmy
020 */
021public class Canonicalizer {
022
023    private Canonicalizer() {
024    }
025
026    /**
027     * Rewrites the module in a form that is easier to pattern match and makes
028     * some implicit constraints explicit.
029     *
030     * @param module the module to canonicalize
031     * @return the canonicalized module
032     */
033    public static IrModule canonical(IrModule module) {
034        CanonicalRewriter rewriter = new CanonicalRewriter();
035
036        IrModule optModule = rewriter.rewrite(module, null);
037        for (Entry<IrSetVar, IrIntVar> entry : rewriter.setVarCards.entrySet()) {
038            optModule.addConstraint(equal(entry.getValue(), card(entry.getKey())));
039        }
040        rewriter.setVars.removeAll(rewriter.setVarCards.keySet());
041        for (IrSetVar setVar : rewriter.setVars) {
042            if (setVar.getCard().getLowBound() > setVar.getKer().size()
043                    || setVar.getCard().getHighBound() < setVar.getEnv().size()) {
044                // These variables need to have their cardinalities constrainted.
045                optModule.addConstraint(equal(
046                        domainInt("|" + setVar.getName() + "|", setVar.getCard()),
047                        card(setVar)));
048            }
049        }
050        return optModule;
051    }
052
053    private static class CanonicalRewriter extends IrRewriter<Void> {
054
055        private final Set<IrSetVar> setVars = new HashSet<>();
056        private final Map<IrSetVar, IrIntVar> setVarCards = new HashMap<>();
057
058        @Override
059        public IrIntExpr visit(IrCard ir, Void a) {
060            /*
061             * |Literal| is a very common expression that is used very often.
062             * Instead, rewrite as NewVar = |Literal| so that every reference
063             * to |Literal| can use the same variable.
064             */
065            IrSetExpr set = rewrite(ir.getSet(), a);
066            if (set instanceof IrSetVar) {
067                IrSetVar setVar = (IrSetVar) set;
068                IrIntVar card = setVarCards.get(setVar);
069                if (card == null) {
070                    card = domainInt("|" + setVar.getName() + "|", setVar.getCard());
071                    setVarCards.put(setVar, card);
072                }
073                return card;
074            }
075            return changed(ir.getSet(), set)
076                    ? card(set)
077                    : ir;
078        }
079
080        @Override
081        public IrSetVar visit(IrSetVar ir, Void a) {
082            setVars.add(ir);
083            return ir;
084        }
085    };
086}