expression.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 "expression.h"

using std::make_pair;
using std::make_unique;
using std::pair;
using std::string;
using std::u32string;
using std::unique_ptr;
using std::vector;

#include <algorithm>

#include <array>
using std::array;

#include <bitset>
using std::bitset;

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

namespace reg {
expression::exptr expression::empty = expression::exptr(new expression);
std::unordered_map<char32_t, expression::exptr> expression::symbols;

char32_t expression::L =
    U'(';  
char32_t expression::R =
    U')';  
char32_t expression::K =
    U'*';  
char32_t expression::A =
    U'+';  
char32_t expression::E =
    U'ε';  
char32_t expression::N =
    U'∅';  

void expression::reset() {
  L = U'(';
  R = U')';
  K = U'*';
  A = U'+';
  E = U'ε';
  N = U'∅';
}


expression::exptr const& expression::spawnEmptySet() {
  return expression::empty;
}


expression::exptr const& expression::spawnEmptyString() {
  return expression::spawnSymbol_(U'\0');
}


expression::exptr const& expression::spawnSymbol_(char32_t symbol) {
  return expression::symbols.emplace(symbol, new expression(symbol))
      .first->second;
}


expression::exptr const& expression::spawnSymbol(string const& symbol) {
  char32_t u32Symbol(converter.from_bytes(symbol)[0]);
  return expression::symbols.emplace(u32Symbol, new expression(u32Symbol))
      .first->second;
}


expression::exptr expression::spawnConcatenation(expression::exptr const& l,
                                                 expression::exptr const& r,
                                                 bool optimized,
                                                 bool aggressive) {
  if (optimized) {
    if (l == expression::spawnEmptyString()) {
      return r;
    }
    if (r == expression::spawnEmptyString()) {
      return l;
    }
    if (r == expression::spawnEmptySet() || l == expression::spawnEmptySet()) {
      return expression::spawnEmptySet();
    }
    if (aggressive) {
      if (*l == *expression::spawnEmptyString()) {
        return r;
      }
      if (*r == *expression::spawnEmptyString()) {
        return l;
      }
      if (*r == *expression::spawnEmptySet() ||
          *l == *expression::spawnEmptySet()) {
        return expression::spawnEmptySet();
      }
    }
  }
  return expression::exptr(new expression(l, r, operation::concatenation));
}


expression::exptr expression::spawnAlternation(expression::exptr const& l,
                                               expression::exptr const& r,
                                               bool optimized,
                                               bool aggressive) {
  if (optimized) {
    if (l == expression::spawnEmptySet()) {
      return r;
    }
    if (r == expression::spawnEmptySet()) {
      return l;
    }
    if (l == r) {
      return l;
    }
    if (aggressive) {
      if (*l == *expression::spawnEmptySet()) {
        return r;
      }
      if (*r == *expression::spawnEmptySet()) {
        return l;
      }
      if (*l == *r) {
        return l->size() > r->size() ? r : l;
      }
      static dfa empty;
      if (empty == nfa::subtract(*l, *r).buildDfa(true)) {
        return r;
      }
      if (empty == nfa::subtract(*r, *l).buildDfa(true)) {
        return l;
      }
    }
  }
  return expression::exptr(new expression(l, r, operation::alternation));
}


expression::exptr expression::spawnKleene(expression::exptr const& b,
                                          bool optimized, bool aggressive) {
  if (optimized) {
    if (b == expression::spawnEmptySet() ||
        b == expression::spawnEmptyString()) {
      return expression::spawnEmptyString();
    }
    if (aggressive) {
      if (*b == *expression::spawnEmptySet() ||
          *b == *expression::spawnEmptyString()) {
        return expression::spawnEmptyString();
      }
      if (*b == expression(b)) {
        return b;
      }
    }
  }
  return expression::exptr(new expression(b));
}


size_t expression::size() const {
  size_t s(1);
  for (exptr const& re : *this) {
    s += re->size();
  }
  return s;
}


expression::operation expression::getOperation() const { return op; }

#ifndef DOXYGEN_SHOULD_SKIP_THIS
expression::operator nfa const&() const {
  if (!acceptingNfa) {
    acceptingNfa = make_unique<nfa const>(gnfa(*this).splitAllTransitions());
  }
  return *acceptingNfa;
}
#endif  // DOXYGEN_SHOULD_SKIP_THIS


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


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


char32_t expression::extractSymbol_() const {
  auto it = std::find_if(expression::symbols.begin(), expression::symbols.end(),
                         [&](pair<char32_t, exptr> const& entry) -> bool {
                           return entry.second.get() == this;
                         });
  if (it == expression::symbols.end()) {
    throw std::logic_error(
        "This RE does not seem to be a valid symbol expression.");
  }
  return it->first;
}


string expression::extractSymbol() const {
  char32_t symbol(extractSymbol_());
  return converter.to_bytes(u32string(!!symbol, symbol));
}

u32string expression::to_u32string() const {
  switch (op) {
    case operation::alternation:
      return subExpressions[0]->to_u32string() + A +
             subExpressions[1]->to_u32string();
    case operation::concatenation: {
      u32string concat;
      if (subExpressions[0]->op >= operation::alternation) {
        concat.append(L + subExpressions[0]->to_u32string() + R);
      } else {
        concat.append(subExpressions[0]->to_u32string());
      }
      if (subExpressions[1]->op >= operation::alternation) {
        concat.append(L + subExpressions[1]->to_u32string() + R);
      } else {
        concat.append(subExpressions[1]->to_u32string());
      }
      return concat;
    }
    case operation::kleene: {
      if (subExpressions[0]->op >= operation::concatenation) {
        return (L + subExpressions[0]->to_u32string() + R) + K;
      } else {
        return subExpressions[0]->to_u32string() + K;
      }
    }
    case operation::symbol: {
      char32_t symbol = extractSymbol_();
      return u32string(1, symbol + (!symbol * E));
    }
    case operation::empty:
      return u32string(1, N);
    default:
      return u32string();
  }
}

string expression::to_string() const {
  return converter.to_bytes(to_u32string());
}

vector<expression::exptr>::const_iterator expression::begin() const {
  return subExpressions.cbegin();
}

vector<expression::exptr>::const_iterator expression::end() const {
  return subExpressions.cend();
}


struct expression::parser {
  enum struct token : unsigned char {
    A,   
    B,   
    C,   
    K,   
    E,   
    F,   
    Σ,   
    P,   
    L,   
    R,   
    S,   
    END  
  };

#define TOKEN(T) static_cast<unsigned char>(reg::expression::parser::token::T)

  typedef bitset<TOKEN(END)> tokens;

  static array<token, TOKEN(END)> const inverseUnitGraph;

  static array<array<tokens, TOKEN(END)>, TOKEN(END)> const inverseBinaryRules;


  static tokens getUClosure(tokens const& m) {
    tokens closure;
    for (unsigned char c(0); c < TOKEN(END); c++) {
      if (m[c]) {
        for (token s(static_cast<token>(c)); s != token::END;
             s = inverseUnitGraph[static_cast<unsigned char>(s)]) {
          closure.set(static_cast<unsigned char>(s));
        }
      }
    }  // Going through the tokens in m.
    return closure;
  }


  static bool canDerive(token symbol, tokens const& left, tokens const& right) {
    tokens leftClosure(getUClosure(left));
    tokens rightClosure(getUClosure(right));
    for (unsigned char li(0); li < TOKEN(END); li++) {
      if (leftClosure[li]) {
        for (unsigned char ri(0); ri < TOKEN(END); ri++) {
          if (rightClosure[ri]) {
            for (unsigned char ci(0); ci < TOKEN(END); ci++) {
              if (inverseBinaryRules[li][ri][ci]) {
                for (unsigned char successor(ci); successor != TOKEN(END);
                     successor = static_cast<unsigned char>(
                         inverseUnitGraph[successor])) {
                  if (static_cast<unsigned char>(symbol) == successor) {
                    return true;
                  }
                }
              }
            }
          }
        }
      }
    }
    return false;
  }


  static void compileTableEntry(size_t row, size_t diag,
                                vector<vector<tokens>>& table) {
    for (size_t i(0); i < diag; i++) {
      tokens first(getUClosure(table[row][i]));
      for (unsigned char fi(0); fi < first.size(); fi++) {
        if (first[fi]) {
          tokens second(getUClosure(table[row + 1 + i][diag - i - 1]));
          for (unsigned char si(0); si < second.size(); si++) {
            if (second[si]) {
              table[row][diag] |= inverseBinaryRules[fi][si];
            }
          }  // Going through the tokens in second.
        }
      }  // Going through the tokens in first.
    }
  }

  vector<char32_t> symbolMapping;  
  size_t mutable symbolMappingIndex;  
  vector<vector<tokens>>
      table;  
  bool badRegularExpression =
      false;  

  parser(u32string const& re) {
    if (re.empty()) {
      badRegularExpression = true;
      return;
    }
    symbolMappingIndex = 0;
    size_t numberOfTokens(re.length());
    symbolMapping.reserve(numberOfTokens);
    table.reserve(numberOfTokens);
    size_t row(0);
    for (char32_t symbol : re) {
      table.push_back(vector<tokens>(numberOfTokens - row, tokens()));
      if (symbol == L) {
        table[row][0].set(TOKEN(L));
      } else if (symbol == R) {
        table[row][0].set(TOKEN(R));
      } else if (symbol == A) {
        table[row][0].set(TOKEN(P));
      } else if (symbol == K) {
        table[row][0].set(TOKEN(S));
      } else {
        table[row][0].set(TOKEN(Σ));
        symbolMapping.push_back(symbol);
      }
      row++;
    }
    symbolMapping.shrink_to_fit();
    for (size_t diag(1); diag < numberOfTokens; diag++) {
      for (size_t row(0); row < numberOfTokens - diag; row++) {
        compileTableEntry(row, diag, table);
      }
    }
    if (!getUClosure(table[0][table[0].size() - 1])[TOKEN(A)]) {
      badRegularExpression = true;
    }
  }

  struct tree {
    parser const* p;  
    token symbol;     
    pair<unique_ptr<tree>, unique_ptr<tree>> children;


    pair<unique_ptr<tree>, unique_ptr<tree>> findNextPair(token symbol,
                                                          size_t row,
                                                          size_t diag,
                                                          parser const* p) {
      for (size_t i = 0; i < diag; i++) {
        size_t leftDiag = diag - i - 1;
        size_t rightDiag = i;
        size_t rightRow = diag + row - rightDiag;
        if (canDerive(symbol, p->table[row][leftDiag],
                      p->table[rightRow][rightDiag])) {
          return make_pair(make_unique<tree>(row, leftDiag, p),
                           make_unique<tree>(rightRow, rightDiag, p));
        }
      }
      return make_pair(unique_ptr<tree>(), unique_ptr<tree>());
    }


    tree(size_t row, size_t diag, parser const* p)
        : p(p),
          symbol([&]() -> token {
            for (unsigned char i(TOKEN(END)); i > 0; i--) {
              if (p->table[row][diag][i - 1]) {
                return static_cast<token>(i - 1);
              }
            }
            return token::END;
          }()),
          children(findNextPair(symbol, row, diag, p)) {}

    exptr operator()(bool optimized, bool aggressive) {
      switch (symbol) {
        case token::A:
          return spawnAlternation((*children.first)(optimized, aggressive),
                                  (*children.second)(optimized, aggressive),
                                  optimized, aggressive);
        case token::B:
          return (*children.second)(optimized, aggressive);
        case token::C:
          return spawnConcatenation((*children.first)(optimized, aggressive),
                                    (*children.second)(optimized, aggressive),
                                    optimized, aggressive);
        case token::K:
          return spawnKleene((*children.first)(optimized, aggressive),
                             optimized, aggressive);
        case token::E:
          return (*children.second)(optimized, aggressive);
        case token::F:
          return (*children.first)(optimized, aggressive);
        case token::Σ: {
          char32_t symbol = p->symbolMapping[p->symbolMappingIndex++];
          if (p->symbolMappingIndex >= p->symbolMapping.size()) {
            p->symbolMappingIndex = 0;
          }
          if (symbol == E) {
            return spawnEmptyString();
          } else if (symbol == N) {
            return spawnEmptySet();
          } else {
            return spawnSymbol_(symbol);
          }
        }
        default:
          return exptr();
      }
    }
  };


  exptr operator()(bool optimized, bool aggressive) {
    if (badRegularExpression) {
      throw std::bad_function_call();
    }
    return tree(0, table.size() - 1, this)(optimized, aggressive);
  }
};

auto const expression::parser::inverseUnitGraph =
    []() -> array<expression::parser::token, TOKEN(END)> {
  array<token, TOKEN(END)> graph;
  graph.fill(token::END);
  graph[TOKEN(Σ)] = token::E;
  graph[TOKEN(E)] = token::K;
  graph[TOKEN(K)] = token::C;
  graph[TOKEN(C)] = token::A;
  return graph;
}();

auto const expression::parser::inverseBinaryRules =
    []() -> array<array<expression::parser::tokens, TOKEN(END)>, TOKEN(END)> {
  array<tokens, TOKEN(END)> noPredecessor;
  noPredecessor.fill(tokens());
  array<array<tokens, TOKEN(END)>, TOKEN(END)> rules;
  rules.fill(noPredecessor);
  rules[TOKEN(A)][TOKEN(B)].set(TOKEN(A));
  rules[TOKEN(P)][TOKEN(C)].set(TOKEN(B));
  rules[TOKEN(C)][TOKEN(K)].set(TOKEN(C));
  rules[TOKEN(E)][TOKEN(S)].set(TOKEN(K));
  rules[TOKEN(L)][TOKEN(F)].set(TOKEN(E));
  rules[TOKEN(A)][TOKEN(R)].set(TOKEN(F));
  return rules;
}();
#undef TOKEN


expression::exptr expression::spawnFromString_(std::u32string const& u32re,
                                               bool optimized,
                                               bool aggressive) {
  parser stringParser(u32re);
  try {
    return stringParser(optimized, aggressive);
  } catch (std::bad_function_call e) {
    throw std::invalid_argument("Malformed regular expression.");
  }
}


expression::exptr expression::spawnFromString(string const& re, bool optimized,
                                              bool aggressive) {
  return spawnFromString_(converter.from_bytes(re), optimized, aggressive);
}

expression::expression() : op(operation::empty) {}
expression::expression(char32_t symbol) : op(operation::symbol) {}
expression::expression(exptr const& l, exptr const& r, operation op)
    : subExpressions({l, r}), op(op) {}
expression::expression(exptr const& b)
    : subExpressions({b}), op(operation::kleene) {}
}  // namespace reg