1 // -*- coding: utf-8 -*-
2 // Copyright (C) 2012, 2013, 2015-2019 Laboratoire de Recherche et
3 // Développement de l'Epita (LRDE).
4 //
5 // This file is part of Spot, a model checking library.
6 //
7 // Spot is free software; you can redistribute it and/or modify it
8 // 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 // (at your option) any later version.
11 //
12 // Spot is distributed in the hope that it will be useful, but WITHOUT
13 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
15 // License for more details.
16 //
17 // 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 #include <iostream>
24 #include <fstream>
25 #include <argp.h>
26 #include <cstdlib>
27 #include "error.h"
28 #include <vector>
29
30 #include "common_setup.hh"
31 #include "common_output.hh"
32 #include "common_range.hh"
33 #include "common_cout.hh"
34
35 #include <cassert>
36 #include <iostream>
37 #include <sstream>
38 #include <set>
39 #include <string>
40 #include <cstdlib>
41 #include <cstring>
42 #include <spot/tl/formula.hh>
43 #include <spot/tl/relabel.hh>
44 #include <spot/gen/formulas.hh>
45
46 using namespace spot;
47
48 const char argp_program_doc[] ="\
49 Generate temporal logic formulas from predefined patterns.";
50
51 // We reuse the values from gen::ltl_pattern_id as option keys.
52 // Additional options should therefore start after gen::LTL_END.
53 enum {
54 OPT_POSITIVE = gen::LTL_END,
55 OPT_NEGATIVE,
56 };
57
58
59 #define OPT_ALIAS(o) { #o, 0, nullptr, OPTION_ALIAS, nullptr, 0 }
60
61 static const argp_option options[] =
62 {
63 /**************************************************/
64 // Keep this alphabetically sorted (except for aliases).
65 { nullptr, 0, nullptr, 0, "Pattern selection:", 1},
66 // J. Geldenhuys and H. Hansen (Spin'06): Larger automata and less
67 // work for LTL model checking.
68 { "and-f", gen::LTL_AND_F, "RANGE", 0, "F(p1)&F(p2)&...&F(pn)", 0 },
69 OPT_ALIAS(gh-e),
70 { "and-fg", gen::LTL_AND_FG, "RANGE", 0, "FG(p1)&FG(p2)&...&FG(pn)", 0 },
71 { "and-gf", gen::LTL_AND_GF, "RANGE", 0, "GF(p1)&GF(p2)&...&GF(pn)", 0 },
72 OPT_ALIAS(ccj-phi),
73 OPT_ALIAS(gh-c2),
74 { "ccj-alpha", gen::LTL_CCJ_ALPHA, "RANGE", 0,
75 "F(p1&F(p2&F(p3&...F(pn)))) & F(q1&F(q2&F(q3&...F(qn))))", 0 },
76 { "ccj-beta", gen::LTL_CCJ_BETA, "RANGE", 0,
77 "F(p&X(p&X(p&...X(p)))) & F(q&X(q&X(q&...X(q))))", 0 },
78 { "ccj-beta-prime", gen::LTL_CCJ_BETA_PRIME, "RANGE", 0,
79 "F(p&(Xp)&(XXp)&...(X...X(p))) & F(q&(Xq)&(XXq)&...(X...X(q)))", 0 },
80 { "dac-patterns", gen::LTL_DAC_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
81 "Dwyer et al. [FMSP'98] Spec. Patterns for LTL "
82 "(range should be included in 1..55)", 0 },
83 OPT_ALIAS(spec-patterns),
84 { "eh-patterns", gen::LTL_EH_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
85 "Etessami and Holzmann [Concur'00] patterns "
86 "(range should be included in 1..12)", 0 },
87 { "fxg-or", gen::LTL_FXG_OR, "RANGE", 0,
88 "F(p0 | XG(p1 | XG(p2 | ... XG(pn))))", 0},
89 { "gf-equiv", gen::LTL_GF_EQUIV, "RANGE", 0,
90 "(GFa1 & GFa2 & ... & GFan) <-> GFz", 0},
91 { "gf-equiv-xn", gen::LTL_GF_EQUIV_XN, "RANGE", 0,
92 "GF(a <-> X^n(a))", 0},
93 { "gf-implies", gen::LTL_GF_IMPLIES, "RANGE", 0,
94 "(GFa1 & GFa2 & ... & GFan) -> GFz", 0},
95 { "gf-implies-xn", gen::LTL_GF_IMPLIES_XN, "RANGE", 0,
96 "GF(a -> X^n(a))", 0},
97 { "gh-q", gen::LTL_GH_Q, "RANGE", 0,
98 "(F(p1)|G(p2))&(F(p2)|G(p3))&...&(F(pn)|G(p{n+1}))", 0 },
99 { "gh-r", gen::LTL_GH_R, "RANGE", 0,
100 "(GF(p1)|FG(p2))&(GF(p2)|FG(p3))&... &(GF(pn)|FG(p{n+1}))", 0 },
101 { "go-theta", gen::LTL_GO_THETA, "RANGE", 0,
102 "!((GF(p1)&GF(p2)&...&GF(pn)) -> G(q->F(r)))", 0 },
103 { "gxf-and", gen::LTL_GXF_AND, "RANGE", 0,
104 "G(p0 & XF(p1 & XF(p2 & ... XF(pn))))", 0},
105 { "hkrss-patterns", gen::LTL_HKRSS_PATTERNS,
106 "RANGE", OPTION_ARG_OPTIONAL,
107 "Holeček et al. patterns from the Liberouter project "
108 "(range should be included in 1..55)", 0 },
109 OPT_ALIAS(liberouter-patterns),
110 { "kr-n", gen::LTL_KR_N, "RANGE", 0,
111 "linear formula with doubly exponential DBA", 0 },
112 { "kr-nlogn", gen::LTL_KR_NLOGN, "RANGE", 0,
113 "quasilinear formula with doubly exponential DBA", 0 },
114 { "kv-psi", gen::LTL_KV_PSI, "RANGE", 0,
115 "quadratic formula with doubly exponential DBA", 0 },
116 OPT_ALIAS(kr-n2),
117 { "ms-example", gen::LTL_MS_EXAMPLE, "RANGE[,RANGE]", 0,
118 "GF(a1&X(a2&X(a3&...Xan)))&F(b1&F(b2&F(b3&...&Xbm)))", 0 },
119 { "ms-phi-h", gen::LTL_MS_PHI_H, "RANGE", 0,
120 "FG(a|b)|FG(!a|Xb)|FG(a|XXb)|FG(!a|XXXb)|...", 0 },
121 { "ms-phi-r", gen::LTL_MS_PHI_R, "RANGE", 0,
122 "(FGa{n}&GFb{n})|((FGa{n-1}|GFb{n-1})&(...))", 0 },
123 { "ms-phi-s", gen::LTL_MS_PHI_S, "RANGE", 0,
124 "(FGa{n}|GFb{n})&((FGa{n-1}&GFb{n-1})|(...))", 0 },
125 { "or-fg", gen::LTL_OR_FG, "RANGE", 0, "FG(p1)|FG(p2)|...|FG(pn)", 0 },
126 OPT_ALIAS(ccj-xi),
127 { "or-g", gen::LTL_OR_G, "RANGE", 0, "G(p1)|G(p2)|...|G(pn)", 0 },
128 OPT_ALIAS(gh-s),
129 { "or-gf", gen::LTL_OR_GF, "RANGE", 0, "GF(p1)|GF(p2)|...|GF(pn)", 0 },
130 OPT_ALIAS(gh-c1),
131 { "p-patterns", gen::LTL_P_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
132 "Pelánek [Spin'07] patterns from BEEM "
133 "(range should be included in 1..20)", 0 },
134 OPT_ALIAS(beem-patterns),
135 OPT_ALIAS(p),
136 { "pps-arbiter-standard", gen::LTL_PPS_ARBITER_STANDARD, "RANGE", 0,
137 "Arbiter with n clients that sent requests (ri) and "
138 "receive grants (gi). Standard semantics.", 0 },
139 { "pps-arbiter-strict", gen::LTL_PPS_ARBITER_STRICT, "RANGE", 0,
140 "Arbiter with n clients that sent requests (ri) and "
141 "receive grants (gi). Strict semantics.", 0 },
142 { "r-left", gen::LTL_R_LEFT, "RANGE", 0, "(((p1 R p2) R p3) ... R pn)", 0 },
143 { "r-right", gen::LTL_R_RIGHT, "RANGE", 0, "(p1 R (p2 R (... R pn)))", 0 },
144 { "rv-counter", gen::LTL_RV_COUNTER, "RANGE", 0, "n-bit counter", 0 },
145 { "rv-counter-carry", gen::LTL_RV_COUNTER_CARRY, "RANGE", 0,
146 "n-bit counter w/ carry", 0 },
147 { "rv-counter-carry-linear", gen::LTL_RV_COUNTER_CARRY_LINEAR,
148 "RANGE", 0, "n-bit counter w/ carry (linear size)", 0 },
149 { "rv-counter-linear", gen::LTL_RV_COUNTER_LINEAR, "RANGE", 0,
150 "n-bit counter (linear size)", 0 },
151 { "sb-patterns", gen::LTL_SB_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
152 "Somenzi and Bloem [CAV'00] patterns "
153 "(range should be included in 1..27)", 0 },
154 { "sejk-f", gen::LTL_SEJK_F, "RANGE[,RANGE]", 0,
155 "f(0,j)=(GFa0 U X^j(b)), f(i,j)=(GFai U G(f(i-1,j)))", 0 },
156 { "sejk-j", gen::LTL_SEJK_J, "RANGE", 0,
157 "(GFa1&...&GFan) -> (GFb1&...&GFbn)", 0 },
158 { "sejk-k", gen::LTL_SEJK_K, "RANGE", 0,
159 "(GFa1|FGb1)&...&(GFan|FGbn)", 0 },
160 { "sejk-patterns", gen::LTL_SEJK_PATTERNS, "RANGE", OPTION_ARG_OPTIONAL,
161 "φ₁,φ₂,φ₃ from Sikert et al's [CAV'16] paper "
162 "(range should be included in 1..3)", 0 },
163 { "tv-f1", gen::LTL_TV_F1, "RANGE", 0,
164 "G(p -> (q | Xq | ... | XX...Xq)", 0 },
165 { "tv-f2", gen::LTL_TV_F2, "RANGE", 0,
166 "G(p -> (q | X(q | X(... | Xq)))", 0 },
167 { "tv-g1", gen::LTL_TV_G1, "RANGE", 0,
168 "G(p -> (q & Xq & ... & XX...Xq)", 0 },
169 { "tv-g2", gen::LTL_TV_G2, "RANGE", 0,
170 "G(p -> (q & X(q & X(... & Xq)))", 0 },
171 { "tv-uu", gen::LTL_TV_UU, "RANGE", 0,
172 "G(p1 -> (p1 U (p2 & (p2 U (p3 & (p3 U ...))))))", 0 },
173 { "u-left", gen::LTL_U_LEFT, "RANGE", 0, "(((p1 U p2) U p3) ... U pn)", 0 },
174 OPT_ALIAS(gh-u),
175 { "u-right", gen::LTL_U_RIGHT, "RANGE", 0, "(p1 U (p2 U (... U pn)))", 0 },
176 OPT_ALIAS(gh-u2),
177 OPT_ALIAS(go-phi),
178 RANGE_DOC,
179 /**************************************************/
180 { nullptr, 0, nullptr, 0, "Output options:", -20 },
181 { "negative", OPT_NEGATIVE, nullptr, 0,
182 "output the negated versions of all formulas", 0 },
183 OPT_ALIAS(negated),
184 { "positive", OPT_POSITIVE, nullptr, 0,
185 "output the positive versions of all formulas (done by default, unless"
186 " --negative is specified without --positive)", 0 },
187 { nullptr, 0, nullptr, 0, "The FORMAT string passed to --format may use "
188 "the following interpreted sequences:", -19 },
189 { "%f", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
190 "the formula (in the selected syntax)", 0 },
191 { "%F", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
192 "the name of the pattern", 0 },
193 { "%L", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
194 "the argument of the pattern", 0 },
195 { "%%", 0, nullptr, OPTION_DOC | OPTION_NO_USAGE,
196 "a single %", 0 },
197 COMMON_LTL_OUTPUT_SPECS,
198 /**************************************************/
199 { nullptr, 0, nullptr, 0, "Miscellaneous options:", -1 },
200 { nullptr, 0, nullptr, 0, nullptr, 0 }
201 };
202
203 struct job
204 {
205 gen::ltl_pattern_id pattern;
206 struct range range;
207 struct range range2;
208 };
209
210 typedef std::vector<job> jobs_t;
211 static jobs_t jobs;
212 bool opt_positive = false;
213 bool opt_negative = false;
214
215 const struct argp_child children[] =
216 {
217 { &output_argp, 0, nullptr, 0 },
218 { &misc_argp, 0, nullptr, 0 },
219 { nullptr, 0, nullptr, 0 }
220 };
221
222 static void
enqueue_job(int pattern,const char * range_str=nullptr)223 enqueue_job(int pattern, const char* range_str = nullptr)
224 {
225 job j;
226 j.pattern = static_cast<gen::ltl_pattern_id>(pattern);
227 j.range2.min = -1;
228 j.range2.max = -1;
229 if (range_str)
230 {
231 if (gen::ltl_pattern_argc(j.pattern) == 2)
232 {
233 const char* comma = strchr(range_str, ',');
234 if (!comma)
235 {
236 j.range2 = j.range = parse_range(range_str);
237 }
238 else
239 {
240 std::string range1(range_str, comma);
241 j.range = parse_range(range1.c_str());
242 j.range2 = parse_range(comma + 1);
243 }
244 }
245 else
246 {
247 j.range = parse_range(range_str);
248 }
249 }
250 else
251 {
252 j.range.min = 1;
253 j.range.max = gen::ltl_pattern_max(j.pattern);
254 if (j.range.max == 0)
255 error(2, 0, "missing range for %s",
256 gen::ltl_pattern_name(j.pattern));
257 }
258 jobs.push_back(j);
259 }
260
261 static int
parse_opt(int key,char * arg,struct argp_state *)262 parse_opt(int key, char* arg, struct argp_state*)
263 {
264 // Called from C code, so should not raise any exception.
265 BEGIN_EXCEPTION_PROTECT;
266 if (key >= gen::LTL_BEGIN && key < gen::LTL_END)
267 {
268 enqueue_job(key, arg);
269 return 0;
270 }
271 // This switch is alphabetically-ordered.
272 switch (key)
273 {
274 case OPT_POSITIVE:
275 opt_positive = true;
276 break;
277 case OPT_NEGATIVE:
278 opt_negative = true;
279 break;
280 default:
281 return ARGP_ERR_UNKNOWN;
282 }
283 END_EXCEPTION_PROTECT;
284 return 0;
285 }
286
287
288 static void
output_pattern(gen::ltl_pattern_id pattern,int n,int n2)289 output_pattern(gen::ltl_pattern_id pattern, int n, int n2)
290 {
291 formula f = gen::ltl_pattern(pattern, n, n2);
292
293 // Make sure we use only "p42"-style of atomic propositions
294 // in lbt's output.
295 if (output_format == lbt_output && !f.has_lbt_atomic_props())
296 f = relabel(f, Pnn);
297
298 std::string args = std::to_string(n);
299 if (n2 >= 0)
300 args = args + ',' + std::to_string(n2);
301 if (opt_positive || !opt_negative)
302 {
303 output_formula_checked(f, nullptr, gen::ltl_pattern_name(pattern),
304 args.c_str());
305 }
306 if (opt_negative)
307 {
308 std::string tmp = "!";
309 tmp += gen::ltl_pattern_name(pattern);
310 output_formula_checked(formula::Not(f), nullptr, tmp.c_str(),
311 args.c_str());
312 }
313 }
314
315 static void
run_jobs()316 run_jobs()
317 {
318 for (auto& j: jobs)
319 {
320 int inc = (j.range.max < j.range.min) ? -1 : 1;
321 int n = j.range.min;
322 for (;;)
323 {
324 int inc2 = (j.range2.max < j.range2.min) ? -1 : 1;
325 int n2 = j.range2.min;
326 for (;;)
327 {
328 output_pattern(j.pattern, n, n2);
329 if (n2 == j.range2.max)
330 break;
331 n2 += inc2;
332 }
333 if (n == j.range.max)
334 break;
335 n += inc;
336 }
337 }
338 }
339
340
341 int
main(int argc,char ** argv)342 main(int argc, char** argv)
343 {
344 return protected_main(argv, [&] {
345 const argp ap = { options, parse_opt, nullptr, argp_program_doc,
346 children, nullptr, nullptr };
347
348 if (int err = argp_parse(&ap, argc, argv, ARGP_NO_HELP, nullptr, nullptr))
349 exit(err);
350
351 if (jobs.empty())
352 error(1, 0, "Nothing to do. Try '%s --help' for more information.",
353 program_name);
354
355 run_jobs();
356 flush_cout();
357 return 0;
358 });
359 }
360