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