modelcheck.cc 9.33 KB
Newer Older
1
// -*- coding: utf-8 -*-
2 3
// Copyright (C) 2011, 2012, 2013, 2014, 2015 Laboratoire de Recherche
// et Developpement 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 "ltsmin.hh"
21
#include "tgbaalgos/dotty.hh"
22 23
#include "ltlenv/defaultenv.hh"
#include "ltlast/allnodes.hh"
24
#include "ltlparse/public.hh"
25
#include "tgbaalgos/translate.hh"
26 27
#include "tgbaalgos/emptiness.hh"
#include "tgbaalgos/reducerun.hh"
28
#include "tgbaalgos/postproc.hh"
29 30
#include "tgba/tgbaproduct.hh"
#include "misc/timer.hh"
31
#include "misc/memusage.hh"
32
#include <cstring>
33 34
#include "kripke/kripkeexplicit.hh"
#include "kripke/kripkeprint.hh"
35

36
static void
37 38 39 40 41 42 43
syntax(char* prog)
{
  // Display the supplied name unless it appears to be a libtool wrapper.
  char* slash = strrchr(prog, '/');
  if (slash && (strncmp(slash + 1, "lt-", 3) == 0))
    prog = slash + 4;

44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
  std::cerr << "usage: " << prog << " [options] model formula\n\
\n\
Options:\n\
  -dDEAD use DEAD as property for marking DEAD states\n\
          (by default DEAD = true)\n\
  -e[ALGO]  run emptiness check, expect an accepting run\n\
  -E[ALGO]  run emptiness check, expect no accepting run\n\
  -C     compute an accepting run (Counterexample) if it exists\n\
  -D     favor a deterministic translation over a small transition\n\
  -gf    output the automaton of the formula in dot format\n\
  -gm    output the model state-space in dot format\n\
  -gK    output the model state-space in Kripke format\n\
  -gp    output the product state-space in dot format\n\
  -T     time the different phases of the execution\n\
  -z     compress states to handle larger models\n\
  -Z     compress states (faster) assuming all values in [0 .. 2^28-1]\n\
";
61 62
  exit(1);
}
63 64

int
65
checked_main(int argc, char **argv)
66
{
67 68 69 70
  spot::timer_map tm;

  bool use_timer = false;

71
  enum { DotFormula, DotModel, DotProduct, EmptinessCheck, Kripke }
72 73 74
  output = EmptinessCheck;
  bool accepting_run = false;
  bool expect_counter_example = false;
75
  bool deterministic = false;
76
  char *dead = 0;
77
  int compress_states = 0;
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

  const char* echeck_algo = "Cou99";

  int dest = 1;
  int n = argc;
  for (int i = 1; i < n; ++i)
    {
      char* opt = argv[i];
      if (*opt == '-')
	{
	  switch (*++opt)
	    {
	    case 'C':
	      accepting_run = true;
	      break;
93 94 95
	    case 'd':
	      dead = opt + 1;
	      break;
96 97 98
	    case 'D':
	      deterministic = true;
	      break;
99 100 101 102 103 104 105
	    case 'e':
	    case 'E':
	      {
		echeck_algo = opt + 1;
		if (!*echeck_algo)
		  echeck_algo = "Cou99";

106
		expect_counter_example = (*opt == 'e');
107 108 109 110 111 112
		output = EmptinessCheck;
		break;
	      }
	    case 'g':
	      switch (opt[1])
		{
113 114 115 116 117 118 119 120 121
		case 'm':
		  output = DotModel;
		  break;
		case 'p':
		  output = DotProduct;
		  break;
		case 'f':
		  output = DotFormula;
		  break;
122 123 124
                case 'K':
                  output = Kripke;
                  break;
125 126 127 128 129 130 131
		default:
		  goto error;
		}
	      break;
	    case 'T':
	      use_timer = true;
	      break;
132
	    case 'z':
133 134 135 136
	      compress_states = 1;
	      break;
	    case 'Z':
	      compress_states = 2;
137
	      break;
138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
	    default:
	    error:
	      std::cerr << "Unknown option `" << argv[i] << "'." << std::endl;
	      exit(1);
	    }
	  --argc;
	}
      else
	{
	  argv[dest++] = argv[i];
	}
    }

  if (argc != 3)
    syntax(argv[0]);

154 155 156
  spot::ltl::default_environment& env =
    spot::ltl::default_environment::instance();

157

158
  spot::ltl::atomic_prop_set ap;
159
  auto dict = spot::make_bdd_dict();
160 161 162 163
  spot::const_kripke_ptr model = nullptr;
  spot::const_tgba_ptr prop = nullptr;
  spot::const_tgba_ptr product = nullptr;
  spot::emptiness_check_instantiator_ptr echeck_inst = nullptr;
164
  int exit_code = 0;
165
  spot::postprocessor post;
166 167
  const spot::ltl::formula* deadf = nullptr;
  const spot::ltl::formula* f = nullptr;
168

169
  if (!dead || !strcasecmp(dead, "true"))
170 171 172 173 174 175 176 177 178 179 180
    {
      deadf = spot::ltl::constant::true_instance();
    }
  else if (!strcasecmp(dead, "false"))
    {
      deadf = spot::ltl::constant::false_instance();
    }
  else
    {
      deadf = env.require(dead);
    }
181

182
  if (output == EmptinessCheck)
183
    {
184
      const char* err;
185
      echeck_inst = spot::make_emptiness_check_instantiator(echeck_algo, &err);
186 187 188
      if (!echeck_inst)
	{
	  std::cerr << "Failed to parse argument of -e/-E near `"
189
		    << err <<  "'\n";
190 191 192
	  exit_code = 1;
	  goto safe_exit;
	}
193 194
    }

195 196 197 198 199 200 201 202 203 204 205
  tm.start("parsing formula");
  {
    spot::ltl::parse_error_list pel;
    f = spot::ltl::parse(argv[2], pel, env, false);
    exit_code = spot::ltl::format_parse_errors(std::cerr, argv[2], pel);
  }
  tm.stop("parsing formula");

  if (exit_code)
    goto safe_exit;

206
  tm.start("translating formula");
207
  {
208 209 210 211 212
    spot::translator trans(dict);
    if (deterministic)
      trans.set_pref(spot::postprocessor::Deterministic);

    prop = trans.run(&f);
213
  }
214
  tm.stop("translating formula");
215

216 217 218
  atomic_prop_collect(f, &ap);

  if (output != DotFormula)
219
    {
220 221 222 223
      tm.start("loading ltsmin model");
      model = spot::load_ltsmin(argv[1], dict, &ap, deadf,
				compress_states, true);
      tm.stop("loading ltsmin model");
224 225 226 227 228 229 230 231 232 233 234 235 236 237

      if (!model)
	{
	  exit_code = 1;
	  goto safe_exit;
	}

      if (output == DotModel)
	{
	  tm.start("dotty output");
	  spot::dotty_reachable(std::cout, model);
	  tm.stop("dotty output");
	  goto safe_exit;
	}
238 239 240
      if (output == Kripke)
      {
        tm.start("kripke output");
241
	spot::kripke_save_reachable_renumbered(std::cout, model);
242 243 244
        tm.stop("kripke output");
        goto safe_exit;
      }
245 246
    }

247 248 249 250 251 252 253 254
  if (output == DotFormula)
    {
      tm.start("dotty output");
      spot::dotty_reachable(std::cout, prop);
      tm.stop("dotty output");
      goto safe_exit;
    }

255
  product = spot::otf_product(model, prop);
256

257
  if (output == DotProduct)
258
    {
259 260 261 262
      tm.start("dotty output");
      spot::dotty_reachable(std::cout, product);
      tm.stop("dotty output");
      goto safe_exit;
263 264
    }

265 266 267
  assert(echeck_inst);

  {
268
    auto ec = echeck_inst->instantiate(product);
269 270 271 272
    bool search_many = echeck_inst->options().get("repeated");
    assert(ec);
    do
      {
273
	int memused = spot::memusage();
274
	tm.start("running emptiness check");
275
	spot::emptiness_check_result_ptr res;
276 277 278 279 280 281 282 283
	try
	  {
	    res = ec->check();
	  }
	catch (std::bad_alloc)
	  {
	    std::cerr << "Out of memory during emptiness check."
		      << std::endl;
284 285
	    if (!compress_states)
	      std::cerr << "Try option -z for state compression." << std::endl;
286 287 288
	    exit_code = 2;
	    exit(exit_code);
	  }
289
	tm.stop("running emptiness check");
290
	memused = spot::memusage() - memused;
291 292

	ec->print_stats(std::cout);
293 294
	std::cout << memused << " pages allocated for emptiness check"
		  << std::endl;
295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317

	if (expect_counter_example == !res &&
	    (!expect_counter_example || ec->safe()))
	  exit_code = 1;

	if (!res)
	  {
	    std::cout << "no accepting run found";
	    if (!ec->safe() && expect_counter_example)
	      {
		std::cout << " even if expected" << std::endl;
		std::cout << "this may be due to the use of the bit"
			  << " state hashing technique" << std::endl;
		std::cout << "you can try to increase the heap size "
			  << "or use an explicit storage"
			  << std::endl;
	      }
	    std::cout << std::endl;
	    break;
	  }
	else if (accepting_run)
	  {

318
	    spot::tgba_run_ptr run;
319
	    tm.start("computing accepting run");
320 321 322 323 324 325 326 327 328 329 330
	    try
	      {
		run = res->accepting_run();
	      }
	    catch (std::bad_alloc)
	      {
		std::cerr << "Out of memory while looking for counterexample."
			  << std::endl;
		exit_code = 2;
		exit(exit_code);
	      }
331 332 333 334 335 336 337 338 339
	    tm.stop("computing accepting run");

	    if (!run)
	      {
		std::cout << "an accepting run exists" << std::endl;
	      }
	    else
	      {
		tm.start("reducing accepting run");
340
		run = spot::reduce_run(res->automaton(), run);
341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
		tm.stop("reducing accepting run");

		tm.start("printing accepting run");
		spot::print_tgba_run(std::cout, product, run);
		tm.stop("printing accepting run");
	      }
	  }
	else
	  {
	    std::cout << "an accepting run exists "
		      << "(use -C to print it)" << std::endl;
	  }
      }
    while (search_many);
  }

 safe_exit:
  if (f)
    f->destroy();

361 362
  deadf->destroy();

363 364
  if (use_timer)
    tm.print(std::cout);
365
  tm.reset_all();		// This helps valgrind.
366 367
  return exit_code;
}
368

369 370 371 372 373 374
int
main(int argc, char **argv)
{
  auto exit_code = checked_main(argc, argv);

  // Additional checks to debug reference counts in formulas.
375 376 377 378
  spot::ltl::atomic_prop::dump_instances(std::cerr);
  spot::ltl::unop::dump_instances(std::cerr);
  spot::ltl::binop::dump_instances(std::cerr);
  spot::ltl::multop::dump_instances(std::cerr);
379
  spot::ltl::bunop::dump_instances(std::cerr);
380 381 382 383
  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);
384
  assert(spot::ltl::bunop::instance_count() == 0);
385
  exit(exit_code);
386
}