ltlfilt.cc 17.7 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
3
// Copyright (C) 2012, 2013, 2014 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 "common_sys.hh"
21
22
23
24
25
26

#include <cstdlib>
#include <string>
#include <iostream>
#include <fstream>
#include <argp.h>
27
#include <cstring>
28
#include "error.h"
29

30
#include "common_setup.hh"
31
#include "common_finput.hh"
32
#include "common_output.hh"
33
#include "common_cout.hh"
34
#include "common_r.hh"
35

36
37
38
#include "misc/hash.hh"
#include "ltlvisit/simplify.hh"
#include "ltlvisit/length.hh"
39
#include "ltlvisit/relabel.hh"
40
#include "ltlvisit/wmunabbrev.hh"
41
#include "ltlvisit/remove_x.hh"
42
#include "ltlvisit/apcollect.hh"
43
#include "ltlast/unop.hh"
44
#include "ltlast/multop.hh"
45
46
47
#include "tgbaalgos/ltl2tgba_fm.hh"
#include "tgbaalgos/minimize.hh"
#include "tgbaalgos/safety.hh"
48
#include "tgbaalgos/stutter_invariance.hh"
49
50

const char argp_program_doc[] ="\
51
52
53
Read a list of formulas and output them back after some optional processing.\v\
Exit status:\n\
  0  if some formulas were output (skipped syntax errors do not count)\n\
54
  1  if no formulas were output (no match)\n\
55
  2  if any error has been reported";
56

57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#define OPT_SKIP_ERRORS 1
#define OPT_DROP_ERRORS 2
#define OPT_NNF 3
#define OPT_LTL 4
#define OPT_NOX 5
#define OPT_BOOLEAN 6
#define OPT_EVENTUAL 7
#define OPT_UNIVERSAL 8
#define OPT_SYNTACTIC_SAFETY 9
#define OPT_SYNTACTIC_GUARANTEE 10
#define OPT_SYNTACTIC_OBLIGATION 11
#define OPT_SYNTACTIC_RECURRENCE 12
#define OPT_SYNTACTIC_PERSISTENCE 13
#define OPT_SAFETY 14
#define OPT_GUARANTEE 15
#define OPT_OBLIGATION 16
#define OPT_SIZE_MIN 17
#define OPT_SIZE_MAX 18
#define OPT_BSIZE_MIN 19
#define OPT_BSIZE_MAX 20
#define OPT_IMPLIED_BY 21
#define OPT_IMPLY 22
#define OPT_EQUIVALENT_TO 23
#define OPT_RELABEL 24
#define OPT_RELABEL_BOOL 25
#define OPT_REMOVE_WM 26
#define OPT_BOOLEAN_TO_ISOP 27
#define OPT_REMOVE_X 28
#define OPT_STUTTER_INSENSITIVE 29
86
#define OPT_AP_N 30
87
88
89
90
91
92
93
94
95
96
97
98
99
100

static const argp_option options[] =
  {
    /**************************************************/
    { 0, 0, 0, 0, "Error handling:", 2 },
    { "skip-errors", OPT_SKIP_ERRORS, 0, 0,
      "output erroneous lines as-is without processing", 0 },
    { "drop-errors", OPT_DROP_ERRORS, 0, 0,
      "discard erroneous lines (default)", 0 },
    { "quiet", 'q', 0, 0, "do not report syntax errors", 0 },
    /**************************************************/
    { 0, 0, 0, 0, "Transformation options:", 3 },
    { "negate", 'n', 0, 0, "negate each formula", 0 },
    { "nnf", OPT_NNF, 0, 0, "rewrite formulas in negative normal form", 0 },
101
102
103
    { "relabel", OPT_RELABEL, "abc|pnn", OPTION_ARG_OPTIONAL,
      "relabel all atomic propositions, alphabetically unless " \
      "specified otherwise", 0 },
104
105
106
    { "relabel-bool", OPT_RELABEL_BOOL, "abc|pnn", OPTION_ARG_OPTIONAL,
      "relabel Boolean subexpressions, alphabetically unless " \
      "specified otherwise", 0 },
107
108
    { "remove-wm", OPT_REMOVE_WM, 0, 0,
      "rewrite operators W and M using U and R", 0 },
109
110
111
    { "boolean-to-isop", OPT_BOOLEAN_TO_ISOP, 0, 0,
      "rewrite Boolean subformulas as irredundant sum of products "
      "(implies at least -r1)", 0 },
112
113
114
    { "remove-x", OPT_REMOVE_X, 0, 0,
      "remove X operators (valid only for stutter-insensitive properties)",
      0 },
115
116
    DECLARE_OPT_R,
    LEVEL_DOC(4),
117
118
119
    /**************************************************/
    { 0, 0, 0, 0,
      "Filtering options (matching is done after transformation):", 5 },
120
    { "ltl", OPT_LTL, 0, 0, "match only LTL formulas (no PSL operator)", 0 },
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
    { "nox", OPT_NOX, 0, 0, "match X-free formulas", 0 },
    { "boolean", OPT_BOOLEAN, 0, 0, "match Boolean formulas", 0 },
    { "eventual", OPT_EVENTUAL, 0, 0, "match pure eventualities", 0 },
    { "universal", OPT_UNIVERSAL, 0, 0, "match purely universal formulas", 0 },
    { "syntactic-safety", OPT_SYNTACTIC_SAFETY, 0, 0,
      "match syntactic-safety formulas", 0 },
    { "syntactic-guarantee", OPT_SYNTACTIC_GUARANTEE, 0, 0,
      "match syntactic-guarantee formulas", 0 },
    { "syntactic-obligation", OPT_SYNTACTIC_OBLIGATION, 0, 0,
      "match syntactic-obligation formulas", 0 },
    { "syntactic-recurrence", OPT_SYNTACTIC_RECURRENCE, 0, 0,
      "match syntactic-recurrence formulas", 0 },
    { "syntactic-persistence", OPT_SYNTACTIC_PERSISTENCE, 0, 0,
      "match syntactic-persistence formulas", 0 },
    { "safety", OPT_SAFETY, 0, 0,
      "match safety formulas (even pathological)", 0 },
    { "guarantee", OPT_GUARANTEE, 0, 0,
      "match guarantee formulas (even pathological)", 0 },
    { "obligation", OPT_OBLIGATION, 0, 0,
      "match obligation formulas (even pathological)", 0 },
    { "size-max", OPT_SIZE_MAX, "INT", 0,
      "match formulas with size <= INT", 0 },
    { "size-min", OPT_SIZE_MIN, "INT", 0,
      "match formulas with size >= INT", 0 },
    { "bsize-max", OPT_BSIZE_MAX, "INT", 0,
      "match formulas with Boolean size <= INT", 0 },
    { "bsize-min", OPT_BSIZE_MIN, "INT", 0,
      "match formulas with Boolean size >= INT", 0 },
149
150
151
152
153
154
    { "implied-by", OPT_IMPLIED_BY, "FORMULA", 0,
      "match formulas implied by FORMULA", 0 },
    { "imply", OPT_IMPLY, "FORMULA", 0,
      "match formulas implying FORMULA", 0 },
    { "equivalent-to", OPT_EQUIVALENT_TO, "FORMULA", 0,
      "match formulas equivalent to FORMULA", 0 },
155
156
157
    { "stutter-insensitive", OPT_STUTTER_INSENSITIVE, 0, 0,
      "match stutter-insensitive LTL formulas", 0 },
    { "stutter-invariant", 0, 0, OPTION_ALIAS, 0, 0 },
158
159
    { "ap", OPT_AP_N, "N", 0,
      "match formulas which use exactly N atomic propositions", 0 },
160
161
162
    { "invert-match", 'v', 0, 0, "select non-matching formulas", 0},
    { "unique", 'u', 0, 0,
      "drop formulas that have already been output (not affected by -v)", 0 },
163
    /**************************************************/
164
    { 0, 0, 0, 0, "Output options:", -20 },
165
166
167
168
169
170
171
172
    { 0, 0, 0, 0, "The FORMAT string passed to --format may use "\
      "the following interpreted sequences:", -19 },
    { "%f", 0, 0, OPTION_DOC | OPTION_NO_USAGE,
      "the formula (in the selected syntax)", 0 },
    { "%F", 0, 0, OPTION_DOC | OPTION_NO_USAGE,
      "the name of the input file", 0 },
    { "%L", 0, 0, OPTION_DOC | OPTION_NO_USAGE,
      "the original line number in the input file", 0 },
173
174
175
176
177
178
    { "%<", 0, 0, OPTION_DOC | OPTION_NO_USAGE,
      "the part of the line before the formula if it "
      "comes from a column extracted from a CSV file", 0 },
    { "%>", 0, 0, OPTION_DOC | OPTION_NO_USAGE,
      "the part of the line after the formula if it "
      "comes from a column extracted from a CSV file", 0 },
179
180
    { "%%", 0, 0, OPTION_DOC | OPTION_NO_USAGE,
      "a single %", 0 },
181
182
183
184
    { 0, 0, 0, 0, "Miscellaneous options:", -1 },
    { 0, 0, 0, 0, 0, 0 }
  };

185
186
const struct argp_child children[] =
  {
187
    { &finput_argp, 0, 0, 1 },
188
    { &output_argp, 0, 0, -20 },
189
    { &misc_argp, 0, 0, -1 },
190
191
192
    { 0, 0, 0, 0 }
  };

193
194
static bool one_match = false;

195
196
197
198
199
enum error_style_t { drop_errors, skip_errors };
static error_style_t error_style = drop_errors;
static bool quiet = false;
static bool nnf = false;
static bool negate = false;
200
static bool boolean_to_isop = false;
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
static bool unique = false;
static bool psl = false;
static bool ltl = false;
static bool nox = false;
static bool invert = false;
static bool boolean = false;
static bool universal = false;
static bool eventual = false;
static bool syntactic_safety = false;
static bool syntactic_guarantee = false;
static bool syntactic_obligation = false;
static bool syntactic_recurrence = false;
static bool syntactic_persistence = false;
static bool safety = false;
static bool guarantee = false;
static bool obligation = false;
static int size_min = -1;
static int size_max = -1;
static int bsize_min = -1;
static int bsize_max = -1;
221
222
enum relabeling_mode { NoRelabeling = 0, ApRelabeling, BseRelabeling };
static relabeling_mode relabeling = NoRelabeling;
223
static spot::ltl::relabeling_style style = spot::ltl::Abc;
224
static bool remove_wm = false;
225
226
static bool remove_x = false;
static bool stutter_insensitive = false;
227
228
static bool ap = false;
static unsigned ap_n = 0;
229

230
231
232
233
static const spot::ltl::formula* implied_by = 0;
static const spot::ltl::formula* imply = 0;
static const spot::ltl::formula* equivalent_to = 0;

234
235
236
237
238
239
static int
to_int(const char* s)
{
  char* endptr;
  int res = strtol(s, &endptr, 10);
  if (*endptr)
240
    error(2, 0, "failed to parse '%s' as an integer.", s);
241
242
243
  return res;
}

244
245
246
247
248

static const spot::ltl::formula*
parse_formula_arg(const std::string& input)
{
  spot::ltl::parse_error_list pel;
249
  const spot::ltl::formula* f = parse_formula(input, pel);
250
  if (spot::ltl::format_parse_errors(std::cerr, input, pel))
251
    error(2, 0, "parse error when parsing an argument");
252
253
254
255
256
  return f;
}



257
static int
258
parse_opt(int key, char* arg, struct argp_state*)
259
260
261
262
263
264
265
266
267
268
{
  // This switch is alphabetically-ordered.
  switch (key)
    {
    case 'n':
      negate = true;
      break;
    case 'q':
      quiet = true;
      break;
269
270
    case OPT_R:
      parse_r(arg);
271
272
273
274
275
276
277
278
279
      break;
    case 'u':
      unique = true;
      break;
    case 'v':
      invert = true;
      break;
    case ARGP_KEY_ARG:
      // FIXME: use stat() to distinguish filename from string?
280
      jobs.emplace_back(arg, true);
281
282
283
284
      break;
    case OPT_BOOLEAN:
      boolean = true;
      break;
285
286
287
    case OPT_BOOLEAN_TO_ISOP:
      boolean_to_isop = true;
      break;
288
289
290
291
292
293
294
295
296
    case OPT_BSIZE_MIN:
      bsize_min = to_int(arg);
      break;
    case OPT_BSIZE_MAX:
      bsize_max = to_int(arg);
      break;
    case OPT_DROP_ERRORS:
      error_style = drop_errors;
      break;
297
298
299
300
301
302
303
    case OPT_EQUIVALENT_TO:
      {
	if (equivalent_to)
	  error(2, 0, "only one --equivalent-to option can be given");
	equivalent_to = parse_formula_arg(arg);
	break;
      }
304
305
306
    case OPT_EVENTUAL:
      eventual = true;
      break;
307
308
309
    case OPT_GUARANTEE:
      guarantee = obligation = true;
      break;
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
    case OPT_IMPLIED_BY:
      {
	const spot::ltl::formula* i = parse_formula_arg(arg);
	// a→c∧b→c ≡ (a∨b)→c
	implied_by =
	  spot::ltl::multop::instance(spot::ltl::multop::Or, implied_by, i);
	break;
      }
    case OPT_IMPLY:
      {
	// a→b∧a→c ≡ a→(b∧c)
	const spot::ltl::formula* i = parse_formula_arg(arg);
	imply =
	  spot::ltl::multop::instance(spot::ltl::multop::And, imply, i);
	break;
      }
326
327
328
329
330
331
332
333
334
335
336
337
    case OPT_LTL:
      ltl = true;
      break;
    case OPT_NNF:
      nnf = true;
      break;
    case OPT_NOX:
      nox = true;
      break;
    case OPT_OBLIGATION:
      obligation = true;
      break;
338
    case OPT_RELABEL:
339
340
    case OPT_RELABEL_BOOL:
      relabeling = (key == OPT_RELABEL_BOOL ? BseRelabeling : ApRelabeling);
341
342
343
344
345
      if (!arg || !strncasecmp(arg, "abc", 6))
	style = spot::ltl::Abc;
      else if (!strncasecmp(arg, "pnn", 4))
	style = spot::ltl::Pnn;
      else
346
347
348
	error(2, 0, "invalid argument for --relabel%s: '%s'",
	      (key == OPT_RELABEL_BOOL ? "-bool" : ""),
	      arg);
349
      break;
350
351
352
    case OPT_REMOVE_WM:
      remove_wm = true;
      break;
353
354
355
    case OPT_REMOVE_X:
      remove_x = true;
      break;
356
357
358
359
360
361
362
363
364
365
366
367
    case OPT_SAFETY:
      safety = obligation = true;
      break;
    case OPT_SIZE_MIN:
      size_min = to_int(arg);
      break;
    case OPT_SIZE_MAX:
      size_max = to_int(arg);
      break;
    case OPT_SKIP_ERRORS:
      error_style = skip_errors;
      break;
368
369
370
    case OPT_STUTTER_INSENSITIVE:
      stutter_insensitive = true;
      break;
371
372
373
374
    case OPT_AP_N:
      ap = true;
      ap_n = to_int(arg);
      break;
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
    case OPT_SYNTACTIC_SAFETY:
      syntactic_safety = true;
      break;
    case OPT_SYNTACTIC_GUARANTEE:
      syntactic_guarantee = true;
      break;
    case OPT_SYNTACTIC_OBLIGATION:
      syntactic_obligation = true;
      break;
    case OPT_SYNTACTIC_RECURRENCE:
      syntactic_recurrence = true;
      break;
    case OPT_SYNTACTIC_PERSISTENCE:
      syntactic_persistence = true;
      break;
390
391
392
    case OPT_UNIVERSAL:
      universal = true;
      break;
393
394
395
396
397
398
    default:
      return ARGP_ERR_UNKNOWN;
    }
  return 0;
}

399
400
401
typedef
std::unordered_set<const spot::ltl::formula*,
		   const spot::ptr_hash<const spot::ltl::formula>> fset_t;
402
403
404

namespace
{
405
  class ltl_processor: public job_processor
406
407
408
409
410
  {
  public:
    spot::ltl::ltl_simplifier& simpl;
    fset_t unique_set;

411
412
413
414
415
    ~ltl_processor()
    {
      fset_t::iterator i = unique_set.begin();
      while (i != unique_set.end())
	(*i++)->destroy();
416
417
418
419
420
421
422

      if (equivalent_to)
	equivalent_to->destroy();
      if (implied_by)
	implied_by->destroy();
      if (imply)
	imply->destroy();
423
424
    }

425
426
427
428
429
430
    ltl_processor(spot::ltl::ltl_simplifier& simpl)
    : simpl(simpl)
    {
    }

    int
431
    process_string(const std::string& input,
432
433
434
		    const char* filename = 0, int linenum = 0)
    {
      spot::ltl::parse_error_list pel;
435
      const spot::ltl::formula* f = parse_formula(input, pel);
436
437
438
439
440
441

      if (!f || pel.size() > 0)
	  {
	    if (!quiet)
	      {
		if (filename)
442
		  error_at_line(0, 0, filename, linenum, "parse error:");
443
444
445
446
447
448
449
		spot::ltl::format_parse_errors(std::cerr, input, pel);
	      }

	    if (f)
	      f->destroy();

	    if (error_style == skip_errors)
450
451
452
	      std::cout << input << std::endl;
	    else
	      assert(error_style == drop_errors);
453
	    check_cout();
454
	    return !quiet;
455
	  }
456
457
      return process_formula(f, filename, linenum);
    }
458

459
460
461
462
    int
    process_formula(const spot::ltl::formula* f,
		    const char* filename = 0, int linenum = 0)
    {
463
      if (negate)
464
	f = spot::ltl::unop::instance(spot::ltl::unop::Not, f);
465

466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
      if (remove_x)
	{
	  // If simplification are enabled, we do them before and after.
	  if (simplification_level)
	    {
	      const spot::ltl::formula* res = simpl.simplify(f);
	      f->destroy();
	      f = res;
	    }

	  const spot::ltl::formula* res = spot::ltl::remove_x(f);
	  f->destroy();
	  f = res;
	}

481
      if (simplification_level || boolean_to_isop)
482
483
484
485
486
487
488
489
490
491
492
493
494
	{
	  const spot::ltl::formula* res = simpl.simplify(f);
	  f->destroy();
	  f = res;
	}

      if (nnf)
	{
	  const spot::ltl::formula* res = simpl.negative_normal_form(f);
	  f->destroy();
	  f = res;
	}

495
      switch (relabeling)
496
	{
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
	case ApRelabeling:
	  {
	    const spot::ltl::formula* res = spot::ltl::relabel(f, style);
	    f->destroy();
	    f = res;
	    break;
	  }
	case BseRelabeling:
	  {
	    const spot::ltl::formula* res = spot::ltl::relabel_bse(f, style);
	    f->destroy();
	    f = res;
	    break;
	  }
	case NoRelabeling:
	  break;
513
514
515
516
517
	}

      if (remove_wm)
	{
	  const spot::ltl::formula* res = spot::ltl::unabbreviate_wm(f);
518
519
520
521
	  f->destroy();
	  f = res;
	}

522
523
524
525
526
527
528
529
530
531
532
533
534
      bool matched = true;

      matched &= !ltl || f->is_ltl_formula();
      matched &= !psl || f->is_psl_formula();
      matched &= !nox || f->is_X_free();
      matched &= !boolean || f->is_boolean();
      matched &= !universal || f->is_universal();
      matched &= !eventual || f->is_eventual();
      matched &= !syntactic_safety || f->is_syntactic_safety();
      matched &= !syntactic_guarantee || f->is_syntactic_guarantee();
      matched &= !syntactic_obligation || f->is_syntactic_obligation();
      matched &= !syntactic_recurrence || f->is_syntactic_recurrence();
      matched &= !syntactic_persistence || f->is_syntactic_persistence();
535
      matched &= !ap || atomic_prop_collect(f)->size() == ap_n;
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550

      if (matched && (size_min > 0 || size_max >= 0))
	{
	  int l = spot::ltl::length(f);
	  matched &= (size_min <= 0) || (l >= size_min);
	  matched &= (size_max < 0) || (l <= size_max);
	}

      if (matched && (bsize_min > 0 || bsize_max >= 0))
	{
	  int l = spot::ltl::length_boolone(f);
	  matched &= (bsize_min <= 0) || (l >= bsize_min);
	  matched &= (bsize_max < 0) || (l <= bsize_max);
	}

551
552
553
      matched &= !implied_by || simpl.implication(implied_by, f);
      matched &= !imply || simpl.implication(f, imply);
      matched &= !equivalent_to || simpl.are_equivalent(f, equivalent_to);
554
      matched &= !stutter_insensitive || spot::is_stutter_invariant(f);
555

556
557
558
559
560
561
      // Match obligations and subclasses using WDBA minimization.
      // Because this is costly, we compute it later, so that we don't
      // have to compute it on formulas that have been discarded for
      // other reasons.
      if (matched && obligation)
	{
562
563
	  auto aut = ltl_to_tgba_fm(f, simpl.get_dict());
	  auto min = minimize_obligation(aut, f);
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
	  assert(min);
	  if (aut == min)
	    {
	      // Not an obligation
	      matched = false;
	    }
	  else
	    {
	      matched &= !guarantee || is_guarantee_automaton(min);
	      matched &= !safety || is_safety_mwdba(min);
	    }
	}

      matched ^= invert;

      if (unique)
	{
	  if (unique_set.insert(f).second)
	    f->clone();
	  else
	    matched = false;
	}

      if (matched)
	{
589
	  one_match = true;
590
	  output_formula_checked(f, filename, linenum, prefix, suffix);
591
592
593
594
595
596
597
598
599
600
	}
      f->destroy();
      return 0;
    }
  };
}

int
main(int argc, char** argv)
{
601
  setup(argv);
602

603
  const argp ap = { options, parse_opt, "[FILENAME[/COL]...]",
604
		    argp_program_doc, children, 0, 0 };
605

606
  if (int err = argp_parse(&ap, argc, argv, ARGP_NO_HELP, 0, 0))
607
608
609
    exit(err);

  if (jobs.empty())
610
    jobs.emplace_back("-", 1);
611

612
613
614
615
616
  if (boolean_to_isop && simplification_level == 0)
    simplification_level = 1;
  spot::ltl::ltl_simplifier_options opt = simplifier_options();
  opt.boolean_to_isop = boolean_to_isop;
  spot::ltl::ltl_simplifier simpl(opt);
617
618
619
620
  ltl_processor processor(simpl);
  if (processor.run())
    return 2;
  return one_match ? 0 : 1;
621
}