taatgba.cc 9.41 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Copyright (C) 2009 Laboratoire d'Informatique de Paris
// 6 (LIP6), département Systèmes Répartis Coopératifs (SRC),
// Université Pierre et Marie Curie.
//
// 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
// the Free Software Foundation; either version 2 of the License, or
// (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
// along with Spot; see the file COPYING.  If not, write to the Free
// Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
// 02111-1307, USA.

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

namespace spot
{
34
35
36
  /*--------.
  | taa_tgba |
  `--------*/
37

38
  taa_tgba::taa_tgba(bdd_dict* dict)
39
    : dict_(dict),
40
41
42
43
44
45
46
      all_acceptance_conditions_(bddfalse),
      all_acceptance_conditions_computed_(false),
      neg_acceptance_conditions_(bddtrue),
      init_(0), state_set_vec_()
  {
  }

47
  taa_tgba::~taa_tgba()
48
49
50
51
52
53
54
55
  {
    ss_vec::iterator j;
    for (j = state_set_vec_.begin(); j != state_set_vec_.end(); ++j)
      delete *j;
    dict_->unregister_all_my_variables(this);
  }

  void
56
  taa_tgba::add_condition(transition* t, const ltl::formula* f)
57
58
  {
    t->condition &= formula_to_bdd(f, dict_, this);
59
    f->destroy();
60
61
62
  }

  state*
63
  taa_tgba::get_init_state() const
64
  {
65
    assert(init_);
66
    return new spot::state_set(init_);
67
68
69
  }

  tgba_succ_iterator*
70
71
72
  taa_tgba::succ_iter(const spot::state* state,
                     const spot::state* global_state,
                     const tgba* global_automaton) const
73
74
75
76
77
  {
    const spot::state_set* s = dynamic_cast<const spot::state_set*>(state);
    assert(s);
    (void) global_state;
    (void) global_automaton;
78
    return new taa_succ_iterator(s->get_state(), all_acceptance_conditions());
79
80
81
  }

  bdd_dict*
82
  taa_tgba::get_dict() const
83
84
85
86
87
  {
    return dict_;
  }

  bdd
88
  taa_tgba::all_acceptance_conditions() const
89
90
91
92
93
94
95
96
97
98
99
  {
    if (!all_acceptance_conditions_computed_)
    {
      all_acceptance_conditions_ =
	compute_all_acceptance_conditions(neg_acceptance_conditions_);
      all_acceptance_conditions_computed_ = true;
    }
    return all_acceptance_conditions_;
  }

  bdd
100
  taa_tgba::neg_acceptance_conditions() const
101
102
103
104
105
  {
    return neg_acceptance_conditions_;
  }

  bdd
106
  taa_tgba::compute_support_conditions(const spot::state* s) const
107
108
109
110
111
112
  {
    const spot::state_set* se = dynamic_cast<const spot::state_set*>(s);
    assert(se);
    const state_set* ss = se->get_state();

    bdd res = bddtrue;
113
114
    taa_tgba::state_set::const_iterator i;
    taa_tgba::state::const_iterator j;
115
116
117
118
119
120
121
    for (i = ss->begin(); i != ss->end(); ++i)
      for (j = (*i)->begin(); j != (*i)->end(); ++j)
	res |= (*j)->condition;
    return res;
  }

  bdd
122
  taa_tgba::compute_support_variables(const spot::state* s) const
123
124
125
126
127
128
  {
    const spot::state_set* se = dynamic_cast<const spot::state_set*>(s);
    assert(se);
    const state_set* ss = se->get_state();

    bdd res = bddtrue;
129
130
    taa_tgba::state_set::const_iterator i;
    taa_tgba::state::const_iterator j;
131
132
133
134
135
136
137
138
139
140
    for (i = ss->begin(); i != ss->end(); ++i)
      for (j = (*i)->begin(); j != (*i)->end(); ++j)
	res &= bdd_support((*j)->condition);
    return res;
  }

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

141
  const taa_tgba::state_set*
142
143
144
145
146
147
148
149
150
151
152
  state_set::get_state() const
  {
    return s_;
  }

  int
  state_set::compare(const spot::state* other) const
  {
    const state_set* o = dynamic_cast<const state_set*>(other);
    assert(o);

153
154
    const taa_tgba::state_set* s1 = get_state();
    const taa_tgba::state_set* s2 = o->get_state();
155

156
157
    if (s1->size() != s2->size())
      return s1->size() - s2->size();
158

159
160
    taa_tgba::state_set::const_iterator it1 = s1->begin();
    taa_tgba::state_set::const_iterator it2 = s2->begin();
161
    while (it2 != s2->end())
162
163
164
165
166
    {
      int i = *it1++ - *it2++;
      if (i != 0)
	return i;
    }
167
    return 0;
168
169
170
171
172
  }

  size_t
  state_set::hash() const
  {
173
    size_t res = 0;
174
    taa_tgba::state_set::const_iterator it = s_->begin();
175
176
    while (it != s_->end())
    {
177
178
      res ^= reinterpret_cast<const char*>(*it++) - static_cast<char*>(0);
      res = wang32_hash(res);
179
180
181
182
183
184
185
    }
    return res;
  }

  state_set*
  state_set::clone() const
  {
186
    if (delete_me_ && s_)
187
      return new spot::state_set(new taa_tgba::state_set(*s_), true);
188
189
    else
      return new spot::state_set(s_, false);
190
191
192
193
194
195
  }

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

196
197
  taa_succ_iterator::taa_succ_iterator(const taa_tgba::state_set* s,
                                       bdd all_acc)
Damien Lefortier's avatar
Damien Lefortier committed
198
    : all_acceptance_conditions_(all_acc), seen_()
199
  {
Damien Lefortier's avatar
Damien Lefortier committed
200
    if (s->empty())
201
    {
202
      taa_tgba::transition* t = new taa_tgba::transition;
Damien Lefortier's avatar
Damien Lefortier committed
203
204
      t->condition = bddtrue;
      t->acceptance_conditions = bddfalse;
205
      t->dst = new taa_tgba::state_set;
Damien Lefortier's avatar
Damien Lefortier committed
206
207
      succ_.push_back(t);
      return;
208
209
    }

210
    bounds_t bounds;
211
    for (taa_tgba::state_set::const_iterator i = s->begin(); i != s->end(); ++i)
Damien Lefortier's avatar
Damien Lefortier committed
212
      bounds.push_back(std::make_pair((*i)->begin(), (*i)->end()));
213
214
215
216
217
218
219
220
221

    /// 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());
    for (bounds_t::const_iterator i = bounds.begin(); i != bounds.end(); ++i)
      pos.push_back(i->first);
222

Damien Lefortier's avatar
Damien Lefortier committed
223
    while (pos[0] != bounds[0].second)
224
    {
225
      taa_tgba::transition* t = new taa_tgba::transition;
Damien Lefortier's avatar
Damien Lefortier committed
226
227
      t->condition = bddtrue;
      t->acceptance_conditions = bddfalse;
228
      taa_tgba::state_set* ss = new taa_tgba::state_set;
229
230
231

      unsigned p;
      for (p = 0; p < pos.size() && t->condition != bddfalse; ++p)
Damien Lefortier's avatar
Damien Lefortier committed
232
      {
233
	taa_tgba::state_set::const_iterator j;
234
235
	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
236
237
238
	    ss->insert(*j);

	// Fill the new transition.
239
240
	t->condition &= (*pos[p])->condition;
	t->acceptance_conditions |= (*pos[p])->acceptance_conditions;
241
      } // If p != pos.size() we have found a contradiction
242
      assert(p > 0);
243
244
245
      t->dst = ss;
      // Boxing to be able to insert ss in the map directly.
      spot::state_set* b = new spot::state_set(ss);
246
247
248

      // If no contradiction, then look for another transition to
      // merge with the new one.
Damien Lefortier's avatar
Damien Lefortier committed
249
      seen_map::iterator i;
250
      if (t->condition != bddfalse)
251
      {
252
	for (i = seen_.find(b); i != seen_.end(); ++i)
253
	{
254
255
256
257
258
259
260
261
262
263
264
265
	  if (*i->second->dst == *t->dst
	      && i->second->condition == t->condition)
	  {
	    i->second->acceptance_conditions &= t->acceptance_conditions;
	    break;
	  }
	  if (*i->second->dst == *t->dst
	      && i->second->acceptance_conditions == t->acceptance_conditions)
	  {
	    i->second->condition |= t->condition;
	    break;
	  }
266
267
	}
      }
268
269
270
271
      // Mark the new transition as seen and keep it if we have not
      // found any contraction and no other transition to merge with,
      // or delete it otherwise.
      if (t->condition != bddfalse && i == seen_.end())
Damien Lefortier's avatar
Damien Lefortier committed
272
      {
273
	seen_.insert(std::make_pair(b, t));
Damien Lefortier's avatar
Damien Lefortier committed
274
275
276
277
278
279
	succ_.push_back(t);
      }
      else
      {
	delete t->dst;
	delete t;
280
	delete b;
Damien Lefortier's avatar
Damien Lefortier committed
281
282
283
284
      }

      for (int i = pos.size() - 1; i >= 0; --i)
      {
285
286
287
	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
288
289
290
291
292
293
294
	{
	  ++pos[i];
	  break;
	}
	else
	  pos[i] = bounds[i].first;
      }
295
    }
Damien Lefortier's avatar
Damien Lefortier committed
296
297
298
299
300
  }

  taa_succ_iterator::~taa_succ_iterator()
  {
    for (unsigned i = 0; i < succ_.size(); ++i)
301
302
    {
      delete succ_[i]->dst;
Damien Lefortier's avatar
Damien Lefortier committed
303
      delete succ_[i];
304
305
306
    }
    for (seen_map::iterator i = seen_.begin(); i != seen_.end(); ++i)
      delete i->first;
Damien Lefortier's avatar
Damien Lefortier committed
307
308
309
310
311
312
313
314
315
316
317
318
  }

  void
  taa_succ_iterator::first()
  {
    i_ = succ_.begin();
  }

  void
  taa_succ_iterator::next()
  {
    ++i_;
319
320
321
322
323
  }

  bool
  taa_succ_iterator::done() const
  {
Damien Lefortier's avatar
Damien Lefortier committed
324
    return i_ == succ_.end();
325
326
327
328
329
330
  }

  spot::state_set*
  taa_succ_iterator::current_state() const
  {
    assert(!done());
331
    return new spot::state_set(new taa_tgba::state_set(*(*i_)->dst), true);
332
333
334
335
336
337
  }

  bdd
  taa_succ_iterator::current_condition() const
  {
    assert(!done());
Damien Lefortier's avatar
Damien Lefortier committed
338
    return (*i_)->condition;
339
340
341
342
343
344
  }

  bdd
  taa_succ_iterator::current_acceptance_conditions() const
  {
    assert(!done());
Damien Lefortier's avatar
Damien Lefortier committed
345
346
    return all_acceptance_conditions_ -
      ((*i_)->acceptance_conditions & all_acceptance_conditions_);
347
  }
348
349
350
351
352
353

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

  std::string
354
355
356
357
358
359
360
  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
361
362
363
364
365
366
367
368
  {
    return label;
  }

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

369
370
371
372
373
374
375
  taa_tgba_formula::~taa_tgba_formula()
  {
    ns_map::iterator i;
    for (i = name_state_map_.begin(); i != name_state_map_.end(); ++i)
      i->first->destroy();
  }

376
  std::string
377
  taa_tgba_formula::label_to_string(const label_t& label) const
378
379
380
  {
    return ltl::to_string(label);
  }
381
382
383
384
385
386

  ltl::formula*
  taa_tgba_formula::clone_if(const label_t& label) const
  {
    return label->clone();
  }
387
}