1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
|
/*-------------------------------------------------------------------------*\
** ScalaCheck **
** Copyright (c) 2007-2013 Rickard Nilsson. All rights reserved. **
** http://www.scalacheck.org **
** **
** This software is released under the terms of the Revised BSD License. **
** There is NO WARRANTY. See the file LICENSE for the full text. **
\*------------------------------------------------------------------------ */
package org.scalacheck
import util.Buildable
import scala.collection.{ JavaConversions => jcl }
sealed abstract class Shrink[T] {
def shrink(x: T): Stream[T]
}
object Shrink {
import Stream.{cons, empty}
import scala.collection._
import java.util.ArrayList
/** Interleaves to streams */
private def interleave[T](xs: Stream[T], ys: Stream[T]): Stream[T] =
if(xs.isEmpty) ys
else if(ys.isEmpty) xs
else Stream(xs.head, ys.head) append interleave(xs.tail, ys.tail)
/** Shrink instance factory */
def apply[T](s: T => Stream[T]): Shrink[T] = new Shrink[T] {
override def shrink(x: T) = s(x)
}
/** Shrink a value */
def shrink[T](x: T)(implicit s: Shrink[T]): Stream[T] = s.shrink(x)
/** Default shrink instance */
implicit def shrinkAny[T]: Shrink[T] = Shrink(x => empty)
/** Shrink instance of container */
implicit def shrinkContainer[C[_],T](implicit v: C[T] => Traversable[T], s: Shrink[T],
b: Buildable[T,C]
): Shrink[C[T]] = Shrink { xs: C[T] =>
def removeChunks(n: Int, xs: Stream[T]): Stream[Stream[T]] =
if(xs.isEmpty) empty
else if(xs.tail.isEmpty) cons(empty, empty)
else {
val n1 = n / 2
val n2 = n - n1
lazy val xs1 = xs.take(n1)
lazy val xs2 = xs.drop(n1)
lazy val xs3 =
for(ys1 <- removeChunks(n1,xs1) if !ys1.isEmpty) yield ys1 append xs2
lazy val xs4 =
for(ys2 <- removeChunks(n2,xs2) if !ys2.isEmpty) yield xs1 append ys2
cons(xs1, cons(xs2, interleave(xs3,xs4)))
}
def shrinkOne(zs: Stream[T]): Stream[Stream[T]] =
if(zs.isEmpty) empty
else {
val x = zs.head
val xs = zs.tail
(for(y <- shrink(x)) yield cons(y,xs)) append
(for(ys <- shrinkOne(xs)) yield cons(x,ys))
}
val ys = v(xs)
val zs = ys.toStream
removeChunks(ys.size,zs).append(shrinkOne(zs)).map(b.fromIterable)
}
/** Shrink instance of integer */
implicit lazy val shrinkInt: Shrink[Int] = Shrink { n =>
def halfs(n: Int): Stream[Int] =
if(n == 0) empty else cons(n, halfs(n/2))
if(n == 0) empty else {
val ns = halfs(n/2).map(n - _)
cons(0, interleave(ns, ns.map(-1 * _)))
}
}
/** Shrink instance of String */
implicit lazy val shrinkString: Shrink[String] = Shrink { s =>
shrinkContainer[List,Char].shrink(s.toList).map(_.mkString)
}
/** Shrink instance of Option */
implicit def shrinkOption[T](implicit s: Shrink[T]): Shrink[Option[T]] =
Shrink {
case None => empty
case Some(x) => cons(None, for(y <- shrink(x)) yield Some(y))
}
/** Shrink instance of 2-tuple */
implicit def shrinkTuple2[T1,T2](implicit
s1: Shrink[T1], s2: Shrink[T2]
): Shrink[(T1,T2)] =
Shrink { case (t1,t2) =>
(for(x1 <- shrink(t1)) yield (x1, t2)) append
(for(x2 <- shrink(t2)) yield (t1, x2))
}
/** Shrink instance of 3-tuple */
implicit def shrinkTuple3[T1,T2,T3](implicit
s1: Shrink[T1], s2: Shrink[T2], s3: Shrink[T3]
): Shrink[(T1,T2,T3)] =
Shrink { case (t1,t2,t3) =>
(for(x1 <- shrink(t1)) yield (x1, t2, t3)) append
(for(x2 <- shrink(t2)) yield (t1, x2, t3)) append
(for(x3 <- shrink(t3)) yield (t1, t2, x3))
}
/** Shrink instance of 4-tuple */
implicit def shrinkTuple4[T1,T2,T3,T4](implicit
s1: Shrink[T1], s2: Shrink[T2], s3: Shrink[T3], s4: Shrink[T4]
): Shrink[(T1,T2,T3,T4)] =
Shrink { case (t1,t2,t3,t4) =>
(for(x1 <- shrink(t1)) yield (x1, t2, t3, t4)) append
(for(x2 <- shrink(t2)) yield (t1, x2, t3, t4)) append
(for(x3 <- shrink(t3)) yield (t1, t2, x3, t4)) append
(for(x4 <- shrink(t4)) yield (t1, t2, t3, x4))
}
/** Shrink instance of 5-tuple */
implicit def shrinkTuple5[T1,T2,T3,T4,T5](implicit
s1: Shrink[T1], s2: Shrink[T2], s3: Shrink[T3], s4: Shrink[T4],
s5: Shrink[T5]
): Shrink[(T1,T2,T3,T4,T5)] =
Shrink { case (t1,t2,t3,t4,t5) =>
(for(x1 <- shrink(t1)) yield (x1, t2, t3, t4, t5)) append
(for(x2 <- shrink(t2)) yield (t1, x2, t3, t4, t5)) append
(for(x3 <- shrink(t3)) yield (t1, t2, x3, t4, t5)) append
(for(x4 <- shrink(t4)) yield (t1, t2, t3, x4, t5)) append
(for(x5 <- shrink(t5)) yield (t1, t2, t3, t4, x5))
}
/** Shrink instance of 6-tuple */
implicit def shrinkTuple6[T1,T2,T3,T4,T5,T6](implicit
s1: Shrink[T1], s2: Shrink[T2], s3: Shrink[T3], s4: Shrink[T4],
s5: Shrink[T5], s6: Shrink[T6]
): Shrink[(T1,T2,T3,T4,T5,T6)] =
Shrink { case (t1,t2,t3,t4,t5,t6) =>
(for(x1 <- shrink(t1)) yield (x1, t2, t3, t4, t5, t6)) append
(for(x2 <- shrink(t2)) yield (t1, x2, t3, t4, t5, t6)) append
(for(x3 <- shrink(t3)) yield (t1, t2, x3, t4, t5, t6)) append
(for(x4 <- shrink(t4)) yield (t1, t2, t3, x4, t5, t6)) append
(for(x5 <- shrink(t5)) yield (t1, t2, t3, t4, x5, t6)) append
(for(x6 <- shrink(t6)) yield (t1, t2, t3, t4, t5, x6))
}
/** Shrink instance of 7-tuple */
implicit def shrinkTuple7[T1,T2,T3,T4,T5,T6,T7](implicit
s1: Shrink[T1], s2: Shrink[T2], s3: Shrink[T3], s4: Shrink[T4],
s5: Shrink[T5], s6: Shrink[T6], s7: Shrink[T7]
): Shrink[(T1,T2,T3,T4,T5,T6,T7)] =
Shrink { case (t1,t2,t3,t4,t5,t6,t7) =>
(for(x1 <- shrink(t1)) yield (x1, t2, t3, t4, t5, t6, t7)) append
(for(x2 <- shrink(t2)) yield (t1, x2, t3, t4, t5, t6, t7)) append
(for(x3 <- shrink(t3)) yield (t1, t2, x3, t4, t5, t6, t7)) append
(for(x4 <- shrink(t4)) yield (t1, t2, t3, x4, t5, t6, t7)) append
(for(x5 <- shrink(t5)) yield (t1, t2, t3, t4, x5, t6, t7)) append
(for(x6 <- shrink(t6)) yield (t1, t2, t3, t4, t5, x6, t7)) append
(for(x7 <- shrink(t7)) yield (t1, t2, t3, t4, t5, t6, x7))
}
/** Shrink instance of 8-tuple */
implicit def shrinkTuple8[T1,T2,T3,T4,T5,T6,T7,T8](implicit
s1: Shrink[T1], s2: Shrink[T2], s3: Shrink[T3], s4: Shrink[T4],
s5: Shrink[T5], s6: Shrink[T6], s7: Shrink[T7], s8: Shrink[T8]
): Shrink[(T1,T2,T3,T4,T5,T6,T7,T8)] =
Shrink { case (t1,t2,t3,t4,t5,t6,t7,t8) =>
(for(x1 <- shrink(t1)) yield (x1, t2, t3, t4, t5, t6, t7, t8)) append
(for(x2 <- shrink(t2)) yield (t1, x2, t3, t4, t5, t6, t7, t8)) append
(for(x3 <- shrink(t3)) yield (t1, t2, x3, t4, t5, t6, t7, t8)) append
(for(x4 <- shrink(t4)) yield (t1, t2, t3, x4, t5, t6, t7, t8)) append
(for(x5 <- shrink(t5)) yield (t1, t2, t3, t4, x5, t6, t7, t8)) append
(for(x6 <- shrink(t6)) yield (t1, t2, t3, t4, t5, x6, t7, t8)) append
(for(x7 <- shrink(t7)) yield (t1, t2, t3, t4, t5, t6, x7, t8)) append
(for(x8 <- shrink(t8)) yield (t1, t2, t3, t4, t5, t6, t7, x8))
}
/** Shrink instance of 9-tuple */
implicit def shrinkTuple9[T1,T2,T3,T4,T5,T6,T7,T8,T9](implicit
s1: Shrink[T1], s2: Shrink[T2], s3: Shrink[T3], s4: Shrink[T4],
s5: Shrink[T5], s6: Shrink[T6], s7: Shrink[T7], s8: Shrink[T8],
s9: Shrink[T9]
): Shrink[(T1,T2,T3,T4,T5,T6,T7,T8,T9)] =
Shrink { case (t1,t2,t3,t4,t5,t6,t7,t8,t9) =>
(for(x1 <- shrink(t1)) yield (x1, t2, t3, t4, t5, t6, t7, t8, t9)) append
(for(x2 <- shrink(t2)) yield (t1, x2, t3, t4, t5, t6, t7, t8, t9)) append
(for(x3 <- shrink(t3)) yield (t1, t2, x3, t4, t5, t6, t7, t8, t9)) append
(for(x4 <- shrink(t4)) yield (t1, t2, t3, x4, t5, t6, t7, t8, t9)) append
(for(x5 <- shrink(t5)) yield (t1, t2, t3, t4, x5, t6, t7, t8, t9)) append
(for(x6 <- shrink(t6)) yield (t1, t2, t3, t4, t5, x6, t7, t8, t9)) append
(for(x7 <- shrink(t7)) yield (t1, t2, t3, t4, t5, t6, x7, t8, t9)) append
(for(x8 <- shrink(t8)) yield (t1, t2, t3, t4, t5, t6, t7, x8, t9)) append
(for(x9 <- shrink(t9)) yield (t1, t2, t3, t4, t5, t6, t7, t8, x9))
}
}
|
