twaproduct.cc 11.2 KB
Newer Older
1
// -*- coding: utf-8 -*-
2 3
// Copyright (C) 2009, 2011-2012, 2014-2018 Laboratoire de Recherche
// et 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 "config.h"
24
#include <spot/twa/twaproduct.hh>
25
#include <string>
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
26
#include <cassert>
27 28
#include <spot/misc/hashfunc.hh>
#include <spot/kripke/kripke.hh>
29 30 31 32 33

namespace spot
{

  ////////////////////////////////////////////////////////////
34
  // state_product
35

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

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

Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
52
  int
53
  state_product::compare(const state* other) const
54
  {
55
    const state_product* o = down_cast<const state_product*>(other);
56 57 58 59 60 61
    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
      twa_succ_iterator_product_common(twa_succ_iterator* left,
86 87 88
                                       twa_succ_iterator* right,
                                       const twa_product* prod,
                                       fixed_size_pool<pool_type::Safe>* pool)
89
        : left_(left), right_(right), prod_(prod), pool_(pool)
90 91
      {
      }
92

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

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() override
111
      {
112 113 114 115 116 117 118 119 120 121 122 123 124 125
        if (!right_)
          return false;

        // 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().)
        if (!(left_->first() && right_->first()))
          {
            delete right_;
            right_ = nullptr;
            return false;
          }
        return next_non_false_();
126 127
      }

128
      bool done() const override
129
      {
130
        return !right_ || right_->done();
131 132
      }

133
      const state_product* dst() const override
134
      {
135 136 137
        return new(pool_->allocate()) state_product(left_->dst(),
                                                    right_->dst(),
                                                    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_type::Safe>* pool_;
145
      friend class spot::twa_product;
146 147 148 149
    };


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

162
      virtual ~twa_succ_iterator_product()
163 164 165
      {
      }

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

174
      bool next_non_false_() override
175
      {
176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
        assert(!done());
        do
          {
            bdd l = left_->cond();
            bdd r = right_->cond();
            bdd current_cond = l & r;

            if (current_cond != bddfalse)
              {
                current_cond_ = current_cond;
                return true;
              }
          }
        while (step_());
        return false;
191 192
      }

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

200
      bdd cond() const override
201
      {
202
        return current_cond_;
203
      }
204

205
      acc_cond::mark_t acc() const override
206
      {
207
        return left_->acc() | (right_->acc() << prod_->left_acc().num_sets());
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
208
      }
209

210 211 212 213 214 215
    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
216
    class twa_succ_iterator_product_kripke final:
217
      public twa_succ_iterator_product_common
218 219
    {
    public:
220
      twa_succ_iterator_product_kripke(twa_succ_iterator* left,
221 222 223
                                       twa_succ_iterator* right,
                                       const twa_product* prod,
                                       fixed_size_pool<pool_type::Safe>* pool)
224
        : twa_succ_iterator_product_common(left, right, prod, pool)
225 226
      {
      }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
227

228
      virtual ~twa_succ_iterator_product_kripke()
229 230
      {
      }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
231

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

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

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

263
      bdd cond() const override
264
      {
265
        return current_cond_;
266 267
      }

268
      acc_cond::mark_t acc() const override
269
      {
270
        return right_->acc();
271 272 273 274 275 276 277
      }

    protected:
      bdd current_cond_;
    };

  } // anonymous
278 279

  ////////////////////////////////////////////////////////////
280
  // twa_product
281

282
  twa_product::twa_product(const const_twa_ptr& left,
Clément Gillard's avatar
Clément Gillard committed
283
                           const const_twa_ptr& right)
284
    : twa(left->get_dict()), left_(left), right_(right),
285
      pool_(sizeof(state_product))
286
  {
287 288
    if (left->get_dict() != right->get_dict())
      throw std::runtime_error("twa_product: left and right automata should "
289
                               "share their bdd_dict");
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
        left_kripke_ = true;
298
      }
299
    else if (dynamic_cast<const kripke*>(right_.get()))
300
      {
301 302
        std::swap(left_, right_);
        left_kripke_ = true;
303 304 305
      }
    else
      {
306
        left_kripke_ = false;
307 308
      }

309 310
    copy_ap_of(left_);
    copy_ap_of(right_);
311

312 313
    assert(num_sets() == 0);
    auto left_num = left->num_sets();
314 315
    auto right_acc = right->get_acceptance() << left_num;
    right_acc &= left->get_acceptance();
316
    set_acceptance(left_num + right->num_sets(), right_acc);
317 318
  }

319
  twa_product::~twa_product()
320
  {
321 322 323 324
    // Make sure we delete the iterator cache before erasing the two
    // automata (by reference counting).
    delete iter_cache_;
    iter_cache_ = nullptr;
325 326
  }

327
  const state*
328
  twa_product::get_init_state() const
329
  {
330 331
    fixed_size_pool<pool_type::Safe>* p =
      const_cast<fixed_size_pool<pool_type::Safe>*>(&pool_);
332
    return new(p->allocate()) state_product(left_->get_init_state(),
333
                                            right_->get_init_state(), p);
334 335
  }

336
  twa_succ_iterator*
337
  twa_product::succ_iter(const state* state) const
338
  {
339
    const state_product* s = down_cast<const state_product*>(state);
340 341
    twa_succ_iterator* li = left_->succ_iter(s->left());
    twa_succ_iterator* ri = right_->succ_iter(s->right());
342

343 344
    if (iter_cache_)
      {
345 346 347 348 349
        twa_succ_iterator_product_common* it =
          down_cast<twa_succ_iterator_product_common*>(iter_cache_);
        it->recycle(left_, li, right_, ri);
        iter_cache_ = nullptr;
        return it;
350 351
      }

352 353
    fixed_size_pool<pool_type::Safe>* p =
      const_cast<fixed_size_pool<pool_type::Safe>*>(&pool_);
354
    if (left_kripke_)
355
      return new twa_succ_iterator_product_kripke(li, ri, this, p);
356
    else
357
      return new twa_succ_iterator_product(li, ri, this, p);
358 359
  }

360
  const acc_cond& twa_product::left_acc() const
361
  {
362 363 364
    return left_->acc();
  }

365
  const acc_cond& twa_product::right_acc() const
366 367
  {
    return right_->acc();
368 369
  }

Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
370
  std::string
371
  twa_product::format_state(const state* state) const
372
  {
373
    const state_product* s = down_cast<const state_product*>(state);
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
374
    return (left_->format_state(s->left())
375 376
            + " * "
            + right_->format_state(s->right()));
377
  }
Alexandre Duret-Lutz's avatar
typo  
Alexandre Duret-Lutz committed
378

379
  state*
380
  twa_product::project_state(const state* s, const const_twa_ptr& t) const
381
  {
382
    const state_product* s2 = down_cast<const state_product*>(s);
383
    if (t.get() == this)
384 385 386 387 388 389 390
      return s2->clone();
    state* res = left_->project_state(s2->left(), t);
    if (res)
      return res;
    return right_->project_state(s2->right(), t);
  }

391
  //////////////////////////////////////////////////////////////////////
392
  // twa_product_init
393

394
  twa_product_init::twa_product_init(const const_twa_ptr& left,
395 396 397
                                       const const_twa_ptr& right,
                                       const state* left_init,
                                       const state* right_init)
398
    : twa_product(left, right),
399 400
      left_init_(left_init), right_init_(right_init)
  {
401 402
    if (left_ != left)
      std::swap(left_init_, right_init_);
403 404
  }

405
  const state*
406
  twa_product_init::get_init_state() const
407
  {
408 409
    fixed_size_pool<pool_type::Safe>* p =
      const_cast<fixed_size_pool<pool_type::Safe>*>(&pool_);
410
    return new(p->allocate()) state_product(left_init_->clone(),
411
                                            right_init_->clone(), p);
412 413
  }

414
}