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.Comparator.naturalOrder; 024import static junit.framework.Assert.assertEquals; 025import static junit.framework.Assert.assertFalse; 026import static junit.framework.Assert.assertTrue; 027import static junit.framework.Assert.fail; 028 029import com.google.common.annotations.GwtCompatible; 030import com.google.common.collect.ImmutableSet; 031import com.google.common.collect.Ordering; 032import com.google.common.primitives.Ints; 033import java.util.ArrayList; 034import java.util.Arrays; 035import java.util.Comparator; 036import java.util.EnumSet; 037import java.util.List; 038import java.util.Spliterator; 039import java.util.function.Consumer; 040import java.util.function.Function; 041import java.util.function.Supplier; 042import org.checkerframework.checker.nullness.qual.Nullable; 043 044/** Tester for {@code Spliterator} implementations. */ 045@GwtCompatible 046public final class SpliteratorTester<E> { 047 /** Return type from "contains the following elements" assertions. */ 048 public interface Ordered { 049 /** 050 * Attests that the expected values must not just be present but must be present in the order 051 * they were given. 052 */ 053 void inOrder(); 054 } 055 056 private abstract static class GeneralSpliterator<E> { 057 final Spliterator<E> spliterator; 058 059 GeneralSpliterator(Spliterator<E> spliterator) { 060 this.spliterator = checkNotNull(spliterator); 061 } 062 063 abstract void forEachRemaining(Consumer<? super E> action); 064 065 abstract boolean tryAdvance(Consumer<? super E> action); 066 067 abstract GeneralSpliterator<E> trySplit(); 068 069 final int characteristics() { 070 return spliterator.characteristics(); 071 } 072 073 final long estimateSize() { 074 return spliterator.estimateSize(); 075 } 076 077 final Comparator<? super E> getComparator() { 078 return spliterator.getComparator(); 079 } 080 081 final long getExactSizeIfKnown() { 082 return spliterator.getExactSizeIfKnown(); 083 } 084 085 final boolean hasCharacteristics(int characteristics) { 086 return spliterator.hasCharacteristics(characteristics); 087 } 088 } 089 090 private static final class GeneralSpliteratorOfObject<E> extends GeneralSpliterator<E> { 091 GeneralSpliteratorOfObject(Spliterator<E> spliterator) { 092 super(spliterator); 093 } 094 095 @Override 096 void forEachRemaining(Consumer<? super E> action) { 097 spliterator.forEachRemaining(action); 098 } 099 100 @Override 101 boolean tryAdvance(Consumer<? super E> action) { 102 return spliterator.tryAdvance(action); 103 } 104 105 @Override 106 GeneralSpliterator<E> trySplit() { 107 Spliterator<E> split = spliterator.trySplit(); 108 return split == null ? null : new GeneralSpliteratorOfObject<>(split); 109 } 110 } 111 112 /* 113 * The AndroidJdkLibsChecker violation is informing us that this method isn't usable under 114 * Desugar. But we want to include it here for Nougat+ users -- and, mainly, for non-Android 115 * users. Fortunately, anyone who tries to use it under Desugar will presumably already see errors 116 * from creating the Spliterator.OfInt in the first place. So it's probably OK for us to suppress 117 * this particular violation. 118 */ 119 @SuppressWarnings("AndroidJdkLibsChecker") 120 private static final class GeneralSpliteratorOfPrimitive<E, C> extends GeneralSpliterator<E> { 121 final Spliterator.OfPrimitive<E, C, ?> spliterator; 122 final Function<Consumer<? super E>, C> consumerizer; 123 124 GeneralSpliteratorOfPrimitive( 125 Spliterator.OfPrimitive<E, C, ?> spliterator, 126 Function<Consumer<? super E>, C> consumerizer) { 127 super(spliterator); 128 this.spliterator = spliterator; 129 this.consumerizer = consumerizer; 130 } 131 132 @Override 133 void forEachRemaining(Consumer<? super E> action) { 134 spliterator.forEachRemaining(consumerizer.apply(action)); 135 } 136 137 @Override 138 boolean tryAdvance(Consumer<? super E> action) { 139 return spliterator.tryAdvance(consumerizer.apply(action)); 140 } 141 142 @Override 143 GeneralSpliterator<E> trySplit() { 144 Spliterator.OfPrimitive<E, C, ?> split = spliterator.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> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 157 spliterator.forEachRemaining(consumer); 158 } 159 }, 160 NO_SPLIT_TRY_ADVANCE { 161 @Override 162 <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 163 while (spliterator.tryAdvance(consumer)) { 164 // do nothing 165 } 166 } 167 }, 168 MAXIMUM_SPLIT { 169 @Override 170 <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 171 for (GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator); 172 prefix != null; 173 prefix = trySplitTestingSize(spliterator)) { 174 forEach(prefix, consumer); 175 } 176 long size = spliterator.getExactSizeIfKnown(); 177 long[] counter = {0}; 178 spliterator.forEachRemaining( 179 e -> { 180 consumer.accept(e); 181 counter[0]++; 182 }); 183 if (size >= 0) { 184 assertEquals(size, counter[0]); 185 } 186 } 187 }, 188 ALTERNATE_ADVANCE_AND_SPLIT { 189 @Override 190 <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer) { 191 while (spliterator.tryAdvance(consumer)) { 192 GeneralSpliterator<E> prefix = trySplitTestingSize(spliterator); 193 if (prefix != null) { 194 forEach(prefix, consumer); 195 } 196 } 197 } 198 }; 199 200 abstract <E> void forEach(GeneralSpliterator<E> spliterator, Consumer<? super E> consumer); 201 } 202 203 private static <E> @Nullable GeneralSpliterator<E> trySplitTestingSize( 204 GeneralSpliterator<E> spliterator) { 205 boolean subsized = spliterator.hasCharacteristics(Spliterator.SUBSIZED); 206 long originalSize = spliterator.estimateSize(); 207 GeneralSpliterator<E> trySplit = spliterator.trySplit(); 208 if (spliterator.estimateSize() > originalSize) { 209 fail( 210 format( 211 "estimated size of spliterator after trySplit (%s) is larger than original size (%s)", 212 spliterator.estimateSize(), originalSize)); 213 } 214 if (trySplit != null) { 215 if (trySplit.estimateSize() > originalSize) { 216 fail( 217 format( 218 "estimated size of trySplit result (%s) is larger than original size (%s)", 219 trySplit.estimateSize(), originalSize)); 220 } 221 } 222 if (subsized) { 223 if (trySplit != null) { 224 assertEquals( 225 "sum of estimated sizes of trySplit and original spliterator after trySplit", 226 originalSize, 227 trySplit.estimateSize() + spliterator.estimateSize()); 228 } else { 229 assertEquals( 230 "estimated size of spliterator after failed trySplit", 231 originalSize, 232 spliterator.estimateSize()); 233 } 234 } 235 return trySplit; 236 } 237 238 public static <E> SpliteratorTester<E> of(Supplier<Spliterator<E>> spliteratorSupplier) { 239 return new SpliteratorTester<>( 240 ImmutableSet.of(() -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()))); 241 } 242 243 /** @since 28.1 */ 244 @SuppressWarnings("AndroidJdkLibsChecker") // see comment on GeneralSpliteratorOfPrimitive 245 public static SpliteratorTester<Integer> ofInt(Supplier<Spliterator.OfInt> spliteratorSupplier) { 246 return new SpliteratorTester<>( 247 ImmutableSet.of( 248 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 249 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 250 } 251 252 /** @since 28.1 */ 253 @SuppressWarnings("AndroidJdkLibsChecker") // see comment on GeneralSpliteratorOfPrimitive 254 public static SpliteratorTester<Long> ofLong(Supplier<Spliterator.OfLong> spliteratorSupplier) { 255 return new SpliteratorTester<>( 256 ImmutableSet.of( 257 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 258 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 259 } 260 261 /** @since 28.1 */ 262 @SuppressWarnings("AndroidJdkLibsChecker") // see comment on GeneralSpliteratorOfPrimitive 263 public static SpliteratorTester<Double> ofDouble( 264 Supplier<Spliterator.OfDouble> spliteratorSupplier) { 265 return new SpliteratorTester<>( 266 ImmutableSet.of( 267 () -> new GeneralSpliteratorOfObject<>(spliteratorSupplier.get()), 268 () -> new GeneralSpliteratorOfPrimitive<>(spliteratorSupplier.get(), c -> c::accept))); 269 } 270 271 private final ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers; 272 273 private SpliteratorTester(ImmutableSet<Supplier<GeneralSpliterator<E>>> spliteratorSuppliers) { 274 this.spliteratorSuppliers = checkNotNull(spliteratorSuppliers); 275 } 276 277 @SafeVarargs 278 public final Ordered expect(Object... elements) { 279 return expect(Arrays.asList(elements)); 280 } 281 282 public final Ordered expect(Iterable<?> elements) { 283 List<List<E>> resultsForAllStrategies = new ArrayList<>(); 284 for (Supplier<GeneralSpliterator<E>> spliteratorSupplier : spliteratorSuppliers) { 285 GeneralSpliterator<E> spliterator = spliteratorSupplier.get(); 286 int characteristics = spliterator.characteristics(); 287 long estimatedSize = spliterator.estimateSize(); 288 for (SpliteratorDecompositionStrategy strategy : 289 EnumSet.allOf(SpliteratorDecompositionStrategy.class)) { 290 List<E> resultsForStrategy = new ArrayList<>(); 291 strategy.forEach(spliteratorSupplier.get(), resultsForStrategy::add); 292 293 // TODO(cpovirk): better failure messages 294 if ((characteristics & Spliterator.NONNULL) != 0) { 295 assertFalse(resultsForStrategy.contains(null)); 296 } 297 if ((characteristics & Spliterator.SORTED) != 0) { 298 Comparator<? super E> comparator = spliterator.getComparator(); 299 if (comparator == null) { 300 comparator = (Comparator) naturalOrder(); 301 } 302 assertTrue(Ordering.from(comparator).isOrdered(resultsForStrategy)); 303 } 304 if ((characteristics & Spliterator.SIZED) != 0) { 305 assertEquals(Ints.checkedCast(estimatedSize), resultsForStrategy.size()); 306 } 307 308 assertEqualIgnoringOrder(elements, resultsForStrategy); 309 resultsForAllStrategies.add(resultsForStrategy); 310 } 311 } 312 return new Ordered() { 313 @Override 314 public void inOrder() { 315 for (List<E> resultsForStrategy : resultsForAllStrategies) { 316 assertEqualInOrder(elements, resultsForStrategy); 317 } 318 } 319 }; 320 } 321}