001 /*
002 * Java Genetic Algorithm Library (jenetics-5.1.0).
003 * Copyright (c) 2007-2019 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.getValue() instanceof Var) {
141 if (!n.isLeaf()) {
142 throw new IllegalArgumentException(format(
143 "Variable node '%s' is not a leaf: %s",
144 n.getValue(), n.toParenthesesString()
145 ));
146 }
147
148 variables.add((Var<V>)n.getValue());
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.getValue();
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>)pattern.getValue();
238 final V v = node.getValue();
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.getValue() instanceof Var)
280 .collect(toMap(t -> t.childPath(), t -> (Var<V>)t.getValue()));
281
282 final TreeNode<V> tree = TreeNode.ofTree(
283 template,
284 n -> n instanceof Val ? ((Val<V>)n).value() : null
285 );
286
287 for (Map.Entry<Path, Var<V>> var : paths.entrySet()) {
288 final Path path = var.getKey();
289 final Var<V> decl = var.getValue();
290
291 final Tree<? extends V, ?> replacement = vars.get(decl);
292 if (replacement != null) {
293 tree.replaceAtPath(path, TreeNode.ofTree(replacement));
294 } else {
295 tree.removeAtPath(path);
296 }
297 }
298
299 return tree;
300 }
301
302 @Override
303 public int hashCode() {
304 return _pattern.hashCode();
305 }
306
307 @Override
308 public boolean equals(final Object obj) {
309 return obj == this ||
310 obj instanceof TreePattern &&
311 _pattern.equals(((TreePattern)obj)._pattern);
312 }
313
314 @Override
315 public String toString() {
316 return _pattern.toParenthesesString();
317 }
318
319 /* *************************************************************************
320 * Static factory methods.
321 * ************************************************************************/
322
323 /**
324 * Compiles the given tree pattern string.
325 *
326 * @param pattern the tree pattern string
327 * @return the compiled pattern
328 * @throws NullPointerException if the given pattern is {@code null}
329 * @throws IllegalArgumentException if the given parentheses tree string
330 * doesn't represent a valid pattern tree or one of the variable
331 * name is not a valid (Java) identifier
332 */
333 public static TreePattern<String> compile(final String pattern) {
334 return compile(pattern, Function.identity());
335 }
336
337 public static <V> TreePattern<V> compile(
338 final String pattern,
339 final Function<? super String, ? extends V> mapper
340 ) {
341 return new TreePattern<>(
342 TreeNode.parse(pattern, v -> Decl.of(v.trim(), mapper))
343 );
344 }
345
346 /* *************************************************************************
347 * Java object serialization
348 * ************************************************************************/
349
350 private Object writeReplace() {
351 return new Serial(Serial.TREE_PATTERN, this);
352 }
353
354 private void readObject(final ObjectOutputStream stream)
355 throws InvalidObjectException
356 {
357 throw new InvalidObjectException("Serialization proxy required.");
358 }
359
360 void write(final ObjectOutput out) throws IOException {
361 out.writeObject(_pattern);
362 }
363
364 @SuppressWarnings({"unchecked", "rawtypes"})
365 static TreePattern read(final ObjectInput in)
366 throws IOException, ClassNotFoundException
367 {
368 final TreeNode pattern = (TreeNode)in.readObject();
369 return new TreePattern(pattern);
370 }
371
372
373 /* *************************************************************************
374 * Pattern node classes.
375 * ************************************************************************/
376
377 /**
378 * A <em>sealed</em> class, which constitutes the nodes of a pattern tree.
379 * The only two implementations of this class are the {@link Var} and the
380 * {@link Val} class. The {@link Var} class represents a placeholder for an
381 * arbitrary sub-tree and the {@link Val} class stands for an arbitrary
382 * concrete sub-tree.
383 *
384 * @see Var
385 * @see Val
386 *
387 * @param <V> the node type the tree-pattern is working on
388 */
389 public abstract static class Decl<V> {
390 private static final char VAR_PREFIX = '$';
391 private static final char ESC_CHAR = '\\';
392
393 private static final Escaper ESCAPER = new Escaper(ESC_CHAR, VAR_PREFIX);
394
395 private Decl() {
396 }
397
398 abstract <B> Decl<B> map(final Function<? super V, ? extends B> mapper);
399
400 static <V> Decl<V> of(
401 final String value,
402 final Function<? super String, ? extends V> mapper
403 ) {
404 return Var.isVar(value)
405 ? Var.of(value.substring(1))
406 : Val.of(mapper.apply(ESCAPER.unescape(value)));
407 }
408 }
409
410 /**
411 * Represents a placeholder (variable) for an arbitrary sub-tree. A
412 * <em>pattern</em> variable is identified by its name. The pattern DSL
413 * denotes variable names with a leading '$' character, e.g. {@code $x},
414 * {@code $y} or {@code $my_var}. It is one of two implementations of the
415 * <em>sealed</em> {@link Decl} class.
416 *
417 * @see Val
418 *
419 * @implNote
420 * This class is comparable by it's name.
421 *
422 * @param <V> the node type the tree-pattern is working
423 */
424 public static final class Var<V>
425 extends Decl<V>
426 implements Comparable<Var<V>>, Serializable
427 {
428 private static final long serialVersionUID = 1L;
429
430 private final String _name;
431
432 private Var(final String name) {
433 if (!isIdentifier(name)) {
434 throw new IllegalArgumentException(format(
435 "Variable is not valid identifier: '%s'",
436 name
437 ));
438 }
439 _name = name;
440 }
441
442 @Override
443 @SuppressWarnings("unchecked")
444 <B> Var<B> map(final Function<? super V, ? extends B> mapper) {
445 return (Var<B>)this;
446 }
447
448 /**
449 * Return the name of the variable.
450 *
451 * @return the variable name
452 */
453 public String name() {
454 return _name;
455 }
456
457 @Override
458 public int compareTo(final Var<V> var) {
459 return _name.compareTo(var._name);
460 }
461
462 @Override
463 public int hashCode() {
464 return _name.hashCode();
465 }
466
467 @Override
468 public boolean equals(final Object obj) {
469 return obj == this ||
470 obj instanceof Var &&
471 Objects.equals(_name, ((Var)obj)._name);
472 }
473
474 @Override
475 public String toString() {
476 return format("%s%s", Decl.VAR_PREFIX, _name);
477 }
478
479 /**
480 * Return a new variable with the given name.
481 *
482 * @param name the name of the variable
483 * @param <V> the node type the tree-pattern is working on
484 * @return a new variable with the given name
485 * @throws NullPointerException if the given {@code name} is {@code null}
486 * @throws IllegalArgumentException if the given {@code name} is not a
487 * valid Java identifier
488 */
489 public static <V> Var<V> of(final String name) {
490 return new Var<>(name);
491 }
492
493 static boolean isVar(final String name) {
494 return !name.isEmpty() && name.charAt(0) == Decl.VAR_PREFIX;
495 }
496
497 /* *********************************************************************
498 * Java object serialization
499 * ********************************************************************/
500
501 private Object writeReplace() {
502 return new Serial(Serial.TREE_PATTERN_VAR, this);
503 }
504
505 private void readObject(final ObjectOutputStream stream)
506 throws InvalidObjectException
507 {
508 throw new InvalidObjectException("Serialization proxy required.");
509 }
510
511 void write(final ObjectOutput out) throws IOException {
512 out.writeObject(_name);
513 }
514
515 @SuppressWarnings({"unchecked", "rawtypes"})
516 static Var read(final ObjectInput in)
517 throws IOException, ClassNotFoundException
518 {
519 final String name = (String)in.readObject();
520 return new Var(name);
521 }
522
523 }
524
525 /**
526 * This class represents a constant pattern value, which can be part of a
527 * whole sub-tree. It is one of two implementations of the <em>sealed</em>
528 * {@link Decl} class.
529 *
530 * @see Var
531 *
532 * @param <V> the node value type
533 */
534 public static final class Val<V> extends Decl<V> implements Serializable {
535 private static final long serialVersionUID = 1L;
536
537 private final V _value;
538
539 private Val(final V value) {
540 _value = value;
541 }
542
543 public V value() {
544 return _value;
545 }
546
547 @Override
548 <B> Val<B> map(final Function<? super V, ? extends B> mapper) {
549 return of(mapper.apply(_value));
550 }
551
552 @Override
553 public int hashCode() {
554 return Objects.hashCode(_value);
555 }
556
557 @Override
558 public boolean equals(final Object obj) {
559 return obj == this ||
560 obj instanceof TreePattern.Val &&
561 Objects.equals(_value, ((Val)obj)._value);
562 }
563
564 @Override
565 public String toString() {
566 return Objects.toString(_value);
567 }
568
569 /**
570 * Create a new <em>value</em> object.
571 *
572 * @param value the underlying pattern value
573 * @param <V> the node type
574 * @return a new <em>value</em> object
575 */
576 public static <V> Val<V> of(final V value) {
577 return new Val<>(value);
578 }
579
580
581 /* *********************************************************************
582 * Java object serialization
583 * ********************************************************************/
584
585 private Object writeReplace() {
586 return new Serial(Serial.TREE_PATTERN_VAL, this);
587 }
588
589 private void readObject(final ObjectOutputStream stream)
590 throws InvalidObjectException
591 {
592 throw new InvalidObjectException("Serialization proxy required.");
593 }
594
595 void write(final ObjectOutput out) throws IOException {
596 out.writeObject(_value);
597 }
598
599 @SuppressWarnings({"unchecked", "rawtypes"})
600 static Val read(final ObjectInput in)
601 throws IOException, ClassNotFoundException
602 {
603 return new Val(in.readObject());
604 }
605 }
606
607 }
|