Module: ppl/ppl Branch: pip Commit: d5889e252f39916812471f4bf2da15d624accf00 URL: http://www.cs.unipr.it/git/gitweb.cgi?p=ppl/ppl.git;a=commit;h=d5889e252f399...

Author: Enea Zaffanella zaffanella@cs.unipr.it Date: Thu Oct 8 20:41:16 2009 +0200

Added implementations for PIP_Problem swap and operator= methods. Added a few consistency checks in method OK(). Pointed out a resource management bug in copy constructor that can result in memory corruption. Added test04() to pipproblem1.cc (currently commented out) showing that a segmentation fault can be obtained when copying a PIP_Problem object having a non-null solution tree.

---

src/PIP_Problem.cc | 54 ++++++++++++++++++++++++++++++++++++- src/PIP_Problem.defs.hh | 2 +- src/PIP_Problem.inlines.hh | 20 ++++++++++++++ tests/PIP_Problem/pipproblem1.cc | 36 +++++++++++++++++++++++++ 4 files changed, 109 insertions(+), 3 deletions(-)

diff --git a/src/PIP_Problem.cc b/src/PIP_Problem.cc index ffb093e..350f065 100644 --- a/src/PIP_Problem.cc +++ b/src/PIP_Problem.cc @@ -53,6 +53,8 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) : external_space_dim(y.external_space_dim), internal_space_dim(y.internal_space_dim), status(y.status), + // FIXME: this causes sharing of the solution tree, + // possibly later resulting in memory corruption (double free). current_solution(y.current_solution), initialized(y.initialized), input_cs(y.input_cs), @@ -60,7 +62,7 @@ PPL::PIP_Problem::PIP_Problem(const PIP_Problem &y) parameters(y.parameters), initial_context(y.initial_context) { PPL_ASSERT(OK()); - //FIXME: must also copy the solution tree + // FIXME: must also copy the solution tree }

PPL::PIP_Problem::~PIP_Problem() { @@ -164,7 +166,55 @@ PPL::PIP_Problem::optimizing_solution() const {

bool PPL::PIP_Problem::OK() const { - //FIXME +#ifndef NDEBUG + using std::endl; + using std::cerr; +#endif + + if (external_space_dim < internal_space_dim) { +#ifndef NDEBUG + cerr << "The internal space dimension of the PIP_Problem is " + << "greater than its external space dimension." + << endl; + ascii_dump(cerr); +#endif + return false; + } + + // Constraint system should be OK. + const dimension_type input_cs_num_rows = input_cs.size(); + for (dimension_type i = input_cs_num_rows; i-- > 0; ) + if (!input_cs[i].OK()) + return false; + + // Constraint system should contain no strict inequalities. + for (dimension_type i = input_cs_num_rows; i-- > 0; ) { + if (input_cs[i].is_strict_inequality()) { +#ifndef NDEBUG + cerr << "The feasible region of the PIP_Problem is defined by " + << "a constraint system containing strict inequalities." + << endl; + ascii_dump(cerr); +#endif + return false; + } + if (input_cs[i].space_dimension() > external_space_dim) { +#ifndef NDEBUG + cerr << "The space dimension of the PIP_Problem is smaller than " + << "the space dimension of one of its constraints." + << endl; + ascii_dump(cerr); +#endif + return false; + } + } + + if (!parameters.OK()) + return false; + if (!initial_context.OK()) + return false; + + // All checks passed. return true; }

diff --git a/src/PIP_Problem.defs.hh b/src/PIP_Problem.defs.hh index beb291b..0096879 100644 --- a/src/PIP_Problem.defs.hh +++ b/src/PIP_Problem.defs.hh @@ -307,7 +307,7 @@ private: Status status;

//! The current solution decision tree - PIP_Tree_Node *current_solution; + PIP_Tree_Node* current_solution;

/*! \brief A Boolean encoding whether or not internal data structures have diff --git a/src/PIP_Problem.inlines.hh b/src/PIP_Problem.inlines.hh index 44cbc94..61fe0a8 100644 --- a/src/PIP_Problem.inlines.hh +++ b/src/PIP_Problem.inlines.hh @@ -50,6 +50,26 @@ PIP_Problem::parameter_space_dimensions() const { return parameters; }

+inline void +PIP_Problem::swap(PIP_Problem& y) { + std::swap(external_space_dim, y.external_space_dim); + std::swap(internal_space_dim, y.internal_space_dim); + std::swap(status, y.status); + std::swap(current_solution, y.current_solution); + std::swap(initialized, y.initialized); + std::swap(input_cs, y.input_cs); + std::swap(first_pending_constraint, y.first_pending_constraint); + std::swap(parameters, y.parameters); + std::swap(initial_context, y.initial_context); +} + +inline PIP_Problem& +PIP_Problem::operator=(const PIP_Problem& y) { + PIP_Problem tmp(y); + swap(tmp); + return *this; +} + } // namespace Parma_Polyhedra_Library

namespace std { diff --git a/tests/PIP_Problem/pipproblem1.cc b/tests/PIP_Problem/pipproblem1.cc index bcd76f8..394a127 100644 --- a/tests/PIP_Problem/pipproblem1.cc +++ b/tests/PIP_Problem/pipproblem1.cc @@ -165,10 +165,46 @@ test03() { return ok; }

+bool +test04() { + Variable i(0); + Variable j(1); + Variable k(2); + Variable m(3); + Variable n(4); + Variables_Set params(k, n); + + Constraint_System cs; + cs.insert(i <= m); + cs.insert(j <= n); + cs.insert(2*i+j <= 2*m+n-k); + cs.insert(2*i+j >= 2*m+n-k); + + PIP_Problem pip(cs.space_dimension(), cs.begin(), cs.end(), params); + + bool ok = (pip.solve() == OPTIMIZED_PIP_PROBLEM); + if (ok) { + const PIP_Tree solution = pip.solution(); + display_solution(solution, params, Variables_Set(i, j), + cs.space_dimension()); + } + + // Copy constructor is buggy. + { + PIP_Problem pip_copy = pip; + // Here we call the destructor of pip_copy + // and we also destroy the (shared) solution tree of pip. + } + + return ok; +} + } // namespace

BEGIN_MAIN DO_TEST(test01); DO_TEST(test02); DO_TEST(test03); + // Uncomment this to get a segmentation fault. + // DO_TEST(test04); END_MAIN