Report index
StatProfilerHTML.jl report
Generated on Thu, 26 Mar 2020 19:09:01
File source code
Line Exclusive Inclusive Code
1 # This file is a part of Julia. License is MIT: https://julialang.org/license
2
3 # Document NTuple here where we have everything needed for the doc system
4 """
5 NTuple{N, T}
6
7 A compact way of representing the type for a tuple of length `N` where all elements are of type `T`.
8
9 # Examples
10 ```jldoctest
11 julia> isa((1, 2, 3, 4, 5, 6), NTuple{6, Int})
12 true
13 ```
14 """
15 NTuple
16
17 ## indexing ##
18
19 length(@nospecialize t::Tuple) = nfields(t)
20 firstindex(@nospecialize t::Tuple) = 1
21 lastindex(@nospecialize t::Tuple) = length(t)
22 size(@nospecialize(t::Tuple), d::Integer) = (d == 1) ? length(t) : throw(ArgumentError("invalid tuple dimension $d"))
23 axes(@nospecialize t::Tuple) = (OneTo(length(t)),)
24 @eval getindex(@nospecialize(t::Tuple), i::Int) = getfield(t, i, $(Expr(:boundscheck)))
25 @eval getindex(@nospecialize(t::Tuple), i::Real) = getfield(t, convert(Int, i), $(Expr(:boundscheck)))
26 getindex(t::Tuple, r::AbstractArray{<:Any,1}) = ([t[ri] for ri in r]...,)
27 getindex(t::Tuple, b::AbstractArray{Bool,1}) = length(b) == length(t) ? getindex(t, findall(b)) : throw(BoundsError(t, b))
28 getindex(t::Tuple, c::Colon) = t
29
30 # returns new tuple; N.B.: becomes no-op if i is out-of-bounds
31
32 """
33 setindex(c::Tuple, v, i::Integer)
34
35 Creates a new tuple similar to `x` with the value at index `i` set to `v`.
36 Throws a `BoundsError` when out of bounds.
37
38 # Examples
39 ```jldoctest
40 julia> Base.setindex((1, 2, 6), 2, 3) == (1, 2, 2)
41 true
42 ```
43 """
44 function setindex(x::Tuple, v, i::Integer)
45 @boundscheck 1 <= i <= length(x) || throw(BoundsError(x, i))
46 @_inline_meta
47 _setindex(v, i, x...)
48 end
49
50 function _setindex(v, i::Integer, first, tail...)
51 @_inline_meta
52 return (ifelse(i == 1, v, first), _setindex(v, i - 1, tail...)...)
53 end
54 _setindex(v, i::Integer) = ()
55
56
57 ## iterating ##
58
59 function iterate(@nospecialize(t::Tuple), i::Int=1)
60 @_inline_meta
61 return (1 <= i <= length(t)) ? (@inbounds t[i], i + 1) : nothing
62 end
63
64 keys(@nospecialize t::Tuple) = OneTo(length(t))
65
66 prevind(@nospecialize(t::Tuple), i::Integer) = Int(i)-1
67 nextind(@nospecialize(t::Tuple), i::Integer) = Int(i)+1
68
69 function keys(t::Tuple, t2::Tuple...)
70 @_inline_meta
71 OneTo(_maxlength(t, t2...))
72 end
73 _maxlength(t::Tuple) = length(t)
74 function _maxlength(t::Tuple, t2::Tuple, t3::Tuple...)
75 @_inline_meta
76 max(length(t), _maxlength(t2, t3...))
77 end
78
79 # this allows partial evaluation of bounded sequences of next() calls on tuples,
80 # while reducing to plain next() for arbitrary iterables.
81 indexed_iterate(t::Tuple, i::Int, state=1) = (@_inline_meta; (getfield(t, i), i+1))
82 indexed_iterate(a::Array, i::Int, state=1) = (@_inline_meta; (a[i], i+1))
83 function indexed_iterate(I, i)
84 x = iterate(I)
85 x === nothing && throw(BoundsError(I, i))
86 x
87 end
88 function indexed_iterate(I, i, state)
89 x = iterate(I, state)
90 x === nothing && throw(BoundsError(I, i))
91 x
92 end
93
94 # Use dispatch to avoid a branch in first
95 first(::Tuple{}) = throw(ArgumentError("tuple must be non-empty"))
96 first(t::Tuple) = t[1]
97
98 # eltype
99
100 eltype(::Type{Tuple{}}) = Bottom
101 function eltype(t::Type{<:Tuple{Vararg{E}}}) where {E}
102 if @isdefined(E)
103 return E
104 else
105 # TODO: need to guard against E being miscomputed by subtyping (ref #23017)
106 # and compute the result manually in this case
107 return _compute_eltype(t)
108 end
109 end
110 eltype(t::Type{<:Tuple}) = _compute_eltype(t)
111 function _compute_eltype(t::Type{<:Tuple})
112 @_pure_meta
113 t isa Union && return promote_typejoin(eltype(t.a), eltype(t.b))
114 t´ = unwrap_unionall(t)
115 r = Union{}
116 for ti in t´.parameters
117 r = promote_typejoin(r, rewrap_unionall(unwrapva(ti), t))
118 end
119 return r
120 end
121
122 # version of tail that doesn't throw on empty tuples (used in array indexing)
123 safe_tail(t::Tuple) = tail(t)
124 safe_tail(t::Tuple{}) = ()
125
126 # front (the converse of tail: it skips the last entry)
127
128 """
129 front(x::Tuple)::Tuple
130
131 Return a `Tuple` consisting of all but the last component of `x`.
132
133 # Examples
134 ```jldoctest
135 julia> Base.front((1,2,3))
136 (1, 2)
137
138 julia> Base.front(())
139 ERROR: ArgumentError: Cannot call front on an empty tuple.
140 ```
141 """
142 function front(t::Tuple)
143 @_inline_meta
144 _front(t...)
145 end
146 _front() = throw(ArgumentError("Cannot call front on an empty tuple."))
147 _front(v) = ()
148 function _front(v, t...)
149 @_inline_meta
150 (v, _front(t...)...)
151 end
152
153 ## mapping ##
154
155 # 1 argument function
156 map(f, t::Tuple{}) = ()
157 map(f, t::Tuple{Any,}) = (f(t[1]),)
158 map(f, t::Tuple{Any, Any}) = (f(t[1]), f(t[2]))
159 map(f, t::Tuple{Any, Any, Any}) = (f(t[1]), f(t[2]), f(t[3]))
160 map(f, t::Tuple) = (@_inline_meta; (f(t[1]), map(f,tail(t))...))
161 # stop inlining after some number of arguments to avoid code blowup
162 const Any16{N} = Tuple{Any,Any,Any,Any,Any,Any,Any,Any,
163 Any,Any,Any,Any,Any,Any,Any,Any,Vararg{Any,N}}
164 const All16{T,N} = Tuple{T,T,T,T,T,T,T,T,
165 T,T,T,T,T,T,T,T,Vararg{T,N}}
166 function map(f, t::Any16)
167 n = length(t)
168 A = Vector{Any}(undef, n)
169 for i=1:n
170 A[i] = f(t[i])
171 end
172 (A...,)
173 end
174 # 2 argument function
175 map(f, t::Tuple{}, s::Tuple{}) = ()
176 map(f, t::Tuple{Any,}, s::Tuple{Any,}) = (f(t[1],s[1]),)
177 map(f, t::Tuple{Any,Any}, s::Tuple{Any,Any}) = (f(t[1],s[1]), f(t[2],s[2]))
178 function map(f, t::Tuple, s::Tuple)
179 @_inline_meta
180 1 (0 %)
1 (0 %) samples spent in map
1 (100 %) (incl.) when called from mapexponents line 127
1 (100 %) samples spent calling +
(f(t[1],s[1]), map(f, tail(t), tail(s))...)
181 end
182 function map(f, t::Any16, s::Any16)
183 n = length(t)
184 A = Vector{Any}(undef, n)
185 for i = 1:n
186 A[i] = f(t[i], s[i])
187 end
188 (A...,)
189 end
190 # n argument function
191 heads(ts::Tuple...) = map(t -> t[1], ts)
192 tails(ts::Tuple...) = map(tail, ts)
193 map(f, ::Tuple{}...) = ()
194 function map(f, t1::Tuple, t2::Tuple, ts::Tuple...)
195 @_inline_meta
196 (f(heads(t1, t2, ts...)...), map(f, tails(t1, t2, ts...)...)...)
197 end
198 function map(f, t1::Any16, t2::Any16, ts::Any16...)
199 n = length(t1)
200 A = Vector{Any}(undef, n)
201 for i = 1:n
202 A[i] = f(t1[i], t2[i], map(t -> t[i], ts)...)
203 end
204 (A...,)
205 end
206
207 _foldl_impl(op, init, itr::Tuple) = afoldl(op, init, itr...)
208
209 # type-stable padding
210 fill_to_length(t::NTuple{N,Any}, val, ::Val{N}) where {N} = t
211 fill_to_length(t::Tuple{}, val, ::Val{1}) = (val,)
212 fill_to_length(t::Tuple{Any}, val, ::Val{2}) = (t..., val)
213 fill_to_length(t::Tuple{}, val, ::Val{2}) = (val, val)
214 #function fill_to_length(t::Tuple, val, ::Val{N}) where {N}
215 # @_inline_meta
216 # return (t..., ntuple(i -> val, N - length(t))...)
217 #end
218
219 # constructing from an iterator
220
221 # only define these in Base, to avoid overwriting the constructors
222 # NOTE: this means this constructor must be avoided in Core.Compiler!
223 if nameof(@__MODULE__) === :Base
224
225 (::Type{T})(x::Tuple) where {T<:Tuple} = convert(T, x) # still use `convert` for tuples
226
227 Tuple(x::Ref) = tuple(getindex(x)) # faster than iterator for one element
228 Tuple(x::Array{T,0}) where {T} = tuple(getindex(x))
229
230 (::Type{T})(itr) where {T<:Tuple} = _totuple(T, itr)
231
232 _totuple(::Type{Tuple{}}, itr, s...) = ()
233
234 function _totuple_err(@nospecialize T)
235 @_noinline_meta
236 throw(ArgumentError("too few elements for tuple type $T"))
237 end
238
239 function _totuple(T, itr, s...)
240 @_inline_meta
241 y = iterate(itr, s...)
242 y === nothing && _totuple_err(T)
243 (convert(tuple_type_head(T), y[1]), _totuple(tuple_type_tail(T), itr, y[2])...)
244 end
245
246 # use iterative algorithm for long tuples
247 function _totuple(T::Type{All16{E,N}}, itr) where {E,N}
248 len = N+16
249 elts = collect(E, Iterators.take(itr,len))
250 if length(elts) != len
251 _totuple_err(T)
252 end
253 (elts...,)
254 end
255
256 _totuple(::Type{Tuple{Vararg{E}}}, itr, s...) where {E} = (collect(E, Iterators.rest(itr,s...))...,)
257
258 _totuple(::Type{Tuple}, itr, s...) = (collect(Iterators.rest(itr,s...))...,)
259
260 end
261
262 ## filter ##
263
264 filter(f, xs::Tuple) = afoldl((ys, x) -> f(x) ? (ys..., x) : ys, (), xs...)
265
266 # use Array for long tuples
267 filter(f, t::Any16) = Tuple(filter(f, collect(t)))
268
269 ## comparison ##
270
271 isequal(t1::Tuple, t2::Tuple) = (length(t1) == length(t2)) && _isequal(t1, t2)
272 _isequal(t1::Tuple{}, t2::Tuple{}) = true
273 _isequal(t1::Tuple{Any}, t2::Tuple{Any}) = isequal(t1[1], t2[1])
274 _isequal(t1::Tuple, t2::Tuple) = isequal(t1[1], t2[1]) && _isequal(tail(t1), tail(t2))
275 function _isequal(t1::Any16, t2::Any16)
276 for i = 1:length(t1)
277 if !isequal(t1[i], t2[i])
278 return false
279 end
280 end
281 return true
282 end
283
284 57 (7 %)
57 (7 %) samples spent in ==
57 (100 %) (incl.) when called from == line 112
40 (70 %) samples spent calling _eq
11 (19 %) samples spent calling _eq
6 (11 %) samples spent calling _eq
==(t1::Tuple, t2::Tuple) = (length(t1) == length(t2)) && _eq(t1, t2)
285 _eq(t1::Tuple{}, t2::Tuple{}) = true
286 _eq_missing(t1::Tuple{}, t2::Tuple{}) = missing
287 function _eq(t1::Tuple, t2::Tuple)
288 40 (5 %)
40 (5 %) samples spent in _eq
40 (100 %) (incl.) when called from == line 284
40 (100 %) samples spent calling ==
eq = t1[1] == t2[1]
289 6 (1 %) 6 (1 %)
6 (1 %) samples spent in _eq
6 (100 %) (ex.), 6 (100 %) (incl.) when called from == line 284
if eq === false
290 return false
291 elseif ismissing(eq)
292 return _eq_missing(tail(t1), tail(t2))
293 else
294 return _eq(tail(t1), tail(t2))
295 end
296 end
297 function _eq_missing(t1::Tuple, t2::Tuple)
298 eq = t1[1] == t2[1]
299 if eq === false
300 return false
301 else
302 return _eq_missing(tail(t1), tail(t2))
303 end
304 end
305 function _eq(t1::Any16, t2::Any16)
306 anymissing = false
307 for i = 1:length(t1)
308 eq = (t1[i] == t2[i])
309 if ismissing(eq)
310 anymissing = true
311 elseif !eq
312 return false
313 end
314 end
315 return anymissing ? missing : true
316 end
317
318 const tuplehash_seed = UInt === UInt64 ? 0x77cfa1eef01bca90 : 0xf01bca90
319 hash(::Tuple{}, h::UInt) = h + tuplehash_seed
320 hash(t::Tuple, h::UInt) = hash(t[1], hash(tail(t), h))
321 function hash(t::Any16, h::UInt)
322 out = h + tuplehash_seed
323 for i = length(t):-1:1
324 out = hash(t[i], out)
325 end
326 return out
327 end
328
329 <(::Tuple{}, ::Tuple{}) = false
330 <(::Tuple{}, ::Tuple) = true
331 <(::Tuple, ::Tuple{}) = false
332 function <(t1::Tuple, t2::Tuple)
333 a, b = t1[1], t2[1]
334 9 (1 %)
9 (1 %) samples spent in <
9 (100 %) (incl.) when called from isless line 21
9 (100 %) samples spent calling ==
eq = (a == b)
335 if ismissing(eq)
336 return missing
337 elseif !eq
338 1 (0 %)
1 (0 %) samples spent in <
1 (100 %) (incl.) when called from < line 340
1 (100 %) samples spent calling <
return a < b
339 end
340 2 (0 %)
2 (0 %) samples spent in <
1 (50 %) (incl.) when called from < line 340
1 (50 %) (incl.) when called from isless line 21
1 (50 %) samples spent calling <
1 (50 %) samples spent calling <
return tail(t1) < tail(t2)
341 end
342 function <(t1::Any16, t2::Any16)
343 n1, n2 = length(t1), length(t2)
344 for i = 1:min(n1, n2)
345 a, b = t1[i], t2[i]
346 eq = (a == b)
347 if ismissing(eq)
348 return missing
349 elseif !eq
350 return a < b
351 end
352 end
353 return n1 < n2
354 end
355
356 isless(::Tuple{}, ::Tuple{}) = false
357 isless(::Tuple{}, ::Tuple) = true
358 isless(::Tuple, ::Tuple{}) = false
359
360 """
361 isless(t1::Tuple, t2::Tuple)
362
363 Returns true when t1 is less than t2 in lexicographic order.
364 """
365 function isless(t1::Tuple, t2::Tuple)
366 a, b = t1[1], t2[1]
367 isless(a, b) || (isequal(a, b) && isless(tail(t1), tail(t2)))
368 end
369 function isless(t1::Any16, t2::Any16)
370 n1, n2 = length(t1), length(t2)
371 for i = 1:min(n1, n2)
372 a, b = t1[i], t2[i]
373 if !isequal(a, b)
374 return isless(a, b)
375 end
376 end
377 return n1 < n2
378 end
379
380 ## functions ##
381
382 isempty(x::Tuple{}) = true
383 isempty(@nospecialize x::Tuple) = false
384
385 revargs() = ()
386 revargs(x, r...) = (revargs(r...)..., x)
387
388 reverse(t::Tuple) = revargs(t...)
389
390 ## specialized reduction ##
391
392 # TODO: these definitions cannot yet be combined, since +(x...)
393 # where x might be any tuple matches too many methods.
394 # TODO: this is inconsistent with the regular sum in cases where the arguments
395 # require size promotion to system size.
396 137 (16 %)
137 (16 %) samples spent in sum
137 (100 %) (incl.) when called from degree line 67
137 (100 %) samples spent calling +
sum(x::Tuple{Any, Vararg{Any}}) = +(x...)
397
398 # NOTE: should remove, but often used on array sizes
399 # TODO: this is inconsistent with the regular prod in cases where the arguments
400 # require size promotion to system size.
401 prod(x::Tuple{}) = 1
402 prod(x::Tuple{Any, Vararg{Any}}) = *(x...)
403
404 all(x::Tuple{}) = true
405 all(x::Tuple{Bool}) = x[1]
406 all(x::Tuple{Bool, Bool}) = x[1]&x[2]
407 all(x::Tuple{Bool, Bool, Bool}) = x[1]&x[2]&x[3]
408 # use generic reductions for the rest
409
410 any(x::Tuple{}) = false
411 any(x::Tuple{Bool}) = x[1]
412 any(x::Tuple{Bool, Bool}) = x[1]|x[2]
413 any(x::Tuple{Bool, Bool, Bool}) = x[1]|x[2]|x[3]
414
415 # equivalent to any(f, t), to be used only in bootstrap
416 _tuple_any(f::Function, t::Tuple) = _tuple_any(f, false, t...)
417 function _tuple_any(f::Function, tf::Bool, a, b...)
418 @_inline_meta
419 _tuple_any(f, tf | f(a), b...)
420 end
421 _tuple_any(f::Function, tf::Bool) = tf
422
423 """
424 empty(x::Tuple)
425
426 Returns an empty tuple, `()`.
427 """
428 empty(@nospecialize x::Tuple) = ()