001/*
002 * Java Genetic Algorithm Library (jenetics-8.1.0).
003 * Copyright (c) 2007-2024 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.Objects.requireNonNull;
024import static io.jenetics.internal.util.Hashes.hash;
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.HashSet;
034import java.util.Map;
035import java.util.Optional;
036import java.util.Set;
037import java.util.function.Function;
038import java.util.stream.Collectors;
039
040import io.jenetics.ext.rewriting.TreePattern.Var;
041import io.jenetics.ext.util.Tree;
042import io.jenetics.ext.util.Tree.Path;
043import io.jenetics.ext.util.TreeNode;
044
045/**
046 * Represents a tree rewrite rule. A rewrite rule consists of a match pattern,
047 * which must be matched, and a substitution pattern, which is expanded and
048 * replaces the variables in the pattern. Some simple <em>arithmetic</em>
049 * rewrite rules.
050 * <pre> {@code
051 *     add($x,0) -> $x
052 *     mul($x,1) -> $x
053 * } </pre>
054 * The <em>substitution</em> pattern may only use variables, already defined in
055 * the <em>match</em> pattern. So, the creation of the following rewrite rule s
056 * would lead to an {@link IllegalArgumentException}:
057 * <pre> {@code
058 *     add($x,0) -> $y
059 *     mul(0,1) -> mul($x,1)
060 * } </pre>
061 *
062 * @see <a href="https://en.wikipedia.org/wiki/Rewriting#Term_rewriting_systems">
063 *      Tree rewriting systems</a>
064 *
065 * @author <a href="mailto:franz.wilhelmstoetter@gmail.com">Franz Wilhelmstötter</a>
066 * @version 5.0
067 * @since 5.0
068 */
069public final class TreeRewriteRule<V> implements TreeRewriter<V>, Serializable {
070
071        @Serial
072        private static final long serialVersionUID = 1L;
073
074        private final TreePattern<V> _left;
075        private final TreePattern<V> _right;
076
077        /**
078         * Create a new rewrite rule from the given <em>matching</em> ({@code left})
079         * and <em>replacement</em> ({@code right}) pattern.
080         *
081         * @param left the matching pattern of the rule
082         * @param right the substitution pattern
083         * @throws NullPointerException if one of the arguments is {@code null}
084         * @throws IllegalArgumentException if the <em>template</em> pattern uses
085         *         variables not defined in the <em>matcher</em> pattern
086         */
087        public TreeRewriteRule(
088                final TreePattern<V> left,
089                final TreePattern<V> right
090        ) {
091                _left = requireNonNull(left);
092                _right = requireNonNull(right);
093
094                final Set<Var<V>> undefined = new HashSet<>(_right.vars());
095                undefined.removeAll(_left.vars());
096
097                if (!undefined.isEmpty()) {
098                        throw new IllegalArgumentException(format(
099                                "Some template variables are not defined in the matcher '%s': %s",
100                                this,
101                                undefined.stream()
102                                        .map(v -> format("%s", v))
103                                        .collect(Collectors.joining(", "))
104                        ));
105                }
106        }
107
108        /**
109         * Return the rule matching pattern.
110         *
111         * @return the rule matching pattern
112         */
113        public TreePattern<V> left() {
114                return _left;
115        }
116
117        /**
118         * Return the replacement pattern of the rule.
119         *
120         * @return the replacement pattern of the rule
121         */
122        public TreePattern<V> right() {
123                return _right;
124        }
125
126        /**
127         * Maps {@code this} rewrite rule from type {@code V} to type {@code B}.
128         *
129         * @param mapper the type mapper
130         * @param <B> the target type
131         * @return a new rewrite rule for the mapped type
132         * @throws NullPointerException if the {@code mapper} is {@code null}
133         */
134        public <B> TreeRewriteRule<B> map(final Function<? super V, ? extends B> mapper) {
135                return new TreeRewriteRule<>(_left.map(mapper), _right.map(mapper));
136        }
137
138        @Override
139        public int rewrite(final TreeNode<V> tree, final int limit) {
140                requireNonNull(tree);
141
142                int rewritten = 0;
143                Optional<TreeMatchResult<V>> result;
144                do {
145                        result = left().matcher(tree).results().findFirst();
146
147                        result.ifPresent(res -> rewrite(res, tree));
148                        rewritten += result.isPresent() ? 1 : 0;
149                } while (result.isPresent() && rewritten < limit);
150
151                return rewritten;
152        }
153
154        private void rewrite(
155                final TreeMatchResult<V> result,
156                final TreeNode<V> tree
157        ) {
158                final Map<Var<V>, Tree<V, ?>> vars = result.vars();
159                final TreeNode<V> r = _right.expand(vars);
160
161                final Path path = result.tree().childPath();
162                tree.replaceAtPath(path, r);
163        }
164
165        @Override
166        public int hashCode() {
167                return hash(_left, hash(_right));
168        }
169
170        @Override
171        public boolean equals(final Object obj) {
172                return obj == this ||
173                        obj instanceof TreeRewriteRule<?> other &&
174                        _left.equals(other._left) &&
175                        _right.equals(other._right);
176        }
177
178        @Override
179        public String toString() {
180                return format("%s -> %s", _left, _right);
181        }
182
183        /**
184         * Compiles the string representation of a rewrite rule:
185         * <pre> {@code
186         *     add($x,0) -> $x
187         *     mul($x,1) -> $x
188         * } </pre>
189         *
190         * @param <V> the tree node type
191         * @param rule the rewrite rule
192         * @param mapper the mapper function which converts the node value into the
193         *        actual type {@code V}
194         * @return a new rewrite rule, compiled from the given rule string
195         * @throws IllegalArgumentException if the rewrite rule is invalid
196         * @throws NullPointerException if on of the arguments is {@code null}
197         */
198        public static <V> TreeRewriteRule<V> parse(
199                final String rule,
200                final Function<? super String, ? extends V> mapper
201        ) {
202                final String[] parts = rule.split("->");
203                if (parts.length == 1) {
204                        throw new IllegalArgumentException(format(
205                                "Invalid rewrite rule; missing separator '->': %s", rule
206                        ));
207                }
208                if (parts.length > 2) {
209                        throw new IllegalArgumentException(format(
210                                "Invalid rewrite rule; found %d separators '->': %s",
211                                parts.length - 1, rule
212                        ));
213                }
214
215                return new TreeRewriteRule<>(
216                        TreePattern.compile(parts[0], mapper),
217                        TreePattern.compile(parts[1], mapper)
218                );
219        }
220
221        /**
222         * Compiles the string representation of a rewrite rule:
223         * <pre> {@code
224         *     add($x,0) -> $x
225         *     mul($x,1) -> $x
226         * } </pre>
227         *
228         * @param rule the rewrite rule
229         * @return a new rewrite rule, compiled from the given rule string
230         * @throws IllegalArgumentException if the rewrite rule is invalid
231         * @throws NullPointerException if on of the arguments is {@code null}
232         */
233        public static TreeRewriteRule<String> parse(final String rule) {
234                return parse(rule, Function.identity());
235        }
236
237
238        /* *************************************************************************
239         *  Java object serialization
240         * ************************************************************************/
241
242        @Serial
243        private Object writeReplace() {
244                return new SerialProxy(SerialProxy.TREE_REWRITE_RULE, this);
245        }
246
247        @Serial
248        private void readObject(final ObjectInputStream stream)
249                throws InvalidObjectException
250        {
251                throw new InvalidObjectException("Serialization proxy required.");
252        }
253
254        void write(final ObjectOutput out) throws IOException {
255                out.writeObject(_left);
256                out.writeObject(_right);
257        }
258
259        @SuppressWarnings({"unchecked", "rawtypes"})
260        static Object read(final ObjectInput in)
261                throws IOException, ClassNotFoundException
262        {
263                final TreePattern left = (TreePattern)in.readObject();
264                final TreePattern right = (TreePattern)in.readObject();
265                return new TreeRewriteRule(left, right);
266        }
267
268}