default_plural_forms_expressions.hpp

Go to the documentation of this file.

//  (C) Copyright 2015 - 2017 Christopher Beck
 
//  Distributed under the Boost Software License, Version 1.0. (See accompanying
//  file LICENSE or copy at http://www.boost.org/LICENSE_1_0.txt)
 
#ifndef SPIRIT_PO_DEFAULT_PLURAL_FORMS_EXPRESSIONS_HPP_INCLUDED
#define SPIRIT_PO_DEFAULT_PLURAL_FORMS_EXPRESSIONS_HPP_INCLUDED
 
/***
 * The namespace default_plural_forms contains all the details to implement
 * the subset of the C grammar used by standard GNU gettext po headers.
 *
 * Boolean expressions return uint 0 or 1.
 *
 * The 'compiler' is a spirit grammar which parses a string into an expression
 * object. The expressions are evaluated by a simple stack machine.
 */
 
#ifndef BOOST_SPIRIT_USE_PHOENIX_V3
#define BOOST_SPIRIT_USE_PHOENIX_V3
#endif
 
#include <algorithm>
#include <vector>
#include <boost/spirit/include/qi.hpp>
#include <boost/phoenix/core.hpp>
#include <boost/phoenix/operator.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/variant/variant.hpp>
#include <boost/variant/recursive_wrapper.hpp>
 
#ifdef SPIRIT_PO_DEBUG
#include <cassert>
#include <string>
#endif
 
namespace spirit_po {
 
namespace qi = boost::spirit::qi;
typedef unsigned int uint;
 
namespace default_plural_forms {
 
// X Macro for repetitive binary ops declarations
 
#define FOREACH_SPIRIT_PO_BINARY_OP(X_) \
 X_(eq_op, ==) X_(neq_op, !=) X_(ge_op, >=) X_(le_op, <=) X_(gt_op, >) X_(lt_op, <) X_(mod_op, %)
 
// && and || are treated slightly differently from other binary ops
 
#define FOREACH_SPIRIT_PO_CONJUNCTION(X_) \
 X_(and_op, &&) X_(or_op, ||)
 
/***
 * Declare / forward declare expr struct types
 */
 
struct constant { uint value; };
struct n_var { n_var() = default; explicit n_var(char) {}}; // work around a quirk in spirit
struct not_op;
struct ternary_op;
 
#define FWD_DECL_(name, op) \
struct name ; \
 
FOREACH_SPIRIT_PO_BINARY_OP(FWD_DECL_)
FOREACH_SPIRIT_PO_CONJUNCTION(FWD_DECL_)
 
#undef FWD_DECL_
 
/***
 * Define expr variant type
 */
 
#define WRAP_(name, op) boost::recursive_wrapper< name >, \
 
typedef boost::variant<constant, n_var, boost::recursive_wrapper<not_op>,
FOREACH_SPIRIT_PO_BINARY_OP(WRAP_)
FOREACH_SPIRIT_PO_CONJUNCTION(WRAP_)
boost::recursive_wrapper<ternary_op>> expr;
 
#undef WRAP_
 
/***
 * Define structs
 */
 
struct not_op { expr e1; };
struct ternary_op { expr e1, e2, e3; };
 
#define DECL_(name, op) \
struct name { expr e1, e2; }; \
 
FOREACH_SPIRIT_PO_BINARY_OP(DECL_)
FOREACH_SPIRIT_PO_CONJUNCTION(DECL_)
 
#undef DECL_
 
/***
 * Visitor that naively evaluates expressions
 */
struct evaluator : public boost::static_visitor<uint> {
  uint n_value_;
  explicit evaluator(uint n) : n_value_(n) {}
 
  uint operator()(const constant & c) const { return c.value; }
  uint operator()(n_var) const { return n_value_; }
  uint operator()(const not_op & op) const { return !boost::apply_visitor(*this, op.e1); }
 
#define EVAL_OP_(name, OPERATOR) \
  uint operator()(const name & op) const { return (boost::apply_visitor(*this, op.e1)) OPERATOR (boost::apply_visitor(*this, op.e2)); } \
 
FOREACH_SPIRIT_PO_BINARY_OP(EVAL_OP_)
FOREACH_SPIRIT_PO_CONJUNCTION(EVAL_OP_)
#undef EVAL_OP_
 
  uint operator()(const ternary_op & op) const { return boost::apply_visitor(*this, op.e1) ? boost::apply_visitor(*this, op.e2) : boost::apply_visitor(*this, op.e3); }
};
 
} // end namespace default_plural_forms
 
} // end namespace spirit_po
 
/***
 * Adapt structs for fusion / qi
 */
 
BOOST_FUSION_ADAPT_STRUCT(spirit_po::default_plural_forms::constant,
  (unsigned int, value))
BOOST_FUSION_ADAPT_STRUCT(spirit_po::default_plural_forms::not_op,
  (spirit_po::default_plural_forms::expr, e1))
BOOST_FUSION_ADAPT_STRUCT(spirit_po::default_plural_forms::ternary_op,
  (spirit_po::default_plural_forms::expr, e1)
  (spirit_po::default_plural_forms::expr, e2)
  (spirit_po::default_plural_forms::expr, e3))
 
#define ADAPT_STRUCT_(name, op) \
BOOST_FUSION_ADAPT_STRUCT(spirit_po::default_plural_forms:: name, \
  (spirit_po::default_plural_forms::expr, e1) \
  (spirit_po::default_plural_forms::expr, e2)) \
 
FOREACH_SPIRIT_PO_BINARY_OP(ADAPT_STRUCT_)
FOREACH_SPIRIT_PO_CONJUNCTION(ADAPT_STRUCT_)
 
#undef ADAPT_STRUCT_
 
namespace spirit_po {
 
namespace default_plural_forms {
 
/***
 * Pseudo-C Grammar
 *
 * Note that the grammar has been somewhat optimized by using local variables
 * and inherited attributes, in order to avoid exponential backtracking overhead.
 * This makes it a little harder to read than if we got rid of all local variables,
 * but then it is too slow to parse the expressions for certain languages.
 *
 * The main idea is that instead of parsing things like
 *
 *   BINARY_OP = LOWER_PRECENDENCE >> BINARY_OP_LITERAL >> CURRENT_PRECEDENCE
 *   CURRENT_PRECEDENCE = BINARY_OP | OTHER_OP | YET_ANOTHER_OP | LOWER_PRECEDENCE
 *
 * (which is bad because if the binary op literal is not there then we have to
 *  backtrack through an entire subexpression)
 *
 * we make BINARY_OP take the subexpression as a parameter, and in each
 * precedence level, we capture the subexpression first and store it in a local
 * variable, so that it does not get reparsed when we backtrack.
 *
 *   BINARY_OP = BINARY_OP_LITERAL >> qi::attr(parameter) >> CURRENT_PRECEDENCE
 *
 *   CURRENT_PRECEDENCE = LOWER_PRECEDENCE[local_var = result] >>
 *     (BINARY_OP(local_var) | OTHER_OP(local_var) | YET_ANOTHER_OP(local_var) | qi::attr(local_var)
 *
 */
 
template <typename Iterator>
struct op_grammar : qi::grammar<Iterator, expr(), qi::space_type> {
  qi::rule<Iterator, constant(), qi::space_type> constant_;
  qi::rule<Iterator, n_var(), qi::space_type> n_;
  qi::rule<Iterator, not_op(), qi::space_type> not_;
  qi::rule<Iterator, and_op(expr), qi::space_type> and_;
  qi::rule<Iterator, or_op(expr), qi::space_type> or_;
  qi::rule<Iterator, eq_op(expr), qi::space_type> eq_;
  qi::rule<Iterator, neq_op(expr), qi::space_type> neq_;
  qi::rule<Iterator, ge_op(expr), qi::space_type> ge_;
  qi::rule<Iterator, le_op(expr), qi::space_type> le_;
  qi::rule<Iterator, gt_op(expr), qi::space_type> gt_;
  qi::rule<Iterator, lt_op(expr), qi::space_type> lt_;
  qi::rule<Iterator, mod_op(expr), qi::space_type> mod_;
  qi::rule<Iterator, ternary_op(expr), qi::space_type> ternary_;
  qi::rule<Iterator, expr(), qi::space_type> paren_expr_;
 
  // expression precedence levels
  qi::rule<Iterator, expr(), qi::space_type, qi::locals<expr>> ternary_level_;
  qi::rule<Iterator, expr(), qi::space_type, qi::locals<expr>> or_level_;
  qi::rule<Iterator, expr(), qi::space_type, qi::locals<expr>> and_level_;
  qi::rule<Iterator, expr(), qi::space_type, qi::locals<expr>> eq_level_;
  qi::rule<Iterator, expr(), qi::space_type, qi::locals<expr>> rel_level_;
  qi::rule<Iterator, expr(), qi::space_type, qi::locals<expr>> mod_level_;
  qi::rule<Iterator, expr(), qi::space_type> atom_level_;
  qi::rule<Iterator, expr(), qi::space_type> expr_;
 
  // handle optional ';' at end
  qi::rule<Iterator, expr(), qi::space_type> main_;
 
  op_grammar() : op_grammar::base_type(main_) {
    using qi::attr;
    using qi::lit;
 
    constant_ = qi::uint_;
    n_ = qi::char_('n');
    paren_expr_ = lit('(') >> expr_ >> lit(')');
    not_ = lit('!') >> atom_level_;
    atom_level_ = paren_expr_ | not_ | n_ | constant_;
 
    mod_ = lit('%') >> attr(qi::_r1) >> atom_level_;
    mod_level_ = qi::omit[atom_level_[qi::_a = qi::_1]] >> (mod_(qi::_a) | attr(qi::_a));
 
    ge_ = lit(">=") >> attr(qi::_r1) >> mod_level_;
    le_ = lit("<=") >> attr(qi::_r1) >> mod_level_;
    gt_ = lit('>') >> attr(qi::_r1) >> mod_level_;
    lt_ = lit('<') >> attr(qi::_r1) >> mod_level_;
    rel_level_ = qi::omit[mod_level_[qi::_a = qi::_1]] >> (ge_(qi::_a) | le_(qi::_a) | gt_(qi::_a) | lt_(qi::_a) | attr(qi::_a));
 
    eq_ = lit("==") >> attr(qi::_r1) >> rel_level_;
    neq_ = lit("!=") >> attr(qi::_r1) >> rel_level_;
    eq_level_ = qi::omit[rel_level_[qi::_a = qi::_1]] >> (eq_(qi::_a) | neq_(qi::_a) | attr(qi::_a));
 
    and_ = lit("&&") >> attr(qi::_r1) >> and_level_;
    and_level_ = qi::omit[eq_level_[qi::_a = qi::_1]] >> (and_(qi::_a) | attr(qi::_a));
 
    or_ = lit("||") >> attr(qi::_r1) >> or_level_;
    or_level_ = qi::omit[and_level_[qi::_a = qi::_1]] >> (or_(qi::_a) | attr(qi::_a));
 
    ternary_ = lit('?') >> attr(qi::_r1) >> ternary_level_ >> lit(':') >> ternary_level_;
    ternary_level_ = qi::omit[or_level_[qi::_a = qi::_1]] >> (ternary_(qi::_a) | attr(qi::_a));
 
    expr_ = ternary_level_;
 
    main_ = expr_ >> -lit(';');
  }
};
 
/***
 * Now define a simple stack machine to evaluate the expressions efficiently.
 *
 * First define op_codes
 */
 
#define ENUMERATE(X, Y) X,
 
enum class op_code { n_var, FOREACH_SPIRIT_PO_BINARY_OP(ENUMERATE) not_op };
 
#undef ENUMERATE
 
/** Instruction that causes us to skip upcoming instructions */
struct skip {
  uint distance;
};
 
/** Instructions that conditionally cause us to skip upcoming instructions */
struct skip_if {
  uint distance;
};
 
struct skip_if_not {
  uint distance;
};
 
/***
 * Instruction is a variant type that represents either a push_constant, branch, jump, or arithmetic op.
 */
typedef boost::variant<constant, skip, skip_if, skip_if_not, op_code> instruction;
 
/***
 * Debug strings for instruction set
 */
#ifdef SPIRIT_PO_DEBUG
inline std::string op_code_string(op_code oc) {
  std::string result = "[  ";
  switch (oc) {
    case op_code::n_var: {
      result += "n ";
      break;
    }
    case op_code::not_op: {
      result += "! ";
      break;
    }
#define OP_CODE_STR_CASE_(X, Y)                  \
    case op_code::X: {                           \
      result += #Y;                              \
      break;                                     \
    }
 
FOREACH_SPIRIT_PO_BINARY_OP(OP_CODE_STR_CASE_)
 
#undef OP_CODE_STR_CASE_
  }
 
  if (result.size() < 5) { result += ' '; } \
  result += "  :   ]";
  return result;
}
 
struct instruction_debug_string_maker : boost::static_visitor<std::string> {
  std::string operator()(const constant & c) const {
    return "[ push : " + std::to_string(c.value) + " ]";
  }
  std::string operator()(const skip & s) const {
    return "[ skip : " + std::to_string(s.distance) + " ]";
  }
  std::string operator()(const skip_if & s) const {
    return "[ sif  : " + std::to_string(s.distance) + " ]";
  }
  std::string operator()(const skip_if_not & s) const {
    return "[ sifn : " + std::to_string(s.distance) + " ]";
  }
  std::string operator()(const op_code & oc) const {
    return op_code_string(oc);
  }
};
 
inline std::string debug_string(const instruction & i) {
  return boost::apply_visitor(instruction_debug_string_maker{}, i);
}
 
#endif // SPIRIT_PO_DEBUG
 
/***
 * Helper: Check if an expression obviously is zero-one valued
 */
struct is_boolean : public boost::static_visitor<bool> {
  bool operator()(const and_op &) const { return true; }
  bool operator()(const or_op &) const { return true; }
  bool operator()(const not_op &) const { return true; }
  bool operator()(const eq_op &) const { return true; }
  bool operator()(const neq_op &) const { return true; }
  bool operator()(const ge_op &) const { return true; }
  bool operator()(const le_op &) const { return true; }
  bool operator()(const gt_op &) const { return true; }
  bool operator()(const lt_op &) const { return true; }
  bool operator()(const n_var &) const { return false; }
  bool operator()(const constant & c) const { return (c.value == 0 || c.value == 1); }
  bool operator()(const mod_op & m) const { return boost::apply_visitor(*this, m.e1); }
  bool operator()(const ternary_op & t) const { return boost::apply_visitor(*this, t.e2) && boost::apply_visitor(*this, t.e3); }
};
 
 
/***
 * Visitor that maps expressions to instruction sequences
 */
struct emitter : public boost::static_visitor<std::vector<instruction>> {
  std::vector<instruction> operator()(const constant & c) const {
    return std::vector<instruction>{instruction{c}};
  }
  std::vector<instruction> operator()(const n_var &) const {
    return std::vector<instruction>{instruction{op_code::n_var}};
  }
  std::vector<instruction> operator()(const not_op & o) const {
    auto result = boost::apply_visitor(*this, o.e1);
    result.emplace_back(op_code::not_op);
    return result;
  }
#define EMIT_OP_(name, op) \
  std::vector<instruction> operator()(const name & o) const {        \
    auto result = boost::apply_visitor(*this, o.e1);                 \
    auto temp = boost::apply_visitor(*this, o.e2);                   \
    std::move(temp.begin(), temp.end(), std::back_inserter(result)); \
    result.emplace_back(op_code::name);                              \
    return result;                                                   \
  }
 
FOREACH_SPIRIT_PO_BINARY_OP(EMIT_OP_)
 
#undef EMIT_OP_
 
  /***
   * We make &&, ||, and ? shortcut
   */
  std::vector<instruction> operator()(const and_op & o) const {
    auto result = boost::apply_visitor(*this, o.e1);
    auto second = boost::apply_visitor(*this, o.e2);
    bool second_is_boolean = boost::apply_visitor(is_boolean(), o.e2);
 
    uint sec_size = static_cast<uint>(second.size());
    if (!second_is_boolean) { sec_size += 2; }
 
    result.emplace_back(skip_if{2});
    result.emplace_back(constant{0});
    result.emplace_back(skip{sec_size});
 
    std::move(second.begin(), second.end(), std::back_inserter(result));
    if (!second_is_boolean) {
      result.emplace_back(op_code::not_op);
      result.emplace_back(op_code::not_op);
    }
 
    return result;
  }
 
  std::vector<instruction> operator()(const or_op & o) const {
    auto result = boost::apply_visitor(*this, o.e1);
    auto second = boost::apply_visitor(*this, o.e2);
    bool second_is_boolean = boost::apply_visitor(is_boolean(), o.e2);
 
    uint sec_size = static_cast<uint>(second.size());
    if (!second_is_boolean) { sec_size += 2; }
 
    result.emplace_back(skip_if_not{2});
    result.emplace_back(constant{1});
    result.emplace_back(skip{sec_size});
 
    std::move(second.begin(), second.end(), std::back_inserter(result));
    if (!second_is_boolean) {
      result.emplace_back(op_code::not_op);
      result.emplace_back(op_code::not_op);
    }
 
    return result;
  }
 
  std::vector<instruction> operator()(const ternary_op & o) const {
    auto result = boost::apply_visitor(*this, o.e1);
    auto tbranch = boost::apply_visitor(*this, o.e2);
    auto fbranch = boost::apply_visitor(*this, o.e3);
 
    uint tsize = static_cast<uint>(tbranch.size());
    uint fsize = static_cast<uint>(fbranch.size());
 
    // We use jump if / jump if not in the way that will let us put the shorter branch first.
    if (tbranch.size() > fbranch.size()) {
       // + 1 to size because we have to put a jump at end of this branch also
      result.emplace_back(skip_if{fsize + 1});
      std::move(fbranch.begin(), fbranch.end(), std::back_inserter(result));
      result.emplace_back(skip{tsize});
      std::move(tbranch.begin(), tbranch.end(), std::back_inserter(result));
    } else {
      result.emplace_back(skip_if_not{tsize + 1});
      std::move(tbranch.begin(), tbranch.end(), std::back_inserter(result));
      result.emplace_back(skip{fsize});
      std::move(fbranch.begin(), fbranch.end(), std::back_inserter(result));
    }
    return result;
  }
};
 
/***
 * Actual stack machine
 */
 
class stack_machine : public boost::static_visitor<uint> {
  std::vector<instruction> instruction_seq_;
  std::vector<uint> stack_;
  uint n_value_;
 
#ifdef SPIRIT_PO_DEBUG
public:
  void debug_print_instructions() const {
    std::cerr << "Instruction sequence:\n";
    for (const auto & i : instruction_seq_) {
      std::cerr << debug_string(i) << std::endl;
    }
  }
private:
 
#define MACHINE_ASSERT(X)                       \
  do {                                          \
    if (!(X)) {                                 \
      std::cerr << "Stack machine failure:\n";  \
      debug_print_instructions();               \
      assert(false && #X);                      \
    }                                           \
  } while(0)
 
#else // SPIRIT_PO_DEBUG
 
#define MACHINE_ASSERT(...)  do {} while(0)
 
#endif // SPIRIT_PO_DEBUG
 
  uint pop_one() {
    MACHINE_ASSERT(stack_.size());
 
    uint result = stack_.back();
    stack_.resize(stack_.size() - 1);
    return result;
  }
 
public:
  explicit stack_machine(const expr & e)
    : instruction_seq_(boost::apply_visitor(emitter(), e))
    , stack_()
    , n_value_()
  {}
 
  /***
   * operator() takes the instruction that we should execute
   * It should perform the operation adjusting the stack
   * It returns the amount by which we should increment the
   * program counter.
   */
  uint operator()(const constant & c) {
    stack_.emplace_back(c.value);
    return 1;
  }
 
  uint operator()(const skip & s) {
    return 1 + s.distance;
  }
 
  uint operator()(const skip_if & s) {
   return 1 + (pop_one() ? s.distance : 0);
  }
 
  uint operator()(const skip_if_not & s) {
   return 1 + (pop_one() ? 0 : s.distance);
  }
 
  uint operator()(op_code oc) {
    switch (oc) {
      case op_code::n_var: {
        stack_.emplace_back(n_value_);
        return 1;
      }
      case op_code::not_op: {
        MACHINE_ASSERT(stack_.size());
        stack_.back() = !stack_.back();
        return 1;
      }
#define STACK_MACHINE_CASE_(name, op)                                                                  \
      case op_code::name: {                                                                            \
        MACHINE_ASSERT(stack_.size() >= 2);                                                            \
        uint parm2 = pop_one();                                                                        \
                                                                                                       \
        if (op_code::name == op_code::mod_op) {                                                        \
          MACHINE_ASSERT(parm2 && "Division by zero when evaluating gettext plural form expression");  \
        }                                                                                              \
                                                                                                       \
        stack_.back() = (stack_.back() op parm2);                                                      \
        return 1;                                                                                      \
      }
 
FOREACH_SPIRIT_PO_BINARY_OP(STACK_MACHINE_CASE_)
 
#undef STACK_MACHINE_CASE_
    }
    MACHINE_ASSERT(false);
    return 1;
  }
 
  uint compute(uint arg) {
    n_value_ = arg;
    stack_.resize(0);
    uint pc = 0;
    while (pc < instruction_seq_.size()) {
      pc += boost::apply_visitor(*this, instruction_seq_[pc]);
    }
    MACHINE_ASSERT(pc == instruction_seq_.size());
    MACHINE_ASSERT(stack_.size() == 1);
    return stack_[0];
  }
};
 
#undef MACHINE_ASSERT
 
// X macros not used anymore
#undef FOREACH_SPIRIT_PO_BINARY_OP
#undef FOREACH_SPIRIT_PO_CONJUNCTION
 
} // end namespace default_plural_forms
 
} // end namespace spirit_po
 
#endif // SPIRIT_PO_DEFAULT_PLURAL_FORMS_EXPRESSIONS_HPP_INCLUDED