Merge branch 'master' of https://bitbucket.org/czan/honours

Conflicts:
	.gitignore
	impl/MaxStrategy.hpp
	impl/VariableAssignment.hpp
	impl/systems/test.eqns
	impl/test/7.eqns

2 files changed, 134 insertions, 42 deletions

diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
index 57dcdeb..f4026dd 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
@@ -10,6 +10,9 @@ template<typename Domain>
 struct MaxStrategy {
   virtual ~MaxStrategy() { }
   virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
+  virtual unsigned int get(const MaxExpression<Domain>& e) {
+    return const_cast<const MaxStrategy*>(this)->get(e);
+  }
 };
 
 unsigned int stack_depth = 1;
@@ -38,20 +41,38 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
       _influence(system.maxExpressionCount(),
                  IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
       _var_influence(system.variableCount(),
-                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
+                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
+      _frozen(false)
   {}
 
+  void freeze() {
+    _frozen = true;
+  }
+
+  void thaw() {
+    _frozen = false;
+  }
+
+  bool is_frozen() {
+    return _frozen;
+  }
+
   void setRho(DynamicVariableAssignment<Domain>& rho) {
     _rho = &rho;
   }
 
   unsigned int get(const MaxExpression<Domain>& e) const {
-    solve(e);
     return _values[e];
   }
 
-  void invalidate(const Variable<Domain>& v) const {
-    solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
+  unsigned int get(const MaxExpression<Domain>& e) {
+    if (!_frozen)
+      solve(e);
+    return _values[e];
+  }
+
+  void invalidate(const Variable<Domain>& v) {
+    log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; 
     _stable.filter(_var_influence[v]);
 
     IdSet<MaxExpression<Domain> > infl = _var_influence[v];
@@ -67,10 +88,10 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
   }
 
 private:
-  void solve(const MaxExpression<Domain>& x) const {
+  void solve(const MaxExpression<Domain>& x) {
     if (!_stable.contains(x)) {
       _stable.insert(x);
-      solver_log::strategy << indent() << "Stabilise " << x << std::endl;
+      log::strategy << indent() << "Stabilise " << x << std::endl;
 
       stack_depth++;
       unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
@@ -78,7 +99,7 @@ private:
       stack_depth--;
 
       if (val != _values[x]) {
-        solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl;
+        log::strategy << x << " => " << *x.arguments()[val] << std::endl;
 
         IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
         _influence[x].clear();
@@ -96,15 +117,17 @@ private:
           solve(_system.maxExpression(*it));
         }
       } else {
-        solver_log::strategy << indent() << x << " did not change" << std::endl;
+        log::strategy << indent() << x << " did not change: "
+		      << x << " => " << *x.arguments()[val] << std::endl;
       }
     } else {
-      solver_log::strategy << indent() << x << " is stable" << std::endl;
+      log::strategy << indent() << x << " is stable: "
+		    << x << " => " << *x.arguments()[_values[x]] << std::endl;
     }
   }
 
   struct DependencyAssignment : public VariableAssignment<Domain>{
-    DependencyAssignment(const DynamicMaxStrategy& strat,
+    DependencyAssignment(DynamicMaxStrategy& strat,
                          VariableAssignment<Domain>& rho,
                          const MaxExpression<Domain>& expr)
       : _strat(strat),
@@ -116,13 +139,13 @@ private:
       return _rho[var];
     }
   private:
-    const DynamicMaxStrategy& _strat;
+    DynamicMaxStrategy& _strat;
     VariableAssignment<Domain>& _rho;
     const MaxExpression<Domain>& _expr;
   };
 
   struct DependencyStrategy : public MaxStrategy<Domain> {
-    DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+    DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
       : _strat(strat),
         _expr(expr) {
     }
@@ -134,19 +157,57 @@ private:
       return _strat._values[e];
     }
   private:
-    const DynamicMaxStrategy& _strat;
+    DynamicMaxStrategy& _strat;
     const MaxExpression<Domain>& _expr;
   };
 
-private:
+private: 
   const EquationSystem<Domain>& _system;
-  mutable DynamicVariableAssignment<Domain>* _rho;
-  mutable IdMap<MaxExpression<Domain>,unsigned int> _values;
-  mutable IdSet<MaxExpression<Domain> > _stable;
-  mutable IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
-  mutable IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
+  DynamicVariableAssignment<Domain>* _rho;
+  IdMap<MaxExpression<Domain>,unsigned int> _values;
+  IdSet<MaxExpression<Domain> > _stable;
+  IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
+  IdMap<Variable<Domain>,IdSet<MaxExpression<Domain> > > _var_influence;
+  bool _frozen;
 };
 
+
+template<typename T>
+IdMap<Variable<T>,T> solve_for(const EquationSystem<T>& system) {
+  IdMap<Variable<T>,T> result(system.variableCount(), infinity<T>());
+
+  DynamicMaxStrategy<T> strategy(system);
+  DynamicVariableAssignment<T> rho(system, strategy, -infinity<T>());
+  strategy.setRho(rho);
+
+  bool changed;
+  do {
+    changed = false;
+
+    // improve strategy
+    rho.freeze();
+    strategy.thaw();
+    for (unsigned int i = 0; i < system.variableCount(); ++i) {
+      strategy.get(*system[system.variable(i)]);
+    }
+
+    // iterate fixpoint
+    strategy.freeze();
+    rho.thaw();
+    for (unsigned int i = 0; i < system.variableCount(); ++i) {
+      Variable<T>& var = system.variable(i);
+      T val = rho[var];
+      if (result[var] != val) {
+	result[var] = val;
+	changed = true;
+      }
+    }
+  } while(changed);
+
+  return result;
+}
+
+
 /*template<typename Domain>
 std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) {
   strat.print(cout);
diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
index ba5f650..2a63756 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/VariableAssignment.hpp
@@ -8,6 +8,9 @@ template<typename Domain>
 struct VariableAssignment {
   virtual ~VariableAssignment() { }
   virtual const Domain& operator[](const Variable<Domain>&) const = 0;
+  virtual const Domain& operator[](const Variable<Domain>& x) {
+    return (*const_cast<const VariableAssignment*>(this))[x];
+  }
 };
 
 #include "EquationSystem.hpp"
@@ -19,46 +22,71 @@ template<typename Domain>
 struct DynamicVariableAssignment : public VariableAssignment<Domain> {
   DynamicVariableAssignment(
     const EquationSystem<Domain>& system,
-    const DynamicMaxStrategy<Domain>& strat
+    DynamicMaxStrategy<Domain>& strat,
+    const Domain& value=infinity<Domain>()
   ) : _system(system),
       _strategy(strat),
-      _values(system.variableCount(), infinity<Domain>()),
+      _values(system.variableCount(), value),
       _stable(system.variableCount()),
       _influence(system.variableCount(),
-                 IdSet<Variable<Domain> >(system.variableCount()))
+                 IdSet<Variable<Domain> >(system.variableCount())),
+      _frozen(false)
   { }
 
+  void freeze() {
+    _frozen = true;
+  }
+
+  void thaw() {
+    _frozen = false;
+  }
+
+  bool is_frozen() {
+    return _frozen;
+  }
+
   const Domain& operator[](const Variable<Domain>& var) const {
-    solve(var);
     return _values[var];
   }
 
-  void invalidate(const Variable<Domain>& x) const {
-    solver_log::fixpoint << indent() << "Invalidating " << x << std::endl;
+  const Domain& operator[](const Variable<Domain>& var) {
+    if (!_frozen)
+      solve(var);
+    return _values[var];
+  }
+
+  void invalidate(const Variable<Domain>& x) {
+    log::fixpoint << indent() << "Invalidating " << x << std::endl;
     if (_stable.contains(x)) {
       _stable.remove(x);
       _values[x] = infinity<Domain>();
-      
-      solve(x);
+     
+      IdSet<Variable<Domain> > infl = _influence[x];
+      _influence[x].clear();
+      for (typename IdSet<Variable<Domain> >::iterator
+	     it = infl.begin(),
+	     ei = infl.end();
+	   it != ei;
+	   ++it) {
+	invalidate(_system.variable(*it));
+      }
     }
   }
 
 private:
 
-  void solve(const Variable<Domain>& x) const {
+  void solve(const Variable<Domain>& x) {
     if (!_stable.contains(x)) {
       _stable.insert(x);
-      solver_log::fixpoint << indent() << "Stabilise " << x << std::endl;
+      log::fixpoint << indent() << "Stabilise " << x << std::endl;
 
       stack_depth++;
-      if (!_system[x])
-        return;
-      Domain val = _system[x]->evalWithStrat(DependencyAssignment(*this, x),
-					     _strategy);
+      Domain val = _system[x]->eval(DependencyAssignment(*this, x),
+                                    _strategy);
       stack_depth--;
 
       if (val != _values[x]) {
-        solver_log::fixpoint << x << " = " << val << std::endl;
+        log::fixpoint << x << " = " << val << std::endl;
 
         IdSet<Variable<Domain> > oldInfluence = _influence[x];
         _influence[x].clear();
@@ -74,15 +102,17 @@ private:
           solve(_system.variable(*it));
         }
       } else {
-        solver_log::fixpoint << indent() << x << " did not change" << std::endl;
+        log::fixpoint << indent() << x << " did not change: "
+		      << x << " = " << val << std::endl;
       }
     } else {
-      solver_log::fixpoint << indent() << x << " is stable" << std::endl;
+      log::fixpoint << indent() << x << " is stable: "
+		    << x << " = " << _values[x] << std::endl;
     }
   }
 
   struct DependencyAssignment : public VariableAssignment<Domain> {
-    DependencyAssignment(const DynamicVariableAssignment& assignment, const Variable<Domain>& var)
+    DependencyAssignment(DynamicVariableAssignment& assignment, const Variable<Domain>& var)
       : _assignment(assignment), _var(var) { }
     const Domain& operator[](const Variable<Domain>& x) const {
       const Domain& result = _assignment[x];
@@ -90,15 +120,16 @@ private:
       return result;
     }
   private:
-    const DynamicVariableAssignment& _assignment;
+    DynamicVariableAssignment& _assignment;
     const Variable<Domain>& _var;
   };
 
   const EquationSystem<Domain>& _system;
-  const DynamicMaxStrategy<Domain>& _strategy;
-  mutable IdMap<Variable<Domain>, Domain> _values;
-  mutable IdSet<Variable<Domain> > _stable;
-  mutable IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+  DynamicMaxStrategy<Domain>& _strategy;
+  IdMap<Variable<Domain>, Domain> _values;
+  IdSet<Variable<Domain> > _stable;
+  IdMap<Variable<Domain>,IdSet<Variable<Domain> > > _influence;
+  bool _frozen;
 };
 
 #endif