dtbasat.cc 34.3 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
3
// Copyright (C) 2013, 2014, 2015 Laboratoire de Recherche et
// Développement de l'Epita.
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//
// 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 3 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 this program.  If not, see <http://www.gnu.org/licenses/>.

Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
20
#include <fstream>
21
22
#include <sstream>
#include <map>
23
#include <spot/misc/bddlt.hh>
24
25
#include <spot/misc/satsolver.hh>
#include <spot/misc/timer.hh>
26
27
#include <spot/priv/satcommon.hh>
#include <spot/twaalgos/dtbasat.hh>
28
#include <spot/twaalgos/langmap.hh>
29
30
#include <spot/twaalgos/sccinfo.hh>
#include <spot/twaalgos/stats.hh>
31

32
33
34
// If you set the SPOT_TMPKEEP environment variable the temporary
// file used to communicate with the sat solver will be left in
// the current directory.
35
//
36
37
38
39
// Additionally, if the following DEBUG macro is set to 1, the CNF
// file will be output with a comment before each clause, and an
// additional output file (dtba-sat.dbg) will be created with a list
// of all positive variables in the result and their meaning.
40
41

#define DEBUG 0
42

43
44
#if DEBUG
#define dout out << "c "
45
#define cnf_comment(...) solver.comment(__VA_ARGS__)
46
#define trace std::cerr
47
#else
48
#define cnf_comment(...) while (0) solver.comment(__VA_ARGS__)
49
50
#define dout while (0) std::cout
#define trace dout
51
52
53
54
55
56
#endif

namespace spot
{
  namespace
  {
57
    static bdd_dict_ptr debug_dict;
58

59
    struct path
60
    {
61
62
      int src_ref;
      int dst_ref;
63

64
65
      path(int src_ref, int dst_ref)
        : src_ref(src_ref), dst_ref(dst_ref)
66
67
68
      {
      }

69
70
71
72
73
74
      path(int src_ref)
        : src_ref(src_ref), dst_ref(src_ref)
      {
      }

      bool operator<(const path& other) const
75
      {
76
        if (this->src_ref < other.src_ref)
77
          return true;
78
        if (this->src_ref > other.src_ref)
79
          return false;
80
        if (this->dst_ref < other.dst_ref)
81
          return true;
82
        if (this->dst_ref > other.dst_ref)
83
          return false;
84
        return false;
85
86
87
88
      }

    };

89
    struct dict
90
    {
91
92
93
94
95
96
97
      std::vector<bdd> alpha_vect;
      std::map<path, unsigned> path_map;
      std::map<bdd, unsigned, bdd_less_than> alpha_map;
      vars_helper helper;
      int nvars = 0;
      unsigned cand_size;
      unsigned ref_size;
98

99
100
      int
      transid(unsigned src, unsigned cond, unsigned dst)
101
      {
102
        return helper.get_t(src, cond, dst);
103
104
      }

105
106
      int
      transid(unsigned src, bdd& cond, unsigned dst)
107
      {
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#if DEBUG
        try
        {
          return helper.get_t(src, alpha_map.at(cond), dst);
        }
        catch (const std::out_of_range& c)
        {
          std::cerr << "label of transid " << fmt_t(src, cond, dst)
            << " not found.\n";
          throw c;
        }
#else
        return helper.get_t(src, alpha_map[cond], dst);
#endif
122
123
      }

124
125
      int
      transacc(unsigned src, unsigned cond, unsigned dst)
126
      {
127
        return helper.get_ta(src, cond, dst);
128
129
      }

130
131
      int
      transacc(unsigned src, bdd& cond, unsigned dst)
132
      {
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#if DEBUG
        try
        {
          return helper.get_ta(src, alpha_map.at(cond), dst);
        }
        catch (const std::out_of_range& c)
        {
          std::cerr << "label of transacc " << fmt_t(src, cond, dst)
            << " not found.\n";
          throw c;
        }
#else
        return helper.get_ta(src, alpha_map[cond], dst);
#endif
147
148
      }

149
150
151
      int
      pathid_ref(unsigned src_cand, unsigned src_ref, unsigned dst_cand,
          unsigned dst_ref)
152
      {
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
#if DEBUG
        try
        {
          return helper.get_prc(
              path_map.at(path(src_ref, dst_ref)), src_cand, dst_cand, false);
        }
        catch (const std::out_of_range& c)
        {
          std::cerr << "path(" << src_ref << ',' << dst_ref << ") of pathid_ref"
            << ' ' << fmt_p(src_cand, src_ref, dst_cand, dst_ref)
            << " not found.\n";
          throw c;
        }
#else
        return helper.get_prc(
            path_map[path(src_ref, dst_ref)], src_cand, dst_cand, false);
#endif
170
171
      }

172
173
174
#if DEBUG
      int
      pathid_ref(unsigned path, unsigned src_cand, unsigned dst_cand)
175
      {
176
        return helper.get_prc(path, src_cand, dst_cand, false);
177
178
      }

179
180
      int
      pathid_cand(unsigned path, unsigned src_cand, unsigned dst_cand)
181
      {
182
        return helper.get_prc(path, src_cand, dst_cand, true);
183
      }
184
#endif
185

186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
      int
      pathid_cand(unsigned src_cand, unsigned src_ref, unsigned dst_cand,
          unsigned dst_ref)
      {
#if DEBUG
        try
        {
          return helper.get_prc(
              path_map.at(path(src_ref, dst_ref)), src_cand, dst_cand, true);
        }
        catch (const std::out_of_range& c)
        {
          std::cerr << "path(" << src_ref << ',' << dst_ref
            << ") of pathid_cand "
            << fmt_p(src_cand, src_ref, dst_cand, dst_ref) << " not found.\n";
          throw c;
        }
#else
        return helper.get_prc(
            path_map[path(src_ref, dst_ref)], src_cand, dst_cand, true);
#endif
      }
208

209
210
211
212
213
      std::string
      fmt_t(unsigned src, bdd& cond, unsigned dst)
      {
        return helper.format_t(debug_dict, src, cond, dst);
      }
214

215
216
217
218
219
      std::string
      fmt_t(unsigned src, unsigned cond, unsigned dst)
      {
        return helper.format_t(debug_dict, src, alpha_vect[cond], dst);
      }
220

221
222
223
224
225
226
      std::string
      fmt_p(unsigned src_cand, unsigned src_ref, unsigned dst_cand,
          unsigned dst_ref)
      {
        return helper.format_p(src_cand, src_ref, dst_cand, dst_ref);
      }
227
228
229

    };

230
    void declare_vars(const const_twa_graph_ptr& aut,
231
232
233
234
                          dict& d,
                          bdd ap,
                          bool state_based,
                          scc_info& sm)
235
    {
236
      d.ref_size = aut->num_states();
237

238
      if (d.cand_size == -1U)
239
        for (unsigned i = 0; i < d.ref_size; ++i)
240
241
242
243
          if (sm.reachable_state(i))
            ++d.cand_size;        // Note that we start from -1U the
                                // cand_size is one less than the
                                // number of reachable states.
244

245
246
247
248
249
250
251
252
253
254
255
256
      // In order to optimize memory usage, src_cand & dst_cand have been
      // removed from path struct (the reasons are: they were no optimization
      // on them and their values are known from the beginning).
      //
      // However, since some optimizations are based on the following i and k,
      // it is necessary to associate to each path constructed, an ID number.
      //
      // Given this ID, src_cand, dst_cand and a boolean that tells we want
      // ref or cand var, the corresponding litteral can be retrieved thanks
      // to get_prc(...), a vars_helper's method.
      unsigned path_size = 0;
      for (unsigned i = 0; i < d.ref_size; ++i)
257
258
259
260
261
262
        {
          if (!sm.reachable_state(i))
            continue;
          unsigned i_scc = sm.scc_of(i);
          bool is_trivial = sm.is_trivial(i_scc);

263
          for (unsigned k = 0; k < d.ref_size; ++k)
264
            {
265
              if (!sm.reachable_state(k))
266
                continue;
267
268
269
270
              if ((sm.scc_of(k) != i_scc || is_trivial)
                    && !(i == k))
                continue;
              d.path_map[path(i, k)] = path_size++;
271
272
273
            }
        }

274
275
276
277
278
279
280
281
282
283
284
285
      // Fill dict's bdd vetor (alpha_vect) and save each bdd and it's
      // corresponding index in alpha_map. This is necessary beacause some
      // loops start from a precise bdd. Therefore, it's useful to know
      // it's corresponding index to deal with vars_helper.
      bdd all = bddtrue;
      for (unsigned j = 0; all != bddfalse; ++j)
      {
        bdd one = bdd_satoneset(all, ap, bddfalse);
        d.alpha_vect.push_back(one);
        d.alpha_map[d.alpha_vect[j]] = j;
        all -= one;
      }
286

287
288
289
290
      // Initialize vars_helper by giving it all the necessary information.
      // 1: nacc_size is 1 (with Büchi) | true: means dtbasat, i-e, not dtwasat.
      d.helper.init(d.cand_size, d.alpha_vect.size(), d.cand_size,
        1, path_size, state_based, true);
291

292
293
      // Based on all previous informations, helper knows all litterals.
      d.helper.declare_all_vars(++d.nvars);
294
    }
295

296
297
    typedef std::pair<int, int> sat_stats;

298
    static
299
    sat_stats dtba_to_sat(satsolver& solver,
300
                          const const_twa_graph_ptr& ref,
301
302
                          dict& d,
                          bool state_based)
303
    {
304
305
      // Compute the AP used.
      bdd ap = ref->ap_vars();
306

307
      // Count the number of atomic propositions.
308
309
      int nap = 0;
      {
310
311
312
313
314
315
316
        bdd cur = ap;
        while (cur != bddtrue)
          {
            ++nap;
            cur = bdd_high(cur);
          }
        nap = 1 << nap;
317
318
      }

319
320
321
      scc_info sm(ref);

      // Number all the SAT variables we may need.
322
323
324
325
      declare_vars(ref, d, ap, state_based, sm);

      // Store alpha_vect's size once for all.
      unsigned alpha_size = d.alpha_vect.size();
326

327
      // Tell the satsolver the number of variables.
328
329
      solver.adjust_nvars(d.nvars);

330
      // Empty automaton is impossible.
331
      assert(d.cand_size > 0);
332
333
334

#if DEBUG
      debug_dict = ref->get_dict();
335
336
      solver.comment("d.ref_size", d.ref_size, '\n');
      solver.comment("d.cand_size", d.cand_size, '\n');
337
338
#endif

339
      cnf_comment("symmetry-breaking clauses\n");
340
      unsigned j = 0;
341
342
343
344
345
346
347
348
      for (unsigned l = 0; l < alpha_size; ++l, ++j)
        for (unsigned i = 0; i < d.cand_size - 1; ++i)
          for (unsigned k = i * nap + j + 2; k < d.cand_size; ++k)
            {
              cnf_comment("¬", d.fmt_t(i, l, k), '\n');
              solver.add({-d.transid(i, l, k), 0});
            }

349
350
      if (!solver.get_nb_clauses())
         cnf_comment("(none)\n");
351

352
      cnf_comment("(1) the candidate automaton is complete\n");
353
      for (unsigned q1 = 0; q1 < d.cand_size; ++q1)
354
355
        for (unsigned l = 0; l < alpha_size; ++l)
          {
356
#if DEBUG
357
358
359
360
361
362
363
364
            solver.comment("");
            for (unsigned q2 = 0; q2 < d.cand_size; q2++)
              {
                solver.comment_rec(d.fmt_t(q1, l, q2), "δ");
                if (q2 != d.cand_size)
                  solver.comment_rec(" ∨ ");
              }
            solver.comment_rec('\n');
365
#endif
366
367
368
369
            for (unsigned q2 = 0; q2 < d.cand_size; q2++)
              solver.add(d.transid(q1, l, q2));
            solver.add(0);
          }
370

371
      cnf_comment("(2) the initial state is reachable\n");
372
      {
373
        unsigned init = ref->get_init_state_number();
374
375
        cnf_comment(d.fmt_p(0, init, 0, init), '\n');
        solver.add({d.pathid_ref(0, init, 0, init), 0});
376
      }
377

378
      for (unsigned q1 = 0; q1 < d.cand_size; ++q1)
379
        {
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
          for (unsigned q1p = 0; q1p < d.ref_size; ++q1p)
          {
            // Added to comply with the variable declaration, i-e to avoid
            // using undeclared variables.
            if (!sm.reachable_state(q1p))
              continue;

            cnf_comment("(3) augmenting paths based on Cand[", q1, "] and Ref[",
                        q1p, "]\n");
            for (auto& tr: ref->out(q1p))
              {
                unsigned dp = tr.dst;
                bdd all = tr.cond;
                while (all != bddfalse)
                  {
                    bdd s = bdd_satoneset(all, ap, bddfalse);
                    all -= s;
397

398
399
400
401
402
403
404
405
406
407
408
409
410
411
                    for (unsigned q2 = 0; q2 < d.cand_size; q2++)
                      {
                        int prev = d.pathid_ref(q1, q1p, q1, q1p);
                        int succ = d.pathid_ref(q2, dp, q2, dp);
                        if (prev == succ)
                          continue;

                        cnf_comment(prev, "∧", d.fmt_t(q1, s, q2), "δ →",
                                    d.fmt_p(q2, dp, q2, dp), '\n');
                        solver.add({-prev, -d.transid(q1, s, q2), succ, 0});
                      }
                  }
              }
          }
412
        }
413

414
      const acc_cond& ra = ref->acc();
415
416
417
418

      // construction of contraints (4,5) : all loops in the product
      // where no accepting run is detected in the ref. automaton,
      // must also be marked as not accepting in the cand. automaton
419
      for (unsigned q1p = 0; q1p < d.ref_size; ++q1p)
420
421
422
423
424
425
        {
          if (!sm.reachable_state(q1p))
            continue;
          unsigned q1p_scc = sm.scc_of(q1p);
          if (sm.is_trivial(q1p_scc))
            continue;
426
          for (unsigned q2p = 0; q2p < d.ref_size; ++q2p)
427
428
429
430
431
432
433
434
435
436
            {
              if (!sm.reachable_state(q2p))
                continue;
              // We are only interested in transition that can form a
              // cycle, so they must belong to the same SCC.
              if (sm.scc_of(q2p) != q1p_scc)
                continue;
              for (unsigned q1 = 0; q1 < d.cand_size; ++q1)
                for (unsigned q2 = 0; q2 < d.cand_size; ++q2)
                  {
437
                    std::string f_p = d.fmt_p(q1, q1p, q2, q2p);
438
                    cnf_comment("(4&5) matching paths from reference based on",
439
                                f_p, '\n');
440

441
                    int pid1 = d.pathid_ref(q1, q1p, q2, q2p);
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
                    for (auto& tr: ref->out(q2p))
                      {
                        unsigned dp = tr.dst;
                        // Skip destinations not in the SCC.
                        if (sm.scc_of(dp) != q1p_scc)
                          continue;

                        if (ra.accepting(tr.acc))
                          continue;
                        for (unsigned q3 = 0; q3 < d.cand_size; ++q3)
                          {
                            if (dp == q1p && q3 == q1) // (4) looping
                              {
                                bdd all = tr.cond;
                                while (all != bddfalse)
                                  {
                                    bdd s = bdd_satoneset(all, ap, bddfalse);
                                    all -= s;
460
461
462
#if DEBUG
                                    std::string f_t = d.fmt_t(q2, s, q1);
                                    cnf_comment(f_p, "R ∧", f_t, "δ → ¬", f_t,
463
                                                "F\n");
464
465
466
467
468
#endif
                                    solver.add({-pid1,
                                                -d.transid(q2, s, q1),
                                                -d.transacc(q2, s, q1),
                                                0});
469
470
471
472
                                  }
                              }
                            else // (5) not looping
                              {
473
                                int pid2 = d.pathid_ref(q1, q1p, q3, dp);
474
475
476
477
478
479
480
481
482
                                if (pid1 == pid2)
                                  continue;

                                bdd all = tr.cond;
                                while (all != bddfalse)
                                  {
                                    bdd s = bdd_satoneset(all, ap, bddfalse);
                                    all -= s;

483
484
485
486
487
488
489
                                    cnf_comment(f_p, "R ∧", d.fmt_t(q2, s, q3),
                                                "δ →", d.fmt_p(q1, q1p, q3, dp),
                                                "R\n");
                                    solver.add({-pid1,
                                                -d.transid(q2, s, q3),
                                                pid2,
                                                0});
490
491
492
493
494
495
496
                                  }
                              }
                          }
                      }
                  }
            }
        }
497
498
499
      // construction of contraints (6,7): all loops in the product
      // where accepting run is detected in the ref. automaton, must
      // also be marked as accepting in the candidate.
500
      for (unsigned q1p = 0; q1p < d.ref_size; ++q1p)
501
502
503
504
505
506
        {
          if (!sm.reachable_state(q1p))
            continue;
          unsigned q1p_scc = sm.scc_of(q1p);
          if (sm.is_trivial(q1p_scc))
            continue;
507
          for (unsigned q2p = 0; q2p < d.ref_size; ++q2p)
508
509
510
511
512
513
514
515
516
517
            {
              if (!sm.reachable_state(q2p))
                continue;
              // We are only interested in transition that can form a
              // cycle, so they must belong to the same SCC.
              if (sm.scc_of(q2p) != q1p_scc)
                continue;
              for (unsigned q1 = 0; q1 < d.cand_size; ++q1)
                for (unsigned q2 = 0; q2 < d.cand_size; ++q2)
                  {
518
                    std::string f_p = d.fmt_p(q1, q1p, q2, q2p);
519
                    cnf_comment("(6&7) matching paths from candidate based on",
520
                                f_p, '\n');
521
522
523

                    int pid1;
                    if (q1 == q2 && q1p == q2p)
524
                      pid1 = d.pathid_ref(q1, q1p, q2, q2p);
525
                    else
526
                      pid1 = d.pathid_cand(q1, q1p, q2, q2p);
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546

                    for (auto& tr: ref->out(q2p))
                      {
                        unsigned dp = tr.dst;
                        // Skip destinations not in the SCC.
                        if (sm.scc_of(dp) != q1p_scc)
                          continue;
                        for (unsigned q3 = 0; q3 < d.cand_size; q3++)
                          {
                            if (dp == q1p && q3 == q1) // (6) looping
                              {
                                // We only care about the looping case if
                                // it is accepting in the reference.
                                if (!ra.accepting(tr.acc))
                                  continue;
                                bdd all = tr.cond;
                                while (all != bddfalse)
                                  {
                                    bdd s = bdd_satoneset(all, ap, bddfalse);
                                    all -= s;
547
548
549
550
551
552
553
554
555
#if DEBUG
                                    std::string f_t = d.fmt_t(q2, s, q1);
                                    cnf_comment(f_p, "C ∧", f_t, "δ →", f_t,
                                                "F\n");
#endif
                                    solver.add({-pid1,
                                                -d.transid(q2, s, q1),
                                                d.transacc(q2, s, q1),
                                                0});
556
557
558
559
                                  }
                              }
                            else // (7) no loop
                              {
560
                                int pid2 = d.pathid_cand(q1, q1p, q3, dp);
561
562
563
564
565
566
567
568
                                if (pid1 == pid2)
                                  continue;

                                bdd all = tr.cond;
                                while (all != bddfalse)
                                  {
                                    bdd s = bdd_satoneset(all, ap, bddfalse);
                                    all -= s;
569
570
571
572
573
574
575
576
577
578
579
#if DEBUG
                                    std::string f_t = d.fmt_t(q2, s, q3);
                                    cnf_comment(f_p, "C ∧", f_t, "δ ∧ ¬", f_t,
                                                "F →", d.fmt_p(q1, q1p, q3, dp),
                                                "C\n");
#endif
                                    solver.add({-pid1,
                                                -d.transid(q2, s, q3),
                                                d.transacc(q2, s, q3),
                                                pid2,
                                                0});
580
581
582
583
584
585
586
                                  }
                              }
                          }
                      }
                  }
            }
        }
587
      return solver.stats();
588
589
    }

590
    static twa_graph_ptr
591
    sat_build(const satsolver::solution& solution, dict& satdict,
592
              const_twa_graph_ptr aut, bool state_based)
593
    {
594
595
      trace << "sat_build(...)\n";

596
      auto autdict = aut->get_dict();
597
      auto a = make_twa_graph(autdict);
598
      a->copy_ap_of(aut);
599
      a->set_buchi();
600
      if (state_based)
601
        a->prop_state_acc(true);
602
      a->prop_deterministic(true);
603
      a->new_states(satdict.cand_size);
604
605
606

#if DEBUG
      std::fstream out("dtba-sat.dbg",
607
                       std::ios_base::trunc | std::ios_base::out);
Alexandre Duret-Lutz's avatar
Alexandre Duret-Lutz committed
608
      out.exceptions(std::ifstream::failbit | std::ifstream::badbit);
609
#endif
610
      std::set<int> acc_states;
611
      std::set<src_cond> seen_trans;
612

613
614
615
616
617
618
619
      unsigned alpha_size = satdict.alpha_vect.size();
      unsigned cand_size = satdict.cand_size;
      for (unsigned i = 0; i < cand_size; ++i)
        for (unsigned j = 0; j < alpha_size; ++j)
          for (unsigned k = 0; k < cand_size; ++k)
          {
            if (solution[satdict.transid(i, j, k) - 1])
620
            {
621
              // Ignore unuseful transitions because of reduced cand_size.
622
              if (i >= cand_size)
623
624
                continue;

625
              // Skip (s,l,d2) if we have already seen some (s,l,d1).
626
627
628
629
630
631
632
633
634
635
636
637
638
              if (seen_trans.insert(src_cond(i, satdict.alpha_vect[j])).second)
              {
                bool accept = false;
                if (state_based)
                  accept = acc_states.find(i) != acc_states.end();
                if (!accept)
                  accept = solution[satdict.transacc(i, j, k) - 1];

                a->new_acc_edge(i, k, satdict.alpha_vect[j], accept);

                if (state_based && accept)
                  acc_states.insert(i);
              }
639
            }
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
          }
#if DEBUG
      dout << "--- transition variables ---\n";
      for (unsigned i = 0; i < cand_size; ++i)
        for (unsigned j = 0; j < alpha_size; ++j)
          for (unsigned k = 0; k < cand_size; ++k)
          {
            int var = satdict.transid(i, j, k);
            std::string f_t = satdict.fmt_t(i, j, k);
            if (solution[var - 1])
              dout << ' ' << var << "\t " << f_t << '\n';
            else
              dout << -var << "\t¬" << f_t << '\n';
          }
      dout << "--- transition_acc variables ---\n";
      if (state_based)
      {
        dout << "In state_based mode with Büchi automaton, there is only 1 "
          "litteral for each src, regardless of dst or cond!\n";
        for (unsigned i = 0; i < cand_size; ++i)
        {
          int var = satdict.transacc(i, 0, 0);
          std::string f_t = satdict.fmt_t(i, 0, 0);
          if (solution[var - 1])
            dout << ' ' << var << "\t " << f_t << '\n';
665
          else
666
667
668
669
670
671
672
            dout << -var << "\t¬" << f_t << '\n';
        }
      }
      else
        for (unsigned i = 0; i < cand_size; ++i)
          for (unsigned j = 0; j < alpha_size; ++j)
            for (unsigned k = 0; k < cand_size; ++k)
673
            {
674
675
676
677
678
679
              int var = satdict.transacc(i, j, k);
              std::string f_t = satdict.fmt_t(i, j, k);
              if (solution[var - 1])
                dout << ' ' << var << "\t " << f_t << '\n';
              else
                dout << -var << "\t¬" << f_t << '\n';
680
            }
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
      dout << "--- ref pathid variables ---\n";
      std::map<int, std::string> cand_vars;
      for (auto it = satdict.path_map.begin(); it != satdict.path_map.end();
          ++it)
        for (unsigned k = 0; k < cand_size; ++k)
          for (unsigned l = 0; l < cand_size; ++l)
          {
            // false:reference | true:cand
            int cand_v = satdict.pathid_cand(it->second, k, l);
            int ref_v = satdict.pathid_ref(it->second, k, l);
            std::string f_p = satdict.fmt_p(k, it->first.src_ref, l,
                it->first.dst_ref);

            cand_vars[cand_v] = f_p;
            if (solution[ref_v - 1])
              dout << ' ' << ref_v << "\t " << f_p << '\n';
            else
              dout << -ref_v << "\t¬" << f_p << '\n';
          }
      dout << "--- cand pathid variables ---\n";
      for (auto it = cand_vars.begin(); it != cand_vars.end(); ++it)
      {
        if (solution[it->first - 1])
          dout << ' ' << it->first << "\t " << it->second << '\n';
705
        else
706
707
          dout << -it->first << "\t¬" << it->second << '\n';
      }
708
#endif
709
      a->merge_edges();
710
711
712
713
      return a;
    }
  }

714
715
  twa_graph_ptr
  dtba_sat_synthetize(const const_twa_graph_ptr& a,
716
                      int target_state_number, bool state_based)
717
  {
718
719
    if (!a->acc().is_buchi())
      throw std::runtime_error
720
        ("dtba_sat() can only work with Büchi acceptance");
721
    if (target_state_number == 0)
722
      return nullptr;
723
    trace << "dtba_sat_synthetize(..., states = " << target_state_number
724
          << ", state_based = " << state_based << ")\n";
725
726
    dict d;
    d.cand_size = target_state_number;
727

728
729
    satsolver solver;
    satsolver::solution_pair solution;
730

731
732
    timer_map t;
    t.start("encode");
733
    dtba_to_sat(solver, a, d, state_based);
734
735
    t.stop("encode");
    t.start("solve");
736
    solution = solver.get_solution();
737
    t.stop("solve");
738

739
    twa_graph_ptr res = nullptr;
740
741
    if (!solution.second.empty())
      res = sat_build(solution.second, d, a, state_based);
742

743
    print_log(t, target_state_number, res, solver); // If SPOT_SATLOG is set.
744

745
    trace << "dtba_sat_synthetize(...) = " << res << '\n';
746
747
748
    return res;
  }

749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
  static twa_graph_ptr
  dichotomy_dtba_research(int max,
                          dict& d,
                          satsolver& solver,
                          timer_map& t1,
                          const_twa_graph_ptr& prev,
                          bool state_based)
  {
    trace << "dichotomy_dtba_research(...)\n";
    int min = 1;
    int target = 0;
    twa_graph_ptr res = nullptr;

    while (min < max)
    {
      target = (max + min) / 2;
      trace << "min:" << min << ", max:" << max << ", target:" << target
        << '\n';

      solver.assume(d.nvars + target);
      trace << "solver.assume(" << d.nvars + target << ")\n";

      satsolver::solution_pair solution = solver.get_solution();
      if (solution.second.empty())
      {
        trace << "UNSAT\n";
        max = target;
      }
      else
      {
        trace << "SAT\n";
        res = sat_build(solution.second, d, prev, state_based);
        min = d.cand_size - stats_reachable(res).states + 1;
      }
    }

    trace << "End with max:" << max << ", min:" << min << '\n';
    if (!res)
    {
      trace << "All assumptions are UNSAT, let's try without...";
      satsolver::solution_pair solution = solver.get_solution();
      trace << (solution.second.empty() ? "UNSAT!\n" : "SAT\n");
      res = solution.second.empty() ? nullptr :
        sat_build(solution.second, d, prev, state_based);
    }

    t1.stop("solve");
    print_log(t1, d.cand_size - target, res, solver); // SPOT_SATLOG.
    return res ? res : std::const_pointer_cast<spot::twa_graph>(prev);
  }

  twa_graph_ptr
  dtba_sat_minimize_assume(const const_twa_graph_ptr& a,
                           bool state_based,
                           int max_states,
                           int sat_incr_steps)
  {
    if (!a->acc().is_buchi())
      throw std::runtime_error
        ("dtba_sat_minimize_assume() can only work with Büchi acceptance");
    if (sat_incr_steps < 0)
      throw std::runtime_error("with 'assume' algorithm, sat_incr_steps value "
                               " must be >= 0");

    const_twa_graph_ptr prev = a;
    dict d;
    d.cand_size = (max_states < 0) ?
      stats_reachable(prev).states - 1 : max_states;
    if (d.cand_size == 0)
      return nullptr;

    trace << "dtba_sat_minimize_assume(..., states = " << d.cand_size
      << ", state_based = " << state_based << ")\n";
    trace << "sat_incr_steps: " << sat_incr_steps << '\n';

    twa_graph_ptr next = spot::make_twa_graph(spot::make_bdd_dict());
    while (next && d.cand_size > 0)
    {
      // Warns the satsolver of the number of assumptions.
      int n_assumptions = (int) d.cand_size < sat_incr_steps ?
        d.cand_size - 1 : sat_incr_steps;
      trace << "number of assumptions:" << n_assumptions << '\n';
      satsolver solver;
      solver.set_nassumptions_vars(n_assumptions);

      // First iteration of classic solving.
      timer_map t1;
      t1.start("encode");
      dtba_to_sat(solver, prev, d, state_based);

      // Compute the AP used.
      bdd ap = prev->ap_vars();

      // Add all assumptions clauses.
      unsigned dst = d.cand_size - 1;
      unsigned alpha_size = d.alpha_vect.size();
      for (int i = 1; i <= n_assumptions; i++, dst--)
      {
        cnf_comment("Next iteration:", dst, "\n");
        int assume_lit = d.nvars + i;

        cnf_comment("Add clauses to forbid the dst state.\n");
        for (unsigned l = 0; l < alpha_size; ++l)
          for (unsigned j = 0; j < d.cand_size; ++j)
          {
            cnf_comment(assume_lit, "→ ¬", d.fmt_t(j, l, dst), '\n');
            solver.add({-assume_lit, -d.transid(j, l, dst), 0});
          }

        // The assumption which has just been encoded implies the preceding
        // ones.
        if (i != 1)
        {
          cnf_comment(assume_lit, "→", assume_lit - 1, '\n');
          solver.add({-assume_lit, assume_lit - 1, 0});
        }
      }
      t1.stop("encode");

      t1.start("solve");
      if (n_assumptions)
      {
        trace << "solver.assume(" << d.nvars + n_assumptions << ")\n";
        solver.assume(d.nvars + n_assumptions);
      }
      satsolver::solution_pair solution = solver.get_solution();

      if (solution.second.empty() && n_assumptions) // UNSAT
      {
        trace << "UNSAT\n";
        return dichotomy_dtba_research(n_assumptions, d, solver, t1, prev,
                                       state_based);
      }

      t1.stop("solve");
      trace << "SAT, restarting from zero\n";
      next = solution.second.empty() ? nullptr :
        sat_build(solution.second, d, prev, state_based);
      print_log(t1, d.cand_size - n_assumptions, next, solver); // SPOT_SATLOG.

      if (next)
      {
        prev = next;
        d = dict();
        d.cand_size = stats_reachable(prev).states - 1;
        if (d.cand_size == 0)
          next = nullptr;
      }
    }

    return prev == a ? nullptr : std::const_pointer_cast<spot::twa_graph>(prev);
  }

902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
  twa_graph_ptr
  dtba_sat_minimize_incr(const const_twa_graph_ptr& a,
      bool state_based, int max_states, int sat_incr_steps)
  {
    if (!a->acc().is_buchi())
      throw std::runtime_error
        (": dtba_sat_minimize_incr() can only work with Büchi acceptance.");
    const_twa_graph_ptr prev = a;
    dict d;
    d.cand_size = (max_states < 0) ?
      stats_reachable(prev).states - 1 : max_states;
    if (d.cand_size == 0)
      return nullptr;

    trace << "dtba_sat_minimize_incr(..., states = " << d.cand_size
      << ", state_based = " << state_based << ")\n";

    bool naive = sat_incr_steps < 0;
    trace << "sat_incr_steps: " << sat_incr_steps << '\n';

    twa_graph_ptr next = spot::make_twa_graph(spot::make_bdd_dict());
    while (next && d.cand_size > 0)
    {
      // First iteration of classic solving.
      satsolver solver;
      timer_map t1;
      t1.start("encode");
      dtba_to_sat(solver, prev, d, state_based);
      t1.stop("encode");
      t1.start("solve");
      satsolver::solution_pair solution = solver.get_solution();
      t1.stop("solve");
      next = solution.second.empty() ? nullptr :
        sat_build(solution.second, d, prev, state_based);
      print_log(t1, d.cand_size, next, solver); // If SPOT_SATLOG is set.

      trace << "First iteration done\n";

      // Compute the AP used.
      bdd ap = prev->ap_vars();

      // Incremental solving loop.
      unsigned orig_cand_size = d.cand_size;
      unsigned alpha_size = d.alpha_vect.size();
      for (int k = 0; next && d.cand_size > 0 && (naive || k < sat_incr_steps);
           ++k)
      {
        t1.start("encode");
        prev = next;
        int reach_states = stats_reachable(prev).states;
        cnf_comment("Next iteration: ", reach_states - 1, "\n");

        trace << "Encoding the deletion of state " << reach_states - 1 << '\n';

        // Add new constraints.
        for (unsigned i = reach_states - 1; i < d.cand_size; ++i)
          for (unsigned l = 0; l < alpha_size; ++l)
            for (unsigned j = 0; j < orig_cand_size; ++j)
              solver.add({-d.transid(j, l, i), 0});

        d.cand_size = reach_states - 1;
        t1.stop("encode");
        t1.start("solve");
        satsolver::solution_pair solution = solver.get_solution();
        t1.stop("solve");
        next = solution.second.empty() ? nullptr :
          sat_build(solution.second, d, prev, state_based);
        print_log(t1, d.cand_size, next, solver); // If SPOT_SATLOG is set.
      }

      if (next)
      {
        trace << "Starting from scratch\n";
        prev = next;
        d = dict();
        d.cand_size = stats_reachable(prev).states - 1;
        if (d.cand_size == 0)
          next = nullptr;
      }
    }

    return prev == a ? nullptr : std::const_pointer_cast<spot::twa_graph>(prev);
  }

986
  twa_graph_ptr
987
  dtba_sat_minimize(const const_twa_graph_ptr& a,
988
                    bool state_based, int max_states)
989
  {
990
991
    int n_states = (max_states < 0) ?
      stats_reachable(a).states : max_states + 1;
992

993
    twa_graph_ptr prev = nullptr;
994
    for (;;)
995
      {
996
997
998
999
1000
1001
1002
        auto next =
          dtba_sat_synthetize(prev ? prev : a, --n_states, state_based);
        if (!next)
          return prev;
        else
          n_states = stats_reachable(next).states;
        prev = next;
1003
      }
1004
    SPOT_UNREACHABLE();
1005
  }
1006

1007
1008
  twa_graph_ptr
  dtba_sat_minimize_dichotomy(const const_twa_graph_ptr& a,
1009
                              bool state_based, bool langmap, int max_states)
1010
  {
1011
    trace << "Dichomoty\n";
1012
1013
    if (max_states < 0)
      max_states = stats_reachable(a).states - 1;
1014
    int min_states = 1;
1015
1016
1017
1018
1019
1020
1021
    if (langmap)
    {
      trace << "Langmap\n";
      std::vector<unsigned> v = language_map(a);
      min_states = get_number_of_distinct_vals(v);
    }
    trace << "min_states=" << min_states << '\n';
1022

1023
    twa_graph_ptr prev = nullptr;
1024
    while (min_states <= max_states)
1025
      {
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
        int target = (max_states + min_states) / 2;
        auto next = dtba_sat_synthetize(prev ? prev : a, target, state_based);
        if (!next)
          {
            min_states = target + 1;
          }
        else
          {
            prev = next;
            max_states = stats_reachable(next).states - 1;
          }
1037
      }
1038
    return prev;
1039
1040
  }
}