001/*
002 * Java Genetic Algorithm Library (jenetics-7.2.0).
003 * Copyright (c) 2007-2023 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.util.Names.isIdentifier;
025
026import java.io.IOException;
027import java.io.InvalidObjectException;
028import java.io.ObjectInput;
029import java.io.ObjectInputStream;
030import java.io.ObjectOutput;
031import java.io.Serial;
032import java.io.Serializable;
033import java.util.Collections;
034import java.util.HashMap;
035import java.util.Map;
036import java.util.Objects;
037import java.util.Optional;
038import java.util.SortedSet;
039import java.util.TreeSet;
040import java.util.function.Function;
041
042import io.jenetics.ext.internal.util.Escaper;
043import io.jenetics.ext.util.Tree;
044import io.jenetics.ext.util.Tree.Path;
045import io.jenetics.ext.util.TreeNode;
046
047/**
048 * This class serves two purposes. Firstly, it is used as a <em>classical</em>
049 * pattern, which is used to find <em>matches</em> against a <em>matching</em>
050 * tree. Secondly, it can <em>expand</em> a given pattern to a full tree with a
051 * given <em>pattern</em> variable to subtree mapping.
052 *
053 * <p><b>Matching trees</b></p>
054 *
055 * A compiled representation of a <em>tree</em> pattern. A tree pattern,
056 * specified as a parentheses string, must first be compiled into an instance of
057 * this class. The resulting pattern can then be used to create a
058 * {@link TreeMatcher} object that can match arbitrary trees against the tree
059 * pattern. All the states involved in performing a match reside in the
060 * matcher, so many matchers can share the same pattern.
061 * <p>
062 * The string representation of a tree pattern is a parenthesis tree string,
063 * with a special wildcard syntax for arbitrary subtrees. The subtree
064 * variables are prefixed with a '$' and must be a valid Java identifier.
065 * <pre>{@code
066 * final TreePattern<String> p1 = TreePattern.compile("add($a,add($b,sin(x)))");
067 * final TreePattern<String> p2 = TreePattern.compile("pow($x,$y)");
068 * }</pre>
069 *
070 * If you need to have values which start with a '$' character, you can escape
071 * it with a '\'.
072 * <pre>{@code
073 * final TreePattern<String> p1 = TreePattern.compile("concat($x,\\$foo)");
074 * }</pre>
075 *
076 * The second value, {@code $foo}, of the {@code concat} function is not treated
077 * as <em>pattern</em> variable.
078 * <p>
079 * If you want to match against trees with a different value type than
080 * {@code String}, you have to specify an additional type mapper function when
081 * compiling the pattern string.
082 * <pre>{@code
083 * final TreePattern<Op<Double>> p = TreePattern.compile(
084 *     "add($a,add($b,sin(x)))",
085 *     MathOp::toMathOp
086 * );
087 * }</pre>
088 *
089 * <p><b>Expanding trees</b></p>
090 *
091 * The second functionality of the tree pattern is to expand a pattern to a whole
092 * tree with a given <em>pattern</em> variable to subtree mapping.
093 * <pre>{@code
094 * final TreePattern<String> pattern = TreePattern.compile("add($x,$y,1)");
095 * final Map<Var<String>, Tree<String, ?>> vars = Map.of(
096 *     Var.of("x"), TreeNode.parse("sin(x)"),
097 *     Var.of("y"), TreeNode.parse("sin(y)")
098 * );
099 *
100 * final Tree<String, ?> tree = pattern.expand(vars);
101 * assertEquals(tree.toParenthesesString(), "add(sin(x),sin(y),1)");
102 * }</pre>
103 *
104 * @see TreeRewriteRule
105 * @see Tree#toParenthesesString()
106 * @see TreeMatcher
107 *
108 * @param <V> the value type of the tree than can match by this pattern
109 *
110 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
111 * @version 7.0
112 * @since 5.0
113 */
114public final class TreePattern<V> implements Serializable {
115
116        @Serial
117        private static final long serialVersionUID = 1L;
118
119        // Primary state of the tree pattern.
120        private final TreeNode<Decl<V>> _pattern;
121
122        // Cached variable set.
123        private final SortedSet<Var<V>> _vars;
124
125        /**
126         * Create a new tree-pattern object from the given pattern tree.
127         *
128         * @param pattern the pattern-tree
129         * @throws NullPointerException if the given {@code pattern} is {@code null}
130         * @throws IllegalArgumentException if {@link Var} nodes are not leaf nodes;
131         *         {@link Tree#isLeaf()} is {@code false}
132         */
133        public TreePattern(final Tree<Decl<V>, ?> pattern) {
134                _pattern = TreeNode.ofTree(pattern);
135                _vars = extractVars(_pattern);
136        }
137
138        // Extracts the variables from the pattern.
139        private static <V> SortedSet<Var<V>>
140        extractVars(final TreeNode<Decl<V>> pattern) {
141                final SortedSet<Var<V>> variables = new TreeSet<>();
142                for (Tree<Decl<V>, ?> n : pattern) {
143                        if (n.value() instanceof Var<V> var) {
144                                if (!n.isLeaf()) {
145                                        throw new IllegalArgumentException(format(
146                                                "Variable node '%s' is not a leaf: %s",
147                                                n.value(), n.toParenthesesString()
148                                        ));
149                                }
150
151                                variables.add(var);
152                        }
153                }
154
155                return Collections.unmodifiableSortedSet(variables);
156        }
157
158        TreeNode<Decl<V>> pattern() {
159                return _pattern;
160        }
161
162        /**
163         * Return the <em>unmodifiable</em> set of variables, defined in {@code this}
164         * pattern. The variables are returned without the angle brackets.
165         *
166         * @return the variables, defined in this pattern
167         */
168        public SortedSet<Var<V>> vars() {
169                return _vars;
170        }
171
172        /**
173         * Maps {@code this} tree-pattern from type {@code V} to type {@code B}.
174         *
175         * @param mapper the type mapper
176         * @param <B> the target type
177         * @return a new tree-pattern for the mapped type
178         */
179        public <B> TreePattern<B> map(final Function<? super V, ? extends B> mapper) {
180                return new TreePattern<>(_pattern.map(d -> d.map(mapper)));
181        }
182
183        /**
184         * Creates a matcher that will match the given input tree against
185         * {@code this} pattern.
186         *
187         * @param tree the tree to be matched
188         * @return a new matcher for {@code this} pattern
189         * @throws NullPointerException if the arguments is {@code null}
190         */
191        public TreeMatcher<V> matcher(final Tree<V, ?> tree) {
192                return TreeMatcher.of(this, tree);
193        }
194
195        /**
196         * Try to match the given {@code tree} against {@code this} pattern.
197         *
198         * @param tree the tree to be matched
199         * @return the match result, or {@link Optional#empty()} if the given
200         *         {@code tree} doesn't match
201         * @throws NullPointerException if the arguments is {@code null}
202         */
203        public Optional<TreeMatchResult<V>> match(final Tree<V, ?> tree) {
204                final Map<Var<V>, Tree<V, ?>> vars = new HashMap<>();
205                final boolean matches = matches(tree, _pattern, vars);
206
207                return matches
208                        ? Optional.of(TreeMatchResult.of(tree, vars))
209                        : Optional.empty();
210        }
211
212        /**
213         * Tests whether the given input {@code tree} matches {@code this} pattern.
214         *
215         * @param tree the tree to be matched
216         * @return {@code true} if the {@code tree} matches {@code this} pattern,
217         *         {@code false} otherwise
218         * @throws NullPointerException if one of the arguments is {@code null}
219         */
220        public boolean matches(final Tree<V, ?> tree) {
221                return matches(tree, _pattern, new HashMap<>());
222        }
223
224        private static <V> boolean matches(
225                final Tree<V, ?> node,
226                final Tree<Decl<V>, ?> pattern,
227                final Map<Var<V>, Tree<V, ?>> vars
228        ) {
229                final Decl<V> decl = pattern.value();
230
231                if (decl instanceof Var<V> var) {
232                        final Tree<? extends V, ?> tree = vars.get(decl);
233                        if (tree == null) {
234                                vars.put(var, node);
235                                return true;
236                        }
237
238                        return tree.equals(node);
239                } else {
240                        final Val<V> p = (Val<V>)decl;
241                        final V v = node.value();
242
243                        if (Objects.equals(v, p.value())) {
244                                if (node.childCount() == pattern.childCount()) {
245                                        for (int i = 0; i < node.childCount(); ++i) {
246                                                final Tree<V, ?> cn = node.childAt(i);
247                                                final Tree<Decl<V>, ?> cp = pattern.childAt(i);
248
249                                                if (!matches(cn, cp, vars)) {
250                                                        return false;
251                                                }
252                                        }
253                                        return true;
254                                } else {
255                                        return false;
256                                }
257                        } else {
258                                return false;
259                        }
260                }
261        }
262
263        /**
264         * Expands {@code this} pattern with the given variable mapping.
265         *
266         * @param vars the variables to use for expanding {@code this} pattern
267         * @return the expanded tree pattern
268         * @throws NullPointerException if one of the arguments is {@code null}
269         * @throws IllegalArgumentException if not all needed variables are part
270         *         of the {@code variables} map
271         */
272        public TreeNode<V> expand(final Map<Var<V>, Tree<V, ?>> vars) {
273                return expand(_pattern, vars);
274        }
275
276        // Expanding the template.
277        private static <V> TreeNode<V> expand(
278                final Tree<Decl<V>, ?> template,
279                final Map<Var<V>, Tree<V, ?>> vars
280        ) {
281                final Map<Path, Var<V>> paths = template.stream()
282                        .filter((Tree<Decl<V>, ?> n) -> n.value() instanceof Var)
283                        .collect(toMap(Tree::childPath, t -> (Var<V>)t.value()));
284
285                final TreeNode<V> tree = TreeNode.ofTree(
286                        template,
287                        n -> n instanceof Val<V> val ? val.value() : null
288                );
289
290                paths.forEach((path, decl) -> {
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<?> other &&
311                        _pattern.equals(other._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         *         names 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        /**
338         * Compiles the given tree pattern string.
339         *
340         * @param pattern the tree pattern string
341         * @param mapper the mapper which converts the serialized string value to
342         *        the desired type
343         * @param <V> the value type of the tree than can be matched by the pattern
344         * @return the compiled pattern
345         * @throws NullPointerException if the given pattern is {@code null}
346         * @throws IllegalArgumentException if the given parentheses tree string
347         *         doesn't represent a valid pattern tree or one of the variable
348         *         names is not a valid (Java) identifier
349         */
350        public static <V> TreePattern<V> compile(
351                final String pattern,
352                final Function<? super String, ? extends V> mapper
353        ) {
354                return new TreePattern<>(
355                        TreeNode.parse(pattern, v -> Decl.of(v.trim(), mapper))
356                );
357        }
358
359        /* *************************************************************************
360         *  Java object serialization
361         * ************************************************************************/
362
363        @Serial
364        private Object writeReplace() {
365                return new SerialProxy(SerialProxy.TREE_PATTERN, this);
366        }
367
368        @Serial
369        private void readObject(final ObjectInputStream stream)
370                throws InvalidObjectException
371        {
372                throw new InvalidObjectException("Serialization proxy required.");
373        }
374
375        void write(final ObjectOutput out) throws IOException {
376                out.writeObject(_pattern);
377        }
378
379        @SuppressWarnings({"unchecked", "rawtypes"})
380        static Object read(final ObjectInput in)
381                throws IOException, ClassNotFoundException
382        {
383                final var pattern = (TreeNode)in.readObject();
384                return new TreePattern(pattern);
385        }
386
387
388        /* *************************************************************************
389         * Pattern node classes.
390         * ************************************************************************/
391
392        private static final char VAR_PREFIX = '$';
393        private static final char ESC_CHAR = '\\';
394
395        private static final Escaper ESCAPER = new Escaper(ESC_CHAR, VAR_PREFIX);
396
397        /**
398         * A sealed interface, which constitutes the nodes of a pattern tree.
399         * The only two implementations of this class are the {@link Var} and the
400         * {@link Val} class. The {@link Var} class represents a placeholder for an
401         * arbitrary subtree and the {@link Val} class stands for an arbitrary
402         * concrete subtree.
403         *
404         * @see Var
405         * @see Val
406         *
407         * @param <V> the node type the tree-pattern is working on
408         */
409        public sealed interface Decl<V> {
410
411                /**
412                 * Returns a new {@link Decl} object with the mapped type {@code B}.
413                 *
414                 * @param mapper the mapping function
415                 * @param <B> the mapped type
416                 * @return the mapped declaration
417                 * @throws NullPointerException if the mapping function is {@code null}
418                 */
419                <B> Decl<B> map(final Function<? super V, ? extends B> mapper);
420
421                static <V> Decl<V> of(
422                        final String value,
423                        final Function<? super String, ? extends V> mapper
424                ) {
425                        return Var.isVar(value)
426                                ? new Var<>(value.substring(1))
427                                : new Val<>(mapper.apply(ESCAPER.unescape(value)));
428                }
429        }
430
431        /**
432         * Represents a placeholder (variable) for an arbitrary subtree. A
433         * <em>pattern</em> variable is identified by its name. The pattern DSL
434         * denotes variable names with a leading '$' character, e.g. {@code $x},
435         * {@code $y} or {@code $my_var}.
436         *
437         * @see Val
438         *
439         * @implNote
440         * This class is comparable by its name.
441         *
442         @param <V> the node type the tree-pattern is working on
443         */
444        public record Var<V>(String name)
445                implements Decl<V>, Comparable<Var<V>>, Serializable
446        {
447                @Serial
448                private static final long serialVersionUID = 2L;
449
450                /**
451                 * @param name the name of the variable
452                 * @throws NullPointerException if the given {@code name} is {@code null}
453                 * @throws IllegalArgumentException if the given {@code name} is not a
454                 *         valid Java identifier
455                 */
456                public Var {
457                        if (!isIdentifier(name)) {
458                                throw new IllegalArgumentException(format(
459                                        "Variable is not valid identifier: '%s'",
460                                        name
461                                ));
462                        }
463                }
464
465                @Override
466                @SuppressWarnings("unchecked")
467                public <B> Var<B> map(final Function<? super V, ? extends B> mapper) {
468                        return (Var<B>)this;
469                }
470
471                @Override
472                public int compareTo(final Var<V> var) {
473                        return name.compareTo(var.name);
474                }
475
476                @Override
477                public String toString() {
478                        return format("%s%s", VAR_PREFIX, name);
479                }
480
481                static boolean isVar(final String name) {
482                        return !name.isEmpty() && name.charAt(0) == VAR_PREFIX;
483                }
484
485        }
486
487        /**
488         * This class represents a constant pattern value, which can be part of a
489         * whole subtree.
490         *
491         * @see Var
492         *
493         * @param <V> the node value type
494         * @param value the underlying pattern value
495         */
496        public record Val<V>(V value) implements Decl<V>, Serializable {
497                @Serial
498                private static final long serialVersionUID = 2L;
499
500                @Override
501                public <B> Val<B> map(final Function<? super V, ? extends B> mapper) {
502                        return new Val<>(mapper.apply(value));
503                }
504
505                @Override
506                public String toString() {
507                        return Objects.toString(value);
508                }
509
510        }
511
512}