From 5f3cb0bf02ed32976370cf6c7f656d000b4d7694 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Fri, 15 Jun 2012 11:26:32 +1000 Subject: Re-write heaps of code to work better. --- impl/Complete.hpp | 7 +- impl/EquationSystem.hpp | 208 ++++++++++++++++++++++---------------------- impl/Expression.hpp | 143 +++++++++++++++++++++--------- impl/FixpointAlgorithm.hpp | 127 ++++++++++++++------------- impl/IdMap.hpp | 1 - impl/IdSet.hpp | 2 +- impl/MaxStrategy.hpp | 175 +++++++++++++++++++++---------------- impl/Operator.hpp | 166 ++++++++++++++++++----------------- impl/VariableAssignment.hpp | 30 +++++-- impl/main.cpp | 84 ++++++++++-------- 10 files changed, 539 insertions(+), 404 deletions(-) diff --git a/impl/Complete.hpp b/impl/Complete.hpp index 1cf40af..22e060a 100644 --- a/impl/Complete.hpp +++ b/impl/Complete.hpp @@ -4,10 +4,15 @@ #include #include +template +T infinity() { } + template struct Complete { Complete() : _value(0), _infinity(false) { } + Complete(const T& value) + : _value(value), _infinity(false) { } Complete(const T& value, const bool& infinity) : _value(value), _infinity(infinity) { if (value == 0 && infinity == true) { @@ -69,7 +74,7 @@ struct Complete { } } bool operator>(const Complete& other) const { - return !(*this < other || *this == other); + return other < *this; } bool operator==(const Complete& other) const { if (_infinity) { diff --git a/impl/EquationSystem.hpp b/impl/EquationSystem.hpp index 13319e0..50a0e45 100644 --- a/impl/EquationSystem.hpp +++ b/impl/EquationSystem.hpp @@ -1,141 +1,145 @@ #ifndef EQUATION_SYSTEM_HPP #define EQUATION_SYSTEM_HPP +#include +#include #include - -template -struct EquationSystem; - -#include "IdSet.hpp" +#include "Operator.hpp" #include "Expression.hpp" -#include "FixpointAlgorithm.hpp" +#include "VariableAssignment.hpp" -template -struct MaxStrategy; - -template +template struct EquationSystem { - virtual ~EquationSystem() { - for (int i = 0, size = _expressions.size(); i < size; ++i) { - delete _expressions[i]; - } - for (int i = 0, size = _vars.size(); i < size; ++i) { - delete _vars[i]; + virtual ~EquationSystem() { } + virtual const Expression* operator[](const Variable&) const = 0; + virtual VariableAssignment* eval(const VariableAssignment& rho) const = 0; + virtual unsigned int variableCount() const = 0; + virtual Variable& variable(unsigned int) const = 0; + virtual StableVariableAssignment* assignment(const Domain& value) const = 0; + virtual bool equalAssignments(const VariableAssignment&, const VariableAssignment&) const = 0; + + virtual void print(std::ostream& cout) const = 0; +}; + +template +struct ConcreteEquationSystem : public EquationSystem { + virtual ~ConcreteEquationSystem() { + for (typename std::set*>::iterator it = _expressions.begin(); + it != _expressions.end(); + ++it) { + delete *it; } - } - Variable* newVariable(const std::string& name) { - typename std::map*>::iterator it = _var_names.find(name); - if (it == _var_names.end()) { - Variable* newVar = new Variable(_vars.size(), name); - _vars.push_back(newVar); - _var_names[name] = newVar; - return _vars[_vars.size()-1]; - } else { - return it->second; + for (typename std::set*>::iterator it = _operators.begin(); + it != _operators.end(); + ++it) { + delete *it; } } - const std::vector*> vars() const { - return _vars; + + MaxExpression& maxExpression(const std::vector*>& arguments) { + unsigned int id = _max_expressions.size(); + Maximum* max = new Maximum(); + MaxExpression* expr = new MaxExpression(id, *max, arguments); + _operators.insert(max); + _max_expressions.push_back(expr); + _expressions.insert(expr); + return *expr; } - const Variable* getVar(unsigned int i) const { - return _vars[i]; + MaxExpression& maxExpression(unsigned int i) const { + return *_max_expressions[i]; } - unsigned int varCount() const { - return _vars.size(); + unsigned int maxExpressionCount() const { + return _max_expressions.size(); } - Expression* newExpression(Operator* op, const std::vector*>& args=std::vector*>()) { - Expression* expr = new Expression(op, args); - _expressions.push_back(expr); - return expr; + Expression& expression(Operator* op, const std::vector*>& arguments) { + Expression* expr = new OperatorExpression(*op, arguments); + _operators.insert(op); + _expressions.insert(expr); + return *expr; } - MaxExpression* newMaxExpression(const std::vector*>& args) { - MaxExpression* expr = new MaxExpression(args); - expr->id(_max_expressions.size()); - _max_expressions.push_back(expr); - _expressions.push_back(expr); - return expr; + Variable& variable(const std::string& name) { + if (_variable_names.find(name) == _variable_names.end()) { + // not found - create a new variable and whatnot + unsigned int id = _variables.size(); + Variable* var = new Variable(id, name); + _variables.push_back(var); + _right_sides.push_back(NULL); + _expressions.insert(var); + _variable_names[name] = var; + return *var; + } else { + return *_variable_names[name]; + } } - unsigned int maxCount() const { - return _max_expressions.count(); + Variable& variable(unsigned int id) const { + return *_variables[id]; } - const MaxExpression* getMax(unsigned int i) const { - return _max_expressions[i]; + unsigned int variableCount() const { + return _variables.size(); } - MaxStrategy strategy() const { - return MaxStrategy(_max_expressions.size()); + Constant& constant(const Domain& value) { + Constant* constant = new Constant(value); + _expressions.insert(constant); + return *constant; } - VariableAssignment assignment() const { - return VariableAssignment(_vars.size()); + Expression* operator[](const Variable& var) const { + return _right_sides[var.id()]; } - - Expression*& operator[] (const Variable& v) { - if (_right_expressions.size() <= v.id()) { - _right_expressions.resize(v.id()+1); - } - return _right_expressions[v.id()]; - } - const Expression* operator[] (const Variable& v) const { - if (_right_expressions.size() <= v.id()) { - throw "Out of range"; - } - return _right_expressions[v.id()]; + Expression*& operator[](const Variable& var) { + return _right_sides[var.id()]; } - template - VariableAssignment foreach(F op, const VariableAssignment& rho) const { - VariableAssignment result(_vars.size()); - for (unsigned int i = 0, size = _vars.size(); i < size; ++i) { - result[*_vars[i]] = op(*_right_expressions[i], rho); - } - return result; + StableVariableAssignment* assignment(const Domain& value) const { + return new StableVariableAssignment(_variables.size(), value); } - - VariableAssignment operator() (const VariableAssignment& rho) const { - VariableAssignment result(_vars.size()); - for (unsigned int i = 0, size = _vars.size(); i < size; ++i) { - result[*_vars[i]] = (*_right_expressions[i])(rho); + VariableAssignment* eval(const VariableAssignment& rho) const { + StableVariableAssignment* result = this->assignment(-infinity()); + for (unsigned int i = 0, length = _variables.size(); + i < length; + ++i) { + const Variable& var = *_variables[i]; + const Expression& expr = * (*this)[var]; + (*result)[var] = expr.eval(rho); } return result; } - VariableAssignment maxFixpoint() const { - unsigned int size = _vars.size(); - VariableAssignment newResult(size, infinity()); - VariableAssignment result(0); - do { - result = newResult; - newResult = (*this)(result); - } while (newResult != result); - return result; + virtual bool equalAssignments(const VariableAssignment& l, const VariableAssignment& r) const { + for (unsigned int i = 0, length = _variables.size(); + i < length; + ++i) { + const Variable& var = *_variables[i]; + if (l[var] != r[var]) + return false; + } + return true; } - VariableAssignment maxFixpoint(const MaxStrategy& strat, const FixpointAlgorithm& algo) const { - return algo.maxFixpoint(strat, *this); + void print(std::ostream& cout) const { + for (unsigned int i = 0, length = _variables.size(); + i < length; + ++i) { + cout << *_variables[i] << " = " << *_right_sides[i] << std::endl; + } } - VariableAssignment minFixpoint(const FixpointAlgorithm& algo) const { - VariableAssignment rho = assignment(); - VariableAssignment lastRho(0); - MaxStrategy strat = strategy(); - do { - lastRho = rho; - strat = strat.improve(*this, rho); - rho = maxFixpoint(strat, algo); - } while(lastRho != rho); - return rho; - } private: - std::map*> _var_names; - std::vector*> _vars; - std::vector*> _max_expressions; - std::vector*> _expressions; - std::vector*> _right_expressions; + std::set*> _operators; + std::set*> _expressions; + std::vector*> _variables; + std::map*> _variable_names; + std::vector*> _max_expressions; + std::vector*> _right_sides; }; -#include "MaxStrategy.hpp" +template +std::ostream& operator<<(std::ostream& cout, const EquationSystem& system) { + system.print(cout); + return cout; +} #endif diff --git a/impl/Expression.hpp b/impl/Expression.hpp index d3dfcf3..72318e4 100644 --- a/impl/Expression.hpp +++ b/impl/Expression.hpp @@ -1,68 +1,125 @@ #ifndef EXPRESSION_HPP #define EXPRESSION_HPP -#include -#include "VariableAssignment.hpp" +#include +#include +#include +#include "IdMap.hpp" #include "Operator.hpp" -template -struct Variable; -template -struct MaxStrategy; - -int ExpressionCount; +template +struct VariableAssignment; -template +template struct Expression { - Expression(Operator* op, const std::vector< Expression* >& args) - : _operator(op), _arguments(args) { } - virtual ~Expression() { - if (!dynamic_cast*>(_operator)) { - delete _operator; - } + virtual ~Expression() { } + + virtual Domain eval(const VariableAssignment&) const = 0; + + virtual void print(std::ostream&) const = 0; +}; + +template +struct Constant : public Expression { + Constant(const Domain& value) + : _value(value) { } + + virtual Domain eval(const VariableAssignment&) const { + return _value; } - virtual T operator() (const VariableAssignment& assignment) const { - return (*_operator)(_arguments, assignment); + + void print(std::ostream& cout) const { + cout << _value; } - protected: - Operator* _operator; - std::vector< Expression* > _arguments; + + private: + Domain _value; }; -template -struct MaxExpression : public Expression { - MaxExpression(const std::vector< Expression* >& args) - : Expression(new Maximum, args) { } +template +struct Variable : public Expression { + Variable(const unsigned int& id, const std::string& name) + : _id(id), _name(name) { } + unsigned int id() const { return _id; } - unsigned int id(unsigned int id) { - return (_id = id); + std::string name() const { + return _name; } - Expression* argument(unsigned int i) const { - if (i >= Expression::_arguments.size()) { - throw "Error"; + + virtual Domain eval(const VariableAssignment& rho) const { + return rho[*this]; + } + + void print(std::ostream& cout) const { + cout << name(); + } + + private: + const unsigned int _id; + const std::string _name; +}; + +template +struct OperatorExpression : public Expression { + OperatorExpression(const Operator& op, const std::vector*>& arguments) + : _operator(op), _arguments(arguments) { } + + virtual Domain eval(const VariableAssignment& rho) const { + std::vector argumentValues; + for (typename std::vector*>::const_iterator it = _arguments.begin(); + it != _arguments.end(); + ++it) { + argumentValues.push_back((*it)->eval(rho)); } - return Expression::_arguments[i]; + return _operator.eval(argumentValues); + } + + const std::vector*> arguments() const { + return _arguments; } - virtual T operator() (const VariableAssignment& assignment) const { - throw "error"; + + const Operator& op() const { + return _operator; } - std::pair bestStrategy(const VariableAssignment& rho, const MaxStrategy& strat) const { - std::pair best = std::pair(-infinity(), 0); - for (unsigned int i = 0, size = Expression::_arguments.size(); i < size; ++i) { - T value = strat(*Expression::_arguments[i], rho); - if (value > best.first) - best = std::pair(value, i); + + void print(std::ostream& cout) const { + cout << _operator << "("; + for (unsigned int i = 0, length = _arguments.size(); + i < length; + ++i) { + if (i > 0) + cout << ", "; + cout << *_arguments[i]; } - std::cerr << "Best strategy: (" << best.first << ", " << best.second << ")" << std::endl << std::endl; - return best; + cout << ")"; + } + + private: + const Operator& _operator; + const std::vector*> _arguments; +}; + +template +struct MaxExpression : public OperatorExpression { + MaxExpression(const unsigned int& id, const Maximum& op, const std::vector*>& arguments) + : OperatorExpression(op, arguments), _id(id) { } + + unsigned int id() const { + return _id; } + private: - unsigned int _id; + const unsigned int _id; }; -#include "Variable.hpp" -#include "MaxStrategy.hpp" +template +std::ostream& operator<<(std::ostream& cout, const Expression& exp) { + exp.print(cout); + return cout; +} + +#include "VariableAssignment.hpp" #endif diff --git a/impl/FixpointAlgorithm.hpp b/impl/FixpointAlgorithm.hpp index ed97bec..f199476 100644 --- a/impl/FixpointAlgorithm.hpp +++ b/impl/FixpointAlgorithm.hpp @@ -1,97 +1,100 @@ #ifndef FIXPOINT_ALGORITHM_HPP #define FIXPOINT_ALGORITHM_HPP +#include "IdSet.hpp" +#include "IdMap.hpp" #include "VariableAssignment.hpp" +#include "EquationSystem.hpp" -template -struct EquationSystem; -template -struct MaxStrategy; - -template +template struct FixpointAlgorithm { - virtual VariableAssignment maxFixpoint(const MaxStrategy&, const EquationSystem&) const = 0; + virtual ~FixpointAlgorithm() { } + virtual VariableAssignment* maxFixpoint(const EquationSystem&) const = 0; }; -#include "EquationSystem.hpp" -#include "MaxStrategy.hpp" - -template -struct NaiveFixpoint : public FixpointAlgorithm { - virtual VariableAssignment maxFixpoint(const MaxStrategy& strat, const EquationSystem& system) const { - unsigned int size = system.varCount(); - VariableAssignment newResult(size, infinity()); - VariableAssignment result(0); +template +struct NaiveFixpointAlgorithm : public FixpointAlgorithm { + virtual VariableAssignment* maxFixpoint(const EquationSystem& system) const { + VariableAssignment* rho = NULL; + VariableAssignment* result = system.assignment(infinity()); do { - result = newResult; - newResult = strat(system, result); - } while (newResult != result); + if (rho) delete rho; + rho = result; + result = system.eval(*rho); + } while (!system.equalAssignments(*rho, *result)); + if (rho) delete rho; return result; } }; - -template -struct RecursiveFixpoint : public FixpointAlgorithm { - // this is a "VariableAssignment" which actually performs a recursive - // call to determine what value to return - struct EvaluatingVariableAssignment : public VariableAssignment { - EvaluatingVariableAssignment(const MaxStrategy& strategy, const EquationSystem& system) - : VariableAssignment(system.varCount(), infinity()), - _strategy(strategy), _system(system), +template +struct SmartFixpointAlgorithm : public FixpointAlgorithm { + struct DynamicVariableAssignment : public VariableAssignment { + DynamicVariableAssignment(const EquationSystem& system) + : _system(system), _evaluating(NULL), - _influence(system.varCount(), IdSet >(system.varCount())), - _stable(system.varCount()) { - } - virtual T& operator[] (const Variable& x) const { - if (_evaluating == NULL) { - solve(x); - return VariableAssignment::_assignment[x.id()]; - } else { - solve(x); - _influence[x].insert(*_evaluating); - return VariableAssignment::_assignment[x.id()]; + _values(system.variableCount(), -infinity()), + _stable(system.variableCount()), + _haveValue(system.variableCount()), + _influence(system.variableCount(), IdSet >(system.variableCount())), + _id(0) { } + + const Domain& operator[](const Variable& var) const { + _id++; + solve(var); + for (unsigned int i = 0; i < _id; ++i) { + std::cout << " "; + } + std::cout << "operator[] " << var.name() << " => " << _values[var] << std::endl; + _id--; + if (_evaluating) { + _influence[var].insert(*_evaluating); } + return _values[var]; } - void solve(const Variable& x) const { + + private: + void solve(const Variable& x) const { if (!_stable.contains(x)) { _stable.insert(x); + for (unsigned int i = 0; i < _id; ++i) { + std::cout << " "; + } + std::cout << "solve(" << x.name() << ") " << &x << " " << _evaluating << std::endl; + std::cout << _stable << std::endl; - const Variable* oldEval = _evaluating; + const Variable* oldEval = _evaluating; _evaluating = &x; - T t = _strategy(*_system[x], *this); + Domain val = _system[x]->eval(*this); _evaluating = oldEval; - if (t != VariableAssignment::_assignment[x.id()]) { - IdSet > oldInfluence = _influence[x]; - _influence[x].clear(); // clear out our idea of what x influences - VariableAssignment::_assignment[x.id()] = t; + if (val != _values[x]) { + IdSet > oldInfluence = _influence[x]; + _influence[x].clear(); + _values[x] = val; - _stable.filter(oldInfluence); // whatever x influences needs to be re-evaluated + _stable.filter(oldInfluence); - for (typename IdSet >::iterator it = oldInfluence.begin(); + for (typename IdSet >::iterator it = oldInfluence.begin(); it != oldInfluence.end(); ++it) { - solve(*_system.getVar(*it)); + solve(_system.variable(*it)); } } } } - private: - const MaxStrategy& _strategy; - const EquationSystem& _system; - mutable const Variable* _evaluating; - mutable IdMap, IdSet > > _influence; - mutable IdSet > _stable; + + const EquationSystem& _system; + mutable const Variable* _evaluating; + mutable IdMap,Domain> _values; + mutable IdSet > _stable; + mutable IdSet > _haveValue; + mutable IdMap,IdSet > > _influence; + mutable unsigned int _id; }; - virtual VariableAssignment maxFixpoint(const MaxStrategy& strat, const EquationSystem& system) const { - EvaluatingVariableAssignment assignment(strat, system); - VariableAssignment result(system.varCount()); - for (unsigned int i = 0; i < system.varCount(); ++i) { - result[*system.getVar(i)] = assignment[*system.getVar(i)]; - } - return result; + virtual VariableAssignment* maxFixpoint(const EquationSystem& system) const { + return new DynamicVariableAssignment(system); } }; diff --git a/impl/IdMap.hpp b/impl/IdMap.hpp index b3a87fb..b265e37 100644 --- a/impl/IdMap.hpp +++ b/impl/IdMap.hpp @@ -58,7 +58,6 @@ struct IdMap { return !(*this == other); } - template friend std::ostream& operator<<(std::ostream& cout, const IdMap& rho); diff --git a/impl/IdSet.hpp b/impl/IdSet.hpp index 6f6fd3f..8c64051 100644 --- a/impl/IdSet.hpp +++ b/impl/IdSet.hpp @@ -91,7 +91,7 @@ class IdSet { void absorb(const IdSet& other) { if (_length == other._length) { - for (unsigned int i = 0; i < _length; ++i) { + for (unsigned int i = 0; i < DIV_ROUND_UP(_length, CELL_SIZE); ++i) { _values[i] |= other._values[i]; } } else { diff --git a/impl/MaxStrategy.hpp b/impl/MaxStrategy.hpp index aa49c9d..5d139fe 100644 --- a/impl/MaxStrategy.hpp +++ b/impl/MaxStrategy.hpp @@ -1,100 +1,129 @@ -#ifndef MAX_STRATEGY_HPP -#define MAX_STRATEGY_HPP +#ifndef MAX_EXPRESSION_HPP +#define MAX_EXPRESSION_HPP -#include #include "Expression.hpp" #include "EquationSystem.hpp" -#include "VariableAssignment.hpp" - -template -struct MaxStrategy { - MaxStrategy() - : _length(0), _assignment(NULL) { } - MaxStrategy(unsigned int length) - : _length(length), _assignment(new unsigned int[length]) { - for (unsigned int i = 0; i < length; ++i) { - _assignment[i] = 0; + +template +struct MaxStrategyExpression : public Expression { + MaxStrategyExpression(const Expression& expr, const IdMap,unsigned int>& strategy) + : _expr(expr), _strategy(strategy) { } + + virtual Domain eval(const VariableAssignment& rho) const { + // relies on implementation details - BAD BAD BAD, maybe + const OperatorExpression* opExpr = dynamic_cast*>(&_expr); + if (opExpr) { + const MaxExpression* maxExpr = dynamic_cast*>(opExpr); + const std::vector*> args = opExpr->arguments(); + if (maxExpr) { + unsigned int i = _strategy[*maxExpr]; + return MaxStrategyExpression(*args[i], _strategy).eval(rho); + } else { + std::vector argumentValues; + for (typename std::vector*>::const_iterator it = args.begin(); + it != args.end(); + ++it) { + argumentValues.push_back(MaxStrategyExpression(**it, _strategy).eval(rho)); + } + return opExpr->op().eval(argumentValues); + } + } else { + return _expr.eval(rho); } } - MaxStrategy(const MaxStrategy& other) - : _length(other._length), _assignment(new unsigned int[other._length]) { - for (unsigned int i = 0; i < other._length; ++i) { - _assignment[i] = other._assignment[i]; - } + + void print(std::ostream& cout) const { + cout << _expr; } + private: + const Expression& _expr; + const IdMap,unsigned int>& _strategy; +}; - virtual ~MaxStrategy() { - delete[] _assignment; +template +struct MaxStrategy : public EquationSystem { + MaxStrategy(const ConcreteEquationSystem& system) + : _system(system), _expressions(system.variableCount(), NULL), _strategy(system.maxExpressionCount(), 0) { } - MaxStrategy& operator=(const MaxStrategy& other) { - if (_length != other._length) { - _length = other._length; - delete[] _assignment; - _assignment = new unsigned int[_length]; - } - for (unsigned int i = 0; i < _length; ++i) { - _assignment[i] = other._assignment[i]; + const Expression* operator[](const Variable& v) const { + if (_expressions[v] == NULL) { + Expression* expression = new MaxStrategyExpression(*_system[v], _strategy); + _expressions[v] = expression; + return expression; + } else { + return _expressions[v]; } - return *this; } - const unsigned int& operator[] (const MaxExpression x) const { - if (x.id() >= _length) { - throw "Array out of bounds"; - } - return _assignment[x.id()]; + unsigned int get(const MaxExpression& e) const { + return _strategy[e]; + } + unsigned int set(const MaxExpression& e, unsigned int i) { + _strategy[e] = i; + return i; } - unsigned int& operator[] (const MaxExpression& x) { - if (x.id() >= _length) { - throw "Array out of bounds"; + + VariableAssignment* eval(const VariableAssignment& rho) const { + StableVariableAssignment* result = this->assignment(-infinity()); + for (unsigned int i = 0, length = _system.variableCount(); + i < length; + ++i) { + const Variable& var = _system.variable(i); + const Expression& expr = * (*this)[var]; + (*result)[var] = expr.eval(rho); } - return _assignment[x.id()]; + return result; } - VariableAssignment operator() (const EquationSystem& eqns, const VariableAssignment& rho) const { - return eqns.foreach(*this, rho); + + unsigned int variableCount() const { + return _system.variableCount(); } - T operator() (const Expression& expr, const VariableAssignment& rho) const { - const MaxExpression* max = dynamic_cast*>(&expr); - if (max == NULL) { - return expr(rho); - } else { - return (*this)(*max->argument(_assignment[max->id()]), rho); - } + + Variable& variable(unsigned int i) const { + return _system.variable(i); } - MaxStrategy improve(const EquationSystem& s, const VariableAssignment& rho) const { - MaxStrategy newStrategy(*this); - for (unsigned int i = 0; i < _length; ++i) { - const MaxExpression& expr = *s.getMax(i); - const T oldValue = (*this)(expr, rho); - - // this relies on the fact that deeper MaxExpressions have a lower id - // than the MaxExpressions containing them. This means that we know that - // we have enough of a strategy to work with what we have within us - std::pair best = expr.bestStrategy(rho, newStrategy); - - if (best.first > oldValue) - newStrategy[expr] = best.second; - } - return newStrategy; + + StableVariableAssignment* assignment(const Domain& v) const { + return _system.assignment(v); + } + + bool equalAssignments(const VariableAssignment& l, const VariableAssignment& r) const { + return _system.equalAssignments(l, r); } - bool operator== (const MaxStrategy& other) const { - if (_length != other._length) - return false; - for (unsigned int i = 0; i < _length; ++i) { - if (_assignment[i] != other._assignment[i]) { - return false; + void improve(const VariableAssignment& rho) { + for (unsigned int i = 0, length = _system.maxExpressionCount(); + i < length; + ++i) { + MaxExpression& expr = _system.maxExpression(i); + Domain bestValue = MaxStrategyExpression(expr, _strategy).eval(rho); + unsigned int bestIndex = this->get(expr); + + // this relies on the fact that an expression will only be proessed after the expressions + // it depends on (which should always be true) + const std::vector*> args = expr.arguments(); + for (unsigned int j = 0, length = args.size(); + j < length; + ++j) { + const Domain value = MaxStrategyExpression(*args[j], _strategy).eval(rho); + if (bestValue < value) { + bestValue = value; + bestIndex = j; + } } + this->set(expr, bestIndex); } - return true; } - bool operator!= (const MaxStrategy& other) const { - return !(*this == other); + + void print(std::ostream& cout) const { + cout << _system << std::endl; } + private: - unsigned int _length; - unsigned int* _assignment; + const ConcreteEquationSystem& _system; + mutable IdMap,Expression*> _expressions; + IdMap,unsigned int> _strategy; }; #endif diff --git a/impl/Operator.hpp b/impl/Operator.hpp index 5f7cd1e..3072abe 100644 --- a/impl/Operator.hpp +++ b/impl/Operator.hpp @@ -1,116 +1,126 @@ #ifndef OPERATOR_HPP #define OPERATOR_HPP -template -T infinity() { } -template<> -float infinity() { - return INFINITY; -} - #include -#include "IdSet.hpp" - -template -struct Variable; - -template -struct VariableAssignment; -template -struct Expression; -template +template struct Operator { virtual ~Operator() { } - virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& rho) const = 0; + + virtual Domain eval(const std::vector&) const = 0; + + virtual void print(std::ostream&) const = 0; }; -template -struct Maximum : public Operator { - virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment) const { - T value = -infinity(); - for (typename std::vector< Expression* >::const_iterator it = args.begin(); - it != args.end(); + +template +struct Maximum : public Operator { + virtual Domain eval(const std::vector& arguments) const { + Domain result = -infinity(); + for (typename std::vector::const_iterator it = arguments.begin(); + it != arguments.end(); ++it) { - T temporary = (**it)(assignment); - value = (temporary > value ? temporary : value); - //if (value == infinity()) break; + result = (result < *it ? *it : result); } - return value; + return result; + } + void print(std::ostream& cout) const { + cout << "max"; } }; -template -struct Minimum : public Operator { - virtual T operator() (const std::vector< Expression* >& args, const VariableAssignment& assignment) const { - T value = infinity(); - for (typename std::vector< Expression* >::const_iterator it = args.begin(); - it != args.end(); + +template +struct Minimum : public Operator { + virtual Domain eval(const std::vector& arguments) const { + Domain result = infinity(); + for (typename std::vector::const_iterator it = arguments.begin(); + it != arguments.end(); ++it) { - T temporary = (**it)(assignment); - value = (temporary < value ? temporary : value); - //if (value == -infinity()) break; + result = (*it < result ? *it : result); } - return value; + return result; + } + void print(std::ostream& cout) const { + cout << "min"; } }; -template -struct Constant : public Operator { - Constant(const T& val) - : _value(val) { } - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { - return _value; +template +struct Negation : public Operator { + virtual Domain eval(const std::vector& arguments) const { + if (arguments.size() > 1) + throw "Too many arguments to a negation."; + return -arguments[0]; + } + void print(std::ostream& cout) const { + cout << "-"; } - private: - const T _value; }; -template -struct Addition: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { - T sum = (*args[0])(ass); - for (unsigned int i = 1, size = args.size(); i < size; ++i) { - sum += (*args[i])(ass); +template +struct Addition : public Operator { + virtual Domain eval(const std::vector& arguments) const { + Domain result = 0; + for (typename std::vector::const_iterator it = arguments.begin(); + it != arguments.end(); + ++it) { + result += *it; } - return sum; + return result; + } + void print(std::ostream& cout) const { + cout << "add"; } }; -template -struct Subtraction: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { - T sum = (*args[0])(ass); - for (unsigned int i = 1, size = args.size(); i < size; ++i) { - sum -= (*args[i])(ass); +template +struct Subtraction : public Operator { + virtual Domain eval(const std::vector& arguments) const { + Domain result = 0; + for (typename std::vector::const_iterator it = arguments.begin(); + it != arguments.end(); + ++it) { + if (it == arguments.begin()) + result = *it; + else + result -= *it; } - return sum; + return result; + } + void print(std::ostream& cout) const { + cout << "sub"; } }; -template -struct Comma: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { - if ((*args[0])(ass) == -infinity()) { - std::cout << "Comma - neg inf" << std::endl; - return -infinity(); - } else { - std::cout << "Comma - finite" << std::endl; - return (*args[1])(ass); +template +struct Comma : public Operator { + virtual Domain eval(const std::vector& arguments) const { + if (arguments[0] == -infinity()) { + return -infinity(); } + return arguments[1]; + } + void print(std::ostream& cout) const { + cout << "comma"; } }; -template -struct Guard: public Operator { - T operator() (const std::vector< Expression* >& args, const VariableAssignment& ass) const { - if ((*args[0])(ass) < (*args[1])(ass)) { - return -infinity(); - } else { - return (*args[2])(ass); +template +struct Guard : public Operator { + virtual Domain eval(const std::vector& arguments) const { + if (arguments[0] < arguments[1]) { + return -infinity(); } + return arguments[2]; + } + void print(std::ostream& cout) const { + cout << "guard"; } }; -#include "VariableAssignment.hpp" -#include "Expression.hpp" +template +std::ostream& operator<<(std::ostream& cout, const Operator& op) { + op.print(cout); + return cout; +} #endif diff --git a/impl/VariableAssignment.hpp b/impl/VariableAssignment.hpp index 9d8137a..e0f7dc8 100644 --- a/impl/VariableAssignment.hpp +++ b/impl/VariableAssignment.hpp @@ -1,17 +1,29 @@ #ifndef VARIABLE_ASSIGNMENT_HPP #define VARIABLE_ASSIGNMENT_HPP -#include "Variable.hpp" +#include "Expression.hpp" #include "IdMap.hpp" -template -struct VariableAssignment : public IdMap,T> { - VariableAssignment(unsigned int length) - : IdMap,T>(length, -infinity()) { } - VariableAssignment(unsigned int length, const T& initial) - : IdMap,T>(length, initial) { } - VariableAssignment(const VariableAssignment& other) - : IdMap,T>(other) { } +template +struct VariableAssignment { + virtual ~VariableAssignment() { } + virtual const Domain& operator[](const Variable&) const = 0; +}; + +template +struct StableVariableAssignment +: public VariableAssignment, public IdMap, Domain> { + StableVariableAssignment(unsigned int length) + : IdMap,Domain>(length, -infinity()) { } + StableVariableAssignment(unsigned int length, const Domain& value) + : IdMap,Domain>(length, value) { } + + const Domain& operator[](const Variable& var) const { + return IdMap,Domain>::operator[](var); + } + Domain& operator[](const Variable& var) { + return IdMap,Domain>::operator[](var); + } }; #endif diff --git a/impl/main.cpp b/impl/main.cpp index 530556f..b03a4f2 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -1,15 +1,12 @@ #include #include -#include -#include #include -#include - -#include "Operator.hpp" +#include "Complete.hpp" #include "Expression.hpp" -#include "MaxStrategy.hpp" +#include "Operator.hpp" #include "EquationSystem.hpp" -#include "Complete.hpp" +#include "MaxStrategy.hpp" +#include "FixpointAlgorithm.hpp" extern "C" { #include "EquationSystemParser.h" @@ -19,36 +16,35 @@ extern "C" { using namespace std; template -Expression* treeToExpression(pANTLR3_BASE_TREE node, EquationSystem& system) { +Expression& treeToExpression(pANTLR3_BASE_TREE node, ConcreteEquationSystem& system) { ANTLR3_UINT32 num = node->getChildCount(node); - string name = (char*) node->getText(node)->chars; - // leaf node - constant or variable if (num == 0) { + // leaf node -> constant or variable if (name == "inf") { - return system.newExpression(new Constant(infinity())); + return system.constant(infinity()); } else { stringstream stream(name); T output; if (stream >> output) { - return system.newExpression(new Constant(output)); + return system.constant(output); } else { - return system.newExpression(system.newVariable(name)); + return system.variable(name); } } } - // other operators + // anything that's not a constant/variable std::vector*> args; pANTLR3_BASE_TREE childNode; for (unsigned int i = 0; i < num; ++i) { childNode = (pANTLR3_BASE_TREE) node->getChild(node, i); - args.push_back(treeToExpression(childNode, system)); + args.push_back(&treeToExpression(childNode, system)); } if (name == "max") { - return system.newMaxExpression(args); + return system.maxExpression(args); } else { Operator* op = NULL; if (name == "min") { @@ -56,21 +52,24 @@ Expression* treeToExpression(pANTLR3_BASE_TREE node, EquationSystem& syste } else if (name == "+") { op = new Addition(); } else if (name == "-") { - op = new Subtraction(); + if (args.size() == 1) { + op = new Negation(); + } else { + op = new Subtraction(); + } } else if (name == ";") { op = new Comma(); } else if (name == "GUARD") { op = new Guard(); } else { - std::cerr << "Unknown leaf node type: " << name << std::endl; - throw "Unknown leaf node type"; + throw "Parse error: Unknown operator"; } - return system.newExpression(op, args); + return system.expression(op, args); } } template -void treeToSystem(pANTLR3_BASE_TREE node, EquationSystem& system) { +void treeToSystem(pANTLR3_BASE_TREE node, ConcreteEquationSystem& system) { ANTLR3_UINT32 num = node->getChildCount(node); if (num % 2 == 1) @@ -83,12 +82,12 @@ void treeToSystem(pANTLR3_BASE_TREE node, EquationSystem& system) { exprNode = (pANTLR3_BASE_TREE) node->getChild(node, i+1); string varName = (char*) varNode->getText(varNode)->chars; - Variable* var = system.newVariable(varName); + Variable& var = system.variable(varName); vector*> args; - args.push_back(system.newExpression(new Constant(-infinity()))); - args.push_back(treeToExpression(exprNode, system)); - system[*var] = system.newMaxExpression(args); + args.push_back(&system.constant(-infinity())); + args.push_back(&treeToExpression(exprNode, system)); + system[var] = &system.maxExpression(args); } } @@ -96,11 +95,11 @@ typedef Complete ZBar; int main (int argc, char* argv[]) { FixpointAlgorithm* algorithm = NULL; if (argc > 2 && !strcmp(argv[2], "naive")) { - algorithm = new NaiveFixpoint(); + algorithm = new NaiveFixpointAlgorithm(); cout << "Naive fixpoint" << endl; } else { - algorithm = new RecursiveFixpoint(); - cout << "Recursive fixpoint" << endl; + algorithm = new SmartFixpointAlgorithm(); + cout << "Smart fixpoint" << endl; } pANTLR3_INPUT_STREAM input; @@ -115,16 +114,33 @@ int main (int argc, char* argv[]) { EquationSystemParser_equation_system_return ret = parser -> equation_system(parser); - EquationSystem system; + ConcreteEquationSystem system; treeToSystem(ret.tree, system); // DO MORE HERE - VariableAssignment rho = system.minFixpoint(*algorithm); - std::cout << rho << std::endl; + cout << system << endl; + VariableAssignment* prev = NULL; + VariableAssignment* result = system.assignment(-infinity()); + MaxStrategy strategy(system); + do { + if (prev) delete prev; + prev = result; + strategy.improve(*prev); + for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) { + Variable& var = system.variable(i); + cout << var.name() << " = " << (*result)[var] << ", "; + } + cout << endl; + result = algorithm->maxFixpoint(strategy); + } while(!system.equalAssignments(*prev, *result)); + if (prev) delete prev; + + VariableAssignment* rho = result; - const std::vector*> vars = system.vars(); - for (unsigned int i = 0, size = vars.size(); i < size; ++i) { - cout << vars[i]->name() << " = " << rho[*vars[i]] << endl; + cout << endl; + for (unsigned int i = 0, size = system.variableCount(); i < size; ++i) { + Variable& var = system.variable(i); + cout << var.name() << " = " << (*rho)[var] << endl; } parser -> free(parser); -- cgit v1.2.3