13627077473

Committed 03 Mar 2025 09:03AM UTC coverage: 92.643% (-1.3%) from 93.899%

Build # 13627077473

Build Type

Pull #164

github

Committed by

web-flow

Commit Message

Merge 451a74022 into 99d438ef7

Pull Request Pull Request #164: Rewrite parser of unit expressions

Coverage Stats

77 of 136 new or added lines in 2 files covered. (56.62%)

3740 of 4037 relevant lines covered (92.64%)

1153.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.53

/classes/local/unit_parser.php

<?php
// This file is part of Moodle - https://moodle.org/
//
// Moodle is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Moodle is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Moodle.  If not, see <https://www.gnu.org/licenses/>.

namespace qtype_formulas\local;

/*

Notes about current implementation:

- only 2 operators allowed: ^ for exponentiation and / for division
- only one / allowed
- no * allowed
- no parens allowed, except in exponent or around the *entire* denominator
- right side of / is considered in parens, even if not written, e.g. J/m*K --> J / (m*K)
- only units, no numbers except for exponents
- positive or negative exponents allowed
- negative exponents allowed with or without parens
- same unit not allowed more than once

Future implementation, must be 100% backwards compatible

- allow parens everywhere
- allow * for explicit multiplication of units
- still only allow one /
- still not allow same unit more than once
- if * is used after /, assume implicit parens, e. g. J / m * K --> J / (m * K)
- do not allow operators other than *, / and ^ as well as unary - (in exponents only)
- allow ** instead of ^

*/


/**
 * Parser for units for qtype_formulas
 *
 * @package    qtype_formulas
 * @copyright  2025 Philipp Imhof
 * @license    https://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
 */
class unit_parser extends parser {

    /** @var array list of used units */
    private array $unitlist = [];

    /**
     * Create a unit parser class and have it parse a given input. The input can be given as a string, in
     * which case it will first be sent to the lexer. If that step has already been made, the constructor
     * also accepts a list of tokens.
     *
     * @param string|array $tokenlist list of tokens as returned from the lexer or input string
     */
    public function __construct($tokenlist) {
        // If the input is given as a string, run it through the lexer first.
        if (is_string($tokenlist)) {
            $lexer = new lexer($tokenlist);
            $tokenlist = $lexer->get_tokens();
        }
        $this->tokenlist = $tokenlist;
        $this->count = count($tokenlist);

        // Check for unbalanced / mismatched parentheses.
        $this->check_parens();

        // Whether we have already seen a slash or the number one (except in exponents).
        $seenslash = false;
        $seenunit = false;
        $inexponent = false;
        foreach ($tokenlist as $token) {
            // The use of functions is not permitted in units, so all identifiers will be classified
            // as UNIT tokens.
            if ($token->type === token::IDENTIFIER) {
                // If inside an exponent, only numbers (and maybe the unary minus) are allowed.
                if ($inexponent) {
                    $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
                }
                // The same unit must not be used more than once.
                if ($this->has_unit_been_used($token)) {
                    $this->die('Unit already used: ' . $token->value, $token);
                }
                $this->unitlist[] = $token->value;
                $token->type = token::UNIT;
                $seenunit = true;
                continue;
            }

            // Do various syntax checks for operators.
            if ($token->type === token::OPERATOR) {
                // We can only accept an operator if there has been at least one unit before.
                if (!$seenunit) {
                    $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
                }
                // The only operators allowed are exponentiation, multiplication, division and the unary minus.
                // Note that the caret (^) always means exponentiation in the context of units.
                if (!in_array($token->value, ['^', '**', '/', '*', '-'])) {
                    $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
                }
                // The unary minus is only allowed inside an exponent.
                if ($token->value === '-' && !$inexponent) {
                    $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
                }
                // Only the unary minus is allowed inside an exponent.
                if ($inexponent && $token->value !== '-') {
                    $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
                }
                if ($token->value === '^' || $token->value === '**') {
                    $inexponent = true;
                }
                if ($token->value === '/') {
                    if ($seenslash) {
                        $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
                    }
                    $seenslash = true;
                }
                continue;
            }

            // Numbers can only be used as exponents and exponents must always be integers.
            if ($token->type === token::NUMBER) {
                if (!$inexponent) {
                    $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
                }
                if (intval($token->value) != $token->value) {
                    $this->die(get_string('error_integerexpected', 'qtype_formulas', $token->value), $token);
                }
                // Only one number is allowed in an exponent, so after the number the
                // exponent must be finished.
                $inexponent = false;
                continue;
            }

            // Parentheses are allowed, but we don't have to do anything with them now.
            if (in_array($token->type, [token::OPENING_PAREN, token::CLOSING_PAREN])) {
                continue;
            }

            // All other tokens are not allowed.
            $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
        }

        // The last token must be a number, a unit or a closing parenthesis.
        $finaltoken = end($tokenlist);
        if (!in_array($finaltoken->type, [token::UNIT, token::NUMBER, token::CLOSING_PAREN])) {
            $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
        }

        $this->statements[] = shunting_yard::unit_infix_to_rpn($this->tokenlist);
    }

    /**
     * Check whether a given unit has already been used.
     *
     * @param token $token token containing the unit
     * @return bool
     */
    protected function has_unit_been_used(token $token): bool {
        return in_array($token->value, $this->unitlist);
    }

    /**
     * Check whether all parentheses are balanced and whether only round parens are used.
     * Otherweise, stop all further processing and output an error message.
     *
     * @return void
     */
    protected function check_parens(): void {
        $parenstack = [];
        foreach ($this->tokenlist as $token) {
            $type = $token->type;
            // We only allow round parens.
            if (($token->type & token::ANY_PAREN) && !($token->type & token::OPEN_OR_CLOSE_PAREN)) {
                $this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);
            }
            if ($type === token::OPENING_PAREN) {
                $parenstack[] = $token;
            }
            if ($type === token::CLOSING_PAREN) {
                $top = end($parenstack);
                // If stack is empty, we have a stray closing paren.
                if (!($top instanceof token)) {
                    $this->die(get_string('error_strayparen', 'qtype_formulas', $token->value), $token);
                }
                array_pop($parenstack);
            }
        }
        // If the stack of parentheses is not empty now, we have an unmatched opening parenthesis.
        if (!empty($parenstack)) {
            $unmatched = end($parenstack);
            $this->die(get_string('error_parennotclosed', 'qtype_formulas', $unmatched->value), $unmatched);
        }
    }

    /**
     * Translate the given input into a string that can be understood by the legacy unit parser, i. e.
     * following all syntax rules. This allows keeping the old unit conversion system in place until
     * we are readyd to eventually replace it.
     *
     * @return string
     */
    public function get_legacy_unit_string(): string {
        $stack = [];

        foreach ($this->statements[0] as $token) {
            // Write numbers and units to the stack.
            if (in_array($token->type, [token::UNIT, token::NUMBER])) {
                $value = $token->value;
                if (is_numeric($value) && $value < 0) {
                    $value = '(' . strval($value) . ')';
                }
                $stack[] = $value;
            }

            // Operators take arguments from stack and stick them together in the appropriate way.
            if ($token->type === token::OPERATOR) {
                $op = $token->value;
                if ($op === '**') {
                    $op = '^';
                }
                if ($op === '*') {
                    $op = ' ';
                }
                $second = array_pop($stack);
                $first = array_pop($stack);
                // With the new syntax, it is possible to write e.g. (m/s^2)*kg. In older versions,
                // everything coming after the / operator will be considered a part of the denominator,
                // so the only way to get the kg into the numerator is to reorder the units and
                // write them as kg*m/s^2. Long story short: if there is a division, it must come last.
                // Note that the syntax currently does not allow more than one /, so we do not need
                // a more sophisticated solution.
                if (strpos($first, '/') !== false) {
                    list($second, $first) = [$first, $second];
                }
                // Legacy syntax allowed parens around the entire denominator, so we do that unless the
                // denominator is just one unit.
                if ($op === '/' && !preg_match('/^[A-Za-z]+$/', $second)) {
                    $second = '(' . $second . ')';
                }
                $stack[] = $first . $op . $second;
            }
        }

        return implode('', $stack);
    }
}

1	<?php
2	// This file is part of Moodle - https://moodle.org/
3	//
4	// Moodle is free software: you can redistribute it and/or modify
5	// it under the terms of the GNU General Public License as published by
6	// the Free Software Foundation, either version 3 of the License, or
7	// (at your option) any later version.
8	//
9	// Moodle is distributed in the hope that it will be useful,
10	// but WITHOUT ANY WARRANTY; without even the implied warranty of
11	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12	// GNU General Public License for more details.
13	//
14	// You should have received a copy of the GNU General Public License
15	// along with Moodle. If not, see <https://www.gnu.org/licenses/>.
16
17	namespace qtype_formulas\local;
18
19	/*
20
21	Notes about current implementation:
22
23	- only 2 operators allowed: ^ for exponentiation and / for division
24	- only one / allowed
25	- no * allowed
26	- no parens allowed, except in exponent or around the entire denominator
27	- right side of / is considered in parens, even if not written, e.g. J/mK --> J / (mK)
28	- only units, no numbers except for exponents
29	- positive or negative exponents allowed
30	- negative exponents allowed with or without parens
31	- same unit not allowed more than once
32
33	Future implementation, must be 100% backwards compatible
34
35	- allow parens everywhere
36	- allow * for explicit multiplication of units
37	- still only allow one /
38	- still not allow same unit more than once
39	- if * is used after /, assume implicit parens, e. g. J / m * K --> J / (m * K)
40	- do not allow operators other than *, / and ^ as well as unary - (in exponents only)
41	- allow ** instead of ^
42
43	*/
44
45
46	/**
47	* Parser for units for qtype_formulas
48	*
49	* @package qtype_formulas
50	* @copyright 2025 Philipp Imhof
51	* @license https://www.gnu.org/copyleft/gpl.html GNU GPL v3 or later
52	*/
53	class unit_parser extends parser {
54
55	/** @var array list of used units */
56	private array $unitlist = [];
57
58	/**
59	* Create a unit parser class and have it parse a given input. The input can be given as a string, in
60	* which case it will first be sent to the lexer. If that step has already been made, the constructor
61	* also accepts a list of tokens.
62	*
63	* @param string\|array $tokenlist list of tokens as returned from the lexer or input string
64	*/
65	public function __construct($tokenlist) {
66	// If the input is given as a string, run it through the lexer first.
67	if (is_string($tokenlist)) {	2,414✔
68	$lexer = new lexer($tokenlist);	2,414✔
69	$tokenlist = $lexer->get_tokens();	2,380✔
70	}
71	$this->tokenlist = $tokenlist;	2,380✔
72	$this->count = count($tokenlist);	2,380✔
73
74	// Check for unbalanced / mismatched parentheses.
75	$this->check_parens();	2,380✔
76
77	// Whether we have already seen a slash or the number one (except in exponents).
78	$seenslash = false;	2,380✔
79	$seenunit = false;	2,380✔
80	$inexponent = false;	2,380✔
81	foreach ($tokenlist as $token) {	2,380✔
82	// The use of functions is not permitted in units, so all identifiers will be classified
83	// as UNIT tokens.
84	if ($token->type === token::IDENTIFIER) {	2,380✔
85	// If inside an exponent, only numbers (and maybe the unary minus) are allowed.
86	if ($inexponent) {	2,142✔
NEW 87	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	×
88	}
89	// The same unit must not be used more than once.
90	if ($this->has_unit_been_used($token)) {	2,142✔
91	$this->die('Unit already used: ' . $token->value, $token);	34✔
92	}
93	$this->unitlist[] = $token->value;	2,142✔
94	$token->type = token::UNIT;	2,142✔
95	$seenunit = true;	2,142✔
96	continue;	2,142✔
97	}
98
99	// Do various syntax checks for operators.
100	if ($token->type === token::OPERATOR) {	2,312✔
101	// We can only accept an operator if there has been at least one unit before.
102	if (!$seenunit) {	2,108✔
103	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	102✔
104	}
105	// The only operators allowed are exponentiation, multiplication, division and the unary minus.
106	// Note that the caret (^) always means exponentiation in the context of units.
107	if (!in_array($token->value, ['^', '*', '/', '', '-'])) {	2,006✔
108	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	34✔
109	}
110	// The unary minus is only allowed inside an exponent.
111	if ($token->value === '-' && !$inexponent) {	2,006✔
NEW 112	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	×
113	}
114	// Only the unary minus is allowed inside an exponent.
115	if ($inexponent && $token->value !== '-') {	2,006✔
116	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	34✔
117	}
118	if ($token->value === '^' \|\| $token->value === '**') {	2,006✔
119	$inexponent = true;	1,394✔
120	}
121	if ($token->value === '/') {	2,006✔
122	if ($seenslash) {	884✔
NEW 123	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	×
124	}
125	$seenslash = true;	884✔
126	}
127	continue;	2,006✔
128	}
129
130	// Numbers can only be used as exponents and exponents must always be integers.
131	if ($token->type === token::NUMBER) {	1,836✔
132	if (!$inexponent) {	1,462✔
133	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	170✔
134	}
135	if (intval($token->value) != $token->value) {	1,292✔
NEW 136	$this->die(get_string('error_integerexpected', 'qtype_formulas', $token->value), $token);	×
137	}
138	// Only one number is allowed in an exponent, so after the number the
139	// exponent must be finished.
140	$inexponent = false;	1,292✔
141	continue;	1,292✔
142	}
143
144	// Parentheses are allowed, but we don't have to do anything with them now.
145	if (in_array($token->type, [token::OPENING_PAREN, token::CLOSING_PAREN])) {	1,054✔
146	continue;	1,054✔
147	}
148
149	// All other tokens are not allowed.
NEW 150	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	×
151	}
152
153	// The last token must be a number, a unit or a closing parenthesis.
154	$finaltoken = end($tokenlist);	2,006✔
155	if (!in_array($finaltoken->type, [token::UNIT, token::NUMBER, token::CLOSING_PAREN])) {	2,006✔
156	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	102✔
157	}
158
159	$this->statements[] = shunting_yard::unit_infix_to_rpn($this->tokenlist);	1,904✔
160	}
161
162	/**
163	* Check whether a given unit has already been used.
164	*
165	* @param token $token token containing the unit
166	* @return bool
167	*/
168	protected function has_unit_been_used(token $token): bool {
169	return in_array($token->value, $this->unitlist);	2,142✔
170	}
171
172	/**
173	* Check whether all parentheses are balanced and whether only round parens are used.
174	* Otherweise, stop all further processing and output an error message.
175	*
176	* @return void
177	*/
178	protected function check_parens(): void {
179	$parenstack = [];	2,380✔
180	foreach ($this->tokenlist as $token) {	2,380✔
181	$type = $token->type;	2,380✔
182	// We only allow round parens.
183	if (($token->type & token::ANY_PAREN) && !($token->type & token::OPEN_OR_CLOSE_PAREN)) {	2,380✔
NEW 184	$this->die(get_string('error_unexpectedtoken', 'qtype_formulas', $token->value), $token);	×
185	}
186	if ($type === token::OPENING_PAREN) {	2,380✔
187	$parenstack[] = $token;	1,054✔
188	}
189	if ($type === token::CLOSING_PAREN) {	2,380✔
190	$top = end($parenstack);	1,054✔
191	// If stack is empty, we have a stray closing paren.
192	if (!($top instanceof token)) {	1,054✔
NEW 193	$this->die(get_string('error_strayparen', 'qtype_formulas', $token->value), $token);	×
194	}
195	array_pop($parenstack);	1,054✔
196	}
197	}
198	// If the stack of parentheses is not empty now, we have an unmatched opening parenthesis.
199	if (!empty($parenstack)) {	2,380✔
NEW 200	$unmatched = end($parenstack);	×
NEW 201	$this->die(get_string('error_parennotclosed', 'qtype_formulas', $unmatched->value), $unmatched);	×
202	}
203	}
204
205	/**
206	* Translate the given input into a string that can be understood by the legacy unit parser, i. e.
207	* following all syntax rules. This allows keeping the old unit conversion system in place until
208	* we are readyd to eventually replace it.
209	*
210	* @return string
211	*/
212	public function get_legacy_unit_string(): string {
213	$stack = [];	935✔
214
215	foreach ($this->statements[0] as $token) {	935✔
216	// Write numbers and units to the stack.
217	if (in_array($token->type, [token::UNIT, token::NUMBER])) {	935✔
218	$value = $token->value;	935✔
219	if (is_numeric($value) && $value < 0) {	935✔
220	$value = '(' . strval($value) . ')';	306✔
221	}
222	$stack[] = $value;	935✔
223	}
224
225	// Operators take arguments from stack and stick them together in the appropriate way.
226	if ($token->type === token::OPERATOR) {	935✔
227	$op = $token->value;	884✔
228	if ($op === '**') {	884✔
229	$op = '^';	153✔
230	}
231	if ($op === '*') {	884✔
232	$op = ' ';	442✔
233	}
234	$second = array_pop($stack);	884✔
235	$first = array_pop($stack);	884✔
236	// With the new syntax, it is possible to write e.g. (m/s^2)*kg. In older versions,
237	// everything coming after the / operator will be considered a part of the denominator,
238	// so the only way to get the kg into the numerator is to reorder the units and
239	// write them as kg*m/s^2. Long story short: if there is a division, it must come last.
240	// Note that the syntax currently does not allow more than one /, so we do not need
241	// a more sophisticated solution.
242	if (strpos($first, '/') !== false) {	884✔
243	list($second, $first) = [$first, $second];	51✔
244	}
245	// Legacy syntax allowed parens around the entire denominator, so we do that unless the
246	// denominator is just one unit.
247	if ($op === '/' && !preg_match('/^[A-Za-z]+$/', $second)) {	884✔
248	$second = '(' . $second . ')';	238✔
249	}
250	$stack[] = $first . $op . $second;	884✔
251	}
252	}
253
254	return implode('', $stack);	935✔
255	}
256	}

FormulasQuestion / moodle-qtype_formulas / 13627077473

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous