ltl2tgba.cc 15.8 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/dotty.hh"
36
#include "tgbaalgos/lbtt.hh"
37
#include "tgba/tgbatba.hh"
38
#include "tgbaalgos/magic.hh"
39
40
#include "tgbaalgos/gtec/gtec.hh"
#include "tgbaalgos/gtec/ce.hh"
41
#include "tgbaparse/public.hh"
42
#include "tgbaalgos/dupexp.hh"
43
#include "tgbaalgos/neverclaim.hh"
44
#include "tgbaalgos/reductgba_sim.hh"
45
#include "tgbaalgos/replayrun.hh"
46

47
48
49
void
syntax(char* prog)
{
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
50
  std::cerr << "Usage: "<< prog << " [OPTIONS...] formula" << std::endl
51
            << "       "<< prog << " -F [OPTIONS...] file" << std::endl
52
            << "       "<< prog << " -X [OPTIONS...] file" << std::endl
Alexandre Duret-Lutz's avatar
spacing    
Alexandre Duret-Lutz committed
53
	    << std::endl
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
54
	    << "Options:" << std::endl
martinez's avatar
martinez committed
55
	    << "  -a    display the acceptance_conditions BDD, not the "
56
	    << "reachability graph"
57
	    << std::endl
martinez's avatar
martinez committed
58
59
60
	    << "  -A    same as -a, but as a set" << std::endl
	    << "  -d    turn on traces during parsing" << std::endl
	    << "  -D    degeneralize the automaton" << std::endl
61
	    << "  -eALGO emptiness-check, expect and compute an accepting run"
62
	    << std::endl
63
	    << "  -EALGO emptiness-check, expect no accepting run" << std::endl
martinez's avatar
martinez committed
64
65
66
67
            << "  -f    use Couvreur's FM algorithm for translation"
	    << std::endl
            << "  -F    read the formula from the file" << std::endl
            << "  -L    fair-loop approximation (implies -f)" << std::endl
martinez's avatar
martinez committed
68
69
	    << "  -N    display the never clain for Spin "
	    << "(implies -D)" << std::endl
martinez's avatar
martinez committed
70
71
            << "  -p    branching postponement (implies -f)" << std::endl
	    << "  -r    display the relation BDD, not the reachability graph"
72
	    << std::endl
martinez's avatar
martinez committed
73
74
	    << "  -r1   reduce formula using basic rewriting" << std::endl
	    << "  -r2   reduce formula using class of eventuality and "
75
	    << "and universality" << std::endl
martinez's avatar
martinez committed
76
	    << "  -r3   reduce formula using implication between "
77
	    << "sub-formulae" << std::endl
martinez's avatar
martinez committed
78
79
80
	    << "  -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
martinez's avatar
martinez committed
81
	    << "  -R1q  use direct simulation to merge some state "
martinez's avatar
martinez committed
82
	    << "(use -L for more reduction)"
83
	    << std::endl
martinez's avatar
martinez committed
84
	    << "  -R1t  use direct simulation to remove some transition "
martinez's avatar
martinez committed
85
	    << "(use -L for more reduction)"
86
	    << std::endl
martinez's avatar
martinez committed
87
88
89
90
91
92
	    << "  -R2q  use delayed simulation to merge some state "
	    << "(the automaton must be degeneralised)"
	    << std::endl
	    << "  -R2t  use delayed simulation to remove some transition "
	    << "(the automaton must be degeneralised)"
	    << std::endl
martinez's avatar
martinez committed
93
	    << "  -R3   use SCC to reduce the automata"
94
	    << std::endl
martinez's avatar
martinez committed
95
	    << "  -Rd   display the simulation relation"
96
	    << std::endl
martinez's avatar
martinez committed
97
	    << "  -RD   display the parity game (dot format)"
98
	    << std::endl
martinez's avatar
martinez committed
99
	    << "  -s    convert to explicit automata, and number states "
100
	    << "in DFS order" << std::endl
martinez's avatar
martinez committed
101
	    << "  -S    convert to explicit automata, and number states "
102
	    << "in BFS order" << std::endl
martinez's avatar
martinez committed
103
	    << "  -t    display reachable states in LBTT's format" << std::endl
104
105
            << "  -U[PROPS]  consider atomic properties PROPS as exclusive "
	    << "events (implies -f)" << std::endl
martinez's avatar
martinez committed
106
107
108
	    << "  -v    display the BDD variables used by the automaton"
	    << std::endl
            << "  -x    try to produce a more deterministic automata "
109
	    << "(implies -f)" << std::endl
martinez's avatar
martinez committed
110
	    << "  -X    do not compute an automaton, read it from a file"
111
	    << std::endl
martinez's avatar
martinez committed
112
	    << "  -y    do not merge states with same symbolic representation "
113
114
115
116
117
118
119
120
	    << "(implies -f)" << std::endl
	    << std::endl
	    << "Where ALGO should be one of:" << std::endl
	    << "  couvreur99" << std::endl
	    << "  couvreur99_shy" << std::endl
	    << "  magic_search" << std::endl
	    << "  magic_search_repeated" << std::endl
    ;
121
122
123
124
125
126
127
128
  exit(2);
}

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

129
  bool debug_opt = false;
130
  bool degeneralize_opt = false;
131
  bool fm_opt = false;
132
  bool fm_exprop_opt = false;
133
  bool fm_symb_merge_opt = true;
134
  bool file_opt = false;
135
  int output = 0;
136
  int formula_index = 0;
137
  std::string echeck_algo;
138
  enum { None, Couvreur, Couvreur2, MagicSearch } echeck = None;
139
  enum { NoneDup, BFS, DFS } dupexp = NoneDup;
140
141
  bool magic_many = false;
  bool expect_counter_example = false;
142
  bool from_file = false;
143
  int reduc_aut = spot::Reduce_None;
144
  int redopt = spot::ltl::Reduce_None;
145
146
  bool display_reduce_form = false;
  bool display_rel_sim = false;
147
  bool display_parity_game = false;
148
  bool post_branching = false;
149
  bool fair_loop_approx = false;
150
151
  spot::ltl::environment& env(spot::ltl::default_environment::instance());
  spot::ltl::atomic_prop_set* unobservables = 0;
152

153
  for (;;)
154
    {
155
      if (argc < formula_index + 2)
156
	syntax(argv[0]);
157
158
159

      ++formula_index;

160
161
162
163
164
165
166
167
168
      if (!strcmp(argv[formula_index], "-a"))
	{
	  output = 2;
	}
      else if (!strcmp(argv[formula_index], "-A"))
	{
	  output = 4;
	}
      else if (!strcmp(argv[formula_index], "-d"))
169
170
171
	{
	  debug_opt = true;
	}
172
173
174
175
      else if (!strcmp(argv[formula_index], "-D"))
	{
	  degeneralize_opt = true;
	}
176
      else if (!strncmp(argv[formula_index], "-e", 2))
177
	{
178
179
180
181
	  if (argv[formula_index][2] != 0)
	    echeck_algo = argv[formula_index] + 2;
	  else
	    echeck_algo = "couvreur99";
182
183
184
	  expect_counter_example = true;
	  output = -1;
	}
185
      else if (!strncmp(argv[formula_index], "-E", 2))
186
	{
187
188
189
190
	  if (argv[formula_index][2] != 0)
	    echeck_algo = argv[formula_index] + 2;
	  else
	    echeck_algo = "couvreur99";
191
192
193
	  expect_counter_example = false;
	  output = -1;
	}
194
195
196
197
198
199
200
201
      else if (!strcmp(argv[formula_index], "-f"))
	{
	  fm_opt = true;
	}
      else if (!strcmp(argv[formula_index], "-F"))
	{
	  file_opt = true;
	}
202
203
204
205
206
      else if (!strcmp(argv[formula_index], "-L"))
	{
	  fair_loop_approx = true;
	  fm_opt = true;
	}
martinez's avatar
martinez committed
207
208
209
210
211
      else if (!strcmp(argv[formula_index], "-N"))
	{
	  degeneralize_opt = true;
	  output = 8;
	}
212
213
214
215
216
      else if (!strcmp(argv[formula_index], "-p"))
	{
	  post_branching = true;
	  fm_opt = true;
	}
217
218
      else if (!strcmp(argv[formula_index], "-r"))
	{
219
220
	  output = 1;
	}
221
222
223
224
225
226
      else if (!strcmp(argv[formula_index], "-r1"))
	{
	  redopt |= spot::ltl::Reduce_Basics;
	}
      else if (!strcmp(argv[formula_index], "-r2"))
	{
227
	  redopt |= spot::ltl::Reduce_Eventuality_And_Universality;
228
229
230
	}
      else if (!strcmp(argv[formula_index], "-r3"))
	{
231
	  redopt |= spot::ltl::Reduce_Syntactic_Implications;
232
233
234
235
236
	}
      else if (!strcmp(argv[formula_index], "-r4"))
	{
	  redopt |= spot::ltl::Reduce_All;
	}
237
238
239
      else if (!strcmp(argv[formula_index], "-R"))
	{
	  output = 3;
240
	}
martinez's avatar
martinez committed
241
242
243
244
245
246
247
248
249
      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"))
250
	{
martinez's avatar
martinez committed
251
	  reduc_aut |= spot::Reduce_quotient_Del_Sim;
252
	}
martinez's avatar
martinez committed
253
      else if (!strcmp(argv[formula_index], "-R2t"))
254
	{
martinez's avatar
martinez committed
255
	  reduc_aut |= spot::Reduce_transition_Del_Sim;
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
	}
      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;
	}
273
274
275
276
277
278
279
280
      else if (!strcmp(argv[formula_index], "-s"))
	{
	  dupexp = DFS;
	}
      else if (!strcmp(argv[formula_index], "-S"))
	{
	  dupexp = BFS;
	}
281
282
283
284
      else if (!strcmp(argv[formula_index], "-t"))
	{
	  output = 6;
	}
285
286
287
288
289
      else if (!strncmp(argv[formula_index], "-U", 2))
	{
	  unobservables = new spot::ltl::atomic_prop_set;
	  fm_opt = true;
	  // Parse -U's argument.
290
	  const char* tok = strtok(argv[formula_index] + 2, ", \t;");
291
292
293
294
	  while (tok)
	    {
	      unobservables->insert
		(static_cast<spot::ltl::atomic_prop*>(env.require(tok)));
295
	      tok = strtok(0, ", \t;");
296
297
	    }
	}
298
299
300
301
      else if (!strcmp(argv[formula_index], "-v"))
	{
	  output = 5;
	}
302
303
304
305
306
      else if (!strcmp(argv[formula_index], "-x"))
	{
	  fm_opt = true;
	  fm_exprop_opt = true;
	}
307
308
309
310
      else if (!strcmp(argv[formula_index], "-X"))
	{
	  from_file = true;
	}
311
312
313
314
315
      else if (!strcmp(argv[formula_index], "-y"))
	{
	  fm_opt = true;
	  fm_symb_merge_opt = false;
	}
316
317
318
319
      else
	{
	  break;
	}
320
321
    }

322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
  if (echeck_algo == "couvreur99")
    {
      echeck = Couvreur;
    }
  else if (echeck_algo == "couvreur99_shy")
    {
      echeck = Couvreur2;
    }
  else if (echeck_algo == "magic_search")
    {
      echeck = MagicSearch;
      degeneralize_opt = true;
    }
  else if (echeck_algo == "magic_search_repeated")
    {
      echeck = MagicSearch;
      degeneralize_opt = true;
      magic_many = true;
    }
  else
    {
      std::cerr << "unknown emptiness-check: " << echeck_algo << std::endl;
      syntax(argv[0]);
    }


348
349
350
351
  std::string input;

  if (file_opt)
    {
352
      if (strcmp(argv[formula_index], "-"))
353
	{
354
	  std::ifstream fin(argv[formula_index]);
355
	  if (!fin)
356
357
358
359
	    {
	      std::cerr << "Cannot open " << argv[formula_index] << std::endl;
	      exit(2);
	    }
360

361
	  if (!std::getline(fin, input, '\0'))
362
363
364
365
366
367
	    {
	      std::cerr << "Cannot read " << argv[formula_index] << std::endl;
	      exit(2);
	    }
	}
      else
368
	{
369
	  std::getline(std::cin, input, '\0');
370
371
372
373
374
375
376
	}
    }
  else
    {
      input = argv[formula_index];
    }

377
  spot::bdd_dict* dict = new spot::bdd_dict();
378
379
380
381
382
383
384
385
386

  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)
387
    {
388
389
390
391
      spot::tgba_bdd_concrete* concrete = 0;
      spot::tgba* to_free = 0;
      spot::tgba* a = 0;

392
393
394
      if (from_file)
	{
	  spot::tgba_parse_error_list pel;
395
396
	  spot::tgba_explicit* e;
	  to_free = a = e = spot::tgba_parse(input, pel, dict, env, debug_opt);
397
398
	  if (spot::format_tgba_parse_errors(std::cerr, pel))
	    return 2;
399
	  e->merge_transitions();
400
	}
401
      else
402
	{
403
	  if (redopt != spot::ltl::Reduce_None)
404
	    {
405
406
407
	      spot::ltl::formula* t = spot::ltl::reduce(f, redopt);
	      spot::ltl::destroy(f);
	      f = t;
408
409
	      if (display_reduce_form)
		std::cout << spot::ltl::to_string(f) << std::endl;
410
	    }
411

412
	  if (fm_opt)
413
	    to_free = a = spot::ltl_to_tgba_fm(f, dict, fm_exprop_opt,
414
					       fm_symb_merge_opt,
415
					       post_branching,
416
					       fair_loop_approx, unobservables);
417
418
419
	  else
	    to_free = a = concrete = spot::ltl_to_tgba_lacim(f, dict);
	}
420

421
422
423
424
      spot::tgba_tba_proxy* degeneralized = 0;
      if (degeneralize_opt)
	a = degeneralized = new spot::tgba_tba_proxy(a);

425
426
427
428
      spot::tgba_reduc* aut_red = 0;
      if (reduc_aut != spot::Reduce_None)
	{
	  a = aut_red = new spot::tgba_reduc(a);
429
430
431
432

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

martinez's avatar
martinez committed
433
434
435
436
	  if (reduc_aut & (spot::Reduce_quotient_Dir_Sim |
			   spot::Reduce_transition_Dir_Sim |
			   spot::Reduce_quotient_Del_Sim |
			   spot::Reduce_transition_Del_Sim))
437
	    {
martinez's avatar
martinez committed
438
439
440
441
442
	      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))
443
444
445
446
		rel_dir =
		  spot::get_direct_relation_simulation(a,
						       std::cout,
						       display_parity_game);
martinez's avatar
martinez committed
447
448
	      else if (reduc_aut & (spot::Reduce_quotient_Del_Sim |
				    spot::Reduce_transition_Del_Sim))
449
450
451
452
		rel_del =
		  spot::get_delayed_relation_simulation(a,
							std::cout,
							display_parity_game);
453
454

	      if (display_rel_sim)
martinez's avatar
martinez committed
455
456
457
458
459
460
		{
		  if (rel_dir)
		    aut_red->display_rel_sim(rel_dir, std::cout);
		  if (rel_del)
		    aut_red->display_rel_sim(rel_del, std::cout);
		}
461

martinez's avatar
martinez committed
462
463
464
465
466
467
468
469
470
471
472
473
474
	      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);
475
476
477
	    }
	}

478
479
480
481
482
483
484
485
486
487
488
489
490
      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;
	}

491
492
      switch (output)
	{
493
494
495
	case -1:
	  /* No output.  */
	  break;
496
497
498
499
	case 0:
	  spot::dotty_reachable(std::cout, a);
	  break;
	case 1:
500
501
502
	  if (concrete)
	    spot::bdd_print_dot(std::cout, concrete->get_dict(),
				concrete->get_core_data().relation);
503
504
	  break;
	case 2:
505
506
507
	  if (concrete)
	    spot::bdd_print_dot(std::cout, concrete->get_dict(),
				concrete->
508
				get_core_data().acceptance_conditions);
509
510
	  break;
	case 3:
511
512
513
	  if (concrete)
	    spot::bdd_print_set(std::cout, concrete->get_dict(),
				concrete->get_core_data().relation);
514
515
	  break;
	case 4:
516
517
518
	  if (concrete)
	    spot::bdd_print_set(std::cout, concrete->get_dict(),
				concrete->
519
				get_core_data().acceptance_conditions);
520
	  break;
521
	case 5:
522
	  a->get_dict()->dump(std::cout);
523
	  break;
524
525
526
	case 6:
	  spot::lbtt_reachable(std::cout, a);
	  break;
527
528
529
	case 8:
	  spot::never_claim_reachable(std::cout, degeneralized, f);
	  break;
530
531
532
	default:
	  assert(!"unknown output option");
	}
533

534
535
      spot::emptiness_check* ec = 0;
      spot::tgba* ec_a = 0;
536
537
538
539
      switch (echeck)
	{
	case None:
	  break;
martinez's avatar
martinez committed
540

541
	case Couvreur:
542
543
544
545
	  ec_a = a;
	  ec = new spot::couvreur99_check(a);
	  break;

546
	case Couvreur2:
547
548
	  ec_a = a;
	  ec = new spot::couvreur99_check_shy(a);
549
	  break;
martinez's avatar
martinez committed
550

551
	case MagicSearch:
552
553
	  ec_a = degeneralized;
	  ec = new spot::magic_search(degeneralized);
554
	  break;
555
	}
martinez's avatar
martinez committed
556

557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
      if (ec)
	{
	  do
	    {
	      spot::emptiness_check_result* res = ec->check();
	      if (expect_counter_example != !!res)
		exit_code = 1;

	      if (!res)
		{
		  std::cout << "no accepting run found" << std::endl;
		  break;
		}
	      else
		{

		  spot::tgba_run* run = res->accepting_run();
		  if (!run)
		    {
576
		      std::cout << "an accepting run exists" << std::endl;
577
578
579
580
		    }
		  else
		    {
		      spot::print_tgba_run(std::cout, run, ec_a);
581
582
		      if (!spot::replay_tgba_run(std::cout, ec_a, run))
			exit_code = 1;
583
584
585
586
587
588
589
		      delete run;
		    }
		}
	      delete res;
	    }
	  while (magic_many);
	  delete ec;
martinez's avatar
martinez committed
590
591
	}

592
593
      if (f)
        spot::ltl::destroy(f);
594
595
      if (expl)
	delete expl;
596
597
      if (degeneralize_opt)
	delete degeneralized;
598
599
      if (aut_red)
	delete aut_red;
600

601
      delete to_free;
602
603
604
605
606
607
608
609
610
611
    }
  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);
612
  delete dict;
613
614
  return exit_code;
}