<?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\Fixer\Import;

use PhpCsFixer\AbstractFixer;
use PhpCsFixer\DocBlock\TypeExpression;
use PhpCsFixer\Fixer\ConfigurableFixerInterface;
use PhpCsFixer\Fixer\ConfigurableFixerTrait;
use PhpCsFixer\Fixer\WhitespacesAwareFixerInterface;
use PhpCsFixer\FixerConfiguration\FixerConfigurationResolver;
use PhpCsFixer\FixerConfiguration\FixerConfigurationResolverInterface;
use PhpCsFixer\FixerConfiguration\FixerOptionBuilder;
use PhpCsFixer\FixerDefinition\CodeSample;
use PhpCsFixer\FixerDefinition\FixerDefinition;
use PhpCsFixer\FixerDefinition\FixerDefinitionInterface;
use PhpCsFixer\Preg;
use PhpCsFixer\Tokenizer\Analyzer\Analysis\TypeAnalysis;
use PhpCsFixer\Tokenizer\Analyzer\AttributeAnalyzer;
use PhpCsFixer\Tokenizer\Analyzer\FunctionsAnalyzer;
use PhpCsFixer\Tokenizer\Analyzer\NamespaceUsesAnalyzer;
use PhpCsFixer\Tokenizer\CT;
use PhpCsFixer\Tokenizer\Processor\ImportProcessor;
use PhpCsFixer\Tokenizer\Token;
use PhpCsFixer\Tokenizer\Tokens;

/**
 * @author VeeWee <toonverwerft@gmail.com>
 * @author Tomas Jadrny <developer@tomasjadrny.cz>
 * @author Greg Korba <greg@codito.dev>
 * @author SpacePossum <possumfromspace@gmail.com>
 * @author Michael Vorisek <https://github.com/mvorisek>
 *
 * @implements ConfigurableFixerInterface<_AutogeneratedInputConfiguration, _AutogeneratedComputedConfiguration>
 *
 * @phpstan-type _AutogeneratedInputConfiguration array{
 *  import_symbols?: bool,
 *  leading_backslash_in_global_namespace?: bool,
 *  phpdoc_tags?: list<string>,
 * }
 * @phpstan-type _AutogeneratedComputedConfiguration array{
 *  import_symbols: bool,
 *  leading_backslash_in_global_namespace: bool,
 *  phpdoc_tags: list<string>,
 * }
 * @phpstan-type _Uses array{
 *   constant?: array<class-string, string>,
 *   class?: array<class-string, string>,
 *   function?: array<class-string, string>
 * }
 *
 * @phpstan-import-type _ImportType from \PhpCsFixer\Tokenizer\Analyzer\Analysis\NamespaceUseAnalysis
 */
final class FullyQualifiedStrictTypesFixer extends AbstractFixer implements ConfigurableFixerInterface, WhitespacesAwareFixerInterface
{
    /** @use ConfigurableFixerTrait<_AutogeneratedInputConfiguration, _AutogeneratedComputedConfiguration> */
    use ConfigurableFixerTrait;

    private const REGEX_CLASS = '(?:\\\?+'.TypeExpression::REGEX_IDENTIFIER
        .'(\\\\'.TypeExpression::REGEX_IDENTIFIER.')*+)';

    /**
     * @var array{
     *     constant?: list<class-string>,
     *     class?: list<class-string>,
     *     function?: list<class-string>
     * }|null
     */
    private ?array $discoveredSymbols;

    /**
     * @var array{
     *     constant?: array<string, class-string>,
     *     class?: array<string, class-string>,
     *     function?: array<string, class-string>
     * }
     */
    private array $symbolsForImport = [];

    /**
     * @var array<int<0, max>, array<string, true>>
     */
    private array $reservedIdentifiersByLevel;

    /**
     * @var array{
     *     constant?: array<string, string>,
     *     class?: array<string, string>,
     *     function?: array<string, string>
     * }
     */
    private array $cacheUsesLast = [];

    /**
     * @var array{
     *     constant?: array<string, class-string>,
     *     class?: array<string, class-string>,
     *     function?: array<string, class-string>
     * }
     */
    private array $cacheUseNameByShortNameLower;

    /** @var _Uses */
    private array $cacheUseShortNameByNameLower;

    public function getDefinition(): FixerDefinitionInterface
    {
        return new FixerDefinition(
            'Removes the leading part of fully qualified symbol references if a given symbol is imported or belongs to the current namespace.',
            [
                new CodeSample(
                    '<?php

use Foo\Bar;
use Foo\Bar\Baz;
use Foo\OtherClass;
use Foo\SomeContract;
use Foo\SomeException;

/**
 * @see \Foo\Bar\Baz
 */
class SomeClass extends \Foo\OtherClass implements \Foo\SomeContract
{
    /**
     * @var \Foo\Bar\Baz
     */
    public $baz;

    /**
     * @param \Foo\Bar\Baz $baz
     */
    public function __construct($baz) {
        $this->baz = $baz;
    }

    /**
     * @return \Foo\Bar\Baz
     */
    public function getBaz() {
        return $this->baz;
    }

    public function doX(\Foo\Bar $foo, \Exception $e): \Foo\Bar\Baz
    {
        try {}
        catch (\Foo\SomeException $e) {}
    }
}
'
                ),
                new CodeSample(
                    '<?php

class SomeClass
{
    public function doY(Foo\NotImported $u, \Foo\NotImported $v)
    {
    }
}
',
                    ['leading_backslash_in_global_namespace' => true]
                ),
                new CodeSample(
                    '<?php
namespace {
    use Foo\A;
    try {
        foo();
    } catch (\Exception|\Foo\A $e) {
    }
}
namespace Foo\Bar {
    class SomeClass implements \Foo\Bar\Baz
    {
    }
}
',
                    ['leading_backslash_in_global_namespace' => true]
                ),
                new CodeSample(
                    '<?php

namespace Foo\Test;

class Foo extends \Other\BaseClass implements \Other\Interface1, \Other\Interface2
{
    /** @var \Other\PropertyPhpDoc */
    private $array;
    public function __construct(\Other\FunctionArgument $arg) {}
    public function foo(): \Other\FunctionReturnType
    {
        try {
            \Other\StaticFunctionCall::bar();
        } catch (\Other\CaughtThrowable $e) {}
    }
}
',
                    ['import_symbols' => true]
                ),
            ]
        );
    }

    /**
     * {@inheritdoc}
     *
     * Must run before NoSuperfluousPhpdocTagsFixer, OrderedAttributesFixer, OrderedImportsFixer, OrderedInterfacesFixer, StatementIndentationFixer.
     * Must run after ClassKeywordFixer, PhpUnitAttributesFixer, PhpdocToPropertyTypeFixer, PhpdocToReturnTypeFixer.
     */
    public function getPriority(): int
    {
        return 7;
    }

    public function isCandidate(Tokens $tokens): bool
    {
        return $tokens->isAnyTokenKindsFound([
            CT::T_USE_TRAIT,
            ...(\defined('T_ATTRIBUTE') ? [T_ATTRIBUTE] : []), // @TODO: drop condition when PHP 8.0+ is required
            T_CATCH,
            T_DOUBLE_COLON,
            T_DOC_COMMENT,
            T_EXTENDS,
            T_FUNCTION,
            T_IMPLEMENTS,
            T_INSTANCEOF,
            T_NEW,
            T_VARIABLE,
        ]);
    }

    protected function createConfigurationDefinition(): FixerConfigurationResolverInterface
    {
        return new FixerConfigurationResolver([
            (new FixerOptionBuilder(
                'leading_backslash_in_global_namespace',
                'Whether FQCN is prefixed with backslash when that FQCN is used in global namespace context.'
            ))
                ->setAllowedTypes(['bool'])
                ->setDefault(false)
                ->getOption(),
            (new FixerOptionBuilder(
                'import_symbols',
                'Whether FQCNs should be automatically imported.'
            ))
                ->setAllowedTypes(['bool'])
                ->setDefault(false)
                ->getOption(),
            (new FixerOptionBuilder(
                'phpdoc_tags',
                'Collection of PHPDoc annotation tags where FQCNs should be processed. As of now only simple tags with `@tag \F\Q\C\N` format are supported (no complex types).'
            ))
                ->setAllowedTypes(['string[]'])
                ->setDefault([
                    'param',
                    'phpstan-param',
                    'phpstan-property',
                    'phpstan-property-read',
                    'phpstan-property-write',
                    'phpstan-return',
                    'phpstan-var',
                    'property',
                    'property-read',
                    'property-write',
                    'psalm-param',
                    'psalm-property',
                    'psalm-property-read',
                    'psalm-property-write',
                    'psalm-return',
                    'psalm-var',
                    'return',
                    'see',
                    'throws',
                    'var',
                ])
                ->getOption(),
        ]);
    }

    protected function applyFix(\SplFileInfo $file, Tokens $tokens): void
    {
        $namespaceUsesAnalyzer = new NamespaceUsesAnalyzer();
        $functionsAnalyzer = new FunctionsAnalyzer();

        $this->symbolsForImport = [];

        foreach ($tokens->getNamespaceDeclarations() as $namespaceIndex => $namespace) {
            $namespace = $tokens->getNamespaceDeclarations()[$namespaceIndex];

            $namespaceName = $namespace->getFullName();

            /** @var _Uses $uses */
            $uses = [];
            $lastUse = null;

            foreach ($namespaceUsesAnalyzer->getDeclarationsInNamespace($tokens, $namespace, true) as $use) {
                if (!$use->isClass()) {
                    continue;
                }

                $uses[$use->getHumanFriendlyType()][ltrim($use->getFullName(), '\\')] = $use->getShortName();
                $lastUse = $use;
            }

            $indexDiff = 0;
            foreach (true === $this->configuration['import_symbols'] ? [true, false] : [false] as $discoverSymbolsPhase) {
                $this->discoveredSymbols = $discoverSymbolsPhase ? [] : null;

                $classyKinds = [T_CLASS, T_INTERFACE, T_TRAIT];
                if (\defined('T_ENUM')) { // @TODO: drop condition when PHP 8.1+ is required
                    $classyKinds[] = T_ENUM;
                }

                $openedCurlyBrackets = 0;
                $this->reservedIdentifiersByLevel = [];

                for ($index = $namespace->getScopeStartIndex(); $index < $namespace->getScopeEndIndex() + $indexDiff; ++$index) {
                    $origSize = \count($tokens);

                    if ($tokens[$index]->equals('{')) {
                        ++$openedCurlyBrackets;
                    } if ($tokens[$index]->equals('}')) {
                        unset($this->reservedIdentifiersByLevel[$openedCurlyBrackets]);
                        --$openedCurlyBrackets;
                    } elseif ($discoverSymbolsPhase && $tokens[$index]->isGivenKind($classyKinds)) {
                        $this->fixNextName($tokens, $index, $uses, $namespaceName);
                    } elseif ($tokens[$index]->isGivenKind(T_FUNCTION)) {
                        $this->fixFunction($functionsAnalyzer, $tokens, $index, $uses, $namespaceName);
                    } elseif ($tokens[$index]->isGivenKind([T_EXTENDS, T_IMPLEMENTS])) {
                        $this->fixExtendsImplements($tokens, $index, $uses, $namespaceName);
                    } elseif ($tokens[$index]->isGivenKind(T_CATCH)) {
                        $this->fixCatch($tokens, $index, $uses, $namespaceName);
                    } elseif ($tokens[$index]->isGivenKind(T_DOUBLE_COLON)) {
                        $this->fixPrevName($tokens, $index, $uses, $namespaceName);
                    } elseif ($tokens[$index]->isGivenKind([T_INSTANCEOF, T_NEW, CT::T_USE_TRAIT, CT::T_TYPE_COLON])) {
                        $this->fixNextName($tokens, $index, $uses, $namespaceName);
                    } elseif ($tokens[$index]->isGivenKind(T_VARIABLE)) {
                        $prevIndex = $tokens->getPrevMeaningfulToken($index);
                        if (null !== $prevIndex && $tokens[$prevIndex]->isGivenKind(T_STRING)) {
                            $this->fixPrevName($tokens, $index, $uses, $namespaceName);
                        }
                    } elseif (\defined('T_ATTRIBUTE') && $tokens[$index]->isGivenKind(T_ATTRIBUTE)) { // @TODO: drop const check when PHP 8.0+ is required
                        $this->fixAttribute($tokens, $index, $uses, $namespaceName);
                    } elseif ($discoverSymbolsPhase && !\defined('T_ATTRIBUTE') && $tokens[$index]->isComment() && Preg::match('/#\[\s*('.self::REGEX_CLASS.')/', $tokens[$index]->getContent(), $matches)) { // @TODO: drop when PHP 8.0+ is required
                        /** @var class-string $attributeClass */
                        $attributeClass = $matches[1];
                        $this->determineShortType($attributeClass, 'class', $uses, $namespaceName);
                    } elseif ($tokens[$index]->isGivenKind(T_DOC_COMMENT)) {
                        Preg::matchAll('/\*\h*@(?:psalm-|phpstan-)?(?:template(?:-covariant|-contravariant)?|(?:import-)?type)\h+('.TypeExpression::REGEX_IDENTIFIER.')(?!\S)/i', $tokens[$index]->getContent(), $matches);
                        foreach ($matches[1] as $reservedIdentifier) {
                            $this->reservedIdentifiersByLevel[$openedCurlyBrackets + 1][$reservedIdentifier] = true;
                        }

                        $this->fixPhpDoc($tokens, $index, $uses, $namespaceName);
                    }

                    $indexDiff += \count($tokens) - $origSize;
                }

                $this->reservedIdentifiersByLevel = [];

                if ($discoverSymbolsPhase) {
                    $this->setupUsesFromDiscoveredSymbols($uses, $namespaceName);
                }
            }

            if ([] !== $this->symbolsForImport) {
                if (null !== $lastUse) {
                    $atIndex = $lastUse->getEndIndex() + 1;
                } elseif (0 !== $namespace->getEndIndex()) {
                    $atIndex = $namespace->getEndIndex() + 1;
                } else {
                    $firstTokenIndex = $tokens->getNextMeaningfulToken($namespace->getScopeStartIndex());
                    if (null !== $firstTokenIndex && $tokens[$firstTokenIndex]->isGivenKind(T_DECLARE)) {
                        $atIndex = $tokens->getNextTokenOfKind($firstTokenIndex, [';']) + 1;
                    } else {
                        $atIndex = $namespace->getScopeStartIndex() + 1;
                    }
                }

                // Insert all registered FQCNs
                $this->createImportProcessor()->insertImports($tokens, $this->symbolsForImport, $atIndex);

                $this->symbolsForImport = [];
            }
        }
    }

    /**
     * @param _Uses $uses
     */
    private function refreshUsesCache(array $uses): void
    {
        if ($this->cacheUsesLast === $uses) {
            return;
        }

        $this->cacheUsesLast = $uses;

        $this->cacheUseNameByShortNameLower = [];
        $this->cacheUseShortNameByNameLower = [];

        foreach ($uses as $kind => $kindUses) {
            foreach ($kindUses as $useLongName => $useShortName) {
                $this->cacheUseNameByShortNameLower[$kind][strtolower($useShortName)] = $useLongName;

                /**
                 * @var class-string $normalisedUseLongName
                 *
                 * @phpstan-ignore varTag.nativeType
                 */
                $normalisedUseLongName = strtolower($useLongName);
                $this->cacheUseShortNameByNameLower[$kind][$normalisedUseLongName] = $useShortName;
            }
        }
    }

    private function isReservedIdentifier(string $symbol): bool
    {
        if (str_contains($symbol, '\\')) { // optimization only
            return false;
        }

        if ((new TypeAnalysis($symbol))->isReservedType()) {
            return true;
        }

        foreach ($this->reservedIdentifiersByLevel as $reservedIdentifiers) {
            if (isset($reservedIdentifiers[$symbol])) {
                return true;
            }
        }

        return false;
    }

    /**
     * Resolve absolute or relative symbol to normalized FQCN.
     *
     * @param _ImportType $importKind
     * @param _Uses       $uses
     *
     * @return class-string
     */
    private function resolveSymbol(string $symbol, string $importKind, array $uses, string $namespaceName): string
    {
        if (str_starts_with($symbol, '\\')) {
            return substr($symbol, 1); // @phpstan-ignore return.type
        }

        if ($this->isReservedIdentifier($symbol)) {
            return $symbol; // @phpstan-ignore return.type
        }

        $this->refreshUsesCache($uses);

        $symbolArr = explode('\\', $symbol, 2);
        $shortStartNameLower = strtolower($symbolArr[0]);
        if (isset($this->cacheUseNameByShortNameLower[$importKind][$shortStartNameLower])) {
            // @phpstan-ignore return.type
            return $this->cacheUseNameByShortNameLower[$importKind][$shortStartNameLower].(isset($symbolArr[1]) ? '\\'.$symbolArr[1] : '');
        }

        return ('' !== $namespaceName ? $namespaceName.'\\' : '').$symbol; // @phpstan-ignore return.type
    }

    /**
     * Shorten normalized FQCN as much as possible.
     *
     * @param _ImportType $importKind
     * @param _Uses       $uses
     */
    private function shortenSymbol(string $fqcn, string $importKind, array $uses, string $namespaceName): string
    {
        if ($this->isReservedIdentifier($fqcn)) {
            return $fqcn;
        }

        $this->refreshUsesCache($uses);

        $res = null;

        // try to shorten the name using namespace
        $iMin = 0;
        if (str_starts_with($fqcn, $namespaceName.'\\')) {
            $tmpRes = substr($fqcn, \strlen($namespaceName) + 1);
            if (!isset($this->cacheUseNameByShortNameLower[$importKind][strtolower(explode('\\', $tmpRes, 2)[0])]) && !$this->isReservedIdentifier($tmpRes)) {
                $res = $tmpRes;
                $iMin = substr_count($namespaceName, '\\') + 1;
            }
        }

        // try to shorten the name using uses
        $tmp = $fqcn;
        for ($i = substr_count($fqcn, '\\'); $i >= $iMin; --$i) {
            if (isset($this->cacheUseShortNameByNameLower[$importKind][strtolower($tmp)])) {
                $tmpRes = $this->cacheUseShortNameByNameLower[$importKind][strtolower($tmp)].substr($fqcn, \strlen($tmp));
                if (!$this->isReservedIdentifier($tmpRes)) {
                    $res = $tmpRes;

                    break;
                }
            }

            if ($i > 0) {
                $tmp = substr($tmp, 0, strrpos($tmp, '\\'));
            }
        }

        // shortening is not possible, add leading backslash if needed
        if (null === $res) {
            $res = $fqcn;
            if ('' !== $namespaceName
                || true === $this->configuration['leading_backslash_in_global_namespace']
                || isset($this->cacheUseNameByShortNameLower[$importKind][strtolower(explode('\\', $res, 2)[0])])
            ) {
                $res = '\\'.$res;
            }
        }

        return $res;
    }

    /**
     * @param _Uses $uses
     */
    private function setupUsesFromDiscoveredSymbols(array &$uses, string $namespaceName): void
    {
        foreach ($this->discoveredSymbols as $kind => $discoveredSymbols) {
            $discoveredFqcnByShortNameLower = [];

            if ('' === $namespaceName) {
                foreach ($discoveredSymbols as $symbol) {
                    if (!str_starts_with($symbol, '\\')) {
                        $shortStartName = explode('\\', ltrim($symbol, '\\'), 2)[0];
                        $shortStartNameLower = strtolower($shortStartName);
                        $discoveredFqcnByShortNameLower[$kind][$shortStartNameLower] = $this->resolveSymbol($shortStartName, $kind, $uses, $namespaceName);
                    }
                }
            }

            foreach ($uses[$kind] ?? [] as $useLongName => $useShortName) {
                $discoveredFqcnByShortNameLower[$kind][strtolower($useShortName)] = $useLongName;
            }

            $useByShortNameLower = [];
            foreach ($uses[$kind] ?? [] as $useShortName) {
                $useByShortNameLower[strtolower($useShortName)] = true;
            }

            uasort($discoveredSymbols, static function ($a, $b) {
                $res = str_starts_with($a, '\\') <=> str_starts_with($b, '\\');
                if (0 !== $res) {
                    return $res;
                }

                return substr_count($a, '\\') <=> substr_count($b, '\\');
            });
            foreach ($discoveredSymbols as $symbol) {
                while (true) {
                    $shortEndNameLower = strtolower(str_contains($symbol, '\\') ? substr($symbol, strrpos($symbol, '\\') + 1) : $symbol);
                    if (!isset($discoveredFqcnByShortNameLower[$kind][$shortEndNameLower])) {
                        $shortStartNameLower = strtolower(explode('\\', ltrim($symbol, '\\'), 2)[0]);
                        if (str_starts_with($symbol, '\\') || ('' === $namespaceName && !isset($useByShortNameLower[$shortStartNameLower]))
                            || !str_contains($symbol, '\\')
                        ) {
                            $discoveredFqcnByShortNameLower[$kind][$shortEndNameLower] = $this->resolveSymbol($symbol, $kind, $uses, $namespaceName);

                            break;
                        }
                    }
                    // else short name collision - keep unimported

                    if (str_starts_with($symbol, '\\') || '' === $namespaceName || !str_contains($symbol, '\\')) {
                        break;
                    }

                    $symbol = substr($symbol, 0, strrpos($symbol, '\\'));
                }
            }

            foreach ($uses[$kind] ?? [] as $useLongName => $useShortName) {
                $discoveredLongName = $discoveredFqcnByShortNameLower[$kind][strtolower($useShortName)] ?? null;
                if (strtolower($discoveredLongName) === strtolower($useLongName)) {
                    unset($discoveredFqcnByShortNameLower[$kind][strtolower($useShortName)]);
                }
            }

            foreach ($discoveredFqcnByShortNameLower[$kind] ?? [] as $fqcn) {
                $shortenedName = ltrim($this->shortenSymbol($fqcn, $kind, [], $namespaceName), '\\');
                if (str_contains($shortenedName, '\\')) { // prevent importing non-namespaced names in global namespace
                    $shortEndName = str_contains($fqcn, '\\') ? substr($fqcn, strrpos($fqcn, '\\') + 1) : $fqcn;
                    $uses[$kind][$fqcn] = $shortEndName;
                    $this->symbolsForImport[$kind][$shortEndName] = $fqcn;
                }
            }

            if (isset($this->symbolsForImport[$kind])) {
                ksort($this->symbolsForImport[$kind], SORT_NATURAL);
            }
        }
    }

    /**
     * @param _Uses $uses
     */
    private function fixFunction(FunctionsAnalyzer $functionsAnalyzer, Tokens $tokens, int $index, array $uses, string $namespaceName): void
    {
        $arguments = $functionsAnalyzer->getFunctionArguments($tokens, $index);

        foreach ($arguments as $i => $argument) {
            $argument = $functionsAnalyzer->getFunctionArguments($tokens, $index)[$i];

            if ($argument->hasTypeAnalysis()) {
                $this->replaceByShortType($tokens, $argument->getTypeAnalysis(), $uses, $namespaceName);
            }
        }

        $returnTypeAnalysis = $functionsAnalyzer->getFunctionReturnType($tokens, $index);

        if (null !== $returnTypeAnalysis) {
            $this->replaceByShortType($tokens, $returnTypeAnalysis, $uses, $namespaceName);
        }
    }

    /**
     * @param _Uses $uses
     */
    private function fixPhpDoc(Tokens $tokens, int $index, array $uses, string $namespaceName): void
    {
        $allowedTags = $this->configuration['phpdoc_tags'];

        if ([] === $allowedTags) {
            return;
        }

        $phpDoc = $tokens[$index];
        $phpDocContent = $phpDoc->getContent();
        $phpDocContentNew = Preg::replaceCallback('/([*{]\h*@)(\S+)(\h+)('.TypeExpression::REGEX_TYPES.')(?!(?!\})\S)/', function ($matches) use ($allowedTags, $uses, $namespaceName) {
            if (!\in_array($matches[2], $allowedTags, true)) {
                return $matches[0];
            }

            return $matches[1].$matches[2].$matches[3].$this->fixPhpDocType($matches[4], $uses, $namespaceName);
        }, $phpDocContent);

        if ($phpDocContentNew !== $phpDocContent) {
            $tokens[$index] = new Token([T_DOC_COMMENT, $phpDocContentNew]);
        }
    }

    /**
     * @param _Uses $uses
     */
    private function fixPhpDocType(string $type, array $uses, string $namespaceName): string
    {
        $typeExpression = new TypeExpression($type, null, []);

        $typeExpression = $typeExpression->mapTypes(function (TypeExpression $type) use ($uses, $namespaceName) {
            $currentTypeValue = $type->toString();

            if ($type->isCompositeType() || !Preg::match('/^'.self::REGEX_CLASS.'$/', $currentTypeValue)) {
                return $type;
            }

            /** @var class-string $currentTypeValue */
            $shortTokens = $this->determineShortType($currentTypeValue, 'class', $uses, $namespaceName);

            if (null === $shortTokens) {
                return $type;
            }

            $newTypeValue = implode('', array_map(
                static fn (Token $token) => $token->getContent(),
                $shortTokens
            ));

            return $currentTypeValue === $newTypeValue
                ? $type
                : new TypeExpression($newTypeValue, null, []);
        });

        return $typeExpression->toString();
    }

    /**
     * @param _Uses $uses
     */
    private function fixExtendsImplements(Tokens $tokens, int $index, array $uses, string $namespaceName): void
    {
        // We handle `extends` and `implements` with similar logic, but we need to exit the loop under different conditions.
        $isExtends = $tokens[$index]->equals([T_EXTENDS]);
        $index = $tokens->getNextMeaningfulToken($index);

        $typeStartIndex = null;
        $typeEndIndex = null;

        while (true) {
            if ($tokens[$index]->equalsAny([',', '{', [T_IMPLEMENTS]])) {
                if (null !== $typeStartIndex) {
                    $index += $this->shortenClassIfPossible($tokens, $typeStartIndex, $typeEndIndex, $uses, $namespaceName);
                }
                $typeStartIndex = null;

                if ($tokens[$index]->equalsAny($isExtends ? [[T_IMPLEMENTS], '{'] : ['{'])) {
                    break;
                }
            } else {
                if (null === $typeStartIndex) {
                    $typeStartIndex = $index;
                }
                $typeEndIndex = $index;
            }

            $index = $tokens->getNextMeaningfulToken($index);
        }
    }

    /**
     * @param _Uses $uses
     */
    private function fixCatch(Tokens $tokens, int $index, array $uses, string $namespaceName): void
    {
        $index = $tokens->getNextMeaningfulToken($index); // '('
        $index = $tokens->getNextMeaningfulToken($index); // first part of first exception class to be caught

        $typeStartIndex = null;
        $typeEndIndex = null;

        while (true) {
            if ($tokens[$index]->equalsAny([')', [T_VARIABLE], [CT::T_TYPE_ALTERNATION]])) {
                if (null === $typeStartIndex) {
                    break;
                }

                $index += $this->shortenClassIfPossible($tokens, $typeStartIndex, $typeEndIndex, $uses, $namespaceName);
                $typeStartIndex = null;

                if ($tokens[$index]->equals(')')) {
                    break;
                }
            } else {
                if (null === $typeStartIndex) {
                    $typeStartIndex = $index;
                }
                $typeEndIndex = $index;
            }

            $index = $tokens->getNextMeaningfulToken($index);
        }
    }

    /**
     * @param _Uses $uses
     */
    private function fixAttribute(Tokens $tokens, int $index, array $uses, string $namespaceName): void
    {
        $attributeAnalysis = AttributeAnalyzer::collectOne($tokens, $index);

        foreach ($attributeAnalysis->getAttributes() as $attribute) {
            $index = $attribute['start'];
            while ($tokens[$index]->equalsAny([[T_STRING], [T_NS_SEPARATOR]])) {
                $index = $tokens->getPrevMeaningfulToken($index);
            }
            $this->fixNextName($tokens, $index, $uses, $namespaceName);
        }
    }

    /**
     * @param _Uses $uses
     */
    private function fixPrevName(Tokens $tokens, int $index, array $uses, string $namespaceName): void
    {
        $typeStartIndex = null;
        $typeEndIndex = null;

        while (true) {
            $index = $tokens->getPrevMeaningfulToken($index);
            if ($tokens[$index]->isObjectOperator()) {
                break;
            }

            if ($tokens[$index]->equalsAny([[T_STRING], [T_NS_SEPARATOR]])) {
                $typeStartIndex = $index;
                if (null === $typeEndIndex) {
                    $typeEndIndex = $index;
                }
            } else {
                if (null !== $typeEndIndex) {
                    $index += $this->shortenClassIfPossible($tokens, $typeStartIndex, $typeEndIndex, $uses, $namespaceName);
                }

                break;
            }
        }
    }

    /**
     * @param _Uses $uses
     */
    private function fixNextName(Tokens $tokens, int $index, array $uses, string $namespaceName): void
    {
        $typeStartIndex = null;
        $typeEndIndex = null;

        while (true) {
            $index = $tokens->getNextMeaningfulToken($index);

            if ($tokens[$index]->equalsAny([[T_STRING], [T_NS_SEPARATOR]])) {
                if (null === $typeStartIndex) {
                    $typeStartIndex = $index;
                }
                $typeEndIndex = $index;
            } else {
                if (null !== $typeStartIndex) {
                    $index += $this->shortenClassIfPossible($tokens, $typeStartIndex, $typeEndIndex, $uses, $namespaceName);
                }

                break;
            }
        }
    }

    /**
     * @param _Uses $uses
     */
    private function shortenClassIfPossible(Tokens $tokens, int $typeStartIndex, int $typeEndIndex, array $uses, string $namespaceName): int
    {
        /** @var class-string $content */
        $content = $tokens->generatePartialCode($typeStartIndex, $typeEndIndex);
        $newTokens = $this->determineShortType($content, 'class', $uses, $namespaceName);
        if (null === $newTokens) {
            return 0;
        }

        $tokens->overrideRange($typeStartIndex, $typeEndIndex, $newTokens);

        return \count($newTokens) - ($typeEndIndex - $typeStartIndex) - 1;
    }

    /**
     * @param _Uses $uses
     */
    private function replaceByShortType(Tokens $tokens, TypeAnalysis $type, array $uses, string $namespaceName): void
    {
        $typeStartIndex = $type->getStartIndex();

        if ($tokens[$typeStartIndex]->isGivenKind(CT::T_NULLABLE_TYPE)) {
            $typeStartIndex = $tokens->getNextMeaningfulToken($typeStartIndex);
        }

        $types = $this->getTypes($tokens, $typeStartIndex, $type->getEndIndex());

        foreach ($types as [$startIndex, $endIndex]) {
            /** @var class-string $content */
            $content = $tokens->generatePartialCode($startIndex, $endIndex);
            $newTokens = $this->determineShortType($content, 'class', $uses, $namespaceName);
            if (null !== $newTokens) {
                $tokens->overrideRange($startIndex, $endIndex, $newTokens);
            }
        }
    }

    /**
     * Determines short type based on FQCN, current namespace and imports (`use` declarations).
     *
     * @param class-string $typeName
     * @param _ImportType  $importKind
     * @param _Uses        $uses
     *
     * @return null|list<Token>
     */
    private function determineShortType(string $typeName, string $importKind, array $uses, string $namespaceName): ?array
    {
        if (null !== $this->discoveredSymbols) {
            if (!$this->isReservedIdentifier($typeName)) {
                $this->discoveredSymbols[$importKind][] = $typeName;
            }

            return null;
        }

        $fqcn = $this->resolveSymbol($typeName, $importKind, $uses, $namespaceName);
        $shortenedType = $this->shortenSymbol($fqcn, $importKind, $uses, $namespaceName);
        if ($shortenedType === $typeName) {
            return null;
        }

        return $this->namespacedStringToTokens($shortenedType);
    }

    /**
     * @return iterable<array{int, int}>
     */
    private function getTypes(Tokens $tokens, int $index, int $endIndex): iterable
    {
        $skipNextYield = false;
        $typeStartIndex = $typeEndIndex = null;
        while (true) {
            if ($tokens[$index]->isGivenKind(CT::T_DISJUNCTIVE_NORMAL_FORM_TYPE_PARENTHESIS_OPEN)) {
                $index = $tokens->getNextMeaningfulToken($index);
                $typeStartIndex = $typeEndIndex = null;

                continue;
            }

            if (
                $tokens[$index]->isGivenKind([CT::T_TYPE_ALTERNATION, CT::T_TYPE_INTERSECTION, CT::T_DISJUNCTIVE_NORMAL_FORM_TYPE_PARENTHESIS_CLOSE])
                || $index > $endIndex
            ) {
                if (!$skipNextYield && null !== $typeStartIndex) {
                    $origCount = \count($tokens);

                    yield [$typeStartIndex, $typeEndIndex];

                    $endIndex += \count($tokens) - $origCount;

                    // type tokens were possibly updated, restart type match
                    $skipNextYield = true;
                    $index = $typeEndIndex = $typeStartIndex;
                } else {
                    $skipNextYield = false;
                    $index = $tokens->getNextMeaningfulToken($index);
                    $typeStartIndex = $typeEndIndex = null;
                }

                if ($index > $endIndex) {
                    break;
                }

                continue;
            }

            if (null === $typeStartIndex) {
                $typeStartIndex = $index;
            }
            $typeEndIndex = $index;

            $index = $tokens->getNextMeaningfulToken($index);
        }
    }

    /**
     * @return list<Token>
     */
    private function namespacedStringToTokens(string $input): array
    {
        $tokens = [];

        if (str_starts_with($input, '\\')) {
            $tokens[] = new Token([T_NS_SEPARATOR, '\\']);
            $input = substr($input, 1);
        }

        $parts = explode('\\', $input);
        foreach ($parts as $index => $part) {
            $tokens[] = new Token([T_STRING, $part]);

            if ($index !== \count($parts) - 1) {
                $tokens[] = new Token([T_NS_SEPARATOR, '\\']);
            }
        }

        return $tokens;
    }

    /**
     * We need to create import processor dynamically (not in costructor), because actual whitespace configuration
     * is set later, not when fixer's instance is created.
     */
    private function createImportProcessor(): ImportProcessor
    {
        return new ImportProcessor($this->whitespacesConfig);
    }
}
