dtbasat.cc 34 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
28
29
#include <spot/priv/satcommon.hh>
#include <spot/twaalgos/dtbasat.hh>
#include <spot/twaalgos/sccinfo.hh>
#include <spot/twaalgos/stats.hh>
30

31
32
33
// 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.
34
//
35
36
37
38
// 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.
39
40

#define DEBUG 0
41

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

namespace spot
{
  namespace
  {
56
    static bdd_dict_ptr debug_dict;
57

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

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

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

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

    };

88
    struct dict
89
    {
90
91
92
93
94
95
96
      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;
97

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

104
105
      int
      transid(unsigned src, bdd& cond, unsigned dst)
106
      {
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#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
121
122
      }

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

129
130
      int
      transacc(unsigned src, bdd& cond, unsigned dst)
131
      {
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#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
146
147
      }

148
149
150
      int
      pathid_ref(unsigned src_cand, unsigned src_ref, unsigned dst_cand,
          unsigned dst_ref)
151
      {
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#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
169
170
      }

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

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

185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
      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
      }
207

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

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

220
221
222
223
224
225
      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);
      }
226
227
228

    };

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

237
      if (d.cand_size == -1U)
238
        for (unsigned i = 0; i < d.ref_size; ++i)
239
240
241
242
          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.
243

244
245
246
247
248
249
250
251
252
253
254
255
      // 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)
256
257
258
259
260
261
        {
          if (!sm.reachable_state(i))
            continue;
          unsigned i_scc = sm.scc_of(i);
          bool is_trivial = sm.is_trivial(i_scc);

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

273
274
275
276
277
278
279
280
281
282
283
284
      // 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;
      }
285

286
287
288
289
      // 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);
290

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

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

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

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

318
319
320
      scc_info sm(ref);

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

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

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

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

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

338
      cnf_comment("symmetry-breaking clauses\n");
339
      unsigned j = 0;
340
341
342
343
344
345
346
347
      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});
            }

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

351
      cnf_comment("(1) the candidate automaton is complete\n");
352
      for (unsigned q1 = 0; q1 < d.cand_size; ++q1)
353
354
        for (unsigned l = 0; l < alpha_size; ++l)
          {
355
#if DEBUG
356
357
358
359
360
361
362
363
            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');
364
#endif
365
366
367
368
            for (unsigned q2 = 0; q2 < d.cand_size; q2++)
              solver.add(d.transid(q1, l, q2));
            solver.add(0);
          }
369

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

377
      for (unsigned q1 = 0; q1 < d.cand_size; ++q1)
378
        {
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
          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;
396

397
398
399
400
401
402
403
404
405
406
407
408
409
410
                    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});
                      }
                  }
              }
          }
411
        }
412

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

      // 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
418
      for (unsigned q1p = 0; q1p < d.ref_size; ++q1p)
419
420
421
422
423
424
        {
          if (!sm.reachable_state(q1p))
            continue;
          unsigned q1p_scc = sm.scc_of(q1p);
          if (sm.is_trivial(q1p_scc))
            continue;
425
          for (unsigned q2p = 0; q2p < d.ref_size; ++q2p)
426
427
428
429
430
431
432
433
434
435
            {
              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)
                  {
436
                    std::string f_p = d.fmt_p(q1, q1p, q2, q2p);
437
                    cnf_comment("(4&5) matching paths from reference based on",
438
                                f_p, '\n');
439

440
                    int pid1 = d.pathid_ref(q1, q1p, q2, q2p);
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
                    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;
459
460
461
#if DEBUG
                                    std::string f_t = d.fmt_t(q2, s, q1);
                                    cnf_comment(f_p, "R ∧", f_t, "δ → ¬", f_t,
462
                                                "F\n");
463
464
465
466
467
#endif
                                    solver.add({-pid1,
                                                -d.transid(q2, s, q1),
                                                -d.transacc(q2, s, q1),
                                                0});
468
469
470
471
                                  }
                              }
                            else // (5) not looping
                              {
472
                                int pid2 = d.pathid_ref(q1, q1p, q3, dp);
473
474
475
476
477
478
479
480
481
                                if (pid1 == pid2)
                                  continue;

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

482
483
484
485
486
487
488
                                    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});
489
490
491
492
493
494
495
                                  }
                              }
                          }
                      }
                  }
            }
        }
496
497
498
      // 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.
499
      for (unsigned q1p = 0; q1p < d.ref_size; ++q1p)
500
501
502
503
504
505
        {
          if (!sm.reachable_state(q1p))
            continue;
          unsigned q1p_scc = sm.scc_of(q1p);
          if (sm.is_trivial(q1p_scc))
            continue;
506
          for (unsigned q2p = 0; q2p < d.ref_size; ++q2p)
507
508
509
510
511
512
513
514
515
516
            {
              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)
                  {
517
                    std::string f_p = d.fmt_p(q1, q1p, q2, q2p);
518
                    cnf_comment("(6&7) matching paths from candidate based on",
519
                                f_p, '\n');
520
521
522

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

                    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;
546
547
548
549
550
551
552
553
554
#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});
555
556
557
558
                                  }
                              }
                            else // (7) no loop
                              {
559
                                int pid2 = d.pathid_cand(q1, q1p, q3, dp);
560
561
562
563
564
565
566
567
                                if (pid1 == pid2)
                                  continue;

                                bdd all = tr.cond;
                                while (all != bddfalse)
                                  {
                                    bdd s = bdd_satoneset(all, ap, bddfalse);
                                    all -= s;
568
569
570
571
572
573
574
575
576
577
578
#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});
579
580
581
582
583
584
585
                                  }
                              }
                          }
                      }
                  }
            }
        }
586
      return solver.stats();
587
588
    }

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

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

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

612
613
614
615
616
617
618
      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])
619
            {
620
              // Ignore unuseful transitions because of reduced cand_size.
621
              if (i >= cand_size)
622
623
                continue;

624
              // Skip (s,l,d2) if we have already seen some (s,l,d1).
625
626
627
628
629
630
631
632
633
634
635
636
637
              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);
              }
638
            }
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
          }
#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';
664
          else
665
666
667
668
669
670
671
            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)
672
            {
673
674
675
676
677
678
              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';
679
            }
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
      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';
704
        else
705
706
          dout << -it->first << "\t¬" << it->second << '\n';
      }
707
#endif
708
      a->merge_edges();
709
710
711
712
      return a;
    }
  }

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

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

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

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

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

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

748
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
  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);
  }

901
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
  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);
  }

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

992
    twa_graph_ptr prev = nullptr;
993
    for (;;)
994
      {
995
996
997
998
999
1000
1001
        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;
1002
      }
1003
    SPOT_UNREACHABLE();
1004
  }
1005

1006
1007
  twa_graph_ptr
  dtba_sat_minimize_dichotomy(const const_twa_graph_ptr& a,
1008
                              bool state_based, int max_states)
1009
  {
1010
1011
    if (max_states < 0)
      max_states = stats_reachable(a).states - 1;
1012
1013
    int min_states = 1;

1014
    twa_graph_ptr prev = nullptr;
1015
    while (min_states <= max_states)
1016
      {
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
        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;
          }
1028
      }
1029
    return prev;
1030
1031
  }
}