Merge "filebackend: cleaned up the FileBackend constructor"

[mediawiki.git] / includes / utils / ConfEditor.php

<?php
/**
 * Configuration file editor.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License along
 * with this program; if not, write to the Free Software Foundation, Inc.,
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
 * http://www.gnu.org/copyleft/gpl.html
 *
 * @file
 */

/**
 * This is a state machine style parser with two internal stacks:
 *   * A next state stack, which determines the state the machine will progress to next
 *   * A path stack, which keeps track of the logical location in the file.
 *
 * Reference grammar:
 *
 * file = T_OPEN_TAG *statement
 * statement = T_VARIABLE "=" expression ";"
 * expression = array / scalar / T_VARIABLE
 * array = T_ARRAY "(" [ element *( "," element ) [ "," ] ] ")"
 * element = assoc-element / expression
 * assoc-element = scalar T_DOUBLE_ARROW expression
 * scalar = T_LNUMBER / T_DNUMBER / T_STRING / T_CONSTANT_ENCAPSED_STRING
 */
class ConfEditor {
        /** The text to parse */
        var $text;

        /** The token array from token_get_all() */
        var $tokens;

        /** The current position in the token array */
        var $pos;

        /** The current 1-based line number */
        var $lineNum;

        /** The current 1-based column number */
        var $colNum;

        /** The current 0-based byte number */
        var $byteNum;

        /** The current ConfEditorToken object */
        var $currentToken;

        /** The previous ConfEditorToken object */
        var $prevToken;

        /**
         * The state machine stack. This is an array of strings where the topmost
         * element will be popped off and become the next parser state.
         */
        var $stateStack;

        /**
         * The path stack is a stack of associative arrays with the following elements:
         *    name              The name of top level of the path
         *    level             The level (number of elements) of the path
         *    startByte         The byte offset of the start of the path
         *    startToken        The token offset of the start
         *    endByte           The byte offset of thee
         *    endToken          The token offset of the end, plus one
         *    valueStartToken   The start token offset of the value part
         *    valueStartByte    The start byte offset of the value part
         *    valueEndToken     The end token offset of the value part, plus one
         *    valueEndByte      The end byte offset of the value part, plus one
         *    nextArrayIndex    The next numeric array index at this level
         *    hasComma          True if the array element ends with a comma
         *    arrowByte         The byte offset of the "=>", or false if there isn't one
         */
        var $pathStack;

        /**
         * The elements of the top of the pathStack for every path encountered, indexed
         * by slash-separated path.
         */
        var $pathInfo;

        /**
         * Next serial number for whitespace placeholder paths (\@extra-N)
         */
        var $serial;

        /**
         * Editor state. This consists of the internal copy/insert operations which
         * are applied to the source string to obtain the destination string.
         */
        var $edits;

        /**
         * Simple entry point for command-line testing
         *
         * @param $text string
         *
         * @return string
         */
        static function test( $text ) {
                try {
                        $ce = new self( $text );
                        $ce->parse();
                } catch ( ConfEditorParseError $e ) {
                        return $e->getMessage() . "\n" . $e->highlight( $text );
                }

                return "OK";
        }

        /**
         * Construct a new parser
         */
        public function __construct( $text ) {
                $this->text = $text;
        }

        /**
         * Edit the text. Returns the edited text.
         * @param array $ops of operations.
         *
         * Operations are given as an associative array, with members:
         *    type:     One of delete, set, append or insert (required)
         *    path:     The path to operate on (required)
         *    key:      The array key to insert/append, with PHP quotes
         *    value:    The value, with PHP quotes
         *
         * delete
         *    Deletes an array element or statement with the specified path.
         *    e.g.
         *        array('type' => 'delete', 'path' => '$foo/bar/baz' )
         *    is equivalent to the runtime PHP code:
         *        unset( $foo['bar']['baz'] );
         *
         * set
         *    Sets the value of an array element. If the element doesn't exist, it
         *    is appended to the array. If it does exist, the value is set, with
         *    comments and indenting preserved.
         *
         * append
         *    Appends a new element to the end of the array. Adds a trailing comma.
         *    e.g.
         *        array( 'type' => 'append', 'path', '$foo/bar',
         *            'key' => 'baz', 'value' => "'x'" )
         *    is like the PHP code:
         *        $foo['bar']['baz'] = 'x';
         *
         * insert
         *    Insert a new element at the start of the array.
         *
         * @throws MWException
         * @return string
         */
        public function edit( $ops ) {
                $this->parse();

                $this->edits = array(
                        array( 'copy', 0, strlen( $this->text ) )
                );
                foreach ( $ops as $op ) {
                        $type = $op['type'];
                        $path = $op['path'];
                        $value = isset( $op['value'] ) ? $op['value'] : null;
                        $key = isset( $op['key'] ) ? $op['key'] : null;

                        switch ( $type ) {
                                case 'delete':
                                        list( $start, $end ) = $this->findDeletionRegion( $path );
                                        $this->replaceSourceRegion( $start, $end, false );
                                        break;
                                case 'set':
                                        if ( isset( $this->pathInfo[$path] ) ) {
                                                list( $start, $end ) = $this->findValueRegion( $path );
                                                $encValue = $value; // var_export( $value, true );
                                                $this->replaceSourceRegion( $start, $end, $encValue );
                                                break;
                                        }
                                        // No existing path, fall through to append
                                        $slashPos = strrpos( $path, '/' );
                                        $key = var_export( substr( $path, $slashPos + 1 ), true );
                                        $path = substr( $path, 0, $slashPos );
                                        // Fall through
                                case 'append':
                                        // Find the last array element
                                        $lastEltPath = $this->findLastArrayElement( $path );
                                        if ( $lastEltPath === false ) {
                                                throw new MWException( "Can't find any element of array \"$path\"" );
                                        }
                                        $lastEltInfo = $this->pathInfo[$lastEltPath];

                                        // Has it got a comma already?
                                        if ( strpos( $lastEltPath, '@extra' ) === false && !$lastEltInfo['hasComma'] ) {
                                                // No comma, insert one after the value region
                                                list( , $end ) = $this->findValueRegion( $lastEltPath );
                                                $this->replaceSourceRegion( $end - 1, $end - 1, ',' );
                                        }

                                        // Make the text to insert
                                        list( $start, $end ) = $this->findDeletionRegion( $lastEltPath );

                                        if ( $key === null ) {
                                                list( $indent, ) = $this->getIndent( $start );
                                                $textToInsert = "$indent$value,";
                                        } else {
                                                list( $indent, $arrowIndent ) =
                                                        $this->getIndent( $start, $key, $lastEltInfo['arrowByte'] );
                                                $textToInsert = "$indent$key$arrowIndent=> $value,";
                                        }
                                        $textToInsert .= ( $indent === false ? ' ' : "\n" );

                                        // Insert the item
                                        $this->replaceSourceRegion( $end, $end, $textToInsert );
                                        break;
                                case 'insert':
                                        // Find first array element
                                        $firstEltPath = $this->findFirstArrayElement( $path );
                                        if ( $firstEltPath === false ) {
                                                throw new MWException( "Can't find array element of \"$path\"" );
                                        }
                                        list( $start, ) = $this->findDeletionRegion( $firstEltPath );
                                        $info = $this->pathInfo[$firstEltPath];

                                        // Make the text to insert
                                        if ( $key === null ) {
                                                list( $indent, ) = $this->getIndent( $start );
                                                $textToInsert = "$indent$value,";
                                        } else {
                                                list( $indent, $arrowIndent ) =
                                                        $this->getIndent( $start, $key, $info['arrowByte'] );
                                                $textToInsert = "$indent$key$arrowIndent=> $value,";
                                        }
                                        $textToInsert .= ( $indent === false ? ' ' : "\n" );

                                        // Insert the item
                                        $this->replaceSourceRegion( $start, $start, $textToInsert );
                                        break;
                                default:
                                        throw new MWException( "Unrecognised operation: \"$type\"" );
                        }
                }

                // Do the edits
                $out = '';
                foreach ( $this->edits as $edit ) {
                        if ( $edit[0] == 'copy' ) {
                                $out .= substr( $this->text, $edit[1], $edit[2] - $edit[1] );
                        } else { // if ( $edit[0] == 'insert' )
                                $out .= $edit[1];
                        }
                }

                // Do a second parse as a sanity check
                $this->text = $out;
                try {
                        $this->parse();
                } catch ( ConfEditorParseError $e ) {
                        throw new MWException(
                                "Sorry, ConfEditor broke the file during editing and it won't parse anymore: " .
                                $e->getMessage() );
                }

                return $out;
        }

        /**
         * Get the variables defined in the text
         * @return array( varname => value )
         */
        function getVars() {
                $vars = array();
                $this->parse();
                foreach ( $this->pathInfo as $path => $data ) {
                        if ( $path[0] != '$' ) {
                                continue;
                        }
                        $trimmedPath = substr( $path, 1 );
                        $name = $data['name'];
                        if ( $name[0] == '@' ) {
                                continue;
                        }
                        if ( $name[0] == '$' ) {
                                $name = substr( $name, 1 );
                        }
                        $parentPath = substr( $trimmedPath, 0,
                                strlen( $trimmedPath ) - strlen( $name ) );
                        if ( substr( $parentPath, -1 ) == '/' ) {
                                $parentPath = substr( $parentPath, 0, -1 );
                        }

                        $value = substr( $this->text, $data['valueStartByte'],
                                $data['valueEndByte'] - $data['valueStartByte']
                        );
                        $this->setVar( $vars, $parentPath, $name,
                                $this->parseScalar( $value ) );
                }

                return $vars;
        }

        /**
         * Set a value in an array, unless it's set already. For instance,
         * setVar( $arr, 'foo/bar', 'baz', 3 ); will set
         * $arr['foo']['bar']['baz'] = 3;
         * @param $array array
         * @param string $path slash-delimited path
         * @param $key mixed Key
         * @param $value mixed Value
         */
        function setVar( &$array, $path, $key, $value ) {
                $pathArr = explode( '/', $path );
                $target =& $array;
                if ( $path !== '' ) {
                        foreach ( $pathArr as $p ) {
                                if ( !isset( $target[$p] ) ) {
                                        $target[$p] = array();
                                }
                                $target =& $target[$p];
                        }
                }
                if ( !isset( $target[$key] ) ) {
                        $target[$key] = $value;
                }
        }

        /**
         * Parse a scalar value in PHP
         * @return mixed Parsed value
         */
        function parseScalar( $str ) {
                if ( $str !== '' && $str[0] == '\'' ) {
                        // Single-quoted string
                        // @todo FIXME: trim() call is due to mystery bug where whitespace gets
                        // appended to the token; without it we ended up reading in the
                        // extra quote on the end!
                        return strtr( substr( trim( $str ), 1, -1 ),
                                array( '\\\'' => '\'', '\\\\' => '\\' ) );
                }
                if ( $str !== '' && $str[0] == '"' ) {
                        // Double-quoted string
                        // @todo FIXME: trim() call is due to mystery bug where whitespace gets
                        // appended to the token; without it we ended up reading in the
                        // extra quote on the end!
                        return stripcslashes( substr( trim( $str ), 1, -1 ) );
                }
                if ( substr( $str, 0, 4 ) == 'true' ) {
                        return true;
                }
                if ( substr( $str, 0, 5 ) == 'false' ) {
                        return false;
                }
                if ( substr( $str, 0, 4 ) == 'null' ) {
                        return null;
                }

                // Must be some kind of numeric value, so let PHP's weak typing
                // be useful for a change
                return $str;
        }

        /**
         * Replace the byte offset region of the source with $newText.
         * Works by adding elements to the $this->edits array.
         */
        function replaceSourceRegion( $start, $end, $newText = false ) {
                // Split all copy operations with a source corresponding to the region
                // in question.
                $newEdits = array();
                foreach ( $this->edits as $edit ) {
                        if ( $edit[0] !== 'copy' ) {
                                $newEdits[] = $edit;
                                continue;
                        }
                        $copyStart = $edit[1];
                        $copyEnd = $edit[2];
                        if ( $start >= $copyEnd || $end <= $copyStart ) {
                                // Outside this region
                                $newEdits[] = $edit;
                                continue;
                        }
                        if ( ( $start < $copyStart && $end > $copyStart )
                                || ( $start < $copyEnd && $end > $copyEnd )
                        ) {
                                throw new MWException( "Overlapping regions found, can't do the edit" );
                        }
                        // Split the copy
                        $newEdits[] = array( 'copy', $copyStart, $start );
                        if ( $newText !== false ) {
                                $newEdits[] = array( 'insert', $newText );
                        }
                        $newEdits[] = array( 'copy', $end, $copyEnd );
                }
                $this->edits = $newEdits;
        }

        /**
         * Finds the source byte region which you would want to delete, if $pathName
         * was to be deleted. Includes the leading spaces and tabs, the trailing line
         * break, and any comments in between.
         * @param $pathName
         * @throws MWException
         * @return array
         */
        function findDeletionRegion( $pathName ) {
                if ( !isset( $this->pathInfo[$pathName] ) ) {
                        throw new MWException( "Can't find path \"$pathName\"" );
                }
                $path = $this->pathInfo[$pathName];
                // Find the start
                $this->firstToken();
                while ( $this->pos != $path['startToken'] ) {
                        $this->nextToken();
                }
                $regionStart = $path['startByte'];
                for ( $offset = -1; $offset >= -$this->pos; $offset-- ) {
                        $token = $this->getTokenAhead( $offset );
                        if ( !$token->isSkip() ) {
                                // If there is other content on the same line, don't move the start point
                                // back, because that will cause the regions to overlap.
                                $regionStart = $path['startByte'];
                                break;
                        }
                        $lfPos = strrpos( $token->text, "\n" );
                        if ( $lfPos === false ) {
                                $regionStart -= strlen( $token->text );
                        } else {
                                // The line start does not include the LF
                                $regionStart -= strlen( $token->text ) - $lfPos - 1;
                                break;
                        }
                }
                // Find the end
                while ( $this->pos != $path['endToken'] ) {
                        $this->nextToken();
                }
                $regionEnd = $path['endByte']; // past the end
                $count = count( $this->tokens );
                for ( $offset = 0; $offset < $count - $this->pos; $offset++ ) {
                        $token = $this->getTokenAhead( $offset );
                        if ( !$token->isSkip() ) {
                                break;
                        }
                        $lfPos = strpos( $token->text, "\n" );
                        if ( $lfPos === false ) {
                                $regionEnd += strlen( $token->text );
                        } else {
                                // This should point past the LF
                                $regionEnd += $lfPos + 1;
                                break;
                        }
                }

                return array( $regionStart, $regionEnd );
        }

        /**
         * Find the byte region in the source corresponding to the value part.
         * This includes the quotes, but does not include the trailing comma
         * or semicolon.
         *
         * The end position is the past-the-end (end + 1) value as per convention.
         * @param $pathName
         * @throws MWException
         * @return array
         */
        function findValueRegion( $pathName ) {
                if ( !isset( $this->pathInfo[$pathName] ) ) {
                        throw new MWException( "Can't find path \"$pathName\"" );
                }
                $path = $this->pathInfo[$pathName];
                if ( $path['valueStartByte'] === false || $path['valueEndByte'] === false ) {
                        throw new MWException( "Can't find value region for path \"$pathName\"" );
                }

                return array( $path['valueStartByte'], $path['valueEndByte'] );
        }

        /**
         * Find the path name of the last element in the array.
         * If the array is empty, this will return the \@extra interstitial element.
         * If the specified path is not found or is not an array, it will return false.
         * @return bool|int|string
         */
        function findLastArrayElement( $path ) {
                // Try for a real element
                $lastEltPath = false;
                foreach ( $this->pathInfo as $candidatePath => $info ) {
                        $part1 = substr( $candidatePath, 0, strlen( $path ) + 1 );
                        $part2 = substr( $candidatePath, strlen( $path ) + 1, 1 );
                        if ( $part2 == '@' ) {
                                // Do nothing
                        } elseif ( $part1 == "$path/" ) {
                                $lastEltPath = $candidatePath;
                        } elseif ( $lastEltPath !== false ) {
                                break;
                        }
                }
                if ( $lastEltPath !== false ) {
                        return $lastEltPath;
                }

                // Try for an interstitial element
                $extraPath = false;
                foreach ( $this->pathInfo as $candidatePath => $info ) {
                        $part1 = substr( $candidatePath, 0, strlen( $path ) + 1 );
                        if ( $part1 == "$path/" ) {
                                $extraPath = $candidatePath;
                        } elseif ( $extraPath !== false ) {
                                break;
                        }
                }

                return $extraPath;
        }

        /**
         * Find the path name of first element in the array.
         * If the array is empty, this will return the \@extra interstitial element.
         * If the specified path is not found or is not an array, it will return false.
         * @return bool|int|string
         */
        function findFirstArrayElement( $path ) {
                // Try for an ordinary element
                foreach ( $this->pathInfo as $candidatePath => $info ) {
                        $part1 = substr( $candidatePath, 0, strlen( $path ) + 1 );
                        $part2 = substr( $candidatePath, strlen( $path ) + 1, 1 );
                        if ( $part1 == "$path/" && $part2 != '@' ) {
                                return $candidatePath;
                        }
                }

                // Try for an interstitial element
                foreach ( $this->pathInfo as $candidatePath => $info ) {
                        $part1 = substr( $candidatePath, 0, strlen( $path ) + 1 );
                        if ( $part1 == "$path/" ) {
                                return $candidatePath;
                        }
                }

                return false;
        }

        /**
         * Get the indent string which sits after a given start position.
         * Returns false if the position is not at the start of the line.
         * @return array
         */
        function getIndent( $pos, $key = false, $arrowPos = false ) {
                $arrowIndent = ' ';
                if ( $pos == 0 || $this->text[$pos - 1] == "\n" ) {
                        $indentLength = strspn( $this->text, " \t", $pos );
                        $indent = substr( $this->text, $pos, $indentLength );
                } else {
                        $indent = false;
                }
                if ( $indent !== false && $arrowPos !== false ) {
                        $arrowIndentLength = $arrowPos - $pos - $indentLength - strlen( $key );
                        if ( $arrowIndentLength > 0 ) {
                                $arrowIndent = str_repeat( ' ', $arrowIndentLength );
                        }
                }

                return array( $indent, $arrowIndent );
        }

        /**
         * Run the parser on the text. Throws an exception if the string does not
         * match our defined subset of PHP syntax.
         */
        public function parse() {
                $this->initParse();
                $this->pushState( 'file' );
                $this->pushPath( '@extra-' . ( $this->serial++ ) );
                $token = $this->firstToken();

                while ( !$token->isEnd() ) {
                        $state = $this->popState();
                        if ( !$state ) {
                                $this->error( 'internal error: empty state stack' );
                        }

                        switch ( $state ) {
                                case 'file':
                                        $this->expect( T_OPEN_TAG );
                                        $token = $this->skipSpace();
                                        if ( $token->isEnd() ) {
                                                break 2;
                                        }
                                        $this->pushState( 'statement', 'file 2' );
                                        break;
                                case 'file 2':
                                        $token = $this->skipSpace();
                                        if ( $token->isEnd() ) {
                                                break 2;
                                        }
                                        $this->pushState( 'statement', 'file 2' );
                                        break;
                                case 'statement':
                                        $token = $this->skipSpace();
                                        if ( !$this->validatePath( $token->text ) ) {
                                                $this->error( "Invalid variable name \"{$token->text}\"" );
                                        }
                                        $this->nextPath( $token->text );
                                        $this->expect( T_VARIABLE );
                                        $this->skipSpace();
                                        $arrayAssign = false;
                                        if ( $this->currentToken()->type == '[' ) {
                                                $this->nextToken();
                                                $token = $this->skipSpace();
                                                if ( !$token->isScalar() ) {
                                                        $this->error( "expected a string or number for the array key" );
                                                }
                                                if ( $token->type == T_CONSTANT_ENCAPSED_STRING ) {
                                                        $text = $this->parseScalar( $token->text );
                                                } else {
                                                        $text = $token->text;
                                                }
                                                if ( !$this->validatePath( $text ) ) {
                                                        $this->error( "Invalid associative array name \"$text\"" );
                                                }
                                                $this->pushPath( $text );
                                                $this->nextToken();
                                                $this->skipSpace();
                                                $this->expect( ']' );
                                                $this->skipSpace();
                                                $arrayAssign = true;
                                        }
                                        $this->expect( '=' );
                                        $this->skipSpace();
                                        $this->startPathValue();
                                        if ( $arrayAssign ) {
                                                $this->pushState( 'expression', 'array assign end' );
                                        } else {
                                                $this->pushState( 'expression', 'statement end' );
                                        }
                                        break;
                                case 'array assign end':
                                case 'statement end':
                                        $this->endPathValue();
                                        if ( $state == 'array assign end' ) {
                                                $this->popPath();
                                        }
                                        $this->skipSpace();
                                        $this->expect( ';' );
                                        $this->nextPath( '@extra-' . ( $this->serial++ ) );
                                        break;
                                case 'expression':
                                        $token = $this->skipSpace();
                                        if ( $token->type == T_ARRAY ) {
                                                $this->pushState( 'array' );
                                        } elseif ( $token->isScalar() ) {
                                                $this->nextToken();
                                        } elseif ( $token->type == T_VARIABLE ) {
                                                $this->nextToken();
                                        } else {
                                                $this->error( "expected simple expression" );
                                        }
                                        break;
                                case 'array':
                                        $this->skipSpace();
                                        $this->expect( T_ARRAY );
                                        $this->skipSpace();
                                        $this->expect( '(' );
                                        $this->skipSpace();
                                        $this->pushPath( '@extra-' . ( $this->serial++ ) );
                                        if ( $this->isAhead( ')' ) ) {
                                                // Empty array
                                                $this->pushState( 'array end' );
                                        } else {
                                                $this->pushState( 'element', 'array end' );
                                        }
                                        break;
                                case 'array end':
                                        $this->skipSpace();
                                        $this->popPath();
                                        $this->expect( ')' );
                                        break;
                                case 'element':
                                        $token = $this->skipSpace();
                                        // Look ahead to find the double arrow
                                        if ( $token->isScalar() && $this->isAhead( T_DOUBLE_ARROW, 1 ) ) {
                                                // Found associative element
                                                $this->pushState( 'assoc-element', 'element end' );
                                        } else {
                                                // Not associative
                                                $this->nextPath( '@next' );
                                                $this->startPathValue();
                                                $this->pushState( 'expression', 'element end' );
                                        }
                                        break;
                                case 'element end':
                                        $token = $this->skipSpace();
                                        if ( $token->type == ',' ) {
                                                $this->endPathValue();
                                                $this->markComma();
                                                $this->nextToken();
                                                $this->nextPath( '@extra-' . ( $this->serial++ ) );
                                                // Look ahead to find ending bracket
                                                if ( $this->isAhead( ")" ) ) {
                                                        // Found ending bracket, no continuation
                                                        $this->skipSpace();
                                                } else {
                                                        // No ending bracket, continue to next element
                                                        $this->pushState( 'element' );
                                                }
                                        } elseif ( $token->type == ')' ) {
                                                // End array
                                                $this->endPathValue();
                                        } else {
                                                $this->error( "expected the next array element or the end of the array" );
                                        }
                                        break;
                                case 'assoc-element':
                                        $token = $this->skipSpace();
                                        if ( !$token->isScalar() ) {
                                                $this->error( "expected a string or number for the array key" );
                                        }
                                        if ( $token->type == T_CONSTANT_ENCAPSED_STRING ) {
                                                $text = $this->parseScalar( $token->text );
                                        } else {
                                                $text = $token->text;
                                        }
                                        if ( !$this->validatePath( $text ) ) {
                                                $this->error( "Invalid associative array name \"$text\"" );
                                        }
                                        $this->nextPath( $text );
                                        $this->nextToken();
                                        $this->skipSpace();
                                        $this->markArrow();
                                        $this->expect( T_DOUBLE_ARROW );
                                        $this->skipSpace();
                                        $this->startPathValue();
                                        $this->pushState( 'expression' );
                                        break;
                        }
                }
                if ( count( $this->stateStack ) ) {
                        $this->error( 'unexpected end of file' );
                }
                $this->popPath();
        }

        /**
         * Initialise a parse.
         */
        protected function initParse() {
                $this->tokens = token_get_all( $this->text );
                $this->stateStack = array();
                $this->pathStack = array();
                $this->firstToken();
                $this->pathInfo = array();
                $this->serial = 1;
        }

        /**
         * Set the parse position. Do not call this except from firstToken() and
         * nextToken(), there is more to update than just the position.
         */
        protected function setPos( $pos ) {
                $this->pos = $pos;
                if ( $this->pos >= count( $this->tokens ) ) {
                        $this->currentToken = ConfEditorToken::newEnd();
                } else {
                        $this->currentToken = $this->newTokenObj( $this->tokens[$this->pos] );
                }

                return $this->currentToken;
        }

        /**
         * Create a ConfEditorToken from an element of token_get_all()
         * @return ConfEditorToken
         */
        function newTokenObj( $internalToken ) {
                if ( is_array( $internalToken ) ) {
                        return new ConfEditorToken( $internalToken[0], $internalToken[1] );
                } else {
                        return new ConfEditorToken( $internalToken, $internalToken );
                }
        }

        /**
         * Reset the parse position
         */
        function firstToken() {
                $this->setPos( 0 );
                $this->prevToken = ConfEditorToken::newEnd();
                $this->lineNum = 1;
                $this->colNum = 1;
                $this->byteNum = 0;

                return $this->currentToken;
        }

        /**
         * Get the current token
         */
        function currentToken() {
                return $this->currentToken;
        }

        /**
         * Advance the current position and return the resulting next token
         */
        function nextToken() {
                if ( $this->currentToken ) {
                        $text = $this->currentToken->text;
                        $lfCount = substr_count( $text, "\n" );
                        if ( $lfCount ) {
                                $this->lineNum += $lfCount;
                                $this->colNum = strlen( $text ) - strrpos( $text, "\n" );
                        } else {
                                $this->colNum += strlen( $text );
                        }
                        $this->byteNum += strlen( $text );
                }
                $this->prevToken = $this->currentToken;
                $this->setPos( $this->pos + 1 );

                return $this->currentToken;
        }

        /**
         * Get the token $offset steps ahead of the current position.
         * $offset may be negative, to get tokens behind the current position.
         * @return ConfEditorToken
         */
        function getTokenAhead( $offset ) {
                $pos = $this->pos + $offset;
                if ( $pos >= count( $this->tokens ) || $pos < 0 ) {
                        return ConfEditorToken::newEnd();
                } else {
                        return $this->newTokenObj( $this->tokens[$pos] );
                }
        }

        /**
         * Advances the current position past any whitespace or comments
         */
        function skipSpace() {
                while ( $this->currentToken && $this->currentToken->isSkip() ) {
                        $this->nextToken();
                }

                return $this->currentToken;
        }

        /**
         * Throws an error if the current token is not of the given type, and
         * then advances to the next position.
         */
        function expect( $type ) {
                if ( $this->currentToken && $this->currentToken->type == $type ) {
                        return $this->nextToken();
                } else {
                        $this->error( "expected " . $this->getTypeName( $type ) .
                                ", got " . $this->getTypeName( $this->currentToken->type ) );
                }
        }

        /**
         * Push a state or two on to the state stack.
         */
        function pushState( $nextState, $stateAfterThat = null ) {
                if ( $stateAfterThat !== null ) {
                        $this->stateStack[] = $stateAfterThat;
                }
                $this->stateStack[] = $nextState;
        }

        /**
         * Pop a state from the state stack.
         * @return mixed
         */
        function popState() {
                return array_pop( $this->stateStack );
        }

        /**
         * Returns true if the user input path is valid.
         * This exists to allow "/" and "@" to be reserved for string path keys
         * @return bool
         */
        function validatePath( $path ) {
                return strpos( $path, '/' ) === false && substr( $path, 0, 1 ) != '@';
        }

        /**
         * Internal function to update some things at the end of a path region. Do
         * not call except from popPath() or nextPath().
         */
        function endPath() {
                $key = '';
                foreach ( $this->pathStack as $pathInfo ) {
                        if ( $key !== '' ) {
                                $key .= '/';
                        }
                        $key .= $pathInfo['name'];
                }
                $pathInfo['endByte'] = $this->byteNum;
                $pathInfo['endToken'] = $this->pos;
                $this->pathInfo[$key] = $pathInfo;
        }

        /**
         * Go up to a new path level, for example at the start of an array.
         */
        function pushPath( $path ) {
                $this->pathStack[] = array(
                        'name' => $path,
                        'level' => count( $this->pathStack ) + 1,
                        'startByte' => $this->byteNum,
                        'startToken' => $this->pos,
                        'valueStartToken' => false,
                        'valueStartByte' => false,
                        'valueEndToken' => false,
                        'valueEndByte' => false,
                        'nextArrayIndex' => 0,
                        'hasComma' => false,
                        'arrowByte' => false
                );
        }

        /**
         * Go down a path level, for example at the end of an array.
         */
        function popPath() {
                $this->endPath();
                array_pop( $this->pathStack );
        }

        /**
         * Go to the next path on the same level. This ends the current path and
         * starts a new one. If $path is \@next, the new path is set to the next
         * numeric array element.
         */
        function nextPath( $path ) {
                $this->endPath();
                $i = count( $this->pathStack ) - 1;
                if ( $path == '@next' ) {
                        $nextArrayIndex =& $this->pathStack[$i]['nextArrayIndex'];
                        $this->pathStack[$i]['name'] = $nextArrayIndex;
                        $nextArrayIndex++;
                } else {
                        $this->pathStack[$i]['name'] = $path;
                }
                $this->pathStack[$i] =
                        array(
                                'startByte' => $this->byteNum,
                                'startToken' => $this->pos,
                                'valueStartToken' => false,
                                'valueStartByte' => false,
                                'valueEndToken' => false,
                                'valueEndByte' => false,
                                'hasComma' => false,
                                'arrowByte' => false,
                        ) + $this->pathStack[$i];
        }

        /**
         * Mark the start of the value part of a path.
         */
        function startPathValue() {
                $path =& $this->pathStack[count( $this->pathStack ) - 1];
                $path['valueStartToken'] = $this->pos;
                $path['valueStartByte'] = $this->byteNum;
        }

        /**
         * Mark the end of the value part of a path.
         */
        function endPathValue() {
                $path =& $this->pathStack[count( $this->pathStack ) - 1];
                $path['valueEndToken'] = $this->pos;
                $path['valueEndByte'] = $this->byteNum;
        }

        /**
         * Mark the comma separator in an array element
         */
        function markComma() {
                $path =& $this->pathStack[count( $this->pathStack ) - 1];
                $path['hasComma'] = true;
        }

        /**
         * Mark the arrow separator in an associative array element
         */
        function markArrow() {
                $path =& $this->pathStack[count( $this->pathStack ) - 1];
                $path['arrowByte'] = $this->byteNum;
        }

        /**
         * Generate a parse error
         */
        function error( $msg ) {
                throw new ConfEditorParseError( $this, $msg );
        }

        /**
         * Get a readable name for the given token type.
         * @return string
         */
        function getTypeName( $type ) {
                if ( is_int( $type ) ) {
                        return token_name( $type );
                } else {
                        return "\"$type\"";
                }
        }

        /**
         * Looks ahead to see if the given type is the next token type, starting
         * from the current position plus the given offset. Skips any intervening
         * whitespace.
         * @return bool
         */
        function isAhead( $type, $offset = 0 ) {
                $ahead = $offset;
                $token = $this->getTokenAhead( $offset );
                while ( !$token->isEnd() ) {
                        if ( $token->isSkip() ) {
                                $ahead++;
                                $token = $this->getTokenAhead( $ahead );
                                continue;
                        } elseif ( $token->type == $type ) {
                                // Found the type
                                return true;
                        } else {
                                // Not found
                                return false;
                        }
                }

                return false;
        }

        /**
         * Get the previous token object
         */
        function prevToken() {
                return $this->prevToken;
        }

        /**
         * Echo a reasonably readable representation of the tokenizer array.
         */
        function dumpTokens() {
                $out = '';
                foreach ( $this->tokens as $token ) {
                        $obj = $this->newTokenObj( $token );
                        $out .= sprintf( "%-28s %s\n",
                                $this->getTypeName( $obj->type ),
                                addcslashes( $obj->text, "\0..\37" ) );
                }
                echo "<pre>" . htmlspecialchars( $out ) . "</pre>";
        }
}

/**
 * Exception class for parse errors
 */
class ConfEditorParseError extends MWException {
        var $lineNum, $colNum;

        function __construct( $editor, $msg ) {
                $this->lineNum = $editor->lineNum;
                $this->colNum = $editor->colNum;
                parent::__construct( "Parse error on line {$editor->lineNum} " .
                        "col {$editor->colNum}: $msg" );
        }

        function highlight( $text ) {
                $lines = StringUtils::explode( "\n", $text );
                foreach ( $lines as $lineNum => $line ) {
                        if ( $lineNum == $this->lineNum - 1 ) {
                                return "$line\n" . str_repeat( ' ', $this->colNum - 1 ) . "^\n";
                        }
                }

                return '';
        }
}

/**
 * Class to wrap a token from the tokenizer.
 */
class ConfEditorToken {
        var $type, $text;

        static $scalarTypes = array( T_LNUMBER, T_DNUMBER, T_STRING, T_CONSTANT_ENCAPSED_STRING );
        static $skipTypes = array( T_WHITESPACE, T_COMMENT, T_DOC_COMMENT );

        static function newEnd() {
                return new self( 'END', '' );
        }

        function __construct( $type, $text ) {
                $this->type = $type;
                $this->text = $text;
        }

        function isSkip() {
                return in_array( $this->type, self::$skipTypes );
        }

        function isScalar() {
                return in_array( $this->type, self::$scalarTypes );
        }

        function isEnd() {
                return $this->type == 'END';
        }
}