CLDRPluralRuleEvaluator.php

Go to the documentation of this file.

<?php
class CLDRPluralRuleEvaluator {
    public static function evaluate( $number, array $rules ) {
        $rules = self::compile( $rules );
        return self::evaluateCompiled( $number, $rules );
    }

    public static function compile( array $rules ) {
        // We can't use array_map() for this because it generates a warning if
        // there is an exception.
        foreach ( $rules as &$rule ) {
            $rule = CLDRPluralRuleConverter::convert( $rule );
        }
        return $rules;
    }

    public static function evaluateCompiled( $number, array $rules ) {
        // Calculate the values of the operand symbols
        $number = strval( $number );
        if ( !preg_match( '/^ -? ( ([0-9]+) (?: \. ([0-9]+) )? )$/x', $number,  $m ) ) {
            wfDebug( __METHOD__.': invalid number input, returning "other"' );
            return count( $rules );
        }
        if ( !isset( $m[3] ) ) {
            $operandSymbols = array(
                'n' => intval( $m[1] ),
                'i' => intval( $m[1] ),
                'v' => 0,
                'w' => 0,
                'f' => 0,
                't' => 0
            );
        } else {
            $absValStr = $m[1];
            $intStr = $m[2];
            $fracStr = $m[3];
            $operandSymbols = array(
                'n' => floatval( $absValStr ),
                'i' => intval( $intStr ),
                'v' => strlen( $fracStr ),
                'w' => strlen( rtrim( $fracStr, '0' ) ),
                'f' => intval( $fracStr ),
                't' => intval( rtrim( $fracStr, '0' ) ),
            );
        }

        // The compiled form is RPN, with tokens strictly delimited by
        // spaces, so this is a simple RPN evaluator.
        foreach ( $rules as $i => $rule ) {
            $stack = array();
            $zero = ord( '0' );
            $nine = ord( '9' );
            foreach ( StringUtils::explode( ' ', $rule ) as $token ) {
                $ord = ord( $token );
                if ( isset( $operandSymbols[$token] ) ) {
                    $stack[] = $operandSymbols[$token];
                } elseif ( $ord >= $zero && $ord <= $nine ) {
                    $stack[] = intval( $token );
                } else {
                    $right = array_pop( $stack );
                    $left = array_pop( $stack );
                    $result = self::doOperation( $token, $left, $right );
                    $stack[] = $result;
                }
            }
            if ( $stack[0] ) {
                return $i;
            }
        }
        // None of the provided rules match. The number belongs to category
        // 'other', which comes last.
        return count( $rules );
    }

    private static function doOperation( $token, $left, $right ) {
        if ( in_array( $token, array( 'in', 'not-in', 'within', 'not-within' ) ) ) {
            if ( !( $right instanceof CLDRPluralRuleEvaluator_Range ) ) {
                $right = new CLDRPluralRuleEvaluator_Range( $right );
            }
        }
        switch ( $token ) {
            case 'or':
                return $left || $right;
            case 'and':
                return $left && $right;
            case 'is':
                return $left == $right;
            case 'is-not':
                return $left != $right;
            case 'in':
                return $right->isNumberIn( $left );
            case 'not-in':
                return !$right->isNumberIn( $left );
            case 'within':
                return $right->isNumberWithin( $left );
            case 'not-within':
                return !$right->isNumberWithin( $left );
            case 'mod':
                if ( is_int( $left ) ) {
                    return (int)fmod( $left, $right );
                }
                return fmod( $left, $right );
            case ',':
                if ( $left instanceof CLDRPluralRuleEvaluator_Range ) {
                    $range = $left;
                } else {
                    $range = new CLDRPluralRuleEvaluator_Range( $left );
                }
                $range->add( $right );
                return $range;
            case '..':
                return new CLDRPluralRuleEvaluator_Range( $left, $right );
            default:
                throw new CLDRPluralRuleError( "Invalid RPN token" );
        }
    }
}

class CLDRPluralRuleEvaluator_Range {
    public $parts = array();

    function __construct( $start, $end = false ) {
        if ( $end === false ) {
            $this->parts[] = $start;
        } else {
            $this->parts[] = array( $start, $end );
        }
    }

    function isNumberIn( $number, $integerConstraint = true ) {
        foreach ( $this->parts as $part ) {
            if ( is_array( $part ) ) {
                if ( ( !$integerConstraint || floor( $number ) === (float)$number )
                    && $number >= $part[0] && $number <= $part[1] )
                {
                    return true;
                }
            } else {
                if ( $number == $part ) {
                    return true;
                }
            }
        }
        return false;
    }

    function isNumberWithin( $number ) {
        return $this->isNumberIn( $number, false );
    }

    function add( $other ) {
        if ( $other instanceof self ) {
            $this->parts = array_merge( $this->parts, $other->parts );
        } else {
            $this->parts[] = $other;
        }
    }

    function __toString() {
        $s = 'Range(';
        foreach ( $this->parts as $i => $part ) {
            if ( $i ) {
                $s .= ', ';
            }
            if ( is_array( $part ) ) {
                $s .= $part[0] . '..' . $part[1];
            } else {
                $s .= $part;
            }
        }
        $s .= ')';
        return $s;
    }

}

class CLDRPluralRuleConverter {
    public $rule;

    public $pos;

    public $end;

    public $operators = array();

    public $operands = array();

    static $precedence = array(
        'or' => 2,
        'and' => 3,
        'is' => 4,
        'is-not' => 4,
        'in' => 4,
        'not-in' => 4,
        'within' => 4,
        'not-within' => 4,
        'mod' => 5,
        ',' => 6,
        '..' => 7,
    );

    const WHITESPACE_CLASS = " \t\r\n";

    const NUMBER_CLASS = '0123456789';

    const OPERAND_SYMBOLS = 'nivwft';

    const WORD_REGEX = '/[a-zA-Z@]+/A';

    public static function convert( $rule ) {
        $parser = new self( $rule );
        return $parser->doConvert();
    }

    protected function __construct( $rule ) {
        $this->rule = $rule;
        $this->pos = 0;
        $this->end = strlen( $rule );
    }

    protected function doConvert() {
        $expectOperator = true;

        // Iterate through all tokens, saving the operators and operands to a
        // stack per Dijkstra's shunting yard algorithm.
        while ( false !== ( $token = $this->nextToken() ) ) {
            // In this grammar, there are only binary operators, so every valid
            // rule string will alternate between operator and operand tokens.
            $expectOperator = !$expectOperator;

            if ( $token instanceof CLDRPluralRuleConverter_Expression ) {
                // Operand
                if ( $expectOperator ) {
                    $token->error( 'unexpected operand' );
                }
                $this->operands[] = $token;
                continue;
            } else {
                // Operator
                if ( !$expectOperator ) {
                    $token->error( 'unexpected operator' );
                }
                // Resolve higher precedence levels
                $lastOp = end( $this->operators );
                while ( $lastOp && self::$precedence[$token->name] <= self::$precedence[$lastOp->name] ) {
                    $this->doOperation( $lastOp, $this->operands );
                    array_pop( $this->operators );
                    $lastOp = end( $this->operators );
                }
                $this->operators[] = $token;
            }
        }

        // Finish off the stack
        while ( $op = array_pop( $this->operators ) ) {
            $this->doOperation( $op, $this->operands );
        }

        // Make sure the result is sane. The first case is possible for an empty
        // string input, the second should be unreachable.
        if ( !count( $this->operands ) ) {
            $this->error( 'condition expected' );
        } elseif ( count( $this->operands ) > 1 ) {
            $this->error( 'missing operator or too many operands' );
        }

        $value = $this->operands[0];
        if ( $value->type !== 'boolean' ) {
            $this->error( 'the result must have a boolean type' );
        }

        return $this->operands[0]->rpn;
    }

    protected function nextToken() {
        if ( $this->pos >= $this->end ) {
            return false;
        }

        // Whitespace
        $length = strspn( $this->rule, self::WHITESPACE_CLASS, $this->pos );
        $this->pos += $length;

        if ( $this->pos >= $this->end ) {
            return false;
        }

        // Number
        $length = strspn( $this->rule, self::NUMBER_CLASS, $this->pos );
        if ( $length !== 0 ) {
            $token = $this->newNumber( substr( $this->rule, $this->pos, $length ), $this->pos );
            $this->pos += $length;
            return $token;
        }

        // Two-character operators
        $op2 = substr( $this->rule, $this->pos, 2 );
        if ( $op2 === '..' || $op2 === '!=' ) {
            $token = $this->newOperator( $op2, $this->pos, 2 );
            $this->pos += 2;
            return $token;
        }

        // Single-character operators
        $op1 = $this->rule[$this->pos];
        if ( $op1 === ',' || $op1 === '=' || $op1 === '%' ) {
            $token = $this->newOperator( $op1, $this->pos, 1 );
            $this->pos ++;
            return $token;
        }

        // Word
        if ( !preg_match( self::WORD_REGEX, $this->rule, $m, 0, $this->pos ) ) {
            $this->error( 'unexpected character "' . $this->rule[$this->pos] . '"' );
        }
        $word1 = strtolower( $m[0] );
        $word2 = '';
        $nextTokenPos = $this->pos + strlen( $word1 );
        if ( $word1 === 'not' || $word1 === 'is' ) {
            // Look ahead one word
            $nextTokenPos += strspn( $this->rule, self::WHITESPACE_CLASS, $nextTokenPos );
            if ( $nextTokenPos < $this->end
                    && preg_match( self::WORD_REGEX, $this->rule, $m, 0, $nextTokenPos ) )
            {
                $word2 = strtolower( $m[0] );
                $nextTokenPos += strlen( $word2 );
            }
        }

        // Two-word operators like "is not" take precedence over single-word operators like "is"
        if ( $word2 !== '' ) {
            $bothWords = "{$word1}-{$word2}";
            if ( isset( self::$precedence[$bothWords] ) ) {
                $token = $this->newOperator( $bothWords, $this->pos, $nextTokenPos - $this->pos );
                $this->pos = $nextTokenPos;
                return $token;
            }
        }

        // Single-word operators
        if ( isset( self::$precedence[$word1] ) ) {
            $token = $this->newOperator( $word1, $this->pos, strlen( $word1 ) );
            $this->pos += strlen( $word1 );
            return $token;
        }

        // The single-character operand symbols
        if ( strpos( self::OPERAND_SYMBOLS, $word1 ) !== false ) {
            $token = $this->newNumber( $word1, $this->pos );
            $this->pos ++;
            return $token;
        }

        // Samples
        if ( $word1 === '@integer' || $word1 === '@decimal' ) {
            // Samples are like comments, they have no effect on rule evaluation.
            // They run from the first sample indicator to the end of the string.
            $this->pos = $this->end;
            return false;
        }

        $this->error( 'unrecognised word' );
    }

    protected function doOperation( $op ) {
        if ( count( $this->operands ) < 2 ) {
            $op->error( 'missing operand' );
        }
        $right = array_pop( $this->operands );
        $left = array_pop( $this->operands );
        $result = $op->operate( $left, $right );
        $this->operands[] = $result;
    }

    protected function newNumber( $text, $pos ) {
        return new CLDRPluralRuleConverter_Expression( $this, 'number', $text, $pos, strlen( $text ) );
    }

    protected function newOperator( $type, $pos, $length ) {
        return new CLDRPluralRuleConverter_Operator( $this, $type, $pos, $length );
    }

    protected function error( $message ) {
        throw new CLDRPluralRuleError( $message );
    }
}

class CLDRPluralRuleConverter_Fragment {
    public $parser, $pos, $length, $end;

    function __construct( $parser, $pos, $length ) {
        $this->parser = $parser;
        $this->pos = $pos;
        $this->length = $length;
        $this->end = $pos + $length;
    }

    public function error( $message ) {
        $text = $this->getText();
        throw new CLDRPluralRuleError( "$message at position " . ( $this->pos + 1 ) . ": \"$text\"" );
    }

    public function getText() {
        return substr( $this->parser->rule, $this->pos, $this->length );
    }
}

class CLDRPluralRuleConverter_Expression extends CLDRPluralRuleConverter_Fragment {
    public $type, $rpn;

    function __construct( $parser, $type, $rpn, $pos, $length ) {
        parent::__construct( $parser, $pos, $length );
        $this->type = $type;
        $this->rpn = $rpn;
    }

    public function isType( $type ) {
        if ( $type === 'range' && ( $this->type === 'range' || $this->type === 'number' ) ) {
            return true;
        }
        if ( $type === $this->type ) {
            return true;
        }
        return false;
    }
}

class CLDRPluralRuleConverter_Operator extends CLDRPluralRuleConverter_Fragment {
    public $name;

    static $opTypes = array(
        'or' => 'bbb',
        'and' => 'bbb',
        'is' => 'nnb',
        'is-not' => 'nnb',
        'in' => 'nrb',
        'not-in' => 'nrb',
        'within' => 'nrb',
        'not-within' => 'nrb',
        'mod' => 'nnn',
        ',' => 'rrr',
        '..' => 'nnr',
    );

    static $typeSpecMap = array(
        'b' => 'boolean',
        'n' => 'number',
        'r' => 'range',
    );

    static $aliasMap = array(
        '%' => 'mod',
        '!=' => 'not-in',
        '=' => 'in'
    );

    function __construct( $parser, $name, $pos, $length ) {
        parent::__construct( $parser, $pos, $length );
        if ( isset( self::$aliasMap[$name] ) ) {
            $name = self::$aliasMap[$name];
        }
        $this->name = $name;
    }

    public function operate( $left, $right ) {
        $typeSpec = self::$opTypes[$this->name];

        $leftType = self::$typeSpecMap[$typeSpec[0]];
        $rightType = self::$typeSpecMap[$typeSpec[1]];
        $resultType = self::$typeSpecMap[$typeSpec[2]];

        $start = min( $this->pos, $left->pos, $right->pos );
        $end = max( $this->end, $left->end, $right->end );
        $length = $end - $start;

        $newExpr = new CLDRPluralRuleConverter_Expression( $this->parser, $resultType,
            "{$left->rpn} {$right->rpn} {$this->name}",
            $start, $length );

        if ( !$left->isType( $leftType ) ) {
            $newExpr->error( "invalid type for left operand: expected $leftType, got {$left->type}" );
        }

        if ( !$right->isType( $rightType ) ) {
            $newExpr->error( "invalid type for right operand: expected $rightType, got {$right->type}" );
        }
        return $newExpr;
    }
}

class CLDRPluralRuleError extends MWException {
    function __construct( $message ) {
        parent::__construct( 'CLDR plural rule error: ' . $message );
    }
}