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/** Tester for {@code Spliterator} implementations. */ 049@GwtCompatible 050@ElementTypesAreNonnullByDefault 051public final class SpliteratorTester<E extends @Nullable Object> { 052 /** Return type from "contains the following elements" assertions. */ 053 public interface Ordered { 054 /** 055 * Attests that the expected values must not just be present but must be present in the order 056 * they were given. 057 */ 058 void inOrder(); 059 } 060 061 private abstract static class GeneralSpliterator<E extends @Nullable Object> { 062 final Spliterator<E> spliterator; 063 064 GeneralSpliterator(Spliterator<E> spliterator) { 065 this.spliterator = checkNotNull(spliterator); 066 } 067 068 abstract void forEachRemaining(Consumer<? super E> action); 069 070 abstract boolean tryAdvance(Consumer<? super E> action); 071 072 abstract @Nullable GeneralSpliterator<E> trySplit(); 073 074 final int characteristics() { 075 return spliterator.characteristics(); 076 } 077 078 final long estimateSize() { 079 return spliterator.estimateSize(); 080 } 081 082 final Comparator<? super E> getComparator() { 083 return spliterator.getComparator(); 084 } 085 086 final long getExactSizeIfKnown() { 087 return spliterator.getExactSizeIfKnown(); 088 } 089 090 final boolean hasCharacteristics(int characteristics) { 091 return spliterator.hasCharacteristics(characteristics); 092 } 093 } 094 095 private static final class GeneralSpliteratorOfObject<E extends @Nullable Object> 096 extends GeneralSpliterator<E> { 097 GeneralSpliteratorOfObject(Spliterator<E> spliterator) { 098 super(spliterator); 099 } 100 101 @Override 102 void forEachRemaining(Consumer<? super E> action) { 103 spliterator.forEachRemaining(action); 104 } 105 106 @Override 107 boolean tryAdvance(Consumer<? super E> action) { 108 return spliterator.tryAdvance(action); 109 } 110 111 @Override 112 @Nullable GeneralSpliterator<E> trySplit() { 113 Spliterator<E> split = spliterator.trySplit(); 114 return split == null ? null : new GeneralSpliteratorOfObject<>(split); 115 } 116 } 117 118 private static final class GeneralSpliteratorOfPrimitive< 119 E extends @Nullable Object, C, S extends Spliterator.OfPrimitive<E, C, S>> 120 extends GeneralSpliterator<E> { 121 final OfPrimitive<E, C, S> spliteratorOfPrimitive; 122 final Function<Consumer<? super E>, C> consumerizer; 123 124 GeneralSpliteratorOfPrimitive( 125 Spliterator.OfPrimitive<E, C, S> spliterator, 126 Function<Consumer<? super E>, C> consumerizer) { 127 super(spliterator); 128 this.spliteratorOfPrimitive = spliterator; 129 this.consumerizer = consumerizer; 130 } 131 132 @Override 133 void forEachRemaining(Consumer<? super E> action) { 134 spliteratorOfPrimitive.forEachRemaining(consumerizer.apply(action)); 135 } 136 137 @Override 138 boolean tryAdvance(Consumer<? super E> action) { 139 return spliteratorOfPrimitive.tryAdvance(consumerizer.apply(action)); 140 } 141 142 @Override 143 @Nullable GeneralSpliterator<E> trySplit() { 144 Spliterator.OfPrimitive<E, C, ?> split = spliteratorOfPrimitive.trySplit(); 145 return split == null ? null : new GeneralSpliteratorOfPrimitive<>(split, consumerizer); 146 } 147 } 148 149 /** 150 * Different ways of decomposing a Spliterator, all of which must produce the same elements (up to 151 * ordering, if Spliterator.ORDERED is not present). 152 */ 153 enum SpliteratorDecompositionStrategy { 154 NO_SPLIT_FOR_EACH_REMAINING { 155 @Override 156 <E extends @Nullable Object> void forEach( 157 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 158 spliterator.forEachRemaining(consumer); 159 } 160 }, 161 NO_SPLIT_TRY_ADVANCE { 162 @Override 163 <E extends @Nullable Object> void forEach( 164 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 165 while (spliterator.tryAdvance(consumer)) { 166 // do nothing 167 } 168 } 169 }, 170 MAXIMUM_SPLIT { 171 @Override 172 <E extends @Nullable Object> void forEach( 173 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 174 for (GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator); 175 prefix != null; 176 prefix = trySplitTestingSize(spliterator)) { 177 forEach(prefix, consumer); 178 } 179 long size = spliterator.getExactSizeIfKnown(); 180 long[] counter = {0}; 181 spliterator.forEachRemaining( 182 e -> { 183 consumer.accept(e); 184 counter[0]++; 185 }); 186 if (size >= 0) { 187 assertEquals(size, counter[0]); 188 } 189 } 190 }, 191 ALTERNATE_ADVANCE_AND_SPLIT { 192 @Override 193 <E extends @Nullable Object> void forEach( 194 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 195 while (spliterator.tryAdvance(consumer)) { 196 GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator); 197 if (prefix != null) { 198 forEach(prefix, consumer); 199 } 200 } 201 } 202 }; 203 204 abstract <E extends @Nullable Object> void forEach( 205 GeneralSpliterator<E> spliterator, Consumer<? super E> consumer); 206 207 static final Set<SpliteratorDecompositionStrategy> ALL_STRATEGIES = 208 unmodifiableSet(new LinkedHashSet<>(asList(values()))); 209 } 210 211 private static <E extends @Nullable Object> @Nullable GeneralSpliterator<E> trySplitTestingSize( 212 GeneralSpliterator<E> spliterator) { 213 boolean subsized = spliterator.hasCharacteristics(Spliterator.SUBSIZED); 214 long originalSize = spliterator.estimateSize(); 215 GeneralSpliterator<E> trySplit = spliterator.trySplit(); 216 if (spliterator.estimateSize() > originalSize) { 217 fail( 218 format( 219 "estimated size of spliterator after trySplit (%s) is larger than original size (%s)", 220 spliterator.estimateSize(), originalSize)); 221 } 222 if (trySplit != null) { 223 if (trySplit.estimateSize() > originalSize) { 224 fail( 225 format( 226 "estimated size of trySplit result (%s) is larger than original size (%s)", 227 trySplit.estimateSize(), originalSize)); 228 } 229 } 230 if (subsized) { 231 if (trySplit != null) { 232 assertEquals( 233 "sum of estimated sizes of trySplit and original spliterator after trySplit", 234 originalSize, 235 trySplit.estimateSize() + spliterator.estimateSize()); 236 } else { 237 assertEquals( 238 "estimated size of spliterator after failed trySplit", 239 originalSize, 240 spliterator.estimateSize()); 241 } 242 } 243 return trySplit; 244 } 245 246 public static <E extends @Nullable Object> SpliteratorTester<E> of( 247 Supplier<Spliterator<E>> spliteratorSupplier) { 248 return new SpliteratorTester<>( 249 ImmutableSet.of(() -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()))); 250 } 251 252 /** 253 * @since 28.1 254 */ 255 public static SpliteratorTester<Integer> ofInt(Supplier<Spliterator.OfInt> spliteratorSupplier) { 256 return new SpliteratorTester<>( 257 ImmutableSet.of( 258 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 259 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 260 } 261 262 /** 263 * @since 28.1 264 */ 265 public static SpliteratorTester<Long> ofLong(Supplier<Spliterator.OfLong> spliteratorSupplier) { 266 return new SpliteratorTester<>( 267 ImmutableSet.of( 268 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 269 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 270 } 271 272 /** 273 * @since 28.1 274 */ 275 public static SpliteratorTester<Double> ofDouble( 276 Supplier<Spliterator.OfDouble> spliteratorSupplier) { 277 return new SpliteratorTester<>( 278 ImmutableSet.of( 279 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 280 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 281 } 282 283 private final ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers; 284 285 private SpliteratorTester(ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers) { 286 this.spliteratorSuppliers = checkNotNull(spliteratorSuppliers); 287 } 288 289 @SafeVarargs 290 @CanIgnoreReturnValue 291 public final Ordered expect(Object... elements) { 292 return expect(Arrays.asList(elements)); 293 } 294 295 @CanIgnoreReturnValue 296 public final Ordered expect(Iterable<?> elements) { 297 List<List<E>> resultsForAllStrategies = new ArrayList<>(); 298 for (Supplier<GeneralSpliterator<E>> spliteratorSupplier : spliteratorSuppliers) { 299 GeneralSpliterator<E> spliterator = spliteratorSupplier.get(); 300 int characteristics = spliterator.characteristics(); 301 long estimatedSize = spliterator.estimateSize(); 302 for (SpliteratorDecompositionStrategy strategy : 303 SpliteratorDecompositionStrategy.ALL_STRATEGIES) { 304 List<E> resultsForStrategy = new ArrayList<>(); 305 strategy.forEach(spliteratorSupplier.get(), resultsForStrategy::add); 306 307 // TODO(cpovirk): better failure messages 308 if ((characteristics & Spliterator.NONNULL) != 0) { 309 assertFalse(resultsForStrategy.contains(null)); 310 } 311 if ((characteristics & Spliterator.SORTED) != 0) { 312 Comparator<? super E> comparator = spliterator.getComparator(); 313 if (comparator == null) { 314 // A sorted spliterator with no comparator is already using natural order. 315 // (We could probably find a way to avoid rawtypes here if we wanted.) 316 @SuppressWarnings({"unchecked", "rawtypes"}) 317 Comparator<? super E> naturalOrder = 318 (Comparator<? super E>) Comparator.<Comparable>naturalOrder(); 319 comparator = naturalOrder; 320 } 321 assertTrue(Ordering.from(comparator).isOrdered(resultsForStrategy)); 322 } 323 if ((characteristics & Spliterator.SIZED) != 0) { 324 assertEquals(Ints.checkedCast(estimatedSize), resultsForStrategy.size()); 325 } 326 327 assertEqualIgnoringOrder(elements, resultsForStrategy); 328 resultsForAllStrategies.add(resultsForStrategy); 329 } 330 } 331 return new Ordered() { 332 @Override 333 public void inOrder() { 334 for (List<E> resultsForStrategy : resultsForAllStrategies) { 335 assertEqualInOrder(elements, resultsForStrategy); 336 } 337 } 338 }; 339 } 340}