gnfa.cpp

Go to the documentation of this file.

// Copyright 2017, 2018 Tom Kranz
//
// This file is part of reglibcpp.
//
// reglibcpp 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.
//
// reglibcpp 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 reglibcpp.  If not, see <https://www.gnu.org/licenses/>.

#include "gnfa.h"
using std::pair;
using std::string;
using std::vector;

#include <unordered_map>
using std::unordered_map;

#include <functional>
using std::reference_wrapper;

#include <forward_list>
using std::forward_list;

#include "dfa.h"
#include "fabuilder.h"
#include "nfa.h"

namespace reg {

struct gnfa::impl {
  std::shared_ptr<nfa const> mutable equivalent;
  unordered_map<string, unordered_map<string, expression::exptr>> transitions;
  string initial;
  string accepting;

  impl() : initial("p0"), accepting("pF") {
    transitions[initial];
    transitions[accepting];
  }

  impl(unordered_map<string, unordered_map<string, expression::exptr>>&
           transitionMap,
       string const& initialState,
       forward_list<reference_wrapper<string const>>& acceptingStates,
       nfa const* eq)
      : equivalent(eq), transitions(move(transitionMap)) {
    initial = generateState('p', '0');
    auto const& epsilon = expression::spawnEmptyString();
    transitions[initial][initialState] = epsilon;
    accepting = generateState('p', 'F');
    for (string const& a : acceptingStates) {
      transitions[a][accepting] = epsilon;
    }
  }


  expression::exptr const& getTransition(string const& qLabel,
                                         string const& pLabel) const {
    auto const& from = transitions.at(qLabel);
    auto reIt = from.find(pLabel);
    if (reIt == from.end() || !reIt->second) {
      return expression::spawnEmptySet();
    }
    return reIt->second;
  }


  void addTransition(string const& qLabel, string const& pLabel,
                     expression::exptr re, bool optimized = true,
                     bool aggressive = false) {
    transitions[qLabel][pLabel] = expression::spawnAlternation(
        getTransition(qLabel, pLabel), re, optimized, aggressive);
  }


  string const& generateState(char prefix = 'q', char suffix = '\0') {
    string state;
    if (suffix == '\0') {
      state = string(!!prefix, prefix).append(std::to_string(0));
      for (size_t q(1); transitions.count(state) != 0; q++) {
        state = string(!!prefix, prefix).append(std::to_string(q));
      }
    } else {
      for (state = string(!!prefix, prefix).append(1, suffix);
           transitions.count(state) != 0; state.append(!!prefix, suffix)) {
      }
    }
    return transitions
        .emplace(move(state), unordered_map<string, expression::exptr>())
        .first->first;
  }
};


gnfa::gnfa(dfa const& d) {
  unordered_map<string, unordered_map<string, expression::exptr>> transitions(
      d.getStates().size() + 2);
  forward_list<reference_wrapper<string const>> acceptingStates;
  for (size_t qi(0); qi < d.getStates().size(); qi++) {
    auto const& qLabel = d.getStates()[qi];
    auto& entry = transitions[qLabel];
    if (d.isAccepting(qi)) {
      acceptingStates.push_front(qLabel);
    }
    for (size_t si(0); si < d.getAlphabet_().size(); si++) {
      char32_t symbol = d.getAlphabet_()[si];
      size_t pi = d.delta(qi, si);
      auto& dest = entry[d.getStates()[pi]];
      if (!dest) {
        dest = expression::spawnSymbol_(symbol);
      } else {
        dest = expression::spawnAlternation(dest,
                                            expression::spawnSymbol_(symbol));
      }
    }
  }
  pim = std::make_unique<impl>(transitions, d.getInitialState(),
                               acceptingStates, new nfa(d));
}


gnfa::gnfa(nfa const& n) {
  unordered_map<string, unordered_map<string, expression::exptr>> transitions(
      n.getStates().size() + 2);
  forward_list<reference_wrapper<string const>> acceptingStates;
  for (size_t qi(0); qi < n.getStates().size(); qi++) {
    auto const& qLabel = n.getStates()[qi];
    auto& entry = transitions[qLabel];
    if (n.isAccepting(qi)) {
      acceptingStates.push_front(qLabel);
    }
    for (char32_t symbol : n.getAlphabet_()) {
      auto& pSet = n.delta_(qi, symbol);
      for (size_t pi(0); pi < pSet.size(); pi++) {
        if (pSet[pi]) {
          auto& dest = entry[n.getStates()[pi]];
          if (!dest) {
            dest = expression::spawnSymbol_(symbol);
          } else {
            dest = expression::spawnAlternation(
                dest, expression::spawnSymbol_(symbol));
          }
        }
      }
    }
  }
  pim = std::make_unique<impl>(transitions, n.getInitialState(),
                               acceptingStates, new nfa(n));
}


gnfa::gnfa(expression::exptr r) : pim(new impl) {
  pim->transitions[pim->initial][pim->accepting] = r;
}

gnfa::gnfa(expression const& r) : pim(new impl) {
  switch (r.getOperation()) {
    case expression::operation::alternation:
      pim->transitions[pim->initial][pim->accepting] =
          expression::spawnAlternation(*r.begin(), *(r.begin() + 1));
      break;
    case expression::operation::concatenation:
      pim->transitions[pim->initial][pim->accepting] =
          expression::spawnConcatenation(*r.begin(), *(r.begin() + 1));
      break;
    case expression::operation::kleene:
      pim->transitions[pim->initial][pim->accepting] =
          expression::spawnKleene(*r.begin());
      break;
    case expression::operation::symbol:
      pim->transitions[pim->initial][pim->accepting] =
          expression::spawnSymbol_(r.extractSymbol_());
      break;
    case expression::operation::empty:
      pim->transitions[pim->initial][pim->accepting] =
          expression::spawnEmptySet();
      break;
  }
}

string const& gnfa::getInitialState() const { return pim->initial; }

string const& gnfa::getAcceptingState() const { return pim->accepting; }

gnfa::state_vector gnfa::getActiveStates() const {
  state_vector active;
  for (auto const& entry : pim->transitions) {
    if (entry.first != pim->initial && entry.first != pim->accepting) {
      active.push_back(std::cref(entry.first));
    }
  }
  return active;
}

expression::exptr gnfa::getTransition(string const& qLabel,
                                      string const& pLabel) const {
  return pim->getTransition(qLabel, pLabel);
}


gnfa::state_pair_vector gnfa::getSplittableTransitions() const {
  state_pair_vector splittable;
  splittable.reserve(pim->transitions.size() * pim->transitions.size());
  for (auto const& from : pim->transitions) {
    for (auto const& to : from.second) {
      if (to.second &&
          to.second->getOperation() > expression::operation::symbol) {
        splittable.emplace_back(std::ref(from.first), std::ref(to.first));
      }
    }
  }
  splittable.shrink_to_fit();
  return splittable;
}


gnfa::state_vector gnfa::splitTransition(string const& q, string const& p) {
  state_vector newStates;
  auto const& re = pim->getTransition(q, p);
  switch (re->getOperation()) {
    case expression::operation::alternation: {
      auto sub1 = *(re->begin());
      auto sub2 = *(re->begin() + 1);
      pim->transitions[q][p] = expression::spawnEmptySet();
      newStates.reserve(4);
      for (size_t i(0); i < 4; i++) {
        newStates.push_back(pim->generateState());
      }
      auto const& epsilon = expression::spawnEmptyString();
      pim->transitions[q][newStates[0]] = epsilon;
      pim->transitions[newStates[0]][newStates[1]] = sub1;
      pim->transitions[newStates[1]][p] = epsilon;
      pim->transitions[q][newStates[2]] = epsilon;
      pim->transitions[newStates[2]][newStates[3]] = sub2;
      pim->transitions[newStates[3]][p] = epsilon;
      break;
    }
    case expression::operation::concatenation: {
      auto sub1 = *(re->begin());
      auto sub2 = *(re->begin() + 1);
      pim->transitions[q][p] = expression::spawnEmptySet();
      newStates.reserve(2);
      for (size_t i(0); i < 2; i++) {
        newStates.push_back(pim->generateState());
      }
      pim->transitions[q][newStates[0]] = sub1;
      pim->transitions[newStates[0]][newStates[1]] =
          expression::spawnEmptyString();
      pim->transitions[newStates[1]][p] = sub2;
      break;
    }
    case expression::operation::kleene: {
      auto sub = *(re->begin());
      auto const& epsilon = expression::spawnEmptyString();
      pim->transitions[q][p] = epsilon;
      newStates.reserve(2);
      for (size_t i(0); i < 2; i++) {
        newStates.push_back(pim->generateState());
      }
      pim->transitions[q][newStates[0]] = epsilon;
      pim->transitions[newStates[1]][p] = epsilon;
      pim->transitions[newStates[1]][newStates[0]] = epsilon;
      pim->transitions[newStates[0]][newStates[1]] = sub;
      break;
    }
    case expression::operation::symbol:
    case expression::operation::empty:;
  }
  return newStates;
}


nfa gnfa::splitAllTransitions() {
  for (auto splittable = getSplittableTransitions(); !splittable.empty();
       splittable = getSplittableTransitions()) {
    for (auto const& nodes : splittable) {
      splitTransition(nodes.first, nodes.second);
    }
  }
  fabuilder b;
  auto const& empty = expression::spawnEmptySet();
  for (auto const& from : pim->transitions) {
    for (auto const& to : from.second) {
      if (to.second != empty) {
        b.addTransition_(from.first, to.first, to.second->extractSymbol_());
      }
    }
  }
  b.makeInitial(pim->initial);
  b.setAccepting(pim->accepting, true);
  return b.buildNfa();
}

void gnfa::bypassTransition(string const& qLabel, string const& pLabel) {
  auto const& re = pim->getTransition(qLabel, pLabel);
  if (re == expression::spawnEmptySet()) {
    return;
  }
  auto const& selfRe = pim->getTransition(qLabel, qLabel);
  for (auto const& from : pim->transitions) {
    if (from.first != qLabel) {
      auto to = from.second.find(qLabel);
      if (to != from.second.end() && to->second) {
        pim->addTransition(
            from.first, pLabel,
            expression::spawnConcatenation(
                to->second, expression::spawnConcatenation(
                                expression::spawnKleene(selfRe), re)));
      }
    }
  }
  pim->transitions[qLabel].erase(pLabel);
}

void gnfa::ripState(string const& qLabel) {
  forward_list<reference_wrapper<string const>> right;
  for (auto const& to : pim->transitions[qLabel]) {
    right.push_front(to.first);
  }
  for (auto const& to : right) {
    if (to.get() != qLabel) {
      bypassTransition(qLabel, to);
    }
  }
  for (auto& from : pim->transitions) {
    from.second.erase(qLabel);
  }
  pim->transitions.erase(qLabel);
}


expression::exptr gnfa::ripAllStates() {
  for (auto const& rippable : getActiveStates()) {
    ripState(rippable);
  }
  return getTransition(getInitialState(), getAcceptingState());
}

gnfa::gnfa(gnfa const& n) : pim(new impl(*(n.pim))) {}


gnfa::gnfa(gnfa&& n) : pim(new impl) { pim.swap(n.pim); }

#ifndef DOXYGEN_SHOULD_SKIP_THIS
gnfa::operator nfa const&() const {
  if (!pim->equivalent) {
    pim->equivalent =
        std::make_shared<nfa const>(gnfa(*this).splitAllTransitions());
  }
  return *pim->equivalent;
}
#endif  // DOXYGEN_SHOULD_SKIP_THIS


bool gnfa::operator==(nfa const& other) const {
  return other.operator==(*this);
}


bool gnfa::operator!=(nfa const& other) const { return !operator==(other); }

gnfa& gnfa::operator=(gnfa const& n) {
  if (this != &n) {
    pim.reset(new impl(*(n.pim)));
  }
  return *this;
}


gnfa& gnfa::operator=(gnfa&& n) {
  if (this != &n) {
    pim.reset(new impl);
    pim.swap(n.pim);
  }
  return *this;
}

gnfa::~gnfa() = default;
}  // namespace reg