tgbaexplicit.cc 9.31 KB
Newer Older
1
// Copyright (C) 2009, 2010, 2011 Laboratoire de Recherche et Dveloppement
Guillaume Sadegh's avatar
Guillaume Sadegh committed
2
3
// de l'Epita (LRDE).
// Copyright (C) 2003, 2004 Laboratoire d'Informatique de Paris 6 (LIP6),
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// dpartement Systmes Rpartis Coopratifs (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.

24
#include <sstream>
25
26
#include "ltlast/atomic_prop.hh"
#include "ltlast/constant.hh"
27
#include "tgbaexplicit.hh"
28
#include "tgba/formula2bdd.hh"
29
#include "misc/bddop.hh"
30
#include <cassert>
31
#include "ltlvisit/tostring.hh"
32
33
34
35
36
37
38
39

namespace spot
{

  ////////////////////////////////////////
  // tgba_explicit_succ_iterator

  tgba_explicit_succ_iterator::tgba_explicit_succ_iterator
40
  (const state_explicit::transitions_t* s, bdd all_acc)
41
    : s_(s), all_acceptance_conditions_(all_acc)
42
43
44
  {
  }

45
  void
46
47
48
49
50
  tgba_explicit_succ_iterator::first()
  {
    i_ = s_->begin();
  }

51
  void
52
53
54
55
56
  tgba_explicit_succ_iterator::next()
  {
    ++i_;
  }

57
  bool
58
  tgba_explicit_succ_iterator::done() const
59
60
61
62
  {
    return i_ == s_->end();
  }

63
  state_explicit*
64
  tgba_explicit_succ_iterator::current_state() const
65
  {
66
    assert(!done());
67
    return const_cast<state_explicit*>(i_->dest);
68
69
  }

70
  bdd
71
  tgba_explicit_succ_iterator::current_condition() const
72
  {
73
    assert(!done());
74
    return i_->condition;
75
76
  }

77
  bdd
78
  tgba_explicit_succ_iterator::current_acceptance_conditions() const
79
  {
80
    assert(!done());
81
    return i_->acceptance_conditions & all_acceptance_conditions_;
82
83
84
85
86
87
88
89
90
91
92
  }


  ////////////////////////////////////////
  // state_explicit

  int
  state_explicit::compare(const spot::state* other) const
  {
    const state_explicit* o = dynamic_cast<const state_explicit*>(other);
    assert(o);
93
94
95
96
97
98
    // Do not simply return "o - this", it might not fit in an int.
    if (o < this)
      return -1;
    if (o > this)
      return 1;
    return 0;
99
100
  }

101
102
103
104
  size_t
  state_explicit::hash() const
  {
    return
105
      reinterpret_cast<const char*>(this) - static_cast<const char*>(0);
106
107
  }

108

109
110
111
112
  ////////////////////////////////////////
  // tgba_explicit


113
  tgba_explicit::tgba_explicit(bdd_dict* dict)
114
115
116
    : dict_(dict), init_(0), all_acceptance_conditions_(bddfalse),
      neg_acceptance_conditions_(bddtrue),
      all_acceptance_conditions_computed_(false)
117
118
119
120
121
  {
  }

  tgba_explicit::~tgba_explicit()
  {
122
    dict_->unregister_all_my_variables(this);
123
  }
124

125
  tgba_explicit::transition*
126
  tgba_explicit::create_transition(state* source, const state* dest)
127
  {
128
129
130
131
132
133
134
    transition t;
    t.dest = dest;
    t.condition = bddtrue;
    t.acceptance_conditions = bddfalse;
    state_explicit::transitions_t::iterator i =
      source->successors.insert(source->successors.end(), t);
    return &*i;
135
  }
136
  void
137
  tgba_explicit::add_condition(transition* t, const ltl::formula* f)
138
  {
139
    t->condition &= formula_to_bdd(f, dict_, this);
140
    f->destroy();
141
142
  }

143
144
145
146
147
148
149
  void
  tgba_explicit::add_conditions(transition* t, bdd f)
  {
    dict_->register_propositions(f, this);
    t->condition &= f;
  }

150
151
152
153
154
155
156
157
158
159
  void
  tgba_explicit::copy_acceptance_conditions_of(const tgba *a)
  {
    assert(neg_acceptance_conditions_ == bddtrue);
    assert(all_acceptance_conditions_computed_ == false);
    bdd f = a->neg_acceptance_conditions();
    dict_->register_acceptance_variables(f, this);
    neg_acceptance_conditions_ = f;
  }

160
161
162
163
164
165
166
167
168
169
170
  void
  tgba_explicit::set_acceptance_conditions(bdd acc)
  {
    assert(neg_acceptance_conditions_ == bddtrue);
    assert(all_acceptance_conditions_computed_ == false);
    dict_->register_acceptance_variables(bdd_support(acc), this);
    neg_acceptance_conditions_ = compute_neg_acceptance_conditions(acc);
    all_acceptance_conditions_computed_ = true;
    all_acceptance_conditions_ = acc;
  }

171
  bool
172
  tgba_explicit::has_acceptance_condition(const ltl::formula* f) const
173
  {
174
    return dict_->is_registered_acceptance_variable(f, this);
175
176
177
  }

  bdd
178
  tgba_explicit::get_acceptance_condition(const ltl::formula* f)
179
  {
180
    bdd_dict::fv_map::iterator i = dict_->acc_map.find(f);
181
    assert(has_acceptance_condition(f));
182
183
    /* If this second assert fails and the first doesn't,
       things are badly broken.  This has already happened. */
184
    assert(i != dict_->acc_map.end());
185
    f->destroy();
186
    bdd v = bdd_ithvar(i->second);
187
    v &= bdd_exist(neg_acceptance_conditions_, v);
188
    return v;
189
190
  }

191
  void
192
  tgba_explicit::add_acceptance_condition(transition* t, const ltl::formula* f)
193
  {
194
195
    bdd c = get_acceptance_condition(f);
    t->acceptance_conditions |= c;
196
197
  }

198
  void
199
  tgba_explicit::add_acceptance_conditions(transition* t, bdd f)
200
201
  {
    bdd sup = bdd_support(f);
202
    dict_->register_acceptance_variables(sup, this);
203
204
    while (sup != bddtrue)
      {
205
	neg_acceptance_conditions_ &= bdd_nithvar(bdd_var(sup));
206
207
	sup = bdd_high(sup);
      }
208
    t->acceptance_conditions |= f;
209
210
  }

211
  state*
212
213
  tgba_explicit::get_init_state() const
  {
214
215
    // Fix empty automata by adding a lone initial state.
    if (!init_)
216
      const_cast<tgba_explicit*>(this)->add_default_init();
217
    return init_;
218
219
  }

220
  tgba_succ_iterator*
221
222
223
  tgba_explicit::succ_iter(const spot::state* state,
			   const spot::state* global_state,
			   const tgba* global_automaton) const
224
225
226
  {
    const state_explicit* s = dynamic_cast<const state_explicit*>(state);
    assert(s);
227
228
    (void) global_state;
    (void) global_automaton;
229
    return new tgba_explicit_succ_iterator(&s->successors,
230
					   all_acceptance_conditions());
231
  }
232

233
234
235
236
237
  bdd
  tgba_explicit::compute_support_conditions(const spot::state* in) const
  {
    const state_explicit* s = dynamic_cast<const state_explicit*>(in);
    assert(s);
238
    const state_explicit::transitions_t& st = s->successors;
239

240
    bdd res = bddfalse;
241
242
243
    state_explicit::transitions_t::const_iterator i;
    for (i = st.begin(); i != st.end(); ++i)
      res |= i->condition;
244
245
246
247
248
249
250
251
    return res;
  }

  bdd
  tgba_explicit::compute_support_variables(const spot::state* in) const
  {
    const state_explicit* s = dynamic_cast<const state_explicit*>(in);
    assert(s);
252
    const state_explicit::transitions_t& st = s->successors;
253
254

    bdd res = bddtrue;
255
256
257
    state_explicit::transitions_t::const_iterator i;
    for (i = st.begin(); i != st.end(); ++i)
      res &= bdd_support(i->condition);
258
259
260
    return res;
  }

261
  bdd_dict*
262
263
264
265
266
  tgba_explicit::get_dict() const
  {
    return dict_;
  }

267
  bdd
268
  tgba_explicit::all_acceptance_conditions() const
269
  {
270
    if (!all_acceptance_conditions_computed_)
271
      {
272
273
	all_acceptance_conditions_ =
	  compute_all_acceptance_conditions(neg_acceptance_conditions_);
274
	all_acceptance_conditions_computed_ = true;
275
      }
276
    return all_acceptance_conditions_;
277
278
279
  }

  bdd
280
  tgba_explicit::neg_acceptance_conditions() const
281
  {
282
    return neg_acceptance_conditions_;
283
284
  }

285
286
287
288
289
  tgba_explicit_string::~tgba_explicit_string()
  {
    ns_map::iterator i;
    for (i = name_state_map_.begin(); i != name_state_map_.end(); ++i)
    {
290
291
292
293
294
      // Do not erase the same state twice.  (Because of possible aliases.)
      if (state_name_map_.erase(i->second))
	{
	  delete i->second;
	}
295
296
297
    }
  }

298
299
300
301
302
303
304
305
306
307
308
  tgba_explicit::state*
  tgba_explicit_string::add_default_init()
  {
    return add_state("empty");
  }

  std::string
  tgba_explicit_string::format_state(const spot::state* s) const
  {
    const state_explicit* se = dynamic_cast<const state_explicit*>(s);
    assert(se);
309
    sn_map::const_iterator i = state_name_map_.find(se);
310
311
312
313
314
315
    assert(i != state_name_map_.end());
    return i->second;
  }

  tgba_explicit_formula::~tgba_explicit_formula()
  {
316
317
318
319
320
321
322
323
324
    ns_map::iterator i = name_state_map_.begin();
    while (i != name_state_map_.end())
    {
      // Advance the iterator before deleting the formula.
      const ltl::formula* s = i->first;
      delete i->second;
      ++i;
      s->destroy();
    }
325
326
327
328
329
330
331
332
333
334
335
336
  }

  tgba_explicit::state* tgba_explicit_formula::add_default_init()
  {
    return add_state(ltl::constant::true_instance());
  }

  std::string
  tgba_explicit_formula::format_state(const spot::state* s) const
  {
    const state_explicit* se = dynamic_cast<const state_explicit*>(s);
    assert(se);
337
    sn_map::const_iterator i = state_name_map_.find(se);
338
339
340
341
    assert(i != state_name_map_.end());
    return ltl::to_string(i->second);
  }

342
343
344
345
  tgba_explicit_number::~tgba_explicit_number()
  {
    ns_map::iterator i = name_state_map_.begin();
    while (i != name_state_map_.end())
346
347
348
349
      {
	delete i->second;
	++i;
      }
350
351
352
353
354
355
356
357
358
359
360
361
  }

  tgba_explicit::state* tgba_explicit_number::add_default_init()
  {
    return add_state(0);
  }

  std::string
  tgba_explicit_number::format_state(const spot::state* s) const
  {
    const state_explicit* se = dynamic_cast<const state_explicit*>(s);
    assert(se);
362
    sn_map::const_iterator i = state_name_map_.find(se);
363
364
365
366
367
    assert(i != state_name_map_.end());
    std::stringstream ss;
    ss << i->second;
    return ss.str();
  }
368
}