1 files changed, 115 insertions, 31 deletions

diff --git a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
index 57dcdeb..9ae7394 100644
--- a/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
+++ b/clang/include/clang/Analysis/Analyses/IntervalSolver/MaxStrategy.hpp
@@ -9,6 +9,9 @@
 template<typename Domain>
 struct MaxStrategy {
   virtual ~MaxStrategy() { }
+  virtual unsigned int get(const MaxExpression<Domain>& e) {
+    return const_cast<const MaxStrategy<Domain>*>(this)->get(e);
+  }
   virtual unsigned int get(const MaxExpression<Domain>& e) const = 0;
 };
 
@@ -37,54 +40,85 @@ struct DynamicMaxStrategy : public MaxStrategy<Domain> {
       _stable(system.maxExpressionCount()),
       _influence(system.maxExpressionCount(),
                  IdSet<MaxExpression<Domain> >(system.maxExpressionCount())),
-      _var_influence(system.variableCount(),
-                     IdSet<MaxExpression<Domain> >(system.maxExpressionCount()))
+      _changed(false)
   {}
 
   void setRho(DynamicVariableAssignment<Domain>& rho) {
     _rho = &rho;
   }
 
+  void hasChanged(bool c) {
+    _changed = c;
+  }
+
+  bool hasChanged() const {
+    return _changed;
+  }
+
   unsigned int get(const MaxExpression<Domain>& e) const {
-    solve(e);
+    solver_log::strategy << indent() << "Look up " << e << std::endl;
     return _values[e];
   }
 
-  void invalidate(const Variable<Domain>& v) const {
-    solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl;
-    _stable.filter(_var_influence[v]);
+  unsigned int get(const MaxExpression<Domain>& e) {
+    solver_log::strategy << indent() << "Solve for " << e << std::endl;
+    solve(e);
+    return _values[e];
+  }
 
-    IdSet<MaxExpression<Domain> > infl = _var_influence[v];
-    _var_influence[v].clear();
+  void invalidate(const Variable<Domain>& v) {
+    solver_log::strategy << indent() << "Invalidating " << v << " - " << *_system[v] << std::endl; 
 
+    IdSet<MaxExpression<Domain> > infl = _influence[*_system[v]];
     for (typename IdSet<MaxExpression<Domain> >::iterator
            it = infl.begin(),
            end = infl.end();
          it != end;
          ++it) {
-      solve(_system.maxExpression(*it));
+      invalidate(_system.maxExpression(*it));
+    }
+  }
+
+  void invalidate(const MaxExpression<Domain>& v) {
+    if (_stable.contains(v)) {
+      solver_log::strategy << indent() << "Invalidating " << v << std::endl; 
+      //solver_log::debug << indent() << "  influence sets " << _influence << std::endl;
+      _stable.remove(v);
+      
+      IdSet<MaxExpression<Domain> > infl = _influence[v];
+      for (typename IdSet<MaxExpression<Domain> >::iterator
+             it = infl.begin(),
+             end = infl.end();
+           it != end;
+           ++it) {
+        invalidate(_system.maxExpression(*it));
+      }
     }
   }
 
 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;
 
-      stack_depth++;
-      unsigned int val = x.bestStrategy(DependencyAssignment(*this, *_rho, x),
-                                        DependencyStrategy(*this, x));
+      stack_depth++; 
+      DependencyAssignment assignment(*this, *_rho, x);
+      DependencyStrategy depStrat(*this, x);
+      unsigned int val = x.bestStrategy(assignment, depStrat, _values[x]);
       stack_depth--;
 
       if (val != _values[x]) {
         solver_log::strategy << x << " => " << *x.arguments()[val] << std::endl;
 
         IdSet<MaxExpression<Domain> > oldInfluence = _influence[x];
-        _influence[x].clear();
+        //_influence[x].clear();
         _values[x] = val;
+        _changed = true;
 
         _rho->invalidate(*_system.varFromExpr(x));
+        
+	//_rho->stabilise();
 
         _stable.filter(oldInfluence);
 
@@ -96,57 +130,107 @@ private:
           solve(_system.maxExpression(*it));
         }
       } else {
-        solver_log::strategy << indent() << x << " did not change" << std::endl;
+        solver_log::strategy << indent() << x << " did not change: "
+		      << x << " => " << *x.arguments()[val] << std::endl;
       }
     } else {
-      solver_log::strategy << indent() << x << " is stable" << std::endl;
+      solver_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),
         _rho(rho),
-        _expr(expr) {
+        _expr(expr),
+	_current(strat._system.variableCount()) {
     }
-    const Domain& operator[](const Variable<Domain>& var) const {
-      _strat._var_influence[var].insert(_expr);
+    const Domain operator[](const Variable<Domain>& var) {
+      // solve the strategy for this variable, too
+      _strat.solve(*_strat._system[var]);
+      _strat._influence[*_strat._system[var]].insert(_expr);
       return _rho[var];
     }
   private:
-    const DynamicMaxStrategy& _strat;
+    DynamicMaxStrategy& _strat;
     VariableAssignment<Domain>& _rho;
     const MaxExpression<Domain>& _expr;
+    IdSet<Variable<Domain> > _current;
   };
 
   struct DependencyStrategy : public MaxStrategy<Domain> {
-    DependencyStrategy(const DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
+    DependencyStrategy(DynamicMaxStrategy& strat, const MaxExpression<Domain>& expr)
       : _strat(strat),
         _expr(expr) {
     }
     unsigned int get(const MaxExpression<Domain>& e) const {
+      _strat._influence[e].insert(_expr);
+      return _strat._values[e];
+    }
+    unsigned int get(const MaxExpression<Domain>& e) {
       _strat.solve(e);
-      if (&_expr != &e) {
-        _strat._influence[e].insert(_expr);
-      }
+      _strat._influence[e].insert(_expr);
       return _strat._values[e];
     }
   private:
-    const DynamicMaxStrategy& _strat;
+    DynamicMaxStrategy& _strat;
     const MaxExpression<Domain>& _expr;
   };
 
+private: 
+  const EquationSystem<Domain>& _system;
+  DynamicVariableAssignment<Domain>* _rho;
+  IdMap<MaxExpression<Domain>,unsigned int> _values;
+  IdSet<MaxExpression<Domain> > _stable;
+  IdMap<MaxExpression<Domain>,IdSet<MaxExpression<Domain> > > _influence;
+  bool _changed;
+};
+
+
+template<typename Domain>
+struct Solver {
+  Solver(const EquationSystem<Domain>& system)
+    : _system(system),
+      _strategy(system),
+      _rho(_system, _strategy, -infinity<Domain>()) {
+    _strategy.setRho(_rho);
+  }
+
+  Domain solve(Variable<Domain>& var) {
+    MaxExpression<Domain>& rhs = *_system[var];
+
+    // _rho automatically keeps up to date with changes made to the
+    // strategy, so you don't need to stabilise it
+
+    _strategy.get(rhs);
+
+
+    /*
+    do {
+      _strategy.hasChanged(false);
+      
+      solver_log::debug << "Stabilise assignment (toplevel)" << std::endl;
+      _rho.stabilise();
+      
+      solver_log::debug << "Improve strategy (toplevel)" << std::endl;
+      // improve strategy
+      _strategy.get(rhs);
+      solver_log::debug << (_strategy.hasChanged() ? "Strategy has changed - loop again" : "Strategy has not changed - terminate") << std::endl;
+    } while (_strategy.hasChanged());
+    */
+
+    return _rho[var];
+  }
 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;
+  DynamicMaxStrategy<Domain> _strategy;
+  DynamicVariableAssignment<Domain> _rho;
 };
 
+
 /*template<typename Domain>
 std::ostream& operator<<(std::ostream& cout, const MaxStrategy<Domain>& strat) {
   strat.print(cout);