ltl2tgba.cc 22.6 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) 2003, 2004  Laboratoire d'Informatique de Paris 6 (LIP6),
// 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.

22
23
#include <iostream>
#include <cassert>
24
25
#include <fstream>
#include <string>
26
#include "ltlvisit/destroy.hh"
27
#include "ltlvisit/reduce.hh"
28
#include "ltlvisit/tostring.hh"
29
#include "ltlvisit/apcollect.hh"
30
31
#include "ltlast/allnodes.hh"
#include "ltlparse/public.hh"
32
#include "tgbaalgos/ltl2tgba_lacim.hh"
33
#include "tgbaalgos/ltl2tgba_fm.hh"
34
#include "tgba/bddprint.hh"
35
#include "tgbaalgos/save.hh"
36
#include "tgbaalgos/dotty.hh"
37
#include "tgbaalgos/lbtt.hh"
38
#include "tgba/tgbatba.hh"
39
#include "tgba/tgbaproduct.hh"
40
#include "tgbaalgos/gv04.hh"
41
#include "tgbaalgos/magic.hh"
42
#include "tgbaalgos/reducerun.hh"
43
44
#include "tgbaalgos/se05.hh"
#include "tgbaalgos/tau03.hh"
45
#include "tgbaalgos/tau03opt.hh"
46
47
#include "tgbaalgos/gtec/gtec.hh"
#include "tgbaalgos/gtec/ce.hh"
48
#include "tgbaparse/public.hh"
49
#include "tgbaalgos/dupexp.hh"
50
#include "tgbaalgos/neverclaim.hh"
51
#include "tgbaalgos/reductgba_sim.hh"
52
#include "tgbaalgos/replayrun.hh"
53
#include "tgbaalgos/rundotdec.hh"
54

55
56
57
void
syntax(char* prog)
{
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
58
  std::cerr << "Usage: "<< prog << " [OPTIONS...] formula" << std::endl
59
            << "       "<< prog << " -F [OPTIONS...] file" << std::endl
60
            << "       "<< prog << " -X [OPTIONS...] file" << std::endl
Alexandre Duret-Lutz's avatar
spacing    
Alexandre Duret-Lutz committed
61
	    << std::endl
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
62
	    << "Options:" << std::endl
martinez's avatar
martinez committed
63
	    << "  -a    display the acceptance_conditions BDD, not the "
64
	    << "reachability graph"
65
	    << std::endl
martinez's avatar
martinez committed
66
	    << "  -A    same as -a, but as a set" << std::endl
67
68
	    << "  -b    display the automaton in the format of spot"
            << std::endl
martinez's avatar
martinez committed
69
	    << "  -d    turn on traces during parsing" << std::endl
70
71
	    << "  -D    degeneralize the automaton as a TBA" << std::endl
	    << "  -DS   degeneralize the automaton as an SBA" << std::endl
72
73
74
	    << "  -e[ALGO]  emptiness-check, expect and compute an "
	    << "accepting run" << std::endl
	    << "  -E[ALGO]  emptiness-check, expect no accepting run"
75
	    << std::endl
martinez's avatar
martinez committed
76
77
78
            << "  -f    use Couvreur's FM algorithm for translation"
	    << std::endl
            << "  -F    read the formula from the file" << std::endl
79
	    << "  -g    graph the accepting run on the automaton (requires -e)"
80
	    << std::endl
81
82
	    << "  -G    graph the accepting run seen as an automaton "
	    << " (requires -e)" << std::endl
martinez's avatar
martinez committed
83
            << "  -L    fair-loop approximation (implies -f)" << std::endl
84
	    << "  -m    try to reduce accepting runs, in a second pass"
85
	    << std::endl
martinez's avatar
martinez committed
86
87
	    << "  -N    display the never clain for Spin "
	    << "(implies -D)" << std::endl
martinez's avatar
martinez committed
88
            << "  -p    branching postponement (implies -f)" << std::endl
89
90
	    << "  -Pfile  multiply the formula with the automaton from `file'."
	    << std::endl
martinez's avatar
martinez committed
91
	    << "  -r    display the relation BDD, not the reachability graph"
92
	    << std::endl
martinez's avatar
martinez committed
93
94
	    << "  -r1   reduce formula using basic rewriting" << std::endl
	    << "  -r2   reduce formula using class of eventuality and "
95
	    << "and universality" << std::endl
martinez's avatar
martinez committed
96
	    << "  -r3   reduce formula using implication between "
97
	    << "sub-formulae" << std::endl
martinez's avatar
martinez committed
98
99
100
	    << "  -r4   reduce formula using all rules" << std::endl
	    << "  -rd   display the reduce formula" << std::endl
	    << "  -R    same as -r, but as a set" << std::endl
101
	    << "  -R1q  merge states using direct simulation "
martinez's avatar
martinez committed
102
	    << "(use -L for more reduction)"
103
	    << std::endl
104
	    << "  -R1t  remove transitions using direct simulation "
martinez's avatar
martinez committed
105
	    << "(use -L for more reduction)"
106
	    << std::endl
107
108
	    << "  -R2q  merge states using delayed simulation" << std::endl
	    << "  -R2t  remove transitions using delayed simulation"
109
	    << std::endl
110
111
112
	    << "  -R3   use SCC to reduce the automata" << std::endl
	    << "  -Rd   display the simulation relation" << std::endl
	    << "  -RD   display the parity game (dot format)" << std::endl
martinez's avatar
martinez committed
113
	    << "  -s    convert to explicit automata, and number states "
114
	    << "in DFS order" << std::endl
martinez's avatar
martinez committed
115
	    << "  -S    convert to explicit automata, and number states "
116
	    << "in BFS order" << std::endl
martinez's avatar
martinez committed
117
	    << "  -t    display reachable states in LBTT's format" << std::endl
118
119
            << "  -U[PROPS]  consider atomic properties PROPS as exclusive "
	    << "events (implies -f)" << std::endl
martinez's avatar
martinez committed
120
121
122
	    << "  -v    display the BDD variables used by the automaton"
	    << std::endl
            << "  -x    try to produce a more deterministic automata "
123
	    << "(implies -f)" << std::endl
martinez's avatar
martinez committed
124
	    << "  -X    do not compute an automaton, read it from a file"
125
	    << std::endl
martinez's avatar
martinez committed
126
	    << "  -y    do not merge states with same symbolic representation "
127
128
129
	    << "(implies -f)" << std::endl
	    << std::endl
	    << "Where ALGO should be one of:" << std::endl
130
	    << "  couvreur99 (the default)" << std::endl
131
	    << "  couvreur99_shy-" << std::endl
132
133
	    << "  couvreur99_shy" << std::endl
	    << "  magic_search" << std::endl
134
	    << "  magic_search_repeated" << std::endl
135
136
137
138
	    << "  bsh_magic_search[(heap size in Mo - 10Mo by default)]"
            << std::endl
	    << "  bsh_magic_search_repeated[(heap size in MB - 10MB"
            << " by default)]" << std::endl
139
	    << "  gv04" << std::endl
140
	    << "  se05_search" << std::endl
141
142
143
144
	    << "  se05_search_repeated" << std::endl
	    << "  bsh_se05_search[(heap size in MB - 10MB by default)]"
            << std::endl
	    << "  bsh_se05_search_repeated[(heap size in MB - 10MB"
145
            << " by default)]" << std::endl
146
147
	    << "  tau03_search" << std::endl
	    << "  tau03_opt_search" << std::endl;
148
149
150
151
152
153
154
155
  exit(2);
}

int
main(int argc, char** argv)
{
  int exit_code = 0;

156
  bool debug_opt = false;
157
  enum { NoDegen, DegenTBA, DegenSBA } degeneralize_opt = NoDegen;
158
  bool degeneralize_maybe = false;
159
  bool fm_opt = false;
160
  bool fm_exprop_opt = false;
161
  bool fm_symb_merge_opt = true;
162
  bool file_opt = false;
163
  int output = 0;
164
  int formula_index = 0;
165
  std::string echeck_algo;
166
  enum { None, Couvreur, Couvreur2, MagicSearch, Se05Search,
167
	 Tau03Search, Tau03OptSearch, Gv04 } echeck = None;
168
  enum { NoneDup, BFS, DFS } dupexp = NoneDup;
169
  bool couv_group = true;
170
  bool search_many = false;
171
172
  bool bit_state_hashing = false;
  int heap_size = 10*1024*1024;
173
  bool expect_counter_example = false;
174
  bool from_file = false;
175
  int reduc_aut = spot::Reduce_None;
176
  int redopt = spot::ltl::Reduce_None;
177
178
  bool display_reduce_form = false;
  bool display_rel_sim = false;
179
  bool display_parity_game = false;
180
  bool post_branching = false;
181
  bool fair_loop_approx = false;
182
  bool graph_run_opt = false;
183
  bool graph_run_tgba_opt = false;
184
  bool opt_reduce = false;
185
186
  spot::ltl::environment& env(spot::ltl::default_environment::instance());
  spot::ltl::atomic_prop_set* unobservables = 0;
187
188
189
  spot::tgba_explicit* system = 0;
  spot::tgba* product = 0;
  spot::bdd_dict* dict = new spot::bdd_dict();
190

191
  for (;;)
192
    {
193
      if (argc < formula_index + 2)
194
	syntax(argv[0]);
195
196
197

      ++formula_index;

198
199
200
201
      if (!strcmp(argv[formula_index], "-a"))
	{
	  output = 2;
	}
202
203
204
205
206
      else if (!strcmp(argv[formula_index], "-b"))
	{
	  output = 7;
	}
      else if (!strcmp(argv[formula_index], "-v"))
207
	{
208
	  output = 5;
209
210
	}
      else if (!strcmp(argv[formula_index], "-d"))
211
212
213
	{
	  debug_opt = true;
	}
214
215
      else if (!strcmp(argv[formula_index], "-D"))
	{
216
217
218
219
220
	  degeneralize_opt = DegenTBA;
	}
      else if (!strcmp(argv[formula_index], "-DS"))
	{
	  degeneralize_opt = DegenSBA;
221
	}
222
      else if (!strncmp(argv[formula_index], "-e", 2))
223
224
225
226
227
228
229
230
231
232
233
234
235
        {
          if (argv[formula_index][2] != 0)
            {
              char *p = strchr(argv[formula_index], '(');
              if (p && sscanf(p+1, "%d)", &heap_size) == 1)
                *p = '\0';
              echeck_algo = argv[formula_index] + 2;
            }
          else
            echeck_algo = "couvreur99";
          expect_counter_example = true;
          output = -1;
        }
236
      else if (!strncmp(argv[formula_index], "-E", 2))
237
238
239
240
241
242
243
244
245
246
247
248
249
        {
          if (argv[formula_index][2] != 0)
            {
              char *p = strchr(argv[formula_index], '(');
              if (p && sscanf(p+1, "%d)", &heap_size) == 1)
                *p = '\0';
              echeck_algo = argv[formula_index] + 2;
            }
          else
            echeck_algo = "couvreur99";
          expect_counter_example = false;
          output = -1;
        }
250
251
252
253
254
255
256
257
      else if (!strcmp(argv[formula_index], "-f"))
	{
	  fm_opt = true;
	}
      else if (!strcmp(argv[formula_index], "-F"))
	{
	  file_opt = true;
	}
258
259
260
261
      else if (!strcmp(argv[formula_index], "-g"))
	{
	  graph_run_opt = true;
	}
262
263
264
265
      else if (!strcmp(argv[formula_index], "-G"))
	{
	  graph_run_tgba_opt = true;
	}
266
267
268
269
270
      else if (!strcmp(argv[formula_index], "-L"))
	{
	  fair_loop_approx = true;
	  fm_opt = true;
	}
271
272
      else if (!strcmp(argv[formula_index], "-m"))
	{
273
	  opt_reduce = true;
274
	}
martinez's avatar
martinez committed
275
276
      else if (!strcmp(argv[formula_index], "-N"))
	{
277
	  degeneralize_opt = DegenSBA;
martinez's avatar
martinez committed
278
279
	  output = 8;
	}
280
281
282
283
284
      else if (!strcmp(argv[formula_index], "-p"))
	{
	  post_branching = true;
	  fm_opt = true;
	}
285
286
287
288
289
      else if (!strncmp(argv[formula_index], "-P", 2))
	{
	  spot::tgba_parse_error_list pel;
	  system = spot::tgba_parse(argv[formula_index] + 2,
				     pel, dict, env, debug_opt);
290
291
	  if (spot::format_tgba_parse_errors(std::cerr,
					     argv[formula_index] + 2, pel))
292
293
294
295
	    return 2;
	  system->merge_transitions();
	  std::clog << argv[formula_index] + 2 << " read" << std::endl;
	}
296
297
      else if (!strcmp(argv[formula_index], "-r"))
	{
298
299
	  output = 1;
	}
300
301
302
303
304
305
      else if (!strcmp(argv[formula_index], "-r1"))
	{
	  redopt |= spot::ltl::Reduce_Basics;
	}
      else if (!strcmp(argv[formula_index], "-r2"))
	{
306
	  redopt |= spot::ltl::Reduce_Eventuality_And_Universality;
307
308
309
	}
      else if (!strcmp(argv[formula_index], "-r3"))
	{
310
	  redopt |= spot::ltl::Reduce_Syntactic_Implications;
311
312
313
314
315
	}
      else if (!strcmp(argv[formula_index], "-r4"))
	{
	  redopt |= spot::ltl::Reduce_All;
	}
316
317
318
      else if (!strcmp(argv[formula_index], "-R"))
	{
	  output = 3;
319
	}
martinez's avatar
martinez committed
320
321
322
323
324
325
326
327
328
      else if (!strcmp(argv[formula_index], "-R1q"))
	{
	  reduc_aut |= spot::Reduce_quotient_Dir_Sim;
	}
      else if (!strcmp(argv[formula_index], "-R1t"))
	{
	  reduc_aut |= spot::Reduce_transition_Dir_Sim;
	}
      else if (!strcmp(argv[formula_index], "-R2q"))
329
	{
martinez's avatar
martinez committed
330
	  reduc_aut |= spot::Reduce_quotient_Del_Sim;
331
	}
martinez's avatar
martinez committed
332
      else if (!strcmp(argv[formula_index], "-R2t"))
333
	{
martinez's avatar
martinez committed
334
	  reduc_aut |= spot::Reduce_transition_Del_Sim;
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
	}
      else if (!strcmp(argv[formula_index], "-R3"))
	{
	  reduc_aut |= spot::Reduce_Scc;
	}
      else if (!strcmp(argv[formula_index], "-rd"))
	{
	  display_reduce_form = true;
	}
      else if (!strcmp(argv[formula_index], "-Rd"))
	{
	  display_rel_sim = true;
	}
      else if (!strcmp(argv[formula_index], "-RD"))
	{
	  display_parity_game = true;
	}
352
353
354
355
356
357
358
359
      else if (!strcmp(argv[formula_index], "-s"))
	{
	  dupexp = DFS;
	}
      else if (!strcmp(argv[formula_index], "-S"))
	{
	  dupexp = BFS;
	}
360
361
362
363
      else if (!strcmp(argv[formula_index], "-t"))
	{
	  output = 6;
	}
364
365
366
367
368
      else if (!strncmp(argv[formula_index], "-U", 2))
	{
	  unobservables = new spot::ltl::atomic_prop_set;
	  fm_opt = true;
	  // Parse -U's argument.
369
	  const char* tok = strtok(argv[formula_index] + 2, ", \t;");
370
371
372
373
	  while (tok)
	    {
	      unobservables->insert
		(static_cast<spot::ltl::atomic_prop*>(env.require(tok)));
374
	      tok = strtok(0, ", \t;");
375
376
	    }
	}
377
378
379
380
      else if (!strcmp(argv[formula_index], "-v"))
	{
	  output = 5;
	}
381
382
383
384
385
      else if (!strcmp(argv[formula_index], "-x"))
	{
	  fm_opt = true;
	  fm_exprop_opt = true;
	}
386
387
388
389
      else if (!strcmp(argv[formula_index], "-X"))
	{
	  from_file = true;
	}
390
391
392
393
394
      else if (!strcmp(argv[formula_index], "-y"))
	{
	  fm_opt = true;
	  fm_symb_merge_opt = false;
	}
395
396
397
398
      else
	{
	  break;
	}
399
400
    }

401
  if (echeck_algo != "")
402
    {
403
404
405
406
407
408
409
      if (echeck_algo == "couvreur99")
	{
	  echeck = Couvreur;
	}
      else if (echeck_algo == "couvreur99_shy")
	{
	  echeck = Couvreur2;
410
411
412
413
414
415
	  couv_group = true;
	}
      else if (echeck_algo == "couvreur99_shy-")
	{
	  echeck = Couvreur2;
	  couv_group = false;
416
417
418
419
	}
      else if (echeck_algo == "magic_search")
	{
	  echeck = MagicSearch;
420
	  degeneralize_maybe = true;
421
422
423
424
	}
      else if (echeck_algo == "magic_search_repeated")
	{
	  echeck = MagicSearch;
425
	  degeneralize_maybe = true;
426
	  search_many = true;
427
	}
428
429
430
      else if (echeck_algo == "bsh_magic_search")
	{
	  echeck = MagicSearch;
431
	  degeneralize_maybe = true;
432
433
434
435
436
          bit_state_hashing = true;
	}
      else if (echeck_algo == "bsh_magic_search_repeated")
	{
	  echeck = MagicSearch;
437
	  degeneralize_maybe = true;
438
          bit_state_hashing = true;
439
	  search_many = true;
440
	}
441
442
      else if (echeck_algo == "se05_search")
	{
443
	  echeck = Se05Search;
444
	  degeneralize_maybe = true;
445
446
447
	}
      else if (echeck_algo == "se05_search_repeated")
	{
448
	  echeck = Se05Search;
449
	  degeneralize_maybe = true;
450
	  search_many = true;
451
452
453
454
	}
      else if (echeck_algo == "bsh_se05_search")
	{
	  echeck = Se05Search;
455
	  degeneralize_maybe = true;
456
457
458
459
460
          bit_state_hashing = true;
	}
      else if (echeck_algo == "bsh_se05_search_repeated")
	{
	  echeck = Se05Search;
461
	  degeneralize_maybe = true;
462
          bit_state_hashing = true;
463
464
465
466
467
	  search_many = true;
	}
      else if (echeck_algo == "tau03_search")
	{
	  echeck = Tau03Search;
468
	}
469
470
471
472
      else if (echeck_algo == "tau03_opt_search")
	{
	  echeck = Tau03OptSearch;
	}
473
474
475
476
477
      else if (echeck_algo == "gv04")
	{
	  echeck = Gv04;
	  degeneralize_maybe = true;
	}
478
479
480
481
482
      else
	{
	  std::cerr << "unknown emptiness-check: " << echeck_algo << std::endl;
	  syntax(argv[0]);
	}
483
484
    }

485
486
  if ((graph_run_opt || graph_run_tgba_opt)
      && (echeck_algo == "" || !expect_counter_example))
487
    {
488
      std::cerr << argv[0] << ": error: -g and -G require -e." << std::endl;
489
490
491
      exit(1);
    }

492
493
494
495
  std::string input;

  if (file_opt)
    {
496
      if (strcmp(argv[formula_index], "-"))
497
	{
498
	  std::ifstream fin(argv[formula_index]);
499
	  if (!fin)
500
501
502
503
	    {
	      std::cerr << "Cannot open " << argv[formula_index] << std::endl;
	      exit(2);
	    }
504

505
	  if (!std::getline(fin, input, '\0'))
506
507
508
509
510
511
	    {
	      std::cerr << "Cannot read " << argv[formula_index] << std::endl;
	      exit(2);
	    }
	}
      else
512
	{
513
	  std::getline(std::cin, input, '\0');
514
515
516
517
518
519
520
	}
    }
  else
    {
      input = argv[formula_index];
    }

521
522
523
524
525
526
527
528
  spot::ltl::formula* f = 0;
  if (!from_file)
    {
      spot::ltl::parse_error_list pel;
      f = spot::ltl::parse(input, pel, env, debug_opt);
      exit_code = spot::ltl::format_parse_errors(std::cerr, input, pel);
    }
  if (f || from_file)
529
    {
530
531
532
533
      spot::tgba_bdd_concrete* concrete = 0;
      spot::tgba* to_free = 0;
      spot::tgba* a = 0;

534
535
536
      if (from_file)
	{
	  spot::tgba_parse_error_list pel;
537
538
	  spot::tgba_explicit* e;
	  to_free = a = e = spot::tgba_parse(input, pel, dict, env, debug_opt);
539
	  if (spot::format_tgba_parse_errors(std::cerr, input, pel))
540
541
542
543
544
	    {
	      delete to_free;
	      delete dict;
	      return 2;
	    }
545
	  e->merge_transitions();
546
	}
547
      else
548
	{
549
	  if (redopt != spot::ltl::Reduce_None)
550
	    {
551
552
553
	      spot::ltl::formula* t = spot::ltl::reduce(f, redopt);
	      spot::ltl::destroy(f);
	      f = t;
554
555
	      if (display_reduce_form)
		std::cout << spot::ltl::to_string(f) << std::endl;
556
	    }
557

558
	  if (fm_opt)
559
	    to_free = a = spot::ltl_to_tgba_fm(f, dict, fm_exprop_opt,
560
					       fm_symb_merge_opt,
561
					       post_branching,
562
					       fair_loop_approx, unobservables);
563
564
565
	  else
	    to_free = a = concrete = spot::ltl_to_tgba_lacim(f, dict);
	}
566

567
      spot::tgba_tba_proxy* degeneralized = 0;
568

569
570
571
572
573
      if (degeneralize_maybe
	  && degeneralize_opt == NoDegen
	  && a->number_of_acceptance_conditions() > 1)
	degeneralize_opt = DegenTBA;
      if (degeneralize_opt == DegenTBA)
574
	a = degeneralized = new spot::tgba_tba_proxy(a);
575
576
      else if (degeneralize_opt == DegenSBA)
	a = degeneralized = new spot::tgba_sba_proxy(a);
577

578
579
580
581
      spot::tgba_reduc* aut_red = 0;
      if (reduc_aut != spot::Reduce_None)
	{
	  a = aut_red = new spot::tgba_reduc(a);
582
583
584
585

	  if (reduc_aut & spot::Reduce_Scc)
	    aut_red->prune_scc();

martinez's avatar
martinez committed
586
587
588
589
	  if (reduc_aut & (spot::Reduce_quotient_Dir_Sim |
			   spot::Reduce_transition_Dir_Sim |
			   spot::Reduce_quotient_Del_Sim |
			   spot::Reduce_transition_Del_Sim))
590
	    {
martinez's avatar
martinez committed
591
592
593
594
595
	      spot::direct_simulation_relation* rel_dir = 0;
	      spot::delayed_simulation_relation* rel_del = 0;

	      if (reduc_aut & (spot::Reduce_quotient_Dir_Sim |
			       spot::Reduce_transition_Dir_Sim))
596
597
598
599
		rel_dir =
		  spot::get_direct_relation_simulation(a,
						       std::cout,
						       display_parity_game);
martinez's avatar
martinez committed
600
601
	      else if (reduc_aut & (spot::Reduce_quotient_Del_Sim |
				    spot::Reduce_transition_Del_Sim))
602
603
604
605
		rel_del =
		  spot::get_delayed_relation_simulation(a,
							std::cout,
							display_parity_game);
606
607

	      if (display_rel_sim)
martinez's avatar
martinez committed
608
609
610
611
612
613
		{
		  if (rel_dir)
		    aut_red->display_rel_sim(rel_dir, std::cout);
		  if (rel_del)
		    aut_red->display_rel_sim(rel_del, std::cout);
		}
614

martinez's avatar
martinez committed
615
616
617
618
619
620
621
622
623
624
625
626
627
	      if (reduc_aut & spot::Reduce_quotient_Dir_Sim)
		aut_red->quotient_state(rel_dir);
	      if (reduc_aut & spot::Reduce_transition_Dir_Sim)
		aut_red->delete_transitions(rel_dir);
	      if (reduc_aut & spot::Reduce_quotient_Del_Sim)
		aut_red->quotient_state(rel_del);
	      if (reduc_aut & spot::Reduce_transition_Del_Sim)
		aut_red->delete_transitions(rel_del);

	      if (rel_dir)
		spot::free_relation_simulation(rel_dir);
	      if (rel_del)
		spot::free_relation_simulation(rel_del);
628
629
630
	    }
	}

631
632
633
634
635
636
637
638
639
640
641
642
643
      spot::tgba_explicit* expl = 0;
      switch (dupexp)
	{
	case NoneDup:
	  break;
	case BFS:
	  a = expl = tgba_dupexp_bfs(a);
	  break;
	case DFS:
	  a = expl = tgba_dupexp_dfs(a);
	  break;
	}

644
645
646
      if (system)
	a = product = new spot::tgba_product(system, a);

647
648
      switch (output)
	{
649
650
651
	case -1:
	  /* No output.  */
	  break;
652
653
654
655
	case 0:
	  spot::dotty_reachable(std::cout, a);
	  break;
	case 1:
656
657
658
	  if (concrete)
	    spot::bdd_print_dot(std::cout, concrete->get_dict(),
				concrete->get_core_data().relation);
659
660
	  break;
	case 2:
661
662
663
	  if (concrete)
	    spot::bdd_print_dot(std::cout, concrete->get_dict(),
				concrete->
664
				get_core_data().acceptance_conditions);
665
666
	  break;
	case 3:
667
668
669
	  if (concrete)
	    spot::bdd_print_set(std::cout, concrete->get_dict(),
				concrete->get_core_data().relation);
670
671
	  break;
	case 4:
672
673
674
	  if (concrete)
	    spot::bdd_print_set(std::cout, concrete->get_dict(),
				concrete->
675
				get_core_data().acceptance_conditions);
676
	  break;
677
	case 5:
678
	  a->get_dict()->dump(std::cout);
679
	  break;
680
681
682
	case 6:
	  spot::lbtt_reachable(std::cout, a);
	  break;
683
684
685
	case 7:
	  spot::tgba_save_reachable(std::cout, a);
	  break;
686
	case 8:
687
688
689
690
691
692
693
	  {
	    assert(degeneralize_opt == DegenSBA);
	    const spot::tgba_sba_proxy* s =
	      static_cast<const spot::tgba_sba_proxy*>(degeneralized);
	    spot::never_claim_reachable(std::cout, s, f);
	    break;
	  }
694
695
696
	default:
	  assert(!"unknown output option");
	}
697

698
      spot::emptiness_check* ec = 0;
699
700
701
702
      switch (echeck)
	{
	case None:
	  break;
martinez's avatar
martinez committed
703

704
	case Couvreur:
705
706
707
	  ec = new spot::couvreur99_check(a);
	  break;

708
	case Couvreur2:
709
	  ec = new spot::couvreur99_check_shy(a, couv_group);
710
	  break;
martinez's avatar
martinez committed
711

712
713
        case MagicSearch:
          if (bit_state_hashing)
714
            ec = spot::bit_state_hashing_magic_search(a, heap_size);
715
          else
716
            ec = spot::explicit_magic_search(a);
717
          break;
718

719
720
        case Se05Search:
          if (bit_state_hashing)
721
            ec = spot::bit_state_hashing_se05_search(a, heap_size);
722
          else
723
            ec = spot::explicit_se05_search(a);
724
          break;
725
726
727
728
729

	case Tau03Search:
          if (a->number_of_acceptance_conditions() == 0)
            {
              std::cout << "To apply tau03_search, the automaton must have at "
730
                        << "least one accepting condition. Try with another "
731
732
733
734
735
736
                        << "algorithm." << std::endl;
            }
          else
            {
              ec = spot::explicit_tau03_search(a);
            }
737
          break;
738
	case Tau03OptSearch:
739
          ec = spot::explicit_tau03_opt_search(a);
740
	  break;
741
742
743
	case Gv04:
	  ec = spot::explicit_gv04_check(a);
	  break;
744
	}
martinez's avatar
martinez committed
745

746
747
748
749
750
      if (ec)
	{
	  do
	    {
	      spot::emptiness_check_result* res = ec->check();
751
	      if (!graph_run_opt && !graph_run_tgba_opt)
752
		ec->print_stats(std::cout);
753
754
	      if (expect_counter_example != !!res &&
                      (!bit_state_hashing || !expect_counter_example))
755
756
757
758
		exit_code = 1;

	      if (!res)
		{
759
760
761
762
763
764
765
766
767
768
769
                  std::cout << "no accepting run found";
                  if (bit_state_hashing && expect_counter_example)
                    {
                      std::cout << " even if expected" << std::endl;
                      std::cout << "this is maybe due to the use of the bit "
                                << "state hashing technic" << std::endl;
                      std::cout << "you can try to increase the heap size "
                                << "or use an explicit storage" << std::endl;
                    }
                  std::cout << std::endl;
                  break;
770
771
772
773
774
775
776
		}
	      else
		{

		  spot::tgba_run* run = res->accepting_run();
		  if (!run)
		    {
777
		      std::cout << "an accepting run exists" << std::endl;
778
779
780
		    }
		  else
		    {
781
		      if (opt_reduce)
782
			{
783
784
			  spot::tgba_run* redrun =
			    spot::reduce_run(res->automaton(), run);
785
			  delete run;
786
			  run = redrun;
787
			}
788
789
790
		      if (graph_run_opt)
			{
			  spot::tgba_run_dotty_decorator deco(run);
791
			  spot::dotty_reachable(std::cout, a, &deco);
792
			}
793
794
795
796
797
798
		      else if (graph_run_tgba_opt)
			{
			  spot::tgba* ar = spot::tgba_run_to_tgba(a, run);
			  spot::dotty_reachable(std::cout, ar);
			  delete ar;
			}
799
800
		      else
			{
801
802
			  spot::print_tgba_run(std::cout, a, run);
			  if (!spot::replay_tgba_run(std::cout, a, run, true))
803
804
			    exit_code = 1;
			}
805
806
807
808
809
		      delete run;
		    }
		}
	      delete res;
	    }
810
	  while (search_many);
811
	  delete ec;
martinez's avatar
martinez committed
812
813
	}

814
815
      if (f)
        spot::ltl::destroy(f);
816
817
      delete product;
      delete system;
818
819
820
      delete expl;
      delete degeneralized;
      delete aut_red;
821
      delete to_free;
822
823
824
825
826
827
828
829
830
831
    }
  else
    {
      exit_code = 1;
    }

  assert(spot::ltl::atomic_prop::instance_count() == 0);
  assert(spot::ltl::unop::instance_count() == 0);
  assert(spot::ltl::binop::instance_count() == 0);
  assert(spot::ltl::multop::instance_count() == 0);
832
  delete dict;
833
834
  return exit_code;
}