cleanacc.cc 10.9 KB
Newer Older
1
// -*- coding: utf-8 -*-
2
// Copyright (C) 2015, 2017, 2018 Laboratoire de Recherche et Développement
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
// de l'Epita.
//
// 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/>.

20
#include <spot/twaalgos/cleanacc.hh>
21 22 23

namespace spot
{
24
  twa_graph_ptr cleanup_acceptance_here(twa_graph_ptr aut, bool strip)
25 26 27
  {
    auto& acc = aut->acc();
    if (acc.num_sets() == 0)
28
      return aut;
29

30
    auto c = aut->get_acceptance();
31
    acc_cond::mark_t used_in_cond = c.used_sets();
32 33

    acc_cond::mark_t used_in_aut = 0U;
34
    acc_cond::mark_t used_on_all_edges = used_in_cond;
35
    for (auto& t: aut->edges())
36 37 38 39
      {
        used_in_aut |= t.acc;
        used_on_all_edges &= t.acc;
      }
40 41

    auto useful = used_in_aut & used_in_cond;
42
    auto useless = strip ? acc.comp(useful) : (used_in_cond - used_in_aut);
43

44
    useless |= used_on_all_edges;
45 46

    if (!useless)
47
      return aut;
48 49

    // Remove useless marks from the automaton
50 51 52 53 54 55 56 57
    if (strip)
      for (auto& t: aut->edges())
        t.acc = t.acc.strip(useless);

    // if x appears on all edges, then
    //   Fin(x) = false and Inf(x) = true
    if (used_on_all_edges)
      c = c.remove(used_on_all_edges, false);
58 59

    // Remove useless marks from the acceptance condition
60 61 62 63
    if (strip)
      aut->set_acceptance(useful.count(), c.strip(useless, true));
    else
      aut->set_acceptance(aut->num_sets(), c.remove(useless, true));
64 65

    // This may in turn cause even more set to be unused, because of
66 67
    // some simplifications in the acceptance condition, so do it again.
    return cleanup_acceptance_here(aut, strip);
68 69
  }

70
  twa_graph_ptr cleanup_acceptance(const_twa_graph_ptr aut)
71
  {
72
    return cleanup_acceptance_here(make_twa_graph(aut,
73
                                                     twa::prop_set::all()));
74 75
  }

76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176
  namespace
  {
    twa_graph_ptr merge_identical_marks_here(twa_graph_ptr aut)
    {
      // always cleanup before proceeding, otherwise if some mark appears in the
      // acceptance condition, but not in the automaton the result is undefined.
      cleanup_acceptance_here(aut, false);

      auto& acc = aut->acc();
      auto& c = acc.get_acceptance();
      acc_cond::mark_t used_in_cond = c.used_sets();

      if (!used_in_cond)
        return aut;

      unsigned num_sets = acc.num_sets();
      std::vector<acc_cond::mark_t> always_together(num_sets);

      for (unsigned i = 0; i < num_sets; ++i)
        if (used_in_cond.has(i))
          always_together[i] = used_in_cond;
        else
          always_together[i] = acc_cond::mark_t({i});

      acc_cond::mark_t previous_a = 0U;
      for (auto& t: aut->edges())
        {
          acc_cond::mark_t a = t.acc & used_in_cond;
          if (a == previous_a)
            continue;
          previous_a = a;
          for (unsigned m: a.sets())
            {
              acc_cond::mark_t at = always_together[m];
              acc_cond::mark_t newm = at & a;

              for (unsigned rem: (at - newm).sets())
                always_together[rem] -= newm;

              always_together[m] = newm;
            }
        }

      acc_cond::mark_t to_remove = 0U;
      for (unsigned i = 0; i < num_sets; ++i)
        {
          auto oldm = always_together[i];
          if (oldm == acc_cond::mark_t({i}))
            continue;

          acc_cond::mark_t newm = oldm.lowest();
          to_remove |= oldm - newm;
          always_together[i] = newm;
        }
      for (auto& t: aut->edges())
        t.acc -= to_remove;

      // Replace the marks in the acceptance condition
      auto pos = &c.back();
      auto end = &c.front();
      while (pos > end)
        {
          switch (pos->sub.op)
            {
            case acc_cond::acc_op::And:
            case acc_cond::acc_op::Or:
              --pos;
              break;
            case acc_cond::acc_op::Fin:
            case acc_cond::acc_op::Inf:
            case acc_cond::acc_op::FinNeg:
            case acc_cond::acc_op::InfNeg:
              acc_cond::mark_t replace = pos[-1].mark & to_remove;
              pos[-1].mark -= replace;
              for (unsigned m: replace.sets())
                pos[-1].mark |= always_together[m];
              pos -= 2;
              break;
            }
        }
      return aut;
    }

    // Eventually remove complementary marks from the acceptance condition.
    acc_cond::acc_code remove_compl_rec(const acc_cond::acc_word* pos,
                                        const std::vector<acc_cond::mark_t>&
                                                          complement)
    {
      auto start = pos - pos->sub.size;
      switch (pos->sub.op)
        {
          case acc_cond::acc_op::And:
            {
              --pos;
              auto res = acc_cond::acc_code::t();
              acc_cond::mark_t seen_fin = 0U;
              auto inf = acc_cond::acc_code::inf(0U);
              do
                {
                  auto tmp = remove_compl_rec(pos, complement);

177
                  if (!tmp.empty())
178
                    {
179 180 181 182 183 184 185 186 187 188
                      if (tmp.back().sub.op == acc_cond::acc_op::Fin
                          && tmp.front().mark.count() == 1)
                        seen_fin |= tmp.front().mark;

                      if (tmp.back().sub.op == acc_cond::acc_op::Inf)
                        {
                          inf &= std::move(tmp);
                          pos -= pos->sub.size + 1;
                          continue;
                        }
189 190 191 192 193 194 195
                    }
                  tmp &= std::move(res);
                  std::swap(tmp, res);
                  pos -= pos->sub.size + 1;
                }
              while (pos > start);

196 197 198
              // Fin(i) & Inf(i) = f;
              if (inf.front().mark & seen_fin)
                return acc_cond::acc_code::f();
199
              for (auto m: seen_fin.sets())
200 201 202 203 204 205 206 207
                {
                  acc_cond::mark_t cm = complement[m];
                  // Fin(i) & Fin(!i) = f;
                  if (cm & seen_fin)
                    return acc_cond::acc_code::f();
                  // Inf({!i}) & Fin({i}) = Fin({i})
                  inf.front().mark -= complement[m];
                }
208

209
              return inf & res;
210 211 212 213 214 215 216 217 218 219
            }
          case acc_cond::acc_op::Or:
            {
              --pos;
              auto res = acc_cond::acc_code::f();
              acc_cond::mark_t seen_inf = 0U;
              auto fin = acc_cond::acc_code::f();
              do
                {
                  auto tmp = remove_compl_rec(pos, complement);
220

221
                  if (!tmp.empty())
222
                    {
223 224 225 226 227 228 229 230 231 232
                      if (tmp.back().sub.op == acc_cond::acc_op::Inf
                          && tmp.front().mark.count() == 1)
                        seen_inf |= tmp.front().mark;

                      if (tmp.back().sub.op == acc_cond::acc_op::Fin)
                        {
                          fin |= std::move(tmp);
                          pos -= pos->sub.size + 1;
                          continue;
                        }
233 234 235 236 237 238 239
                    }
                  tmp |= std::move(res);
                  std::swap(tmp, res);
                  pos -= pos->sub.size + 1;
                }
              while (pos > start);

240 241 242
              // Fin(i) | Inf(i) = t;
              if (fin.front().mark & seen_inf)
                return acc_cond::acc_code::t();
243
              for (auto m: seen_inf.sets())
244 245 246 247 248 249 250 251
                {
                  acc_cond::mark_t cm = complement[m];
                  // Inf({i}) | Inf({!i}) = t;
                  if (cm & seen_inf)
                    return acc_cond::acc_code::t();
                  // Fin({!i}) | Inf({i}) = Inf({i})
                  fin.front().mark -= complement[m];
                }
252
              return res | fin;
253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
            }
          case acc_cond::acc_op::Fin:
            return acc_cond::acc_code::fin(pos[-1].mark);
          case acc_cond::acc_op::Inf:
            return acc_cond::acc_code::inf(pos[-1].mark);
          case acc_cond::acc_op::FinNeg:
          case acc_cond::acc_op::InfNeg:
            SPOT_UNREACHABLE();
        };
        SPOT_UNREACHABLE();
        return {};
    }

    // Always cleanup_acceptance_here with stripping after calling this function
    // As complementary marks might be simplified in the acceptance condition.
    twa_graph_ptr simplify_complementary_marks_here(twa_graph_ptr aut)
    {
      auto& acc = aut->acc();
      auto c = acc.get_acceptance();
      acc_cond::mark_t used_in_cond = c.used_sets();
      if (!used_in_cond)
        return aut;

276
      // complement[i] holds sets that appear when set #i does not.
277 278 279 280 281 282 283
      unsigned num_sets = acc.num_sets();
      std::vector<acc_cond::mark_t> complement(num_sets);

      for (unsigned i = 0; i < num_sets; ++i)
        if (used_in_cond.has(i))
          complement[i] = used_in_cond - acc_cond::mark_t({i});

284 285 286 287 288 289 290 291 292 293 294 295
      // Let's visit all edges to update complement[i].  To skip some
      // duplicated work, prev_acc remember the "acc" sets of the
      // previous edge, so we can skip consecutive edges with
      // identical "acc" sets.  Note that there is no value of
      // prev_acc that would allow us to fail the comparison on the
      // first edge (this was issue #315), so we have to deal with
      // that first edge specifically.
      acc_cond::mark_t prev_acc = 0U;
      const auto& edges = aut->edges();
      auto b = edges.begin();
      auto e = edges.end();
      auto update = [&](acc_cond::mark_t tacc)
296
        {
297
          prev_acc = tacc;
298 299
          for (unsigned m: used_in_cond.sets())
            {
300 301
              if (tacc.has(m))
                complement[m] -= tacc;
302
              else
303 304 305 306 307 308 309 310 311 312 313 314
                complement[m] &= tacc;
            }
        };
      if (b != e)
        {
          update(b->acc);
          ++b;
          while (b != e)
            {
              if (b->acc != prev_acc)
                update(b->acc);
              ++b;
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
            }
        }
      aut->set_acceptance(num_sets,
                          remove_compl_rec(&acc.get_acceptance().back(),
                                           complement));
      return aut;
    }
  }

  twa_graph_ptr simplify_acceptance_here(twa_graph_ptr aut)
  {
    cleanup_acceptance_here(aut, false);
    merge_identical_marks_here(aut);
    simplify_complementary_marks_here(aut);
    cleanup_acceptance_here(aut, true);

    return aut;
  }

  twa_graph_ptr simplify_acceptance(const_twa_graph_ptr aut)
  {
    return simplify_acceptance_here(make_twa_graph(aut, twa::prop_set::all()));
  }
338
}