1 /*
2 * Copyright (c) 2012, 2013 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 package java.util.stream;
26
27 import java.util.EnumMap;
28 import java.util.Map;
29
30 /**
31 * Flags corresponding to characteristics of streams and operations. Flags are utilized by the stream
32 * framework to control, specialize or optimize computation.
33 *
34 * <p>
35 * Stream flags may be used to describe characteristics of several different entities associated with streams:
36 * stream sources, intermediate operations, and terminal operations. Not all stream flags are meaningful for all
37 * entities; the following table summarizes which flags are meaningful in what contexts:
38 * <pre>
39 * DISTINCT SORTED ORDERED SIZED SHORT_CIRCUIT PARALLEL
40 * Stream source Y Y Y Y N Y
41 * Intermediate operation PCI PCI PCI PC PI PC
42 * Terminal operation N N PC N PI N
43 * </pre>
44 *
45 * <p>In the above table, "PCI" means "may preserve, clear, or inject"; "PC" means "may preserve or clear",
46 * "PI" means "may preserve or inject", and "N" means "not valid".
47 *
48 * <p>Stream flags are represented by unioned bit sets, so that a single word may describe all the
49 * characteristics of a given stream entity, and that, for example, the flags for a stream source can be
50 * efficiently combined with the flags for later operations on that stream.
51 *
52 * <p>The bit masks {@link #STREAM_MASK}, {@link #OP_MASK}, and {@link #TERMINAL_OP_MASK} can be ANDed with
53 * a bit set of stream flags to produce a mask containing only the valid flags for that entity type.
54 *
55 * <p>When describing a stream source, one only need describe what characteristics that stream has; when describing
56 * a stream operation, one need describe whether the operation preserves, injects, or clears that characteristic.
57 * Accordingly, two bits are used for each flag, so as to allow representing not only the presence of of a
58 * characteristic, but how an operation modifies that characteristic. There are two common forms in which
59 * flag bits are combined into an {@code int} bit set. <em>Stream flags</em> are a unioned bit set constructed by
60 * ORing the enum characteristic values of {@link #set()} (or, more commonly, ORing the corresponding static named
61 * constants prefixed with {@code IS_}). <em>Operation flags</em> are a unioned bit set constructed by
62 * ORing the enum characteristic values of {@link #set()} or {@link #clear()} (to inject, or clear, respectively,
63 * the corresponding flag), or more commonly ORing the corresponding named constants prefixed with {@code IS_}
64 * or {@code NOT_}. Flags that are not marked with {@code IS_} or {@code NOT_} are implicitly treated as preserved.
65 * Care must be taken when combining bitsets that the correct combining operations are applied in the correct order.
66 *
67 * <p>
68 * With the exception of {@link #PARALLEL}, stream characteristics can be derived from the equivalent
69 * {@link java.util.Spliterator} characteristics: {@link java.util.Spliterator#DISTINCT},
70 * {@link java.util.Spliterator#SORTED}, {@link java.util.Spliterator#ORDERED}, and
71 * {@link java.util.Spliterator#SIZED}. A spliterator characteristics bit set can be converted to stream flags
72 * using the method {@link #fromCharacteristics(int)} and converted back using {@link #toCharacteristics(int)}.
73 * (The bit set {@link #SPLITERATOR_CHARACTERISTICS_MASK} is used to AND with a bit set to produce a valid
74 * spliterator characteristics bit set that can be converted to stream flags.)
75 *
76 * <p>
77 * The source of a stream encapsulates a spliterator. The characteristics of that source
78 * spliterator when transformed to stream flags will be a proper subset of stream flags of that stream.
79 * For example:
80 * <pre> {@code
81 * Spliterator s = ...;
82 * Stream stream = Streams.stream(s);
83 * flagsFromSpliterator = fromCharacteristics(s.characteristics());
84 * assert(flagsFromSpliterator & stream.getStreamFlags() == flagsFromSpliterator);
85 * }</pre>
86 *
87 * <p>
88 * An intermediate operation, performed on an input stream to create a new output stream,
89 * may preserve, clear or inject stream or operation characteristics.
90 * Similarly, a terminal operation, performed on an input stream to produce an output result
91 * may preserve, clear or inject stream or operation characteristics.
92 * Preservation means that if that characteristic is present on the input, then it is
93 * also present on the output. Clearing means that the characteristic is not present on the output regardless
94 * of the input. Injection means that the characteristic is present on the output regardless of the input.
95 * If a characteristic is not cleared or injected then it is implicitly preserved.
96 *
97 * <p>
98 * A pipeline consists of a stream source encapsulating a spliterator, one or more intermediate operations,
99 * and finally a terminal operation that produces a result. At each stage of the pipeline, a combined
100 * stream and operation flags can be calculated, using {@link #combineOpFlags(int, int)}.
101 * Such flags ensure that preservation, clearing and injecting information is retained at each stage.
102 *
103 * The combined stream and operation flags for the source stage of the pipeline is calculated as
104 * follows:
105 * <pre> {@code
106 * int flagsForSourceStage = combineOpFlags(sourceFlags, INITIAL_OPS_VALUE);
107 * }</pre>
108 *
109 * The combined stream and operation flags of each subsequent intermediate operation stage in the pipeline is
110 * calculated as follows:
111 * <pre> {@code
112 * int flagsForThisStage = combineOpFlags(flagsForPreviousStage, thisOpFlags);
113 * }</pre>
114 *
115 * Finally the flags output from the last intermediate operation of the pipeline are combined with the operation flags
116 * of the terminal operation to produce the flags output from the pipeline.
117 *
118 * <p>Those flags can then be used to apply optimizations. For example, if {@code SIZED.isKnown(flags)} returns true
119 * then the stream size remains constant throughout the pipeline, this information can be utilized to pre-allocate data
120 * structures and combined with {@link java.util.Spliterator#SUBSIZED} that information can be utilized to perform
121 * concurrent in-place updates into a shared array.
122 *
123 * For specific details see the {@link AbstractPipeline} constructors.
124 *
125 * @since 1.8
126 */
127 // @@@ When a new flag is added what should happen for existing operations?
128 // Need to move to a builder approach used by ops where the masks for the new flag are
129 // taken into account for default behaviour.
130 enum StreamOpFlag {
131
132 /*
133 * Each characteristic takes up 2 bits in a bit set to accommodate preserving, clearing and
134 * setting/injecting information.
135 *
136 * This applies to stream flags, intermediate/terminal operation flags, and combined stream and
137 * operation flags. Even though the former only requires 1 bit of information per characteristic,
138 * is it more efficient when combining flags to align set and inject bits.
139 *
140 * Characteristics belong to certain types, see the Type enum. Bit masks for the types are
141 * constructed as per the following table:
142 *
143 * DISTINCT SORTED ORDERED SIZED SHORT_CIRCUIT PARALLEL
144 * SPLITERATOR 01 01 01 01 00 00
145 * STREAM 01 01 01 01 00 01
146 * OP 11 11 11 10 01 10
147 * TERMINAL_OP 00 00 10 00 01 00
148 * UPSTREAM_TERMINAL_OP 00 00 10 00 00 00
149 *
150 * 01 = set/inject
151 * 10 = clear
152 * 11 = preserve
153 *
154 * Construction of the columns is performed using a simple builder for non-zero values.
155 */
156
157
158 // The following flags correspond to characteristics on Spliterator
159 // and the values MUST be equal.
160 //
161
162 /**
163 * Characteristic value signifying that, for each pair of
164 * encountered elements in a stream {@code x, y}, {@code !x.equals(y)}.
165 * <p>
166 * A stream may have this value or an intermediate operation can preserve, clear or inject
167 * this value.
168 */
169 // 0, 0x00000001
170 // Matches Spliterator.DISTINCT
171 DISTINCT(0,
172 set(Type.SPLITERATOR).set(Type.STREAM).setAndClear(Type.OP)),
173
174 /**
175 * Characteristic value signifying that encounter order follows a
176 * defined sort order.
177 * <p>
178 * A stream can have this value or an intermediate operation can preserve, clear or inject
179 * this value.
180 */
181 // 1, 0x00000004
182 // Matches Spliterator.SORTED
183 SORTED(1,
184 set(Type.SPLITERATOR).set(Type.STREAM).setAndClear(Type.OP)),
185
186 /**
187 * Characteristic value signifying that an encounter order is
188 * defined for stream elements.
189 * <p>
190 * A stream can have this value, an intermediate operation can preserve, clear or inject
191 * this value, or a terminal operation can preserve or clear this value.
192 */
193 // 2, 0x00000010
194 // Matches Spliterator.ORDERED
195 ORDERED(2,
196 set(Type.SPLITERATOR).set(Type.STREAM).setAndClear(Type.OP).clear(Type.TERMINAL_OP)
197 .clear(Type.UPSTREAM_TERMINAL_OP)),
198
199 /**
200 * Characteristic value signifying that size of the stream
201 * is of a known finite size that is equal to the known finite
202 * size of the source spliterator input to the first stream
203 * in the pipeline.
204 * <p>
205 * A stream can have this value or an intermediate operation can preserve or clear
206 * this value.
207 */
208 // 3, 0x00000040
209 // Matches Spliterator.SIZED
210 SIZED(3,
211 set(Type.SPLITERATOR).set(Type.STREAM).clear(Type.OP)),
212
213 // The following Spliterator characteristics are not currently used but a
214 // gap in the bit set is deliberately retained to enable corresponding stream
215 // flags if//when required without modification to other flag values.
216 //
217 // 4, 0x00000100 INFINITE(4, ...
218 // 5, 0x00000400 NONNULL(5, ...
219 // 6, 0x00001000 IMMUTABLE(6, ...
220 // 7, 0x00004000 CONCURRENT(7, ...
221 // 8, 0x00010000 SUBSIZED(8, ...)
222
223 // The following 3 flags are currently undefined and a free for any further
224 // spliterator characteristics.
225 //
226 // 9, 0x00040000
227 // 10, 0x00100000
228 // 11, 0x00400000
229
230 // The following flags are specific to streams and operations
231 //
232
233 /**
234 * Characteristic value signifying that an operation may short-circuit the stream.
235 * <p>
236 * An intermediate operation can preserve or inject this value,
237 * or a terminal operation can preserve or inject this value.
238 */
239 // 12, 0x01000000
240 SHORT_CIRCUIT(12,
241 set(Type.OP).set(Type.TERMINAL_OP)),
242
243
244 /**
245 * Characteristic value signifying that the stream is to be evaluated in parallel rather than
246 * sequentially.
247 * <p>
248 * A stream can have this value or an intermediate operation can preserve or clear
249 * this value.
250 */
251 // 13, 0x04000000
252 PARALLEL(13,
253 set(Type.STREAM).clear(Type.OP));
254
255 // The following 2 flags are currently undefined and a free for any further
256 // stream flags if/when required
257 //
258 // 14, 0x10000000
259 // 15, 0x40000000
260
261 /**
262 * Type of a flag
263 */
264 enum Type {
265 /** The flag is associated with spliterator characteristics. */
266 SPLITERATOR,
267
268 /** The flag is associated with stream flags. */
269 STREAM,
270
271 /** The flag is associated with intermediate operation flags. */
272 OP,
273
274 /** The flag is associated with terminal operation flags. */
275 TERMINAL_OP,
276
277 /**
278 * The flag is associated with terminal operation flags that are propagated upstream
279 * across the last stateful operation boundary
280 */
281 UPSTREAM_TERMINAL_OP
282 }
283
284 /**
285 * The bit pattern for setting/injecting a flag.
286 */
287 private static final int SET_BITS = 0b01;
288
289 /**
290 * The bit pattern for clearing a flag.
291 */
292 private static final int CLEAR_BITS = 0b10;
293
294 /**
295 * The bit pattern for preserving a flag.
296 */
297 private static final int PRESERVE_BITS = 0b11;
298
299 private static MaskBuilder set(Type t) {
300 return new MaskBuilder(new EnumMap<>(Type.class)).set(t);
301 }
302
303 private static class MaskBuilder {
304 final Map<Type, Integer> map;
305
306 MaskBuilder(Map<Type, Integer> map) {
307 this.map = map;
308 }
309
310 MaskBuilder mask(Type t, Integer i) {
311 map.put(t, i);
312 return this;
313 }
314
315 MaskBuilder set(Type t) {
316 return mask(t, SET_BITS);
317 }
318
319 MaskBuilder clear(Type t) {
320 return mask(t, CLEAR_BITS);
321 }
322
323 MaskBuilder setAndClear(Type t) {
324 return mask(t, PRESERVE_BITS);
325 }
326
327 Map<Type, Integer> build() {
328 for (Type t : Type.values()) {
329 map.putIfAbsent(t, 0b00);
330 }
331 return map;
332 }
333 }
334
335 // The mask table for a flag, this is used to determine
336 // if a flag corresponds to a certain flag type and for creating
337 // mask constants.
338 private final Map<Type, Integer> maskTable;
339
340 // The bit position in the bit mask
341 private final int bitPosition;
342
343 // The set 2 bit set offset at the bit position
344 private final int set;
345
346 // The clear 2 bit set offset at the bit position
347 private final int clear;
348
349 // The preserve 2 bit set offset at the bit position
350 private final int preserve;
351
352 private StreamOpFlag(int position, MaskBuilder maskBuilder) {
353 this.maskTable = maskBuilder.build();
354 // Two bits per flag
355 position *= 2;
356 this.bitPosition = position;
357 this.set = SET_BITS << position;
358 this.clear = CLEAR_BITS << position;
359 this.preserve = PRESERVE_BITS << position;
360 }
361
362 /**
363 * Get the bitmap associated with setting this characteristic
364 * @return the bitmap for setting this characteristic
365 */
366 int set() {
367 return set;
368 }
369
370 /**
371 * Get the bitmap associated with clearing this characteristic
372 * @return the bitmap for clearing this characteristic
373 */
374 int clear() {
375 return clear;
376 }
377
378 /**
379 * Is this flag a stream-based flag?
380 *
381 * @return true if a stream-based flag, otherwise false.
382 */
383 boolean isStreamFlag() {
384 return maskTable.get(Type.STREAM) > 0;
385 }
386
387 /**
388 * Check if this flag is set on stream flags, injected on operation flags,
389 * and injected on combined stream and operation flags.
390 *
391 * @param flags the stream flags, operation flags, or combined stream and operation flags
392 * @return true if this flag is known, otherwise false.
393 */
394 boolean isKnown(int flags) {
395 return (flags & preserve) == set;
396 }
397
398 /**
399 * Check if this flag is cleared on operation flags or combined stream and operation flags.
400 *
401 * @param flags the operation flags or combined stream and operations flags.
402 * @return true if this flag is preserved, otherwise false.
403 */
404 boolean isCleared(int flags) {
405 return (flags & preserve) == clear;
406 }
407
408 /**
409 * Check if this flag is preserved on combined stream and operation flags.
410 *
411 * @param flags the combined stream and operations flags.
412 * @return true if this flag is preserved, otherwise false.
413 */
414 boolean isPreserved(int flags) {
415 return (flags & preserve) == preserve;
416 }
417
418 /**
419 *
420 * @param t the flag type.
421 * @return true if this flag can be set for the flag type, otherwise false.
422 */
423 boolean canSet(Type t) {
424 return (maskTable.get(t) & SET_BITS) > 0;
425 }
426
427 /**
428 * The bit mask for spliterator characteristics
429 */
430 static final int SPLITERATOR_CHARACTERISTICS_MASK = createMask(Type.SPLITERATOR);
431
432 /**
433 * The bit mask for source stream flags.
434 */
435 static final int STREAM_MASK = createMask(Type.STREAM);
436
437 /**
438 * The bit mask for intermediate operation flags.
439 */
440 static final int OP_MASK = createMask(Type.OP);
441
442 /**
443 * The bit mask for terminal operation flags.
444 */
445 static final int TERMINAL_OP_MASK = createMask(Type.TERMINAL_OP);
446
447 /**
448 * The bit mask for upstream terminal operation flags.
449 */
450 static final int UPSTREAM_TERMINAL_OP_MASK = createMask(Type.UPSTREAM_TERMINAL_OP);
451
452 private static int createMask(Type t) {
453 int mask = 0;
454 for (StreamOpFlag flag : StreamOpFlag.values()) {
455 mask |= flag.maskTable.get(t) << flag.bitPosition;
456 }
457 return mask;
458 }
459
460 // Complete flag mask
461 private static final int FLAG_MASK = createFlagMask();
462
463 private static int createFlagMask() {
464 int mask = 0;
465 for (StreamOpFlag flag : StreamOpFlag.values()) {
466 mask |= flag.preserve;
467 }
468 return mask;
469 }
470
471 // Flag mask for stream flags that are set
472 private static final int FLAG_MASK_IS = STREAM_MASK;
473
474 // Flag mask for stream flags that are cleared
475 private static final int FLAG_MASK_NOT = STREAM_MASK << 1;
476
477 /**
478 * The initial value to be combined with the stream flags of the first stream in the pipeline.
479 */
480 static final int INITIAL_OPS_VALUE = FLAG_MASK_IS | FLAG_MASK_NOT;
481
482 /**
483 * The bit value to set or inject {@link #DISTINCT}
484 */
485 static final int IS_DISTINCT = DISTINCT.set;
486
487 /**
488 * The bit value to clear {@link #DISTINCT}
489 */
490 static final int NOT_DISTINCT = DISTINCT.clear;
491
492 /**
493 * The bit value to set or inject {@link #SORTED}
494 */
495 static final int IS_SORTED = SORTED.set;
496
497 /**
498 * The bit value to clear {@link #SORTED}
499 */
500 static final int NOT_SORTED = SORTED.clear;
501
502 /**
503 * The bit value to set or inject {@link #ORDERED}
504 */
505 static final int IS_ORDERED = ORDERED.set;
506
507 /**
508 * The bit value to clear {@link #ORDERED}
509 */
510 static final int NOT_ORDERED = ORDERED.clear;
511
512 /**
513 * The bit value to set {@link #SIZED}
514 */
515 static final int IS_SIZED = SIZED.set;
516
517 /**
518 * The bit value to clear {@link #SIZED}
519 */
520 static final int NOT_SIZED = SIZED.clear;
521
522 /**
523 * The bit value to inject {@link #SHORT_CIRCUIT}
524 */
525 static final int IS_SHORT_CIRCUIT = SHORT_CIRCUIT.set;
526
527 /**
528 * The bit value to set {@link #PARALLEL}
529 */
530 static final int IS_PARALLEL = PARALLEL.set;
531
532 /**
533 * The bit value to clear {@link #PARALLEL}
534 */
535 static final int NOT_PARALLEL = PARALLEL.clear;
536
537 private static int getMask(int flags) {
538 return (flags == 0)
539 ? FLAG_MASK
540 : ~(flags | ((FLAG_MASK_IS & flags) << 1) | ((FLAG_MASK_NOT & flags) >> 1));
541 }
542
543 /**
544 * Combine stream or operation flags with previously combined stream and operation flags to
545 * produce updated combined stream and operation flags.
546 * <p>
547 * A flag set on stream flags or injected on operation flags,
548 * and injected combined stream and operation flags,
549 * will be injected on the updated combined stream and operation flags.
550 * </p>
551 * <p>
552 * A flag set on stream flags or injected on operation flags,
553 * and cleared on the combined stream and operation flags,
554 * will be cleared on the updated combined stream and operation flags.
555 * </p>
556 * <p>
557 * A flag set on the stream flags or injected on operation flags,
558 * and preserved on the combined stream and operation flags,
559 * will be injected on the updated combined stream and operation flags.
560 * </p>
561 * <p>
562 * A flag not set on the stream flags or cleared/preserved on operation flags,
563 * and injected on the combined stream and operation flags,
564 * will be injected on the updated combined stream and operation flags.
565 * </p>
566 * <p>
567 * A flag not set on the stream flags or cleared/preserved on operation flags,
568 * and cleared on the combined stream and operation flags,
569 * will be cleared on the updated combined stream and operation flags.
570 * </p>
571 * <p>
572 * A flag not set on the stream flags,
573 * and preserved on the combined stream and operation flags
574 * will be preserved on the updated combined stream and operation flags.
575 * </p>
576 * <p>
577 * A flag cleared on operation flags,
578 * and preserved on the combined stream and operation flags
579 * will be cleared on the updated combined stream and operation flags.
580 * </p>
581 * <p>
582 * A flag preserved on operation flags,
583 * and preserved on the combined stream and operation flags
584 * will be preserved on the updated combined stream and operation flags.
585 * </p>
586 *
587 * @param newStreamOrOpFlags the stream or operation flags.
588 * @param prevCombOpFlags previously combined stream and operation flags.
589 * The value {#link INITIAL_OPS_VALUE} must be used as the seed value.
590 * @return the updated combined stream and operation flags.
591 */
592 static int combineOpFlags(int newStreamOrOpFlags, int prevCombOpFlags) {
593 // 0x01 or 0x10 nibbles are transformed to 0x11
594 // 0x00 nibbles remain unchanged
595 // Then all the bits are flipped
596 // Then the result is logically or'ed with the operation flags.
597 return (prevCombOpFlags & StreamOpFlag.getMask(newStreamOrOpFlags)) | newStreamOrOpFlags;
598 }
599
600 /**
601 * Convert combined stream and operation flags to stream flags.
602 *
603 * <p> Each flag injected on the combined stream and operation flags will be set on the stream flags.
604 *
605 * @param combOpFlags the combined stream and operation flags.
606 * @return the stream flags.
607 */
608 static int toStreamFlags(int combOpFlags) {
609 // By flipping the nibbles 0x11 become 0x00 and 0x01 become 0x10
610 // Shift left 1 to restore set flags and mask off anything other than the set flags
611 return ((~combOpFlags) >> 1) & FLAG_MASK_IS & combOpFlags;
612 }
613
614 /**
615 * Convert stream flags to a spliterator characteristic bit set.
616 *
617 * @param streamFlags the stream flags.
618 * @return the spliterator characteristic bit set.
619 */
620 static int toCharacteristics(int streamFlags) {
621 return streamFlags & SPLITERATOR_CHARACTERISTICS_MASK;
622 }
623
624 /**
625 * Convert a spliterator characteristic bit set to stream flags.
626 *
627 * @param characteristics the spliterator characteristic bit set.
628 * @return the stream flags.
629 */
630 static int fromCharacteristics(int characteristics) {
631 return characteristics & SPLITERATOR_CHARACTERISTICS_MASK;
632 }
633 }