Tokens.php

<?php

declare(strict_types=1);

/*
 * This file is part of PHP CS Fixer.
 *
 * (c) Fabien Potencier <fabien@symfony.com>
 *     Dariusz Rumiński <dariusz.ruminski@gmail.com>
 *
 * This source file is subject to the MIT license that is bundled
 * with this source code in the file LICENSE.
 */

namespace PhpCsFixer\Tokenizer;

use PhpCsFixer\Console\Application;
use PhpCsFixer\Preg;
use PhpCsFixer\Tokenizer\Analyzer\Analysis\NamespaceAnalysis;
use PhpCsFixer\Tokenizer\Analyzer\NamespacesAnalyzer;
use PhpCsFixer\Utils;

/**
 * Collection of code tokens.
 *
 * Its role is to provide the ability to manage collection and navigate through it.
 *
 * As a token prototype you should understand a single element generated by token_get_all.
 *
 * @author Dariusz Rumiński <dariusz.ruminski@gmail.com>
 *
 * @extends \SplFixedArray<Token>
 *
 * @method Token offsetGet($offset)
 *
 * @final
 */
class Tokens extends \SplFixedArray
{
    public const BLOCK_TYPE_PARENTHESIS_BRACE = 1;
    public const BLOCK_TYPE_CURLY_BRACE = 2;
    public const BLOCK_TYPE_INDEX_SQUARE_BRACE = 3;
    public const BLOCK_TYPE_ARRAY_SQUARE_BRACE = 4;
    public const BLOCK_TYPE_DYNAMIC_PROP_BRACE = 5;
    public const BLOCK_TYPE_DYNAMIC_VAR_BRACE = 6;
    public const BLOCK_TYPE_ARRAY_INDEX_CURLY_BRACE = 7;
    public const BLOCK_TYPE_GROUP_IMPORT_BRACE = 8;
    public const BLOCK_TYPE_DESTRUCTURING_SQUARE_BRACE = 9;
    public const BLOCK_TYPE_BRACE_CLASS_INSTANTIATION = 10;
    public const BLOCK_TYPE_ATTRIBUTE = 11;
    public const BLOCK_TYPE_DISJUNCTIVE_NORMAL_FORM_TYPE_PARENTHESIS = 12;
    public const BLOCK_TYPE_DYNAMIC_CLASS_CONSTANT_FETCH_CURLY_BRACE = 13;

    private const NON_MEANINGFUL_TOKENS = [T_WHITESPACE, T_COMMENT, T_DOC_COMMENT];
    private const DIRECTION_PREV = -1;
    private const DIRECTION_NEXT = 1;

    /**
     * Static class cache.
     *
     * @var array<non-empty-string, self>
     */
    private static array $cache = [];

    /**
     * Cache of block starts. Any change in collection will invalidate it.
     *
     * @var array<int, int>
     */
    private array $blockStartCache = [];

    /**
     * Cache of block ends. Any change in collection will invalidate it.
     *
     * @var array<int, int>
     */
    private array $blockEndCache = [];

    /**
     * A MD5 hash of the code string.
     *
     * @var ?non-empty-string
     */
    private ?string $codeHash = null;

    /**
     * Flag is collection was changed.
     *
     * It doesn't know about change of collection's items. To check it run `isChanged` method.
     */
    private bool $changed = false;

    /**
     * Set of found token kinds.
     *
     * When the token kind is present in this set it means that given token kind
     * was ever seen inside the collection (but may not be part of it any longer).
     * The key is token kind and the value is always true.
     *
     * @var array<int|non-empty-string, int>
     */
    private array $foundTokenKinds = [];

    /**
     * @var null|list<NamespaceAnalysis>
     */
    private ?array $namespaceDeclarations = null;

    /**
     * Clone tokens collection.
     */
    public function __clone()
    {
        foreach ($this as $key => $val) {
            $this[$key] = clone $val;
        }
    }

    /**
     * Clear cache - one position or all of them.
     *
     * @param null|non-empty-string $key position to clear, when null clear all
     */
    public static function clearCache(?string $key = null): void
    {
        if (null === $key) {
            self::$cache = [];

            return;
        }

        unset(self::$cache[$key]);
    }

    /**
     * Detect type of block.
     *
     * @return null|array{type: self::BLOCK_TYPE_*, isStart: bool}
     */
    public static function detectBlockType(Token $token): ?array
    {
        static $blockEdgeKinds = null;

        if (null === $blockEdgeKinds) {
            $blockEdgeKinds = [];
            foreach (self::getBlockEdgeDefinitions() as $type => $definition) {
                $blockEdgeKinds[
                    \is_string($definition['start']) ? $definition['start'] : $definition['start'][0]
                ] = ['type' => $type, 'isStart' => true];
                $blockEdgeKinds[
                    \is_string($definition['end']) ? $definition['end'] : $definition['end'][0]
                ] = ['type' => $type, 'isStart' => false];
            }
        }

        // inlined extractTokenKind() call on the hot path
        /** @var int|non-empty-string */
        $tokenKind = $token->isArray() ? $token->getId() : $token->getContent();

        return $blockEdgeKinds[$tokenKind] ?? null;
    }

    /**
     * Create token collection from array.
     *
     * @param array<int, Token> $array       the array to import
     * @param ?bool             $saveIndices save the numeric indices used in the original array, default is yes
     */
    public static function fromArray($array, $saveIndices = null): self
    {
        $tokens = new self(\count($array));

        if (false !== $saveIndices && !array_is_list($array)) {
            Utils::triggerDeprecation(new \InvalidArgumentException(sprintf(
                'Parameter "array" should be a list. This will be enforced in version %d.0.',
                Application::getMajorVersion() + 1
            )));

            foreach ($array as $key => $val) {
                $tokens[$key] = $val;
            }
        } else {
            $index = 0;
            foreach ($array as $val) {
                $tokens[$index++] = $val;
            }
        }

        $tokens->generateCode(); // regenerate code to calculate code hash
        $tokens->clearChanged();

        return $tokens;
    }

    /**
     * Create token collection directly from code.
     *
     * @param string $code PHP code
     */
    public static function fromCode(string $code): self
    {
        $codeHash = self::calculateCodeHash($code);

        if (self::hasCache($codeHash)) {
            $tokens = self::getCache($codeHash);

            // generate the code to recalculate the hash
            $tokens->generateCode();

            if ($codeHash === $tokens->codeHash) {
                $tokens->clearEmptyTokens();
                $tokens->clearChanged();

                return $tokens;
            }
        }

        $tokens = new self();
        $tokens->setCode($code);
        $tokens->clearChanged();

        return $tokens;
    }

    /**
     * @return array<self::BLOCK_TYPE_*, array{start: array{int, string}|string, end: array{int, string}|string}>
     */
    public static function getBlockEdgeDefinitions(): array
    {
        static $definitions = null;
        if (null === $definitions) {
            $definitions = [
                self::BLOCK_TYPE_CURLY_BRACE => [
                    'start' => '{',
                    'end' => '}',
                ],
                self::BLOCK_TYPE_PARENTHESIS_BRACE => [
                    'start' => '(',
                    'end' => ')',
                ],
                self::BLOCK_TYPE_INDEX_SQUARE_BRACE => [
                    'start' => '[',
                    'end' => ']',
                ],
                self::BLOCK_TYPE_ARRAY_SQUARE_BRACE => [
                    'start' => [CT::T_ARRAY_SQUARE_BRACE_OPEN, '['],
                    'end' => [CT::T_ARRAY_SQUARE_BRACE_CLOSE, ']'],
                ],
                self::BLOCK_TYPE_DYNAMIC_PROP_BRACE => [
                    'start' => [CT::T_DYNAMIC_PROP_BRACE_OPEN, '{'],
                    'end' => [CT::T_DYNAMIC_PROP_BRACE_CLOSE, '}'],
                ],
                self::BLOCK_TYPE_DYNAMIC_VAR_BRACE => [
                    'start' => [CT::T_DYNAMIC_VAR_BRACE_OPEN, '{'],
                    'end' => [CT::T_DYNAMIC_VAR_BRACE_CLOSE, '}'],
                ],
                self::BLOCK_TYPE_ARRAY_INDEX_CURLY_BRACE => [
                    'start' => [CT::T_ARRAY_INDEX_CURLY_BRACE_OPEN, '{'],
                    'end' => [CT::T_ARRAY_INDEX_CURLY_BRACE_CLOSE, '}'],
                ],
                self::BLOCK_TYPE_GROUP_IMPORT_BRACE => [
                    'start' => [CT::T_GROUP_IMPORT_BRACE_OPEN, '{'],
                    'end' => [CT::T_GROUP_IMPORT_BRACE_CLOSE, '}'],
                ],
                self::BLOCK_TYPE_DESTRUCTURING_SQUARE_BRACE => [
                    'start' => [CT::T_DESTRUCTURING_SQUARE_BRACE_OPEN, '['],
                    'end' => [CT::T_DESTRUCTURING_SQUARE_BRACE_CLOSE, ']'],
                ],
                self::BLOCK_TYPE_BRACE_CLASS_INSTANTIATION => [
                    'start' => [CT::T_BRACE_CLASS_INSTANTIATION_OPEN, '('],
                    'end' => [CT::T_BRACE_CLASS_INSTANTIATION_CLOSE, ')'],
                ],
                self::BLOCK_TYPE_DISJUNCTIVE_NORMAL_FORM_TYPE_PARENTHESIS => [
                    'start' => [CT::T_DISJUNCTIVE_NORMAL_FORM_TYPE_PARENTHESIS_OPEN, '('],
                    'end' => [CT::T_DISJUNCTIVE_NORMAL_FORM_TYPE_PARENTHESIS_CLOSE, ')'],
                ],
                self::BLOCK_TYPE_DYNAMIC_CLASS_CONSTANT_FETCH_CURLY_BRACE => [
                    'start' => [CT::T_DYNAMIC_CLASS_CONSTANT_FETCH_CURLY_BRACE_OPEN, '{'],
                    'end' => [CT::T_DYNAMIC_CLASS_CONSTANT_FETCH_CURLY_BRACE_CLOSE, '}'],
                ],
            ];

            // @TODO: drop condition when PHP 8.0+ is required
            if (\defined('T_ATTRIBUTE')) {
                $definitions[self::BLOCK_TYPE_ATTRIBUTE] = [
                    'start' => [T_ATTRIBUTE, '#['],
                    'end' => [CT::T_ATTRIBUTE_CLOSE, ']'],
                ];
            }
        }

        return $definitions;
    }

    /**
     * Set new size of collection.
     *
     * @param int $size
     */
    #[\ReturnTypeWillChange]
    public function setSize($size): bool
    {
        if (\count($this) !== $size) {
            $this->changed = true;
            $this->namespaceDeclarations = null;

            return parent::setSize($size);
        }

        return true;
    }

    /**
     * Unset collection item.
     *
     * @param int $index
     */
    public function offsetUnset($index): void
    {
        if (\count($this) - 1 !== $index) {
            Utils::triggerDeprecation(new \InvalidArgumentException(sprintf(
                'Tokens should be a list - only the last index can be unset. This will be enforced in version %d.0.',
                Application::getMajorVersion() + 1
            )));
        }

        if (isset($this[$index])) {
            if (isset($this->blockStartCache[$index])) {
                unset($this->blockEndCache[$this->blockStartCache[$index]], $this->blockStartCache[$index]);
            }
            if (isset($this->blockEndCache[$index])) {
                unset($this->blockStartCache[$this->blockEndCache[$index]], $this->blockEndCache[$index]);
            }

            $this->unregisterFoundToken($this[$index]);

            $this->changed = true;
            $this->namespaceDeclarations = null;
        }

        parent::offsetUnset($index);
    }

    /**
     * Set collection item.
     *
     * Warning! `$newval` must not be typehinted to be compatible with `ArrayAccess::offsetSet` method.
     *
     * @param int   $index
     * @param Token $newval
     */
    public function offsetSet($index, $newval): void
    {
        if (0 > $index || \count($this) <= $index) {
            Utils::triggerDeprecation(new \InvalidArgumentException(sprintf(
                'Tokens should be a list - index must be within the existing range. This will be enforced in version %d.0.',
                Application::getMajorVersion() + 1
            )));
        }

        if (!isset($this[$index]) || !$this[$index]->equals($newval)) {
            if (isset($this[$index])) {
                if (isset($this->blockStartCache[$index])) {
                    unset($this->blockEndCache[$this->blockStartCache[$index]], $this->blockStartCache[$index]);
                }
                if (isset($this->blockEndCache[$index])) {
                    unset($this->blockStartCache[$this->blockEndCache[$index]], $this->blockEndCache[$index]);
                }

                $this->unregisterFoundToken($this[$index]);
            }

            $this->changed = true;
            $this->namespaceDeclarations = null;

            $this->registerFoundToken($newval);
        }

        parent::offsetSet($index, $newval);
    }

    /**
     * Clear internal flag if collection was changed and flag for all collection's items.
     */
    public function clearChanged(): void
    {
        $this->changed = false;
    }

    /**
     * Clear empty tokens.
     *
     * Empty tokens can occur e.g. after calling clear on item of collection.
     */
    public function clearEmptyTokens(): void
    {
        $limit = \count($this);

        for ($index = 0; $index < $limit; ++$index) {
            if ($this->isEmptyAt($index)) {
                break;
            }
        }

        // no empty token found, therefore there is no need to override collection
        if ($limit === $index) {
            return;
        }

        for ($count = $index; $index < $limit; ++$index) {
            if (!$this->isEmptyAt($index)) {
                // use directly for speed, skip the register of token kinds found etc.
                parent::offsetSet($count++, $this[$index]);
            }
        }

        // should already be true
        if (!$this->changed) {
            // must never happen
            throw new \LogicException('Unexpected non-changed collection with _EMPTY_ Tokens. Fix the code!');
        }

        // we are moving the tokens, we need to clear the index-based Cache
        $this->namespaceDeclarations = null;
        $this->blockStartCache = [];
        $this->blockEndCache = [];

        $this->setSize($count);
    }

    /**
     * Ensure that on given index is a whitespace with given kind.
     *
     * If there is a whitespace then it's content will be modified.
     * If not - the new Token will be added.
     *
     * @param int    $index       index
     * @param int    $indexOffset index offset for Token insertion
     * @param string $whitespace  whitespace to set
     *
     * @return bool if new Token was added
     */
    public function ensureWhitespaceAtIndex(int $index, int $indexOffset, string $whitespace): bool
    {
        $removeLastCommentLine = static function (self $tokens, int $index, int $indexOffset, string $whitespace): string {
            $token = $tokens[$index];

            if (1 === $indexOffset && $token->isGivenKind(T_OPEN_TAG)) {
                if (str_starts_with($whitespace, "\r\n")) {
                    $tokens[$index] = new Token([T_OPEN_TAG, rtrim($token->getContent())."\r\n"]);

                    return \strlen($whitespace) > 2 // @TODO: can be removed on PHP 8; https://php.net/manual/en/function.substr.php
                        ? substr($whitespace, 2)
                        : '';
                }

                $tokens[$index] = new Token([T_OPEN_TAG, rtrim($token->getContent()).$whitespace[0]]);

                return \strlen($whitespace) > 1 // @TODO: can be removed on PHP 8; https://php.net/manual/en/function.substr.php
                    ? substr($whitespace, 1)
                    : '';
            }

            return $whitespace;
        };

        if ($this[$index]->isWhitespace()) {
            $whitespace = $removeLastCommentLine($this, $index - 1, $indexOffset, $whitespace);

            if ('' === $whitespace) {
                $this->clearAt($index);
            } else {
                $this[$index] = new Token([T_WHITESPACE, $whitespace]);
            }

            return false;
        }

        $whitespace = $removeLastCommentLine($this, $index, $indexOffset, $whitespace);

        if ('' === $whitespace) {
            return false;
        }

        $this->insertAt(
            $index + $indexOffset,
            [new Token([T_WHITESPACE, $whitespace])]
        );

        return true;
    }

    /**
     * @param self::BLOCK_TYPE_* $type        type of block
     * @param int                $searchIndex index of opening brace
     *
     * @return int<0, max> index of closing brace
     */
    public function findBlockEnd(int $type, int $searchIndex): int
    {
        return $this->findOppositeBlockEdge($type, $searchIndex, true);
    }

    /**
     * @param self::BLOCK_TYPE_* $type        type of block
     * @param int                $searchIndex index of closing brace
     *
     * @return int<0, max> index of opening brace
     */
    public function findBlockStart(int $type, int $searchIndex): int
    {
        return $this->findOppositeBlockEdge($type, $searchIndex, false);
    }

    /**
     * @param int|non-empty-list<int> $possibleKind kind or array of kinds
     * @param int                     $start        optional offset
     * @param null|int                $end          optional limit
     *
     * @return ($possibleKind is int ? array<int<0, max>, Token> : array<int, array<int<0, max>, Token>>)
     */
    public function findGivenKind($possibleKind, int $start = 0, ?int $end = null): array
    {
        if (null === $end) {
            $end = \count($this);
        }

        $elements = [];
        $possibleKinds = (array) $possibleKind;

        foreach ($possibleKinds as $kind) {
            $elements[$kind] = [];
        }

        $possibleKinds = array_filter($possibleKinds, fn ($kind): bool => $this->isTokenKindFound($kind));

        if (\count($possibleKinds) > 0) {
            for ($i = $start; $i < $end; ++$i) {
                $token = $this[$i];
                if ($token->isGivenKind($possibleKinds)) {
                    $elements[$token->getId()][$i] = $token;
                }
            }
        }

        return \is_array($possibleKind) ? $elements : $elements[$possibleKind];
    }

    public function generateCode(): string
    {
        $code = $this->generatePartialCode(0, \count($this) - 1);
        $this->changeCodeHash(self::calculateCodeHash($code));

        return $code;
    }

    /**
     * Generate code from tokens between given indices.
     *
     * @param int $start start index
     * @param int $end   end index
     */
    public function generatePartialCode(int $start, int $end): string
    {
        $code = '';

        for ($i = $start; $i <= $end; ++$i) {
            $code .= $this[$i]->getContent();
        }

        return $code;
    }

    /**
     * Get hash of code.
     */
    public function getCodeHash(): string
    {
        return $this->codeHash;
    }

    /**
     * Get index for closest next token which is non whitespace.
     *
     * This method is shorthand for getNonWhitespaceSibling method.
     *
     * @param int         $index       token index
     * @param null|string $whitespaces whitespaces characters for Token::isWhitespace
     */
    public function getNextNonWhitespace(int $index, ?string $whitespaces = null): ?int
    {
        return $this->getNonWhitespaceSibling($index, self::DIRECTION_NEXT, $whitespaces);
    }

    /**
     * Get index for closest next token of given kind.
     *
     * This method is shorthand for getTokenOfKindSibling method.
     *
     * @param int                           $index         token index
     * @param list<array{int}|string|Token> $tokens        possible tokens
     * @param bool                          $caseSensitive perform a case sensitive comparison
     */
    public function getNextTokenOfKind(int $index, array $tokens = [], bool $caseSensitive = true): ?int
    {
        return $this->getTokenOfKindSibling($index, self::DIRECTION_NEXT, $tokens, $caseSensitive);
    }

    /**
     * Get index for closest sibling token which is non whitespace.
     *
     * @param int         $index       token index
     * @param -1|1        $direction
     * @param null|string $whitespaces whitespaces characters for Token::isWhitespace
     */
    public function getNonWhitespaceSibling(int $index, int $direction, ?string $whitespaces = null): ?int
    {
        while (true) {
            $index += $direction;
            if (!$this->offsetExists($index)) {
                return null;
            }

            if (!$this[$index]->isWhitespace($whitespaces)) {
                return $index;
            }
        }
    }

    /**
     * Get index for closest previous token which is non whitespace.
     *
     * This method is shorthand for getNonWhitespaceSibling method.
     *
     * @param int         $index       token index
     * @param null|string $whitespaces whitespaces characters for Token::isWhitespace
     */
    public function getPrevNonWhitespace(int $index, ?string $whitespaces = null): ?int
    {
        return $this->getNonWhitespaceSibling($index, self::DIRECTION_PREV, $whitespaces);
    }

    /**
     * Get index for closest previous token of given kind.
     * This method is shorthand for getTokenOfKindSibling method.
     *
     * @param int                           $index         token index
     * @param list<array{int}|string|Token> $tokens        possible tokens
     * @param bool                          $caseSensitive perform a case sensitive comparison
     */
    public function getPrevTokenOfKind(int $index, array $tokens = [], bool $caseSensitive = true): ?int
    {
        return $this->getTokenOfKindSibling($index, self::DIRECTION_PREV, $tokens, $caseSensitive);
    }

    /**
     * Get index for closest sibling token of given kind.
     *
     * @param int                           $index         token index
     * @param -1|1                          $direction
     * @param list<array{int}|string|Token> $tokens        possible tokens
     * @param bool                          $caseSensitive perform a case sensitive comparison
     */
    public function getTokenOfKindSibling(int $index, int $direction, array $tokens = [], bool $caseSensitive = true): ?int
    {
        $tokens = array_filter($tokens, fn ($token): bool => $this->isTokenKindFound($this->extractTokenKind($token)));

        if (0 === \count($tokens)) {
            return null;
        }

        while (true) {
            $index += $direction;
            if (!$this->offsetExists($index)) {
                return null;
            }

            if ($this[$index]->equalsAny($tokens, $caseSensitive)) {
                return $index;
            }
        }
    }

    /**
     * Get index for closest sibling token not of given kind.
     *
     * @param int                           $index     token index
     * @param -1|1                          $direction
     * @param list<array{int}|string|Token> $tokens    possible tokens
     */
    public function getTokenNotOfKindSibling(int $index, int $direction, array $tokens = []): ?int
    {
        return $this->getTokenNotOfKind(
            $index,
            $direction,
            fn (int $a): bool => $this[$a]->equalsAny($tokens),
        );
    }

    /**
     * Get index for closest sibling token not of given kind.
     *
     * @param int       $index     token index
     * @param -1|1      $direction
     * @param list<int> $kinds     possible tokens kinds
     */
    public function getTokenNotOfKindsSibling(int $index, int $direction, array $kinds = []): ?int
    {
        return $this->getTokenNotOfKind(
            $index,
            $direction,
            fn (int $index): bool => $this[$index]->isGivenKind($kinds),
        );
    }

    /**
     * Get index for closest sibling token that is not a whitespace, comment or attribute.
     *
     * @param int  $index     token index
     * @param -1|1 $direction
     */
    public function getMeaningfulTokenSibling(int $index, int $direction): ?int
    {
        return $this->getTokenNotOfKind(
            $index,
            $direction,
            fn (int $index): bool => $this[$index]->isGivenKind(self::NON_MEANINGFUL_TOKENS),
        );
    }

    /**
     * Get index for closest sibling token which is not empty.
     *
     * @param int  $index     token index
     * @param -1|1 $direction
     */
    public function getNonEmptySibling(int $index, int $direction): ?int
    {
        while (true) {
            $index += $direction;
            if (!$this->offsetExists($index)) {
                return null;
            }

            if (!$this->isEmptyAt($index)) {
                return $index;
            }
        }
    }

    /**
     * Get index for closest next token that is not a whitespace or comment.
     *
     * @param int $index token index
     */
    public function getNextMeaningfulToken(int $index): ?int
    {
        return $this->getTokenNotOfKind(
            $index,
            self::DIRECTION_NEXT,
            fn (int $index): bool => $this[$index]->isGivenKind(self::NON_MEANINGFUL_TOKENS),
        );
    }

    /**
     * Get index for closest previous token that is not a whitespace or comment.
     *
     * @param int $index token index
     */
    public function getPrevMeaningfulToken(int $index): ?int
    {
        return $this->getTokenNotOfKind(
            $index,
            self::DIRECTION_PREV,
            fn (int $index): bool => $this[$index]->isGivenKind(self::NON_MEANINGFUL_TOKENS),
        );
    }

    /**
     * Find a sequence of meaningful tokens and returns the array of their locations.
     *
     * @param non-empty-list<array{0: int, 1?: string}|string|Token> $sequence      an array of token (kinds)
     * @param int                                                    $start         start index, defaulting to the start of the file
     * @param null|int                                               $end           end index, defaulting to the end of the file
     * @param array<int, bool>|bool                                  $caseSensitive global case sensitiveness or a list of booleans, whose keys should match
     *                                                                              the ones used in $sequence. If any is missing, the default case-sensitive
     *                                                                              comparison is used
     *
     * @return null|non-empty-array<int<0, max>, Token> an array containing the tokens matching the sequence elements, indexed by their position
     */
    public function findSequence(array $sequence, int $start = 0, ?int $end = null, $caseSensitive = true): ?array
    {
        $sequenceCount = \count($sequence);
        if (0 === $sequenceCount) {
            throw new \InvalidArgumentException('Invalid sequence.');
        }

        // $end defaults to the end of the collection
        $end = null === $end ? \count($this) - 1 : min($end, \count($this) - 1);

        if ($start + $sequenceCount - 1 > $end) {
            return null;
        }

        $nonMeaningFullKind = [T_COMMENT, T_DOC_COMMENT, T_WHITESPACE];

        // make sure the sequence content is "meaningful"
        foreach ($sequence as $key => $token) {
            // if not a Token instance already, we convert it to verify the meaningfulness
            if (!$token instanceof Token) {
                if (\is_array($token) && !isset($token[1])) {
                    // fake some content as it is required by the Token constructor,
                    // although optional for search purposes
                    $token[1] = 'DUMMY';
                }

                $token = new Token($token);
            }

            if ($token->isGivenKind($nonMeaningFullKind)) {
                throw new \InvalidArgumentException(sprintf('Non-meaningful token at position: "%s".', $key));
            }

            if ('' === $token->getContent()) {
                throw new \InvalidArgumentException(sprintf('Non-meaningful (empty) token at position: "%s".', $key));
            }
        }

        foreach ($sequence as $token) {
            if (!$this->isTokenKindFound($this->extractTokenKind($token))) {
                return null;
            }
        }

        // remove the first token from the sequence, so we can freely iterate through the sequence after a match to
        // the first one is found
        $firstKey = array_key_first($sequence);
        $firstCs = self::isKeyCaseSensitive($caseSensitive, $firstKey);
        $firstToken = $sequence[$firstKey];
        unset($sequence[$firstKey]);

        // begin searching for the first token in the sequence (start included)
        $index = $start - 1;
        while ($index <= $end) {
            $index = $this->getNextTokenOfKind($index, [$firstToken], $firstCs);

            // ensure we found a match and didn't get past the end index
            if (null === $index || $index > $end) {
                return null;
            }

            // initialise the result array with the current index
            $result = [$index => $this[$index]];

            // advance cursor to the current position
            $currIdx = $index;

            // iterate through the remaining tokens in the sequence
            foreach ($sequence as $key => $token) {
                $currIdx = $this->getNextMeaningfulToken($currIdx);

                // ensure we didn't go too far
                if (null === $currIdx || $currIdx > $end) {
                    return null;
                }

                if (!$this[$currIdx]->equals($token, self::isKeyCaseSensitive($caseSensitive, $key))) {
                    // not a match, restart the outer loop
                    continue 2;
                }

                // append index to the result array
                $result[$currIdx] = $this[$currIdx];
            }

            // do we have a complete match?
            // hint: $result is bigger than $sequence since the first token has been removed from the latter
            if (\count($sequence) < \count($result)) {
                return $result;
            }
        }

        return null;
    }

    /**
     * Insert instances of Token inside collection.
     *
     * @param int                      $index start inserting index
     * @param list<Token>|Token|Tokens $items instances of Token to insert
     */
    public function insertAt(int $index, $items): void
    {
        $this->insertSlices([$index => $items]);
    }

    /**
     * Insert a slices or individual Tokens into multiple places in a single run.
     *
     * This approach is kind-of an experiment - it's proven to improve performance a lot for big files that needs plenty of new tickets to be inserted,
     * like edge case example of 3.7h vs 4s (https://github.com/PHP-CS-Fixer/PHP-CS-Fixer/issues/3996#issuecomment-455617637),
     * yet at same time changing a logic of fixers in not-always easy way.
     *
     * To be discussed:
     * - should we always aim to use this method?
     * - should we deprecate `insertAt` method ?
     *
     * The `$slices` parameter is an assoc array, in which:
     * - index: starting point for inserting of individual slice, with indices being relatives to original array collection before any Token inserted
     * - value under index: a slice of Tokens to be inserted
     *
     * @internal
     *
     * @param array<int, list<Token>|Token|Tokens> $slices
     */
    public function insertSlices(array $slices): void
    {
        $itemsCount = 0;

        foreach ($slices as $slice) {
            $itemsCount += \is_array($slice) || $slice instanceof self ? \count($slice) : 1;
        }

        if (0 === $itemsCount) {
            return;
        }

        $oldSize = \count($this);
        $this->changed = true;
        $this->namespaceDeclarations = null;
        $this->blockStartCache = [];
        $this->blockEndCache = [];
        $this->setSize($oldSize + $itemsCount);

        krsort($slices);
        $farthestSliceIndex = array_key_first($slices);

        // We check only the farthest index, if it's within the size of collection, other indices will be valid too.
        if (!\is_int($farthestSliceIndex) || $farthestSliceIndex > $oldSize) {
            throw new \OutOfBoundsException(sprintf('Cannot insert index "%s" outside of collection.', $farthestSliceIndex));
        }

        $previousSliceIndex = $oldSize;

        // since we only move already existing items around, we directly call into SplFixedArray::offset* methods.
        // that way we get around additional overhead this class adds with overridden offset* methods.
        foreach ($slices as $index => $slice) {
            if (!\is_int($index) || $index < 0) {
                throw new \OutOfBoundsException(sprintf('Invalid index "%s".', $index));
            }

            $slice = \is_array($slice) || $slice instanceof self ? $slice : [$slice];
            $sliceCount = \count($slice);

            for ($i = $previousSliceIndex - 1; $i >= $index; --$i) {
                parent::offsetSet($i + $itemsCount, $this[$i]);
            }

            $previousSliceIndex = $index;
            $itemsCount -= $sliceCount;

            foreach ($slice as $indexItem => $item) {
                if ('' === $item->getContent()) {
                    throw new \InvalidArgumentException('Must not add empty token to collection.');
                }

                $this->registerFoundToken($item);

                parent::offsetSet($index + $itemsCount + $indexItem, $item);
            }
        }
    }

    /**
     * Check if collection was change: collection itself (like insert new tokens) or any of collection's elements.
     */
    public function isChanged(): bool
    {
        return $this->changed;
    }

    public function isEmptyAt(int $index): bool
    {
        $token = $this[$index];

        return null === $token->getId() && '' === $token->getContent();
    }

    public function clearAt(int $index): void
    {
        $this[$index] = new Token('');
    }

    /**
     * Override tokens at given range.
     *
     * @param int                      $indexStart start overriding index
     * @param int                      $indexEnd   end overriding index
     * @param array<int, Token>|Tokens $items      tokens to insert
     */
    public function overrideRange(int $indexStart, int $indexEnd, iterable $items): void
    {
        $indexToChange = $indexEnd - $indexStart + 1;
        $itemsCount = \count($items);

        // If we want to add more items than passed range contains we need to
        // add placeholders for overhead items.
        if ($itemsCount > $indexToChange) {
            $placeholders = [];

            while ($itemsCount > $indexToChange) {
                $placeholders[] = new Token('__PLACEHOLDER__');
                ++$indexToChange;
            }

            $this->insertAt($indexEnd + 1, $placeholders);
        }

        // Override each items.
        foreach ($items as $itemIndex => $item) {
            $this[$indexStart + $itemIndex] = $item;
        }

        // If we want to add fewer tokens than passed range contains then clear
        // not needed tokens.
        if ($itemsCount < $indexToChange) {
            $this->clearRange($indexStart + $itemsCount, $indexEnd);
        }
    }

    /**
     * @param null|string $whitespaces optional whitespaces characters for Token::isWhitespace
     */
    public function removeLeadingWhitespace(int $index, ?string $whitespaces = null): void
    {
        $this->removeWhitespaceSafely($index, self::DIRECTION_PREV, $whitespaces);
    }

    /**
     * @param null|string $whitespaces optional whitespaces characters for Token::isWhitespace
     */
    public function removeTrailingWhitespace(int $index, ?string $whitespaces = null): void
    {
        $this->removeWhitespaceSafely($index, self::DIRECTION_NEXT, $whitespaces);
    }

    /**
     * Set code. Clear all current content and replace it by new Token items generated from code directly.
     *
     * @param string $code PHP code
     */
    public function setCode(string $code): void
    {
        // No need to work when the code is the same.
        // That is how we avoid a lot of work and setting changed flag.
        if ($code === $this->generateCode()) {
            return;
        }

        // clear memory
        $this->setSize(0);

        $tokens = token_get_all($code, TOKEN_PARSE);

        $this->setSize(\count($tokens));

        foreach ($tokens as $index => $token) {
            $this[$index] = new Token($token);
        }

        $this->applyTransformers();

        $this->foundTokenKinds = [];

        foreach ($this as $token) {
            $this->registerFoundToken($token);
        }

        if (\PHP_VERSION_ID < 8_00_00) {
            $this->rewind();
        }

        $this->changeCodeHash(self::calculateCodeHash($code));
        $this->changed = true;
        $this->namespaceDeclarations = null;
    }

    public function toJson(): string
    {
        $output = new \SplFixedArray(\count($this));

        foreach ($this as $index => $token) {
            $output[$index] = $token->toArray();
        }

        if (\PHP_VERSION_ID < 8_00_00) {
            $this->rewind();
        }

        return json_encode($output, JSON_THROW_ON_ERROR | JSON_PRETTY_PRINT | JSON_NUMERIC_CHECK);
    }

    /**
     * Check if all token kinds given as argument are found.
     *
     * @param list<int|string> $tokenKinds
     */
    public function isAllTokenKindsFound(array $tokenKinds): bool
    {
        foreach ($tokenKinds as $tokenKind) {
            if (!isset($this->foundTokenKinds[$tokenKind])) {
                return false;
            }
        }

        return true;
    }

    /**
     * Check if any token kind given as argument is found.
     *
     * @param list<int|string> $tokenKinds
     */
    public function isAnyTokenKindsFound(array $tokenKinds): bool
    {
        foreach ($tokenKinds as $tokenKind) {
            if (isset($this->foundTokenKinds[$tokenKind])) {
                return true;
            }
        }

        return false;
    }

    /**
     * Check if token kind given as argument is found.
     *
     * @param int|string $tokenKind
     */
    public function isTokenKindFound($tokenKind): bool
    {
        return isset($this->foundTokenKinds[$tokenKind]);
    }

    /**
     * @param int|string $tokenKind
     */
    public function countTokenKind($tokenKind): int
    {
        return $this->foundTokenKinds[$tokenKind] ?? 0;
    }

    /**
     * Clear tokens in the given range.
     */
    public function clearRange(int $indexStart, int $indexEnd): void
    {
        for ($i = $indexStart; $i <= $indexEnd; ++$i) {
            $this->clearAt($i);
        }
    }

    /**
     * Checks for monolithic PHP code.
     *
     * Checks that the code is pure PHP code, in a single code block, starting
     * with an open tag.
     */
    public function isMonolithicPhp(): bool
    {
        if (1 !== ($this->countTokenKind(T_OPEN_TAG) + $this->countTokenKind(T_OPEN_TAG_WITH_ECHO))) {
            return false;
        }

        return 0 === $this->countTokenKind(T_INLINE_HTML)
            || (1 === $this->countTokenKind(T_INLINE_HTML) && Preg::match('/^#!.+$/', $this[0]->getContent()));
    }

    /**
     * @param int $start start index
     * @param int $end   end index
     */
    public function isPartialCodeMultiline(int $start, int $end): bool
    {
        for ($i = $start; $i <= $end; ++$i) {
            if (str_contains($this[$i]->getContent(), "\n")) {
                return true;
            }
        }

        return false;
    }

    public function hasAlternativeSyntax(): bool
    {
        return $this->isAnyTokenKindsFound([
            T_ENDDECLARE,
            T_ENDFOR,
            T_ENDFOREACH,
            T_ENDIF,
            T_ENDSWITCH,
            T_ENDWHILE,
        ]);
    }

    public function clearTokenAndMergeSurroundingWhitespace(int $index): void
    {
        $count = \count($this);
        $this->clearAt($index);

        if ($index === $count - 1) {
            return;
        }

        $nextIndex = $this->getNonEmptySibling($index, 1);

        if (null === $nextIndex || !$this[$nextIndex]->isWhitespace()) {
            return;
        }

        $prevIndex = $this->getNonEmptySibling($index, self::DIRECTION_PREV);

        if ($this[$prevIndex]->isWhitespace()) {
            $this[$prevIndex] = new Token([T_WHITESPACE, $this[$prevIndex]->getContent().$this[$nextIndex]->getContent()]);
        } elseif ($this->isEmptyAt($prevIndex + 1)) {
            $this[$prevIndex + 1] = new Token([T_WHITESPACE, $this[$nextIndex]->getContent()]);
        }

        $this->clearAt($nextIndex);
    }

    /**
     * @internal This is performance-related workaround for lack of proper DI, may be removed at some point
     *
     * @return list<NamespaceAnalysis>
     */
    public function getNamespaceDeclarations(): array
    {
        if (null === $this->namespaceDeclarations) {
            $this->namespaceDeclarations = (new NamespacesAnalyzer())->getDeclarations($this);
        }

        return $this->namespaceDeclarations;
    }

    /**
     * @internal
     */
    protected function applyTransformers(): void
    {
        $transformers = Transformers::createSingleton();
        $transformers->transform($this);
    }

    /**
     * @param -1|1 $direction
     */
    private function removeWhitespaceSafely(int $index, int $direction, ?string $whitespaces = null): void
    {
        $whitespaceIndex = $this->getNonEmptySibling($index, $direction);
        if (isset($this[$whitespaceIndex]) && $this[$whitespaceIndex]->isWhitespace()) {
            $newContent = '';
            $tokenToCheck = $this[$whitespaceIndex];

            // if the token candidate to remove is preceded by single line comment we do not consider the new line after this comment as part of T_WHITESPACE
            if (isset($this[$whitespaceIndex - 1]) && $this[$whitespaceIndex - 1]->isComment() && !str_starts_with($this[$whitespaceIndex - 1]->getContent(), '/*')) {
                [, $newContent, $whitespacesToCheck] = Preg::split('/^(\R)/', $this[$whitespaceIndex]->getContent(), -1, PREG_SPLIT_DELIM_CAPTURE);

                if ('' === $whitespacesToCheck) {
                    return;
                }

                $tokenToCheck = new Token([T_WHITESPACE, $whitespacesToCheck]);
            }

            if (!$tokenToCheck->isWhitespace($whitespaces)) {
                return;
            }

            if ('' === $newContent) {
                $this->clearAt($whitespaceIndex);
            } else {
                $this[$whitespaceIndex] = new Token([T_WHITESPACE, $newContent]);
            }
        }
    }

    /**
     * @param self::BLOCK_TYPE_* $type        type of block
     * @param int                $searchIndex index of starting brace
     * @param bool               $findEnd     if method should find block's end or start
     *
     * @return int<0, max> index of opposite brace
     */
    private function findOppositeBlockEdge(int $type, int $searchIndex, bool $findEnd): int
    {
        $blockEdgeDefinitions = self::getBlockEdgeDefinitions();

        if (!isset($blockEdgeDefinitions[$type])) {
            throw new \InvalidArgumentException(sprintf('Invalid param type: "%s".', $type));
        }

        if ($findEnd && isset($this->blockStartCache[$searchIndex])) {
            return $this->blockStartCache[$searchIndex];
        }

        if (!$findEnd && isset($this->blockEndCache[$searchIndex])) {
            return $this->blockEndCache[$searchIndex];
        }

        $startEdge = $blockEdgeDefinitions[$type]['start'];
        $endEdge = $blockEdgeDefinitions[$type]['end'];
        $startIndex = $searchIndex;
        $endIndex = \count($this) - 1;
        $indexOffset = 1;

        if (!$findEnd) {
            [$startEdge, $endEdge] = [$endEdge, $startEdge];
            $indexOffset = -1;
            $endIndex = 0;
        }

        if (!$this[$startIndex]->equals($startEdge)) {
            throw new \InvalidArgumentException(sprintf('Invalid param $startIndex - not a proper block "%s".', $findEnd ? 'start' : 'end'));
        }

        $blockLevel = 0;

        for ($index = $startIndex; $index !== $endIndex; $index += $indexOffset) {
            $token = $this[$index];

            if ($token->equals($startEdge)) {
                ++$blockLevel;

                continue;
            }

            if ($token->equals($endEdge)) {
                --$blockLevel;

                if (0 === $blockLevel) {
                    break;
                }
            }
        }

        if (!$this[$index]->equals($endEdge)) {
            throw new \UnexpectedValueException(sprintf('Missing block "%s".', $findEnd ? 'end' : 'start'));
        }

        if ($startIndex < $index) {
            $this->blockStartCache[$startIndex] = $index;
            $this->blockEndCache[$index] = $startIndex;
        } else {
            $this->blockStartCache[$index] = $startIndex;
            $this->blockEndCache[$startIndex] = $index;
        }

        return $index;
    }

    /**
     * Calculate hash for code.
     *
     * @return non-empty-string
     */
    private static function calculateCodeHash(string $code): string
    {
        return CodeHasher::calculateCodeHash($code);
    }

    /**
     * Get cache value for given key.
     *
     * @param non-empty-string $key item key
     */
    private static function getCache(string $key): self
    {
        if (!self::hasCache($key)) {
            throw new \OutOfBoundsException(sprintf('Unknown cache key: "%s".', $key));
        }

        return self::$cache[$key];
    }

    /**
     * Check if given key exists in cache.
     *
     * @param non-empty-string $key item key
     */
    private static function hasCache(string $key): bool
    {
        return isset(self::$cache[$key]);
    }

    /**
     * @param non-empty-string $key   item key
     * @param Tokens           $value item value
     */
    private static function setCache(string $key, self $value): void
    {
        self::$cache[$key] = $value;
    }

    /**
     * Change code hash.
     *
     * Remove old cache and set new one.
     *
     * @param non-empty-string $codeHash new code hash
     */
    private function changeCodeHash(string $codeHash): void
    {
        if (null !== $this->codeHash) {
            self::clearCache($this->codeHash);
        }

        $this->codeHash = $codeHash;
        self::setCache($this->codeHash, $this);
    }

    /**
     * Register token as found.
     *
     * @param array{int}|string|Token $token token prototype
     */
    private function registerFoundToken($token): void
    {
        // inlined extractTokenKind() call on the hot path
        /** @var int|non-empty-string */
        $tokenKind = $token instanceof Token
            ? ($token->isArray() ? $token->getId() : $token->getContent())
            : (\is_array($token) ? $token[0] : $token);

        $this->foundTokenKinds[$tokenKind] ??= 0;
        ++$this->foundTokenKinds[$tokenKind];
    }

    /**
     * Unregister token as not found.
     *
     * @param array{int}|string|Token $token token prototype
     */
    private function unregisterFoundToken($token): void
    {
        // inlined extractTokenKind() call on the hot path
        /** @var int|non-empty-string */
        $tokenKind = $token instanceof Token
            ? ($token->isArray() ? $token->getId() : $token->getContent())
            : (\is_array($token) ? $token[0] : $token);

        if (1 === $this->foundTokenKinds[$tokenKind]) {
            unset($this->foundTokenKinds[$tokenKind]);
        } else {
            --$this->foundTokenKinds[$tokenKind];
        }
    }

    /**
     * @param array{int}|string|Token $token token prototype
     *
     * @return int|non-empty-string
     */
    private function extractTokenKind($token)
    {
        return $token instanceof Token
            ? ($token->isArray() ? $token->getId() : $token->getContent())
            : (\is_array($token) ? $token[0] : $token);
    }

    /**
     * @param int                 $index     token index
     * @param -1|1                $direction
     * @param callable(int): bool $filter
     */
    private function getTokenNotOfKind(int $index, int $direction, callable $filter): ?int
    {
        while (true) {
            $index += $direction;
            if (!$this->offsetExists($index)) {
                return null;
            }

            if ($this->isEmptyAt($index) || $filter($index)) {
                continue;
            }

            return $index;
        }
    }

    /**
     * A helper method used to find out whether a certain input token has to be case-sensitively matched.
     *
     * @param array<int, bool>|bool $caseSensitive global case sensitiveness or an array of booleans, whose keys should match
     *                                             the ones used in $sequence. If any is missing, the default case-sensitive
     *                                             comparison is used
     * @param int                   $key           the key of the token that has to be looked up
     */
    private static function isKeyCaseSensitive($caseSensitive, int $key): bool
    {
        if (\is_array($caseSensitive)) {
            return $caseSensitive[$key] ?? true;
        }

        return $caseSensitive;
    }
}