sccfilter.cc 10.3 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

20
#include "sccfilter.hh"
21
#include "reachiter.hh"
22
#include "sccinfo.hh"
23
24
25
26
27

namespace spot
{
  namespace
  {
28
29
30
31
    // BDD.id -> Acc number
    typedef std::map<int, unsigned> accremap_t;
    typedef std::vector<accremap_t> remap_table_t;

32
    typedef std::tuple<bool, bdd, acc_cond::mark_t> filtered_trans;
33

34

35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
    // SCC filters are objects with two methods:
    //  state(src) return true iff s should be kept
    //  trans(src, dst, cond, acc) returns a triplet
    //     (keep, cond2, acc2) where keep is a Boolean stating if the
    //                      transition should be kept, and cond2/acc2
    //                      give replacement values for cond/acc
    struct id_filter
    {
      scc_info* si;
      id_filter(scc_info* si)
	: si(si)
      {
      }

      // Accept all states
      bool state(unsigned)
      {
	return true;
      }

55
      unsigned accsets(unsigned n)
56
      {
57
	return n;
58
59
      }

60
      // Accept all transitions, unmodified
61
      filtered_trans trans(unsigned, unsigned, bdd cond, acc_cond::mark_t acc)
62
63
64
65
66
67
      {
	return filtered_trans{true, cond, acc};
      }
    };

    // Remove useless states.
68
69
    template <class next_filter = id_filter>
    struct state_filter: next_filter
70
    {
71
72
73
      template<typename... Args>
      state_filter(scc_info* si, Args&&... args)
	: next_filter(si, std::forward<Args>(args)...)
74
75
      {
      }
76
77
78

      bool state(unsigned s)
      {
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
	return this->next_filter::state(s) && this->si->is_useful_state(s);
      }
    };

    // Suspension filter, used only by compsusp.cc
    template <class next_filter = id_filter>
    struct susp_filter: next_filter
    {
      bdd suspvars;
      bdd ignoredvars;
      bool early_susp;

      template<typename... Args>
      susp_filter(scc_info* si,
		  bdd suspvars, bdd ignoredvars, bool early_susp,
		  Args&&... args)
	: next_filter(si, std::forward<Args>(args)...),
	  suspvars(suspvars),
	  ignoredvars(ignoredvars),
	  early_susp(early_susp)
      {
      }

      filtered_trans trans(unsigned src, unsigned dst,
103
			   bdd cond, acc_cond::mark_t acc)
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
      {
	bool keep;
	std::tie(keep, cond, acc) =
	  this->next_filter::trans(src, dst, cond, acc);

	if (keep)
	  {
	    // Always remove ignored variables
	    cond = bdd_exist(cond, ignoredvars);

	    // Remove the suspension variables only if
	    // the destination in not in an accepting SCC,
	    // or if we are between SCC with early_susp unset.
	    unsigned u = this->si->scc_of(dst);
	    if (!this->si->is_accepting_scc(u)
		|| (!early_susp && (u != this->si->scc_of(src))))
	      cond = bdd_exist(cond, suspvars);
	  }

	return filtered_trans(keep, cond, acc);
124
125
126
127
128
      }
    };

    // Remove acceptance conditions from all transitions outside of
    // non-accepting SCCs.
129
130
    template <class next_filter = id_filter>
    struct acc_filter_all: next_filter
131
    {
132
133
134
      template<typename... Args>
      acc_filter_all(scc_info* si, Args&&... args)
	: next_filter(si, std::forward<Args>(args)...)
135
136
137
138
      {
      }

      filtered_trans trans(unsigned src, unsigned dst,
139
			   bdd cond, acc_cond::mark_t acc)
140
      {
141
142
143
	bool keep;
	std::tie(keep, cond, acc) =
	  this->next_filter::trans(src, dst, cond, acc);
144

145
146
147
148
149
150
	if (keep)
	  {
	    unsigned u = this->si->scc_of(src);
	    // If the transition is between two SCCs, or in a
	    // non-accepting SCC.  Remove the acceptance sets.
	    if (!this->si->is_accepting_scc(u) || u != this->si->scc_of(dst))
151
	      acc = 0U;
152
153
154
	  }

	return filtered_trans(keep, cond, acc);
155
156
157
158
159
      }
    };

    // Remove acceptance conditions from all transitions whose
    // destination is not an accepting SCCs.
160
161
    template <class next_filter = id_filter>
    struct acc_filter_some: next_filter
162
    {
163
164
165
      template<typename... Args>
      acc_filter_some(scc_info* si, Args&&... args)
	: next_filter(si, std::forward<Args>(args)...)
166
167
168
      {
      }

169
      filtered_trans trans(unsigned src, unsigned dst,
170
			   bdd cond, acc_cond::mark_t acc)
171
      {
172
173
174
175
176
	bool keep;
	std::tie(keep, cond, acc) =
	  this->next_filter::trans(src, dst, cond, acc);

	if (!this->si->is_accepting_scc(this->si->scc_of(dst)))
177
	  acc = 0U;
178
	return filtered_trans(keep, cond, acc);
179
180
181
      }
    };

182
183
184
    // Simplify redundant acceptance sets used in each SCCs.
    template <class next_filter = id_filter>
    struct acc_filter_simplify: next_filter
185
    {
186
187
      // Acceptance sets to strip in each SCC.
      std::vector<acc_cond::mark_t> strip_;
188

189
190
191
      template<typename... Args>
      acc_filter_simplify(scc_info* si, Args&&... args)
	: next_filter(si, std::forward<Args>(args)...)
192
193
194
      {
      }

195
      unsigned accsets(unsigned n)
196
      {
197
	unsigned scc_count = this->si->scc_count();
198
199
200
201
202
203
204
205
206
	auto& acc = this->si->get_aut()->acc();
	assert(n == acc.num_sets());
	(void) n;

	auto used_acc = this->si->used_acc();
	assert(used_acc.size() == scc_count);
	strip_.resize(scc_count);
	std::vector<unsigned> cnt(scc_count); // # of useful sets in each SCC
	unsigned max = 0;		      // Max number of useful sets
207
208
	for (unsigned n = 0; n < scc_count; ++n)
	  {
209
	    if (!this->si->is_accepting_scc(n))
210
	      continue;
211
212
213
214
	    strip_[n] = acc.useless(used_acc[n].begin(), used_acc[n].end());
	    cnt[n] = acc.num_sets() - strip_[n].count();
	    if (cnt[n] > max)
	      max = cnt[n];
215
216
217
218
219
220
	  }
	// Now that we know about the max number of acceptance
	// conditions, add extra acceptance conditions to those SCC
	// that do not have enough.
	for (unsigned n = 0; n < scc_count; ++n)
	  {
221
	    if (!this->si->is_accepting_scc(n))
222
	      continue;
223
224
	    if (cnt[n] < max)
	      strip_[n].remove_some(max - cnt[n]);
225
	  }
226
	return max;
227
228
      }

229
230
      filtered_trans trans(unsigned src, unsigned dst, bdd cond,
			   acc_cond::mark_t acc)
231
      {
232
233
234
235
	bool keep;
	std::tie(keep, cond, acc) =
	  this->next_filter::trans(src, dst, cond, acc);

236
	if (keep && acc)
237
	  {
238
239
	    unsigned u = this->si->scc_of(dst);

240
241
	    if (!this->si->is_accepting_scc(u))
	      acc = 0U;
242
	    else
243
	      acc = acc.strip(strip_[u]);
244
	  }
245
	return filtered_trans{keep, cond, acc};
246
247
248
249
      }
    };


250
    template<class F, typename... Args>
251
    tgba_digraph_ptr scc_filter_apply(const_tgba_digraph_ptr aut,
252
				      scc_info* given_si, Args&&... args)
253
    {
254
255
256
257
      if (!aut->acc().is_generalized_buchi())
	throw std::runtime_error
	  ("scc_filter() works only with generalized Büchi acceptance");

258
      tgba_digraph_ptr filtered = make_tgba_digraph(aut->get_dict());
259
260
261
      unsigned in_n = aut->num_states(); // Number of input states.
      if (in_n == 0)			 // Nothing to filter.
	return filtered;
262
      filtered->copy_ap_of(aut);
263

264
265
266
267
268
      // Compute scc_info if not supplied.
      scc_info* si = given_si;
      if (!si)
	si = new scc_info(aut);

269
      F filter(si, std::forward<Args>(args)...);
270
271
272
273
274
275
276
277
278
279
280

      // Renumber all useful states.
      unsigned out_n = 0;		 // Number of output states.
      std::vector<unsigned> inout; // Associate old states to new ones.
      inout.reserve(in_n);
      for (unsigned i = 0; i < in_n; ++i)
	if (filter.state(i))
	  inout.push_back(out_n++);
	else
	  inout.push_back(-1U);

281
      filtered->
282
	set_generalized_buchi(filter.accsets(aut->acc().num_sets()));
283
      filtered->new_states(out_n);
284
285
286
287
288
      for (unsigned isrc = 0; isrc < in_n; ++isrc)
	{
	  unsigned osrc = inout[isrc];
	  if (osrc >= out_n)
	    continue;
289
	  for (auto& t: aut->out(isrc))
290
291
292
293
294
295
	    {
	      unsigned odst = inout[t.dst];
	      if (odst >= out_n)
		continue;
	      bool want;
	      bdd cond;
296
	      acc_cond::mark_t acc;
297
298
299
	      std::tie(want, cond, acc) =
		filter.trans(isrc, t.dst, t.cond, t.acc);
	      if (want)
300
		filtered->new_transition(osrc, odst, cond, acc);
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
	    }
	}
      if (!given_si)
	delete si;
      // If the initial state has been filtered out, we don't attempt
      // to fix it.
      auto init = inout[aut->get_init_state_number()];
      if (init < out_n)
	filtered->set_init_state(init);
      return filtered;
    }


  }

316
317
  tgba_digraph_ptr
  scc_filter_states(const const_tgba_digraph_ptr& aut, scc_info* given_si)
318
  {
319
    auto res = scc_filter_apply<state_filter<>>(aut, given_si);
320
    res->prop_copy(aut, { true, true, true, true, true });
321
    return res;
322
323
  }

324
325
  tgba_digraph_ptr
  scc_filter(const const_tgba_digraph_ptr& aut, bool remove_all_useless,
326
327
	     scc_info* given_si)
  {
328
    tgba_digraph_ptr res;
329
    if (remove_all_useless)
330
331
332
      res = scc_filter_apply<state_filter
			     <acc_filter_all
			      <acc_filter_simplify<>>>>(aut, given_si);
333
    else
334
335
336
337
      res = scc_filter_apply<state_filter
			     <acc_filter_some
			      <acc_filter_simplify<>>>>(aut, given_si);
    res->merge_transitions();
338
    res->prop_copy(aut,
339
340
341
342
		   { false,  // state-based acceptance is not preserved
		     true,
		     true,
		     true,
343
		     true,
344
		   });
345
    return res;
346
347
  }

348
349
  tgba_digraph_ptr
  scc_filter_susp(const const_tgba_digraph_ptr& aut, bool remove_all_useless,
350
351
352
		  bdd suspvars, bdd ignoredvars, bool early_susp,
		  scc_info* given_si)
  {
353
    tgba_digraph_ptr res;
354
    if (remove_all_useless)
355
356
357
358
359
360
361
      res = scc_filter_apply<susp_filter
			     <state_filter
			      <acc_filter_all
			       <acc_filter_simplify<>>>>>(aut, given_si,
							  suspvars,
							  ignoredvars,
							  early_susp);
362
    else
363
364
365
366
367
368
369
370
      res = scc_filter_apply<susp_filter
			     <state_filter
			      <acc_filter_some
			       <acc_filter_simplify<>>>>>(aut, given_si,
							  suspvars,
							  ignoredvars,
							  early_susp);
    res->merge_transitions();
371
    res->prop_copy(aut,
372
373
374
375
		   { false,  // state-based acceptance is not preserved
		     true,
		     true,
		     false,	// determinism may not be preserved
376
		     false,  	// stutter inv. of suspvars probably altered
377
		   });
378
    return res;
379
380
  }

381
}