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;


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;
      }
    }
  }
  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(op != operation::empty);
  for (exptr const& re : subExpressions) {
    s += re->size();
  }
  return s;
}


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


bool expression::operator==(expression const& r) const {
  if (!acceptingDfa) {
    acceptingDfa = make_unique<dfa const>(dfa::builder(gnfa(*this).splitAllTransitions()).minimize());
  }
  if (!r.acceptingDfa) {
    r.acceptingDfa = make_unique<dfa const>(dfa::builder(gnfa(r).splitAllTransitions()).minimize());
  }
  return *acceptingDfa == *r.acceptingDfa;
}


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


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().append(U"+").append(subExpressions[1]->to_u32string());
    case operation::concatenation : {
      u32string concat;
      if (subExpressions[0]->op >= operation::alternation) {
        concat.append(1, '(');
        concat.append(subExpressions[0]->to_u32string());
        concat.append(1, ')');
      } else {
        concat.append(subExpressions[0]->to_u32string());
      }
      if (subExpressions[1]->op >= operation::alternation) {
        concat.append(1, '(');
        concat.append(subExpressions[1]->to_u32string());
        concat.append(1, ')');
      } else {
        concat.append(subExpressions[1]->to_u32string());
      }
      return concat;
    }
    case operation::kleene : {
      if (subExpressions[0]->op >= operation::concatenation) {
        return u32string(1, U'(').append(subExpressions[0]->to_u32string()).append(U")*");
      } else {
        return subExpressions[0]->to_u32string().append(1, '*');
      }
    }
    case operation::symbol : {
      char32_t symbol = extractSymbol();
      return symbol == U'\0' ? u32string(U"ε") : u32string(1, symbol);
    }
    case operation::empty : return u32string(U"∅");
    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 token : unsigned char {
      A, 
      B, 
      C, 
      K, 
      E, 
      F, 
      Σ, 
      P, 
      L, 
      R, 
      S, 
      END 
    };

  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[s]) {
        closure.set(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 = inverseUnitGraph[successor]) {
            if (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.
    }
  }

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

  parser(u32string const& re, literals const& lits) {
    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 == lits.L) { table[row][0].set(token::L); }
      else if (symbol == lits.R) { table[row][0].set(token::R); }
      else if (symbol == lits.P) { table[row][0].set(token::P); }
      else if (symbol == lits.S) { 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 == p->lits.EPSILON) { return spawnEmptyString(); }
          else if (symbol == p->lits.EMPTY) { 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,expression::parser::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,expression::parser::token::END>,expression::parser::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;
}();


expression::exptr expression::spawnFromString(std::u32string const& re, literals lits, bool optimized, bool aggressive) {
  parser stringParser(re, lits);
  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, literals lits, bool optimized, bool aggressive) {
  return spawnFromString(converter.from_bytes(utf8Re), lits, 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) {}
}