genltl.cc 9.98 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
// Copyright (C) 2012, 2013, 2015-2017 Laboratoire de Recherche et
3
// 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


21
#include "common_sys.hh"
22
23
24
25
26
27
28
29

#include <iostream>
#include <fstream>
#include <argp.h>
#include <cstdlib>
#include "error.h"
#include <vector>

30
#include "common_setup.hh"
31
#include "common_output.hh"
32
#include "common_range.hh"
33
#include "common_cout.hh"
34
35
36
37
38
39
40
41

#include <cassert>
#include <iostream>
#include <sstream>
#include <set>
#include <string>
#include <cstdlib>
#include <cstring>
42
43
#include <spot/tl/formula.hh>
#include <spot/tl/relabel.hh>
44
#include <spot/gen/formulas.hh>
45
46
47
48

using namespace spot;

const char argp_program_doc[] ="\
49
Generate temporal logic formulas from predefined patterns.";
50

51
52
53
// We reuse the values from spot::gen::ltl_patterns as option keys.
// Additional options should therefore start after
// spot::gen::LAST_CLASS.
54
enum {
55
  OPT_POSITIVE = spot::gen::LAST_CLASS + 1,
56
  OPT_NEGATIVE,
57
};
58

59

60
#define OPT_ALIAS(o) { #o, 0, nullptr, OPTION_ALIAS, nullptr, 0 }
61
62
63
64
65

static const argp_option options[] =
  {
    /**************************************************/
    // Keep this alphabetically sorted (expect for aliases).
66
    { nullptr, 0, nullptr, 0, "Pattern selection:", 1},
67
68
    // J. Geldenhuys and H. Hansen (Spin'06): Larger automata and less
    // work for LTL model checking.
69
    { "and-f", spot::gen::AND_F, "RANGE", 0, "F(p1)&F(p2)&...&F(pn)", 0 },
70
    OPT_ALIAS(gh-e),
71
72
    { "and-fg", spot::gen::AND_FG, "RANGE", 0, "FG(p1)&FG(p2)&...&FG(pn)", 0 },
    { "and-gf", spot::gen::AND_GF, "RANGE", 0, "GF(p1)&GF(p2)&...&GF(pn)", 0 },
73
74
    OPT_ALIAS(ccj-phi),
    OPT_ALIAS(gh-c2),
75
    { "ccj-alpha", spot::gen::CCJ_ALPHA, "RANGE", 0,
76
      "F(p1&F(p2&F(p3&...F(pn)))) & F(q1&F(q2&F(q3&...F(qn))))", 0 },
77
    { "ccj-beta", spot::gen::CCJ_BETA, "RANGE", 0,
78
      "F(p&X(p&X(p&...X(p)))) & F(q&X(q&X(q&...X(q))))", 0 },
79
    { "ccj-beta-prime", spot::gen::CCJ_BETA_PRIME, "RANGE", 0,
80
      "F(p&(Xp)&(XXp)&...(X...X(p))) & F(q&(Xq)&(XXq)&...(X...X(q)))", 0 },
81
    { "dac-patterns", spot::gen::DAC_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
82
      "Dwyer et al. [FMSP'98] Spec. Patterns for LTL "
83
      "(range should be included in 1..55)", 0 },
84
    OPT_ALIAS(spec-patterns),
85
    { "eh-patterns", spot::gen::EH_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
86
87
      "Etessami and Holzmann [Concur'00] patterns "
      "(range should be included in 1..12)", 0 },
88
    { "gh-q", spot::gen::GH_Q, "RANGE", 0,
89
      "(F(p1)|G(p2))&(F(p2)|G(p3))&...&(F(pn)|G(p{n+1}))", 0 },
90
    { "gh-r", spot::gen::GH_R, "RANGE", 0,
91
      "(GF(p1)|FG(p2))&(GF(p2)|FG(p3))&... &(GF(pn)|FG(p{n+1}))", 0 },
92
    { "go-theta", spot::gen::GO_THETA, "RANGE", 0,
93
      "!((GF(p1)&GF(p2)&...&GF(pn)) -> G(q->F(r)))", 0 },
94
    { "hkrss-patterns", spot::gen::HKRSS_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
95
96
97
      "Holeček et al. patterns from the Liberouter project "
      "(range should be included in 1..55)", 0 },
    OPT_ALIAS(liberouter-patterns),
98
    { "kr-n", spot::gen::KR_N, "RANGE", 0,
99
      "linear formula with doubly exponential DBA", 0 },
100
    { "kr-nlogn", spot::gen::KR_NLOGN, "RANGE", 0,
101
      "quasilinear formula with doubly exponential DBA", 0 },
102
    { "kv-psi", spot::gen::KV_PSI, "RANGE", 0,
103
      "quadratic formula with doubly exponential DBA", 0 },
104
    OPT_ALIAS(kr-n2),
105
    { "or-fg", spot::gen::OR_FG, "RANGE", 0, "FG(p1)|FG(p2)|...|FG(pn)", 0 },
106
    OPT_ALIAS(ccj-xi),
107
    { "or-g", spot::gen::OR_G, "RANGE", 0, "G(p1)|G(p2)|...|G(pn)", 0 },
108
    OPT_ALIAS(gh-s),
109
    { "or-gf", spot::gen::OR_GF, "RANGE", 0, "GF(p1)|GF(p2)|...|GF(pn)", 0 },
110
    OPT_ALIAS(gh-c1),
111
    { "p-patterns", spot::gen::P_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
112
113
114
115
      "Pelánek [Spin'07] patterns from BEEM "
      "(range should be included in 1..20)", 0 },
    OPT_ALIAS(beem-patterns),
    OPT_ALIAS(p),
116
117
118
119
120
    { "r-left", spot::gen::R_LEFT, "RANGE", 0,
      "(((p1 R p2) R p3) ... R pn)", 0 },
    { "r-right", spot::gen::R_RIGHT, "RANGE", 0,
      "(p1 R (p2 R (... R pn)))", 0 },
    { "rv-counter", spot::gen::RV_COUNTER, "RANGE", 0,
121
      "n-bit counter", 0 },
122
    { "rv-counter-carry", spot::gen::RV_COUNTER_CARRY, "RANGE", 0,
123
      "n-bit counter w/ carry", 0 },
124
    { "rv-counter-carry-linear", spot::gen::RV_COUNTER_CARRY_LINEAR, "RANGE", 0,
125
      "n-bit counter w/ carry (linear size)", 0 },
126
    { "rv-counter-linear", spot::gen::RV_COUNTER_LINEAR, "RANGE", 0,
127
      "n-bit counter (linear size)", 0 },
128
    { "sb-patterns", spot::gen::SB_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
129
130
      "Somenzi and Bloem [CAV'00] patterns "
      "(range should be included in 1..27)", 0 },
131
132
133
134
135
136
137
138
139
    { "tv-f1", spot::gen::TV_F1, "RANGE", 0,
      "G(p -> (q | Xq | ... | XX...Xq)", 0 },
    { "tv-f2", spot::gen::TV_F2, "RANGE", 0,
      "G(p -> (q | X(q | X(... | Xq)))", 0 },
    { "tv-g1", spot::gen::TV_G1, "RANGE", 0,
      "G(p -> (q & Xq & ... & XX...Xq)", 0 },
    { "tv-g2", spot::gen::TV_G2, "RANGE", 0,
      "G(p -> (q & X(q & X(... & Xq)))", 0 },
    { "tv-uu", spot::gen::TV_UU, "RANGE", 0,
140
      "G(p1 -> (p1 U (p2 & (p2 U (p3 & (p3 U ...))))))", 0 },
141
142
    { "u-left", spot::gen::U_LEFT, "RANGE", 0,
      "(((p1 U p2) U p3) ... U pn)", 0 },
143
    OPT_ALIAS(gh-u),
144
145
    { "u-right", spot::gen::U_RIGHT, "RANGE", 0,
      "(p1 U (p2 U (... U pn)))", 0 },
146
147
    OPT_ALIAS(gh-u2),
    OPT_ALIAS(go-phi),
148
    RANGE_DOC,
149
  /**************************************************/
150
    { nullptr, 0, nullptr, 0, "Output options:", -20 },
151
152
153
154
155
156
    { "negative", OPT_NEGATIVE, nullptr, 0,
      "output the negated versions of all formulas", 0 },
    OPT_ALIAS(negated),
    { "positive", OPT_POSITIVE, nullptr, 0,
      "output the positive versions of all formulas (done by default, unless"
      " --negative is specified without --positive)", 0 },
157
    { nullptr, 0, nullptr, 0, "The FORMAT string passed to --format may use "
158
      "the following interpreted sequences:", -19 },
159
    { "%f", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
160
      "the formula (in the selected syntax)", 0 },
161
    { "%F", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
162
      "the name of the pattern", 0 },
163
    { "%L", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
164
      "the argument of the pattern", 0 },
165
    { "%%", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
166
      "a single %", 0 },
167
    COMMON_LTL_OUTPUT_SPECS,
168
169
    { nullptr, 0, nullptr, 0, "Miscellaneous options:", -1 },
    { nullptr, 0, nullptr, 0, nullptr, 0 }
170
171
172
173
  };

struct job
{
174
  spot::gen::ltl_pattern pattern;
175
  struct range range;
176
177
178
179
};

typedef std::vector<job> jobs_t;
static jobs_t jobs;
180
181
bool opt_positive = false;
bool opt_negative = false;
182
183
184

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

static void
191
enqueue_job(int pattern, const char* range_str)
192
193
{
  job j;
194
  j.pattern = static_cast<spot::gen::ltl_pattern>(pattern);
195
  j.range = parse_range(range_str);
196
197
198
  jobs.push_back(j);
}

199
200
201
202
static void
enqueue_job(int pattern, int min, int max)
{
  job j;
203
  j.pattern = static_cast<spot::gen::ltl_pattern>(pattern);
204
205
206
207
  j.range = {min, max};
  jobs.push_back(j);
}

208
static int
209
parse_opt(int key, char* arg, struct argp_state*)
210
211
212
213
{
  // This switch is alphabetically-ordered.
  switch (key)
    {
214
215
    case spot::gen::DAC_PATTERNS:
    case spot::gen::HKRSS_PATTERNS:
216
217
218
219
220
      if (arg)
        enqueue_job(key, arg);
      else
        enqueue_job(key, 1, 55);
      break;
221
    case spot::gen::EH_PATTERNS:
222
223
224
225
226
      if (arg)
        enqueue_job(key, arg);
      else
        enqueue_job(key, 1, 12);
      break;
227
    case spot::gen::P_PATTERNS:
228
229
230
231
232
      if (arg)
        enqueue_job(key, arg);
      else
        enqueue_job(key, 1, 20);
      break;
233
    case spot::gen::SB_PATTERNS:
234
235
236
237
238
      if (arg)
        enqueue_job(key, arg);
      else
        enqueue_job(key, 1, 27);
      break;
239
240
241
242
243
244
    case OPT_POSITIVE:
      opt_positive = true;
      break;
    case OPT_NEGATIVE:
      opt_negative = true;
      break;
245
    default:
246
      if (key >= spot::gen::FIRST_CLASS && key < spot::gen::LAST_CLASS)
247
        {
248
249
          enqueue_job(key, arg);
          break;
250
        }
251
      return ARGP_ERR_UNKNOWN;
252
    }
253
  return 0;
254
255
256
}


257
static void
258
output_pattern(spot::gen::ltl_pattern pattern, int n)
259
{
260
  formula f = spot::gen::genltl(pattern, n);
261

262
263
  // Make sure we use only "p42"-style of atomic propositions
  // in lbt's output.
264
265
  if (output_format == lbt_output && !f.has_lbt_atomic_props())
    f = relabel(f, Pnn);
266

267
268
  if (opt_positive || !opt_negative)
    {
269
      output_formula_checked(f, spot::gen::ltl_pattern_name(pattern), n);
270
271
272
273
    }
  if (opt_negative)
    {
      std::string tmp = "!";
274
      tmp += spot::gen::ltl_pattern_name(pattern);
275
276
      output_formula_checked(spot::formula::Not(f), tmp.c_str(), n);
    }
277
278
279
280
281
}

static void
run_jobs()
{
282
  for (auto& j: jobs)
283
    {
284
285
      int inc = (j.range.max < j.range.min) ? -1 : 1;
      int n = j.range.min;
286
      for (;;)
287
288
289
290
291
292
        {
          output_pattern(j.pattern, n);
          if (n == j.range.max)
            break;
          n += inc;
        }
293
294
295
296
297
298
299
    }
}


int
main(int argc, char** argv)
{
300
  setup(argv);
301

302
  const argp ap = { options, parse_opt, nullptr, argp_program_doc,
303
                    children, nullptr, nullptr };
304

305
  if (int err = argp_parse(&ap, argc, argv, ARGP_NO_HELP, nullptr, nullptr))
306
307
308
309
    exit(err);

  if (jobs.empty())
    error(1, 0, "Nothing to do.  Try '%s --help' for more information.",
310
          program_name);
311

312
313
314
315
316
317
318
319
320
  try
    {
      run_jobs();
    }
  catch (const std::runtime_error& e)
    {
      error(2, 0, "%s", e.what());
    }

321
  flush_cout();
322
323
  return 0;
}