ltl2tgba.cc 12.7 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/reducform.hh"
28
29
#include "ltlast/allnodes.hh"
#include "ltlparse/public.hh"
30
#include "tgbaalgos/ltl2tgba_lacim.hh"
31
#include "tgbaalgos/ltl2tgba_fm.hh"
32
#include "tgba/bddprint.hh"
33
#include "tgbaalgos/dotty.hh"
34
#include "tgbaalgos/lbtt.hh"
35
#include "tgba/tgbatba.hh"
36
#include "tgbaalgos/magic.hh"
37
38
#include "tgbaalgos/gtec/gtec.hh"
#include "tgbaalgos/gtec/ce.hh"
39
#include "tgbaparse/public.hh"
40
#include "tgbaalgos/dupexp.hh"
41
#include "tgbaalgos/neverclaim.hh"
42
43
44
45

void
syntax(char* prog)
{
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
46
  std::cerr << "Usage: "<< prog << " [OPTIONS...] formula" << std::endl
47
            << "       "<< prog << " -F [OPTIONS...] file" << std::endl
48
            << "       "<< prog << " -X [OPTIONS...] file" << std::endl
Alexandre Duret-Lutz's avatar
spacing    
Alexandre Duret-Lutz committed
49
	    << std::endl
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
50
	    << "Options:" << std::endl
51
	    << "  -a   display the acceptance_conditions BDD, not the "
52
	    << "reachability graph"
53
	    << std::endl
54
	    << "  -A   same as -a, but as a set" << std::endl
55
	    << "  -d   turn on traces during parsing" << std::endl
56
	    << "  -D   degeneralize the automaton" << std::endl
57
58
	    << "  -e   emptiness-check (Couvreur), expect and compute "
	    << "a counter-example" << std::endl
59
60
	    << "  -e2  emptiness-check (Couvreur variant), expect and compute "
	    << "a counter-example" << std::endl
61
62
	    << "  -E   emptiness-check (Couvreur), expect no counter-example "
	    << std::endl
63
64
	    << "  -E2  emptiness-check (Couvreur variant), expect no "
	    << "counter-example " << std::endl
65
66
67
            << "  -f   use Couvreur's FM algorithm for translation"
	    << std::endl
            << "  -F   read the formula from the file" << std::endl
68
            << "  -L   fair-loop approximation (implies -f)" << std::endl
69
70
71
72
73
74
	    << "  -m   magic-search (implies -D), expect a counter-example"
	    << std::endl
	    << "  -M   magic-search (implies -D), expect no counter-example"
	    << std::endl
	    << "  -n   same as -m, but display more counter-examples"
	    << std::endl
75
76
	    << "  -N   display the never clain for Spin "
	    << "(implies -D)" << std::endl
77
            << "  -p   branching postponement (implies -f)" << std::endl
78
	    << "  -r   display the relation BDD, not the reachability graph"
79
	    << std::endl
80
81
82
83
84
85
	    << "  -r1  reduce formula using basic rewriting" << std::endl
	    << "  -r2  reduce formula using class of eventuality and "
	    << "and universality" << std::endl
	    << "  -r3  reduce formula using implication between "
	    << "sub-formulae" << std::endl
	    << "  -r4  reduce formula using all rules" << std::endl
86
	    << "  -R   same as -r, but as a set" << std::endl
87
88
89
90
	    << "  -s   convert to explicit automata, and number states "
	    << "in DFS order" << std::endl
	    << "  -S   convert to explicit automata, and number states "
	    << "in BFS order" << std::endl
91
	    << "  -t   display reachable states in LBTT's format" << std::endl
92
93
	    << "  -T   display reachable states in LBTT's format w/o "
	    << "acceptance conditions" << std::endl
Alexandre Duret-Lutz's avatar
spacing    
Alexandre Duret-Lutz committed
94
	    << "  -v   display the BDD variables used by the automaton"
95
	    << std::endl
96
97
            << "  -x   try to produce a more deterministic automata "
	    << "(implies -f)" << std::endl
98
	    << "  -X   do not compute an automaton, read it from a file"
99
100
	    << std::endl
	    << "  -y   do not merge states with same symbolic representation "
101
	    << "(implies -f)" << std::endl;
102
103
104
105
106
107
108
109
  exit(2);
}

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

110
  bool debug_opt = false;
111
  bool degeneralize_opt = false;
112
  bool fm_opt = false;
113
  bool fm_exprop_opt = false;
114
  bool fm_symb_merge_opt = true;
115
  bool file_opt = false;
116
  int output = 0;
117
  int formula_index = 0;
118
  enum { None, Couvreur, Couvreur2, MagicSearch } echeck = None;
119
  enum { NoneDup, BFS, DFS } dupexp = NoneDup;
120
121
  bool magic_many = false;
  bool expect_counter_example = false;
122
  bool from_file = false;
123
124
125
126
  bool reduc_r1 = false;
  bool reduc_r2 = false;
  bool reduc_r3 = false;
  bool reduc_r4 = false;
127
  bool post_branching = false;
128
  bool fair_loop_approx = false;
129

130
  for (;;)
131
    {
132
      if (argc < formula_index + 2)
133
	syntax(argv[0]);
134
135
136

      ++formula_index;

137
138
139
140
141
142
143
144
145
      if (!strcmp(argv[formula_index], "-a"))
	{
	  output = 2;
	}
      else if (!strcmp(argv[formula_index], "-A"))
	{
	  output = 4;
	}
      else if (!strcmp(argv[formula_index], "-d"))
146
147
148
	{
	  debug_opt = true;
	}
149
150
151
152
      else if (!strcmp(argv[formula_index], "-D"))
	{
	  degeneralize_opt = true;
	}
153
154
155
156
157
158
      else if (!strcmp(argv[formula_index], "-e"))
	{
	  echeck = Couvreur;
	  expect_counter_example = true;
	  output = -1;
	}
159
160
161
162
163
164
      else if (!strcmp(argv[formula_index], "-e2"))
	{
	  echeck = Couvreur2;
	  expect_counter_example = true;
	  output = -1;
	}
165
166
167
168
169
170
      else if (!strcmp(argv[formula_index], "-E"))
	{
	  echeck = Couvreur;
	  expect_counter_example = false;
	  output = -1;
	}
171
172
173
174
175
176
      else if (!strcmp(argv[formula_index], "-E2"))
	{
	  echeck = Couvreur2;
	  expect_counter_example = false;
	  output = -1;
	}
177
178
179
180
181
182
183
184
      else if (!strcmp(argv[formula_index], "-f"))
	{
	  fm_opt = true;
	}
      else if (!strcmp(argv[formula_index], "-F"))
	{
	  file_opt = true;
	}
185
186
187
188
189
      else if (!strcmp(argv[formula_index], "-L"))
	{
	  fair_loop_approx = true;
	  fm_opt = true;
	}
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
      else if (!strcmp(argv[formula_index], "-m"))
	{
	  echeck = MagicSearch;
	  degeneralize_opt = true;
	  expect_counter_example = true;
	  output = -1;
	}
      else if (!strcmp(argv[formula_index], "-M"))
	{
	  echeck = MagicSearch;
	  degeneralize_opt = true;
	  expect_counter_example = false;
	  output = -1;
	}
      else if (!strcmp(argv[formula_index], "-n"))
	{
	  echeck = MagicSearch;
	  degeneralize_opt = true;
	  expect_counter_example = true;
	  output = -1;
	  magic_many = true;
	}
212
213
214
215
216
      else if (!strcmp(argv[formula_index], "-N"))
	{
	  degeneralize_opt = true;
	  output = 8;
	}
217
218
219
220
221
      else if (!strcmp(argv[formula_index], "-p"))
	{
	  post_branching = true;
	  fm_opt = true;
	}
222
223
      else if (!strcmp(argv[formula_index], "-r"))
	{
224
225
226
227
228
	  output = 1;
	}
      else if (!strcmp(argv[formula_index], "-R"))
	{
	  output = 3;
229
	}
230
231
232
233
234
235
236
237
      else if (!strcmp(argv[formula_index], "-s"))
	{
	  dupexp = DFS;
	}
      else if (!strcmp(argv[formula_index], "-S"))
	{
	  dupexp = BFS;
	}
238
239
240
241
      else if (!strcmp(argv[formula_index], "-t"))
	{
	  output = 6;
	}
242
243
244
245
      else if (!strcmp(argv[formula_index], "-T"))
	{
	  output = 7;
	}
246
247
248
249
      else if (!strcmp(argv[formula_index], "-v"))
	{
	  output = 5;
	}
250
251
252
253
254
      else if (!strcmp(argv[formula_index], "-x"))
	{
	  fm_opt = true;
	  fm_exprop_opt = true;
	}
255
256
257
258
      else if (!strcmp(argv[formula_index], "-X"))
	{
	  from_file = true;
	}
259
260
261
262
263
      else if (!strcmp(argv[formula_index], "-y"))
	{
	  fm_opt = true;
	  fm_symb_merge_opt = false;
	}
264
265
266
267
268
269
270
271
272
273
274
275
276
      else if (!strcmp(argv[formula_index], "-r1"))
	{
	  reduc_r1 = true;
	}
      else if (!strcmp(argv[formula_index], "-r2"))
	{
	  reduc_r2 = true;
	}
      else if (!strcmp(argv[formula_index], "-r3"))
	{
	  reduc_r3 = true;
	}
      else if (!strcmp(argv[formula_index], "-r4"))
277
	{
278
279
	  reduc_r4 = true;
	}
280
281
282
283
      else
	{
	  break;
	}
284
285
    }

286
287
288
289
  std::string input;

  if (file_opt)
    {
290
      if (strcmp(argv[formula_index], "-"))
291
	{
292
	  std::ifstream fin(argv[formula_index]);
293
	  if (!fin)
294
295
296
297
	    {
	      std::cerr << "Cannot open " << argv[formula_index] << std::endl;
	      exit(2);
	    }
298

299
	  if (!std::getline(fin, input, '\0'))
300
301
302
303
304
305
	    {
	      std::cerr << "Cannot read " << argv[formula_index] << std::endl;
	      exit(2);
	    }
	}
      else
306
	{
307
	  std::getline(std::cin, input, '\0');
308
309
310
311
312
313
314
	}
    }
  else
    {
      input = argv[formula_index];
    }

315
  spot::ltl::environment& env(spot::ltl::default_environment::instance());
316
  spot::bdd_dict* dict = new spot::bdd_dict();
317
318
319
320
321
322
323
324
325

  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)
326
    {
327
328
329
330
      spot::tgba_bdd_concrete* concrete = 0;
      spot::tgba* to_free = 0;
      spot::tgba* a = 0;

331
332
333
      if (from_file)
	{
	  spot::tgba_parse_error_list pel;
334
335
	  spot::tgba_explicit* e;
	  to_free = a = e = spot::tgba_parse(input, pel, dict, env, debug_opt);
336
337
	  if (spot::format_tgba_parse_errors(std::cerr, pel))
	    return 2;
338
	  e->merge_transitions();
339
	}
340
      else
341
	{
342

343
	  spot::ltl::formula* ftmp = f;
344
	  if (reduc_r4)
345
346
347
348
349
	    {
	      f = spot::ltl::reduce(f);
	    }
	  else if (reduc_r1 | reduc_r2 | reduc_r3)
	    {
350
	      spot::ltl::option o = spot::ltl::BRI;
351
	      if (reduc_r1 & !reduc_r2 & !reduc_r3)
352
		o = spot::ltl::Base;
353
	      if (!reduc_r1 & reduc_r2 & !reduc_r3)
354
		o = spot::ltl::EventualUniversal;
355
356
357
	      if (reduc_r1 & reduc_r2 & !reduc_r3)
		o = spot::ltl::EventualUniversalBase;
	      if (!reduc_r1 & !reduc_r2 & reduc_r3)
358
		o = spot::ltl::Inf;
359
360
361
362
363
	      if (reduc_r1 & !reduc_r2 & reduc_r3)
		o = spot::ltl::InfBase;
	      if (!reduc_r1 & reduc_r2 & reduc_r3)
		o = spot::ltl::InfEventualUniversal;

364
365
	      f = spot::ltl::reduce(f, o);
	    }
366

367
	  if (fm_opt)
368
	    to_free = a = spot::ltl_to_tgba_fm(f, dict, fm_exprop_opt,
369
					       fm_symb_merge_opt,
370
371
					       post_branching,
					       fair_loop_approx);
372
373
	  else
	    to_free = a = concrete = spot::ltl_to_tgba_lacim(f, dict);
374

375
376
377
378
	  if (reduc_r1 || reduc_r2 || reduc_r3 || reduc_r4)
	    {
	      spot::ltl::destroy(ftmp);
	    }
379
	}
380

381
      spot::tgba_tba_proxy* degeneralized = 0;
382
383
384
      if (degeneralize_opt)
	a = degeneralized = new spot::tgba_tba_proxy(a);

385
386
387
388
389
390
391
392
393
394
395
396
397
      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;
	}

398
399
      switch (output)
	{
400
401
402
	case -1:
	  /* No output.  */
	  break;
403
404
405
406
	case 0:
	  spot::dotty_reachable(std::cout, a);
	  break;
	case 1:
407
408
409
	  if (concrete)
	    spot::bdd_print_dot(std::cout, concrete->get_dict(),
				concrete->get_core_data().relation);
410
411
	  break;
	case 2:
412
413
414
	  if (concrete)
	    spot::bdd_print_dot(std::cout, concrete->get_dict(),
				concrete->
415
				get_core_data().acceptance_conditions);
416
417
	  break;
	case 3:
418
419
420
	  if (concrete)
	    spot::bdd_print_set(std::cout, concrete->get_dict(),
				concrete->get_core_data().relation);
421
422
	  break;
	case 4:
423
424
425
	  if (concrete)
	    spot::bdd_print_set(std::cout, concrete->get_dict(),
				concrete->
426
				get_core_data().acceptance_conditions);
427
	  break;
428
	case 5:
429
	  a->get_dict()->dump(std::cout);
430
	  break;
431
432
433
	case 6:
	  spot::lbtt_reachable(std::cout, a);
	  break;
434
435
436
	case 7:
	  spot::nonacceptant_lbtt_reachable(std::cout, a);
	  break;
437
438
439
	case 8:
	  spot::never_claim_reachable(std::cout, degeneralized, f);
	  break;
440
441
442
	default:
	  assert(!"unknown output option");
	}
443

444
445
446
447
448
      switch (echeck)
	{
	case None:
	  break;
	case Couvreur:
449
	case Couvreur2:
450
	  {
451
	    spot::emptiness_check* ec;
452
	    if (echeck == Couvreur)
453
	      ec = new spot::emptiness_check(a);
454
	    else
455
456
457
	      ec = new spot::emptiness_check_shy(a);

	    bool res = ec->check();
458

459
460
461
462
463
	    if (expect_counter_example)
	      {
		if (res)
		  {
		    exit_code = 1;
464
		    delete ec;
465
466
		    break;
		  }
467
		spot::counter_example ce(ec->result());
468
		ce.print_result(std::cout);
469
470
471
472
473
	      }
	    else
	      {
		exit_code = !res;
	      }
474
	    delete ec;
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
	  }
	  break;
	case MagicSearch:
	  {
	    spot::magic_search ms(degeneralized);
	    bool res = ms.check();
	    if (expect_counter_example)
	      {
		if (!res)
		  {
		    exit_code = 1;
		    break;
		  }
		do
		  ms.print_result(std::cout);
		while (magic_many && ms.check());
	      }
	    else
	      {
		exit_code = res;
	      }
	  }
	  break;
	}

500
501
      if (f)
        spot::ltl::destroy(f);
502
503
      if (expl)
	delete expl;
504
505
506
      if (degeneralize_opt)
	delete degeneralized;

507
      delete to_free;
508
509
510
511
512
513
514
515
516
517
    }
  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);
518
  delete dict;
519
520
  return exit_code;
}