001/* 002 * Java Genetic Algorithm Library (jenetics-6.2.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 */ 020package io.jenetics.ext.rewriting; 021 022import static java.lang.String.format; 023import static java.util.stream.Collectors.toMap; 024import static io.jenetics.ext.internal.Names.isIdentifier; 025 026import java.io.IOException; 027import java.io.InvalidObjectException; 028import java.io.ObjectInput; 029import java.io.ObjectOutput; 030import java.io.ObjectOutputStream; 031import java.io.Serializable; 032import java.util.Collections; 033import java.util.HashMap; 034import java.util.Map; 035import java.util.Objects; 036import java.util.Optional; 037import java.util.SortedSet; 038import java.util.TreeSet; 039import java.util.function.Function; 040 041import io.jenetics.ext.internal.Escaper; 042import io.jenetics.ext.util.Tree; 043import io.jenetics.ext.util.Tree.Path; 044import 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 */ 113public 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}