3 * Parse and evaluate a plural rule.
5 * http://unicode.org/reports/tr35/#Language_Plural_Rules
7 * @author Niklas Laxstrom, Tim Starling
9 * @copyright Copyright © 2010-2012, Niklas Laxström
10 * @license http://www.gnu.org/copyleft/gpl.html GNU General Public License 2.0 or later
15 class CLDRPluralRuleEvaluator
{
17 * Evaluate a number against a set of plural rules. If a rule passes,
18 * return the index of plural rule.
20 * @param int The number to be evaluated against the rules
21 * @param array The associative array of plural rules in pluralform => rule format.
22 * @return int The index of the plural form which passed the evaluation
24 public static function evaluate( $number, array $rules ) {
25 $rules = self
::compile( $rules );
26 return self
::evaluateCompiled( $number, $rules );
30 * Convert a set of rules to a compiled form which is optimised for
31 * fast evaluation. The result will be an array of strings, and may be cached.
33 * @param $rules The rules to compile
34 * @return An array of compile rules.
36 public static function compile( array $rules ) {
37 // We can't use array_map() for this because it generates a warning if
38 // there is an exception.
39 foreach ( $rules as &$rule ) {
40 $rule = CLDRPluralRuleConverter
::convert( $rule );
46 * Evaluate a compiled set of rules returned by compile(). Do not allow
47 * the user to edit the compiled form, or else PHP errors may result.
49 public static function evaluateCompiled( $number, array $rules ) {
50 // The compiled form is RPN, with tokens strictly delimited by
51 // spaces, so this is a simple RPN evaluator.
52 foreach ( $rules as $i => $rule ) {
56 foreach ( StringUtils
::explode( ' ', $rule ) as $token ) {
58 if ( $token === 'n' ) {
60 } elseif ( $ord >= $zero && $ord <= $nine ) {
61 $stack[] = intval( $token );
63 $right = array_pop( $stack );
64 $left = array_pop( $stack );
65 $result = self
::doOperation( $token, $left, $right );
73 // None of the provided rules match. The number belongs to caregory
74 // 'other' which comes last.
75 return count( $rules );
79 * Do a single operation
81 * @param $token string The token string
82 * @param $left The left operand. If it is an object, its state may be destroyed.
83 * @param $right The right operand
84 * @throws CLDRPluralRuleError
87 private static function doOperation( $token, $left, $right ) {
88 if ( in_array( $token, array( 'in', 'not-in', 'within', 'not-within' ) ) ) {
89 if ( !($right instanceof CLDRPluralRuleEvaluator_Range
) ) {
90 $right = new CLDRPluralRuleEvaluator_Range( $right );
95 return $left ||
$right;
97 return $left && $right;
99 return $left == $right;
101 return $left != $right;
103 return $right->isNumberIn( $left );
105 return !$right->isNumberIn( $left );
107 return $right->isNumberWithin( $left );
109 return !$right->isNumberWithin( $left );
111 if ( is_int( $left ) ) {
112 return (int) fmod( $left, $right );
114 return fmod( $left, $right );
116 if ( $left instanceof CLDRPluralRuleEvaluator_Range
) {
119 $range = new CLDRPluralRuleEvaluator_Range( $left );
121 $range->add( $right );
124 return new CLDRPluralRuleEvaluator_Range( $left, $right );
126 throw new CLDRPluralRuleError( "Invalid RPN token" );
132 * Evaluator helper class representing a range list.
134 class CLDRPluralRuleEvaluator_Range
{
135 public $parts = array();
137 function __construct( $start, $end = false ) {
138 if ( $end === false ) {
139 $this->parts
[] = $start;
141 $this->parts
[] = array( $start, $end );
146 * Determine if the given number is inside the range. If $integerConstraint
147 * is true, the number must additionally be an integer if it is to match
150 function isNumberIn( $number, $integerConstraint = true ) {
151 foreach ( $this->parts
as $part ) {
152 if ( is_array( $part ) ) {
153 if ( ( !$integerConstraint ||
floor( $number ) === (float)$number )
154 && $number >= $part[0] && $number <= $part[1] )
159 if ( $number == $part ) {
168 * Readable alias for isNumberIn( $number, false ), and the implementation
169 * of the "within" operator.
171 function isNumberWithin( $number ) {
172 return $this->isNumberIn( $number, false );
176 * Add another part to this range. The supplied new part may either be a
177 * range object itself, or a single number.
179 function add( $other ) {
180 if ( $other instanceof self
) {
181 $this->parts
= array_merge( $this->parts
, $other->parts
);
183 $this->parts
[] = $other;
190 function __toString() {
192 foreach ( $this->parts
as $i => $part ) {
196 if ( is_array( $part ) ) {
197 $s .= $part[0] . '..' . $part[1];
209 * Helper class for converting rules to reverse polish notation (RPN).
211 class CLDRPluralRuleConverter
{
212 public $rule, $pos, $end;
213 public $operators = array();
214 public $operands = array();
217 * Precedence levels. Note that there's no need to worry about associativity
218 * for the level 4 operators, since they return boolean and don't accept
221 static $precedence = array(
236 * A character list defining whitespace, for use in strspn() etc.
238 const WHITESPACE_CLASS
= " \t\r\n";
241 * Same for digits. Note that the grammar given in UTS #35 doesn't allow
242 * negative numbers or decimals.
244 const NUMBER_CLASS
= '0123456789';
247 * An anchored regular expression which matches a word at the current offset.
249 const WORD_REGEX
= '/[a-zA-Z]+/A';
252 * Convert a rule to RPN. This is the only public entry point.
254 public static function convert( $rule ) {
255 $parser = new self( $rule );
256 return $parser->doConvert();
260 * Private constructor.
262 protected function __construct( $rule ) {
265 $this->end
= strlen( $rule );
271 protected function doConvert() {
272 $expectOperator = true;
274 // Iterate through all tokens, saving the operators and operands to a
275 // stack per Dijkstra's shunting yard algorithm.
276 while ( false !== ( $token = $this->nextToken() ) ) {
277 // In this grammar, there are only binary operators, so every valid
278 // rule string will alternate between operator and operand tokens.
279 $expectOperator = !$expectOperator;
281 if ( $token instanceof CLDRPluralRuleConverter_Expression
) {
283 if ( $expectOperator ) {
284 $token->error( 'unexpected operand' );
286 $this->operands
[] = $token;
290 if ( !$expectOperator ) {
291 $token->error( 'unexpected operator' );
293 // Resolve higher precedence levels
294 $lastOp = end( $this->operators
);
295 while ( $lastOp && self
::$precedence[$token->name
] <= self
::$precedence[$lastOp->name
] ) {
296 $this->doOperation( $lastOp, $this->operands
);
297 array_pop( $this->operators
);
298 $lastOp = end( $this->operators
);
300 $this->operators
[] = $token;
304 // Finish off the stack
305 while ( $op = array_pop( $this->operators
) ) {
306 $this->doOperation( $op, $this->operands
);
309 // Make sure the result is sane. The first case is possible for an empty
310 // string input, the second should be unreachable.
311 if ( !count( $this->operands
) ) {
312 $this->error( 'condition expected' );
313 } elseif ( count( $this->operands
) > 1 ) {
314 $this->error( 'missing operator or too many operands' );
317 $value = $this->operands
[0];
318 if ( $value->type
!== 'boolean' ) {
319 $this->error( 'the result must have a boolean type' );
322 return $this->operands
[0]->rpn
;
326 * Fetch the next token from the input string. Return it as a
327 * CLDRPluralRuleConverter_Fragment object.
329 protected function nextToken() {
330 if ( $this->pos
>= $this->end
) {
335 $length = strspn( $this->rule
, self
::WHITESPACE_CLASS
, $this->pos
);
336 $this->pos +
= $length;
338 if ( $this->pos
>= $this->end
) {
343 $length = strspn( $this->rule
, self
::NUMBER_CLASS
, $this->pos
);
344 if ( $length !== 0 ) {
345 $token = $this->newNumber( substr( $this->rule
, $this->pos
, $length ), $this->pos
);
346 $this->pos +
= $length;
351 if ( $this->rule
[$this->pos
] === ',' ) {
352 $token = $this->newOperator( ',', $this->pos
, 1 );
358 if ( substr( $this->rule
, $this->pos
, 2 ) === '..' ) {
359 $token = $this->newOperator( '..', $this->pos
, 2 );
365 if ( !preg_match( self
::WORD_REGEX
, $this->rule
, $m, 0, $this->pos
) ) {
366 $this->error( 'unexpected character "' . $this->rule
[$this->pos
] . '"' );
368 $word1 = strtolower( $m[0] );
370 $nextTokenPos = $this->pos +
strlen( $word1 );
371 if ( $word1 === 'not' ||
$word1 === 'is' ) {
372 // Look ahead one word
373 $nextTokenPos +
= strspn( $this->rule
, self
::WHITESPACE_CLASS
, $nextTokenPos );
374 if ( $nextTokenPos < $this->end
375 && preg_match( self
::WORD_REGEX
, $this->rule
, $m, 0, $nextTokenPos ) )
377 $word2 = strtolower( $m[0] );
378 $nextTokenPos +
= strlen( $word2 );
382 // Two-word operators like "is not" take precedence over single-word operators like "is"
383 if ( $word2 !== '' ) {
384 $bothWords = "{$word1}-{$word2}";
385 if ( isset( self
::$precedence[$bothWords] ) ) {
386 $token = $this->newOperator( $bothWords, $this->pos
, $nextTokenPos - $this->pos
);
387 $this->pos
= $nextTokenPos;
392 // Single-word operators
393 if ( isset( self
::$precedence[$word1] ) ) {
394 $token = $this->newOperator( $word1, $this->pos
, strlen( $word1 ) );
395 $this->pos +
= strlen( $word1 );
399 // The special numerical keyword "n"
400 if ( $word1 === 'n' ) {
401 $token = $this->newNumber( 'n', $this->pos
);
406 $this->error( 'unrecognised word' );
410 * For the binary operator $op, pop its operands off the stack and push
411 * a fragment with rpn and type members describing the result of that
414 protected function doOperation( $op ) {
415 if ( count( $this->operands
) < 2 ) {
416 $op->error( 'missing operand' );
418 $right = array_pop( $this->operands
);
419 $left = array_pop( $this->operands
);
420 $result = $op->operate( $left, $right );
421 $this->operands
[] = $result;
425 * Create a numerical expression object
427 protected function newNumber( $text, $pos ) {
428 return new CLDRPluralRuleConverter_Expression( $this, 'number', $text, $pos, strlen( $text ) );
432 * Create a binary operator
434 protected function newOperator( $type, $pos, $length ) {
435 return new CLDRPluralRuleConverter_Operator( $this, $type, $pos, $length );
441 protected function error( $message ) {
442 throw new CLDRPluralRuleError( $message );
447 * Helper for CLDRPluralRuleConverter.
448 * The base class for operators and expressions, describing a region of the input string.
450 class CLDRPluralRuleConverter_Fragment
{
451 public $parser, $pos, $length, $end;
453 function __construct( $parser, $pos, $length ) {
454 $this->parser
= $parser;
456 $this->length
= $length;
457 $this->end
= $pos +
$length;
460 public function error( $message ) {
461 $text = $this->getText();
462 throw new CLDRPluralRuleError( "$message at position " . ( $this->pos +
1 ) . ": \"$text\"" );
465 public function getText() {
466 return substr( $this->parser
->rule
, $this->pos
, $this->length
);
471 * Helper for CLDRPluralRuleConverter.
472 * An expression object, representing a region of the input string (for error
473 * messages), the RPN notation used to evaluate it, and the result type for
476 class CLDRPluralRuleConverter_Expression
extends CLDRPluralRuleConverter_Fragment
{
479 function __construct( $parser, $type, $rpn, $pos, $length ) {
480 parent
::__construct( $parser, $pos, $length );
485 public function isType( $type ) {
486 if ( $type === 'range' && ( $this->type
=== 'range' ||
$this->type
=== 'number' ) ) {
489 if ( $type === $this->type
) {
497 * Helper for CLDRPluralRuleConverter.
498 * An operator object, representing a region of the input string (for error
499 * messages), and the binary operator at that location.
501 class CLDRPluralRuleConverter_Operator
extends CLDRPluralRuleConverter_Fragment
{
505 * Each op type has three characters: left operand type, right operand type and result type
511 * A number is a kind of range.
513 static $opTypes = array(
521 'not-within' => 'nrb',
528 * Map converting from the abbrevation to the full form.
530 static $typeSpecMap = array(
536 function __construct( $parser, $name, $pos, $length ) {
537 parent
::__construct( $parser, $pos, $length );
541 public function operate( $left, $right ) {
542 $typeSpec = self
::$opTypes[$this->name
];
544 $leftType = self
::$typeSpecMap[$typeSpec[0]];
545 $rightType = self
::$typeSpecMap[$typeSpec[1]];
546 $resultType = self
::$typeSpecMap[$typeSpec[2]];
548 $start = min( $this->pos
, $left->pos
, $right->pos
);
549 $end = max( $this->end
, $left->end
, $right->end
);
550 $length = $end - $start;
552 $newExpr = new CLDRPluralRuleConverter_Expression( $this->parser
, $resultType,
553 "{$left->rpn} {$right->rpn} {$this->name}",
556 if ( !$left->isType( $leftType ) ) {
557 $newExpr->error( "invalid type for left operand: expected $leftType, got {$left->type}" );
560 if ( !$right->isType( $rightType ) ) {
561 $newExpr->error( "invalid type for right operand: expected $rightType, got {$right->type}" );
568 * The exception class for all the classes in this file. This will be thrown
569 * back to the caller if there is any validation error.
571 class CLDRPluralRuleError
extends MWException
{
572 function __construct( $message ) {
573 parent
::__construct( 'CLDR plural rule error: ' . $message );