1 | import { isConstantNode, isParenthesisNode } from '../../utils/is'
|
2 | import { factory } from '../../utils/factory'
|
3 | import { createUtil } from './simplify/util'
|
4 | import { createSimplifyCore } from './simplify/simplifyCore'
|
5 | import { createSimplifyConstant } from './simplify/simplifyConstant'
|
6 | import { createResolve } from './simplify/resolve'
|
7 | import { hasOwnProperty } from '../../utils/object'
|
8 |
|
9 | const name = 'simplify'
|
10 | const dependencies = [
|
11 | 'config',
|
12 | 'typed',
|
13 | 'parse',
|
14 | 'add',
|
15 | 'subtract',
|
16 | 'multiply',
|
17 | 'divide',
|
18 | 'pow',
|
19 | 'isZero',
|
20 | 'equal',
|
21 | '?fraction',
|
22 | '?bignumber',
|
23 | 'mathWithTransform',
|
24 | 'ConstantNode',
|
25 | 'FunctionNode',
|
26 | 'OperatorNode',
|
27 | 'ParenthesisNode',
|
28 | 'SymbolNode'
|
29 | ]
|
30 |
|
31 | export const createSimplify = /* #__PURE__ */ factory(name, dependencies, (
|
32 | {
|
33 | config,
|
34 | typed,
|
35 | parse,
|
36 | add,
|
37 | subtract,
|
38 | multiply,
|
39 | divide,
|
40 | pow,
|
41 | isZero,
|
42 | equal,
|
43 | fraction,
|
44 | bignumber,
|
45 | mathWithTransform,
|
46 | ConstantNode,
|
47 | FunctionNode,
|
48 | OperatorNode,
|
49 | ParenthesisNode,
|
50 | SymbolNode
|
51 | }
|
52 | ) => {
|
53 | const simplifyConstant = createSimplifyConstant({
|
54 | typed,
|
55 | config,
|
56 | mathWithTransform,
|
57 | fraction,
|
58 | bignumber,
|
59 | ConstantNode,
|
60 | OperatorNode,
|
61 | FunctionNode,
|
62 | SymbolNode
|
63 | })
|
64 | const simplifyCore = createSimplifyCore({
|
65 | equal,
|
66 | isZero,
|
67 | add,
|
68 | subtract,
|
69 | multiply,
|
70 | divide,
|
71 | pow,
|
72 | ConstantNode,
|
73 | OperatorNode,
|
74 | FunctionNode,
|
75 | ParenthesisNode
|
76 | })
|
77 | const resolve = createResolve({
|
78 | parse,
|
79 | FunctionNode,
|
80 | OperatorNode,
|
81 | ParenthesisNode
|
82 | })
|
83 |
|
84 | const { isCommutative, isAssociative, flatten, unflattenr, unflattenl, createMakeNodeFunction } =
|
85 | createUtil({ FunctionNode, OperatorNode, SymbolNode })
|
86 |
|
87 | /**
|
88 | * Simplify an expression tree.
|
89 | *
|
90 | * A list of rules are applied to an expression, repeating over the list until
|
91 | * no further changes are made.
|
92 | * It's possible to pass a custom set of rules to the function as second
|
93 | * argument. A rule can be specified as an object, string, or function:
|
94 | *
|
95 | * const rules = [
|
96 | * { l: 'n1*n3 + n2*n3', r: '(n1+n2)*n3' },
|
97 | * 'n1*n3 + n2*n3 -> (n1+n2)*n3',
|
98 | * function (node) {
|
99 | * // ... return a new node or return the node unchanged
|
100 | * return node
|
101 | * }
|
102 | * ]
|
103 | *
|
104 | * String and object rules consist of a left and right pattern. The left is
|
105 | * used to match against the expression and the right determines what matches
|
106 | * are replaced with. The main difference between a pattern and a normal
|
107 | * expression is that variables starting with the following characters are
|
108 | * interpreted as wildcards:
|
109 | *
|
110 | * - 'n' - matches any Node
|
111 | * - 'c' - matches any ConstantNode
|
112 | * - 'v' - matches any Node that is not a ConstantNode
|
113 | *
|
114 | * The default list of rules is exposed on the function as `simplify.rules`
|
115 | * and can be used as a basis to built a set of custom rules.
|
116 | *
|
117 | * For more details on the theory, see:
|
118 | *
|
119 | * - [Strategies for simplifying math expressions (Stackoverflow)](https://stackoverflow.com/questions/7540227/strategies-for-simplifying-math-expressions)
|
120 | * - [Symbolic computation - Simplification (Wikipedia)](https://en.wikipedia.org/wiki/Symbolic_computation#Simplification)
|
121 | *
|
122 | * An optional `options` argument can be passed as last argument of `simplify`.
|
123 | * There is currently one option available: `exactFractions`, a boolean which
|
124 | * is `true` by default.
|
125 | *
|
126 | * Syntax:
|
127 | *
|
128 | * simplify(expr)
|
129 | * simplify(expr, rules)
|
130 | * simplify(expr, rules)
|
131 | * simplify(expr, rules, scope)
|
132 | * simplify(expr, rules, scope, options)
|
133 | * simplify(expr, scope)
|
134 | * simplify(expr, scope, options)
|
135 | *
|
136 | * Examples:
|
137 | *
|
138 | * math.simplify('2 * 1 * x ^ (2 - 1)') // Node "2 * x"
|
139 | * math.simplify('2 * 3 * x', {x: 4}) // Node "24"
|
140 | * const f = math.parse('2 * 1 * x ^ (2 - 1)')
|
141 | * math.simplify(f) // Node "2 * x"
|
142 | * math.simplify('0.4 * x', {}, {exactFractions: true}) // Node "x * 2 / 5"
|
143 | * math.simplify('0.4 * x', {}, {exactFractions: false}) // Node "0.4 * x"
|
144 | *
|
145 | * See also:
|
146 | *
|
147 | * derivative, parse, evaluate, rationalize
|
148 | *
|
149 | * @param {Node | string} expr
|
150 | * The expression to be simplified
|
151 | * @param {Array<{l:string, r: string} | string | function>} [rules]
|
152 | * Optional list with custom rules
|
153 | * @return {Node} Returns the simplified form of `expr`
|
154 | */
|
155 | const simplify = typed('simplify', {
|
156 | string: function (expr) {
|
157 | return simplify(parse(expr), simplify.rules, {}, {})
|
158 | },
|
159 |
|
160 | 'string, Object': function (expr, scope) {
|
161 | return simplify(parse(expr), simplify.rules, scope, {})
|
162 | },
|
163 |
|
164 | 'string, Object, Object': function (expr, scope, options) {
|
165 | return simplify(parse(expr), simplify.rules, scope, options)
|
166 | },
|
167 |
|
168 | 'string, Array': function (expr, rules) {
|
169 | return simplify(parse(expr), rules, {}, {})
|
170 | },
|
171 |
|
172 | 'string, Array, Object': function (expr, rules, scope) {
|
173 | return simplify(parse(expr), rules, scope, {})
|
174 | },
|
175 |
|
176 | 'string, Array, Object, Object': function (expr, rules, scope, options) {
|
177 | return simplify(parse(expr), rules, scope, options)
|
178 | },
|
179 |
|
180 | 'Node, Object': function (expr, scope) {
|
181 | return simplify(expr, simplify.rules, scope, {})
|
182 | },
|
183 |
|
184 | 'Node, Object, Object': function (expr, scope, options) {
|
185 | return simplify(expr, simplify.rules, scope, options)
|
186 | },
|
187 |
|
188 | Node: function (expr) {
|
189 | return simplify(expr, simplify.rules, {}, {})
|
190 | },
|
191 |
|
192 | 'Node, Array': function (expr, rules) {
|
193 | return simplify(expr, rules, {}, {})
|
194 | },
|
195 |
|
196 | 'Node, Array, Object': function (expr, rules, scope) {
|
197 | return simplify(expr, rules, scope, {})
|
198 | },
|
199 |
|
200 | 'Node, Array, Object, Object': function (expr, rules, scope, options) {
|
201 | rules = _buildRules(rules)
|
202 | let res = resolve(expr, scope)
|
203 | res = removeParens(res)
|
204 | const visited = {}
|
205 | let str = res.toString({ parenthesis: 'all' })
|
206 | while (!visited[str]) {
|
207 | visited[str] = true
|
208 | _lastsym = 0 // counter for placeholder symbols
|
209 | for (let i = 0; i < rules.length; i++) {
|
210 | if (typeof rules[i] === 'function') {
|
211 | res = rules[i](res, options)
|
212 | } else {
|
213 | flatten(res)
|
214 | res = applyRule(res, rules[i])
|
215 | }
|
216 | unflattenl(res) // using left-heavy binary tree here since custom rule functions may expect it
|
217 | }
|
218 | str = res.toString({ parenthesis: 'all' })
|
219 | }
|
220 | return res
|
221 | }
|
222 | })
|
223 | simplify.simplifyCore = simplifyCore
|
224 | simplify.resolve = resolve
|
225 |
|
226 | function removeParens (node) {
|
227 | return node.transform(function (node, path, parent) {
|
228 | return isParenthesisNode(node)
|
229 | ? removeParens(node.content)
|
230 | : node
|
231 | })
|
232 | }
|
233 |
|
234 | // All constants that are allowed in rules
|
235 | const SUPPORTED_CONSTANTS = {
|
236 | true: true,
|
237 | false: true,
|
238 | e: true,
|
239 | i: true,
|
240 | Infinity: true,
|
241 | LN2: true,
|
242 | LN10: true,
|
243 | LOG2E: true,
|
244 | LOG10E: true,
|
245 | NaN: true,
|
246 | phi: true,
|
247 | pi: true,
|
248 | SQRT1_2: true,
|
249 | SQRT2: true,
|
250 | tau: true
|
251 | // null: false,
|
252 | // undefined: false,
|
253 | // version: false,
|
254 | }
|
255 |
|
256 | // Array of strings, used to build the ruleSet.
|
257 | // Each l (left side) and r (right side) are parsed by
|
258 | // the expression parser into a node tree.
|
259 | // Left hand sides are matched to subtrees within the
|
260 | // expression to be parsed and replaced with the right
|
261 | // hand side.
|
262 | // TODO: Add support for constraints on constants (either in the form of a '=' expression or a callback [callback allows things like comparing symbols alphabetically])
|
263 | // To evaluate lhs constants for rhs constants, use: { l: 'c1+c2', r: 'c3', evaluate: 'c3 = c1 + c2' }. Multiple assignments are separated by ';' in block format.
|
264 | // It is possible to get into an infinite loop with conflicting rules
|
265 | simplify.rules = [
|
266 | simplifyCore,
|
267 | // { l: 'n+0', r: 'n' }, // simplifyCore
|
268 | // { l: 'n^0', r: '1' }, // simplifyCore
|
269 | // { l: '0*n', r: '0' }, // simplifyCore
|
270 | // { l: 'n/n', r: '1'}, // simplifyCore
|
271 | // { l: 'n^1', r: 'n' }, // simplifyCore
|
272 | // { l: '+n1', r:'n1' }, // simplifyCore
|
273 | // { l: 'n--n1', r:'n+n1' }, // simplifyCore
|
274 | { l: 'log(e)', r: '1' },
|
275 |
|
276 | // temporary rules
|
277 | { l: 'n-n1', r: 'n+-n1' }, // temporarily replace 'subtract' so we can further flatten the 'add' operator
|
278 | { l: '-(c*v)', r: '(-c) * v' }, // make non-constant terms positive
|
279 | { l: '-v', r: '(-1) * v' },
|
280 | { l: 'n/n1^n2', r: 'n*n1^-n2' }, // temporarily replace 'divide' so we can further flatten the 'multiply' operator
|
281 | { l: 'n/n1', r: 'n*n1^-1' },
|
282 |
|
283 | // expand nested exponentiation
|
284 | { l: '(n ^ n1) ^ n2', r: 'n ^ (n1 * n2)' },
|
285 |
|
286 | // collect like factors
|
287 | { l: 'n*n', r: 'n^2' },
|
288 | { l: 'n * n^n1', r: 'n^(n1+1)' },
|
289 | { l: 'n^n1 * n^n2', r: 'n^(n1+n2)' },
|
290 |
|
291 | // collect like terms
|
292 | { l: 'n+n', r: '2*n' },
|
293 | { l: 'n+-n', r: '0' },
|
294 | { l: 'n1*n2 + n2', r: '(n1+1)*n2' },
|
295 | { l: 'n1*n3 + n2*n3', r: '(n1+n2)*n3' },
|
296 |
|
297 | // remove parenthesis in the case of negating a quantitiy
|
298 | { l: 'n1 + -1 * (n2 + n3)', r: 'n1 + -1 * n2 + -1 * n3' },
|
299 |
|
300 | simplifyConstant,
|
301 |
|
302 | { l: '(-n)*n1', r: '-(n*n1)' }, // make factors positive (and undo 'make non-constant terms positive')
|
303 |
|
304 | // ordering of constants
|
305 | { l: 'c+v', r: 'v+c', context: { add: { commutative: false } } },
|
306 | { l: 'v*c', r: 'c*v', context: { multiply: { commutative: false } } },
|
307 |
|
308 | // undo temporary rules
|
309 | // { l: '(-1) * n', r: '-n' }, // #811 added test which proved this is redundant
|
310 | { l: 'n+-n1', r: 'n-n1' }, // undo replace 'subtract'
|
311 | { l: 'n*(n1^-1)', r: 'n/n1' }, // undo replace 'divide'
|
312 | { l: 'n*n1^-n2', r: 'n/n1^n2' },
|
313 | { l: 'n1^-1', r: '1/n1' },
|
314 |
|
315 | { l: 'n*(n1/n2)', r: '(n*n1)/n2' }, // '*' before '/'
|
316 | { l: 'n-(n1+n2)', r: 'n-n1-n2' }, // '-' before '+'
|
317 | // { l: '(n1/n2)/n3', r: 'n1/(n2*n3)' },
|
318 | // { l: '(n*n1)/(n*n2)', r: 'n1/n2' },
|
319 |
|
320 | { l: '1*n', r: 'n' }, // this pattern can be produced by simplifyConstant
|
321 |
|
322 | { l: 'n1/(n2/n3)', r: '(n1*n3)/n2' }
|
323 |
|
324 | ]
|
325 |
|
326 | /**
|
327 | * Parse the string array of rules into nodes
|
328 | *
|
329 | * Example syntax for rules:
|
330 | *
|
331 | * Position constants to the left in a product:
|
332 | * { l: 'n1 * c1', r: 'c1 * n1' }
|
333 | * n1 is any Node, and c1 is a ConstantNode.
|
334 | *
|
335 | * Apply difference of squares formula:
|
336 | * { l: '(n1 - n2) * (n1 + n2)', r: 'n1^2 - n2^2' }
|
337 | * n1, n2 mean any Node.
|
338 | *
|
339 | * Short hand notation:
|
340 | * 'n1 * c1 -> c1 * n1'
|
341 | */
|
342 | function _buildRules (rules) {
|
343 | // Array of rules to be used to simplify expressions
|
344 | const ruleSet = []
|
345 | for (let i = 0; i < rules.length; i++) {
|
346 | let rule = rules[i]
|
347 | let newRule
|
348 | const ruleType = typeof rule
|
349 | switch (ruleType) {
|
350 | case 'string':
|
351 | {
|
352 | const lr = rule.split('->')
|
353 | if (lr.length === 2) {
|
354 | rule = { l: lr[0], r: lr[1] }
|
355 | } else {
|
356 | throw SyntaxError('Could not parse rule: ' + rule)
|
357 | }
|
358 | }
|
359 | /* falls through */
|
360 | case 'object':
|
361 | newRule = {
|
362 | l: removeParens(parse(rule.l)),
|
363 | r: removeParens(parse(rule.r))
|
364 | }
|
365 | if (rule.context) {
|
366 | newRule.evaluate = rule.context
|
367 | }
|
368 | if (rule.evaluate) {
|
369 | newRule.evaluate = parse(rule.evaluate)
|
370 | }
|
371 |
|
372 | if (isAssociative(newRule.l)) {
|
373 | const makeNode = createMakeNodeFunction(newRule.l)
|
374 | const expandsym = _getExpandPlaceholderSymbol()
|
375 | newRule.expanded = {}
|
376 | newRule.expanded.l = makeNode([newRule.l.clone(), expandsym])
|
377 | // Push the expandsym into the deepest possible branch.
|
378 | // This helps to match the newRule against nodes returned from getSplits() later on.
|
379 | flatten(newRule.expanded.l)
|
380 | unflattenr(newRule.expanded.l)
|
381 | newRule.expanded.r = makeNode([newRule.r, expandsym])
|
382 | }
|
383 | break
|
384 | case 'function':
|
385 | newRule = rule
|
386 | break
|
387 | default:
|
388 | throw TypeError('Unsupported type of rule: ' + ruleType)
|
389 | }
|
390 | // console.log('Adding rule: ' + rules[i])
|
391 | // console.log(newRule)
|
392 | ruleSet.push(newRule)
|
393 | }
|
394 | return ruleSet
|
395 | }
|
396 |
|
397 | let _lastsym = 0
|
398 | function _getExpandPlaceholderSymbol () {
|
399 | return new SymbolNode('_p' + _lastsym++)
|
400 | }
|
401 |
|
402 | /**
|
403 | * Returns a simplfied form of node, or the original node if no simplification was possible.
|
404 | *
|
405 | * @param {ConstantNode | SymbolNode | ParenthesisNode | FunctionNode | OperatorNode} node
|
406 | * @return {ConstantNode | SymbolNode | ParenthesisNode | FunctionNode | OperatorNode} The simplified form of `expr`, or the original node if no simplification was possible.
|
407 | */
|
408 | const applyRule = typed('applyRule', {
|
409 | 'Node, Object': function (node, rule) {
|
410 | // console.log('Entering applyRule(' + node.toString() + ')')
|
411 |
|
412 | // Do not clone node unless we find a match
|
413 | let res = node
|
414 |
|
415 | // First replace our child nodes with their simplified versions
|
416 | // If a child could not be simplified, the assignments will have
|
417 | // no effect since the node is returned unchanged
|
418 | if (res instanceof OperatorNode || res instanceof FunctionNode) {
|
419 | if (res.args) {
|
420 | for (let i = 0; i < res.args.length; i++) {
|
421 | res.args[i] = applyRule(res.args[i], rule)
|
422 | }
|
423 | }
|
424 | } else if (res instanceof ParenthesisNode) {
|
425 | if (res.content) {
|
426 | res.content = applyRule(res.content, rule)
|
427 | }
|
428 | }
|
429 |
|
430 | // Try to match a rule against this node
|
431 | let repl = rule.r
|
432 | let matches = _ruleMatch(rule.l, res)[0]
|
433 |
|
434 | // If the rule is associative operator, we can try matching it while allowing additional terms.
|
435 | // This allows us to match rules like 'n+n' to the expression '(1+x)+x' or even 'x+1+x' if the operator is commutative.
|
436 | if (!matches && rule.expanded) {
|
437 | repl = rule.expanded.r
|
438 | matches = _ruleMatch(rule.expanded.l, res)[0]
|
439 | }
|
440 |
|
441 | if (matches) {
|
442 | // const before = res.toString({parenthesis: 'all'})
|
443 |
|
444 | // Create a new node by cloning the rhs of the matched rule
|
445 | // we keep any implicit multiplication state if relevant
|
446 | const implicit = res.implicit
|
447 | res = repl.clone()
|
448 | if (implicit && 'implicit' in repl) {
|
449 | res.implicit = true
|
450 | }
|
451 |
|
452 | // Replace placeholders with their respective nodes without traversing deeper into the replaced nodes
|
453 | res = res.transform(function (node) {
|
454 | if (node.isSymbolNode && hasOwnProperty(matches.placeholders, node.name)) {
|
455 | return matches.placeholders[node.name].clone()
|
456 | } else {
|
457 | return node
|
458 | }
|
459 | })
|
460 |
|
461 | // const after = res.toString({parenthesis: 'all'})
|
462 | // console.log('Simplified ' + before + ' to ' + after)
|
463 | }
|
464 |
|
465 | return res
|
466 | }
|
467 | })
|
468 |
|
469 | /**
|
470 | * Get (binary) combinations of a flattened binary node
|
471 | * e.g. +(node1, node2, node3) -> [
|
472 | * +(node1, +(node2, node3)),
|
473 | * +(node2, +(node1, node3)),
|
474 | * +(node3, +(node1, node2))]
|
475 | *
|
476 | */
|
477 | function getSplits (node, context) {
|
478 | const res = []
|
479 | let right, rightArgs
|
480 | const makeNode = createMakeNodeFunction(node)
|
481 | if (isCommutative(node, context)) {
|
482 | for (let i = 0; i < node.args.length; i++) {
|
483 | rightArgs = node.args.slice(0)
|
484 | rightArgs.splice(i, 1)
|
485 | right = (rightArgs.length === 1) ? rightArgs[0] : makeNode(rightArgs)
|
486 | res.push(makeNode([node.args[i], right]))
|
487 | }
|
488 | } else {
|
489 | rightArgs = node.args.slice(1)
|
490 | right = (rightArgs.length === 1) ? rightArgs[0] : makeNode(rightArgs)
|
491 | res.push(makeNode([node.args[0], right]))
|
492 | }
|
493 | return res
|
494 | }
|
495 |
|
496 | /**
|
497 | * Returns the set union of two match-placeholders or null if there is a conflict.
|
498 | */
|
499 | function mergeMatch (match1, match2) {
|
500 | const res = { placeholders: {} }
|
501 |
|
502 | // Some matches may not have placeholders; this is OK
|
503 | if (!match1.placeholders && !match2.placeholders) {
|
504 | return res
|
505 | } else if (!match1.placeholders) {
|
506 | return match2
|
507 | } else if (!match2.placeholders) {
|
508 | return match1
|
509 | }
|
510 |
|
511 | // Placeholders with the same key must match exactly
|
512 | for (const key in match1.placeholders) {
|
513 | res.placeholders[key] = match1.placeholders[key]
|
514 | if (hasOwnProperty(match2.placeholders, key)) {
|
515 | if (!_exactMatch(match1.placeholders[key], match2.placeholders[key])) {
|
516 | return null
|
517 | }
|
518 | }
|
519 | }
|
520 |
|
521 | for (const key in match2.placeholders) {
|
522 | res.placeholders[key] = match2.placeholders[key]
|
523 | }
|
524 |
|
525 | return res
|
526 | }
|
527 |
|
528 | /**
|
529 | * Combine two lists of matches by applying mergeMatch to the cartesian product of two lists of matches.
|
530 | * Each list represents matches found in one child of a node.
|
531 | */
|
532 | function combineChildMatches (list1, list2) {
|
533 | const res = []
|
534 |
|
535 | if (list1.length === 0 || list2.length === 0) {
|
536 | return res
|
537 | }
|
538 |
|
539 | let merged
|
540 | for (let i1 = 0; i1 < list1.length; i1++) {
|
541 | for (let i2 = 0; i2 < list2.length; i2++) {
|
542 | merged = mergeMatch(list1[i1], list2[i2])
|
543 | if (merged) {
|
544 | res.push(merged)
|
545 | }
|
546 | }
|
547 | }
|
548 | return res
|
549 | }
|
550 |
|
551 | /**
|
552 | * Combine multiple lists of matches by applying mergeMatch to the cartesian product of two lists of matches.
|
553 | * Each list represents matches found in one child of a node.
|
554 | * Returns a list of unique matches.
|
555 | */
|
556 | function mergeChildMatches (childMatches) {
|
557 | if (childMatches.length === 0) {
|
558 | return childMatches
|
559 | }
|
560 |
|
561 | const sets = childMatches.reduce(combineChildMatches)
|
562 | const uniqueSets = []
|
563 | const unique = {}
|
564 | for (let i = 0; i < sets.length; i++) {
|
565 | const s = JSON.stringify(sets[i])
|
566 | if (!unique[s]) {
|
567 | unique[s] = true
|
568 | uniqueSets.push(sets[i])
|
569 | }
|
570 | }
|
571 | return uniqueSets
|
572 | }
|
573 |
|
574 | /**
|
575 | * Determines whether node matches rule.
|
576 | *
|
577 | * @param {ConstantNode | SymbolNode | ParenthesisNode | FunctionNode | OperatorNode} rule
|
578 | * @param {ConstantNode | SymbolNode | ParenthesisNode | FunctionNode | OperatorNode} node
|
579 | * @return {Object} Information about the match, if it exists.
|
580 | */
|
581 | function _ruleMatch (rule, node, isSplit) {
|
582 | // console.log('Entering _ruleMatch(' + JSON.stringify(rule) + ', ' + JSON.stringify(node) + ')')
|
583 | // console.log('rule = ' + rule)
|
584 | // console.log('node = ' + node)
|
585 |
|
586 | // console.log('Entering _ruleMatch(' + rule.toString() + ', ' + node.toString() + ')')
|
587 | let res = [{ placeholders: {} }]
|
588 |
|
589 | if ((rule instanceof OperatorNode && node instanceof OperatorNode) ||
|
590 | (rule instanceof FunctionNode && node instanceof FunctionNode)) {
|
591 | // If the rule is an OperatorNode or a FunctionNode, then node must match exactly
|
592 | if (rule instanceof OperatorNode) {
|
593 | if (rule.op !== node.op || rule.fn !== node.fn) {
|
594 | return []
|
595 | }
|
596 | } else if (rule instanceof FunctionNode) {
|
597 | if (rule.name !== node.name) {
|
598 | return []
|
599 | }
|
600 | }
|
601 |
|
602 | // rule and node match. Search the children of rule and node.
|
603 | if ((node.args.length === 1 && rule.args.length === 1) || !isAssociative(node) || isSplit) {
|
604 | // Expect non-associative operators to match exactly
|
605 | const childMatches = []
|
606 | for (let i = 0; i < rule.args.length; i++) {
|
607 | const childMatch = _ruleMatch(rule.args[i], node.args[i])
|
608 | if (childMatch.length === 0) {
|
609 | // Child did not match, so stop searching immediately
|
610 | return []
|
611 | }
|
612 | // The child matched, so add the information returned from the child to our result
|
613 | childMatches.push(childMatch)
|
614 | }
|
615 | res = mergeChildMatches(childMatches)
|
616 | } else if (node.args.length >= 2 && rule.args.length === 2) { // node is flattened, rule is not
|
617 | // Associative operators/functions can be split in different ways so we check if the rule matches each
|
618 | // them and return their union.
|
619 | const splits = getSplits(node, rule.context)
|
620 | let splitMatches = []
|
621 | for (let i = 0; i < splits.length; i++) {
|
622 | const matchSet = _ruleMatch(rule, splits[i], true) // recursing at the same tree depth here
|
623 | splitMatches = splitMatches.concat(matchSet)
|
624 | }
|
625 | return splitMatches
|
626 | } else if (rule.args.length > 2) {
|
627 | throw Error('Unexpected non-binary associative function: ' + rule.toString())
|
628 | } else {
|
629 | // Incorrect number of arguments in rule and node, so no match
|
630 | return []
|
631 | }
|
632 | } else if (rule instanceof SymbolNode) {
|
633 | // If the rule is a SymbolNode, then it carries a special meaning
|
634 | // according to the first character of the symbol node name.
|
635 | // c.* matches a ConstantNode
|
636 | // n.* matches any node
|
637 | if (rule.name.length === 0) {
|
638 | throw new Error('Symbol in rule has 0 length...!?')
|
639 | }
|
640 | if (SUPPORTED_CONSTANTS[rule.name]) {
|
641 | // built-in constant must match exactly
|
642 | if (rule.name !== node.name) {
|
643 | return []
|
644 | }
|
645 | } else if (rule.name[0] === 'n' || rule.name.substring(0, 2) === '_p') {
|
646 | // rule matches _anything_, so assign this node to the rule.name placeholder
|
647 | // Assign node to the rule.name placeholder.
|
648 | // Our parent will check for matches among placeholders.
|
649 | res[0].placeholders[rule.name] = node
|
650 | } else if (rule.name[0] === 'v') {
|
651 | // rule matches any variable thing (not a ConstantNode)
|
652 | if (!isConstantNode(node)) {
|
653 | res[0].placeholders[rule.name] = node
|
654 | } else {
|
655 | // Mis-match: rule was expecting something other than a ConstantNode
|
656 | return []
|
657 | }
|
658 | } else if (rule.name[0] === 'c') {
|
659 | // rule matches any ConstantNode
|
660 | if (node instanceof ConstantNode) {
|
661 | res[0].placeholders[rule.name] = node
|
662 | } else {
|
663 | // Mis-match: rule was expecting a ConstantNode
|
664 | return []
|
665 | }
|
666 | } else {
|
667 | throw new Error('Invalid symbol in rule: ' + rule.name)
|
668 | }
|
669 | } else if (rule instanceof ConstantNode) {
|
670 | // Literal constant must match exactly
|
671 | if (!equal(rule.value, node.value)) {
|
672 | return []
|
673 | }
|
674 | } else {
|
675 | // Some other node was encountered which we aren't prepared for, so no match
|
676 | return []
|
677 | }
|
678 |
|
679 | // It's a match!
|
680 |
|
681 | // console.log('_ruleMatch(' + rule.toString() + ', ' + node.toString() + ') found a match')
|
682 | return res
|
683 | }
|
684 |
|
685 | /**
|
686 | * Determines whether p and q (and all their children nodes) are identical.
|
687 | *
|
688 | * @param {ConstantNode | SymbolNode | ParenthesisNode | FunctionNode | OperatorNode} p
|
689 | * @param {ConstantNode | SymbolNode | ParenthesisNode | FunctionNode | OperatorNode} q
|
690 | * @return {Object} Information about the match, if it exists.
|
691 | */
|
692 | function _exactMatch (p, q) {
|
693 | if (p instanceof ConstantNode && q instanceof ConstantNode) {
|
694 | if (!equal(p.value, q.value)) {
|
695 | return false
|
696 | }
|
697 | } else if (p instanceof SymbolNode && q instanceof SymbolNode) {
|
698 | if (p.name !== q.name) {
|
699 | return false
|
700 | }
|
701 | } else if ((p instanceof OperatorNode && q instanceof OperatorNode) ||
|
702 | (p instanceof FunctionNode && q instanceof FunctionNode)) {
|
703 | if (p instanceof OperatorNode) {
|
704 | if (p.op !== q.op || p.fn !== q.fn) {
|
705 | return false
|
706 | }
|
707 | } else if (p instanceof FunctionNode) {
|
708 | if (p.name !== q.name) {
|
709 | return false
|
710 | }
|
711 | }
|
712 |
|
713 | if (p.args.length !== q.args.length) {
|
714 | return false
|
715 | }
|
716 |
|
717 | for (let i = 0; i < p.args.length; i++) {
|
718 | if (!_exactMatch(p.args[i], q.args[i])) {
|
719 | return false
|
720 | }
|
721 | }
|
722 | } else {
|
723 | return false
|
724 | }
|
725 |
|
726 | return true
|
727 | }
|
728 |
|
729 | return simplify
|
730 | })
|