tgbaproduct.cc 10.9 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
// Copyright (C) 2009, 2011, 2012, 2014, 2015 Laboratoire de Recherche et
3
// Développement de l'Epita (LRDE).
Guillaume Sadegh's avatar
Guillaume Sadegh committed
4
// Copyright (C) 2003, 2004, 2006 Laboratoire d'Informatique de
5 6
// Paris 6 (LIP6), département Systèmes Répartis Coopératifs (SRC),
// Université Pierre et Marie Curie.
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
7 8 9 10 11
//
// This file is part of Spot, a model checking library.
//
// Spot is free software; you can redistribute it and/or modify it
// under the terms of the GNU General Public License as published by
12
// the Free Software Foundation; either version 3 of the License, or
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
13 14 15 16 17 18 19 20
// (at your option) any later version.
//
// Spot is distributed in the hope that it will be useful, but WITHOUT
// ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
// or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
// License for more details.
//
// You should have received a copy of the GNU General Public License
21
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
22

23
#include "tgbaproduct.hh"
24
#include <string>
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
25
#include <cassert>
26
#include "misc/hashfunc.hh"
27
#include "kripke/kripke.hh"
28 29 30 31 32

namespace spot
{

  ////////////////////////////////////////////////////////////
33
  // state_product
34

35
  state_product::~state_product()
36
  {
37 38
    left_->destroy();
    right_->destroy();
39 40
  }

41 42 43 44 45 46 47 48 49 50
  void
  state_product::destroy() const
  {
    if (--count_)
      return;
    fixed_size_pool* p = pool_;
    this->~state_product();
    p->deallocate(this);
  }

Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
51
  int
52
  state_product::compare(const state* other) const
53
  {
54
    const state_product* o = down_cast<const state_product*>(other);
55 56 57 58 59 60 61
    assert(o);
    int res = left_->compare(o->left());
    if (res != 0)
      return res;
    return right_->compare(o->right());
  }

62 63 64
  size_t
  state_product::hash() const
  {
65 66
    // We assume that size_t is 32-bit wide.
    return wang32_hash(left_->hash()) ^ wang32_hash(right_->hash());
67 68
  }

69 70
  state_product*
  state_product::clone() const
71
  {
72 73
    ++count_;
    return const_cast<state_product*>(this);
74 75
  }

76
  ////////////////////////////////////////////////////////////
77
  // twa_succ_iterator_product
78

79
  namespace
80
  {
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
81

82
    class twa_succ_iterator_product_common: public twa_succ_iterator
83 84
    {
    public:
85 86
      twa_succ_iterator_product_common(twa_succ_iterator* left,
					twa_succ_iterator* right,
87
					const twa_product* prod,
88
					fixed_size_pool* pool)
89
	: left_(left), right_(right), prod_(prod), pool_(pool)
90 91
      {
      }
92

93 94
      void recycle(const const_twa_ptr& l, twa_succ_iterator* left,
		   const_twa_ptr r, twa_succ_iterator* right)
95 96 97 98 99 100 101
      {
	l->release_iter(left_);
	left_ = left;
	r->release_iter(right_);
	right_ = right;
      }

102
      virtual ~twa_succ_iterator_product_common()
103
      {
104 105
	delete left_;
	delete right_;
106 107
      }

108
      virtual bool next_non_false_() = 0;
109

110
      bool first()
111
      {
112
	if (!right_)
113
	  return false;
114

115 116 117 118
	// If one of the two successor sets is empty initially, we
	// reset right_, so that done() can detect this situation
	// easily.  (We choose to reset right_ because this variable
	// is already used by done().)
119
	if (!(left_->first() && right_->first()))
120
	  {
121 122
	    delete right_;
	    right_ = 0;
123
	    return false;
124
	  }
125
	return next_non_false_();
126 127 128 129 130 131 132 133 134
      }

      bool done() const
      {
	return !right_ || right_->done();
      }

      state_product* current_state() const
      {
135 136 137
	return new(pool_->allocate()) state_product(left_->current_state(),
						    right_->current_state(),
						    pool_);
138 139 140
      }

    protected:
141 142
      twa_succ_iterator* left_;
      twa_succ_iterator* right_;
143
      const twa_product* prod_;
144
      fixed_size_pool* pool_;
145
      friend class spot::twa_product;
146 147 148 149
    };


    /// \brief Iterate over the successors of a product computed on the fly.
150
    class twa_succ_iterator_product: public twa_succ_iterator_product_common
151 152
    {
    public:
153 154
      twa_succ_iterator_product(twa_succ_iterator* left,
				 twa_succ_iterator* right,
155
				 const twa_product* prod,
156
				 fixed_size_pool* pool)
157
	: twa_succ_iterator_product_common(left, right, prod, pool)
158 159 160
      {
      }

161
      virtual ~twa_succ_iterator_product()
162 163 164
      {
      }

165
      bool step_()
166
      {
167 168 169 170
	if (left_->next())
	  return true;
	left_->first();
	return right_->next();
171 172
      }

173
      bool next_non_false_()
174
      {
175 176
	assert(!done());
	do
177 178 179 180 181 182 183 184
	  {
	    bdd l = left_->current_condition();
	    bdd r = right_->current_condition();
	    bdd current_cond = l & r;

	    if (current_cond != bddfalse)
	      {
		current_cond_ = current_cond;
185
		return true;
186 187
	      }
	  }
188 189
	while (step_());
	return false;
190 191
      }

192
      bool next()
193
      {
194 195 196
	if (step_())
	  return next_non_false_();
	return false;
197 198
      }

199
      bdd current_condition() const
200
      {
201
	return current_cond_;
202
      }
203

204
      acc_cond::mark_t current_acceptance_conditions() const
205
      {
206 207 208 209 210 211
	return
	  prod_->acc().join(prod_->left_acc(),
			    left_->current_acceptance_conditions(),
			    prod_->right_acc(),
			    right_->current_acceptance_conditions());
       }
212

213 214 215 216 217 218
    protected:
      bdd current_cond_;
    };

    /// Iterate over the successors of a product computed on the fly.
    /// This one assumes that LEFT is an iterator over a Kripke structure
219 220
    class twa_succ_iterator_product_kripke:
      public twa_succ_iterator_product_common
221 222
    {
    public:
223 224
      twa_succ_iterator_product_kripke(twa_succ_iterator* left,
					twa_succ_iterator* right,
225
					const twa_product* prod,
226
					fixed_size_pool* pool)
227
	: twa_succ_iterator_product_common(left, right, prod, pool)
228 229
      {
      }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
230

231
      virtual ~twa_succ_iterator_product_kripke()
232 233
      {
      }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
234

235
      bool next_non_false_()
236 237 238 239
      {
	// All the transitions of left_ iterator have the
	// same label, because it is a Kripke structure.
	bdd l = left_->current_condition();
240 241
	assert(!right_->done());
	do
242 243 244 245 246 247 248
	  {
	    bdd r = right_->current_condition();
	    bdd current_cond = l & r;

	    if (current_cond != bddfalse)
	      {
		current_cond_ = current_cond;
249
		return true;
250 251
	      }
	  }
252 253
	while (right_->next());
	return false;
254
      }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
255

256
      bool next()
257
      {
258 259 260 261 262 263
	if (left_->next())
	  return true;
	left_->first();
	if (right_->next())
	  return next_non_false_();
	return false;
264
      }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
265

266 267 268 269 270
      bdd current_condition() const
      {
	return current_cond_;
      }

271
      acc_cond::mark_t current_acceptance_conditions() const
272 273 274 275 276 277 278 279 280
      {
	return right_->current_acceptance_conditions();
      }

    protected:
      bdd current_cond_;
    };

  } // anonymous
281 282

  ////////////////////////////////////////////////////////////
283
  // twa_product
284

285 286
  twa_product::twa_product(const const_twa_ptr& left,
			     const const_twa_ptr& right)
287
    : twa(left->get_dict()), left_(left), right_(right),
288
      pool_(sizeof(state_product))
289
  {
290
    assert(get_dict() == right_->get_dict());
291 292 293 294

    // If one of the side is a Kripke structure, it is easier to deal
    // with (we don't have to fix the acceptance conditions, and
    // computing the successors can be improved a bit).
295
    if (dynamic_cast<const kripke*>(left_.get()))
296 297 298
      {
	left_kripke_ = true;
      }
299
    else if (dynamic_cast<const kripke*>(right_.get()))
300 301 302 303 304 305 306 307 308
      {
	std::swap(left_, right_);
	left_kripke_ = true;
      }
    else
      {
	left_kripke_ = false;
      }

309 310 311
    auto d = get_dict();
    d->register_all_propositions_of(&left_, this);
    d->register_all_propositions_of(&right_, this);
312

313
    assert(acc_.num_sets() == 0);
314 315 316 317 318
    auto left_num = left->acc().num_sets();
    auto right_acc = right->get_acceptance();
    right_acc.shift_left(left_num);
    right_acc.append_and(left->get_acceptance());
    set_acceptance(left_num + right->acc().num_sets(), right_acc);
319 320
  }

321
  twa_product::~twa_product()
322
  {
323
    get_dict()->unregister_all_my_variables(this);
324 325 326 327 328 329 330
    // Prevent these states from being destroyed by ~tgba(): they
    // will be destroyed before when the pool is destructed.
    if (last_support_conditions_input_)
      {
	last_support_conditions_input_->destroy();
	last_support_conditions_input_ = 0;
      }
331 332
  }

Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
333
  state*
334
  twa_product::get_init_state() const
335
  {
336 337 338
    fixed_size_pool* p = const_cast<fixed_size_pool*>(&pool_);
    return new(p->allocate()) state_product(left_->get_init_state(),
					    right_->get_init_state(), p);
339 340
  }

341
  twa_succ_iterator*
342
  twa_product::succ_iter(const state* state) const
343
  {
344
    const state_product* s = down_cast<const state_product*>(state);
345
    assert(s);
346 347
    twa_succ_iterator* li = left_->succ_iter(s->left());
    twa_succ_iterator* ri = right_->succ_iter(s->right());
348

349 350
    if (iter_cache_)
      {
351 352
	twa_succ_iterator_product_common* it =
	  down_cast<twa_succ_iterator_product_common*>(iter_cache_);
353 354 355 356 357
	it->recycle(left_, li, right_, ri);
	iter_cache_ = nullptr;
	return it;
      }

358
    fixed_size_pool* p = const_cast<fixed_size_pool*>(&pool_);
359
    if (left_kripke_)
360
      return new twa_succ_iterator_product_kripke(li, ri, this, p);
361
    else
362
      return new twa_succ_iterator_product(li, ri, this, p);
363 364
  }

365
  bdd
366
  twa_product::compute_support_conditions(const state* in) const
367
  {
368
    const state_product* s = down_cast<const state_product*>(in);
369 370 371 372 373 374
    assert(s);
    bdd lsc = left_->support_conditions(s->left());
    bdd rsc = right_->support_conditions(s->right());
    return lsc & rsc;
  }

375
  const acc_cond& twa_product::left_acc() const
376
  {
377 378 379
    return left_->acc();
  }

380
  const acc_cond& twa_product::right_acc() const
381 382
  {
    return right_->acc();
383 384
  }

Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
385
  std::string
386
  twa_product::format_state(const state* state) const
387
  {
388
    const state_product* s = down_cast<const state_product*>(state);
389
    assert(s);
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
390 391
    return (left_->format_state(s->left())
	    + " * "
392 393
	    + right_->format_state(s->right()));
  }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
394

395
  state*
396
  twa_product::project_state(const state* s, const const_twa_ptr& t) const
397
  {
398
    const state_product* s2 = down_cast<const state_product*>(s);
399
    assert(s2);
400
    if (t.get() == this)
401 402 403 404 405 406 407
      return s2->clone();
    state* res = left_->project_state(s2->left(), t);
    if (res)
      return res;
    return right_->project_state(s2->right(), t);
  }

408
  std::string
409
  twa_product::transition_annotation(const twa_succ_iterator* t) const
410
  {
411 412
    const twa_succ_iterator_product_common* i =
      down_cast<const twa_succ_iterator_product_common*>(t);
413 414 415 416 417 418 419 420 421 422
    assert(i);
    std::string left = left_->transition_annotation(i->left_);
    std::string right = right_->transition_annotation(i->right_);
    if (left == "")
      return right;
    if (right == "")
      return left;
    return "<" + left + ", " + right + ">";
  }

423
  //////////////////////////////////////////////////////////////////////
424
  // twa_product_init
425

426 427
  twa_product_init::twa_product_init(const const_twa_ptr& left,
				       const const_twa_ptr& right,
428 429
				       const state* left_init,
				       const state* right_init)
430
    : twa_product(left, right),
431 432
      left_init_(left_init), right_init_(right_init)
  {
433 434
    if (left_ != left)
      std::swap(left_init_, right_init_);
435 436 437
  }

  state*
438
  twa_product_init::get_init_state() const
439
  {
440 441 442
    fixed_size_pool* p = const_cast<fixed_size_pool*>(&pool_);
    return new(p->allocate()) state_product(left_init_->clone(),
					    right_init_->clone(), p);
443 444
  }

445
}