source: branches/dev-jw-2590/Compiler/ModelicaMiddleEnd/src/jastadd/structural/Graphs.jadd @ 13900

Last change on this file since 13900 was 13900, checked in by jwedin, 7 weeks ago

Changed so that node count dumping is done on the root node instead of statically on ASTNode. Refactored some fields to no longer be static. Changed so that DSSets are given their id in the constructor. #5865

File size: 77.9 KB
Line 
1/*
2    Copyright (C) 2009 Modelon AB
3
4    This program is free software: you can redistribute it and/or modify
5    it under the terms of the GNU General Public License as published by
6    the Free Software Foundation, version 3 of the License.
7
8    This program is distributed in the hope that it will be useful,
9    but WITHOUT ANY WARRANTY; without even the implied warranty of
10    GNU General Public License for more details.
11
12    You should have received a copy of the GNU General Public License
13    along with this program.  If not, see <http://www.gnu.org/licenses/>.
14*/
15
16import java.util.ArrayList;
17import java.util.Collection;
18import java.util.Collections;
19import java.util.Iterator;
20import java.util.LinkedHashMap;
21import java.util.LinkedHashSet;
22import java.util.LinkedList;
23import java.util.ListIterator;
24import java.util.Map;
25import java.util.TreeMap;
26import java.util.Random;
27import java.util.Set;
28import java.util.Stack;
29import java.util.EnumSet;
30
31import org.jmodelica.util.collections.ListMap;
32import org.jmodelica.util.collections.LinkedHashListMap;
33import org.jmodelica.util.collections.FilteredIterator;
34import org.jmodelica.util.collections.HashStack;
35
36import org.jmodelica.util.tarjan.Tarjan;
37import org.jmodelica.util.tarjan.SimpleTarjan;
38import org.jmodelica.util.tarjan.TarjanComponent;
39
40aspect Graphs {
41
42public abstract class AbstractBiPGraph<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>> {
43
44    private static final String DEFAULT_EQ_PREFIX = "eq_";
45    private static final String DEFAULT_EQ_SUBFIX = "";
46   
47    protected Map<String, V> variableMap = new LinkedHashMap<String, V>();
48    protected Map<String, E> equationMap = new LinkedHashMap<String, E>();
49    protected ListMap<FAbstractEquation, E> equationIndexMap = new LinkedHashListMap<FAbstractEquation, E>();
50    private boolean initialSystem = false;
51    private Enumerator enumerator = new Enumerator(1);
52
53    public AbstractBiPGraph() {
54    }
55
56    public <E_OTHER extends AbstractEq<E_OTHER, V_OTHER>, V_OTHER extends AbstractVar<E_OTHER, V_OTHER>> AbstractBiPGraph(Collection<E_OTHER> eqs, Collection<V_OTHER> vars) {
57        for (E_OTHER oldE : eqs)
58            addEquation(oldE.getEquation(), oldE.groupNumber(), oldE.variability(), oldE.type(), oldE.isMeta(), oldE.getName());
59        for (V_OTHER oldV : vars)
60            addVariable(oldV.getName(), oldV.getVariable());
61        for (E_OTHER oldE : eqs) {
62            E e = getEquation(oldE.getName());
63            for (V_OTHER oldV : oldE.getVariables()) {
64                V v = getVariable(oldV.getName());
65                if (v != null)
66                    addInsidence(e, v);
67            }
68        }
69    }
70
71    public <E_OTHER extends AbstractEq<E_OTHER, V_OTHER>, V_OTHER extends AbstractVar<E_OTHER, V_OTHER>> AbstractBiPGraph(Collection<E_OTHER> block, boolean isInitial) {
72        this(block, collectMatchingVariables(block));
73        initialSystem = isInitial;
74        for (E_OTHER e : block) {
75            if (!e.isMeta()) {
76                match(getEquation(e.getName()), getVariable(e.getMatching().getName()));
77            }
78        }
79    }
80
81    private static <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<V> collectMatchingVariables(Collection<E> eqns) {
82        Collection<V> vars = new ArrayList<V>();
83        for (E e : eqns) {
84            if (!e.isMeta()) {
85                vars.add(e.getMatching());
86            }
87        }
88        return vars;
89    }
90
91    public boolean isComplete() {
92        return getUnmatchedVariables().size() == 0 && getUnmatchedEquations().size() == 0;
93    }
94
95    public Collection<E> getEquations() {
96        return equationMap.values();
97    }
98
99    public Collection<V> getVariables() {
100        return variableMap.values();
101    }
102
103    public E getEquation(String name) {
104        return equationMap.get(name);
105    }
106
107    public void setAsInitialSystem() {
108        initialSystem = true;
109        for (E eqn : getEquations()) {
110            if (eqn.groupNumber() != 0) {
111                continue;
112            }
113            for (V var : lookupVars(eqn.getEquation().findInitUniqueDAEVarUsesInTree())) {
114                for (E groupEqn : eqn.getGroupMembers()) {
115                    addEdge(groupEqn, var);
116                }
117            }
118        }
119    }
120
121    public boolean isInitialSystem() {
122        return initialSystem;
123    }
124   
125    public java.util.List<E> getEquations(FAbstractEquation eqn) {
126        return equationIndexMap.getList(eqn);
127    }
128
129    private E addEquation(FAbstractEquation eqn, int groupNumber, TypePrefixVariability variability, FType type, boolean isMeta, String prefix, String subfix, Enumerator enumerator) {
130        String name;
131        do {
132            name = prefix + enumerator.next() + subfix;
133        } while (getEquation(name) != null);
134        return addEquation(eqn, groupNumber, variability, type, isMeta, name);
135    }
136
137    protected E addEquation(FAbstractEquation eqn, int groupNumber, Collection<E> groupMemberList, TypePrefixVariability variability, FType type, String name) {
138        return addEquation(eqn, groupNumber, groupMemberList, variability, type, false, name);
139    }
140
141    protected E addEquation(FAbstractEquation eqn, int groupNumber, TypePrefixVariability variability, FType type, boolean isMeta, String name) {
142        return addEquation(eqn, groupNumber, equationIndexMap.getList(eqn, true), variability, type, isMeta, name);
143    }
144
145    protected E addEquation(FAbstractEquation eqn, int groupNumber, Collection<E> groupMemberList, TypePrefixVariability variability, FType type, boolean isMeta, String name) {
146        E e = equationMap.get(name);
147        if (e != null)
148            throw new IllegalArgumentException("Equation with the name '" + name + "' already exists:\n" + e.getEquation() + "\nNew equation:\n" + eqn);
149        e = createEq(name, eqn, groupNumber, groupMemberList, variability, type, isMeta);
150        equationMap.put(name,e);
151        insertIntoEquationIndexMap(eqn,e);
152        return e;
153    }
154
155    protected abstract E createEq(String name, FAbstractEquation eqn, int groupNumber, Collection<E> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta);
156
157    public V addVariable(FVariable var) {
158        return addVariable(var.name(), var);
159    }
160
161    public V addVariable(String name, FVariable var) {
162        V v = variableMap.get(name);
163        if (v==null) {
164            v = createVar(name, var);
165            variableMap.put(name,v);
166        }       
167        return v;
168    }
169
170    protected abstract V createVar(String name, FVariable var);
171
172    public void removeEquation(E e) {
173        for (V v : e.getVariables()) {
174            if (v.getMatching() == e) {
175                v.setMatching(null);
176            }
177        }
178        e.setMatching(null);
179        e.getVariables().clear();
180        equationMap.remove(e.getName());
181        removeFromEquationIndexMap(e.getEquation(),e);
182    }
183
184    public void removeVariable(V v) {
185        for (E e : getEquations()) {
186            if (e.getMatching() == v) {
187                e.setMatching(null);
188            }
189            e.getVariables().remove(v);
190        }
191        v.setMatching(null);
192        variableMap.remove(v.getName());
193    }
194
195    public void removeVariables(Collection<? extends FVariable> fVars) {
196        for (FVariable fVar : fVars) {
197            V var = getVariable(fVar.name());
198            if (var != null)
199                removeVariable(var);
200        }
201    }
202   
203    public V getVariable(String name) {
204        return variableMap.get(name);
205    }
206
207    public final boolean addEdge(String equationName, String variableName) {
208        return addEdge(getEquation(equationName), getVariable(variableName));
209    }
210
211    public boolean addEdge(E e, V v) {
212        if (v==null || e==null)
213            return false;
214        if (e.getVariables().contains(v))
215            return false;
216        e.addVariable(v);
217        return true;
218    }
219
220    public enum VarType {
221        DERIVATIVE_VARIABLES { 
222            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.derivativeVariables(); }
223            public boolean isOk(TypePrefixVariability variability)               { return variability.continuousVariability(); }
224        },
225        DIFFERENTIATED_VARIABLES { 
226            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.allDifferentiatedRealVariables(); }
227            public boolean isOk(TypePrefixVariability variability)               { return variability.continuousVariability(); }
228        }, 
229        ALGEBRAIC_VARIABLES { 
230            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.normalAlgebraicVariables(); }
231        }, 
232        CONTINUOUS_ALGEBRAIC_VARIABLES { 
233            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.normalAlgebraicContinousRealVariables(); }
234            public boolean isOk(TypePrefixVariability variability)               { return variability.continuousVariability(); }
235        }, 
236        DISCRETE_ALGEBRAIC_VARIABLES { 
237            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.discreteVariables(); }
238            public boolean isOk(TypePrefixVariability variability)               { return variability.discreteVariability(); }
239        }, 
240        DISCRETE_PRE_VARIABLES { 
241            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.discretePreVariables(); }
242            public boolean isOk(TypePrefixVariability variability)               { return variability.discreteVariability(); }
243        },
244        NON_FIXED_PARAMETERS {
245            public Collection<? extends FVariable> variables(BLTVariables c)            { return c.initialParameters(); }
246            public boolean isOk(TypePrefixVariability variability)               { return variability.parameterVariability(); }
247        };
248
249        public abstract Collection<? extends FVariable> variables(BLTVariables c);
250        public boolean isOk(TypePrefixVariability e) { return true; }
251    }
252
253    public void addVariables(BLTVariables variables, EnumSet<VarType> variableTypes) {
254        for (VarType t : variableTypes) {
255            for (FVariable fv : t.variables(variables)) {
256                addVariable(fv.name(), fv);
257            }
258        }
259        for (FVariable fv : variables.extraVariables()) {
260            addVariable(fv.name(), fv);
261        }
262    }
263
264    public void addEquations(Iterable<FAbstractEquation> eqns, EnumSet<VarType> variableTypes) {
265        do_addEquations(eqns, variableTypes, DEFAULT_EQ_PREFIX, enumerator);
266    }
267
268    public void addEquations(Iterable<FAbstractEquation> eqns, EnumSet<VarType> variableTypes, String eqNamePrefix, Enumerator enumerator) {
269        if (eqNamePrefix.equals(DEFAULT_EQ_PREFIX))
270            throw new IllegalArgumentException("The equation name prefix '" + eqNamePrefix + "' is reserved!");
271        do_addEquations(eqns, variableTypes, eqNamePrefix, enumerator);
272    }
273
274    private void do_addEquations(Iterable<FAbstractEquation> eqns, EnumSet<VarType> variableTypes, String eqNamePrefix, Enumerator enumerator) {
275        Set<FVariable> emptySet = Collections.emptySet();
276        for (FAbstractEquation e : eqns) {
277           
278            IncidenceMap incMap = e.createIncidenceMap(this, variableTypes);
279            int n_eq = incMap.numEqs();
280           
281            Collection<E> groupMembers = getEquations(e);
282            int n_existing = 0;
283            int n_existing_meta = 0;
284            for (E eqn : groupMembers) {
285                n_existing += 1;
286                if (eqn.isMeta()) {
287                    n_existing_meta++;
288                }
289            }
290            if (n_existing != 0 && (n_existing - n_existing_meta) != n_eq) {
291                throw new IllegalArgumentException("Equation already exist in BiPGraph but with different number of scalars, previously " + n_existing + ", now " + n_eq + ", equation:\n" + e);
292            }
293            if (n_existing == 0) {
294                groupMembers = new ArrayList<E>();
295                Enumerator subEnumerator = enumerator;
296                String prefix = eqNamePrefix;
297                String subfix = "";
298                if (n_eq > 1) {
299                    subEnumerator = new Enumerator(1);
300                    prefix += enumerator.next() + "[";
301                    subfix = "]";
302                }
303                if (n_eq == 0) {
304                    E eqn = addEquation(e, 0, incMap.variability(0), incMap.type(0), true, prefix, subfix, subEnumerator);
305                    groupMembers.add(eqn);
306                } else {
307                    for (int i = n_eq - 1; 0 <= i; i--) { // During tarjan the order will be reversed,
308                        // need to reverse here to preserve the initial order.
309                        E eqn = addEquation(e, i, incMap.variability(i), incMap.type(i), false, prefix, subfix, subEnumerator);
310                        groupMembers.add(eqn);
311                    }
312                }
313            }
314            for (E eqn : groupMembers) {
315                incMap.addEdges(eqn, false);
316            }
317        }
318    }
319   
320    protected CommonAccessExpLookupVisitor<FAccessExp> getCommonAccessExpLookupVisitor() {
321        if (isInitialSystem()) {
322            return InitDAEVarUseLookupVisitor.instance;
323        } else {
324            return DAEVarUseLookupVisitor.instance;
325        }
326    }
327   
328    /**
329     * Handles incidences between variables in an FAbstractEquation.
330     * The base case is a scalar equation where all variables are
331     * dependent on each other.
332     */
333    protected class IncidenceMap {
334        private Set<V> vars = null;
335        protected final FAbstractEquation equation;
336        protected final VariableResolver<E, V> resolver;
337       
338        public IncidenceMap(FAbstractEquation e, VariableResolver<E, V> resolver) {
339            equation = e;
340            this.resolver = resolver;
341        }
342       
343        protected Set<V> vars() {
344            if (vars == null) {
345                vars = resolver.lookupVars(equation.findCommonAccessExpsInTree(getCommonAccessExpLookupVisitor()));
346            }
347            return vars;
348        }
349       
350        public TypePrefixVariability variability(int i) {
351            return equation.variability();
352        }
353       
354        public FType type(int i) {
355            return equation.type();
356        }
357       
358        public void addEdges(E eqn, boolean log) {
359            for (V var : vars()) {
360                if (log) {
361                    getStepLogger().logVerbose("*** %s", var);
362                }
363                addEdge(eqn, var);
364            }
365        }
366       
367        public int numEqs() {
368            return equation.numScalarEquations();
369        }
370    }
371   
372    /**
373     * An interface that should be implemented by all IncidenceMap classes that
374     * represent an equation which only has one or more variables on the left hand
375     * side (one variable on the left hand side per scalar equation)
376     */
377    protected interface AssignmentIncidenceMap {
378        public Iterable<FAccessExp> rhs(String assignedLHS);
379        public Collection<FAccessExp> assigned();
380    }
381   
382    /**
383     * Handles normal equations which are on the form "x = ...".
384     */
385    protected class SingleAssignmentIncidenceMap extends IncidenceMap implements AssignmentIncidenceMap {
386        private final FAccessExp assigned;
387        private Collection<FAccessExp> rhsUses;
388       
389        public SingleAssignmentIncidenceMap(FEquation eqn, VariableResolver<E, V> resolver) {
390            super(eqn, resolver);
391            assigned = eqn.getLeft().asFAccessExp();
392           
393        }
394       
395        private Collection<FAccessExp> rhsUses() {
396            if (rhsUses == null) {
397                rhsUses = equation.FAccessExpsInRHS(getCommonAccessExpLookupVisitor());
398            }
399            return rhsUses;
400        }
401       
402        @Override
403        public Iterable<FAccessExp> rhs(String assignedLHS) {
404            if (assignedLHS.equals(assigned.name())) {
405                return rhsUses();
406            } else {
407                return Collections.emptyList();
408            }
409        }
410       
411        @Override
412        public Collection<FAccessExp> assigned() {
413            return Collections.singletonList(assigned);
414        }
415    }
416   
417    /**
418     * Handles incidences between variables in a non-scalar FAbstractEquation.
419     * Isolates LHS variables from each other.
420     */
421    protected abstract class MultiIncidenceMap extends IncidenceMap {
422        private Map<Integer, V> lhs = null;
423        private Set<FAccessExp> lhsUses = null;
424        protected final EnumSet<VarType> variableTypes;
425       
426        public MultiIncidenceMap(FAbstractEquation e, VariableResolver<E, V> resolver, EnumSet<VarType> variableTypes) {
427            super(e, resolver);
428            this.variableTypes = variableTypes;
429        }
430       
431        protected Set<FAccessExp> lhsUses() {
432            if (lhsUses == null) {
433                lhsUses = equation.FAccessExpsInLHS(getCommonAccessExpLookupVisitor());
434            }
435            return lhsUses;
436        }
437       
438        protected abstract void computeLHS(Map<Integer, V> lhs);
439       
440        protected Map<Integer, V> lhs() {
441            if (lhs == null) {
442                Map<Integer, V> lhsTmp = new HashMap<Integer, V>();
443                computeLHS(lhsTmp);
444                lhs = lhsTmp;
445            }
446            return lhs;
447        }
448       
449        protected void buildLhsFunction(Map<Integer, V> lhs, EnumSet<VarType> variableTypes) {
450            int i = 0;
451            for (FAccessExp use : lhsUses()) {
452                if (variableTypes != null) {
453                    FAbstractVariable fv = use.myFV();
454                    if (fv != null && !addLhs(fv, variableTypes)) {
455                        continue;
456                    }
457                }
458                buildLhsFunction(lhs, use, i++);
459            }
460        }
461       
462        protected void buildLhsFunction(Map<Integer, V> lhs, FAccessExp use, int i) {
463            V var = getVariable(use.name());
464            lhs.put(i, var);
465        }
466       
467        protected boolean addLhs(FAbstractVariable fv, EnumSet<VarType> variableTypes) {
468            for (VarType t : variableTypes) {
469                if (t.isOk(variability(fv))) {
470                    return true;
471                }
472            }
473            return false;
474        }
475       
476        @Override
477        public TypePrefixVariability variability(int i) {
478            V var = lhs().get(i);
479            if (var == null) {
480                return super.variability(i);
481            }
482            return variability(var.getVariable());
483        }
484       
485        private TypePrefixVariability variability(FAbstractVariable fv) {
486            TypePrefixVariability v = fv.variability();
487            if (v.parameterOrLess()) {
488                v = fv.type().funcOutputVariability();
489            }
490            return v;
491        }
492       
493        @Override
494        public FType type(int i) {
495            V var = lhs().get(i);
496            if (var == null) {
497                return super.type(i);
498            }
499            return var.type();
500        }
501       
502        @Override
503        public void addEdges(E eqn, boolean log) {
504            int i = eqn.groupNumber();
505            V lhsVar = lhs().get(i);
506            for (V var : vars()) {
507                if (var == lhsVar || rhs(i).contains(var)) {
508                    addEdge(eqn, var);
509                }
510            }
511        }
512
513        protected abstract Set<V> rhs(int i);
514
515        @Override
516        public int numEqs() {
517            return lhs().size();
518        }
519    }
520   
521    /**
522     * Handles incidences between variables in a non-scalar FAbstractEquation.
523     * Isolates LHS variables from each other.
524     * Assumes all LHS variables are dependent on all RHS variables.
525     */
526    protected class ManyIncidenceMap extends MultiIncidenceMap {
527       
528        private Set<V> rhs = null;
529       
530        public ManyIncidenceMap(FAbstractEquation e, VariableResolver<E, V> resolver, EnumSet<VarType> variableTypes) {
531            super(e, resolver, variableTypes);
532        }
533       
534        protected Set<V> rhs() {
535            if (rhs == null) {
536                rhs = resolver.lookupVars(equation.FAccessExpsInRHS());
537                if (equation instanceof FAlgorithm) {
538                    rhs.removeAll(resolver.lookupVars(lhsUses()));
539                }
540            }
541            return rhs;
542        }
543       
544        protected void computeLHS(Map<Integer, V> lhs) {
545            if (equation instanceof FFunctionCallEquation) {
546                buildLhsFunction(lhs, variableTypes);
547            } else {
548                buildLhsOther(lhs, variableTypes);
549            }
550        }
551       
552        private void buildLhsOther(Map<Integer, V> lhs, EnumSet<VarType> variableTypes) {
553            int i = 0;
554            for (FAbstractVariable fv : ASTNode.lookupFVariablesInSet(lhsUses())) {
555                if (variableTypes != null) {
556                    if (!addLhs(fv, variableTypes)) {
557                        continue;
558                    }
559                }
560               
561                V var = getVariable(fv.name());
562                lhs.put(i++, var);
563            }
564        }
565       
566        @Override
567        protected Set<V> rhs(int i) {
568            return rhs();
569        }
570    }
571   
572    /**
573     * Handles incidences between variables in a non-scalar FAbstractEquation.
574     * Isolates LHS variables from each other.
575     * Computes RHS dependencies for LHS.
576     */
577    protected class SplitIncidenceMap extends MultiIncidenceMap implements AssignmentIncidenceMap {
578        protected ArrayList<Set<V>> splitMap;
579        protected Map<FAccessExp, Collection<FAccessExp>> resolvedDependencies;
580        private Map<String, FAccessExp> nameToAssignedMap;
581       
582        public SplitIncidenceMap(FFunctionCallEquation e, VariableResolver<E, V> resolver, EnumSet<VarType> variableTypes) {
583            super(e, resolver, variableTypes);
584        }
585       
586        private Map<FAccessExp, Collection<FAccessExp>> sortDependencies(Map<FAccessExp, Set<FAccessExp>> unsortedDependencies) {
587            final Map<String, Integer> varToPosMap = new HashMap<String, Integer>();
588            int counter = 0;
589            for (FAccessExp use : equation.FAccessExpsInRHS()) {
590                if (!varToPosMap.containsKey(use.name())) {
591                    varToPosMap.put(use.name(), counter++);
592                }
593            }
594            Map<FAccessExp, Collection<FAccessExp>> resolvedDependencies = new HashMap<>();
595            for (Map.Entry<FAccessExp, Set<FAccessExp>> entry : unsortedDependencies.entrySet()) {
596                ArrayList<FAccessExp> uses = new ArrayList<>(entry.getValue());
597                Collections.sort(uses, new Comparator<FAccessExp>() {
598                    public int compare(FAccessExp a, FAccessExp b) {
599                        return varToPosMap.get(a.name()) - varToPosMap.get(b.name());
600                    }
601                });
602                resolvedDependencies.put(entry.getKey(), uses);
603            }
604            return resolvedDependencies;
605        }
606       
607        protected Map<FAccessExp, Collection<FAccessExp>> resolvedDependencies() {
608            if (resolvedDependencies == null) {
609                DependencyVariableEvaluator pve = new DependencyVariableEvaluator();
610                FFunctionCallEquation equation = (FFunctionCallEquation) this.equation;
611                try {
612                    equation.getCall().evaluate(pve);
613                    Map<FAccessExp, Set<FAccessExp>> unsortedDependencies = pve.resolveDependencies(equation);
614                    resolvedDependencies = sortDependencies(unsortedDependencies);
615                } catch (ConstantEvaluationException e) {
616                    ASTNode.log.debug("SplitIncidenceMap failed to compute dependency information, falling back to normal heuristics!");
617                    resolvedDependencies = new HashMap<FAccessExp, Collection<FAccessExp>>();
618                    Collection<FAccessExp> rhs = equation.FAccessExpsInRHS();
619                    for (FAccessExp lhs : lhsUses()) {
620                        resolvedDependencies.put(lhs, rhs);
621                    }
622                }
623            }
624            return resolvedDependencies;
625        }
626       
627        protected Map<String, FAccessExp> nameToAssignedMap() {
628            if (nameToAssignedMap == null) {
629                nameToAssignedMap = new HashMap<>();
630                for (FAccessExp use : lhsUses()) {
631                    FAccessExp old = nameToAssignedMap.put(use.name(), use);
632                    if (old != null) {
633                        throw new UnsupportedOperationException("The following equation assignes the same variable twice, " + old + ", this class doesn't handle that:\n" + equation);
634                    }
635                }
636            }
637            return nameToAssignedMap;
638        }
639       
640   
641        @Override
642        protected void computeLHS(Map<Integer, V> lhs) {
643            splitMap = new ArrayList<Set<V>>();
644            buildLhsFunction(lhs, variableTypes);
645        }
646       
647        @Override
648        protected void buildLhsFunction(Map<Integer, V> lhs, FAccessExp use, int i) {
649            super.buildLhsFunction(lhs, use, i);
650            Set<V> s = resolver.lookupVars(resolvedDependencies().get(use));
651            splitMap.add(s);
652        }
653
654        @Override
655        protected Set<V> rhs(int i) {
656            lhs(); // Just ensure that splitMap is computed.
657           return splitMap.get(i);
658        }
659
660        @Override
661        public Collection<FAccessExp> assigned() {
662            return lhsUses();
663        }
664
665        @Override
666        public final Iterable<FAccessExp> rhs(String assignedLHS) {
667            FAccessExp use = nameToAssignedMap().get(assignedLHS);
668            if (use == null) {
669                return Collections.emptyList();
670            } else {
671                return resolvedDependencies().get(use);
672            }
673        }
674       
675    }
676   
677   
678    public boolean match(E e, V v) {
679        if (!canMatch(e, v))
680            return false;
681        if (e.getMatching() != null)
682            e.getMatching().setMatching(null);
683        if (v.getMatching() != null)
684            v.getMatching().setMatching(null);
685        v.setMatching(e);
686        e.setMatching(v);
687        return true;
688    }
689
690    public boolean canMatch(E e, V v) {
691        if (e.isMeta())
692            return false;
693       
694        FAbstractEquation equation = e.getEquation();
695        FVariable variable = v.getVariable();
696       
697        if (!variable.isReal() && !equation.isSolved(variable).isAnalyticallySolvable()) {
698            return false;
699        }
700       
701        if (initialSystem)
702            return true;
703       
704        if (equation instanceof FAlgorithm)
705            return true;
706       
707        // Discrete variables can only be matched to discrete equations.
708        // Except discrete reals in initial system.
709        return variable.isContinuous() || e.variability().discreteVariability() || equation.isInitial();
710    }
711
712    public void addInsidence(E e, V v) {
713        e.addVariable(v);
714    }
715
716    public Collection<E> greedyMatching() {
717        Collection<E> unmatched = new ArrayList<E>();
718        for (E e : getEquations()) {
719            if (e.getMatching() != null)
720                continue;
721            for (V v : e.getVariables()) {
722                if (v.getMatching()==null) {
723                    match(e, v);
724                    break;
725                }
726            }
727            if (e.getMatching() == null)
728                unmatched.add(e);
729        }
730        return unmatched;
731    }
732
733    /**
734     * Comparator that is used during matching of variables to equations. We
735     * need to use a comparator during this since we wan't to prioritize
736     * matching of certain variables. For example, when matching the initial
737     * system, there is usually more variables than equations. In that case it
738     * is better to leave a variable with start value unmatched since we then
739     * can use the start value as an extra initial condition (equation).
740     */
741    private static class VarMatchingComparator implements Comparator<AbstractVar<?,?>> {
742        private Set<FAbstractVariable> hasExtraStartConditions;
743        private VarMatchingComparator(Set<FAbstractVariable> hasExtraStartConditions) {
744            if (hasExtraStartConditions == null)
745                hasExtraStartConditions = Collections.emptySet();
746            this.hasExtraStartConditions = hasExtraStartConditions;
747        }
748       
749        /**
750         * Variable o1 will be prefered over o2 by returning a negative number.
751         * This means that o1 will be matched (if possible) before o2, which
752         * means that we wan't to return a positive number for the variables
753         * that we wan't to be unmatched (and used as initial conditions).
754         */
755        @Override
756        public int compare(AbstractVar<?,?> o1, AbstractVar<?,?> o2) {
757            FVariable v1 = o1.getVariable();
758            FVariable v2 = o2.getVariable();
759           
760            // Variables that has an extra start condition (equation already in
761            // the system) should be matched last
762            boolean b1 = (v1.isPreVariable() && hasExtraStartConditions.contains(v1.myNonPreVariable())) || hasExtraStartConditions.contains(v1);
763            boolean b2 = (v2.isPreVariable() && hasExtraStartConditions.contains(v2.myNonPreVariable())) || hasExtraStartConditions.contains(v2);
764            int diff = (b1 ? 1 : 0) - (b2 ? 1 : 0);
765            if (diff != 0)
766                return diff;
767           
768            // Discrete pre() and continuous variables with start value should
769            // be matched last
770            b1 = (v1.isDiscrete() && v1.isPreVariable() || v1.isContinuous()) && v1.startAttributeSet();
771            b2 = (v2.isDiscrete() && v2.isPreVariable() || v2.isContinuous()) && v2.startAttributeSet();
772            diff = (b1 ? 1 : 0) - (b2 ? 1 : 0);
773            if (diff != 0)
774                return diff;
775           
776            // pre() variables should be matched last (why?)
777            diff = (v1.isPreVariable() ? 1 : 0) - (v2.isPreVariable() ? 1 : 0);
778            if (diff != 0)
779                return diff;
780           
781            // Make the sorting deterministic by comparing the names
782            return o1.getName().compareTo(o2.getName());
783        }
784    }
785
786    public java.util.List<Map<V, Set<E>>> bfs(Collection<E> startingNodes, Comparator<? super V> varComparator) {
787        java.util.List<Map<V, Set<E>>> Lv = new ArrayList<Map<V, Set<E>>>();
788        Set<E> Le_current = new LinkedHashSet<E>();
789        Set<E> Le_next = new LinkedHashSet<E>();
790       
791        Le_current.addAll(startingNodes);
792        // Reset nodes
793        lightReset();
794       
795        int layer = 0;
796        boolean freeVarNodeFound = false;
797        //System.out.println("************** BFS ************* starting nodes: " + startingNodes);
798       
799        while (Le_current.size() > 0 && !freeVarNodeFound) {
800            //System.out.println("*** layer: " + layer);
801            //System.out.println(Lv);
802            //System.out.println(Le_current);
803            Lv.add(new TreeMap<V, Set<E>>(varComparator));
804           
805            for (E s : Le_current) {
806                //System.out.println(" eq: " + s);
807                for (V t : s.getVariables()) {
808                    if (!canMatch(s, t))
809                        continue;
810                    //System.out.println("  " + t + " layer: " + t.getLayer());
811                    if (t.getLayer() >= layer) {
812                        //System.out.println("    adding " + t);
813                        t.setLayer(layer);
814                        Set<E> h = Lv.get(layer).get(t);
815                        if (h == null) {
816                            h = new LinkedHashSet<E>();
817                            Lv.get(layer).put(t, h);
818                        }
819                        h.add(s);
820                        E u = t.getMatching();
821                        if (u != null) {
822                            //System.out.println("     " + t + "'s matching is " + u);
823                            u.setLayer(layer);
824                            Le_next.add(u);
825                        } else {
826                            //System.out.println("     " + t + "has no matching");
827                            freeVarNodeFound = true;
828                        }
829                    }
830                }
831            }
832            layer++;
833            Le_current = Le_next;
834            Le_next = new LinkedHashSet<E>();
835        }
836       
837        java.util.List<V> delQueue = new ArrayList<V>();
838        for (V v : Lv.get(Lv.size() - 1).keySet()) {
839            if (v.getMatching() != null) {
840                delQueue.add(v);
841            }
842        }
843        for (V v : delQueue) {
844            Lv.get(Lv.size() - 1).remove(v);
845        }
846        //System.out.println(Lv);
847        //System.out.println("************** BFS ends *************");
848        return Lv;
849    }
850
851    public java.util.List<java.util.List<Edge>> dfs(java.util.List<Map<V, Set<E>>> Lv) {
852        lightReset();
853        java.util.List<java.util.List<Edge>> P = new ArrayList<java.util.List<Edge>>();
854       
855        boolean found_path = true;
856        for (V v : Lv.get(Lv.size() - 1).keySet()) {
857            ArrayList<Edge> P_tmp = new ArrayList<Edge>();
858           
859            ListIterator<Map<V, Set<E>>> iter = Lv.listIterator(Lv.size());
860            while (iter.hasPrevious()) {
861                Map<V, Set<E>> l = iter.previous();
862                v.setVisited(true);
863                if (!found_path) {
864                    break;
865                }
866                found_path = false;
867                for (E e : l.get(v)) {
868                    if (!e.isVisited() && canMatch(e, v)) {
869                        e.setVisited(true);
870                        P_tmp.add(new Edge(e, v));
871                        v = e.getMatching();
872                        found_path = true;
873                        break;
874                    }
875                }
876            }
877            if (P_tmp.size() == Lv.size()) {
878                P.add(P_tmp);
879            }
880        }
881        //System.out.println(P);
882        return P;
883    }
884
885    public void reassign(java.util.List<java.util.List<Edge>> P) {
886        for (java.util.List<Edge> l : P) {
887            for (Edge ed : l) {
888                match(ed.getEquation(), ed.getVariable());
889            }
890        }
891    }
892
893    public void maximumMatching(boolean resetMatching) {
894        maximumMatching(resetMatching, null);
895    }
896
897    public void maximumMatching(boolean resetMatching, Set<FAbstractVariable> hasExtraStartConditions) {
898        if (resetMatching) {
899            reset();
900            greedyMatching();
901        }
902       
903        // Initialize set of free equations
904        Set<E> startingNodes = new LinkedHashSet<E>();
905        for (E e : getEquations()) {
906            if (e.getMatching()==null) {
907                startingNodes.add(e);
908            }
909        }
910       
911        Set<E> unmatchedEquations = new LinkedHashSet<E>(getUnmatchedEquations());
912       
913        java.util.List<Map<V, Set<E>>> Lv = null;
914        java.util.List<java.util.List<Edge>> P = null;
915        Comparator<? super V> varComparator = new VarMatchingComparator(hasExtraStartConditions);
916       
917        while (unmatchedEquations.size()>0) {
918           
919            Lv = bfs(unmatchedEquations, varComparator);
920            P = dfs(Lv);
921           
922            if (Lv.get(Lv.size()-1).size()==0) {
923                break;
924            }
925           
926            reassign(P);
927           
928            for (java.util.List<Edge> l : P) {
929                unmatchedEquations.remove(l.get(l.size()-1).getEquation());
930            }
931        }
932    }
933
934    protected class UnmatchedEquationsCriteria implements Criteria<E> {
935        @Override
936        public boolean test(E elem) {
937            return elem.getMatching() == null && !elem.isMeta();
938        }
939    }
940
941    public Iterator<E> unmatchedEquationsIterator() {
942        return new FilteredIterator<E>(getEquations().iterator(), new UnmatchedEquationsCriteria());
943    }
944
945    public Iterable<E> unmatchedEquationsIterable() {
946        return new Iterable<E>() {
947            @Override
948            public Iterator<E> iterator() {
949                return unmatchedEquationsIterator();
950            }
951        };
952    }
953
954    public Collection<E> getUnmatchedEquations() {
955        java.util.List<E> l = new ArrayList<E>();
956        for (E e : unmatchedEquationsIterable())
957            l.add(e);
958        return l;
959    }
960
961    protected class UnmatchedVariablesCriteria implements Criteria<AbstractVar<?,?>> {
962        @Override
963        public boolean test(AbstractVar<?,?> elem) {
964            return elem.getMatching() == null;
965        }
966    }
967
968    public Iterator<V> unmatchedVariablesIterator() {
969        return new FilteredIterator<V>(getVariables().iterator(), new UnmatchedVariablesCriteria());
970    }
971
972    public Iterable<V> unmatchedVariablesIterable() {
973        return new Iterable<V>() {
974            @Override
975            public Iterator<V> iterator() {
976                return unmatchedVariablesIterator();
977            }
978        };
979    }
980
981    public Collection<V> getUnmatchedVariables() {
982        java.util.List<V> l = new ArrayList<V>();
983        for (V v : unmatchedVariablesIterable())
984            l.add(v);
985        return l;
986    }
987
988    public java.util.List<E> getMatchedEquations() {
989        java.util.List<E> l = new ArrayList<E>();
990        for (E e : getEquations()) {
991            if (e.getMatching()!=null) {
992                l.add(e);
993            }
994        }
995        return l;
996    }
997
998    public java.util.List<V> getMatchedVariables() {
999        java.util.List<V> l = new ArrayList<V>();
1000        for (V v : getVariables()) {
1001            if (v.getMatching()!=null) {
1002                l.add(v);
1003            }
1004        }
1005        return l;
1006    }
1007
1008    public Collection<E> getVisitedEquations() {
1009        Collection<E> l = new ArrayList<E>();
1010        for (E e: getEquations()) {
1011            if (e.isVisited())
1012                l.add(e);
1013        }
1014        return l;
1015    }
1016
1017    public Collection<V> getVisitedVariables() {
1018        Collection<V> l = new ArrayList<V>();
1019        for (V v: getVariables()) {
1020            if (v.isVisited())
1021                l.add(v);
1022        }
1023        return l;
1024    }
1025
1026    private static Collection<SCCContributor> SCCContributors;
1027
1028    /**
1029     * Adds a new strongly connected component contributor to the list of
1030     * contributors.
1031     */
1032    private static <T extends SCCContributor> T addSCCContributor(T contributor) {
1033        if (SCCContributors == null)
1034            SCCContributors = new ArrayList<SCCContributor>();
1035        SCCContributors.add(contributor);
1036        return contributor;
1037    }
1038
1039    /**
1040     * Retrieves the list of strongly connected component contributors.
1041     * This method should always be used since it ensures that the list is
1042     * initialized properly.
1043     */
1044    public static Collection<SCCContributor> getSCCContributors() {
1045        if (SCCContributors == null)
1046            SCCContributors = new ArrayList<SCCContributor>();
1047        return SCCContributors;
1048    }
1049   
1050    /**
1051     * Abstract class for describing arc contributors to Tarjan's strongly
1052     * connected components algorithm.
1053     */
1054    public static abstract class SCCContributor {
1055        private final String option;
1056       
1057        private SCCContributor() {
1058            option = null;
1059        }
1060
1061        private SCCContributor(String option) {
1062            this.option = option;
1063        }
1064
1065        public boolean isActive(StepUtil stepUtil) {
1066            return option == null || stepUtil != null && stepUtil.getOptionRegistry().getBooleanOption(option);
1067        }
1068
1069        /**
1070         * This method returns a list of equations that the supplied equation
1071         * depend on. This method is implemented by the overriding class.
1072         *
1073         * Surounding BiPGraph is provided for convenience
1074         */
1075        public abstract <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> members(E equation, AbstractBiPGraph<E, V, ?> graph);
1076
1077        /**
1078         * This method returns a list of equations that the supplied equation
1079         * should be in the same group as. It is important that there is a
1080         * symmetry in the lists returned. If A return a list containing B and
1081         * C. Then the list for B should contain A and C, finally the list for
1082         * C should contain A and B. Unexepected behaviour otherwise! The list
1083         * for A may contain A itself. This method is implemented by the
1084         * overriding class.
1085         *
1086         * Use this method instead of members() when it is known from the start
1087         * that the lists are symetric. The implementation that backs this
1088         * method is way more efficient for large lists.
1089         *
1090         * Surounding BiPGraph is provided for convenience
1091         */
1092        public abstract <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> sameBlockMembers(E equation, AbstractBiPGraph<E, V, ?> graph);
1093
1094        /**
1095         * This method returns a map that map an equation to a list of object
1096         * identifiers. All equations that are associated with the same object
1097         * identifier are kept in the same block.
1098         *
1099         * Surounding BiPGraph is provided for convenience
1100         */
1101        public abstract <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Map<E, Collection<? extends Object>> memberSets(E equation, AbstractBiPGraph<E, V, ?> graph);
1102       
1103        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>> Collection<C> mergeComponents(Collection<C> components, AbstractBiPGraph<E, V, ?> graph) {
1104            return components;
1105        }
1106    }
1107   
1108    private static final GroupMemberContributor GROUP_MEMBER_CONTRIBUTOR = new GroupMemberContributor();
1109   
1110    /**
1111     * Contributor that describes the relationship between BiPGrah equations
1112     * that link to the same AST equation, for example FFunctionCallEquations.
1113     */
1114    private static class GroupMemberContributor extends SCCContributor {
1115       
1116        @Override
1117        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> members(E equation, AbstractBiPGraph<E, V, ?> graph) {
1118            return Collections.emptyList();
1119        }
1120       
1121        @Override
1122        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> sameBlockMembers(E equation, AbstractBiPGraph<E, V, ?> graph) {
1123            return equation.getGroupMembers();
1124        }
1125
1126       
1127        @Override
1128        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Map<E, Collection<? extends Object>> memberSets(E equation, AbstractBiPGraph<E, V, ?> graph) {
1129            return Collections.emptyMap();
1130        }
1131    }
1132   
1133   
1134    private static final HomotopyContributor HOMOTOPY_CONTRIBUTOR = addSCCContributor(new HomotopyContributor());
1135   
1136    /**
1137     * Contributor that ensures that all equations with homotopy are computed in the same block.
1138     */
1139    private static class HomotopyContributor extends SCCContributor {
1140       
1141        private static final Collection<? extends Object> memberSets = Arrays.asList("homotopy");
1142       
1143        @Override
1144        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> members(E equation, AbstractBiPGraph<E, V, ?> graph) {
1145            return Collections.emptyList();
1146        }
1147
1148        @Override
1149        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Collection<E> sameBlockMembers(E equation, AbstractBiPGraph<E, V, ?> graph) {
1150            return Collections.emptyList();
1151        }
1152
1153        @Override
1154        public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> Map<E, Collection<? extends Object>> memberSets(E equation, AbstractBiPGraph<E, V, ?> graph) {
1155            if (!graph.isInitialSystem() || graph.insideHomotopySimplified() || !equation.getEquation().containsFHomotopyExp()) {
1156                return Collections.emptyMap();
1157            }
1158            Map<E, Collection<? extends Object>> eqsIdentMap = new HashMap<E, Collection<? extends Object>>();
1159            eqsIdentMap.put(equation, memberSets);
1160            return eqsIdentMap;
1161        }
1162    }
1163   
1164    protected abstract C createComponentBlock();
1165
1166    public Collection<C> tarjan(boolean forceGroupMembersIntoSameBlock) {
1167        return tarjan(null, forceGroupMembersIntoSameBlock);
1168    }
1169   
1170
1171    public Collection<C> tarjan(StepUtil stepUtil, boolean forceGroupMembersIntoSameBlock) {
1172        return tarjan(stepUtil, Collections.<SCCContributor>emptyList(), forceGroupMembersIntoSameBlock);
1173    }
1174
1175    public Collection<C> tarjan(StepUtil stepUtil, Collection<SCCContributor> extraContributors,
1176            boolean forceGroupMembersIntoSameBlock) {
1177        tarjanReset();
1178       
1179        Collection<SCCContributor> groupMemberContributors;
1180        if (forceGroupMembersIntoSameBlock) {
1181            groupMemberContributors = Collections.<SCCContributor>singletonList(GROUP_MEMBER_CONTRIBUTOR);
1182        } else {
1183            groupMemberContributors = Collections.<SCCContributor>emptyList();
1184        }
1185       
1186        Collection<SCCContributor> contributors = new ArrayList<SCCContributor>();
1187        for (SCCContributor contributor : new ChainedIterable<SCCContributor>(getSCCContributors(), groupMemberContributors, extraContributors)) {
1188            if (!contributor.isActive(stepUtil))
1189                continue;
1190            contributors.add(contributor);
1191        }
1192       
1193       
1194        BiPTarjan tarjan = new BiPTarjan(contributors);
1195        Collection<C> components = tarjan.tarjan(getEquations());
1196//        for (SCCContributor contributor : contributors) {
1197//            components = contributor.mergeComponents(components, this);
1198//        }
1199        return components;
1200    }
1201
1202    private class BiPTarjan extends Tarjan<E, C> {
1203       
1204        private final Collection<SCCContributor> contributors;
1205        Map<E, Collection<Collection<E>>> keepTogetherMap = new LinkedHashMap<E, Collection<Collection<E>>>();
1206       
1207        public BiPTarjan(Collection<SCCContributor> contributors) {
1208            this.contributors = contributors;
1209            Map<Object, Collection<E>> memberSetsMap = new HashMap<Object, Collection<E>>();
1210            for (SCCContributor contributor : contributors) {
1211                for (E equation : getEquations()) {
1212                    for (Map.Entry<E, Collection<? extends Object>> eqIdent : contributor.memberSets(equation, AbstractBiPGraph.this).entrySet()) {
1213                        for (Object identifier : eqIdent.getValue()) {
1214                            Collection<E> memberSet = memberSetsMap.get(identifier);
1215                            if (memberSet == null) {
1216                                memberSet = new ArrayList<E>();
1217                                memberSetsMap.put(identifier, memberSet);
1218                            }
1219                            Collection<Collection<E>> keepTogetherLists = keepTogetherMap.get(eqIdent.getKey());
1220                            if (keepTogetherLists == null) {
1221                                keepTogetherLists = new ArrayList<Collection<E>>();
1222                                keepTogetherMap.put(eqIdent.getKey(), keepTogetherLists);
1223                            }
1224                            memberSet.add(eqIdent.getKey());
1225                            keepTogetherLists.add(memberSet);
1226                        }
1227                    }
1228                }
1229            }
1230        }
1231
1232        @Override
1233        protected boolean visited(E e) {
1234            return e.isVisited();
1235        }
1236
1237        @Override
1238        protected void setVisited(E e, boolean val) {
1239            e.setVisited(val);
1240        }
1241
1242        @Override
1243        protected boolean shouldVisit(E e) {
1244            return e.tarjanVisit();
1245        }
1246
1247        @Override
1248        protected void addPredecessors(E e, Collection<E> predecessors) {
1249            for (V v : e.getVariables()) {
1250                E ee = v.getMatching();
1251                if (ee != null && e != ee && v.tarjanVisit())
1252                    predecessors.add(ee);
1253            }
1254            for (SCCContributor contributor : contributors)
1255                for (E ee : contributor.members(e, AbstractBiPGraph.this))
1256                    if (e != ee && ee.tarjanVisit())
1257                        predecessors.add(ee);
1258        }
1259
1260        @Override
1261        protected int getIndex(E e) {
1262            return e.getTarjanNbr();
1263        }
1264
1265        @Override
1266        protected void setIndex(E e, int val) {
1267            e.setTarjanNbr(val);
1268        }
1269
1270        @Override
1271        protected int getLowLink(E e) {
1272            return e.getTarjanLowLink();
1273        }
1274
1275        @Override
1276        protected void setLowLink(E e, int val) {
1277            e.setTarjanLowLink(val);
1278        }
1279
1280        @Override
1281        protected void forceIntoSame(E e, Set<E> members) {
1282            members.remove(e); // Added later
1283            forceIntoSameInternal(e, members);
1284        }
1285
1286        private void forceIntoSameInternal(E e, Set<E> members) {
1287            if (members.contains(e)) {
1288                return;
1289            }
1290            members.add(e);
1291            Collection<Collection<E>> keepTogetherLists = keepTogetherMap.get(e);
1292            if (keepTogetherLists != null) {
1293                for (Collection<E> keepTogether : keepTogetherLists) {
1294                    for (E ee : keepTogether) {
1295                        forceIntoSameInternal(ee, members);
1296                    }
1297                }
1298            }
1299            for (SCCContributor contributor : contributors) {
1300                for (E member : contributor.sameBlockMembers(e, AbstractBiPGraph.this)) {
1301                    forceIntoSameInternal(member, members);
1302                }
1303            }
1304        }
1305
1306        @Override
1307        protected C createComponent() {
1308            return createComponentBlock();
1309        }
1310       
1311    }
1312
1313    public void reset() {
1314        for (E e : getEquations()) {
1315            e.reset();
1316        }
1317        for (V v : getVariables()) {
1318            v.reset();
1319        }
1320    }
1321
1322    public void lightReset() {
1323        for (E e : getEquations()) {
1324            e.lightReset();
1325        }
1326        for (V v : getVariables()) {
1327            v.lightReset();
1328        }
1329    }
1330
1331    public void tarjanReset() {
1332        for (E e : getEquations()) {
1333            e.tarjanReset();
1334        }
1335    }
1336
1337    public void insertIntoEquationIndexMap(FAbstractEquation eqn, E e) {
1338        equationIndexMap.add(eqn, e);
1339    }
1340
1341    public void removeFromEquationIndexMap(FAbstractEquation eqn, E e) {
1342        equationIndexMap.removeFirst(eqn, e);
1343    }
1344
1345    public String printMatching() {
1346        StringBuffer str = new StringBuffer();
1347        str.append("----------------------------------------\n");
1348        str.append("BiPGraph matching:\n");
1349        for (E e : getEquations()) {
1350            if (e.getMatching()!=null) {
1351                str.append(e);
1352                str.append(" : ");
1353                str.append(e.getMatching());
1354                str.append("\n");
1355            }
1356        }       
1357        str.append("Unmatched equations: {");
1358        for (E e : unmatchedEquationsIterable()) {
1359            str.append(e + " ");
1360        }
1361        str.append("}\n");
1362       
1363        str.append("Unmatched variables: {");
1364        for (V v : unmatchedVariablesIterable()) {
1365            str.append(v + " ");
1366        }
1367        str.append("}\n");
1368       
1369        str.append("----------------------------------------\n");
1370        return str.toString();
1371    }
1372
1373    public Object printMatchingObj() {
1374        return new Object() {
1375            @Override
1376            public String toString() {
1377                return printMatching();
1378            }
1379        };
1380    }
1381
1382    public String toString() {
1383        StringBuffer str = new StringBuffer();
1384        str.append("BiPGraph (" + getEquations().size() + " equations, " + variableMap.size() + " variables)\n");
1385        str.append("Variables: {");
1386        for (String vName : variableMap.keySet()) {
1387            V v = variableMap.get(vName);
1388            str.append(v);
1389            str.append(" ");
1390        }
1391        str.append("}\n");
1392        Map<FAbstractEquation, E> printedMap = new HashMap<FAbstractEquation, E>();
1393        for (E e : getEquations()) {
1394            str.append(e);
1395            str.append(" : ");
1396            for (V v : e.getVariables()) {
1397                str.append(v);
1398                str.append(canMatch(e, v) ? '@' : '#');
1399                if (v.getMatching() == e || e.getMatching() == v) {
1400                    str.append('M');
1401                }
1402                str.append(' ');
1403            }
1404            String previousPrintLabel = null;
1405            if (e.getGroupMembers().size() > 1) {
1406                E previous = printedMap.get(e.getEquation());
1407               
1408                if (previous == null) {
1409                    printedMap.put(e.getEquation(), e);
1410                } else {
1411                    previousPrintLabel = previous.getName();
1412                }
1413            }
1414            if (previousPrintLabel == null) {
1415                str.append("// " + e.printEquation() + "\n");
1416            } else {
1417                str.append("// Already printed, see " + previousPrintLabel + "\n");
1418            }
1419        }
1420        return str.toString();
1421    }
1422
1423    public class Edge {
1424        private V variable;
1425        private E equation;
1426
1427        public Edge(E e, V v) {
1428            this.equation = e;
1429            this.variable = v;
1430        }
1431
1432        public V getVariable() {
1433            return variable;
1434        }
1435
1436        public void setVariable(V variable) {
1437            this.variable = variable;
1438        }
1439
1440        public E getEquation() {
1441            return equation;
1442        }
1443
1444        public void setEquation(E equation) {
1445            this.equation = equation;
1446        }
1447
1448        public String toString() {
1449            return "(" + equation + "," + variable + ")";
1450        }
1451
1452    }
1453   
1454    public Map<V, Collection<E>> computeVariableToEquationMap() {
1455        Map<V, Collection<E>> map = new HashMap<V, Collection<E>>();
1456        for (E eqn : getEquations()) {
1457            for (V var : eqn.getVariables()) {
1458                Collection<E> eqns = map.get(var);
1459                if (eqns == null) {
1460                    eqns = new ArrayList<E>();
1461                    map.put(var, eqns);
1462                }
1463                eqns.add(eqn);
1464            }
1465        }
1466        return map;
1467    }
1468
1469    public int countNumberOfIncidences() {
1470        int count = 0;
1471        for (E e : getEquations()) {
1472            count += e.getVariables().size();
1473        }
1474        return count;
1475    }
1476}
1477
1478    public class DAEVarUseLookupVisitor extends FAccessExpLookupVisitor {
1479        public static final DAEVarUseLookupVisitor instance = new DAEVarUseLookupVisitor();
1480       
1481        @Override
1482        public void visit(ASTNode<? extends ASTNode> node, Set<FAccessExp> set) {
1483            node.findDAEVarUsesInTree(set, this);
1484        }
1485    }
1486
1487    public class InitDAEVarUseLookupVisitor extends FAccessExpLookupVisitor {
1488        public static final InitDAEVarUseLookupVisitor instance = new InitDAEVarUseLookupVisitor();
1489       
1490        @Override
1491        public void visit(ASTNode<? extends ASTNode> node, Set<FAccessExp> set) {
1492            node.findInitDAEVarUsesInTree(set, this);
1493        }
1494    }
1495   
1496    public class InitUniqueDAEVarUseLookupVisitor extends FAccessExpLookupVisitor {
1497        public static final InitUniqueDAEVarUseLookupVisitor instance = new InitUniqueDAEVarUseLookupVisitor();
1498       
1499        @Override
1500        public void visit(ASTNode<? extends ASTNode> node, Set<FAccessExp> set) {
1501            node.findInitUniqueDAEVarUsesInTree(set, this);
1502        }
1503    }
1504   
1505
1506    public void ASTNode.findDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1507        findCommonAccessExpsInTree(set, visitor);
1508    }
1509
1510    @Override
1511    public void FHomotopyExp.findDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1512        visitor.visit(getActual(), set);
1513    }
1514
1515    public void ASTNode.findInitDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1516        findCommonAccessExpsInTree(set, visitor);
1517    }
1518
1519    public Set<FAccessExp> ASTNode.findInitUniqueDAEVarUsesInTree() {
1520        return findCommonAccessExpsInTree(InitUniqueDAEVarUseLookupVisitor.instance);
1521    }
1522
1523    public void ASTNode.findInitUniqueDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1524        for (ASTNode n : this) {
1525            visitor.visit(n, set);
1526        }
1527    }
1528
1529    public void FHomotopyExp.findInitUniqueDAEVarUsesInTree(Set<FAccessExp> set, CommonAccessExpLookupVisitor<FAccessExp> visitor) {
1530        visitor.visit(getActual(), set);
1531        DefaultFAccessExpLookupVisitor.instance.visit(getSimplified(), set);
1532    }
1533   
1534
1535
1536/**
1537 * This class represent a component result from Tarjan's strongly connected
1538 * components algorithm.
1539 * It is basically a list of equations that depends on eachother and a list of
1540 * equations that they depend upon.
1541 */
1542public class SCCBlock<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> extends TarjanComponent<E> {
1543    private boolean containsHomotopy = false;
1544
1545    public void addMember(E member) {
1546        super.addMember(member);
1547        if (!containsHomotopy && member.getEquation().containsFHomotopyExp())
1548            containsHomotopy = true;
1549    }
1550   
1551    public boolean containsHomotopy() {
1552        return containsHomotopy;
1553    }
1554   
1555    public AbstractEquationBlock createEquationBlock(BlockProducer producer, StepUtil stepUtil, boolean isInitial) {
1556        return EquationBlockFactory.createEquationBlock(this, producer, stepUtil, isInitial);
1557    }
1558}
1559
1560public class BiPGraph extends AbstractBiPGraph<Eq, Var, SCCBlock<Eq, Var>> {
1561
1562    public BiPGraph() {
1563        super();
1564    }
1565
1566    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> BiPGraph(Collection<E> block, boolean isInitial) {
1567        super(block, isInitial);
1568    }
1569
1570    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> BiPGraph(Collection<E> eqns, Collection<V> vars) {
1571        super(eqns, vars);
1572    }
1573
1574    @Override
1575    protected Eq createEq(String name, FAbstractEquation eqn, int groupNumber, Collection<Eq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1576        return new Eq(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1577    }
1578
1579    @Override
1580    protected Var createVar(String name, FVariable var) {
1581        return new Var(name, var);
1582    }
1583   
1584    @Override
1585    protected SCCBlock<Eq, Var> createComponentBlock() {
1586        return new SCCBlock<Eq, Var>();
1587    }
1588}
1589
1590public class Eq extends AbstractEq<Eq, Var> {
1591
1592    public Eq(String name, FAbstractEquation eqn, int groupNumber, Collection<Eq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1593        super(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1594    }
1595
1596}
1597
1598public class Var extends AbstractVar<Eq, Var> {
1599
1600    public Var(String name, FVariable v) {
1601        super(name, v);
1602    }
1603
1604}
1605
1606
1607public class SolvingBiPGraph extends AbstractBiPGraph<SolvingEq, SolvingVar, SCCBlock<SolvingEq, SolvingVar>> {
1608
1609    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> SolvingBiPGraph(Collection<E> eqns, Collection<V> vars) {
1610        super(eqns, vars);
1611    }
1612
1613    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> SolvingBiPGraph(Collection<E> block, boolean isInitial) {
1614        super(block, isInitial);
1615    }
1616
1617    @Override
1618    public boolean canMatch(SolvingEq e, SolvingVar v) {
1619        return super.canMatch(e, v) && isSolved(e, v).isSolvable();
1620    }
1621
1622    public Solvability isSolved(SolvingEq e, SolvingVar v) {
1623        return e.getEquation().isSolved(v.getVariable(), true);
1624    }
1625
1626    @Override
1627    public void addInsidence(SolvingEq e, SolvingVar v) {
1628        super.addInsidence(e, v);
1629        v.occurrence();
1630        if (e.isReal() != v.isReal())
1631            return;
1632        e.sameTypeOccurrence();
1633        v.sameTypeOccurrence();
1634        Solvability solvability = isSolved(e, v);
1635        switch (solvability) {
1636        case ANALYTICALLY_SOLVABLE:
1637            e.addAnalyticallySolvableVariable(v);
1638            v.analyticallySolvableOccurrence();
1639            break;
1640        case NUMERICALLY_SOLVABLE:
1641            e.addNumericallySolvableVariable(v);
1642            v.numericallySolvableOccurrence();
1643            break;
1644        }
1645    }
1646
1647    @Override
1648    protected SolvingEq createEq(String name, FAbstractEquation eqn, int groupNumber, Collection<SolvingEq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1649        return new SolvingEq(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1650    }
1651
1652    @Override
1653    protected SolvingVar createVar(String name, FVariable var) {
1654        return new SolvingVar(name, var);
1655    }
1656
1657    @Override
1658    public void removeVariable(SolvingVar v) {
1659        for (SolvingEq e : getEquations())
1660            e.getSolvableVariables().remove(v);
1661        super.removeVariable(v);
1662    }
1663
1664    @Override
1665    protected SCCBlock<SolvingEq, SolvingVar> createComponentBlock() {
1666        return new SCCBlock<SolvingEq, SolvingVar>();
1667    }
1668}
1669
1670public class SolvingEq extends AbstractEq<SolvingEq, SolvingVar> implements Comparable<SolvingEq> {
1671
1672    private java.util.List<SolvingVar> solvableVariables = new ArrayList<SolvingVar>();
1673    private int analyticallySolvableOccurrences = 0;
1674    private int numericallySolvableOccurrences = 0;
1675    private int sameTypeOccurrences = 0;
1676    private boolean isRes = false;
1677
1678    public SolvingEq(String name, FAbstractEquation eqn, int groupNumber, Collection<SolvingEq> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1679        super(name, eqn, groupNumber, groupMembers, variability, type, isMeta);
1680    }
1681
1682    public void sameTypeOccurrence(){
1683        sameTypeOccurrences++;
1684    }
1685
1686    public int getNbrSameTypeOccurrences(){
1687        return sameTypeOccurrences;
1688    }
1689
1690    public void addAnalyticallySolvableVariable(SolvingVar v) {
1691        solvableVariables.add(v);
1692        analyticallySolvableOccurrences++;
1693    }
1694
1695    public void addNumericallySolvableVariable(SolvingVar v) {
1696        solvableVariables.add(v);
1697        numericallySolvableOccurrences++;
1698    }
1699
1700    public java.util.List<SolvingVar> getSolvableVariables() {
1701        return solvableVariables;
1702    }
1703
1704    public void isRes(boolean bol){
1705        isRes = bol;
1706    }
1707
1708    public boolean isRes(){
1709        return isRes;
1710    }
1711
1712    public boolean tarjanVisit() {
1713        return !isRes();
1714    }
1715
1716    /**
1717     * Returns integer greater than zero if this equation suites better as residual
1718     * equation than the <code>other</code> equation. Zero is returned if they are equal
1719     * and less than zero is returned if the <code>other</code> variable is better.
1720     */
1721    @Override
1722    public int compareTo(SolvingEq other) {
1723        int diff = (isReal() ? 1 : 0) - (other.isReal() ? 1 : 0);
1724        if (diff != 0)
1725            return diff;
1726        diff = getNbrSameTypeOccurrences() - other.getNbrSameTypeOccurrences();
1727        if (diff != 0)
1728            return diff;
1729        diff = numericallySolvableOccurrences - other.numericallySolvableOccurrences;
1730        if (diff != 0)
1731            return diff;
1732        diff = other.analyticallySolvableOccurrences - analyticallySolvableOccurrences;
1733        if (diff != 0)
1734            return diff;
1735        return 0;
1736    }
1737
1738}
1739
1740public class SolvingVar extends AbstractVar<SolvingEq, SolvingVar> implements Comparable<SolvingVar> {
1741
1742    private int occurrences = 0;
1743    private int sameTypeOccurrences = 0;
1744    private int analyticallySolvableOccurrences = 0;
1745    private int numericallySolvableOccurrences = 0;
1746    private boolean isIter = false;
1747
1748    public SolvingVar(String name, FVariable v) {
1749        super(name, v);
1750    }
1751
1752    public void occurrence(){
1753        occurrences++;
1754    }
1755
1756    public void sameTypeOccurrence(){
1757        sameTypeOccurrences++;
1758    }
1759
1760    public void analyticallySolvableOccurrence(){
1761        analyticallySolvableOccurrences++;
1762    }
1763
1764    public void numericallySolvableOccurrence(){
1765        numericallySolvableOccurrences++;
1766    }
1767
1768    public int getNbrOccurrences(){
1769        return occurrences;
1770    }
1771
1772    public int getNbrSameTypeOccurrences(){
1773        return sameTypeOccurrences;
1774    }
1775
1776    public int getNbrAnalyticallySolvableOccurrences(){
1777        return analyticallySolvableOccurrences;
1778    }
1779
1780    public int getNbrNumericallySolvableOccurrences(){
1781        return numericallySolvableOccurrences;
1782    }
1783
1784    public void isIter(boolean bol){
1785        isIter = bol;
1786    }
1787
1788    public boolean isIter(){
1789        return isIter;
1790    }
1791
1792    public boolean tarjanVisit() {
1793        return !isIter();
1794    }
1795
1796    /**
1797     * Returns integer greather than zero if this variable sutes better as iteration
1798     * variable than the <code>other</code> variable. Zero is returned if they are equal
1799     * and <0 is returned if the <code>other</code> variable is better.
1800     */
1801    @Override
1802    public int compareTo(SolvingVar other) {
1803        int diff = (isReal() ? 1 : 0) - (other.isReal() ? 1 : 0);
1804        if (diff != 0)
1805            return diff;
1806        diff = (other.getVariable().isTemporary() ? 1 : 0) - (getVariable().isTemporary() ? 1 : 0);
1807        if (diff != 0)
1808            return diff;
1809        diff = getNbrSameTypeOccurrences() - other.getNbrSameTypeOccurrences();
1810        if (diff != 0)
1811            return diff;
1812        diff = getNbrNumericallySolvableOccurrences() - other.getNbrNumericallySolvableOccurrences();
1813        if (diff != 0)
1814            return diff;
1815        diff = other.getNbrAnalyticallySolvableOccurrences() - getNbrAnalyticallySolvableOccurrences();
1816        if (diff != 0)
1817            return diff;
1818        diff = (getVariable().attributeSet(FAttribute.START) ? 1 : 0) - (other.getVariable().attributeSet(FAttribute.START) ? 1 : 0);
1819        if (diff != 0)
1820            return diff;
1821        diff = other.getVariable().getFAccess().numDots() - getVariable().getFAccess().numDots();
1822        if (diff != 0)
1823            return diff;
1824        return 0;
1825    }
1826}
1827
1828
1829public abstract class AbstractEq<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> {
1830
1831    private final String name;
1832    private final FAbstractEquation eqn;
1833    private final int groupNumber;
1834    private final TypePrefixVariability variability;
1835    private final FType type;
1836    private final boolean isMeta;
1837    private java.util.List<V> variables = new ArrayList<V>();
1838    private V matching = null;
1839    private boolean visited = false;
1840    private int layer = 1000000;
1841    private int tarjanNbr = 0;
1842    private int tarjanLowLink = 0;
1843    private int depth = 1;
1844    /** In some cases, equations needs to be treated as a group, e.g., in the
1845     * case when several equations are generated from a function call equation.
1846     * In this case, all the "scalar" equations generated for the function call
1847     * equation are members of each such equation. Note that every equation is
1848     * member of its own group: scalar equations therefor has one member:
1849     * itself. This approach makes handling of equation groups more consistent,
1850     * e.g., when a function call equation needs to be differentiated.
1851     */
1852    private final Collection<E> groupMembers;
1853
1854    public AbstractEq(String name, FAbstractEquation eqn, int groupNumber, Collection<E> groupMembers, TypePrefixVariability variability, FType type, boolean isMeta) {
1855        this.name = name;
1856        this.eqn = eqn;
1857        this.groupNumber = groupNumber;
1858        this.groupMembers = Collections.unmodifiableCollection(groupMembers);
1859        this.variability = variability;
1860        this.type = type;
1861        this.isMeta = isMeta;
1862    }
1863
1864    public boolean isMeta() {
1865        return isMeta;
1866    }
1867
1868    public void addVariable(V v) {
1869        variables.add(v);
1870    }
1871
1872    public void reset() {
1873        setMatching(null);
1874        setVisited(false);
1875        setLayer(1000000);
1876    }
1877
1878    public void lightReset() {
1879        setVisited(false);
1880        setLayer(1000000);
1881    }
1882
1883    public void tarjanReset() {
1884        setTarjanLowLink(0);
1885        setTarjanNbr(0);
1886        setVisited(false);
1887    }
1888
1889    public String getName() {
1890        return name;
1891    }
1892
1893    public FAbstractEquation getEquation() {
1894        return eqn;
1895    }
1896
1897    public int groupNumber() {
1898        return groupNumber;
1899    }
1900
1901    public java.util.List<V> getVariables() {
1902        return variables;
1903    }
1904
1905    public V getMatching() {
1906        return matching;
1907    }
1908
1909    public void setMatching(V matching) {
1910        this.matching = matching;
1911    }
1912
1913    public boolean isVisited() {
1914        return visited;
1915    }
1916
1917    public void setVisited(boolean visited) {
1918        this.visited = visited;
1919    }
1920
1921    public boolean tarjanVisit() {
1922        return true;
1923    }
1924
1925    public int getLayer() {
1926        return layer;
1927    }
1928
1929    public void setLayer(int layer) {
1930        this.layer = layer;
1931    }
1932
1933    public int getTarjanNbr() {
1934        return tarjanNbr;
1935    }
1936
1937    public void setTarjanNbr(int tarjanNbr) {
1938        this.tarjanNbr = tarjanNbr;
1939    }
1940
1941    public int getTarjanLowLink() {
1942        return tarjanLowLink;
1943    }
1944
1945    public void setTarjanLowLink(int tarjanLowLink) {
1946        this.tarjanLowLink = tarjanLowLink;
1947    }
1948
1949    public String toString() {
1950        return getName();
1951    }
1952
1953    public String printEquation() {
1954        return getEquation().toString();
1955    }
1956
1957    public boolean isReal() {
1958        return type.isReal();
1959    }
1960
1961    public FType type() {
1962        return type;
1963    }
1964
1965    public int getDepth(){
1966        return this.depth;
1967    }
1968
1969    public void setDepth(int d){
1970        this.depth = d;
1971    }
1972
1973    public Collection<E> getGroupMembers() {
1974        return groupMembers;
1975    }
1976
1977    public V getVariable(String name) {
1978        for (V var : variables) {
1979            if (var.getName().equals(name)) {
1980                return var;
1981            }
1982        }
1983        return null;
1984    }
1985
1986    public TypePrefixVariability variability() {
1987        return variability;
1988    }
1989
1990    @Override
1991    public boolean equals(Object o) {
1992        if (!(o instanceof AbstractEq))
1993            return false;
1994        AbstractEq other = (AbstractEq)o;
1995        return getName().equals(other.getName());
1996    }
1997
1998    @Override
1999    public int hashCode() {
2000        return getName().hashCode();
2001    }
2002   
2003    public void removeIncidencesNotInSet(Set<V> vars) {
2004        Iterator<V> it = variables.iterator();
2005        while (it.hasNext()) {
2006            V var = it.next();
2007            if (!vars.contains(var))
2008                it.remove();
2009        }
2010    }
2011
2012}
2013
2014public abstract class AbstractVar<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> {
2015
2016    private final String name;
2017    private final FVariable v;
2018    private E matching = null;
2019    private boolean visited = false;
2020    private int layer = 1000000;
2021
2022    public AbstractVar(String name, FVariable v) {
2023        this.name = name;
2024        this.v = v;
2025    }
2026
2027    public void reset() {
2028        setMatching(null);
2029        setVisited(false);
2030        setLayer(1000000);
2031    }
2032
2033    public void lightReset() {
2034        setVisited(false);
2035        setLayer(1000000);
2036    }
2037
2038    public String getName() {
2039        return name;
2040    }
2041
2042    public FVariable getVariable() {
2043        return v;
2044    }
2045
2046    public E getMatching() {
2047        return matching;
2048    }
2049
2050    public void setMatching(E matching) {
2051        this.matching = matching;
2052    }
2053
2054    public boolean isVisited() {
2055        return visited;
2056    }
2057
2058    public void setVisited(boolean visited) {
2059        this.visited = visited;
2060    }
2061
2062    public boolean tarjanVisit() {
2063        return true;
2064    }
2065
2066    public int getLayer() {
2067        return layer;
2068    }
2069
2070    public void setLayer(int layer) {
2071        this.layer = layer;
2072    }
2073
2074    public String toString() {
2075        return v.displayName();
2076    }
2077
2078    public boolean isReal() {
2079        return type().isReal();
2080    }
2081
2082    public FType type() {
2083        return getVariable().type();
2084    }
2085
2086    @Override
2087    public boolean equals(Object o) {
2088        if (!(o instanceof AbstractVar))
2089            return false;
2090        AbstractVar other = (AbstractVar)o;
2091        return getName().equals(other.getName());
2092    }
2093
2094    @Override
2095    public int hashCode() {
2096        return getName().hashCode();
2097    }
2098}
2099
2100public class AbstractBiPGraph {
2101    protected static interface VariableResolver<E extends AbstractEq<E, V>, V extends AbstractVar<E, V>> {
2102        public Set<V> lookupVars(Iterable<FAccessExp> set);
2103    }
2104}
2105
2106public VariableResolver<E, V> AbstractBiPGraph.defaultVariableResolver() {
2107    return new VariableResolver<E,V>() {
2108        public Set<V> lookupVars(Iterable<FAccessExp> set) {
2109            return AbstractBiPGraph.this.lookupVars(set);
2110        }
2111    };
2112}
2113
2114public Set<V> AbstractBiPGraph.lookupVars(Iterable<FAccessExp> set) {
2115    Set<V> res = new LinkedHashSet<V>();
2116    for (FAccessExp use : set) {
2117        V var = getVariable(use.name());
2118        if (var != null)
2119            res.add(var);
2120    }
2121    return res;
2122}
2123
2124    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2125    AbstractBiPGraph<E, V, C>.IncidenceMap
2126    FAbstractEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes) {
2127        return createIncidenceMap(g, variableTypes, g.defaultVariableResolver());
2128    }
2129   
2130    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2131    AbstractBiPGraph<E, V, C>.IncidenceMap
2132    FAbstractEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2133            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2134        return g.new IncidenceMap(this, resolver);
2135    }
2136
2137    @Override
2138    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2139    AbstractBiPGraph<E, V ,C>.IncidenceMap
2140    FAlgorithm.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2141            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2142        return g.new ManyIncidenceMap(this, resolver, variableTypes);
2143    }
2144
2145    @Override
2146    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>>
2147    AbstractBiPGraph<E, V, C>.IncidenceMap
2148    FIfEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2149            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2150        return g.new ManyIncidenceMap(this, resolver, variableTypes);
2151    }
2152
2153    @Override
2154    public <E extends AbstractEq<E, V>, V extends AbstractVar<E, V>, C extends SCCBlock<E, V>> 
2155    AbstractBiPGraph<E, V, C>.IncidenceMap
2156    FFunctionCallEquation.createIncidenceMap(AbstractBiPGraph<E, V, C> g, EnumSet<AbstractBiPGraph.VarType> variableTypes,
2157            AbstractBiPGraph.VariableResolver<E, V> resolver) {
2158        if (myOptions().getStringOption("function_incidence_computation").equals("all")) {
2159            try {
2160                AbstractBiPGraph<E, V, C>.SplitIncidenceMap splitIncidenceMap = g.new SplitIncidenceMap(this, resolver, variableTypes);
2161                splitIncidenceMap.lhs(); // trigger cache calculations
2162                return splitIncidenceMap;
2163            } catch (ConstantEvaluationException e) {
2164               
2165            }
2166        }
2167        return g.new ManyIncidenceMap(this, resolver, variableTypes);
2168    }
2169   
2170
2171}
2172
2173aspect AugmentingPath {
2174   
2175    public abstract class AbstractBiPGraph {
2176        private final Enumerator visitEnumerator = new Enumerator(1);
2177        public abstract class AugmentingPathAlgorithm<R> {
2178            private final R TRUE_VALUE;
2179
2180            protected AugmentingPathAlgorithm(R TRUE_VALUE) {
2181                this.TRUE_VALUE = TRUE_VALUE;
2182            }
2183
2184            public R augmentingPath(E e) {
2185                return augmentingPath(e, Collections.<V>emptyList());
2186            }
2187
2188            public R augmentingPath(E e, Collection<V> preVisit) {
2189                int visitNum = visitEnumerator.next();
2190                for (V var : preVisit)
2191                    var.augmentingPathVisit(visitNum);
2192                return visitEqn(e, visitNum);
2193            }
2194           
2195            private final R visitEqn(E eqn, int num) {
2196                R res = startValue(eqn);
2197                if (!eqn.augmentingPathVisit(num))
2198                    return res;
2199                for (V var : visitVariables(eqn)) {
2200                    if (!shouldVisit(eqn, var))
2201                        continue;
2202                    if (var.getMatching() == null) {
2203                        match(eqn, var);
2204                        return TRUE_VALUE;
2205                    } else if (var.augmentingPathVisit(num)) {
2206                        R subRes = visitEqn(var.getMatching(), num);
2207                        if (subRes == TRUE_VALUE) {
2208                            match(eqn, var);
2209                            return TRUE_VALUE;
2210                        }
2211                        res = mergeSubRes(res, subRes, eqn);
2212                    }
2213                }
2214                return res;
2215            }
2216
2217            protected void match(E eqn, V var) {
2218                AbstractBiPGraph.this.match(eqn, var);
2219            }
2220
2221            protected abstract R startValue(E eqn);
2222
2223            protected abstract R mergeSubRes(R res, R subRes, E eqn);
2224
2225            protected boolean shouldVisit(E eqn, V var) {
2226                return canMatch(eqn, var);
2227            }
2228
2229            protected Iterable<V> visitVariables(E eqn) {
2230                return eqn.getVariables();
2231            }
2232
2233            public R trueValue() {
2234                return TRUE_VALUE;
2235            }
2236        }
2237
2238        private final StandardAugmentingPath STANDARD_AUGMENTING_PATH = new StandardAugmentingPath();
2239
2240        public class StandardAugmentingPath extends AugmentingPathAlgorithm<Boolean> {
2241            public StandardAugmentingPath() {
2242                super(true);
2243            }
2244
2245            @Override
2246            protected Boolean startValue(E eqn) {
2247                return false;
2248            }
2249
2250            @Override
2251            protected Boolean mergeSubRes(Boolean res, Boolean subRes, E eqn) {
2252                return false;
2253            }
2254        }
2255    }
2256   
2257    private int AbstractEq.augmentingPathVisitNumber = 0;
2258    public boolean AbstractEq.augmentingPathVisit(int num) {
2259        boolean res = num > augmentingPathVisitNumber;
2260        augmentingPathVisitNumber = num;
2261        return res;
2262    }
2263   
2264    private int AbstractVar.augmentingPathVisitNumber = 0;
2265    public boolean AbstractVar.augmentingPathVisit(int num) {
2266        boolean res = num > augmentingPathVisitNumber;
2267        augmentingPathVisitNumber = num;
2268        return res;
2269    }
2270   
2271    public boolean AbstractBiPGraph.augmentPath(E e) {
2272        e.setVisited(true);
2273        for (V v : e.getVariables()) {
2274            if (!canMatch(e, v))
2275                continue;
2276            if (v.getMatching()==null) {
2277                match(e, v);
2278                return true;
2279            } else if (!v.isVisited()) {
2280                v.setVisited(true);
2281                if (augmentPath(v.getMatching())) {
2282                    match(e, v);
2283                    return true;
2284                }
2285            }
2286        }
2287        return false;
2288    }
2289
2290}
Note: See TracBrowser for help on using the repository browser.