TokenMatcherGenerator::buildStateTransition() - Code Metrics - Inspection of "Token matchers use built over minimized DFA" - remorhaz/php-unilex - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Push — master ( c01dfe...f39ce2 )

by Edward

created 2020-04-07 11:27 UTC

TokenMatcherGenerator::buildStateTransition() B

↳ Parent: TokenMatcherGenerator

Complexity

Conditions	9
Paths	6

Size

Total Lines	41
Code Lines	25

Duplication

Lines	0
Ratio	0 %

Importance

Changes

Metric	Value
cc	9
eloc	25
nc	6
nop	5
dl	0
loc	41
rs	8.0555
c	0
b	0
f	0

<?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_key_last;
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;

    /**
     * @var TokenSpec[]
     */
    private $tokenNfaStateMap = [];

    private $regExpMap = [];

    private $dfaRegExpTransitionMap;

    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
    {
        $code = $this->spec->getBeforeMatch();

        return
            $this->buildMethodPart("\$context = \$this->createContext(\$buffer, \$tokenFactory);") .
            $this->buildMethodPart($code);
    }

    /**
     * @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();
        $result = $this->buildMethodPart("\$context->setRegExps(", $indent);
        $tokenSpecList = $this->spec->getTokenSpecList($mode);
        $lastTokenKey = array_key_last($tokenSpecList);
        foreach ($tokenSpecList as $tokenKey => $tokenSpec) {
            $regExpValue = var_export($tokenSpec->getRegExp(), true);
            $regExpArg = $tokenKey === $lastTokenKey ? $regExpValue : "{$regExpValue},";
            $result .= $this->buildMethodPart($regExpArg, $indent + 1);
        }
        $result .= $this->buildMethodPart(");");

        return
            $result .
            $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);
                $result .= $this->isFinishStateWithSingleEnteringTransition($mode, $stateOut)
                    ? $this->buildToken($mode, $stateOut, 3)
                    : $this->buildStateTransition($mode, $stateIn, $stateOut, $symbol, 3);
                $result .= $this->buildMethodPart("}");
            }
        }

        return $result;
    }

    /**
     * @param string $mode
     * @param int    $stateIn
     * @param int    $stateOut
     * @param int    $symbol
     * @param int    $indent
     * @return string
     * @throws Exception
     */
    private function buildStateTransition(
        string $mode,
        int $stateIn,
        int $stateOut,
        int $symbol,
        int $indent = 3
    ): string {
        $transitionMap = $this->getRegExpTransitionMap();
        $result = '';
        if ($transitionMap->transitionExists($stateIn, $stateOut)) {
            $transitionValue = $transitionMap->getTransition($stateIn, $stateOut);
            foreach ($transitionValue as $transitionSymbol => $regExps) {
                if ($transitionSymbol == $symbol) {
                    if (empty($regExps)) {
                        throw new Exception("No target regular expressions");
                    }
                    $regExpValues = [];
                    foreach ($regExps as $regExp) {
                        $regExpValues[] = var_export($regExp, true);
                    }
                    if (count($regExps) == 1) {
                        $regExpArgs = array_pop($regExpValues);
                        $result .= $this->buildMethodPart("\$context->allowRegExps({$regExpArgs});", $indent);
                        break;
                    }
                    $lastValueKey = array_key_last($regExpValues);
                    $result .= $this->buildMethodPart("\$context->allowRegExps(", $indent);
                    foreach ($regExpValues as $valueKey => $regExpValue) {
                        $result .= $this->buildMethodPart(
                            $lastValueKey === $valueKey ? $regExpValue : "{$regExpValue},",
                            $indent + 1
                        );
                    }
                    $result .= $this->buildMethodPart(");", $indent);
                }
            }
        }

        return
            $result .
            $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 = $this->buildMethodPart("switch (\$context->getRegExp()) {");
        foreach ($this->regExpMap as $regExp => [$allowedStateIds, $forbiddenStateIds]) {
            if (!in_array($stateIn, $allowedStateIds)) {
                continue;
            }
            $tokenSpec = $this->spec->getTokenSpec($mode, (string) $regExp);
            $regExpArg = var_export($tokenSpec->getRegExp(), true);
            $result .=
                $this->buildMethodPart("case {$regExpArg}:", $indent + 1) .
                $this->buildSingleToken($tokenSpec, $indent + 2);
        }

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

        return
            $result .
            $this->buildMethodPart("default:", $indent + 1) .
            $this->buildMethodPart("goto error;", $indent + 2) .
            $this->buildMethodPart("}", $indent);
    }

    private function buildSingleToken(TokenSpec $tokenSpec, int $indent): string
    {
        return
            $this->buildMethodPart($tokenSpec->getCode(), $indent) .
            $this->buildOnToken($indent) . "\n" .
            $this->buildMethodPart("return true;\n", $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 $context
     * @return Dfa
     * @throws Exception
     */
    private function buildDfa(string $context): Dfa
    {
        $nfa = new Nfa();
        $startState = $nfa->getStateMap()->createState();
        $nfa->getStateMap()->addStartState($startState);
        $nfaRegExpMap = [];
        $this->tokenNfaStateMap[$context] = [];
        foreach ($this->spec->getTokenSpecList($context) 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?..
                }
            }
        }
        foreach ($dfaRegExpMap as $regExp => $regExpStateIds) {
            $this->regExpMap[(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);
            }
        }

        $this->dfaRegExpTransitionMap = new TransitionMap($dfa->getStateMap());
        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]
                                        )
                                    );
                                }
                            }
                        }
                    }
                }
                $this->dfaRegExpTransitionMap->addTransition($dfaSourceStateId, $dfaTargetStateId, $dfaTransitionValue);
            }
        }

        return $dfa;
    }

    /**
     * @return TransitionMap
     * @throws Exception
     */
    private function getRegExpTransitionMap(): TransitionMap
    {
        if (isset($this->dfaRegExpTransitionMap)) {
            return $this->dfaRegExpTransitionMap;
        }

        throw new Exception("Regular expression transition map not defined");
    }

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

remorhaz / php-unilex

Push — master ( c01dfe...f39ce2 )

TokenMatcherGenerator::buildStateTransition() B

Complexity

Size

Duplication

Importance

Duplication Side-by-Side

Filter issues like