001 /*
002 * Java Genetic Algorithm Library (jenetics-6.3.0).
003 * Copyright (c) 2007-2021 Franz Wilhelmstötter
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 * http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 *
017 * Author:
018 * Franz Wilhelmstötter (franz.wilhelmstoetter@gmail.com)
019 */
020 package io.jenetics.ext.rewriting;
021
022 import static java.lang.String.format;
023 import static java.util.stream.Collectors.toMap;
024 import static io.jenetics.ext.internal.Names.isIdentifier;
025
026 import java.io.IOException;
027 import java.io.InvalidObjectException;
028 import java.io.ObjectInput;
029 import java.io.ObjectOutput;
030 import java.io.ObjectOutputStream;
031 import java.io.Serializable;
032 import java.util.Collections;
033 import java.util.HashMap;
034 import java.util.Map;
035 import java.util.Objects;
036 import java.util.Optional;
037 import java.util.SortedSet;
038 import java.util.TreeSet;
039 import java.util.function.Function;
040
041 import io.jenetics.ext.internal.Escaper;
042 import io.jenetics.ext.util.Tree;
043 import io.jenetics.ext.util.Tree.Path;
044 import io.jenetics.ext.util.TreeNode;
045
046 /**
047 * This class serves two purposes. Firstly, it is used as a <em>classical</em>
048 * pattern, which is used to find <em>matches</em> against a <em>matching</em>
049 * tree. Secondly, it can <em>expand</em> a given pattern to a full tree with a
050 * given <em>pattern</em> variable to sub-tree mapping.
051 *
052 * <p><b>Matching trees</b></p>
053 *
054 * A compiled representation of a <em>tree</em> pattern. A tree pattern,
055 * specified as a parentheses string, must first be compiled into an instance of
056 * this class. The resulting pattern can then be used to create a
057 * {@link TreeMatcher} object that can match arbitrary trees against the tree
058 * pattern. All of the state involved in performing a match resides in the
059 * matcher, so many matchers can share the same pattern.
060 * <p>
061 * The string representation of a tree pattern is a parenthesis tree string,
062 * with a special wildcard syntax for arbitrary sub-trees. The sub-trees
063 * variables are prefixed with a '$' and must be a valid Java identifier.
064 * <pre>{@code
065 * final TreePattern<String> p1 = TreePattern.compile("add($a,add($b,sin(x)))");
066 * final TreePattern<String> p2 = TreePattern.compile("pow($x,$y)");
067 * }</pre>
068 *
069 * If you need to have values which starts with a '$' character, you can escape
070 * it with a '\'.
071 * <pre>{@code
072 * final TreePattern<String> p1 = TreePattern.compile("concat($x,\\$foo)");
073 * }</pre>
074 *
075 * The second value, {@code $foo}, of the {@code concat} function is not treated
076 * as <em>pattern</em> variable.
077 * <p>
078 * If you want to match against trees with a different value type than
079 * {@code String}, you have to specify an additional type mapper function when
080 * compiling the pattern string.
081 * <pre>{@code
082 * final TreePattern<Op<Double>> p = TreePattern.compile(
083 * "add($a,add($b,sin(x)))",
084 * MathOp::toMathOp
085 * );
086 * }</pre>
087 *
088 * <p><b>Expanding trees</b></p>
089 *
090 * The second functionality of the tree pattern is to expand a pattern to a whole
091 * tree with a given <em>pattern</em> variable to sub-tree mapping.
092 * <pre>{@code
093 * final TreePattern<String> pattern = TreePattern.compile("add($x,$y,1)");
094 * final Map<Var<String>, Tree<String, ?>> vars = Map.of(
095 * Var.of("x"), TreeNode.parse("sin(x)"),
096 * Var.of("y"), TreeNode.parse("sin(y)")
097 * );
098 *
099 * final Tree<String, ?> tree = pattern.expand(vars);
100 * assertEquals(tree.toParenthesesString(), "add(sin(x),sin(y),1)");
101 * }</pre>
102 *
103 * @see TreeRewriteRule
104 * @see Tree#toParenthesesString()
105 * @see TreeMatcher
106 *
107 * @param <V> the value type of the tree than can be matched by this pattern
108 *
109 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
110 * @version 5.0
111 * @since 5.0
112 */
113 public final class TreePattern<V> implements Serializable {
114
115 private static final long serialVersionUID = 1L;
116
117 // Primary state of the tree pattern.
118 private final TreeNode<Decl<V>> _pattern;
119
120 // Cached variable set.
121 private final SortedSet<Var<V>> _vars;
122
123 /**
124 * Create a new tree-pattern object from the given pattern tree.
125 *
126 * @param pattern the pattern-tree
127 * @throws NullPointerException if the given {@code pattern} is {@code null}
128 * @throws IllegalArgumentException if {@link Var} nodes are not leaf nodes;
129 * {@link Tree#isLeaf()} is {@code false}
130 */
131 public TreePattern(final Tree<Decl<V>, ?> pattern) {
132 _pattern = TreeNode.ofTree(pattern);
133 _vars = extractVars(_pattern);
134 }
135
136 // Extracts the variables from the pattern.
137 private static <V> SortedSet<Var<V>>
138 extractVars(final TreeNode<Decl<V>> pattern) {
139 final SortedSet<Var<V>> variables = new TreeSet<>();
140 for (Tree<Decl<V>, ?> n : pattern) {
141 if (n.value() instanceof Var) {
142 if (!n.isLeaf()) {
143 throw new IllegalArgumentException(format(
144 "Variable node '%s' is not a leaf: %s",
145 n.value(), n.toParenthesesString()
146 ));
147 }
148
149 variables.add((Var<V>)n.value());
150 }
151 }
152
153 return Collections.unmodifiableSortedSet(variables);
154 }
155
156 TreeNode<Decl<V>> pattern() {
157 return _pattern;
158 }
159
160 /**
161 * Return the <em>unmodifiable</em> set of variables, defined in {@code this}
162 * pattern. The variables are returned without the angle brackets.
163 *
164 * @return the variables, defined in this pattern
165 */
166 public SortedSet<Var<V>> vars() {
167 return _vars;
168 }
169
170 /**
171 * Maps {@code this} tree-pattern from type {@code V} to type {@code B}.
172 *
173 * @param mapper the type mapper
174 * @param <B> the target type
175 * @return a new tree-pattern for the mapped type
176 */
177 public <B> TreePattern<B> map(final Function<? super V, ? extends B> mapper) {
178 return new TreePattern<>(_pattern.map(d -> d.map(mapper)));
179 }
180
181 /**
182 * Creates a matcher that will match the given input tree against
183 * {@code this} pattern.
184 *
185 * @param tree the tree to be matched
186 * @return a new matcher for {@code this} pattern
187 * @throws NullPointerException if the arguments is {@code null}
188 */
189 public TreeMatcher<V> matcher(final Tree<V, ?> tree) {
190 return TreeMatcher.of(this, tree);
191 }
192
193 /**
194 * Try to match the given {@code tree} against {@code this} pattern.
195 *
196 * @param tree the tree to be matched
197 * @return the match result, or {@link Optional#empty()} if the given
198 * {@code tree} doesn't match
199 * @throws NullPointerException if the arguments is {@code null}
200 */
201 public Optional<TreeMatchResult<V>> match(final Tree<V, ?> tree) {
202 final Map<Var<V>, Tree<V, ?>> vars = new HashMap<>();
203 final boolean matches = matches(tree, _pattern, vars);
204
205 return matches
206 ? Optional.of(TreeMatchResult.of(tree, vars))
207 : Optional.empty();
208 }
209
210 /**
211 * Tests whether the given input {@code tree} matches {@code this} pattern.
212 *
213 * @param tree the tree to be matched
214 * @return {@code true} if the {@code tree} matches {@code this} pattern,
215 * {@code false} otherwise
216 * @throws NullPointerException if one of the arguments is {@code null}
217 */
218 public boolean matches(final Tree<V, ?> tree) {
219 return matches(tree, _pattern, new HashMap<>());
220 }
221
222 private static <V> boolean matches(
223 final Tree<V, ?> node,
224 final Tree<Decl<V>, ?> pattern,
225 final Map<Var<V>, Tree<V, ?>> vars
226 ) {
227 final Decl<V> decl = pattern.value();
228
229 if (decl instanceof Var<?>) {
230 final Tree<? extends V, ?> tree = vars.get(decl);
231 if (tree == null) {
232 vars.put((Var<V>)decl, node);
233 return true;
234 }
235
236 return tree.equals(node);
237 } else {
238 final Val<V> p = (Val<V>)decl;
239 final V v = node.value();
240
241 if (Objects.equals(v, p.value())) {
242 if (node.childCount() == pattern.childCount()) {
243 for (int i = 0; i < node.childCount(); ++i) {
244 final Tree<V, ?> cn = node.childAt(i);
245 final Tree<Decl<V>, ?> cp = pattern.childAt(i);
246
247 if (!matches(cn, cp, vars)) {
248 return false;
249 }
250 }
251 return true;
252 } else {
253 return false;
254 }
255 } else {
256 return false;
257 }
258 }
259 }
260
261 /**
262 * Expands {@code this} pattern with the given variable mapping.
263 *
264 * @param vars the variables to use for expanding {@code this} pattern
265 * @return the expanded tree pattern
266 * @throws NullPointerException if one of the arguments is {@code null}
267 * @throws IllegalArgumentException if not all needed variables are part
268 * of the {@code variables} map
269 */
270 public TreeNode<V> expand(final Map<Var<V>, Tree<V, ?>> vars) {
271 return expand(_pattern, vars);
272 }
273
274 // Expanding the template.
275 private static <V> TreeNode<V> expand(
276 final Tree<Decl<V>, ?> template,
277 final Map<Var<V>, Tree<V, ?>> vars
278 ) {
279 final Map<Path, Var<V>> paths = template.stream()
280 .filter((Tree<Decl<V>, ?> n) -> n.value() instanceof Var)
281 .collect(toMap(Tree::childPath, t -> (Var<V>)t.value()));
282
283 final TreeNode<V> tree = TreeNode.ofTree(
284 template,
285 n -> n instanceof Val ? ((Val<V>)n).value() : null
286 );
287
288 paths.forEach((path, decl) -> {
289 final Tree<? extends V, ?> replacement = vars.get(decl);
290 if (replacement != null) {
291 tree.replaceAtPath(path, TreeNode.ofTree(replacement));
292 } else {
293 tree.removeAtPath(path);
294 }
295 });
296
297 return tree;
298 }
299
300 @Override
301 public int hashCode() {
302 return _pattern.hashCode();
303 }
304
305 @Override
306 public boolean equals(final Object obj) {
307 return obj == this ||
308 obj instanceof TreePattern &&
309 _pattern.equals(((TreePattern)obj)._pattern);
310 }
311
312 @Override
313 public String toString() {
314 return _pattern.toParenthesesString();
315 }
316
317 /* *************************************************************************
318 * Static factory methods.
319 * ************************************************************************/
320
321 /**
322 * Compiles the given tree pattern string.
323 *
324 * @param pattern the tree pattern string
325 * @return the compiled pattern
326 * @throws NullPointerException if the given pattern is {@code null}
327 * @throws IllegalArgumentException if the given parentheses tree string
328 * doesn't represent a valid pattern tree or one of the variable
329 * name is not a valid (Java) identifier
330 */
331 public static TreePattern<String> compile(final String pattern) {
332 return compile(pattern, Function.identity());
333 }
334
335 /**
336 * Compiles the given tree pattern string.
337 *
338 * @param pattern the tree pattern string
339 * @param mapper the mapper which converts the serialized string value to
340 * the desired type
341 * @param <V> the value type of the tree than can be matched by the pattern
342 * @return the compiled pattern
343 * @throws NullPointerException if the given pattern is {@code null}
344 * @throws IllegalArgumentException if the given parentheses tree string
345 * doesn't represent a valid pattern tree or one of the variable
346 * name is not a valid (Java) identifier
347 */
348 public static <V> TreePattern<V> compile(
349 final String pattern,
350 final Function<? super String, ? extends V> mapper
351 ) {
352 return new TreePattern<>(
353 TreeNode.parse(pattern, v -> Decl.of(v.trim(), mapper))
354 );
355 }
356
357 /* *************************************************************************
358 * Java object serialization
359 * ************************************************************************/
360
361 private Object writeReplace() {
362 return new Serial(Serial.TREE_PATTERN, this);
363 }
364
365 private void readObject(final ObjectOutputStream stream)
366 throws InvalidObjectException
367 {
368 throw new InvalidObjectException("Serialization proxy required.");
369 }
370
371 void write(final ObjectOutput out) throws IOException {
372 out.writeObject(_pattern);
373 }
374
375 @SuppressWarnings({"unchecked", "rawtypes"})
376 static Object read(final ObjectInput in)
377 throws IOException, ClassNotFoundException
378 {
379 final var pattern = (TreeNode)in.readObject();
380 return new TreePattern(pattern);
381 }
382
383
384 /* *************************************************************************
385 * Pattern node classes.
386 * ************************************************************************/
387
388 /**
389 * A <em>sealed</em> class, which constitutes the nodes of a pattern tree.
390 * The only two implementations of this class are the {@link Var} and the
391 * {@link Val} class. The {@link Var} class represents a placeholder for an
392 * arbitrary sub-tree and the {@link Val} class stands for an arbitrary
393 * concrete sub-tree.
394 *
395 * @see Var
396 * @see Val
397 *
398 * @param <V> the node type the tree-pattern is working on
399 */
400 public abstract static class Decl<V> {
401 private static final char VAR_PREFIX = '$';
402 private static final char ESC_CHAR = '\\';
403
404 private static final Escaper ESCAPER = new Escaper(ESC_CHAR, VAR_PREFIX);
405
406 private Decl() {
407 }
408
409 abstract <B> Decl<B> map(final Function<? super V, ? extends B> mapper);
410
411 static <V> Decl<V> of(
412 final String value,
413 final Function<? super String, ? extends V> mapper
414 ) {
415 return Var.isVar(value)
416 ? Var.of(value.substring(1))
417 : Val.of(mapper.apply(ESCAPER.unescape(value)));
418 }
419 }
420
421 /**
422 * Represents a placeholder (variable) for an arbitrary sub-tree. A
423 * <em>pattern</em> variable is identified by its name. The pattern DSL
424 * denotes variable names with a leading '$' character, e.g. {@code $x},
425 * {@code $y} or {@code $my_var}. It is one of two implementations of the
426 * <em>sealed</em> {@link Decl} class.
427 *
428 * @see Val
429 *
430 * @implNote
431 * This class is comparable by it's name.
432 *
433 * @param <V> the node type the tree-pattern is working
434 */
435 public static final class Var<V>
436 extends Decl<V>
437 implements Comparable<Var<V>>, Serializable
438 {
439 private static final long serialVersionUID = 1L;
440
441 private final String _name;
442
443 private Var(final String name) {
444 if (!isIdentifier(name)) {
445 throw new IllegalArgumentException(format(
446 "Variable is not valid identifier: '%s'",
447 name
448 ));
449 }
450 _name = name;
451 }
452
453 @Override
454 @SuppressWarnings("unchecked")
455 <B> Var<B> map(final Function<? super V, ? extends B> mapper) {
456 return (Var<B>)this;
457 }
458
459 /**
460 * Return the name of the variable.
461 *
462 * @return the variable name
463 */
464 public String name() {
465 return _name;
466 }
467
468 @Override
469 public int compareTo(final Var<V> var) {
470 return _name.compareTo(var._name);
471 }
472
473 @Override
474 public int hashCode() {
475 return _name.hashCode();
476 }
477
478 @Override
479 public boolean equals(final Object obj) {
480 return obj == this ||
481 obj instanceof Var &&
482 Objects.equals(_name, ((Var)obj)._name);
483 }
484
485 @Override
486 public String toString() {
487 return format("%s%s", Decl.VAR_PREFIX, _name);
488 }
489
490 /**
491 * Return a new variable with the given name.
492 *
493 * @param name the name of the variable
494 * @param <V> the node type the tree-pattern is working on
495 * @return a new variable with the given name
496 * @throws NullPointerException if the given {@code name} is {@code null}
497 * @throws IllegalArgumentException if the given {@code name} is not a
498 * valid Java identifier
499 */
500 public static <V> Var<V> of(final String name) {
501 return new Var<>(name);
502 }
503
504 static boolean isVar(final String name) {
505 return !name.isEmpty() && name.charAt(0) == Decl.VAR_PREFIX;
506 }
507
508 /* *********************************************************************
509 * Java object serialization
510 * ********************************************************************/
511
512 private Object writeReplace() {
513 return new Serial(Serial.TREE_PATTERN_VAR, this);
514 }
515
516 private void readObject(final ObjectOutputStream stream)
517 throws InvalidObjectException
518 {
519 throw new InvalidObjectException("Serialization proxy required.");
520 }
521
522 void write(final ObjectOutput out) throws IOException {
523 out.writeObject(_name);
524 }
525
526 @SuppressWarnings("rawtypes")
527 static Object read(final ObjectInput in)
528 throws IOException, ClassNotFoundException
529 {
530 final String name = (String)in.readObject();
531 return new Var(name);
532 }
533
534 }
535
536 /**
537 * This class represents a constant pattern value, which can be part of a
538 * whole sub-tree. It is one of two implementations of the <em>sealed</em>
539 * {@link Decl} class.
540 *
541 * @see Var
542 *
543 * @param <V> the node value type
544 */
545 public static final class Val<V> extends Decl<V> implements Serializable {
546 private static final long serialVersionUID = 1L;
547
548 private final V _value;
549
550 private Val(final V value) {
551 _value = value;
552 }
553
554 public V value() {
555 return _value;
556 }
557
558 @Override
559 <B> Val<B> map(final Function<? super V, ? extends B> mapper) {
560 return Val.of(mapper.apply(_value));
561 }
562
563 @Override
564 public int hashCode() {
565 return Objects.hashCode(_value);
566 }
567
568 @Override
569 public boolean equals(final Object obj) {
570 return obj == this ||
571 obj instanceof TreePattern.Val &&
572 Objects.equals(_value, ((Val)obj)._value);
573 }
574
575 @Override
576 public String toString() {
577 return Objects.toString(_value);
578 }
579
580 /**
581 * Create a new <em>value</em> object.
582 *
583 * @param value the underlying pattern value
584 * @param <V> the node type
585 * @return a new <em>value</em> object
586 */
587 public static <V> Val<V> of(final V value) {
588 return new Val<>(value);
589 }
590
591
592 /* *********************************************************************
593 * Java object serialization
594 * ********************************************************************/
595
596 private Object writeReplace() {
597 return new Serial(Serial.TREE_PATTERN_VAL, this);
598 }
599
600 private void readObject(final ObjectOutputStream stream)
601 throws InvalidObjectException
602 {
603 throw new InvalidObjectException("Serialization proxy required.");
604 }
605
606 void write(final ObjectOutput out) throws IOException {
607 out.writeObject(_value);
608 }
609
610 @SuppressWarnings({"unchecked", "rawtypes"})
611 static Object read(final ObjectInput in)
612 throws IOException, ClassNotFoundException
613 {
614 return new Val(in.readObject());
615 }
616 }
617
618 }
|