taatgba.cc 8.81 KB
Newer Older
1
// -*- coding: utf-8 -*-
2 3
// Copyright (C) 2009, 2010, 2011, 2012, 2013, 2014, 2015 Laboratoire
// de Recherche et Développement de l'Epita (LRDE)
4 5 6 7 8
//
// 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
9
// the Free Software Foundation; either version 3 of the License, or
10 11 12 13 14 15 16 17
// (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
18
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
19

Damien Lefortier's avatar
Damien Lefortier committed
20
#include <map>
21
#include <algorithm>
22
#include <iterator>
23 24
#include <iostream>
#include "tgba/formula2bdd.hh"
25
#include "ltlvisit/tostring.hh"
26
#include "ltlvisit/clone.hh"
27
#include "taatgba.hh"
28 29 30

namespace spot
{
31 32 33
  /*--------.
  | taa_tgba |
  `--------*/
34

35
  taa_tgba::taa_tgba(const bdd_dict_ptr& dict)
36
    : twa(dict),
37 38 39 40
      init_(0), state_set_vec_()
  {
  }

41
  taa_tgba::~taa_tgba()
42 43 44 45
  {
    ss_vec::iterator j;
    for (j = state_set_vec_.begin(); j != state_set_vec_.end(); ++j)
      delete *j;
46
    get_dict()->unregister_all_my_variables(this);
47 48 49
  }

  void
50
  taa_tgba::add_condition(transition* t, const ltl::formula* f)
51
  {
52
    t->condition &= formula_to_bdd(f, get_dict(), this);
53
    f->destroy();
54 55 56
  }

  state*
57
  taa_tgba::get_init_state() const
58
  {
59
    assert(init_);
60
    return new spot::set_state(init_);
61 62 63
  }

  tgba_succ_iterator*
64
  taa_tgba::succ_iter(const spot::state* state) const
65
  {
66
    const spot::set_state* s = down_cast<const spot::set_state*>(state);
67
    assert(s);
68
    return new taa_succ_iterator(s->get_state(), acc_);
69 70 71
  }

  bdd
72
  taa_tgba::compute_support_conditions(const spot::state* s) const
73
  {
74
    const spot::set_state* se = down_cast<const spot::set_state*>(s);
75 76 77 78
    assert(se);
    const state_set* ss = se->get_state();

    bdd res = bddtrue;
79 80
    taa_tgba::state_set::const_iterator i;
    taa_tgba::state::const_iterator j;
81 82 83 84 85 86 87 88 89 90
    for (i = ss->begin(); i != ss->end(); ++i)
      for (j = (*i)->begin(); j != (*i)->end(); ++j)
	res |= (*j)->condition;
    return res;
  }

  /*----------.
  | state_set |
  `----------*/

91
  const taa_tgba::state_set*
92
  set_state::get_state() const
93 94 95 96 97
  {
    return s_;
  }

  int
98
  set_state::compare(const spot::state* other) const
99
  {
100
    const set_state* o = down_cast<const set_state*>(other);
101 102
    assert(o);

103 104
    const taa_tgba::state_set* s1 = get_state();
    const taa_tgba::state_set* s2 = o->get_state();
105

106 107
    if (s1->size() != s2->size())
      return s1->size() - s2->size();
108

109 110
    taa_tgba::state_set::const_iterator it1 = s1->begin();
    taa_tgba::state_set::const_iterator it2 = s2->begin();
111
    while (it2 != s2->end())
112 113 114 115 116
    {
      int i = *it1++ - *it2++;
      if (i != 0)
	return i;
    }
117
    return 0;
118 119 120
  }

  size_t
121
  set_state::hash() const
122
  {
123
    size_t res = 0;
124
    taa_tgba::state_set::const_iterator it = s_->begin();
125 126
    while (it != s_->end())
    {
127 128
      res ^= reinterpret_cast<const char*>(*it++) - static_cast<char*>(0);
      res = wang32_hash(res);
129 130 131 132
    }
    return res;
  }

133 134
  set_state*
  set_state::clone() const
135
  {
136
    if (delete_me_ && s_)
137
      return new spot::set_state(new taa_tgba::state_set(*s_), true);
138
    else
139
      return new spot::set_state(s_, false);
140 141 142 143 144 145
  }

  /*--------------.
  | taa_succ_iter |
  `--------------*/

146
  taa_succ_iterator::taa_succ_iterator(const taa_tgba::state_set* s,
147 148
                                       const acc_cond& acc)
    : seen_(), acc_(acc)
149
  {
Damien Lefortier's avatar
Damien Lefortier committed
150
    if (s->empty())
151
    {
152
      taa_tgba::transition* t = new taa_tgba::transition;
Damien Lefortier's avatar
Damien Lefortier committed
153
      t->condition = bddtrue;
154
      t->acceptance_conditions = 0U;
155
      t->dst = new taa_tgba::state_set;
Damien Lefortier's avatar
Damien Lefortier committed
156 157
      succ_.push_back(t);
      return;
158 159
    }

160
    bounds_t bounds;
161 162
    for (auto& i: *s)
      bounds.emplace_back(i->begin(), i->end());
163 164 165 166 167 168 169

    /// Sorting might make the cartesian product faster by not
    /// exploring all possibilities.
    std::sort(bounds.begin(), bounds.end(), distance_sort());

    std::vector<iterator> pos;
    pos.reserve(bounds.size());
170 171
    for (auto i: bounds)
      pos.push_back(i.first);
172

Damien Lefortier's avatar
Damien Lefortier committed
173
    while (pos[0] != bounds[0].second)
174
    {
175
      taa_tgba::transition* t = new taa_tgba::transition;
Damien Lefortier's avatar
Damien Lefortier committed
176
      t->condition = bddtrue;
177
      t->acceptance_conditions = 0U;
178
      taa_tgba::state_set* ss = new taa_tgba::state_set;
179 180 181

      unsigned p;
      for (p = 0; p < pos.size() && t->condition != bddfalse; ++p)
Damien Lefortier's avatar
Damien Lefortier committed
182
      {
183
	taa_tgba::state_set::const_iterator j;
184 185
	for (j = (*pos[p])->dst->begin(); j != (*pos[p])->dst->end(); ++j)
	  if ((*j)->size() > 0) // Remove sink states.
Damien Lefortier's avatar
Damien Lefortier committed
186 187 188
	    ss->insert(*j);

	// Fill the new transition.
189 190
	t->condition &= (*pos[p])->condition;
	t->acceptance_conditions |= (*pos[p])->acceptance_conditions;
191
      } // If p != pos.size() we have found a contradiction
192
      assert(p > 0);
193 194
      t->dst = ss;
      // Boxing to be able to insert ss in the map directly.
195
      spot::set_state* b = new spot::set_state(ss);
196 197 198

      // If no contradiction, then look for another transition to
      // merge with the new one.
199
      seen_map::iterator i = seen_.end(); // Initialize to silent a g++ warning.
200
      std::vector<taa_tgba::transition*>::iterator j;
201
      if (t->condition != bddfalse)
202
      {
203 204 205
	i = seen_.find(b);
	if (i != seen_.end())
	  for (j = i->second.begin(); j != i->second.end(); ++j)
206
	  {
207 208 209 210 211 212 213 214 215 216 217 218 219
	    taa_tgba::transition* current = *j;
	    if (*current->dst == *t->dst
		&& current->condition == t->condition)
	    {
	      current->acceptance_conditions &= t->acceptance_conditions;
	      break;
	    }
	    if (*current->dst == *t->dst
		&& current->acceptance_conditions == t->acceptance_conditions)
	    {
	      current->condition |= t->condition;
	      break;
	    }
220 221
	}
      }
222
      // Mark the new transition as seen and keep it if we have not
223 224 225 226
      // found any contradiction and no other transition to merge
      // with, or delete it otherwise.
      if (t->condition != bddfalse
	  && (i == seen_.end() || j == i->second.end()))
Damien Lefortier's avatar
Damien Lefortier committed
227
      {
228
	seen_[b].push_back(t);
229 230
	if (i != seen_.end())
	  delete b;
Damien Lefortier's avatar
Damien Lefortier committed
231 232 233 234 235 236
	succ_.push_back(t);
      }
      else
      {
	delete t->dst;
	delete t;
237
	delete b;
Damien Lefortier's avatar
Damien Lefortier committed
238 239 240 241
      }

      for (int i = pos.size() - 1; i >= 0; --i)
      {
242 243 244
	if ((i < int(p))
	    && (std::distance(pos[i], bounds[i].second) > 1
		|| (i == 0 && std::distance(pos[i], bounds[i].second) == 1)))
Damien Lefortier's avatar
Damien Lefortier committed
245 246 247 248 249 250 251
	{
	  ++pos[i];
	  break;
	}
	else
	  pos[i] = bounds[i].first;
      }
252
    }
Damien Lefortier's avatar
Damien Lefortier committed
253 254 255 256
  }

  taa_succ_iterator::~taa_succ_iterator()
  {
257 258
    for (seen_map::iterator i = seen_.begin(); i != seen_.end();)
    {
259
      // Advance the iterator before deleting the state set.
260
      const spot::set_state* s = i->first;
261 262 263
      ++i;
      delete s;
    }
264 265 266 267 268
    for (unsigned i = 0; i < succ_.size(); ++i)
    {
      delete succ_[i]->dst;
      delete succ_[i];
    }
Damien Lefortier's avatar
Damien Lefortier committed
269 270
  }

271
  bool
Damien Lefortier's avatar
Damien Lefortier committed
272 273 274
  taa_succ_iterator::first()
  {
    i_ = succ_.begin();
275
    return i_ != succ_.end();
Damien Lefortier's avatar
Damien Lefortier committed
276 277
  }

278
  bool
Damien Lefortier's avatar
Damien Lefortier committed
279 280 281
  taa_succ_iterator::next()
  {
    ++i_;
282
    return i_ != succ_.end();
283 284 285 286 287
  }

  bool
  taa_succ_iterator::done() const
  {
Damien Lefortier's avatar
Damien Lefortier committed
288
    return i_ == succ_.end();
289 290
  }

291
  spot::set_state*
292 293 294
  taa_succ_iterator::current_state() const
  {
    assert(!done());
295
    return new spot::set_state(new taa_tgba::state_set(*(*i_)->dst), true);
296 297 298 299 300 301
  }

  bdd
  taa_succ_iterator::current_condition() const
  {
    assert(!done());
Damien Lefortier's avatar
Damien Lefortier committed
302
    return (*i_)->condition;
303 304
  }

305
  acc_cond::mark_t
306 307 308
  taa_succ_iterator::current_acceptance_conditions() const
  {
    assert(!done());
309
    return acc_.comp((*i_)->acceptance_conditions);
310
  }
311 312 313 314 315

  /*----------------.
  | taa_tgba_string |
  `----------------*/

316 317 318 319 320 321 322 323 324 325 326 327
  taa_tgba_string::~taa_tgba_string()
  {
    ns_map::iterator i;
    for (i = name_state_map_.begin(); i != name_state_map_.end(); ++i)
    {
      taa_tgba::state::iterator i2;
      for (i2 = i->second->begin(); i2 != i->second->end(); ++i2)
	delete *i2;
      delete i->second;
    }
  }

328
  std::string
329 330 331 332 333 334 335
  taa_tgba_string::label_to_string(const label_t& label) const
  {
    return label;
  }

  std::string
  taa_tgba_string::clone_if(const label_t& label) const
336 337 338 339 340 341 342 343
  {
    return label;
  }

  /*-----------------.
  | taa_tgba_formula |
  `-----------------*/

344 345 346
  taa_tgba_formula::~taa_tgba_formula()
  {
    ns_map::iterator i;
347
    for (i = name_state_map_.begin(); i != name_state_map_.end();)
348 349 350 351
    {
      taa_tgba::state::iterator i2;
      for (i2 = i->second->begin(); i2 != i->second->end(); ++i2)
	delete *i2;
352
      // Advance the iterator before destroying the formula.
353 354 355 356 357
      const ltl::formula* s = i->first;
      delete i->second;
      ++i;
      s->destroy();
    }
358 359
  }

360
  std::string
361
  taa_tgba_formula::label_to_string(const label_t& label) const
362 363 364
  {
    return ltl::to_string(label);
  }
365

366
  const ltl::formula*
367 368 369 370
  taa_tgba_formula::clone_if(const label_t& label) const
  {
    return label->clone();
  }
371
}