expression.cpp

Go to the documentation of this file.

#include "expression.h"

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

#include <algorithm>

#include <array>
using std::array;

#include <bitset>
using std::bitset;

#include "gnfa.h"
#include "nfa.h"
#include "dfa.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.insert(make_pair(symbol, exptr(new expression(symbol)))).first->second;
}

expression::exptr const& expression::spawnSymbol(string const& utf8Symbol) {
  char32_t u32Symbol(converter.from_bytes(utf8Symbol)[0]);
  return expression::symbols.insert(make_pair(u32Symbol, exptr(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;
      }
      dfa empty;
      if (empty == nfa::subtract(*l, *r).build()) {
        return r;
      }
      if (empty == nfa::subtract(*r, *l).build()) {
        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);
}

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

bool expression::operator!=(expression const& other) const {
  return *this != static_cast<nfa const&>(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::extractUtf8Symbol() const {
  char32_t symbol(extractSymbol());
  if (symbol == U'\0') {
    return string();
  } else {
    return converter.to_bytes(extractSymbol());
  }
}

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& re, literals lits, bool optimized, bool aggressive) {
  char32_t l = L;
  char32_t r = R;
  char32_t k = K;
  char32_t a = A;
  char32_t e = E;
  char32_t n = N;
  L = lits.L;
  R = lits.R;
  K = lits.S;
  A = lits.P;
  E = lits.EPSILON;
  N = lits.EMPTY;
  parser stringParser(re);
  exptr result;
  try {
    result = stringParser(optimized, aggressive);
    L = l;
    R = r;
    K = k;
    A = a;
    E = e;
    N = n;
  } catch (std::bad_function_call ex) {
    L = l;
    R = r;
    K = k;
    A = a;
    E = e;
    N = n;
    throw std::invalid_argument("Malformed regular expression.");
  }
  return result;
}

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


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

expression::exptr expression::spawnFromString(string const& utf8Re, bool optimized, bool aggressive) {
  return spawnFromString(converter.from_bytes(utf8Re), 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) {}
}