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 */
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}