languages/utils/CLDRPluralRuleConverter.php

   1 <?php
   2 /**
   3  * @author Niklas Laxström, Tim Starling
   4  *
   5  * @copyright Copyright © 2010-2012, Niklas Laxström
   6  * @license http://www.gnu.org/copyleft/gpl.html GNU General Public License 2.0 or later
   7  *
   8  * @file
   9  * @since 1.20
  10  */
  11
  12 /**
  13  * Helper class for converting rules to reverse polish notation (RPN).
  14  */
  15 class CLDRPluralRuleConverter {
  16         /**
  17          * The input string
  18          *
  19          * @var string
  20          */
  21         public $rule;
  22
  23         /**
  24          * The current position
  25          *
  26          * @var int
  27          */
  28         public $pos;
  29
  30         /**
  31          * The past-the-end position
  32          *
  33          * @var int
  34          */
  35         public $end;
  36
  37         /**
  38          * The operator stack
  39          *
  40          * @var array
  41          */
  42         public $operators = array();
  43
  44         /**
  45          * The operand stack
  46          *
  47          * @var array
  48          */
  49         public $operands = array();
  50
  51         /**
  52          * Precedence levels. Note that there's no need to worry about associativity
  53          * for the level 4 operators, since they return boolean and don't accept
  54          * boolean inputs.
  55          */
  56         private static $precedence = array(
  57                 'or' => 2,
  58                 'and' => 3,
  59                 'is' => 4,
  60                 'is-not' => 4,
  61                 'in' => 4,
  62                 'not-in' => 4,
  63                 'within' => 4,
  64                 'not-within' => 4,
  65                 'mod' => 5,
  66                 ',' => 6,
  67                 '..' => 7,
  68         );
  69
  70         /**
  71          * A character list defining whitespace, for use in strspn() etc.
  72          */
  73         const WHITESPACE_CLASS = " \t\r\n";
  74
  75         /**
  76          * Same for digits. Note that the grammar given in UTS #35 doesn't allow
  77          * negative numbers or decimal separators.
  78          */
  79         const NUMBER_CLASS = '0123456789';
  80
  81         /**
  82          * A character list of symbolic operands.
  83          */
  84         const OPERAND_SYMBOLS = 'nivwft';
  85
  86         /**
  87          * An anchored regular expression which matches a word at the current offset.
  88          */
  89         const WORD_REGEX = '/[a-zA-Z@]+/A';
  90
  91         /**
  92          * Convert a rule to RPN. This is the only public entry point.
  93          *
  94          * @param string $rule The rule to convert
  95          * @return string The RPN representation of the rule
  96          */
  97         public static function convert( $rule ) {
  98                 $parser = new self( $rule );
  99
 100                 return $parser->doConvert();
 101         }
 102
 103         /**
 104          * Private constructor.
 105          */
 106         protected function __construct( $rule ) {
 107                 $this->rule = $rule;
 108                 $this->pos = 0;
 109                 $this->end = strlen( $rule );
 110         }
 111
 112         /**
 113          * Do the operation.
 114          *
 115          * @return string The RPN representation of the rule (e.g. "5 3 mod n is")
 116          */
 117         protected function doConvert() {
 118                 $expectOperator = true;
 119
 120                 // Iterate through all tokens, saving the operators and operands to a
 121                 // stack per Dijkstra's shunting yard algorithm.
 122                 /** @var CLDRPluralRuleConverterOperator $token */
 123                 while ( false !== ( $token = $this->nextToken() ) ) {
 124                         // In this grammar, there are only binary operators, so every valid
 125                         // rule string will alternate between operator and operand tokens.
 126                         $expectOperator = !$expectOperator;
 127
 128                         if ( $token instanceof CLDRPluralRuleConverterExpression ) {
 129                                 // Operand
 130                                 if ( $expectOperator ) {
 131                                         $token->error( 'unexpected operand' );
 132                                 }
 133                                 $this->operands[] = $token;
 134                                 continue;
 135                         } else {
 136                                 // Operator
 137                                 if ( !$expectOperator ) {
 138                                         $token->error( 'unexpected operator' );
 139                                 }
 140                                 // Resolve higher precedence levels
 141                                 $lastOp = end( $this->operators );
 142                                 while ( $lastOp && self::$precedence[$token->name] <= self::$precedence[$lastOp->name] ) {
 143                                         $this->doOperation( $lastOp, $this->operands );
 144                                         array_pop( $this->operators );
 145                                         $lastOp = end( $this->operators );
 146                                 }
 147                                 $this->operators[] = $token;
 148                         }
 149                 }
 150
 151                 // Finish off the stack
 152                 while ( $op = array_pop( $this->operators ) ) {
 153                         $this->doOperation( $op, $this->operands );
 154                 }
 155
 156                 // Make sure the result is sane. The first case is possible for an empty
 157                 // string input, the second should be unreachable.
 158                 if ( !count( $this->operands ) ) {
 159                         $this->error( 'condition expected' );
 160                 } elseif ( count( $this->operands ) > 1 ) {
 161                         $this->error( 'missing operator or too many operands' );
 162                 }
 163
 164                 $value = $this->operands[0];
 165                 if ( $value->type !== 'boolean' ) {
 166                         $this->error( 'the result must have a boolean type' );
 167                 }
 168
 169                 return $this->operands[0]->rpn;
 170         }
 171
 172         /**
 173          * Fetch the next token from the input string.
 174          *
 175          * @return CLDRPluralRuleConverterFragment The next token
 176          */
 177         protected function nextToken() {
 178                 if ( $this->pos >= $this->end ) {
 179                         return false;
 180                 }
 181
 182                 // Whitespace
 183                 $length = strspn( $this->rule, self::WHITESPACE_CLASS, $this->pos );
 184                 $this->pos += $length;
 185
 186                 if ( $this->pos >= $this->end ) {
 187                         return false;
 188                 }
 189
 190                 // Number
 191                 $length = strspn( $this->rule, self::NUMBER_CLASS, $this->pos );
 192                 if ( $length !== 0 ) {
 193                         $token = $this->newNumber( substr( $this->rule, $this->pos, $length ), $this->pos );
 194                         $this->pos += $length;
 195
 196                         return $token;
 197                 }
 198
 199                 // Two-character operators
 200                 $op2 = substr( $this->rule, $this->pos, 2 );
 201                 if ( $op2 === '..' || $op2 === '!=' ) {
 202                         $token = $this->newOperator( $op2, $this->pos, 2 );
 203                         $this->pos += 2;
 204
 205                         return $token;
 206                 }
 207
 208                 // Single-character operators
 209                 $op1 = $this->rule[$this->pos];
 210                 if ( $op1 === ',' || $op1 === '=' || $op1 === '%' ) {
 211                         $token = $this->newOperator( $op1, $this->pos, 1 );
 212                         $this->pos++;
 213
 214                         return $token;
 215                 }
 216
 217                 // Word
 218                 if ( !preg_match( self::WORD_REGEX, $this->rule, $m, 0, $this->pos ) ) {
 219                         $this->error( 'unexpected character "' . $this->rule[$this->pos] . '"' );
 220                 }
 221                 $word1 = strtolower( $m[0] );
 222                 $word2 = '';
 223                 $nextTokenPos = $this->pos + strlen( $word1 );
 224                 if ( $word1 === 'not' || $word1 === 'is' ) {
 225                         // Look ahead one word
 226                         $nextTokenPos += strspn( $this->rule, self::WHITESPACE_CLASS, $nextTokenPos );
 227                         if ( $nextTokenPos < $this->end
 228                                 && preg_match( self::WORD_REGEX, $this->rule, $m, 0, $nextTokenPos )
 229                         ) {
 230                                 $word2 = strtolower( $m[0] );
 231                                 $nextTokenPos += strlen( $word2 );
 232                         }
 233                 }
 234
 235                 // Two-word operators like "is not" take precedence over single-word operators like "is"
 236                 if ( $word2 !== '' ) {
 237                         $bothWords = "{$word1}-{$word2}";
 238                         if ( isset( self::$precedence[$bothWords] ) ) {
 239                                 $token = $this->newOperator( $bothWords, $this->pos, $nextTokenPos - $this->pos );
 240                                 $this->pos = $nextTokenPos;
 241
 242                                 return $token;
 243                         }
 244                 }
 245
 246                 // Single-word operators
 247                 if ( isset( self::$precedence[$word1] ) ) {
 248                         $token = $this->newOperator( $word1, $this->pos, strlen( $word1 ) );
 249                         $this->pos += strlen( $word1 );
 250
 251                         return $token;
 252                 }
 253
 254                 // The single-character operand symbols
 255                 if ( strpos( self::OPERAND_SYMBOLS, $word1 ) !== false ) {
 256                         $token = $this->newNumber( $word1, $this->pos );
 257                         $this->pos++;
 258
 259                         return $token;
 260                 }
 261
 262                 // Samples
 263                 if ( $word1 === '@integer' || $word1 === '@decimal' ) {
 264                         // Samples are like comments, they have no effect on rule evaluation.
 265                         // They run from the first sample indicator to the end of the string.
 266                         $this->pos = $this->end;
 267
 268                         return false;
 269                 }
 270
 271                 $this->error( 'unrecognised word' );
 272         }
 273
 274         /**
 275          * For the binary operator $op, pop its operands off the stack and push
 276          * a fragment with rpn and type members describing the result of that
 277          * operation.
 278          *
 279          * @param CLDRPluralRuleConverterOperator $op
 280          */
 281         protected function doOperation( $op ) {
 282                 if ( count( $this->operands ) < 2 ) {
 283                         $op->error( 'missing operand' );
 284                 }
 285                 $right = array_pop( $this->operands );
 286                 $left = array_pop( $this->operands );
 287                 $result = $op->operate( $left, $right );
 288                 $this->operands[] = $result;
 289         }
 290
 291         /**
 292          * Create a numerical expression object
 293          *
 294          * @param string $text
 295          * @param int $pos
 296          * @return CLDRPluralRuleConverterExpression The numerical expression
 297          */
 298         protected function newNumber( $text, $pos ) {
 299                 return new CLDRPluralRuleConverterExpression( $this, 'number', $text, $pos, strlen( $text ) );
 300         }
 301
 302         /**
 303          * Create a binary operator
 304          *
 305          * @param string $type
 306          * @param int $pos
 307          * @param int $length
 308          * @return CLDRPluralRuleConverterOperator The operator
 309          */
 310         protected function newOperator( $type, $pos, $length ) {
 311                 return new CLDRPluralRuleConverterOperator( $this, $type, $pos, $length );
 312         }
 313
 314         /**
 315          * Throw an error
 316          */
 317         protected function error( $message ) {
 318                 throw new CLDRPluralRuleError( $message );
 319         }
 320 }