FormulaParser::reduce() - Code Metrics - Inspection of "Implement a configurable parser" - Smoren/formula-tools-php - Measure and Improve Code Quality continuously with Scrutinizer

Passed

Pull Request — master (#1)

unknown

created 2023-02-10 09:26 UTC

FormulaParser::reduce() A

↳ Parent: FormulaParser

Complexity

Conditions	4
Paths	4

Size

Total Lines	20
Code Lines	13

Duplication

Lines	0
Ratio	0 %

Code Coverage

Tests	0
CRAP Score	20

Importance

Changes	1
Bugs	0	Features	0

Metric	Value
cc	4
eloc	13
c	1
b	0
f	0
nc	4
nop	1
dl	0
loc	20
ccs	0
cts	13
cp	0
crap	20
rs	9.8333

<?php

declare(strict_types=1);

namespace Smoren\FormulaTools\V2;

use Smoren\FormulaTools\V2\Exceptions\{
    EmptyStreamException,
    MissingOperandException,
    MissingOperatorException,
    OpAssociationException,
    UnclosedBracketException,
};
use Smoren\FormulaTools\V2\Interfaces\{
    IBinaryOpAcceptor,
    IBinaryOpFactory,
    IDialect,
filter:
    dependency_paths: ["lib/*"]
    IOpDefinition,
    IParser,
    IUnaryOpAcceptor,
    IUnaryOpFactory,
};

/**
 * @template Token
 * @template Result
 * @implements IParser<Token, Result>
 */
class FormulaParser implements IParser
{
    /** @var IDialect<Token, Result> */
    protected IDialect $dialect;
    protected int $position = 0;
    /** @var Result[] */
    protected array $resultStack = [];
    /** @var (IOpDefinition | IUnaryOpAcceptor<Token, Result>)[] */

    protected array $opStack = [];
    /** @var (IUnaryOpAcceptor<Token, Result> | IBinaryOpAcceptor<Token, Result>)[] */

    protected array $acceptorStack = [];

    /**
     * @param IDialect<Token, Result> $dialect
     */
    public function __construct(IDialect $dialect)
    {
        $this->dialect = $dialect;
    }

    public function getDialect(): IDialect
    {
        return $this->dialect;
    }

    public function setDialect(IDialect $dialect)
    {
        $this->dialect = $dialect;
    }

    public function getPosition(): int
    {
        return $this->position;
    }

    /**
     * @param IOpDefinition | IUnaryOpAcceptor<Token, Result> $op
     * @param int $followingPrecedence
     * @return bool
     * @phpstan-assert-if-true IUnaryOpFactory<Result> | IBinaryOpFactory<Result> $op
     */
    protected function shouldReduce($op, int $followingPrecedence): bool
    {
        if (!($op instanceof IUnaryOpFactory || $op instanceof IBinaryOpFactory)) {
            return false;
        }
        $prec = $op->getRightPrecedence();
        if ($prec !== $followingPrecedence) {
            return $prec > $followingPrecedence;
        }
        // An attempt to reduce a non-associative operator.
        throw new OpAssociationException($op, $this->position);
    }

    protected function reduce(int $followingPrecedence): void
    {
        $i = count($this->resultStack) - 1; // `i` always equals the index of the last node.
        for ($opIndex = count($this->opStack); $opIndex--;) {
            $op = $this->opStack[$opIndex];
            if (!$this->shouldReduce($op, $followingPrecedence)) {
                return; // Reduction stops here.
            }

            // Perform one step of reduction.
            array_pop($this->opStack);
            if ($op instanceof IUnaryOpFactory) {
                // Reduce a unary operator.
                $this->resultStack[$i] = $op->create($this->resultStack[$i]);
            } else {
                // Reduce a binary operator.
                assert(count($this->resultStack) >= 2);
                $rhs = array_pop($this->resultStack);
                $i--;
                $this->resultStack[$i] = $op->create($this->resultStack[$i], $rhs);
            }
        }
    }

    /**
     * @param Token $token
filter:
    dependency_paths: ["lib/*"]
     * @return bool
     */
    protected function acceptTerm($token): bool
    {
        $op = $this->dialect->acceptPrefixOrCircumfixOp($token, $this);
        if ($op === null) {
            // Not an operator - try to parse a term and push it onto the result stack.
            // This call may throw.
            $this->resultStack[] = $this->dialect->parseTerm($token, $this);
            return true;
        }

        if ($op instanceof IUnaryOpFactory) {
            $this->reduce($op->getLeftPrecedence()); // Check for non-associative operators.
        } else {
            $this->acceptorStack[] = $op; // Push the circumfix operator onto its stack.
        }
        // Push the unary/circumfix operator onto the operator stack.
        $this->opStack[] = $op;
        return false;
    }

    /**
     * @param Token $token
     * @return bool
     */
    protected function finishCircumfixOp($token): bool
    {
        if (!(bool)$this->acceptorStack) {
            return false;
        }
        // Check the token with the most deeply nested operator.
        $factory = $this->acceptorStack[count($this->acceptorStack) - 1]->accept($token);
        if ($factory === null) {
            return false;
        }

        // `token` is the second part of the *circumfix operator seen earlier.
        $this->reduce(PHP_INT_MIN); // Reduce the contained operand.
        $op = array_pop($this->opStack);
        array_pop($this->acceptorStack);
        if ($op instanceof IBinaryOpAcceptor) {
            assert(count($this->resultStack) >= 2);
            $rhs = array_pop($this->resultStack);
            $this->reduce($op->getLeftPrecedence()); // Reduce the left-hand-side operand.
            // We cannot reduce the postcircumfix operator right now because we need to check that
            // the operator that follows it respects associativity rules. So we push
            // the right-hand-side operand back onto the stack and create a stub binary operator
            // that remembers our right precedence.
            $this->resultStack[] = $rhs;
            $this->opStack[] = new class ($op->getRightPrecedence(), $factory) implements IBinaryOpFactory {
                private int $precedence;
                /** @var callable(Result, Result): Result */
                private $factory;

                /**
                 * @param int $precedence
                 * @param callable(Result, Result): Result $factory
                 */
                public function __construct(int $precedence, callable $factory)
                {
                    $this->precedence = $precedence;
                    $this->factory = $factory;
                }

                public function getLeftPrecedence(): int
                {
                    throw new \LogicException("Unreachable");
                }

                public function getRightPrecedence(): int
                {
                    return $this->precedence;
                }

                public function create($lhs, $rhs)
                {
                    return ($this->factory)($lhs, $rhs);
                }
            };
        } else {
            // A circumfix operator does not have precedence. Reduce it right away.
            $i = count($this->resultStack) - 1;
            /** @var callable(Result): Result $factory */
            $this->resultStack[$i] = $factory($this->resultStack[$i]);
        }
        return true;
    }

    /**
     * @param Token $token
     * @return bool
     */
    protected function acceptBinaryOp($token): bool
    {
        // The second part of a *circumfix operator should be prioritized over a binary or postfix
        // operator, otherwise the former would be irreducible at all.
        if ($this->finishCircumfixOp($token)) {
            return false;
        }

        $op = $this->dialect->acceptPostfixOrInfixOp($token, $this);
        if ($op !== null) {
            $this->reduce($op->getLeftPrecedence()); // Reduce its left-hand-side operand.
            $this->opStack[] = $op;
            if ($op instanceof IBinaryOpAcceptor) {
                $this->acceptorStack[] = $op;
                return true; // It is binary.
            }
            return $op instanceof IBinaryOpFactory;
        }

        // We failed to recognize a binary operator in this dialect. Try juxtaposition if defined.
        $op = $this->dialect->getJuxtapositionOp($this);
        if ($op !== null) {
            $this->reduce($op->getLeftPrecedence()); // Reduce its left-hand-side operand.
            $this->opStack[] = $op;
            // If `token` is a term, then we should be waiting for another binary operator,
            // and vice versa.
            return !$this->acceptTerm($token);
        }
        throw new MissingOperatorException($token, $this->position);
    }

    /**
     * @param iterable<Token> $tokens
     * @return Result
filter:
    dependency_paths: ["lib/*"]
     */
    public function parse(iterable $tokens)
    {
        assert(!(bool)$this->resultStack); // We are not reenterable.
        assert(!(bool)$this->opStack);
        $waitingForTerm = true;
        try {
            foreach ($tokens as $this->position => $token) {
                if ($waitingForTerm) {
                    if ($this->acceptTerm($token)) {
                        $waitingForTerm = false;
                    }
                } elseif ($this->acceptBinaryOp($token)) {
                    $waitingForTerm = true;
                }
            }

            if ($waitingForTerm) {
                throw count($this->resultStack) === 0 ? (
                    new EmptyStreamException()
                ) : new MissingOperandException();
            }
            $this->reduce(PHP_INT_MIN);
            if ((bool)$this->opStack) {
                throw new UnclosedBracketException();
            }
        } catch (\Throwable $e) {
            $this->resultStack = []; // Break a possible reference cycle.
            $this->opStack = [];
            $this->acceptorStack = [];
            throw $e;
        }

        assert(count($this->resultStack) === 1);
        return array_pop($this->resultStack);
    }
}


1			<?php
2
3			declare(strict_types=1);
4
5			namespace Smoren\FormulaTools\V2;
6
7			use Smoren\FormulaTools\V2\Exceptions\{
8			EmptyStreamException,
9			MissingOperandException,
10			MissingOperatorException,
11			OpAssociationException,
12			UnclosedBracketException,
13			};
14			use Smoren\FormulaTools\V2\Interfaces\{
15			IBinaryOpAcceptor,
16			IBinaryOpFactory,
17			IDialect,
			0 ignored issues – show Bug introduced 2023-02-10 08:29 UTC by Report Bug Copy Issue Report The type `Smoren\FormulaTools\V2\Interfaces\IDialect` was not found. Maybe you did not declare it correctly or list all dependencies? The issue could also be caused by a filter entry in the build configuration. If the path has been excluded in your configuration, e.g. `excluded_paths: ["lib/"]`, you can move it to the dependency path list as follows: filter: dependency_paths: ["lib/"] For further information see https://scrutinizer-ci.com/docs/tools/php/php-scrutinizer/#list-dependency-paths Loading history...
18			IOpDefinition,
19			IParser,
20			IUnaryOpAcceptor,
21			IUnaryOpFactory,
22			};
23
24			/**
25			* @template Token
26			* @template Result
27			* @implements IParser<Token, Result>
28			*/
29			class FormulaParser implements IParser
30			{
31			/** @var IDialect<Token, Result> */
32			protected IDialect $dialect;
33			protected int $position = 0;
34			/** @var Result[] */
35			protected array $resultStack = [];
36			/** @var (IOpDefinition \| IUnaryOpAcceptor<Token, Result>)[] */
			0 ignored issues – show Documentation Bug introduced 2023-02-10 08:29 UTC by Report Bug Copy Issue Report The doc comment `(IOpDefinition \| IUnaryO...eptor<Token, Result>)[]` at position `3` could not be parsed: Expected ')' at position 3, but found 'IUnaryOpAcceptor'. Loading history...
37			protected array $opStack = [];
38			/** @var (IUnaryOpAcceptor<Token, Result> \| IBinaryOpAcceptor<Token, Result>)[] */
			0 ignored issues – show Documentation Bug introduced 2023-02-10 08:29 UTC by Report Bug Copy Issue Report The doc comment `(IUnaryOpAcceptor<Token,...eptor<Token, Result>)[]` at position `1` could not be parsed: Expected ')' at position 1, but found 'IUnaryOpAcceptor'. Loading history...
39			protected array $acceptorStack = [];
40
41			/**
42			* @param IDialect<Token, Result> $dialect
43			*/
44			public function __construct(IDialect $dialect)
45			{
46			$this->dialect = $dialect;
47			}
48
49			public function getDialect(): IDialect
50			{
51			return $this->dialect;
52			}
53
54			public function setDialect(IDialect $dialect)
55			{
56			$this->dialect = $dialect;
57			}
58
59			public function getPosition(): int
60			{
61			return $this->position;
62			}
63
64			/**
65			* @param IOpDefinition \| IUnaryOpAcceptor<Token, Result> $op
66			* @param int $followingPrecedence
67			* @return bool
68			* @phpstan-assert-if-true IUnaryOpFactory<Result> \| IBinaryOpFactory<Result> $op
69			*/
70			protected function shouldReduce($op, int $followingPrecedence): bool
71			{
72			if (!($op instanceof IUnaryOpFactory \|\| $op instanceof IBinaryOpFactory)) {
73			return false;
74			}
75			$prec = $op->getRightPrecedence();
76			if ($prec !== $followingPrecedence) {
77			return $prec > $followingPrecedence;
78			}
79			// An attempt to reduce a non-associative operator.
80			throw new OpAssociationException($op, $this->position);
81			}
82
83			protected function reduce(int $followingPrecedence): void
84			{
85			$i = count($this->resultStack) - 1; // `i` always equals the index of the last node.
86			for ($opIndex = count($this->opStack); $opIndex--;) {
87			$op = $this->opStack[$opIndex];
88			if (!$this->shouldReduce($op, $followingPrecedence)) {
89			return; // Reduction stops here.
90			}
91
92			// Perform one step of reduction.
93			array_pop($this->opStack);
94			if ($op instanceof IUnaryOpFactory) {
95			// Reduce a unary operator.
96			$this->resultStack[$i] = $op->create($this->resultStack[$i]);
97			} else {
98			// Reduce a binary operator.
99			assert(count($this->resultStack) >= 2);
100			$rhs = array_pop($this->resultStack);
101			$i--;
102			$this->resultStack[$i] = $op->create($this->resultStack[$i], $rhs);
103			}
104			}
105			}
106
107			/**
108			* @param Token $token
			0 ignored issues – show Bug introduced 2023-02-10 08:29 UTC by Report Bug Copy Issue Report The type `Smoren\FormulaTools\V2\Token` was not found. Maybe you did not declare it correctly or list all dependencies? The issue could also be caused by a filter entry in the build configuration. If the path has been excluded in your configuration, e.g. `excluded_paths: ["lib/"]`, you can move it to the dependency path list as follows: filter: dependency_paths: ["lib/"] For further information see https://scrutinizer-ci.com/docs/tools/php/php-scrutinizer/#list-dependency-paths Loading history...
109			* @return bool
110			*/
111			protected function acceptTerm($token): bool
112			{
113			$op = $this->dialect->acceptPrefixOrCircumfixOp($token, $this);
114			if ($op === null) {
115			// Not an operator - try to parse a term and push it onto the result stack.
116			// This call may throw.
117			$this->resultStack[] = $this->dialect->parseTerm($token, $this);
118			return true;
119			}
120
121			if ($op instanceof IUnaryOpFactory) {
122			$this->reduce($op->getLeftPrecedence()); // Check for non-associative operators.
123			} else {
124			$this->acceptorStack[] = $op; // Push the circumfix operator onto its stack.
125			}
126			// Push the unary/circumfix operator onto the operator stack.
127			$this->opStack[] = $op;
128			return false;
129			}
130
131			/**
132			* @param Token $token
133			* @return bool
134			*/
135			protected function finishCircumfixOp($token): bool
136			{
137			if (!(bool)$this->acceptorStack) {
138			return false;
139			}
140			// Check the token with the most deeply nested operator.
141			$factory = $this->acceptorStack[count($this->acceptorStack) - 1]->accept($token);
142			if ($factory === null) {
143			return false;
144			}
145
146			// `token` is the second part of the *circumfix operator seen earlier.
147			$this->reduce(PHP_INT_MIN); // Reduce the contained operand.
148			$op = array_pop($this->opStack);
149			array_pop($this->acceptorStack);
150			if ($op instanceof IBinaryOpAcceptor) {
151			assert(count($this->resultStack) >= 2);
152			$rhs = array_pop($this->resultStack);
153			$this->reduce($op->getLeftPrecedence()); // Reduce the left-hand-side operand.
154			// We cannot reduce the postcircumfix operator right now because we need to check that
155			// the operator that follows it respects associativity rules. So we push
156			// the right-hand-side operand back onto the stack and create a stub binary operator
157			// that remembers our right precedence.
158			$this->resultStack[] = $rhs;
159			$this->opStack[] = new class ($op->getRightPrecedence(), $factory) implements IBinaryOpFactory {
160			private int $precedence;
161			/** @var callable(Result, Result): Result */
162			private $factory;
163
164			/**
165			* @param int $precedence
166			* @param callable(Result, Result): Result $factory
167			*/
168			public function __construct(int $precedence, callable $factory)
169			{
170			$this->precedence = $precedence;
171			$this->factory = $factory;
172			}
173
174			public function getLeftPrecedence(): int
175			{
176			throw new \LogicException("Unreachable");
177			}
178
179			public function getRightPrecedence(): int
180			{
181			return $this->precedence;
182			}
183
184			public function create($lhs, $rhs)
185			{
186			return ($this->factory)($lhs, $rhs);
187			}
188			};
189			} else {
190			// A circumfix operator does not have precedence. Reduce it right away.
191			$i = count($this->resultStack) - 1;
192			/** @var callable(Result): Result $factory */
193			$this->resultStack[$i] = $factory($this->resultStack[$i]);
194			}
195			return true;
196			}
197
198			/**
199			* @param Token $token
200			* @return bool
201			*/
202			protected function acceptBinaryOp($token): bool
203			{
204			// The second part of a *circumfix operator should be prioritized over a binary or postfix
205			// operator, otherwise the former would be irreducible at all.
206			if ($this->finishCircumfixOp($token)) {
207			return false;
208			}
209
210			$op = $this->dialect->acceptPostfixOrInfixOp($token, $this);
211			if ($op !== null) {
212			$this->reduce($op->getLeftPrecedence()); // Reduce its left-hand-side operand.
213			$this->opStack[] = $op;
214			if ($op instanceof IBinaryOpAcceptor) {
215			$this->acceptorStack[] = $op;
216			return true; // It is binary.
217			}
218			return $op instanceof IBinaryOpFactory;
219			}
220
221			// We failed to recognize a binary operator in this dialect. Try juxtaposition if defined.
222			$op = $this->dialect->getJuxtapositionOp($this);
223			if ($op !== null) {
224			$this->reduce($op->getLeftPrecedence()); // Reduce its left-hand-side operand.
225			$this->opStack[] = $op;
226			// If `token` is a term, then we should be waiting for another binary operator,
227			// and vice versa.
228			return !$this->acceptTerm($token);
229			}
230			throw new MissingOperatorException($token, $this->position);
231			}
232
233			/**
234			* @param iterable<Token> $tokens
235			* @return Result
			0 ignored issues – show Bug introduced 2023-02-10 08:29 UTC by Report Bug Copy Issue Report The type `Smoren\FormulaTools\V2\Result` was not found. Maybe you did not declare it correctly or list all dependencies? The issue could also be caused by a filter entry in the build configuration. If the path has been excluded in your configuration, e.g. `excluded_paths: ["lib/"]`, you can move it to the dependency path list as follows: filter: dependency_paths: ["lib/"] For further information see https://scrutinizer-ci.com/docs/tools/php/php-scrutinizer/#list-dependency-paths Loading history...
236			*/
237			public function parse(iterable $tokens)
238			{
239			assert(!(bool)$this->resultStack); // We are not reenterable.
240			assert(!(bool)$this->opStack);
241			$waitingForTerm = true;
242			try {
243			foreach ($tokens as $this->position => $token) {
244			if ($waitingForTerm) {
245			if ($this->acceptTerm($token)) {
246			$waitingForTerm = false;
247			}
248			} elseif ($this->acceptBinaryOp($token)) {
249			$waitingForTerm = true;
250			}
251			}
252
253			if ($waitingForTerm) {
254			throw count($this->resultStack) === 0 ? (
255			new EmptyStreamException()
256			) : new MissingOperandException();
257			}
258			$this->reduce(PHP_INT_MIN);
259			if ((bool)$this->opStack) {
260			throw new UnclosedBracketException();
261			}
262			} catch (\Throwable $e) {
263			$this->resultStack = []; // Break a possible reference cycle.
264			$this->opStack = [];
265			$this->acceptorStack = [];
266			throw $e;
267			}
268
269			assert(count($this->resultStack) === 1);
270			return array_pop($this->resultStack);
271			}
272			}
273

Smoren / formula-tools-php

Pull Request — master (#1)

FormulaParser::reduce() A

Complexity

Size

Duplication

Code Coverage

Importance

Duplication Side-by-Side

Filter issues like