1 /*
  2  * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
  3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  4  *
  5  * This code is free software; you can redistribute it and/or modify it
  6  * under the terms of the GNU General Public License version 2 only, as
  7  * published by the Free Software Foundation.  Oracle designates this
  8  * particular file as subject to the "Classpath" exception as provided
  9  * by Oracle in the LICENSE file that accompanied this code.
 10  *
 11  * This code is distributed in the hope that it will be useful, but WITHOUT
 12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 14  * version 2 for more details (a copy is included in the LICENSE file that
 15  * accompanied this code).
 16  *
 17  * You should have received a copy of the GNU General Public License version
 18  * 2 along with this work; if not, write to the Free Software Foundation,
 19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 20  *
 21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 22  * or visit www.oracle.com if you need additional information or have any
 23  * questions.
 24  */
 25 
 26 package java.lang;
 27 
 28 import java.util.NoSuchElementException;
 29 import java.util.Objects;
 30 import java.util.concurrent.Callable;
 31 import java.util.function.Function;
 32 import java.util.function.Supplier;
 33 
 34 import jdk.internal.vm.annotation.ForceInline;
 35 import jdk.internal.vm.annotation.Stable;
 36 
 37 import static jdk.internal.javac.PreviewFeature.Feature.SCOPE_LOCALS;
 38 
 39 /**
 40  * Represents a scoped value.
 41  *
 42  * <p> A scope-local value (hereinafter called a scope local) differs from a normal variable in that it is dynamically
 43  * scoped and intended for cases where context needs to be passed from a caller
 44  * to a transitive callee without using an explicit parameter. A scope-local value
 45  * does not have a default/initial value: it is bound, meaning it gets a value,
 46  * when executing an operation specified to {@link #where(ScopeLocal, Object)}.
 47  * Code executed by the operation
 48  * uses the {@link #get()} method to get the value of the scope local. The scope local reverts
 49  * to being unbound (or its previous value) when the operation completes.
 50  *
 51  * <p> Access to the value of a scope local is controlled by the accessibility
 52  * of the {@code ScopeLocal} object. A {@code ScopeLocal} object  will typically be declared
 53  * in a private static field so that it can only be accessed by code in that class
 54  * (or other classes within its nest).
 55  *
 56  * <p> Scope locals  support nested bindings. If a scope local has a value
 57  * then the {@code runWithBinding} or {@code callWithBinding} can be invoked to run
 58  * another operation with a new value. Code executed by this methods "sees" the new
 59  * value of the scope local. The scope local reverts to its previous value when the
 60  * operation completes.
 61  *
 62  * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
 63  * or method in this class will cause a {@link NullPointerException} to be thrown.
 64  *
 65  * @apiNote
 66  * The following example uses a scope local to make credentials available to callees.
 67  *
 68  * <pre>{@code
 69  *   private static final ScopeLocal<Credentials> CREDENTIALS = ScopeLocal.newInstance();
 70  *
 71  *   Credentials creds = ...
 72  *   ScopeLocal.where(CREDENTIALS, creds).run(creds, () -> {
 73  *       :
 74  *       Connection connection = connectDatabase();
 75  *       :
 76  *   });
 77  *
 78  *   Connection connectDatabase() {
 79  *       Credentials credentials = CREDENTIALS.get();
 80  *       :
 81  *   }
 82  * }</pre>
 83  *
 84  * @param <T> the scope local's type
 85  * @since 99
 86  */
 87 @jdk.internal.javac.PreviewFeature(feature=SCOPE_LOCALS)
 88 public final class ScopeLocal<T> {
 89     private final @Stable int hash;
 90 
 91     public final int hashCode() { return hash; }
 92 
 93     /**
 94      * An immutable map from {@code ScopeLocal} to values.
 95      *
 96      * <p> Unless otherwise specified, passing a {@code null} argument to a constructor
 97      * or method in this class will cause a {@link NullPointerException} to be thrown.
 98      *
 99      * @since 99
100      */
101 
102     static class Snapshot {
103         final Snapshot prev;
104         final Carrier bindings;
105         final short primaryBits;
106 
107         private static final Object NIL = new Object();
108 
109         Snapshot(Carrier bindings, Snapshot prev, short primaryBits) {
110             this.prev = prev;
111             this.bindings = bindings;
112             this.primaryBits = primaryBits;
113         }
114 
115         Object find(ScopeLocal<?> key) {
116             for (Snapshot b = this; b != null; b = b.prev) {
117                 if (((1 << Cache.primaryIndex(key)) & b.primaryBits) != 0) {
118                     for (Carrier binding = b.bindings;
119                          binding != null;
120                          binding = binding.prev) {
121                         if (binding.getKey() == key) {
122                             Object value = binding.get();
123                             return value;
124                         }
125                     }
126                 }
127             }
128             return NIL;
129         }
130     }
131 
132      static final class EmptySnapshot extends Snapshot {
133         private EmptySnapshot() {
134             super(null, null, (short)0);
135         }
136 
137         private static final Snapshot SINGLETON = new EmptySnapshot();
138 
139         static final Snapshot getInstance() {
140             return SINGLETON;
141         }
142     }
143 
144     /**
145      * An immutable map from a set of ScopeLocals to their bound values.
146      * When map() or call() is invoked, the ScopeLocals bound in this set
147      * are bound, such that calling the get() method returns the associated
148      * value.
149      */
150     public static final class Carrier {
151         // Bit masks: a 1 in postion n indicates that this set of bound values
152         // hits that slot in the cache
153         final short primaryBits, secondaryBits;
154         final ScopeLocal<?> key;
155         final Object value;
156         final Carrier prev;
157 
158         Carrier(ScopeLocal<?> key, Object value, Carrier prev, short primaryBits, short secondaryBits) {
159             this.key = key;
160             this.value = value;
161             this.prev = prev;
162             this.primaryBits = primaryBits;
163             this.secondaryBits = secondaryBits;
164         }
165 
166         /**
167          * Add a binding to this map, returning a new Carrier instance.
168          */
169         private static final <T> Carrier where(ScopeLocal<T> key, T value,
170                                                Carrier prev,
171                                                short primaryBits, short secondaryBits) {
172             primaryBits |= (short)(1 << Cache.primaryIndex(key));
173             secondaryBits |= (short)(1 << Cache.secondaryIndex(key));
174             return new Carrier(key, value, prev, primaryBits, secondaryBits);
175         }
176 
177         /**
178          * Return a new map, which consists of the contents of this map plus a
179          * new binding of key and value.
180          * @param key   The ScopeLocal to bind a value to
181          * @param value The new value
182          * @param <T>   The type of the ScopeLocal
183          * @return TBD
184          */
185         public final <T> Carrier where(ScopeLocal<T> key, T value) {
186             return where(key, value, this, primaryBits, secondaryBits);
187         }
188 
189         /*
190          * Return a new set consisting of a single binding.
191          */
192         static final <T> Carrier of(ScopeLocal<T> key, T value) {
193             return where(key, value, null, (short)0, (short)0);
194         }
195 
196         final Object get() {
197             return value;
198         }
199 
200         final ScopeLocal<?> getKey() {
201             return key;
202         }
203 
204         /**
205          * Search for the value of a binding in this set
206          * @param key the ScopeLocal to find
207          * @param <T> the type of the ScopeLocal
208          * @return the value
209          * @throws NoSuchElementException if key is not bound to any value
210          *
211          */
212         @SuppressWarnings("unchecked")
213         public final <T> T get(ScopeLocal<T> key) {
214             for (Carrier b = this;
215                  b != null; b = b.prev) {
216                 if (b.getKey() == key) {
217                     Object value = b.get();
218                     return (T)value;
219                 }
220             }
221             throw new NoSuchElementException();
222         }
223 
224         /**
225          * Runs a value-returning operation with this some ScopeLocals bound to values.
226          * Code executed by the operation can use the {@link #get()} method to
227          * get the value of the scope local. The scope locals revert to their previous values or
228          * becomes {@linkplain #isBound() unbound} when the operation completes.
229          *
230          * @param op    the operation to run
231          * @param <R>   the type of the result of the function
232          * @return the result
233          * @throws Exception if the operation completes with an exception
234          */
235         public final <R> R call(Callable<R> op) throws Exception {
236             Objects.requireNonNull(op);
237             Cache.invalidate(primaryBits | secondaryBits);
238             var prevBindings = addScopeLocalBindings(this, primaryBits);
239             try {
240                 return op.call();
241             } finally {
242                 Thread currentThread = Thread.currentThread();
243                 currentThread.scopeLocalBindings = prevBindings;
244                 Cache.invalidate(primaryBits | secondaryBits);
245             }
246         }
247 
248         /**
249          * Runs a value-returning operation with this some ScopeLocals bound to values.
250          * If the operation terminates with an exception {@code e}, apply {@code handler}
251          * to {@code e} and return the result.
252          *
253          * @param op the operation to run
254          * @param handler a function to be applied if the operation completes with an exception
255          * @param <R> the type of the result of the function
256          * @return the result
257          */
258         public final <R> R callOrElse(Callable<R> op,
259                                       Function<? super Exception, ? extends R> handler) {
260             try {
261                 return call(op);
262             } catch (Exception e) {
263                 return handler.apply(e);
264             }
265         }
266 
267         /**
268          * Runs an operation with some ScopeLocals bound to our values.
269          * Code executed by the operation can use the {@link #get()} method to
270          * get the value of the scope local. The scope locals revert to their previous values or
271          * becomes {@linkplain #isBound() unbound} when the operation completes.
272          *
273          * @param op    the operation to run
274          */
275         public final void run(Runnable op) {
276             Objects.requireNonNull(op);
277             Cache.invalidate(primaryBits | secondaryBits);
278             var prevBindings = addScopeLocalBindings(this, primaryBits);
279             try {
280                 op.run();
281             } finally {
282                 Thread currentThread = Thread.currentThread();
283                 currentThread.scopeLocalBindings = prevBindings;
284                 Cache.invalidate(primaryBits | secondaryBits);
285             }
286         }
287 
288         /*
289          * Add a list of bindings to the current Thread's set of bound values.
290          */
291         private final static Snapshot addScopeLocalBindings(Carrier bindings, short primaryBits) {
292             Snapshot prev = getScopeLocalBindings();
293             var b = new Snapshot(bindings, prev, primaryBits);
294             ScopeLocal.setScopeLocalBindings(b);
295             return prev;
296         }
297     }
298 
299     /**
300      * Creates a binding for a ScopeLocal instance.
301      * That {@link Carrier} may be used later to invoke a {@link Callable} or
302      * {@link Runnable} instance. More bindings may be added to the {@link Carrier}
303      * by the {@link Carrier#where(ScopeLocal, Object)} method.
304      *
305      * @param key the ScopeLocal to bind
306      * @param value The value to bind it to
307      * @param <T> the type of the ScopeLocal
308      * @return A Carrier instance that contains one binding, that of key and value
309      */
310     public static <T> Carrier where(ScopeLocal<T> key, T value) {
311         return Carrier.of(key, value);
312     }
313 
314     /**
315      * Creates a binding for a ScopeLocal instance and runs a value-returning
316      * operation with that bound ScopeLocal.
317      * @param key the ScopeLocal to bind
318      * @param value The value to bind it to
319      * @param <T> the type of the ScopeLocal
320      * @param <U> the type of the Result
321      * @param op the operation to call
322      * @return the result
323      * @throws Exception if the operation completes with an exception
324      */
325     public static <T, U> U where(ScopeLocal<T> key, T value, Callable<U> op) throws Exception {
326         return where(key, value).call(op);
327     }
328 
329     /**
330      * Creates a binding for a ScopeLocal instance and runs an
331      * operation with that bound ScopeLocal.
332      * @param key the ScopeLocal to bind
333      * @param value The value to bind it to
334      * @param <T> the type of the ScopeLocal
335      * @param op the operation to run
336      */
337     public static <T> void where(ScopeLocal<T> key, T value, Runnable op) {
338         where(key, value).run(op);
339     }
340 
341     private ScopeLocal() {
342         this.hash = generateKey();
343     }
344 
345     /**
346      * Creates a scope-local handle to refer to a value of type T.
347      *
348      * @param <T> the type of the scope local's value.
349      * @return a scope-local handle
350      */
351     public static <T> ScopeLocal<T> newInstance() {
352         return new ScopeLocal<T>();
353     }
354 
355     /**
356      * Returns the value of the scope local.
357      * @return the value of the scope local
358      * @throws NoSuchElementException if the scope local is not bound (exception is TBD)
359      */
360     @ForceInline
361     @SuppressWarnings("unchecked")
362     public T get() {
363         Object[] objects;
364         if ((objects = Thread.scopeLocalCache()) != null) {
365             // This code should perhaps be in class Cache. We do it
366             // here because the generated code is small and fast and
367             // we really want it to be inlined in the caller.
368             int n = (hash & Cache.TABLE_MASK) * 2;
369             if (objects[n] == this) {
370                 return (T)objects[n + 1];
371             }
372             n = ((hash >>> Cache.INDEX_BITS) & Cache.TABLE_MASK) * 2;
373             if (objects[n] == this) {
374                 return (T)objects[n + 1];
375             }
376         }
377         return slowGet();
378     }
379 
380     @SuppressWarnings("unchecked")
381     private T slowGet() {
382         var bindings = scopeLocalBindings();
383         var value =  bindings.find(this);
384         if (value == Snapshot.NIL) {
385             throw new NoSuchElementException();
386         }
387         Cache.put(this, value);
388         return (T)value;
389     }
390 
391     /**
392      * Returns {@code true} if the scope local is bound to a value.
393      *
394      * @return {@code true} if the scope local is bound to a value, otherwise {@code false}
395      */
396     @SuppressWarnings("unchecked")
397     public boolean isBound() {
398         return (scopeLocalBindings().find(this) != Snapshot.NIL);
399     }
400 
401     /**
402      * Return the value of the scope local or NIL if not bound.
403      */
404     private Object findBinding() {
405         return scopeLocalBindings().find(this);
406     }
407 
408     /**
409      * Return the value of the scope local if bound, otherwise returns {@code other}.
410      * @param other the value to return if not bound, can be {@code null}
411      * @return the value of the scope local if bound, otherwise {@code other}
412      */
413     public T orElse(T other) {
414         Object obj = findBinding();
415         if (obj != Snapshot.NIL) {
416             @SuppressWarnings("unchecked")
417             T value = (T) obj;
418             return value;
419         } else {
420             return other;
421         }
422     }
423 
424     /**
425      * Return the value of the scope local if bound, otherwise throws an exception
426      * produced by the exception supplying function.
427      * @param <X> Type of the exception to be thrown
428      * @param exceptionSupplier the supplying function that produces an
429      *        exception to be thrown
430      * @return the value of the scope local if bound
431      * @throws X if the scope local is unbound
432      */
433     public <X extends Throwable> T orElseThrow(Supplier<? extends X> exceptionSupplier) throws X {
434         Objects.requireNonNull(exceptionSupplier);
435         Object obj = findBinding();
436         if (obj != Snapshot.NIL) {
437             @SuppressWarnings("unchecked")
438             T value = (T) obj;
439             return value;
440         } else {
441             throw exceptionSupplier.get();
442         }
443     }
444 
445     private static Snapshot getScopeLocalBindings() {
446         Thread currentThread = Thread.currentThread();
447         return currentThread.scopeLocalBindings;
448     }
449 
450     private static void setScopeLocalBindings(Snapshot bindings) {
451         Thread currentThread = Thread.currentThread();
452         currentThread.scopeLocalBindings = bindings;
453     }
454 
455     private Snapshot scopeLocalBindings() {
456         return getScopeLocalBindings();
457     }
458 
459     private static int nextKey = 0xf0f0_f0f0;
460 
461     // A Marsaglia xor-shift generator used to generate hashes. This one has full period, so
462     // it generates 2**32 - 1 hashes before it repeats. We're going to use the lowest n bits
463     // and the next n bits as cache indexes, so we make sure that those indexes are
464     // different.
465     private static synchronized int generateKey() {
466         int x = nextKey;
467         do {
468             x ^= x >>> 12;
469             x ^= x << 9;
470             x ^= x >>> 23;
471         } while ((x & Cache.TABLE_MASK)
472                 == ((x >>> Cache.INDEX_BITS) & Cache.TABLE_MASK));
473         return (nextKey = x);
474     }
475 
476     // A small fixed-size key-value cache. When a scope scope local's get() method
477     // is invoked, we record the result of the lookup in this per-thread cache
478     // for fast access in future.
479     private static class Cache {
480         static final int INDEX_BITS = 4;  // Must be a power of 2
481         static final int TABLE_SIZE = 1 << INDEX_BITS;
482         static final int TABLE_MASK = TABLE_SIZE - 1;
483 
484         static final int primaryIndex(ScopeLocal<?> key) {
485             return key.hash & TABLE_MASK;
486         }
487 
488         static final int secondaryIndex(ScopeLocal<?> key) {
489             return (key.hash >> INDEX_BITS) & TABLE_MASK;
490         }
491 
492         static void put(ScopeLocal<?> key, Object value) {
493             Object[] theCache = Thread.scopeLocalCache();
494             if (theCache == null) {
495                 theCache = new Object[TABLE_SIZE * 2];
496                 Thread.setScopeLocalCache(theCache);
497             }
498             // Update the cache to replace one entry with the value we just looked up.
499             // Each value can be in one of two possible places in the cache.
500             // Pick a victim at (pseudo-)random.
501             Thread thread = Thread.currentThread();
502             int k1 = primaryIndex(key);
503             int k2 = secondaryIndex(key);
504             var usePrimaryIndex = chooseVictim(thread);
505             int victim = usePrimaryIndex ? k1 : k2;
506             int other = usePrimaryIndex ? k2 : k1;
507             setKeyAndObjectAt(victim, key, value);
508             if (getKey(theCache, other) == key) {
509                 setKey(theCache, other, null);
510             }
511         }
512 
513         private static final void update(Object key, Object value) {
514             Object[] objects;
515             if ((objects = Thread.scopeLocalCache()) != null) {
516                 int k1 = key.hashCode() & TABLE_MASK;
517                 if (getKey(objects, k1) == key) {
518                     setKeyAndObjectAt(k1, key, value);
519                 }
520                 int k2 = (key.hashCode() >> INDEX_BITS) & TABLE_MASK;
521                 if (getKey(objects, k2) == key) {
522                     setKeyAndObjectAt(k2, key, value);
523                 }
524             }
525         }
526 
527         private static final void remove(Object key) {
528             Object[] objects;
529             if ((objects = Thread.scopeLocalCache()) != null) {
530                 int k1 = key.hashCode() & TABLE_MASK;
531                 if (getKey(objects, k1) == key) {
532                     setKeyAndObjectAt(k1, null, null);
533                 }
534                 int k2 = (key.hashCode() >> INDEX_BITS) & TABLE_MASK;
535                 if (getKey(objects, k2) == key) {
536                     setKeyAndObjectAt(k2, null, null);
537                 }
538             }
539         }
540 
541         private static void setKeyAndObjectAt(int n, Object key, Object value) {
542             Thread.scopeLocalCache()[n * 2] = key;
543             Thread.scopeLocalCache()[n * 2 + 1] = value;
544         }
545 
546         private static Object getKey(Object[] objs, int n) {
547             return objs[n * 2];
548         }
549 
550         private static void setKey(Object[] objs, int n, Object key) {
551             objs[n * 2] = key;
552         }
553 
554         // Return either true or false, at pseudo-random, with a bias towards true.
555         // This chooses either the primary or secondary cache slot, but the
556         // primary slot is approximately twice as likely to be chosen as the
557         // secondary one.
558         private static boolean chooseVictim(Thread thread) {
559             int tmp = thread.victims;
560             tmp ^= tmp << 13;
561             tmp ^= tmp >>> 17;
562             tmp ^= tmp << 5;
563             thread.victims = tmp;
564             return (tmp & 15) >= 5;
565         }
566 
567         public static void invalidate() {
568             Thread.setScopeLocalCache(null);
569         }
570 
571         // Null a set of cache entries, indicated by the 1-bits given
572         static void invalidate(int toClearBits) {
573             assert(toClearBits == (short)toClearBits);
574             Object[] objects;
575             if ((objects = Thread.scopeLocalCache()) != null) {
576                 for (short bits = (short)toClearBits; bits != 0; ) {
577                     int index = Integer.numberOfTrailingZeros(bits);
578                     setKeyAndObjectAt(index, null, null);
579                     bits &= ~1 << index;
580                 }
581             }
582         }
583     }
584 }