TokenMatcherGenerator::buildOnTransition() - Code Metrics - Inspection of "Token matcher and build process cleanup" - remorhaz/php-unilex - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( 93b753...7b55bb )

by Edward

created 2020-04-08 10:27 UTC

TokenMatcherGenerator::buildOnTransition() A

↳ Parent: TokenMatcherGenerator

Complexity

Conditions	1
Paths	1

Size

Total Lines	3
Code Lines	1

Duplication

Lines	0
Ratio	0 %

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	1
eloc	1
c	1
b	0
f	0
nc	1
nop	0
dl	0
loc	3
rs	10

<?php

declare(strict_types=1);

namespace Remorhaz\UniLex\Lexer;

use ReflectionException;
use Remorhaz\UniLex\AST\Translator;
use Remorhaz\UniLex\AST\Tree;
use Remorhaz\UniLex\Exception;
use Remorhaz\UniLex\RegExp\FSM\Dfa;
use Remorhaz\UniLex\RegExp\FSM\DfaBuilder;
use Remorhaz\UniLex\RegExp\FSM\Nfa;
use Remorhaz\UniLex\RegExp\FSM\NfaBuilder;
use Remorhaz\UniLex\RegExp\FSM\Range;
use Remorhaz\UniLex\RegExp\FSM\RangeSet;
use Remorhaz\UniLex\RegExp\FSM\TransitionMap;
use Remorhaz\UniLex\RegExp\ParserFactory;
use Remorhaz\UniLex\RegExp\PropertyLoader;
use Remorhaz\UniLex\Unicode\CharBufferFactory;
use Throwable;

use function array_diff;
use function array_intersect;
use function array_keys;
use function array_merge;
use function array_pop;
use function array_unique;
use function count;
use function implode;
use function in_array;
use function var_export;

class TokenMatcherGenerator
{

    private $spec;

    private $output;

    private $dfa;

    private $regExpMap = [];

    private $visitedHashMap = [];

    public function __construct(TokenMatcherSpec $spec)
    {
        $this->spec = $spec;
    }

    /**
     * @return string
     * @throws Exception
     * @throws ReflectionException
     */
    private function buildOutput(): string
    {
        return
            "{$this->buildFileComment()}\ndeclare(strict_types=1);\n\n" .
            "{$this->buildHeader()}\n" .
            "class {$this->spec->getTargetShortName()} extends {$this->spec->getTemplateClass()->getShortName()}\n" .
            "{\n" .
            "\n" .
            "    public function match({$this->buildMatchParameters()}): bool\n" .
            "    {\n{$this->buildMatchBody()}" .
            "    }\n" .
            "}\n";
    }

    /**
     * @return TokenMatcherInterface
     * @throws Exception
     */
    public function load(): TokenMatcherInterface
    {
        $targetClass = $this->spec->getTargetClassName();
        if (!class_exists($targetClass)) {
            try {
                $source = $this->getOutput(false);
                eval($source);

            } catch (Throwable $e) {
                throw new Exception("Invalid PHP code generated", 0, $e);
            }
            if (!class_exists($targetClass)) {
                throw new Exception("Failed to generate target class");
            }
        }

        return new $targetClass();
    }

    /**
     * @param bool $asFile
     * @return string
     * @throws Exception
     * @throws ReflectionException
     */
    public function getOutput(bool $asFile = true): string
    {
        if (!isset($this->output)) {
            $this->output = $this->buildOutput();
        }

        return $asFile ? "<?php\n\n{$this->output}" : $this->output;
    }

    private function buildFileComment(): string
    {
        $content = $this->spec->getFileComment();
        if ('' == $content) {
            return '';
        }
        $comment = "/**\n";
        $commentLineList = explode("\n", $content);
        foreach ($commentLineList as $commentLine) {
            $comment .= rtrim(" * {$commentLine}") . "\n";
        }
        $comment .= " */\n";

        return $comment;
    }

    /**
     * @return string
     * @throws ReflectionException
     */
    public function buildHeader(): string
    {
        $headerParts = [];
        $namespace = $this->spec->getTargetNamespaceName();
        if ($namespace != '') {
            $headerParts[] = $this->buildMethodPart("namespace {$namespace};", 0);
        }
        $useList = $this->buildUseList();
        if ('' != $useList) {
            $headerParts[] = $useList;
        }
        $header = $this->buildMethodPart($this->spec->getHeader(), 0);
        if ('' != $header) {
            $headerParts[] = $header;
        }

        return implode("\n", $headerParts);
    }

    /**
     * @return string
     * @throws ReflectionException
     */
    private function buildUseList(): string
    {
        $result = '';
        foreach ($this->spec->getUsedClassList() as $alias => $className) {
            $classWithAlias = is_string($alias) ? "{$className} {$alias}" : $className;
            $result .= $this->buildMethodPart("use {$classWithAlias};", 0);
        }

        return $result;
    }

    /**
     * @return string
     * @throws ReflectionException
     */
    private function buildMatchParameters(): string
    {
        $paramList = [];
        foreach ($this->spec->getMatchMethod()->getParameters() as $matchParameter) {
            if ($matchParameter->hasType()) {
                $param = $matchParameter->getType()->isBuiltin()
                    ? $matchParameter->getType()->getName()
                    : $matchParameter->getClass()->getShortName();
                $param .= " ";
            } else {
                $param = "";
            }
            $param .= "\${$matchParameter->getName()}";
            $paramList[] = $param;
        }

        return implode(", ", $paramList);
    }

    /**
     * @return string
     * @throws Exception
     */
    private function buildMatchBody(): string
    {
        $result = $this->buildBeforeMatch();

        foreach ($this->spec->getModeList() as $mode) {
            if (TokenMatcherInterface::DEFAULT_MODE == $mode) {
                continue;
            }
            $result .=
                $this->buildMethodPart("if (\$context->getMode() == '{$mode}') {") .
                $this->buildFsmEntry($mode, 3) .
                $this->buildMethodPart("}");
        }
        foreach ($this->spec->getModeList() as $mode) {
            if (TokenMatcherInterface::DEFAULT_MODE == $mode) {
                $result .= $this->buildFsmEntry(TokenMatcherInterface::DEFAULT_MODE) . "\n";
            }
            $result .= $this->buildFsmMoves($mode);
        }

        $result .= $this->buildErrorState();

        return $result;
    }

    private function buildBeforeMatch(): string
    {
        return
            $this->buildMethodPart("\$context = \$this->createContext(\$buffer, \$tokenFactory);") .
            $this->buildMethodPart($this->spec->getBeforeMatch());
    }

    /**
     * @param string $mode
     * @param int    $indent
     * @return string
     * @throws Exception
     */
    private function buildFsmEntry(string $mode, int $indent = 2): string
    {
        $state = $this->getDfa($mode)->getStateMap()->getStartState();

        return $this->buildMethodPart("goto {$this->buildStateLabel('state', $mode, $state)};", $indent);
    }

    private function buildStateLabel(string $prefix, string $mode, int $state): string
    {
        $contextSuffix = TokenMatcherInterface::DEFAULT_MODE == $mode
            ? ''
            : ucfirst($mode);

        return "{$prefix}{$contextSuffix}{$state}";
    }

    /**
     * @param string $mode
     * @return string
     * @throws Exception
     */
    private function buildFsmMoves(string $mode): string
    {
        $result = '';
        foreach ($this->getDfa($mode)->getStateMap()->getStateList() as $stateIn) {
            if ($this->isFinishStateWithSingleEnteringTransition($mode, $stateIn)) {
                continue;
            }
            $result .=
                $this->buildStateEntry($mode, $stateIn) .
                $this->buildStateTransitionList($mode, $stateIn) .
                $this->buildStateFinish($mode, $stateIn);
        }

        return $result;
    }

    /**
     * @param string $mode
     * @param int    $stateIn
     * @return string
     * @throws Exception
     */
    private function buildStateEntry(string $mode, int $stateIn): string
    {
        $result = '';
        $result .= $this->buildMethodPart("{$this->buildStateLabel('state', $mode, $stateIn)}:");
        $moves = $this->getDfa($mode)->getTransitionMap()->getExitList($stateIn);
        if (empty($moves)) {
            return $result;
        }
        $result .= $this->buildMethodPart("if (\$context->getBuffer()->isEnd()) {");
        $result .= $this->getDfa($mode)->getStateMap()->isFinishState($stateIn)
            ? $this->buildMethodPart("goto {$this->buildStateLabel('finish', $mode, $stateIn)};", 3)
            : $this->buildMethodPart("goto error;", 3);
        $result .=
            $this->buildMethodPart("}") .
            $this->buildMethodPart("\$char = \$context->getBuffer()->getSymbol();");

        return $result;
    }

    /**
     * @param string $mode
     * @param int    $stateIn
     * @return string
     * @throws Exception
     */
    private function buildStateTransitionList(string $mode, int $stateIn): string
    {
        $result = '';
        foreach ($this->getDfa($mode)->getTransitionMap()->getExitList($stateIn) as $stateOut => $symbolList) {
            foreach ($symbolList as $symbol) {
                $rangeSet = $this->getDfa($mode)->getSymbolTable()->getRangeSet($symbol);
                $result .=
                    $this->buildMethodPart("if ({$this->buildRangeSetCondition($rangeSet)}) {") .
                    $this->buildOnTransition() .
                    $this->buildMethodPart("\$context->getBuffer()->nextSymbol();", 3) .
                    $this->buildMarkTransitionVisited($mode, $stateIn, $stateOut, $symbol, 3);
                $result .= $this->isFinishStateWithSingleEnteringTransition($mode, $stateOut)
                    ? $this->buildToken($mode, $stateOut, 3)
                    : $this->buildStateTransition($mode, $stateOut, 3);
                $result .= $this->buildMethodPart("}");
            }
        }

        return $result;
    }

    private function buildMarkTransitionVisited(
        string $mode,
        int $stateIn,
        int $stateOut,
        int $symbol,
        int $indent = 3
    ): string {
        $result = '';
        $hash = $this->buildHash($stateIn, $stateOut, $symbol);
        foreach ($this->visitedHashMap[$mode] ?? [] as $regExps) {
            foreach ($regExps as $hashes) {
                if (in_array($hash, $hashes)) {
                    $hashArg = var_export($hash, true);
                    $result .= $this->buildMethodPart("\$context->visitTransition({$hashArg});", $indent);
                    break 2;
                }
            }
        }

        return $result;
    }

    /**
     * @param string $mode
     * @param int    $stateOut
     * @param int    $indent
     * @return string
     */
    private function buildStateTransition(string $mode, int $stateOut, int $indent = 3): string
    {
        return $this->buildMethodPart("goto {$this->buildStateLabel('state', $mode, $stateOut)};", $indent);
    }

    /**
     * @param string $mode
     * @param int    $stateOut
     * @return bool
     * @throws Exception
     */
    private function isFinishStateWithSingleEnteringTransition(string $mode, int $stateOut): bool
    {
        if (!$this->getDfa($mode)->getStateMap()->isFinishState($stateOut)) {
            return false;
        }
        $enters = $this->getDfa($mode)->getTransitionMap()->getEnterList($stateOut);
        $exits = $this->getDfa($mode)->getTransitionMap()->getExitList($stateOut);
        if (!(count($enters) == 1 && count($exits) == 0)) {
            return false;
        }
        $symbolList = array_pop($enters);

        return count($symbolList) == 1;
    }

    private function buildHex(int $char): string
    {
        $hexChar = strtoupper(dechex($char));
        if (strlen($hexChar) % 2 != 0) {
            $hexChar = "0{$hexChar}";
        }

        return "0x{$hexChar}";
    }

    private function buildRangeCondition(Range $range): array
    {
        $startChar = $this->buildHex($range->getStart());
        if ($range->getStart() == $range->getFinish()) {
            return ["{$startChar} == \$char"];
        }
        $finishChar = $this->buildHex($range->getFinish());
        if ($range->getStart() + 1 == $range->getFinish()) {
            return [
                "{$startChar} == \$char",
                "{$finishChar} == \$char",
            ];
        }

        return ["{$startChar} <= \$char && \$char <= {$finishChar}"];
    }

    private function buildRangeSetCondition(RangeSet $rangeSet): string
    {
        $conditionList = [];
        foreach ($rangeSet->getRanges() as $range) {
            $conditionList = array_merge($conditionList, $this->buildRangeCondition($range));
        }
        $result = implode(" || ", $conditionList);
        if (strlen($result) + 15 <= 120 || count($conditionList) == 1) {
            return ltrim($result);
        }
        $result = $this->buildMethodPart(implode(" ||\n", $conditionList), 1);

        return "\n    " . ltrim($result);
    }

    /**
     * @param string $mode
     * @param int    $stateIn
     * @return string
     * @throws Exception
     */
    private function buildStateFinish(string $mode, int $stateIn): string
    {
        if (!$this->getDfa($mode)->getStateMap()->isFinishState($stateIn)) {
            return $this->buildMethodPart("goto error;\n");
        }
        $result = '';
        if (!empty($this->getDfa($mode)->getTransitionMap()->getExitList($stateIn))) {
            $result .= $this->buildMethodPart("{$this->buildStateLabel('finish', $mode, $stateIn)}:");
        }
        $result .= "{$this->buildToken($mode, $stateIn)}\n";

        return $result;
    }

    /**
     * @param string $mode
     * @param int    $stateIn
     * @param int    $indent
     * @return string
     * @throws Exception
     */
    private function buildToken(string $mode, int $stateIn, int $indent = 2): string
    {
        $result = '';
        $regExpCount = 0;
        foreach ($this->visitedHashMap[$mode][$stateIn] ?? [] as $regExp => $visitedHashes) {
            if (empty($visitedHashes)) {
                throw new Exception("Empty tokens are not allowed");
            }
            $visitedHashValues = [];
            foreach ($visitedHashes as $visitedHash) {
                $visitedHashValues[] = var_export($visitedHash, true);
            }
            $visitedHashArgs = implode(', ', $visitedHashValues);
            $tokenSpec = $this->spec->getTokenSpec($mode, (string) $regExp);
            $result .=
                $this->buildMethodPart("if (\$context->isVisitedTransition({$visitedHashArgs})) {", $indent) .
                $this->buildMethodPart("// {$regExp}", $indent + 1) .
                $this->buildSingleToken($tokenSpec, $indent + 1) .
                $this->buildMethodPart("}", $indent);
            $regExpCount++;
        }

        if (0 == $regExpCount) {
            throw new Exception("No tokens found for state {$stateIn}");
        }

        return
            $result .
            $this->buildMethodPart("goto error;", $indent);
    }

    private function buildSingleToken(TokenSpec $tokenSpec, int $indent): string
    {
        return
            $this->buildMethodPart($tokenSpec->getCode(), $indent) .
            $this->buildOnToken($indent) . "\n" .
            $this->buildMethodPart("return true;", $indent);
    }

    private function buildErrorState(): string
    {
        $code = $this->spec->getOnError();

        return
            $this->buildMethodPart("error:") .
            $this->buildMethodPart('' == $code ? "return false;" : $code);
    }

    private function buildMethodPart(string $code, int $indent = 2): string
    {
        if ('' == $code) {
            return '';
        }
        $result = '';
        $codeLineList = explode("\n", $code);
        foreach ($codeLineList as $codeLine) {
            $line = '';
            for ($i = 0; $i < $indent; $i++) {
                $line .= "    ";
            }
            $result .= rtrim($line . $codeLine) . "\n";
        }

        return $result;
    }

    private function buildOnTransition(): string
    {
        return $this->buildMethodPart($this->spec->getOnTransition(), 3);
    }

    private function buildOnToken(int $indent = 2): string
    {
        return $this->buildMethodPart($this->spec->getOnToken(), $indent);
    }

    /**
     * @param string $context
     * @return Dfa
     * @throws Exception
     */
    private function getDfa(string $context): Dfa
    {
        if (!isset($this->dfa[$context])) {
            $this->dfa[$context] = $this->buildDfa($context);
        }

        return $this->dfa[$context];
    }

    /**
     * @param string $mode
     * @return Dfa
     * @throws Exception
     */
    private function buildDfa(string $mode): Dfa
    {
        $nfa = new Nfa();
        $startState = $nfa->getStateMap()->createState();
        $nfa->getStateMap()->addStartState($startState);
        $nfaRegExpMap = [];
        foreach ($this->spec->getTokenSpecList($mode) as $tokenSpec) {
            $existingStates = $nfa->getStateMap()->getStateList();
            $regExpEntryState = $nfa->getStateMap()->createState();
            $nfa
                ->getEpsilonTransitionMap()
                ->addTransition($startState, $regExpEntryState, true);
            $this->buildRegExp($nfa, $regExpEntryState, $tokenSpec->getRegExp());
            $nfaRegExpMap[$tokenSpec->getRegExp()] = array_diff(
                $nfa->getStateMap()->getStateList(),
                $existingStates
            );
        }

        $dfa = DfaBuilder::fromNfa($nfa);
        $dfaRegExpMap = [];
        foreach (array_keys($nfaRegExpMap, null, true) as $regExp) {
            $dfaRegExpMap[$regExp] = [];
        }
        $allDfaStateIds = $dfa->getStateMap()->getStateList();
        foreach ($allDfaStateIds as $dfaStateId) {
            $nfaStateIds = $dfa->getStateMap()->getStateValue($dfaStateId);
            foreach ($nfaRegExpMap as $regExp => $nfaRegExpStateIds) {
                if (!empty(array_intersect($nfaStateIds, $nfaRegExpStateIds))) {
                    $dfaRegExpMap[(string) $regExp][] = $dfaStateId; // TODO: why the hell integer?..
                }
            }
        }
        $this->regExpMap[$mode] = [];
        foreach ($dfaRegExpMap as $regExp => $regExpStateIds) {
            $this->regExpMap[$mode][(string) $regExp] = [$regExpStateIds, array_diff($allDfaStateIds, $regExpStateIds)];
        }
        $nfaRegExpTransitionMap = new TransitionMap($nfa->getStateMap());
        foreach ($nfa->getSymbolTransitionMap()->getTransitionList() as $nfaSourceStateId => $nfaTransitionTargets) {
            foreach ($nfaTransitionTargets as $nfaTargetStateId => $nfaSymbolIds) {
                $regExps = [];
                foreach ($nfaRegExpMap as $regExp => $nfaRegExpIds) {
                    if (in_array($nfaSourceStateId, $nfaRegExpIds) || in_array($nfaTargetStateId, $nfaRegExpIds)) {
                        $regExps[] = (string) $regExp;
                    }
                }
                $nfaTransitionValue = [];
                foreach ($nfaSymbolIds as $nfaSymbolId) {
                    $nfaTransitionValue[$nfaSymbolId] = $regExps;
                }
                $nfaRegExpTransitionMap->addTransition($nfaSourceStateId, $nfaTargetStateId, $nfaTransitionValue);
            }
        }

        $map = [];
        $mapIn = [];
        $mapOut = [];
        foreach ($dfa->getTransitionMap()->getTransitionList() as $dfaSourceStateId => $dfaTransitionTargets) {
            foreach ($dfaTransitionTargets as $dfaTargetStateId => $dfaSymbolIds) {
                $matchingNfaSourceStateIds = $dfa->getStateMap()->getStateValue($dfaSourceStateId);
                $matchingNfaTargetStateIds = $dfa->getStateMap()->getStateValue($dfaTargetStateId);
                $dfaTransitionValue = [];
                foreach ($matchingNfaSourceStateIds as $nfaSourceStateId) {
                    foreach ($matchingNfaTargetStateIds as $nfaTargetStateId) {
                        if (
                            $nfa->getStateMap()->stateExists($nfaSourceStateId) && // TODO: find out invalid id
                            $nfa->getStateMap()->stateExists($nfaTargetStateId) &&
                            $nfaRegExpTransitionMap->transitionExists($nfaSourceStateId, $nfaTargetStateId)
                        ) {
                            $nfaTransitionValue = $nfaRegExpTransitionMap->getTransition(
                                $nfaSourceStateId,
                                $nfaTargetStateId
                            );
                            foreach ($dfaSymbolIds as $dfaSymbolId) {
                                if (isset($nfaTransitionValue[$dfaSymbolId])) {
                                    $dfaTransitionValue[$dfaSymbolId] = array_unique(
                                        array_merge(
                                            $dfaTransitionValue[$dfaSymbolId] ?? [],
                                            $nfaTransitionValue[$dfaSymbolId]
                                        )
                                    );
                                }
                            }
                        }
                    }
                }
                foreach ($dfaTransitionValue as $dfaSymbolId => $regExps) {
                    $hash = $this->buildHash($dfaSourceStateId, $dfaTargetStateId, $dfaSymbolId);
                    $map[$hash] = $regExps;
                    $mapIn[$dfaSourceStateId] = array_merge($mapIn[$dfaSourceStateId] ?? [], [$hash]);
                    $mapOut[$dfaTargetStateId] = array_merge($mapOut[$dfaTargetStateId] ?? [], [$hash]);
                }
            }
        }
        $incomingTransitionsForHash = [];
        $incomingTransitionsForState = [];
        foreach ($mapIn as $stateId => $hashes) {
            foreach ($hashes as $hash) {
                $incomingTransitionsForHash[$hash] = $mapOut[$stateId] ?? [];
            }
        }
        foreach (array_keys($mapOut) as $stateId) {
            if ($dfa->getStateMap()->isFinishState($stateId)) {
                $incomingTransitionsForState[$stateId] = $mapOut[$stateId] ?? [];
            }
        }
        $this->visitedHashMap[$mode] = [];
        foreach ($incomingTransitionsForState as $stateId => $hashes) {
            $inHashBuffer = $hashes;
            $processedHashes = [];
            $visitedHashes = [];
            $regExps = [];
            foreach ($hashes as $hash) {
                $regExps = array_unique(array_merge($regExps, $map[$hash]));
            }
            while (!empty($inHashBuffer)) {
                $inHash = array_pop($inHashBuffer);
                if (isset($processedHashes[$inHash])) {
                    continue;
                }
                $processedHashes[$inHash] = true;
                $inRegExps = array_intersect($map[$inHash], $regExps);
                if (count($inRegExps) == 1) {
                    $inRegExp = $inRegExps[array_key_first($inRegExps)];
                    $visitedHashes[$inRegExp][] = $inHash;
                    continue;
                }
                array_push($inHashBuffer, ...($incomingTransitionsForHash[$inHash] ?? []));
            }
            $this->visitedHashMap[$mode][$stateId] = $visitedHashes;
        }

        return $dfa;
    }

    private function buildHash(int $stateIn, int $stateOut, int $symbol): string
    {
        return "{$stateIn}-{$stateOut}:{$symbol}";
    }

    /**
     * @param Nfa    $nfa
     * @param int    $entryState
     * @param string $regExp
     * @throws Exception
     */
    private function buildRegExp(Nfa $nfa, int $entryState, string $regExp): void
    {
        $buffer = CharBufferFactory::createFromString($regExp);
        $tree = new Tree();
        ParserFactory::createFromBuffer($tree, $buffer)->run();
        $nfaBuilder = new NfaBuilder($nfa, PropertyLoader::create());
        $nfaBuilder->setStartState($entryState);
        (new Translator($tree, $nfaBuilder))->run();
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			namespace Remorhaz\UniLex\Lexer;
6
7			use ReflectionException;
8			use Remorhaz\UniLex\AST\Translator;
9			use Remorhaz\UniLex\AST\Tree;
10			use Remorhaz\UniLex\Exception;
11			use Remorhaz\UniLex\RegExp\FSM\Dfa;
12			use Remorhaz\UniLex\RegExp\FSM\DfaBuilder;
13			use Remorhaz\UniLex\RegExp\FSM\Nfa;
14			use Remorhaz\UniLex\RegExp\FSM\NfaBuilder;
15			use Remorhaz\UniLex\RegExp\FSM\Range;
16			use Remorhaz\UniLex\RegExp\FSM\RangeSet;
17			use Remorhaz\UniLex\RegExp\FSM\TransitionMap;
18			use Remorhaz\UniLex\RegExp\ParserFactory;
19			use Remorhaz\UniLex\RegExp\PropertyLoader;
20			use Remorhaz\UniLex\Unicode\CharBufferFactory;
21			use Throwable;
22
23			use function array_diff;
24			use function array_intersect;
25			use function array_keys;
26			use function array_merge;
27			use function array_pop;
28			use function array_unique;
29			use function count;
30			use function implode;
31			use function in_array;
32			use function var_export;
33
34			class TokenMatcherGenerator
35			{
36
37			private $spec;
38
39			private $output;
40
41			private $dfa;
42
43			private $regExpMap = [];
44
45			private $visitedHashMap = [];
46
47			public function __construct(TokenMatcherSpec $spec)
48			{
49			$this->spec = $spec;
50			}
51
52			/**
53			* @return string
54			* @throws Exception
55			* @throws ReflectionException
56			*/
57			private function buildOutput(): string
58			{
59			return
60			"{$this->buildFileComment()}\ndeclare(strict_types=1);\n\n" .
61			"{$this->buildHeader()}\n" .
62			"class {$this->spec->getTargetShortName()} extends {$this->spec->getTemplateClass()->getShortName()}\n" .
63			"{\n" .
64			"\n" .
65			" public function match({$this->buildMatchParameters()}): bool\n" .
66			" {\n{$this->buildMatchBody()}" .
67			" }\n" .
68			"}\n";
69			}
70
71			/**
72			* @return TokenMatcherInterface
73			* @throws Exception
74			*/
75			public function load(): TokenMatcherInterface
76			{
77			$targetClass = $this->spec->getTargetClassName();
78			if (!class_exists($targetClass)) {
79			try {
80			$source = $this->getOutput(false);
81			eval($source);
			0 ignored issues – show introduced 2020-02-17 16:36 UTC by Report Bug Copy Issue Report The use of eval() is discouraged. Loading history...
82			} catch (Throwable $e) {
83			throw new Exception("Invalid PHP code generated", 0, $e);
84			}
85			if (!class_exists($targetClass)) {
86			throw new Exception("Failed to generate target class");
87			}
88			}
89
90			return new $targetClass();
91			}
92
93			/**
94			* @param bool $asFile
95			* @return string
96			* @throws Exception
97			* @throws ReflectionException
98			*/
99			public function getOutput(bool $asFile = true): string
100			{
101			if (!isset($this->output)) {
102			$this->output = $this->buildOutput();
103			}
104
105			return $asFile ? "<?php\n\n{$this->output}" : $this->output;
106			}
107
108			private function buildFileComment(): string
109			{
110			$content = $this->spec->getFileComment();
111			if ('' == $content) {
112			return '';
113			}
114			$comment = "/**\n";
115			$commentLineList = explode("\n", $content);
116			foreach ($commentLineList as $commentLine) {
117			$comment .= rtrim(" * {$commentLine}") . "\n";
118			}
119			$comment .= " */\n";
120
121			return $comment;
122			}
123
124			/**
125			* @return string
126			* @throws ReflectionException
127			*/
128			public function buildHeader(): string
129			{
130			$headerParts = [];
131			$namespace = $this->spec->getTargetNamespaceName();
132			if ($namespace != '') {
133			$headerParts[] = $this->buildMethodPart("namespace {$namespace};", 0);
134			}
135			$useList = $this->buildUseList();
136			if ('' != $useList) {
137			$headerParts[] = $useList;
138			}
139			$header = $this->buildMethodPart($this->spec->getHeader(), 0);
140			if ('' != $header) {
141			$headerParts[] = $header;
142			}
143
144			return implode("\n", $headerParts);
145			}
146
147			/**
148			* @return string
149			* @throws ReflectionException
150			*/
151			private function buildUseList(): string
152			{
153			$result = '';
154			foreach ($this->spec->getUsedClassList() as $alias => $className) {
155			$classWithAlias = is_string($alias) ? "{$className} {$alias}" : $className;
156			$result .= $this->buildMethodPart("use {$classWithAlias};", 0);
157			}
158
159			return $result;
160			}
161
162			/**
163			* @return string
164			* @throws ReflectionException
165			*/
166			private function buildMatchParameters(): string
167			{
168			$paramList = [];
169			foreach ($this->spec->getMatchMethod()->getParameters() as $matchParameter) {
170			if ($matchParameter->hasType()) {
171			$param = $matchParameter->getType()->isBuiltin()
172			? $matchParameter->getType()->getName()
173			: $matchParameter->getClass()->getShortName();
174			$param .= " ";
175			} else {
176			$param = "";
177			}
178			$param .= "\${$matchParameter->getName()}";
179			$paramList[] = $param;
180			}
181
182			return implode(", ", $paramList);
183			}
184
185			/**
186			* @return string
187			* @throws Exception
188			*/
189			private function buildMatchBody(): string
190			{
191			$result = $this->buildBeforeMatch();
192
193			foreach ($this->spec->getModeList() as $mode) {
194			if (TokenMatcherInterface::DEFAULT_MODE == $mode) {
195			continue;
196			}
197			$result .=
198			$this->buildMethodPart("if (\$context->getMode() == '{$mode}') {") .
199			$this->buildFsmEntry($mode, 3) .
200			$this->buildMethodPart("}");
201			}
202			foreach ($this->spec->getModeList() as $mode) {
203			if (TokenMatcherInterface::DEFAULT_MODE == $mode) {
204			$result .= $this->buildFsmEntry(TokenMatcherInterface::DEFAULT_MODE) . "\n";
205			}
206			$result .= $this->buildFsmMoves($mode);
207			}
208
209			$result .= $this->buildErrorState();
210
211			return $result;
212			}
213
214			private function buildBeforeMatch(): string
215			{
216			return
217			$this->buildMethodPart("\$context = \$this->createContext(\$buffer, \$tokenFactory);") .
218			$this->buildMethodPart($this->spec->getBeforeMatch());
219			}
220
221			/**
222			* @param string $mode
223			* @param int $indent
224			* @return string
225			* @throws Exception
226			*/
227			private function buildFsmEntry(string $mode, int $indent = 2): string
228			{
229			$state = $this->getDfa($mode)->getStateMap()->getStartState();
230
231			return $this->buildMethodPart("goto {$this->buildStateLabel('state', $mode, $state)};", $indent);
232			}
233
234			private function buildStateLabel(string $prefix, string $mode, int $state): string
235			{
236			$contextSuffix = TokenMatcherInterface::DEFAULT_MODE == $mode
237			? ''
238			: ucfirst($mode);
239
240			return "{$prefix}{$contextSuffix}{$state}";
241			}
242
243			/**
244			* @param string $mode
245			* @return string
246			* @throws Exception
247			*/
248			private function buildFsmMoves(string $mode): string
249			{
250			$result = '';
251			foreach ($this->getDfa($mode)->getStateMap()->getStateList() as $stateIn) {
252			if ($this->isFinishStateWithSingleEnteringTransition($mode, $stateIn)) {
253			continue;
254			}
255			$result .=
256			$this->buildStateEntry($mode, $stateIn) .
257			$this->buildStateTransitionList($mode, $stateIn) .
258			$this->buildStateFinish($mode, $stateIn);
259			}
260
261			return $result;
262			}
263
264			/**
265			* @param string $mode
266			* @param int $stateIn
267			* @return string
268			* @throws Exception
269			*/
270			private function buildStateEntry(string $mode, int $stateIn): string
271			{
272			$result = '';
273			$result .= $this->buildMethodPart("{$this->buildStateLabel('state', $mode, $stateIn)}:");
274			$moves = $this->getDfa($mode)->getTransitionMap()->getExitList($stateIn);
275			if (empty($moves)) {
276			return $result;
277			}
278			$result .= $this->buildMethodPart("if (\$context->getBuffer()->isEnd()) {");
279			$result .= $this->getDfa($mode)->getStateMap()->isFinishState($stateIn)
280			? $this->buildMethodPart("goto {$this->buildStateLabel('finish', $mode, $stateIn)};", 3)
281			: $this->buildMethodPart("goto error;", 3);
282			$result .=
283			$this->buildMethodPart("}") .
284			$this->buildMethodPart("\$char = \$context->getBuffer()->getSymbol();");
285
286			return $result;
287			}
288
289			/**
290			* @param string $mode
291			* @param int $stateIn
292			* @return string
293			* @throws Exception
294			*/
295			private function buildStateTransitionList(string $mode, int $stateIn): string
296			{
297			$result = '';
298			foreach ($this->getDfa($mode)->getTransitionMap()->getExitList($stateIn) as $stateOut => $symbolList) {
299			foreach ($symbolList as $symbol) {
300			$rangeSet = $this->getDfa($mode)->getSymbolTable()->getRangeSet($symbol);
301			$result .=
302			$this->buildMethodPart("if ({$this->buildRangeSetCondition($rangeSet)}) {") .
303			$this->buildOnTransition() .
304			$this->buildMethodPart("\$context->getBuffer()->nextSymbol();", 3) .
305			$this->buildMarkTransitionVisited($mode, $stateIn, $stateOut, $symbol, 3);
306			$result .= $this->isFinishStateWithSingleEnteringTransition($mode, $stateOut)
307			? $this->buildToken($mode, $stateOut, 3)
308			: $this->buildStateTransition($mode, $stateOut, 3);
309			$result .= $this->buildMethodPart("}");
310			}
311			}
312
313			return $result;
314			}
315
316			private function buildMarkTransitionVisited(
317			string $mode,
318			int $stateIn,
319			int $stateOut,
320			int $symbol,
321			int $indent = 3
322			): string {
323			$result = '';
324			$hash = $this->buildHash($stateIn, $stateOut, $symbol);
325			foreach ($this->visitedHashMap[$mode] ?? [] as $regExps) {
326			foreach ($regExps as $hashes) {
327			if (in_array($hash, $hashes)) {
328			$hashArg = var_export($hash, true);
329			$result .= $this->buildMethodPart("\$context->visitTransition({$hashArg});", $indent);
330			break 2;
331			}
332			}
333			}
334
335			return $result;
336			}
337
338			/**
339			* @param string $mode
340			* @param int $stateOut
341			* @param int $indent
342			* @return string
343			*/
344			private function buildStateTransition(string $mode, int $stateOut, int $indent = 3): string
345			{
346			return $this->buildMethodPart("goto {$this->buildStateLabel('state', $mode, $stateOut)};", $indent);
347			}
348
349			/**
350			* @param string $mode
351			* @param int $stateOut
352			* @return bool
353			* @throws Exception
354			*/
355			private function isFinishStateWithSingleEnteringTransition(string $mode, int $stateOut): bool
356			{
357			if (!$this->getDfa($mode)->getStateMap()->isFinishState($stateOut)) {
358			return false;
359			}
360			$enters = $this->getDfa($mode)->getTransitionMap()->getEnterList($stateOut);
361			$exits = $this->getDfa($mode)->getTransitionMap()->getExitList($stateOut);
362			if (!(count($enters) == 1 && count($exits) == 0)) {
363			return false;
364			}
365			$symbolList = array_pop($enters);
366
367			return count($symbolList) == 1;
368			}
369
370			private function buildHex(int $char): string
371			{
372			$hexChar = strtoupper(dechex($char));
373			if (strlen($hexChar) % 2 != 0) {
374			$hexChar = "0{$hexChar}";
375			}
376
377			return "0x{$hexChar}";
378			}
379
380			private function buildRangeCondition(Range $range): array
381			{
382			$startChar = $this->buildHex($range->getStart());
383			if ($range->getStart() == $range->getFinish()) {
384			return ["{$startChar} == \$char"];
385			}
386			$finishChar = $this->buildHex($range->getFinish());
387			if ($range->getStart() + 1 == $range->getFinish()) {
388			return [
389			"{$startChar} == \$char",
390			"{$finishChar} == \$char",
391			];
392			}
393
394			return ["{$startChar} <= \$char && \$char <= {$finishChar}"];
395			}
396
397			private function buildRangeSetCondition(RangeSet $rangeSet): string
398			{
399			$conditionList = [];
400			foreach ($rangeSet->getRanges() as $range) {
401			$conditionList = array_merge($conditionList, $this->buildRangeCondition($range));
402			}
403			$result = implode(" \|\| ", $conditionList);
404			if (strlen($result) + 15 <= 120 \|\| count($conditionList) == 1) {
405			return ltrim($result);
406			}
407			$result = $this->buildMethodPart(implode(" \|\|\n", $conditionList), 1);
408
409			return "\n " . ltrim($result);
410			}
411
412			/**
413			* @param string $mode
414			* @param int $stateIn
415			* @return string
416			* @throws Exception
417			*/
418			private function buildStateFinish(string $mode, int $stateIn): string
419			{
420			if (!$this->getDfa($mode)->getStateMap()->isFinishState($stateIn)) {
421			return $this->buildMethodPart("goto error;\n");
422			}
423			$result = '';
424			if (!empty($this->getDfa($mode)->getTransitionMap()->getExitList($stateIn))) {
425			$result .= $this->buildMethodPart("{$this->buildStateLabel('finish', $mode, $stateIn)}:");
426			}
427			$result .= "{$this->buildToken($mode, $stateIn)}\n";
428
429			return $result;
430			}
431
432			/**
433			* @param string $mode
434			* @param int $stateIn
435			* @param int $indent
436			* @return string
437			* @throws Exception
438			*/
439			private function buildToken(string $mode, int $stateIn, int $indent = 2): string
440			{
441			$result = '';
442			$regExpCount = 0;
443			foreach ($this->visitedHashMap[$mode][$stateIn] ?? [] as $regExp => $visitedHashes) {
444			if (empty($visitedHashes)) {
445			throw new Exception("Empty tokens are not allowed");
446			}
447			$visitedHashValues = [];
448			foreach ($visitedHashes as $visitedHash) {
449			$visitedHashValues[] = var_export($visitedHash, true);
450			}
451			$visitedHashArgs = implode(', ', $visitedHashValues);
452			$tokenSpec = $this->spec->getTokenSpec($mode, (string) $regExp);
453			$result .=
454			$this->buildMethodPart("if (\$context->isVisitedTransition({$visitedHashArgs})) {", $indent) .
455			$this->buildMethodPart("// {$regExp}", $indent + 1) .
456			$this->buildSingleToken($tokenSpec, $indent + 1) .
457			$this->buildMethodPart("}", $indent);
458			$regExpCount++;
459			}
460
461			if (0 == $regExpCount) {
462			throw new Exception("No tokens found for state {$stateIn}");
463			}
464
465			return
466			$result .
467			$this->buildMethodPart("goto error;", $indent);
468			}
469
470			private function buildSingleToken(TokenSpec $tokenSpec, int $indent): string
471			{
472			return
473			$this->buildMethodPart($tokenSpec->getCode(), $indent) .
474			$this->buildOnToken($indent) . "\n" .
475			$this->buildMethodPart("return true;", $indent);
476			}
477
478			private function buildErrorState(): string
479			{
480			$code = $this->spec->getOnError();
481
482			return
483			$this->buildMethodPart("error:") .
484			$this->buildMethodPart('' == $code ? "return false;" : $code);
485			}
486
487			private function buildMethodPart(string $code, int $indent = 2): string
488			{
489			if ('' == $code) {
490			return '';
491			}
492			$result = '';
493			$codeLineList = explode("\n", $code);
494			foreach ($codeLineList as $codeLine) {
495			$line = '';
496			for ($i = 0; $i < $indent; $i++) {
497			$line .= " ";
498			}
499			$result .= rtrim($line . $codeLine) . "\n";
500			}
501
502			return $result;
503			}
504
505			private function buildOnTransition(): string
506			{
507			return $this->buildMethodPart($this->spec->getOnTransition(), 3);
508			}
509
510			private function buildOnToken(int $indent = 2): string
511			{
512			return $this->buildMethodPart($this->spec->getOnToken(), $indent);
513			}
514
515			/**
516			* @param string $context
517			* @return Dfa
518			* @throws Exception
519			*/
520			private function getDfa(string $context): Dfa
521			{
522			if (!isset($this->dfa[$context])) {
523			$this->dfa[$context] = $this->buildDfa($context);
524			}
525
526			return $this->dfa[$context];
527			}
528
529			/**
530			* @param string $mode
531			* @return Dfa
532			* @throws Exception
533			*/
534			private function buildDfa(string $mode): Dfa
535			{
536			$nfa = new Nfa();
537			$startState = $nfa->getStateMap()->createState();
538			$nfa->getStateMap()->addStartState($startState);
539			$nfaRegExpMap = [];
540			foreach ($this->spec->getTokenSpecList($mode) as $tokenSpec) {
541			$existingStates = $nfa->getStateMap()->getStateList();
542			$regExpEntryState = $nfa->getStateMap()->createState();
543			$nfa
544			->getEpsilonTransitionMap()
545			->addTransition($startState, $regExpEntryState, true);
546			$this->buildRegExp($nfa, $regExpEntryState, $tokenSpec->getRegExp());
547			$nfaRegExpMap[$tokenSpec->getRegExp()] = array_diff(
548			$nfa->getStateMap()->getStateList(),
549			$existingStates
550			);
551			}
552
553			$dfa = DfaBuilder::fromNfa($nfa);
554			$dfaRegExpMap = [];
555			foreach (array_keys($nfaRegExpMap, null, true) as $regExp) {
556			$dfaRegExpMap[$regExp] = [];
557			}
558			$allDfaStateIds = $dfa->getStateMap()->getStateList();
559			foreach ($allDfaStateIds as $dfaStateId) {
560			$nfaStateIds = $dfa->getStateMap()->getStateValue($dfaStateId);
561			foreach ($nfaRegExpMap as $regExp => $nfaRegExpStateIds) {
562			if (!empty(array_intersect($nfaStateIds, $nfaRegExpStateIds))) {
563			$dfaRegExpMap[(string) $regExp][] = $dfaStateId; // TODO: why the hell integer?..
564			}
565			}
566			}
567			$this->regExpMap[$mode] = [];
568			foreach ($dfaRegExpMap as $regExp => $regExpStateIds) {
569			$this->regExpMap[$mode][(string) $regExp] = [$regExpStateIds, array_diff($allDfaStateIds, $regExpStateIds)];
570			}
571			$nfaRegExpTransitionMap = new TransitionMap($nfa->getStateMap());
572			foreach ($nfa->getSymbolTransitionMap()->getTransitionList() as $nfaSourceStateId => $nfaTransitionTargets) {
573			foreach ($nfaTransitionTargets as $nfaTargetStateId => $nfaSymbolIds) {
574			$regExps = [];
575			foreach ($nfaRegExpMap as $regExp => $nfaRegExpIds) {
576			if (in_array($nfaSourceStateId, $nfaRegExpIds) \|\| in_array($nfaTargetStateId, $nfaRegExpIds)) {
577			$regExps[] = (string) $regExp;
578			}
579			}
580			$nfaTransitionValue = [];
581			foreach ($nfaSymbolIds as $nfaSymbolId) {
582			$nfaTransitionValue[$nfaSymbolId] = $regExps;
583			}
584			$nfaRegExpTransitionMap->addTransition($nfaSourceStateId, $nfaTargetStateId, $nfaTransitionValue);
585			}
586			}
587
588			$map = [];
589			$mapIn = [];
590			$mapOut = [];
591			foreach ($dfa->getTransitionMap()->getTransitionList() as $dfaSourceStateId => $dfaTransitionTargets) {
592			foreach ($dfaTransitionTargets as $dfaTargetStateId => $dfaSymbolIds) {
593			$matchingNfaSourceStateIds = $dfa->getStateMap()->getStateValue($dfaSourceStateId);
594			$matchingNfaTargetStateIds = $dfa->getStateMap()->getStateValue($dfaTargetStateId);
595			$dfaTransitionValue = [];
596			foreach ($matchingNfaSourceStateIds as $nfaSourceStateId) {
597			foreach ($matchingNfaTargetStateIds as $nfaTargetStateId) {
598			if (
599			$nfa->getStateMap()->stateExists($nfaSourceStateId) && // TODO: find out invalid id
600			$nfa->getStateMap()->stateExists($nfaTargetStateId) &&
601			$nfaRegExpTransitionMap->transitionExists($nfaSourceStateId, $nfaTargetStateId)
602			) {
603			$nfaTransitionValue = $nfaRegExpTransitionMap->getTransition(
604			$nfaSourceStateId,
605			$nfaTargetStateId
606			);
607			foreach ($dfaSymbolIds as $dfaSymbolId) {
608			if (isset($nfaTransitionValue[$dfaSymbolId])) {
609			$dfaTransitionValue[$dfaSymbolId] = array_unique(
610			array_merge(
611			$dfaTransitionValue[$dfaSymbolId] ?? [],
612			$nfaTransitionValue[$dfaSymbolId]
613			)
614			);
615			}
616			}
617			}
618			}
619			}
620			foreach ($dfaTransitionValue as $dfaSymbolId => $regExps) {
621			$hash = $this->buildHash($dfaSourceStateId, $dfaTargetStateId, $dfaSymbolId);
622			$map[$hash] = $regExps;
623			$mapIn[$dfaSourceStateId] = array_merge($mapIn[$dfaSourceStateId] ?? [], [$hash]);
624			$mapOut[$dfaTargetStateId] = array_merge($mapOut[$dfaTargetStateId] ?? [], [$hash]);
625			}
626			}
627			}
628			$incomingTransitionsForHash = [];
629			$incomingTransitionsForState = [];
630			foreach ($mapIn as $stateId => $hashes) {
631			foreach ($hashes as $hash) {
632			$incomingTransitionsForHash[$hash] = $mapOut[$stateId] ?? [];
633			}
634			}
635			foreach (array_keys($mapOut) as $stateId) {
636			if ($dfa->getStateMap()->isFinishState($stateId)) {
637			$incomingTransitionsForState[$stateId] = $mapOut[$stateId] ?? [];
638			}
639			}
640			$this->visitedHashMap[$mode] = [];
641			foreach ($incomingTransitionsForState as $stateId => $hashes) {
642			$inHashBuffer = $hashes;
643			$processedHashes = [];
644			$visitedHashes = [];
645			$regExps = [];
646			foreach ($hashes as $hash) {
647			$regExps = array_unique(array_merge($regExps, $map[$hash]));
648			}
649			while (!empty($inHashBuffer)) {
650			$inHash = array_pop($inHashBuffer);
651			if (isset($processedHashes[$inHash])) {
652			continue;
653			}
654			$processedHashes[$inHash] = true;
655			$inRegExps = array_intersect($map[$inHash], $regExps);
656			if (count($inRegExps) == 1) {
657			$inRegExp = $inRegExps[array_key_first($inRegExps)];
658			$visitedHashes[$inRegExp][] = $inHash;
659			continue;
660			}
661			array_push($inHashBuffer, ...($incomingTransitionsForHash[$inHash] ?? []));
662			}
663			$this->visitedHashMap[$mode][$stateId] = $visitedHashes;
664			}
665
666			return $dfa;
667			}
668
669			private function buildHash(int $stateIn, int $stateOut, int $symbol): string
670			{
671			return "{$stateIn}-{$stateOut}:{$symbol}";
672			}
673
674			/**
675			* @param Nfa $nfa
676			* @param int $entryState
677			* @param string $regExp
678			* @throws Exception
679			*/
680			private function buildRegExp(Nfa $nfa, int $entryState, string $regExp): void
681			{
682			$buffer = CharBufferFactory::createFromString($regExp);
683			$tree = new Tree();
684			ParserFactory::createFromBuffer($tree, $buffer)->run();
685			$nfaBuilder = new NfaBuilder($nfa, PropertyLoader::create());
686			$nfaBuilder->setStartState($entryState);
687			(new Translator($tree, $nfaBuilder))->run();
688			}
689			}
690

remorhaz / php-unilex

Push — master ( 93b753...7b55bb )

TokenMatcherGenerator::buildOnTransition() A

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like