1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * https://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.lang3.concurrent;
18
19 import java.util.concurrent.CancellationException;
20 import java.util.concurrent.ConcurrentHashMap;
21 import java.util.concurrent.ConcurrentMap;
22 import java.util.concurrent.ExecutionException;
23 import java.util.concurrent.Future;
24 import java.util.concurrent.FutureTask;
25 import java.util.function.Function;
26
27 import org.apache.commons.lang3.exception.ExceptionUtils;
28
29 /**
30 * Definition of an interface for a wrapper around a calculation that takes a single parameter and returns a result. The
31 * results for the calculation will be cached for future requests.
32 *
33 * <p>
34 * This is not a fully functional cache: it is unbounded, and there is no way of limiting or removing results once they
35 * have been generated. In particular, note the exception-caching default: unless the {@code recalculate} constructor
36 * option is set to {@code true}, the <em>first</em> exception thrown by a calculation for a given parameter is cached
37 * and rethrown for every future call with that parameter for the lifetime of this instance - a single transient
38 * failure permanently poisons that key. Set {@code recalculate} to {@code true} to retry failed calculations on
39 * subsequent calls instead.
40 * </p>
41 * <p>
42 * Thanks go to Brian Goetz, Tim Peierls and the members of JCP JSR-166 Expert Group for coming up with the
43 * original implementation of the class. It was also published within Java Concurrency in Practice as a sample.
44 * </p>
45 *
46 * @param <I> The type of the input to the calculation
47 * @param <O> The type of the output of the calculation
48 * @since 3.6
49 */
50 public class Memoizer<I, O> implements Computable<I, O> {
51
52 private final ConcurrentMap<I, Future<O>> cache = new ConcurrentHashMap<>();
53 private final Function<? super I, FutureTask<O>> mappingFunction;
54 private final boolean recalculate;
55
56 /**
57 * Constructs a Memoizer for the provided Computable calculation.
58 *
59 * <p>
60 * If a calculation throws an exception for any reason, this exception will be cached and returned for all future
61 * calls with the provided parameter.
62 * </p>
63 *
64 * @param computable The computation whose results should be memorized
65 */
66 public Memoizer(final Computable<I, O> computable) {
67 this(computable, false);
68 }
69
70 /**
71 * Constructs a Memoizer for the provided Computable calculation, with the option of whether a Computation that
72 * experiences an error should recalculate on subsequent calls or return the same cached exception.
73 *
74 * @param computable The computation whose results should be memorized
75 * @param recalculate determines whether the computation should be recalculated on subsequent calls if the previous call
76 * failed
77 */
78 public Memoizer(final Computable<I, O> computable, final boolean recalculate) {
79 this.recalculate = recalculate;
80 this.mappingFunction = k -> new FutureTask<>(() -> computable.compute(k));
81 }
82
83 /**
84 * Constructs a Memoizer for the provided Function calculation.
85 *
86 * <p>
87 * If a calculation throws an exception for any reason, this exception will be cached and returned for all future
88 * calls with the provided parameter.
89 * </p>
90 *
91 * @param function The function whose results should be memorized
92 * @since 2.13.0
93 */
94 public Memoizer(final Function<I, O> function) {
95 this(function, false);
96 }
97
98 /**
99 * Constructs a Memoizer for the provided Function calculation, with the option of whether a Function that
100 * experiences an error should recalculate on subsequent calls or return the same cached exception.
101 *
102 * @param function The computation whose results should be memorized
103 * @param recalculate determines whether the computation should be recalculated on subsequent calls if the previous call
104 * failed
105 * @since 2.13.0
106 */
107 public Memoizer(final Function<I, O> function, final boolean recalculate) {
108 this.recalculate = recalculate;
109 this.mappingFunction = k -> new FutureTask<>(() -> function.apply(k));
110 }
111
112 /**
113 * This method will return the result of the calculation and cache it, if it has not previously been calculated.
114 *
115 * <p>
116 * This cache will also cache exceptions that occur during the computation if the {@code recalculate} parameter in the
117 * constructor was set to {@code false}, or not set: the first exception thrown for a given argument is rethrown for
118 * every future call with that argument. Otherwise, if an exception happened on the previous calculation,
119 * the method will attempt again to generate a value.
120 * </p>
121 * <p>
122 * The calculation for a given argument runs at most once per cached entry and executes <em>outside</em> any internal
123 * lock of the backing map (the pattern published in <em>Java Concurrency in Practice</em>): a slow calculation for
124 * one key does not block calls for unrelated keys, and a calculation may itself use this Memoizer without
125 * deadlocking. Concurrent callers for the same argument wait on the same {@link Future}.
126 * </p>
127 *
128 * @param arg The argument for the calculation
129 * @return The result of the calculation
130 * @throws InterruptedException Thrown if the calculation is interrupted.
131 */
132 @Override
133 public O compute(final I arg) throws InterruptedException {
134 while (true) {
135 Future<O> future = cache.get(arg);
136 if (future == null) {
137 final FutureTask<O> futureTask = mappingFunction.apply(arg);
138 future = cache.putIfAbsent(arg, futureTask);
139 if (future == null) {
140 // This thread won the race to install the task: run the user computation here,
141 // outside the ConcurrentHashMap's internal locks. Losing threads (and later
142 // callers) block on futureTask.get() instead of on a map bin lock.
143 future = futureTask;
144 futureTask.run();
145 }
146 }
147 try {
148 return future.get();
149 } catch (final CancellationException e) {
150 cache.remove(arg, future);
151 } catch (final ExecutionException e) {
152 if (recalculate) {
153 cache.remove(arg, future);
154 }
155 throw launderException(e.getCause());
156 }
157 }
158 }
159
160 /**
161 * Always throws an unchecked exception or error, rethrowing a {@link RuntimeException} or {@link Error} unchanged
162 * and wrapping any other throwable in an {@link IllegalStateException}.
163 *
164 * @param throwable The throwable to rethrow or wrap.
165 * @return Never returns normally.
166 */
167 private RuntimeException launderException(final Throwable throwable) {
168 throw new IllegalStateException("Unchecked exception", ExceptionUtils.throwUnchecked(throwable));
169 }
170 }