001 /*
002 * Java Genetic Algorithm Library (jenetics-6.0.0).
003 * Copyright (c) 2007-2020 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 = new HashMap<>();
095 * vars.put(Var.of("x"), TreeNode.parse("sin(x)"));
096 * vars.put(Var.of("y"), TreeNode.parse("sin(y)"));
097 *
098 * final Tree<String, ?> tree = pattern.expand(vars);
099 * assertEquals(tree.toParenthesesString(), "add(sin(x),sin(y),1)");
100 * }</pre>
101 *
102 * @see TreeRewriteRule
103 * @see Tree#toParenthesesString()
104 * @see TreeMatcher
105 *
106 * @param <V> the value type of the tree than can be matched by this pattern
107 *
108 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
109 * @version 5.0
110 * @since 5.0
111 */
112 public final class TreePattern<V> implements Serializable {
113
114 private static final long serialVersionUID = 1L;
115
116 // Primary state of the tree pattern.
117 private final TreeNode<Decl<V>> _pattern;
118
119 // Cached variable set.
120 private final SortedSet<Var<V>> _vars;
121
122 /**
123 * Create a new tree-pattern object from the given pattern tree.
124 *
125 * @param pattern the pattern-tree
126 * @throws NullPointerException if the given {@code pattern} is {@code null}
127 * @throws IllegalArgumentException if {@link Var} nodes are not leaf nodes;
128 * {@link Tree#isLeaf()} is {@code false}
129 */
130 public TreePattern(final Tree<Decl<V>, ?> pattern) {
131 _pattern = TreeNode.ofTree(pattern);
132 _vars = extractVars(_pattern);
133 }
134
135 // Extracts the variables from the pattern.
136 private static <V> SortedSet<Var<V>>
137 extractVars(final TreeNode<Decl<V>> pattern) {
138 final SortedSet<Var<V>> variables = new TreeSet<>();
139 for (Tree<Decl<V>, ?> n : pattern) {
140 if (n.value() instanceof Var) {
141 if (!n.isLeaf()) {
142 throw new IllegalArgumentException(format(
143 "Variable node '%s' is not a leaf: %s",
144 n.value(), n.toParenthesesString()
145 ));
146 }
147
148 variables.add((Var<V>)n.value());
149 }
150 }
151
152 return Collections.unmodifiableSortedSet(variables);
153 }
154
155 TreeNode<Decl<V>> pattern() {
156 return _pattern;
157 }
158
159 /**
160 * Return the <em>unmodifiable</em> set of variables, defined in {@code this}
161 * pattern. The variables are returned without the angle brackets.
162 *
163 * @return the variables, defined in this pattern
164 */
165 public SortedSet<Var<V>> vars() {
166 return _vars;
167 }
168
169 /**
170 * Maps {@code this} tree-pattern from type {@code V} to type {@code B}.
171 *
172 * @param mapper the type mapper
173 * @param <B> the target type
174 * @return a new tree-pattern for the mapped type
175 */
176 public <B> TreePattern<B> map(final Function<? super V, ? extends B> mapper) {
177 return new TreePattern<>(_pattern.map(d -> d.map(mapper)));
178 }
179
180 /**
181 * Creates a matcher that will match the given input tree against
182 * {@code this} pattern.
183 *
184 * @param tree the tree to be matched
185 * @return a new matcher for {@code this} pattern
186 * @throws NullPointerException if the arguments is {@code null}
187 */
188 public TreeMatcher<V> matcher(final Tree<V, ?> tree) {
189 return TreeMatcher.of(this, tree);
190 }
191
192 /**
193 * Try to match the given {@code tree} against {@code this} pattern.
194 *
195 * @param tree the tree to be matched
196 * @return the match result, or {@link Optional#empty()} if the given
197 * {@code tree} doesn't match
198 * @throws NullPointerException if the arguments is {@code null}
199 */
200 public Optional<TreeMatchResult<V>> match(final Tree<V, ?> tree) {
201 final Map<Var<V>, Tree<V, ?>> vars = new HashMap<>();
202 final boolean matches = matches(tree, _pattern, vars);
203
204 return matches
205 ? Optional.of(TreeMatchResult.of(tree, vars))
206 : Optional.empty();
207 }
208
209 /**
210 * Tests whether the given input {@code tree} matches {@code this} pattern.
211 *
212 * @param tree the tree to be matched
213 * @return {@code true} if the {@code tree} matches {@code this} pattern,
214 * {@code false} otherwise
215 * @throws NullPointerException if one of the arguments is {@code null}
216 */
217 public boolean matches(final Tree<V, ?> tree) {
218 return matches(tree, _pattern, new HashMap<>());
219 }
220
221 private static <V> boolean matches(
222 final Tree<V, ?> node,
223 final Tree<Decl<V>, ?> pattern,
224 final Map<Var<V>, Tree<V, ?>> vars
225 ) {
226 final Decl<V> decl = pattern.value();
227
228 if (decl instanceof Var) {
229 final Tree<? extends V, ?> tree = vars.get(decl);
230 if (tree == null) {
231 vars.put((Var<V>)decl, node);
232 return true;
233 }
234
235 return tree.equals(node);
236 } else {
237 final Val<V> p = (Val<V>)decl;
238 final V v = node.value();
239
240 if (Objects.equals(v, p.value())) {
241 if (node.childCount() == pattern.childCount()) {
242 for (int i = 0; i < node.childCount(); ++i) {
243 final Tree<V, ?> cn = node.childAt(i);
244 final Tree<Decl<V>, ?> cp = pattern.childAt(i);
245
246 if (!matches(cn, cp, vars)) {
247 return false;
248 }
249 }
250 return true;
251 } else {
252 return false;
253 }
254 } else {
255 return false;
256 }
257 }
258 }
259
260 /**
261 * Expands {@code this} pattern with the given variable mapping.
262 *
263 * @param vars the variables to use for expanding {@code this} pattern
264 * @return the expanded tree pattern
265 * @throws NullPointerException if one of the arguments is {@code null}
266 * @throws IllegalArgumentException if not all needed variables are part
267 * of the {@code variables} map
268 */
269 public TreeNode<V> expand(final Map<Var<V>, Tree<V, ?>> vars) {
270 return expand(_pattern, vars);
271 }
272
273 // Expanding the template.
274 private static <V> TreeNode<V> expand(
275 final Tree<Decl<V>, ?> template,
276 final Map<Var<V>, Tree<V, ?>> vars
277 ) {
278 final Map<Path, Var<V>> paths = template.stream()
279 .filter((Tree<Decl<V>, ?> n) -> n.value() instanceof Var)
280 .collect(toMap(Tree::childPath, t -> (Var<V>)t.value()));
281
282 final TreeNode<V> tree = TreeNode.ofTree(
283 template,
284 n -> n instanceof Val ? ((Val<V>)n).value() : null
285 );
286
287 paths.forEach((path, decl) -> {
288 final Tree<? extends V, ?> replacement = vars.get(decl);
289 if (replacement != null) {
290 tree.replaceAtPath(path, TreeNode.ofTree(replacement));
291 } else {
292 tree.removeAtPath(path);
293 }
294 });
295
296 return tree;
297 }
298
299 @Override
300 public int hashCode() {
301 return _pattern.hashCode();
302 }
303
304 @Override
305 public boolean equals(final Object obj) {
306 return obj == this ||
307 obj instanceof TreePattern &&
308 _pattern.equals(((TreePattern)obj)._pattern);
309 }
310
311 @Override
312 public String toString() {
313 return _pattern.toParenthesesString();
314 }
315
316 /* *************************************************************************
317 * Static factory methods.
318 * ************************************************************************/
319
320 /**
321 * Compiles the given tree pattern string.
322 *
323 * @param pattern the tree pattern string
324 * @return the compiled pattern
325 * @throws NullPointerException if the given pattern is {@code null}
326 * @throws IllegalArgumentException if the given parentheses tree string
327 * doesn't represent a valid pattern tree or one of the variable
328 * name is not a valid (Java) identifier
329 */
330 public static TreePattern<String> compile(final String pattern) {
331 return compile(pattern, Function.identity());
332 }
333
334 /**
335 * Compiles the given tree pattern string.
336 *
337 * @param pattern the tree pattern string
338 * @param mapper the mapper which converts the serialized string value to
339 * the desired type
340 * @param <V> the value type of the tree than can be matched by the pattern
341 * @return the compiled pattern
342 * @throws NullPointerException if the given pattern is {@code null}
343 * @throws IllegalArgumentException if the given parentheses tree string
344 * doesn't represent a valid pattern tree or one of the variable
345 * name is not a valid (Java) identifier
346 */
347 public static <V> TreePattern<V> compile(
348 final String pattern,
349 final Function<? super String, ? extends V> mapper
350 ) {
351 return new TreePattern<>(
352 TreeNode.parse(pattern, v -> Decl.of(v.trim(), mapper))
353 );
354 }
355
356 /* *************************************************************************
357 * Java object serialization
358 * ************************************************************************/
359
360 private Object writeReplace() {
361 return new Serial(Serial.TREE_PATTERN, this);
362 }
363
364 private void readObject(final ObjectOutputStream stream)
365 throws InvalidObjectException
366 {
367 throw new InvalidObjectException("Serialization proxy required.");
368 }
369
370 void write(final ObjectOutput out) throws IOException {
371 out.writeObject(_pattern);
372 }
373
374 @SuppressWarnings({"unchecked", "rawtypes"})
375 static Object read(final ObjectInput in)
376 throws IOException, ClassNotFoundException
377 {
378 final var pattern = (TreeNode)in.readObject();
379 return new TreePattern(pattern);
380 }
381
382
383 /* *************************************************************************
384 * Pattern node classes.
385 * ************************************************************************/
386
387 /**
388 * A <em>sealed</em> class, which constitutes the nodes of a pattern tree.
389 * The only two implementations of this class are the {@link Var} and the
390 * {@link Val} class. The {@link Var} class represents a placeholder for an
391 * arbitrary sub-tree and the {@link Val} class stands for an arbitrary
392 * concrete sub-tree.
393 *
394 * @see Var
395 * @see Val
396 *
397 * @param <V> the node type the tree-pattern is working on
398 */
399 public abstract static class Decl<V> {
400 private static final char VAR_PREFIX = '$';
401 private static final char ESC_CHAR = '\\';
402
403 private static final Escaper ESCAPER = new Escaper(ESC_CHAR, VAR_PREFIX);
404
405 private Decl() {
406 }
407
408 abstract <B> Decl<B> map(final Function<? super V, ? extends B> mapper);
409
410 static <V> Decl<V> of(
411 final String value,
412 final Function<? super String, ? extends V> mapper
413 ) {
414 return Var.isVar(value)
415 ? Var.of(value.substring(1))
416 : Val.of(mapper.apply(ESCAPER.unescape(value)));
417 }
418 }
419
420 /**
421 * Represents a placeholder (variable) for an arbitrary sub-tree. A
422 * <em>pattern</em> variable is identified by its name. The pattern DSL
423 * denotes variable names with a leading '$' character, e.g. {@code $x},
424 * {@code $y} or {@code $my_var}. It is one of two implementations of the
425 * <em>sealed</em> {@link Decl} class.
426 *
427 * @see Val
428 *
429 * @implNote
430 * This class is comparable by it's name.
431 *
432 * @param <V> the node type the tree-pattern is working
433 */
434 public static final class Var<V>
435 extends Decl<V>
436 implements Comparable<Var<V>>, Serializable
437 {
438 private static final long serialVersionUID = 1L;
439
440 private final String _name;
441
442 private Var(final String name) {
443 if (!isIdentifier(name)) {
444 throw new IllegalArgumentException(format(
445 "Variable is not valid identifier: '%s'",
446 name
447 ));
448 }
449 _name = name;
450 }
451
452 @Override
453 @SuppressWarnings("unchecked")
454 <B> Var<B> map(final Function<? super V, ? extends B> mapper) {
455 return (Var<B>)this;
456 }
457
458 /**
459 * Return the name of the variable.
460 *
461 * @return the variable name
462 */
463 public String name() {
464 return _name;
465 }
466
467 @Override
468 public int compareTo(final Var<V> var) {
469 return _name.compareTo(var._name);
470 }
471
472 @Override
473 public int hashCode() {
474 return _name.hashCode();
475 }
476
477 @Override
478 public boolean equals(final Object obj) {
479 return obj == this ||
480 obj instanceof Var &&
481 Objects.equals(_name, ((Var)obj)._name);
482 }
483
484 @Override
485 public String toString() {
486 return format("%s%s", Decl.VAR_PREFIX, _name);
487 }
488
489 /**
490 * Return a new variable with the given name.
491 *
492 * @param name the name of the variable
493 * @param <V> the node type the tree-pattern is working on
494 * @return a new variable with the given name
495 * @throws NullPointerException if the given {@code name} is {@code null}
496 * @throws IllegalArgumentException if the given {@code name} is not a
497 * valid Java identifier
498 */
499 public static <V> Var<V> of(final String name) {
500 return new Var<>(name);
501 }
502
503 static boolean isVar(final String name) {
504 return !name.isEmpty() && name.charAt(0) == Decl.VAR_PREFIX;
505 }
506
507 /* *********************************************************************
508 * Java object serialization
509 * ********************************************************************/
510
511 private Object writeReplace() {
512 return new Serial(Serial.TREE_PATTERN_VAR, this);
513 }
514
515 private void readObject(final ObjectOutputStream stream)
516 throws InvalidObjectException
517 {
518 throw new InvalidObjectException("Serialization proxy required.");
519 }
520
521 void write(final ObjectOutput out) throws IOException {
522 out.writeObject(_name);
523 }
524
525 @SuppressWarnings("rawtypes")
526 static Object read(final ObjectInput in)
527 throws IOException, ClassNotFoundException
528 {
529 final String name = (String)in.readObject();
530 return new Var(name);
531 }
532
533 }
534
535 /**
536 * This class represents a constant pattern value, which can be part of a
537 * whole sub-tree. It is one of two implementations of the <em>sealed</em>
538 * {@link Decl} class.
539 *
540 * @see Var
541 *
542 * @param <V> the node value type
543 */
544 public static final class Val<V> extends Decl<V> implements Serializable {
545 private static final long serialVersionUID = 1L;
546
547 private final V _value;
548
549 private Val(final V value) {
550 _value = value;
551 }
552
553 public V value() {
554 return _value;
555 }
556
557 @Override
558 <B> Val<B> map(final Function<? super V, ? extends B> mapper) {
559 return Val.of(mapper.apply(_value));
560 }
561
562 @Override
563 public int hashCode() {
564 return Objects.hashCode(_value);
565 }
566
567 @Override
568 public boolean equals(final Object obj) {
569 return obj == this ||
570 obj instanceof TreePattern.Val &&
571 Objects.equals(_value, ((Val)obj)._value);
572 }
573
574 @Override
575 public String toString() {
576 return Objects.toString(_value);
577 }
578
579 /**
580 * Create a new <em>value</em> object.
581 *
582 * @param value the underlying pattern value
583 * @param <V> the node type
584 * @return a new <em>value</em> object
585 */
586 public static <V> Val<V> of(final V value) {
587 return new Val<>(value);
588 }
589
590
591 /* *********************************************************************
592 * Java object serialization
593 * ********************************************************************/
594
595 private Object writeReplace() {
596 return new Serial(Serial.TREE_PATTERN_VAL, this);
597 }
598
599 private void readObject(final ObjectOutputStream stream)
600 throws InvalidObjectException
601 {
602 throw new InvalidObjectException("Serialization proxy required.");
603 }
604
605 void write(final ObjectOutput out) throws IOException {
606 out.writeObject(_value);
607 }
608
609 @SuppressWarnings({"unchecked", "rawtypes"})
610 static Object read(final ObjectInput in)
611 throws IOException, ClassNotFoundException
612 {
613 return new Val(in.readObject());
614 }
615 }
616
617 }
|