001/*
002 * Java Genetic Algorithm Library (jenetics-8.3.0).
003 * Copyright (c) 2007-2025 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 instanceof TreeRewriteRule<?> other &&
173                        _left.equals(other._left) &&
174                        _right.equals(other._right);
175        }
176
177        @Override
178        public String toString() {
179                return format("%s -> %s", _left, _right);
180        }
181
182        /**
183         * Compiles the string representation of a rewrite rule:
184         * <pre> {@code
185         *     add($x,0) -> $x
186         *     mul($x,1) -> $x
187         * } </pre>
188         *
189         * @param <V> the tree node type
190         * @param rule the rewrite rule
191         * @param mapper the mapper function which converts the node value into the
192         *        actual type {@code V}
193         * @return a new rewrite rule, compiled from the given rule string
194         * @throws IllegalArgumentException if the rewrite rule is invalid
195         * @throws NullPointerException if on of the arguments is {@code null}
196         */
197        public static <V> TreeRewriteRule<V> parse(
198                final String rule,
199                final Function<? super String, ? extends V> mapper
200        ) {
201                final String[] parts = rule.split("->");
202                if (parts.length == 1) {
203                        throw new IllegalArgumentException(format(
204                                "Invalid rewrite rule; missing separator '->': %s", rule
205                        ));
206                }
207                if (parts.length > 2) {
208                        throw new IllegalArgumentException(format(
209                                "Invalid rewrite rule; found %d separators '->': %s",
210                                parts.length - 1, rule
211                        ));
212                }
213
214                return new TreeRewriteRule<>(
215                        TreePattern.compile(parts[0], mapper),
216                        TreePattern.compile(parts[1], mapper)
217                );
218        }
219
220        /**
221         * Compiles the string representation of a rewrite rule:
222         * <pre> {@code
223         *     add($x,0) -> $x
224         *     mul($x,1) -> $x
225         * } </pre>
226         *
227         * @param rule the rewrite rule
228         * @return a new rewrite rule, compiled from the given rule string
229         * @throws IllegalArgumentException if the rewrite rule is invalid
230         * @throws NullPointerException if on of the arguments is {@code null}
231         */
232        public static TreeRewriteRule<String> parse(final String rule) {
233                return parse(rule, Function.identity());
234        }
235
236
237        /* *************************************************************************
238         *  Java object serialization
239         * ************************************************************************/
240
241        @Serial
242        private Object writeReplace() {
243                return new SerialProxy(SerialProxy.TREE_REWRITE_RULE, this);
244        }
245
246        @Serial
247        private void readObject(final ObjectInputStream stream)
248                throws InvalidObjectException
249        {
250                throw new InvalidObjectException("Serialization proxy required.");
251        }
252
253        void write(final ObjectOutput out) throws IOException {
254                out.writeObject(_left);
255                out.writeObject(_right);
256        }
257
258        @SuppressWarnings({"unchecked", "rawtypes"})
259        static Object read(final ObjectInput in)
260                throws IOException, ClassNotFoundException
261        {
262                final TreePattern left = (TreePattern)in.readObject();
263                final TreePattern right = (TreePattern)in.readObject();
264                return new TreeRewriteRule(left, right);
265        }
266
267}