001/* 002 * Copyright (C) 2015 The Guava Authors 003 * 004 * Licensed under the Apache License, Version 2.0 (the "License"); 005 * you may not use this file except in compliance with the License. 006 * You may obtain a copy of the License at 007 * 008 * http://www.apache.org/licenses/LICENSE-2.0 009 * 010 * Unless required by applicable law or agreed to in writing, software 011 * distributed under the License is distributed on an "AS IS" BASIS, 012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 013 * See the License for the specific language governing permissions and 014 * limitations under the License. 015 */ 016 017package com.google.common.collect.testing; 018 019import static com.google.common.base.Preconditions.checkNotNull; 020import static com.google.common.collect.testing.Helpers.assertEqualIgnoringOrder; 021import static com.google.common.collect.testing.Helpers.assertEqualInOrder; 022import static com.google.common.collect.testing.Platform.format; 023import static java.util.Arrays.asList; 024import static java.util.Collections.unmodifiableSet; 025import static junit.framework.Assert.assertEquals; 026import static junit.framework.Assert.assertFalse; 027import static junit.framework.Assert.assertTrue; 028import static junit.framework.Assert.fail; 029 030import com.google.common.annotations.GwtCompatible; 031import com.google.common.collect.ImmutableSet; 032import com.google.common.collect.Ordering; 033import com.google.common.primitives.Ints; 034import com.google.errorprone.annotations.CanIgnoreReturnValue; 035import java.util.ArrayList; 036import java.util.Arrays; 037import java.util.Comparator; 038import java.util.LinkedHashSet; 039import java.util.List; 040import java.util.Set; 041import java.util.Spliterator; 042import java.util.Spliterator.OfPrimitive; 043import java.util.function.Consumer; 044import java.util.function.Function; 045import java.util.function.Supplier; 046import org.checkerframework.checker.nullness.qual.Nullable; 047 048/** 049 * Tester for {@code Spliterator} implementations. 050 * 051 * @since 21.0 052 */ 053@GwtCompatible 054@ElementTypesAreNonnullByDefault 055public final class SpliteratorTester<E extends @Nullable Object> { 056 /** Return type from "contains the following elements" assertions. */ 057 public interface Ordered { 058 /** 059 * Attests that the expected values must not just be present but must be present in the order 060 * they were given. 061 */ 062 void inOrder(); 063 } 064 065 private abstract static class GeneralSpliterator<E extends @Nullable Object> { 066 final Spliterator<E> spliterator; 067 068 GeneralSpliterator(Spliterator<E> spliterator) { 069 this.spliterator = checkNotNull(spliterator); 070 } 071 072 abstract void forEachRemaining(Consumer<? super E> action); 073 074 abstract boolean tryAdvance(Consumer<? super E> action); 075 076 abstract @Nullable GeneralSpliterator<E> trySplit(); 077 078 final int characteristics() { 079 return spliterator.characteristics(); 080 } 081 082 final long estimateSize() { 083 return spliterator.estimateSize(); 084 } 085 086 final Comparator<? super E> getComparator() { 087 return spliterator.getComparator(); 088 } 089 090 final long getExactSizeIfKnown() { 091 return spliterator.getExactSizeIfKnown(); 092 } 093 094 final boolean hasCharacteristics(int characteristics) { 095 return spliterator.hasCharacteristics(characteristics); 096 } 097 } 098 099 private static final class GeneralSpliteratorOfObject<E extends @Nullable Object> 100 extends GeneralSpliterator<E> { 101 GeneralSpliteratorOfObject(Spliterator<E> spliterator) { 102 super(spliterator); 103 } 104 105 @Override 106 void forEachRemaining(Consumer<? super E> action) { 107 spliterator.forEachRemaining(action); 108 } 109 110 @Override 111 boolean tryAdvance(Consumer<? super E> action) { 112 return spliterator.tryAdvance(action); 113 } 114 115 @Override 116 @Nullable GeneralSpliterator<E> trySplit() { 117 Spliterator<E> split = spliterator.trySplit(); 118 return split == null ? null : new GeneralSpliteratorOfObject<>(split); 119 } 120 } 121 122 private static final class GeneralSpliteratorOfPrimitive< 123 E extends @Nullable Object, C, S extends Spliterator.OfPrimitive<E, C, S>> 124 extends GeneralSpliterator<E> { 125 final OfPrimitive<E, C, S> spliteratorOfPrimitive; 126 final Function<Consumer<? super E>, C> consumerizer; 127 128 GeneralSpliteratorOfPrimitive( 129 Spliterator.OfPrimitive<E, C, S> spliterator, 130 Function<Consumer<? super E>, C> consumerizer) { 131 super(spliterator); 132 this.spliteratorOfPrimitive = spliterator; 133 this.consumerizer = consumerizer; 134 } 135 136 @Override 137 void forEachRemaining(Consumer<? super E> action) { 138 spliteratorOfPrimitive.forEachRemaining(consumerizer.apply(action)); 139 } 140 141 @Override 142 boolean tryAdvance(Consumer<? super E> action) { 143 return spliteratorOfPrimitive.tryAdvance(consumerizer.apply(action)); 144 } 145 146 @Override 147 @Nullable GeneralSpliterator<E> trySplit() { 148 Spliterator.OfPrimitive<E, C, ?> split = spliteratorOfPrimitive.trySplit(); 149 return split == null ? null : new GeneralSpliteratorOfPrimitive<>(split, consumerizer); 150 } 151 } 152 153 /** 154 * Different ways of decomposing a Spliterator, all of which must produce the same elements (up to 155 * ordering, if Spliterator.ORDERED is not present). 156 */ 157 enum SpliteratorDecompositionStrategy { 158 NO_SPLIT_FOR_EACH_REMAINING { 159 @Override 160 <E extends @Nullable Object> void forEach( 161 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 162 spliterator.forEachRemaining(consumer); 163 } 164 }, 165 NO_SPLIT_TRY_ADVANCE { 166 @Override 167 <E extends @Nullable Object> void forEach( 168 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 169 while (spliterator.tryAdvance(consumer)) { 170 // do nothing 171 } 172 } 173 }, 174 MAXIMUM_SPLIT { 175 @Override 176 <E extends @Nullable Object> void forEach( 177 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 178 for (GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator); 179 prefix != null; 180 prefix = trySplitTestingSize(spliterator)) { 181 forEach(prefix, consumer); 182 } 183 long size = spliterator.getExactSizeIfKnown(); 184 long[] counter = {0}; 185 spliterator.forEachRemaining( 186 e -> { 187 consumer.accept(e); 188 counter[0]++; 189 }); 190 if (size >= 0) { 191 assertEquals(size, counter[0]); 192 } 193 } 194 }, 195 ALTERNATE_ADVANCE_AND_SPLIT { 196 @Override 197 <E extends @Nullable Object> void forEach( 198 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 199 while (spliterator.tryAdvance(consumer)) { 200 GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator); 201 if (prefix != null) { 202 forEach(prefix, consumer); 203 } 204 } 205 } 206 }; 207 208 abstract <E extends @Nullable Object> void forEach( 209 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer); 210 211 static final Set<SpliteratorDecompositionStrategy> ALL_STRATEGIES = 212 unmodifiableSet(new LinkedHashSet<>(asList(values()))); 213 } 214 215 private static <E extends @Nullable Object> @Nullable GeneralSpliterator<E> trySplitTestingSize( 216 GeneralSpliterator<E> spliterator) { 217 boolean subsized = spliterator.hasCharacteristics(Spliterator.SUBSIZED); 218 long originalSize = spliterator.estimateSize(); 219 GeneralSpliterator<E> trySplit = spliterator.trySplit(); 220 if (spliterator.estimateSize() > originalSize) { 221 fail( 222 format( 223 "estimated size of spliterator after trySplit (%s) is larger than original size (%s)", 224 spliterator.estimateSize(), originalSize)); 225 } 226 if (trySplit != null) { 227 if (trySplit.estimateSize() > originalSize) { 228 fail( 229 format( 230 "estimated size of trySplit result (%s) is larger than original size (%s)", 231 trySplit.estimateSize(), originalSize)); 232 } 233 } 234 if (subsized) { 235 if (trySplit != null) { 236 assertEquals( 237 "sum of estimated sizes of trySplit and original spliterator after trySplit", 238 originalSize, 239 trySplit.estimateSize() + spliterator.estimateSize()); 240 } else { 241 assertEquals( 242 "estimated size of spliterator after failed trySplit", 243 originalSize, 244 spliterator.estimateSize()); 245 } 246 } 247 return trySplit; 248 } 249 250 public static <E extends @Nullable Object> SpliteratorTester<E> of( 251 Supplier<Spliterator<E>> spliteratorSupplier) { 252 return new SpliteratorTester<>( 253 ImmutableSet.of(() -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()))); 254 } 255 256 /** 257 * @since 28.1 258 */ 259 public static SpliteratorTester<Integer> ofInt(Supplier<Spliterator.OfInt> spliteratorSupplier) { 260 return new SpliteratorTester<>( 261 ImmutableSet.of( 262 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 263 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 264 } 265 266 /** 267 * @since 28.1 268 */ 269 public static SpliteratorTester<Long> ofLong(Supplier<Spliterator.OfLong> spliteratorSupplier) { 270 return new SpliteratorTester<>( 271 ImmutableSet.of( 272 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 273 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 274 } 275 276 /** 277 * @since 28.1 278 */ 279 public static SpliteratorTester<Double> ofDouble( 280 Supplier<Spliterator.OfDouble> spliteratorSupplier) { 281 return new SpliteratorTester<>( 282 ImmutableSet.of( 283 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 284 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 285 } 286 287 private final ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers; 288 289 private SpliteratorTester(ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers) { 290 this.spliteratorSuppliers = checkNotNull(spliteratorSuppliers); 291 } 292 293 @SafeVarargs 294 @CanIgnoreReturnValue 295 public final Ordered expect(Object... elements) { 296 return expect(Arrays.asList(elements)); 297 } 298 299 @CanIgnoreReturnValue 300 public final Ordered expect(Iterable<?> elements) { 301 List<List<E>> resultsForAllStrategies = new ArrayList<>(); 302 for (Supplier<GeneralSpliterator<E>> spliteratorSupplier : spliteratorSuppliers) { 303 GeneralSpliterator<E> spliterator = spliteratorSupplier.get(); 304 int characteristics = spliterator.characteristics(); 305 long estimatedSize = spliterator.estimateSize(); 306 for (SpliteratorDecompositionStrategy strategy : 307 SpliteratorDecompositionStrategy.ALL_STRATEGIES) { 308 List<E> resultsForStrategy = new ArrayList<>(); 309 strategy.forEach(spliteratorSupplier.get(), resultsForStrategy::add); 310 311 // TODO(cpovirk): better failure messages 312 if ((characteristics & Spliterator.NONNULL) != 0) { 313 assertFalse(resultsForStrategy.contains(null)); 314 } 315 if ((characteristics & Spliterator.SORTED) != 0) { 316 Comparator<? super E> comparator = spliterator.getComparator(); 317 if (comparator == null) { 318 // A sorted spliterator with no comparator is already using natural order. 319 // (We could probably find a way to avoid rawtypes here if we wanted.) 320 @SuppressWarnings({"unchecked", "rawtypes"}) 321 Comparator<? super E> naturalOrder = 322 (Comparator<? super E>) Comparator.<Comparable>naturalOrder(); 323 comparator = naturalOrder; 324 } 325 assertTrue(Ordering.from(comparator).isOrdered(resultsForStrategy)); 326 } 327 if ((characteristics & Spliterator.SIZED) != 0) { 328 assertEquals(Ints.checkedCast(estimatedSize), resultsForStrategy.size()); 329 } 330 331 assertEqualIgnoringOrder(elements, resultsForStrategy); 332 resultsForAllStrategies.add(resultsForStrategy); 333 } 334 } 335 return new Ordered() { 336 @Override 337 public void inOrder() { 338 for (List<E> resultsForStrategy : resultsForAllStrategies) { 339 assertEqualInOrder(elements, resultsForStrategy); 340 } 341 } 342 }; 343 } 344}