001package org.clafer.ast.analysis;
002
003import gnu.trove.list.array.TIntArrayList;
004import java.util.ArrayList;
005import java.util.HashMap;
006import java.util.Iterator;
007import java.util.List;
008import java.util.Map;
009import java.util.Map.Entry;
010import org.clafer.ast.AstAbstractClafer;
011import org.clafer.ast.AstClafer;
012import org.clafer.ast.AstConcreteClafer;
013import org.clafer.ast.AstRef;
014import org.clafer.ast.AstUtil;
015import org.clafer.collection.Pair;
016import org.clafer.common.Util;
017import org.clafer.graph.GraphUtil;
018import org.clafer.graph.KeyGraph;
019
020/**
021 * This analyzer determines where symmetry is and is not possible.
022 *
023 * @author jimmy
024 */
025public class SymmetryAnalyzer implements Analyzer {
026
027    @Override
028    public Analysis analyze(Analysis analysis) {
029        return breakableChildren(breakableRefs(analysis));
030    }
031
032    /**
033     * Find which children need breaking.
034     *
035     * @param analysis the analysis
036     * @return the analysis
037     */
038    private Analysis breakableChildren(Analysis analysis) {
039        Map<AstClafer, AstConcreteClafer[]> breakableChildren = new HashMap<>();
040        for (AstAbstractClafer clafer : analysis.getAbstractClafers()) {
041            breakableChildren(clafer, breakableChildren, analysis);
042        }
043        breakableChildren(analysis.getModel(), breakableChildren, analysis);
044        return analysis.setBreakableChildrenMap(breakableChildren);
045    }
046
047    private boolean breakableChildren(AstClafer clafer, Map<AstClafer, AstConcreteClafer[]> breakableChildren, Analysis analysis) {
048        List<AstConcreteClafer> breakables = new ArrayList<>();
049        for (AstConcreteClafer child : clafer.getChildren()) {
050            if (breakableChildren(child, breakableChildren, analysis)) {
051                breakables.add(child);
052            }
053        }
054        breakableChildren.put(clafer, breakables.toArray(new AstConcreteClafer[breakables.size()]));
055        AstRef ref = AstUtil.getInheritedRef(clafer);
056        return (clafer instanceof AstConcreteClafer && !analysis.getCard((AstConcreteClafer) clafer).isExact())
057                || !breakables.isEmpty() || (ref != null && analysis.isBreakableRef(ref));
058    }
059
060    /**
061     * Find which references need breaking.
062     *
063     * Does not need breaking.
064     * <pre>
065     * A
066     *     B -> integer
067     * </pre>
068     *
069     * Does need breaking.
070     * <pre>
071     * A
072     *     B -> integer 2
073     * </pre>
074     *
075     * Cannot be broken.
076     * <pre>
077     * A 2
078     *    B -> A
079     * </pre>
080     *
081     * @param analysis the analysis
082     * @return the analysis
083     */
084    private Analysis breakableRefs(Analysis analysis) {
085        // Use this graph to detect when symmetries cannot be broken.
086        KeyGraph<AstClafer> graph = new KeyGraph<>();
087        for (AstClafer clafer : analysis.getClafers()) {
088            if (clafer instanceof AstConcreteClafer) {
089                AstConcreteClafer concreteClafer = (AstConcreteClafer) clafer;
090                if (concreteClafer.hasParent() && analysis.getScope(concreteClafer.getParent()) > 1) {
091                    addDependency(graph, concreteClafer, concreteClafer.getParent(), analysis);
092                }
093                if (concreteClafer.hasSuperClafer()) {
094                    addDependency(graph, concreteClafer, concreteClafer.getSuperClafer(), analysis);
095                }
096            }
097            for (AstConcreteClafer child : clafer.getChildren()) {
098                addDependency(graph, clafer, child, analysis);
099            }
100            if (clafer.hasRef()) {
101                addDependency(graph, clafer, clafer.getRef().getTargetType(), analysis);
102            }
103        }
104
105        Map<AstRef, int[]> breakableRefsMap = new HashMap<>();
106        Map<AstClafer, AstRef[]> breakableTargetsMap = new HashMap<>();
107        for (AstClafer clafer : analysis.getClafers()) {
108            if (clafer.hasRef()) {
109                if (!GraphUtil.hasPath(
110                        graph.getVertex(clafer.getRef().getTargetType()),
111                        graph.getVertex(clafer),
112                        graph)) {
113                    int scope = analysis.getScope(clafer);
114                    TIntArrayList breakableIds = new TIntArrayList();
115                    for (int i = 0; i < scope; i++) {
116                        Pair<AstConcreteClafer, Integer> concreteId = analysis.getConcreteId(clafer, i);
117                        AstConcreteClafer concreteClafer = concreteId.getFst();
118                        int id = concreteId.getSnd().intValue();
119
120                        if (analysis.getCard(concreteClafer).getHigh() == 1) {
121                            /*
122                             * It is possible this ref id does not need to be broken.
123                             * 
124                             * For example:
125                             *     abstract Feature
126                             *         footprint -> integer
127                             *     A : Feature
128                             *     B : Feature 2
129                             * 
130                             * Then the footprints under A do not have symmetry, since
131                             * there is only one A. However, the footprints under B
132                             * do need to be broken.
133                             */
134                            int[] possibleParents =
135                                    analysis.getPartialSolution(concreteClafer).getPossibleParents(id);
136
137                            if (!singleParentScope(concreteClafer.getParent(), possibleParents, analysis)) {
138                                breakableIds.add(i);
139                            }
140                        } else {
141                            breakableIds.add(i);
142                        }
143                    }
144                    if (!breakableIds.isEmpty()) {
145                        breakableRefsMap.put(clafer.getRef(), breakableIds.toArray());
146                    }
147                    AstRef[] breakableTarget = breakableTargetsMap.get(clafer.getRef().getTargetType());
148                    if (breakableTarget == null) {
149                        breakableTarget = new AstRef[]{clafer.getRef()};
150                    } else {
151                        breakableTarget = Util.cons(clafer.getRef(), breakableTarget);
152                    }
153                    breakableTargetsMap.put(clafer.getRef().getTargetType(), breakableTarget);
154                }
155            }
156        }
157        Iterator<Entry<AstClafer, AstRef[]>> iter = breakableTargetsMap.entrySet().iterator();
158        while (iter.hasNext()) {
159            Entry<AstClafer, AstRef[]> entry = iter.next();
160            if (singleSourceScope(entry.getValue(), analysis)) {
161                iter.remove();
162            }
163        }
164        return analysis.setBreakableRefsMap(breakableRefsMap).setBreakableTargetsMap(breakableTargetsMap);
165    }
166
167    private void addDependency(KeyGraph<AstClafer> graph, AstClafer from, AstClafer to, Analysis analysis) {
168        if (analysis.getScope(from) > 1 && analysis.getScope(to) > 1) {
169            graph.getVertex(from).addNeighbour(graph.getVertex(to));
170        }
171    }
172
173    private boolean singleParentScope(AstClafer parentType, int[] possibleIds, Analysis analysis) {
174        for (int id : possibleIds) {
175            Pair<AstConcreteClafer, Integer> concreteId = analysis.getConcreteId(parentType, id);
176            if (analysis.getScope(concreteId.getFst()) > 1) {
177                return false;
178            }
179        }
180        return true;
181    }
182
183    private boolean singleSourceScope(AstRef[] refs, Analysis analysis) {
184        int scope = 0;
185        for (AstRef ref : refs) {
186            scope += analysis.getScope(ref.getSourceType());
187            if (scope > 1) {
188                return false;
189            }
190        }
191        return true;
192    }
193}