text:
"""
    AbstractPowerRepresentation

An abstract representation type of points and tangent vectors on a power manifold.
"""
abstract type AbstractPowerRepresentation end

"""
    ArrayPowerRepresentation

Representation of points and tangent vectors on a power manifold using multidimensional
arrays where first dimensions are equal to [`representation_size`](@ref) of the
wrapped manifold and the following ones are equal to the number of elements in each
direction.

[`Torus`](@ref) uses this representation.
"""
struct ArrayPowerRepresentation <: AbstractPowerRepresentation end

"""
    NestedPowerRepresentation

Representation of points and tangent vectors on a power manifold using arrays
of size equal to `TSize` of a [`PowerManifold`](@ref).
Each element of such array stores a single point or tangent vector.

[`GraphManifold`](@ref) uses this representation.
"""
struct NestedPowerRepresentation <: AbstractPowerRepresentation end

@doc raw"""
    AbstractPowerManifold{𝔽,M,TPR} <: Manifold{𝔽}

An abstract [`Manifold`](@ref) to represent manifolds that are build as powers
of another [`Manifold`](@ref) `M` with representation type `TPR`, a subtype of
[`AbstractPowerRepresentation`](@ref).
"""
abstract type AbstractPowerManifold{𝔽,M<:Manifold{𝔽},TPR<:AbstractPowerRepresentation} <:
              Manifold{𝔽} end

@doc raw"""
    PowerManifold{𝔽,TM<:Manifold,TSize<:Tuple,TPR<:AbstractPowerRepresentation} <: AbstractPowerManifold{𝔽,TM}

The power manifold $\mathcal M^{n_1× n_2 × … × n_d}$ with power geometry
 `TSize` statically defines the number of elements along each axis.

For example, a manifold-valued time series would be represented by a power manifold with
$d$ equal to 1 and $n_1$ equal to the number of samples. A manifold-valued image
(for example in diffusion tensor imaging) would be represented by a two-axis power
manifold ($d=2$) with $n_1$ and $n_2$ equal to width and height of the image.

While the size of the manifold is static, points on the power manifold
would not be represented by statically-sized arrays. Operations on small
power manifolds might be faster if they are represented as [`ProductManifold`](@ref).

# Constructor

    PowerManifold(M, N_1, N_2, ..., N_d)
    PowerManifold(M, NestedPowerRepresentation(), N_1, N_2, ..., N_d)
    M^(N_1, N_2, ..., N_d)

Generate the power manifold $M^{N_1 × N_2 × … × N_d}$.
By default, the [`ArrayPowerRepresentation`](@ref) of points
and tangent vectors is used, although a different one, for example
[`NestedPowerRepresentation`](@ref), can be given as the second argument to the
constructor.
When `M` is a `PowerManifold` (not any [`AbstractPowerManifold`](@ref)) itself, given
dimensions will be appended to the dimensions already present, for example
`PowerManifold(PowerManifold(Sphere(2), 2), 3)` is equivalent to
`PowerManifold(Sphere(2), 2, 3)`. This feature preserves the representation of the inner
power manifold (unless it's explicitly overridden).
If you specify `NestedPowerRepresentation()`, the sizes are not concatenated but you end up
with a nested power manifold within a power manifold.
"""
struct PowerManifold{𝔽,TM<:Manifold{𝔽},TSize,TPR<:AbstractPowerRepresentation} <:
       AbstractPowerManifold{𝔽,TM,TPR}
    manifold::TM
end

function PowerManifold(M::Manifold{𝔽}, size::Integer...) where {𝔽}
    return PowerManifold{𝔽,typeof(M),Tuple{size...},ArrayPowerRepresentation}(M)
end
function PowerManifold(
    M::Manifold{𝔽},
    ::TPR,
    size::Integer...,
) where {𝔽,TPR<:AbstractPowerRepresentation}
    return PowerManifold{𝔽,typeof(M),Tuple{size...},TPR}(M)
end
function PowerManifold(
    M::PowerManifold{𝔽,TM,TSize,TPR},
    size::Integer...,
) where {𝔽,TM<:Manifold{𝔽},TSize,TPR<:AbstractPowerRepresentation}
    return PowerManifold{𝔽,TM,Tuple{TSize.parameters...,size...},TPR}(M.manifold)
end
function PowerManifold(
    M::PowerManifold{𝔽,TM,TSize},
    ::TPR,
    size::Integer...,
) where {𝔽,TM<:Manifold{𝔽},TSize,TPR<:AbstractPowerRepresentation}
    return PowerManifold{𝔽,TM,Tuple{TSize.parameters...,size...},TPR}(M.manifold)
end
function PowerManifold(
    M::PowerManifold{𝔽,TM,TSize},
    ::NestedPowerRepresentation,
    size::Integer...,
) where {𝔽,TM<:Manifold{𝔽},TSize}
    return PowerManifold{
        𝔽,
        PowerManifold{𝔽,TM,TSize},
        Tuple{size...},
        NestedPowerRepresentation,
    }(
        M,
    )
end
@doc raw"""
    PowerMetric <: Metric

Represent the [`Metric`](@ref) on an [`AbstractPowerManifold`](@ref), i.e. the inner
product on the tangent space is the sum of the inner product of each elements
tangent space of the power manifold.
"""
struct PowerMetric <: Metric end

"""
    PowerRetraction(retraction::AbstractRetractionMethod)

Power retraction based on `retraction`. Works on [`AbstractPowerManifold`](@ref)s.
"""
struct PowerRetraction{TR<:AbstractRetractionMethod} <: AbstractRetractionMethod
    retraction::TR
end

"""
    InversePowerRetraction(inverse_retractions::AbstractInverseRetractionMethod...)

Power inverse retraction of `inverse_retractions`. Works on [`AbstractPowerManifold`](@ref)s.
"""
struct InversePowerRetraction{TR<:AbstractInverseRetractionMethod} <:
       AbstractInverseRetractionMethod
    inverse_retraction::TR
end

"""
    PowerPointDistribution(M::AbstractPowerManifold, distribution)

Power distribution on manifold `M`, based on `distribution`.
"""
struct PowerPointDistribution{TM<:AbstractPowerManifold,TD<:MPointDistribution,TX} <:
       MPointDistribution{TM}
    manifold::TM
    distribution::TD
    point::TX
end

"""
    PowerFVectorDistribution([type::VectorBundleFibers], [x], distr)

Generates a random vector at a `point` from vector space (a fiber of a tangent
bundle) of type `type` using the power distribution of `distr`.

Vector space type and `point` can be automatically inferred from distribution `distr`.
"""
struct PowerFVectorDistribution{
    TSpace<:VectorBundleFibers{<:VectorSpaceType,<:AbstractPowerManifold},
    TD<:FVectorDistribution,
    TX,
} <: FVectorDistribution{TSpace,TX}
    type::TSpace
    point::TX
    distribution::TD
end

"""
    PowerVectorTransport(method::AbstractVectorTransportMethod)

Power vector transport method based on `method`. Works on [`AbstractPowerManifold`](@ref)s.
"""
struct PowerVectorTransport{TR<:AbstractVectorTransportMethod} <:
       AbstractVectorTransportMethod
    method::TR
end

"""
    PowerBasisData{TB<:AbstractArray}

Data storage for an array of basis data.
"""
struct PowerBasisData{TB<:AbstractArray}
    bases::TB
end

const PowerManifoldMultidimensional =
    AbstractPowerManifold{𝔽,<:Manifold{𝔽},ArrayPowerRepresentation} where {𝔽}
const PowerManifoldNested =
    AbstractPowerManifold{𝔽,<:Manifold{𝔽},NestedPowerRepresentation} where {𝔽}

_access_nested(x, i::Int) = x[i]
_access_nested(x, i::Tuple) = x[i...]

function allocate_result(M::PowerManifoldNested, f, x...)
    return [
        allocate_result(M.manifold, f, map(y -> _access_nested(y, i), x)...)
        for i in get_iterator(M)
    ]
end
function allocate_result(M::PowerManifoldNested, f::typeof(flat), w::TFVector, x)
    alloc = [allocate(_access_nested(w.data, i)) for i in get_iterator(M)]
    return FVector(CotangentSpace, alloc)
end
function allocate_result(M::PowerManifoldNested, f::typeof(get_vector), p, X)
    return [allocate_result(M.manifold, f, _access_nested(p, i)) for i in get_iterator(M)]
end
function allocate_result(M::PowerManifoldNested, f::typeof(sharp), w::CoTFVector, x)
    alloc = [allocate(_access_nested(w.data, i)) for i in get_iterator(M)]
    return FVector(TangentSpace, alloc)
end
function allocate_result(
    M::PowerManifoldNested,
    f::typeof(get_coordinates),
    p,
    X,
    B::AbstractBasis,
)
    return invoke(
        allocate_result,
        Tuple{Manifold,typeof(get_coordinates),Any,Any,typeof(B)},
        M,
        f,
        p,
        X,
        B,
    )
end

function allocation_promotion_function(M::AbstractPowerManifold, f, args::Tuple)
    return allocation_promotion_function(M.manifold, f, args)
end

Base.:^(M::Manifold, n) = PowerManifold(M, n...)

"""
    check_manifold_point(M::AbstractProductManifold, p; kwargs...)

Check whether `p` is a valid point on an [`AbstractPowerManifold`](@ref) `M`,
i.e. each element of `p` has to be a valid point on the base manifold.
If `p` is not a point on `M` a `CompositeManifoldError` consisting of all error messages of the
components, for which the tests fail is returned.

The tolerance for the last test can be set using the `kwargs...`.
"""
function check_manifold_point(M::AbstractPowerManifold, p; kwargs...)
    rep_size = representation_size(M.manifold)
    e = [
        (i, check_manifold_point(M.manifold, _read(M, rep_size, p, i); kwargs...))
        for i in get_iterator(M)
    ]
    errors = filter((x) -> !(x[2] === nothing), e)
    cerr = [ComponentManifoldError(er...) for er in errors]
    (length(errors) > 1) && return CompositeManifoldError(cerr)
    (length(errors) == 1) && return cerr[1]
    return nothing
end

"""
    check_tangent_vector(M::AbstractPowerManifold, p, X; check_base_point = true, kwargs... )

Check whether `X` is a tangent vector to `p` an the [`AbstractPowerManifold`](@ref)
`M`, i.e. atfer [`check_manifold_point`](@ref)`(M, p)`, and all projections to
base manifolds must be respective tangent vectors.
The optional parameter `check_base_point` indicates, whether to call [`check_manifold_point`](@ref)  for `p`.
If `X` is not a tangent vector to `p` on `M` a `CompositeManifoldError` consisting of all error
messages of the components, for which the tests fail is returned.

The tolerance for the last test can be set using the `kwargs...`.
"""
function check_tangent_vector(
    M::AbstractPowerManifold,
    p,
    X;
    check_base_point = true,
    kwargs...,
)
    if check_base_point
        mpe = check_manifold_point(M, p)
        mpe === nothing || return mpe
    end
    rep_size = representation_size(M.manifold)
    e = [
        (
            i,
            check_tangent_vector(
                M.manifold,
                _read(M, rep_size, p, i),
                _read(M, rep_size, X, i);
                kwargs...,
            ),
        ) for i in get_iterator(M)
    ]
    errors = filter((x) -> !(x[2] === nothing), e)
    cerr = [ComponentManifoldError(er...) for er in errors]
    (length(errors) > 1) && return CompositeManifoldError(cerr)
    (length(errors) == 1) && return cerr[1]
    return nothing
end

function det_local_metric(
    M::MetricManifold{PowerMetric,𝔽,<:AbstractPowerManifold{𝔽}},
    p::AbstractArray,
) where {𝔽}
    result = one(number_eltype(p))
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        result *= det_local_metric(M.manifold, _read(M, rep_size, p, i))
    end
    return result
end

@doc raw"""
    distance(M::AbstractPowerManifold, p, q)

Compute the distance between `q` and `p` on an [`AbstractPowerManifold`](@ref),
i.e. from the element wise distances the Forbenius norm is computed.
"""
function distance(M::AbstractPowerManifold, p, q)
    sum_squares = zero(number_eltype(p))
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        sum_squares +=
            distance(M.manifold, _read(M, rep_size, p, i), _read(M, rep_size, q, i))^2
    end
    return sqrt(sum_squares)
end

@doc raw"""
    exp(M::AbstractPowerManifold, p, X)

Compute the exponential map from `p` in direction `X` on the [`AbstractPowerManifold`](@ref) `M`,
which can be computed using the base manifolds exponential map elementwise.
"""
exp(::AbstractPowerManifold, ::Any...)

function exp!(M::AbstractPowerManifold, q, p, X)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        exp!(
            M.manifold,
            _write(M, rep_size, q, i),
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
        )
    end
    return q
end

@doc raw"""
    flat(M::AbstractPowerManifold, p, X::FVector{TangentSpaceType})

use the musical isomorphism to transform the tangent vector `X` from the tangent space at
`p` on an [`AbstractPowerManifold`](@ref) `M` to a cotangent vector.
This can be done elementwise for each entry of `X` (and `p`).
"""
flat(::AbstractPowerManifold, ::Any...)

function flat!(M::AbstractPowerManifold, ξ::CoTFVector, p, X::TFVector)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        flat!(
            M.manifold,
            FVector(CotangentSpace, _write(M, rep_size, ξ.data, i)),
            _read(M, rep_size, p, i),
            FVector(TangentSpace, _read(M, rep_size, X.data, i)),
        )
    end
    return ξ
end

function get_basis(M::AbstractPowerManifold, p, B::AbstractBasis)
    rep_size = representation_size(M.manifold)
    vs = [get_basis(M.manifold, _read(M, rep_size, p, i), B) for i in get_iterator(M)]
    return CachedBasis(B, PowerBasisData(vs))
end
function get_basis(M::AbstractPowerManifold, p, B::DiagonalizingOrthonormalBasis)
    rep_size = representation_size(M.manifold)
    vs = [
        get_basis(
            M.manifold,
            _read(M, rep_size, p, i),
            DiagonalizingOrthonormalBasis(_read(M, rep_size, B.frame_direction, i)),
        ) for i in get_iterator(M)
    ]
    return CachedBasis(B, PowerBasisData(vs))
end
for BT in ManifoldsBase.DISAMBIGUATION_BASIS_TYPES
    if BT == DiagonalizingOrthonormalBasis
        continue
    end
    eval(quote
        @invoke_maker 3 AbstractBasis get_basis(M::AbstractPowerManifold, p, B::$BT)
    end)
end

"""
    get_component(M::AbstractPowerManifold, p, idx...)

Get the component of a point `p` on an [`AbstractPowerManifold`](@ref) `M` at index `idx`.
"""
function get_component(M::AbstractPowerManifold, p, idx...)
    rep_size = representation_size(M.manifold)
    return _read(M, rep_size, p, idx)
end

function get_coordinates(M::AbstractPowerManifold, p, X, B::DefaultOrthonormalBasis)
    rep_size = representation_size(M.manifold)
    vs = [
        get_coordinates(M.manifold, _read(M, rep_size, p, i), _read(M, rep_size, X, i), B) for i in get_iterator(M)
    ]
    return reduce(vcat, reshape(vs, length(vs)))
end
function get_coordinates(
    M::AbstractPowerManifold,
    p,
    X,
    B::CachedBasis{𝔽,<:AbstractBasis,<:PowerBasisData},
) where {𝔽}
    rep_size = representation_size(M.manifold)
    vs = [
        get_coordinates(
            M.manifold,
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
            _access_nested(B.data.bases, i),
        ) for i in get_iterator(M)
    ]
    return reduce(vcat, reshape(vs, length(vs)))
end

function get_coordinates!(M::AbstractPowerManifold, Y, p, X, B::DefaultOrthonormalBasis)
    rep_size = representation_size(M.manifold)
    dim = manifold_dimension(M.manifold)
    v_iter = 1
    for i in get_iterator(M)
        # TODO: this view is really suboptimal when `dim` can be statically determined
        get_coordinates!(
            M.manifold,
            view(Y, v_iter:(v_iter + dim - 1)),
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
            B,
        )
        v_iter += dim
    end
    return Y
end
function get_coordinates!(
    M::AbstractPowerManifold,
    Y,
    p,
    X,
    B::CachedBasis{𝔽,<:AbstractBasis,<:PowerBasisData},
) where {𝔽}
    rep_size = representation_size(M.manifold)
    dim = manifold_dimension(M.manifold)
    v_iter = 1
    for i in get_iterator(M)
        get_coordinates!(
            M.manifold,
            view(Y, v_iter:(v_iter + dim - 1)),
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
            _access_nested(B.data.bases, i),
        )
        v_iter += dim
    end
    return Y
end

get_iterator(M::PowerManifold{𝔽,<:Manifold{𝔽},Tuple{N}}) where {𝔽,N} = Base.OneTo(N)
@generated function get_iterator(
    M::PowerManifold{𝔽,<:Manifold{𝔽},SizeTuple},
) where {𝔽,SizeTuple}
    size_tuple = size_to_tuple(SizeTuple)
    return Base.product(map(Base.OneTo, size_tuple)...)
end

function get_vector!(
    M::PowerManifold,
    Y,
    p,
    X,
    B::CachedBasis{𝔽,<:AbstractBasis{𝔽},<:PowerBasisData},
) where {𝔽}
    dim = manifold_dimension(M.manifold)
    rep_size = representation_size(M.manifold)
    v_iter = 1
    for i in get_iterator(M)
        get_vector!(
            M.manifold,
            _write(M, rep_size, Y, i),
            _read(M, rep_size, p, i),
            X[v_iter:(v_iter + dim - 1)],
            _access_nested(B.data.bases, i),
        )
        v_iter += dim
    end
    return Y
end
function get_vector!(M::AbstractPowerManifold, Y, p, X, B::DefaultOrthonormalBasis)
    dim = manifold_dimension(M.manifold)
    rep_size = representation_size(M.manifold)
    v_iter = 1
    for i in get_iterator(M)
        get_vector!(
            M.manifold,
            _write(M, rep_size, Y, i),
            _read(M, rep_size, p, i),
            X[v_iter:(v_iter + dim - 1)],
            B,
        )
        v_iter += dim
    end
    return Y
end

"""
    getindex(p, M::AbstractPowerManifold, i::Union{Integer,Colon,AbstractVector}...)
    p[M::AbstractPowerManifold, i...]

Access the element(s) at index `[i...]` of a point `p` on an [`AbstractPowerManifold`](@ref)
`M` by linear or multidimensional indexing.
See also [Array Indexing](https://docs.julialang.org/en/v1/manual/arrays/#man-array-indexing-1) in Julia.
"""
Base.@propagate_inbounds function Base.getindex(
    p::AbstractArray,
    M::AbstractPowerManifold,
    I::Union{Integer,Colon,AbstractVector}...,
)
    return get_component(M, p, I...)
end
Base.@propagate_inbounds function Base.getindex(
    p::AbstractArray,
    M::AbstractPowerManifold,
    I::Integer...,
)
    return collect(get_component(M, p, I...))
end

@doc raw"""
    injectivity_radius(M::AbstractPowerManifold[, p])

the injectivity radius on an [`AbstractPowerManifold`](@ref) is for the global case
equal to the one of its base manifold. For a given point `p` it's equal to the
minimum of all radii in the array entries.
"""
function injectivity_radius(M::AbstractPowerManifold, p)
    radius = 0.0
    initialized = false
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        cur_rad = injectivity_radius(M.manifold, _read(M, rep_size, p, i))
        if initialized
            radius = min(cur_rad, radius)
        else
            radius = cur_rad
            initialized = true
        end
    end
    return radius
end
injectivity_radius(M::AbstractPowerManifold) = injectivity_radius(M.manifold)
eval(
    quote
        @invoke_maker 1 Manifold injectivity_radius(
            M::AbstractPowerManifold,
            rm::AbstractRetractionMethod,
        )
    end,
)
eval(
    quote
        @invoke_maker 1 Manifold injectivity_radius(
            M::AbstractPowerManifold,
            rm::ExponentialRetraction,
        )
    end,
)

@doc raw"""
    inverse_retract(M::AbstractPowerManifold, p, q, m::InversePowerRetraction)

Compute the inverse retraction from `p` with respect to `q` on an [`AbstractPowerManifold`](@ref) `M`
using an [`InversePowerRetraction`](@ref), which by default encapsulates a inverse retraction
of the base manifold. Then this method is performed elementwise, so the encapsulated inverse
retraction method has to be one that is available on the base [`Manifold`](@ref).
"""
inverse_retract(::AbstractPowerManifold, ::Any...)

function inverse_retract!(M::AbstractPowerManifold, X, p, q, method::InversePowerRetraction)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        inverse_retract!(
            M.manifold,
            _write(M, rep_size, X, i),
            _read(M, rep_size, p, i),
            _read(M, rep_size, q, i),
            method.inverse_retraction,
        )
    end
    return X
end

@doc raw"""
    inner(M::AbstractPowerManifold, p, X, Y)

Compute the inner product of `X` and `Y` from the tangent space at `p` on an
[`AbstractPowerManifold`](@ref) `M`, i.e. for each arrays entry the tangent
vector entries from `X` and `Y` are in the tangent space of the corresponding
element from `p`.
The inner product is then the sum of the elementwise inner products.
"""
function inner(M::AbstractPowerManifold, p, X, Y)
    result = zero(number_eltype(X))
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        result += inner(
            M.manifold,
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
            _read(M, rep_size, Y, i),
        )
    end
    return result
end

default_metric_dispatch(::AbstractPowerManifold, ::PowerMetric) = Val(true)

function Base.isapprox(M::AbstractPowerManifold, p, q; kwargs...)
    result = true
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        result &= isapprox(
            M.manifold,
            _read(M, rep_size, p, i),
            _read(M, rep_size, q, i);
            kwargs...,
        )
    end
    return result
end
function Base.isapprox(M::AbstractPowerManifold, p, X, Y; kwargs...)
    result = true
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        result &= isapprox(
            M.manifold,
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
            _read(M, rep_size, Y, i);
            kwargs...,
        )
    end
    return result
end

@doc raw"""
    log(M::AbstractPowerManifold, p, q)

Compute the logarithmic map from `p` to `q` on the [`AbstractPowerManifold`](@ref) `M`,
which can be computed using the base manifolds logarithmic map elementwise.
"""
log(::AbstractPowerManifold, ::Any...)

function log!(M::AbstractPowerManifold, X, p, q)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        log!(
            M.manifold,
            _write(M, rep_size, X, i),
            _read(M, rep_size, p, i),
            _read(M, rep_size, q, i),
        )
    end
    return X
end

@doc raw"""
    manifold_dimension(M::PowerManifold)

Returns the manifold-dimension of an [`PowerManifold`](@ref) `M`
$=\mathcal N = (\mathcal M)^{n_1,…,n_d}$, i.e. with $n=(n_1,…,n_d)$ the array
size of the power manifold and $d_{\mathcal M}$ the dimension of the base manifold
$\mathcal M$, the manifold is of dimension

````math
\dim(\mathcal N) = \dim(\mathcal M)\prod_{i=1}^d n_i = n_1n_2\cdot…\cdot n_d \dim(\mathcal M).
````
"""
function manifold_dimension(M::PowerManifold{𝔽,<:Manifold,TSize}) where {𝔽,TSize}
    return manifold_dimension(M.manifold) * prod(size_to_tuple(TSize))
end

function mid_point!(M::AbstractPowerManifold, q, p1, p2)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        mid_point!(
            M.manifold,
            _write(M, rep_size, q, i),
            _read(M, rep_size, p1, i),
            _read(M, rep_size, p2, i),
        )
    end
    return q
end

@doc raw"""
    norm(M::AbstractPowerManifold, p, X)

Compute the norm of `X` from the tangent space of `p` on an
[`AbstractPowerManifold`](@ref) `M`, i.e. from the element wise norms the
Frobenius norm is computed.
"""
function LinearAlgebra.norm(M::AbstractPowerManifold, p, X)
    sum_squares = zero(number_eltype(X))
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        sum_squares +=
            norm(M.manifold, _read(M, rep_size, p, i), _read(M, rep_size, X, i))^2
    end
    return sqrt(sum_squares)
end

@doc raw"""
    power_dimensions(M::PowerManifold)

return the power of `M`,
"""
function power_dimensions(M::PowerManifold{𝔽,<:Manifold,TSize}) where {𝔽,TSize}
    return size_to_tuple(TSize)
end

@doc raw"""
    project(M::AbstractPowerManifold, p)

Project the point `p` from the embedding onto the [`AbstractPowerManifold`](@ref) `M`
by projecting all components.
"""
project(::AbstractPowerManifold, ::Any)

function project!(M::AbstractPowerManifold, q, p)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        project!(M.manifold, _write(M, rep_size, q, i), _read(M, rep_size, p, i))
    end
    return q
end

@doc raw"""
    project(M::AbstractPowerManifold, p, X)

Project the point `X` onto the tangent space at `p` on the
[`AbstractPowerManifold`](@ref) `M` by projecting all components.
"""
project(::AbstractPowerManifold, ::Any, ::Any)

function project!(M::AbstractPowerManifold, Z, q, Y)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        project!(
            M.manifold,
            _write(M, rep_size, Z, i),
            _read(M, rep_size, q, i),
            _read(M, rep_size, Y, i),
        )
    end
    return Z
end

function Random.rand(rng::AbstractRNG, d::PowerFVectorDistribution)
    fv = zero_vector(d.type, d.point)
    Distributions._rand!(rng, d, fv)
    return fv
end
function Random.rand(rng::AbstractRNG, d::PowerPointDistribution)
    x = allocate_result(d.manifold, rand, d.point)
    Distributions._rand!(rng, d, x)
    return x
end

function Distributions._rand!(
    rng::AbstractRNG,
    d::PowerFVectorDistribution,
    v::AbstractArray,
)
    PM = d.type.manifold
    rep_size = representation_size(PM.manifold)
    for i in get_iterator(d.type.manifold)
        copyto!(d.distribution.point, _read(PM, rep_size, d.point, i))
        Distributions._rand!(rng, d.distribution, _read(PM, rep_size, v, i))
    end
    return v
end
function Distributions._rand!(rng::AbstractRNG, d::PowerPointDistribution, x::AbstractArray)
    M = d.manifold
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        Distributions._rand!(rng, d.distribution, _write(M, rep_size, x, i))
    end
    return x
end

Base.@propagate_inbounds @inline function _read(
    M::AbstractPowerManifold,
    rep_size::Tuple,
    x::AbstractArray,
    i::Int,
)
    return _read(M, rep_size, x, (i,))
end
Base.@propagate_inbounds @inline function _read(
    ::PowerManifoldMultidimensional,
    rep_size::Tuple,
    x::AbstractArray,
    i::Tuple,
)
    return view(x, rep_size_to_colons(rep_size)..., i...)
end
Base.@propagate_inbounds @inline function _read(
    ::PowerManifoldMultidimensional,
    rep_size::Tuple,
    x::HybridArray,
    i::Tuple,
)
    return x[rep_size_to_colons(rep_size)..., i...]
end
Base.@propagate_inbounds @inline function _read(
    ::PowerManifoldNested,
    rep_size::Tuple,
    x::AbstractArray,
    i::Tuple,
)
    return view(x[i...], rep_size_to_colons(rep_size)...)
end

@generated function rep_size_to_colons(rep_size::Tuple)
    N = length(rep_size.parameters)
    return ntuple(i -> Colon(), N)
end

function representation_size(M::PowerManifold{𝔽,<:Manifold,TSize}) where {𝔽,TSize}
    return (representation_size(M.manifold)..., size_to_tuple(TSize)...)
end

@doc raw"""
    retract(M::AbstractPowerManifold, p, X, method::PowerRetraction)

Compute the retraction from `p` with tangent vector `X` on an [`AbstractPowerManifold`](@ref) `M`
using a [`PowerRetraction`](@ref), which by default encapsulates a retraction of the
base manifold. Then this method is performed elementwise, so the encapsulated retraction
method has to be one that is available on the base [`Manifold`](@ref).
"""
retract(::AbstractPowerManifold, ::Any...)

function retract!(M::AbstractPowerManifold, q, p, X, method::PowerRetraction)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        retract!(
            M.manifold,
            _write(M, rep_size, q, i),
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
            method.retraction,
        )
    end
    return q
end

"""
    set_component!(M::AbstractPowerManifold, q, p, idx...)

Set the component of a point `q` on an [`AbstractPowerManifold`](@ref) `M` at index `idx`
to `p`, which itself is a point on the [`Manifold`](@ref) the power manifold is build on.
"""
function set_component!(M::AbstractPowerManifold, q, p, idx...)
    rep_size = representation_size(M.manifold)
    return copyto!(_write(M, rep_size, q, idx), p)
end
"""
    setindex!(q, p, M::AbstractPowerManifold, i::Union{Integer,Colon,AbstractVector}...)
    q[M::AbstractPowerManifold, i...] = p

Set the element(s) at index `[i...]` of a point `q` on an [`AbstractPowerManifold`](@ref)
`M` by linear or multidimensional indexing to `q`.
See also [Array Indexing](https://docs.julialang.org/en/v1/manual/arrays/#man-array-indexing-1) in Julia.
"""
Base.@propagate_inbounds function Base.setindex!(
    q::AbstractArray,
    p,
    M::AbstractPowerManifold,
    I::Union{Integer,Colon,AbstractVector}...,
)
    return set_component!(M, q, p, I...)
end

@doc raw"""
    sharp(M::AbstractPowerManifold, p, ξ::FVector{CotangentSpaceType})

Use the musical isomorphism to transform the cotangent vector `ξ` from the tangent space at
`p` on an [`AbstractPowerManifold`](@ref) `M` to a tangent vector.
This can be done elementwise for every entry of `ξ` (and `p`).
"""
sharp(::AbstractPowerManifold, ::Any...)

function sharp!(M::AbstractPowerManifold, X::TFVector, p, ξ::CoTFVector)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        sharp!(
            M.manifold,
            FVector(TangentSpace, _write(M, rep_size, X.data, i)),
            _read(M, rep_size, p, i),
            FVector(CotangentSpace, _read(M, rep_size, ξ.data, i)),
        )
    end
    return X
end

function Base.show(
    io::IO,
    mime::MIME"text/plain",
    B::CachedBasis{𝔽,T,D},
) where {T<:AbstractBasis,D<:PowerBasisData,𝔽}
    println(io, "$(T()) for a power manifold")
    for i in Base.product(map(Base.OneTo, size(B.data.bases))...)
        println(io, "Basis for component $i:")
        show(io, mime, _access_nested(B.data.bases, i))
        println(io)
    end
    return nothing
end
function Base.show(
    io::IO,
    M::PowerManifold{𝔽,TM,TSize,ArrayPowerRepresentation},
) where {𝔽,TM,TSize}
    return print(io, "PowerManifold($(M.manifold), $(join(TSize.parameters, ", ")))")
end
function Base.show(io::IO, M::PowerManifold{𝔽,TM,TSize,TPR}) where {𝔽,TM,TSize,TPR}
    return print(
        io,
        "PowerManifold($(M.manifold), $(TPR()), $(join(TSize.parameters, ", ")))",
    )
end

Distributions.support(tvd::PowerFVectorDistribution) = FVectorSupport(tvd.type, tvd.point)
Distributions.support(d::PowerPointDistribution) = MPointSupport(d.manifold)

function vector_bundle_transport(fiber::VectorSpaceType, M::PowerManifold)
    return PowerVectorTransport(ParallelTransport())
end

function vector_transport_direction(M::AbstractPowerManifold, p, X, d)
    return vector_transport_direction(M, p, X, d, PowerVectorTransport(ParallelTransport()))
end

function vector_transport_direction!(M::AbstractPowerManifold, Y, p, X, d)
    return vector_transport_direction!(
        M,
        Y,
        p,
        X,
        d,
        PowerVectorTransport(ParallelTransport()),
    )
end

@doc raw"""
    vector_transport_to(M::AbstractPowerManifold, p, X, q, method::PowerVectorTransport)

Compute the vector transport the tangent vector `X`at `p` to `q` on the
[`PowerManifold`](@ref) `M` using an [`PowerVectorTransport`](@ref) `m`.
This method is performed elementwise, i.e. the method `m` has to be implemented on the
base manifold.
"""
vector_transport_to(::AbstractPowerManifold, ::Any, ::Any, ::Any, ::PowerVectorTransport)
function vector_transport_to(M::AbstractPowerManifold, p, X, q)
    return vector_transport_to(M, p, X, q, PowerVectorTransport(ParallelTransport()))
end

function vector_transport_to!(M::AbstractPowerManifold, Y, p, X, q)
    return vector_transport_to!(M, Y, p, X, q, PowerVectorTransport(ParallelTransport()))
end
function vector_transport_to!(M::AbstractPowerManifold, Y, p, X, q, m::PowerVectorTransport)
    rep_size = representation_size(M.manifold)
    for i in get_iterator(M)
        vector_transport_to!(
            M.manifold,
            _write(M, rep_size, Y, i),
            _read(M, rep_size, p, i),
            _read(M, rep_size, X, i),
            _read(M, rep_size, q, i),
            m.method,
        )
    end
    return Y
end

"""
    view(p, M::AbstractPowerManifold, i::Union{Integer,Colon,AbstractVector}...)

Get the view of the element(s) at index `[i...]` of a point `p` on an
[`AbstractPowerManifold`](@ref) `M` by linear or multidimensional indexing.
"""
function Base.view(
    p::AbstractArray,
    M::AbstractPowerManifold,
    I::Union{Integer,Colon,AbstractVector}...,
)
    rep_size = representation_size(M.manifold)
    return _write(M, rep_size, p, I...)
end

@inline function _write(M::AbstractPowerManifold, rep_size::Tuple, x::AbstractArray, i::Int)
    return _write(M, rep_size, x, (i,))
end
@inline function _write(
    M::PowerManifoldMultidimensional,
    rep_size::Tuple,
    x::AbstractArray,
    i::Tuple,
)
    return view(x, rep_size_to_colons(rep_size)..., i...)
end
@inline function _write(M::PowerManifoldNested, rep_size::Tuple, x::AbstractArray, i::Tuple)
    return view(x[i...], rep_size_to_colons(rep_size)...)
end


text:
using StructuralCausalModels

# fig2.6.dag <- dagitty("dag { {X V} -> U; S1 <- U; {Y V} -> W; W -> S2}")
dag_1 = "dag { U <- {X V}; S1 <- U; {Y V} -> W; S2 <- W}";
dag_2 = "dag { S1 <- U <- {X V}; {Y V} -> W -> S2}";
dag_3 = "dag { S1 <- U; U <- X; U <- V; Y -> W; V -> W -> S2}";

d1 = from_dagitty(dag_1);
d2 = from_dagitty(dag_2);
d3 = from_dagitty(dag_3);
g1 = to_dagitty(d1);
g2 = to_dagitty(d2);
g3 = to_dagitty(d3)

d4 =OrderedDict(
  [:u, :w] => :v,
  [:u] => :x,
  :s1 => [:u],
  :w => :y,
  [:s2] => [:w]
)
g4 = to_dagitty(d4)

dag = DAG("dag_1", dag_1)

@testset "dagitty conversions" begin

  @test d1 == OrderedDict(
    :S2 => :W,
    :W  => [:Y, :V],
    :S1 => :U,
    :U  => [:X, :V]
  )
  @test d2 == OrderedDict(
    :S2 => :W,
    :W  => [:Y, :V],
    :U  => [:X, :V],
    :S1 => :U
  )
  @test d3 == OrderedDict(
    :S2 => :W,
    :W  => [:V, :Y],
    :U  => [:V, :X],
    :S1 => :U
  )
  @test g1 == "dag { S2 <- W; W <- { Y V }; S1 <- U; U <- { X V } }"
  @test g2 == "dag { S2 <- W; W <- { Y V }; U <- { X V }; S1 <- U }"
  @test g3 == "dag { S2 <- W; W <- { V Y }; U <- { V X }; S1 <- U }"
  @test g4 == "dag { u <- v; w <- v; u <- x; s1 <- u; w <- y; s2 <- w }"
  @test dag.d == OrderedDict(
    :S2 => :W,
    :W  => [:Y, :V],
    :S1 => :U,
    :U  => [:X, :V]
  )

end

ext: jl


text:
# ### m10.yyt.jl

using Pkg, DrWatson

@quickactivate "StatisticalRethinkingTuring"
using Turing
using StatisticalRethinking
Turing.setprogress!(false)

delim=';'
df = CSV.read(sr_datadir("UCBadmit.csv"), DataFrame; delim);

@model ppl10_yy(admit, reject) = begin
   α₁ ~ Normal(0,100)
   α₂ ~ Normal(0,100)

   for i ∈ 1:length(admit)
       λₐ = exp(α₁)
       λᵣ = exp(α₂)
       admit[i] ~ Poisson(λₐ)
       reject[i] ~ Poisson(λᵣ)
   end
end;

m10_yyt = ppl10_yy(df.admit, df.reject)
nchains = 4; sampler = NUTS(0.65); nsamples=2000
chns10_yyt = mapreduce(c -> sample(m10_yyt, sampler, nsamples), chainscat, 1:nchains)

# Rethinking/CmdStan result

m_10_yyt_result = "
    mean   sd 5.5% 94.5% n_eff Rhat
 a1 4.99 0.02 4.95  5.02  2201    1
 a2 5.44 0.02 5.41  5.47  2468    1
";

# End of 10/m10.yyt.jl


text:
"""
	grdsample(cmd0::String="", arg1=nothing, kwargs...)

Reads a grid file and interpolates it to create a new grid file with either: a
different registration; or a new grid-spacing or number of nodes, and perhaps
also a new sub-region

Full option list at [`grdsample`]($(GMTdoc)grdsample.html)

Parameters
----------

- **G** | **save** | **outgrid** | **outfile** :: [Type => Str]

    Output grid file name. Note that this is optional and to be used only when saving
    the result directly on disk. Otherwise, just use the G = grdsample(....) form.
    ($(GMTdoc)grdsample.html#g)
- $(GMT.opt_I)
    ($(GMTdoc)grdsample.html#i)
- $(GMT.opt_R)
- **T** | **toggle** :: [Type => Bool]

    Toggle the node registration for the output grid so as to become the opposite of the input grid
    ($(GMTdoc)grdsample.html#t)
- $(GMT.opt_V)
- $(GMT.opt_f)
- $(GMT.opt_n)
- $(GMT.opt_r)
- $(GMT.opt_x)
"""
function grdsample(cmd0::String="", arg1=nothing; kwargs...)

	length(kwargs) == 0 && return monolitic("grdsample", cmd0, arg1)

	d = init_module(false, kwargs...)[1]		# Also checks if the user wants ONLY the HELP mode
	cmd, = parse_common_opts(d, "", [:G :I :R :V_params :f :n :r :x])
	cmd  = parse_these_opts(cmd, d, [[:T :toggle]])

	common_grd(d, cmd0, cmd, "grdsample ", arg1)		# Finish build cmd and run it
end

# ---------------------------------------------------------------------------------------------------
grdsample(arg1, cmd0::String=""; kw...) = grdsample(cmd0, arg1; kw...)


text:
"""
    truncfloat(x::Real, ndigits=3)

truncate all but the last `ndigits` digits to the
right of the decimal point in `x`.
"""
function truncfloat(x::Real, ndigits=3)
    xf = float(x)
    fac = 10^ndigits
    round(Int,xf*fac)/fac
end

"""
    merge1!(d::AbstractDict, others::AbstractArray{AbstractDict})

The same as `merge!`, except that `others` is an array of `AbstractDict`s.
This is far more efficient when the length of `others` is large.
"""
function merge1!(d::AbstractDict, others::AbstractArray{T}) where T <: AbstractDict
    for other in others
        @inbounds for (k,v) in other
            d[k] = v
        end
    end
    return d
end

"""
    merge1(ds::AbstractArray)

Return a dictionary merging the `AbstractDict`s in `ds`.
`merge1` is like `merge`, but the dictionaries are passed
in an array, rather than separate parameters. This is much
more efficient for many dictionaries.
The output `AbstractDict` is of the same concrete type as
the first element of `ds`. All of the remaining dictionaries
must be compatible with this choice.
"""
function merge1(ds::AbstractArray{T}) where T <: AbstractDict
    t = eltype(ds)
    merge1!(t(),ds)
end

"""
    nonuniquecount(itr)

Return the number of nonunique values in `itr`.
This is no more efficient than `length(nonunique(itr))`.
"""
function nonuniquecount(a::AbstractArray{T}) where {T}
    d = Dict{T,Int}()
    nucount = 0
    @inbounds for x in a
        if haskey(d,x)
            d[x] += 1
            if d[x] == 2
                nucount += 1
            end
        else
            d[x] = 1
        end
    end
    nucount
end

"""
    nonunique(itr)

Return an array containing one value from `itr` for each nonunique value.
"""
function nonunique(a::AbstractArray{T}) where {T}
    seen = Dict{T,Int}()
    out = Vector{T}()
    for x in a
        if haskey(seen,x)
            seen[x] += 1
            seen[x] == 2 && push!(out,x)
        else
            seen[x] = 1
        end
    end
    return out
end
# Above is faster than below, for at least some tests
# function nonunique(a::AbstractArray{T}) where {T}
#     d = DataStructures.counter(T)
#     nu = Vector{T}()
#     @inbounds for x in a
#         push!(d,x)
#         d[x] == 2 && push!(nu,x)
#     end
#     nu
# end

"""
    sortcountmap(itr; byvalue=true, rev=true)

Return a `countmap`, a dictionary mapping each unique value in `itr` to its number of occurrences,
sorted by count in decreasing order.

If `byvalue=false`, sorting is done by key. I don't expect the sort interface to stay
stable for long, so this function may break in various ways.
"""
function sortcountmap(arr; byvalue=true,rev=true)
    if byvalue
        sort(countmap(arr), byvalue=true, rev=rev)
    else
        sort(countmap(arr), rev=rev)  # we must omit byvalue. byvalue=false fails to order by key.
    end
end

"""
    foreachdict(f,itr::AbstractDict)

Equivalent to `foreachdict(f,keys(itr),values(itr))`.

# Example

```jldoctest
julia> d = Dict(:a=>1, :b=>2);

julia> foreachdict((k,v) -> println(k,v), d)
a1
b2
```
"""
foreachdict(f,itr::AbstractDict) = foreach(f,keys(itr),values(itr))

"""
    function foreachdict(f,itrs...)

Equivalent to `foreach(f,itrs...)`, except that each element `itr` of
`itrs` that is a subtype of `AbstractDict` is replaced with `keys(itr), values(itr)`.
"""
function foreachdict(f,itrs...)
    a = Any[]
    for itr in itrs
        if isa(itr,AbstractDict)
            push!(a,keys(itr))
            push!(a,values(itr))
        else
            push!(a,itr)
        end
    end
    foreach(f,a...)
end

foreachdict(f) = foreach(f)

"""
    equalelements(a,b)

Return `true` if `a` and `b` are element-wise equal, using `==`.
For arrays, this is equivalent to `a == b`. But, for some iterators
a method for `==` is not defined.

`equalelements` should give the same result as `collect(a) == collect(b)`,
but perhaps do it more efficiently as it avoids allocation.
This funciton may be unnecessary in v0.7.
"""
function equalelements(a,b)
    for (x,y) in zip(a,b)
        x != y && return false
    end
    return true
end

"""
    allkeysequal(a::AbstractArray)::Bool

Return `true` only if all elements of `a` have keys and the set of keys of the first element of `a` is identical
to the set of keys of each of the other elements.
"""
#function check_key_consistency(a::AbstractArray{AbstractDict}) #  AbstractArray{Any} also works here
function allkeysequal(a::AbstractArray)
    length(a) == 0 && return false
    len = length(a[1])
    all(x -> length(x) == len, a) || return false
    ks = keys(a[1])
    for (i,obj) in enumerate(a)
        equalelements(keys(obj),  ks)  || return false
    end
    return true
end

"""
    countmaptypes(arr::Array)

Return a count map of the types of elements in `arr`
"""
function countmaptypes(arr::Array)
    typelist = [typeof(x) for x in arr]
    StatsBase.countmap(typelist)
end

"""
    countmaptypes(arr::Array{T}) where T <: AbstractDict

Return a count map of the value types for each key in elements of `arr`.

`arr` is an array of objects of type `AbstractDict` with identical keys.
"""
function countmaptypes(arr::Array{T}) where T <: AbstractDict
    type_counts = DataStructures.OrderedDict{String,Dict}()
    length(arr) < 1 && return type_counts
    keylist = collect(keys(arr[1]))
    for k in keylist
        typelist = [typeof(arr[i][k]) for i in 1:length(arr)]   # Allocation :(
        type_counts[k] = StatsBase.countmap(typelist)
    end
    return type_counts
end

"""
    countmapvalues(arr::AbstractArray, keyname::AbstractString)

Return a `Dict` of the values found for `keyname` and the number of times each appears.
"""
function countmapvalues(arr::AbstractArray, keyname::AbstractString)
    (length(arr) > 0 && haskey(arr[1], keyname)) || error("No key '$keyname'")
    return StatsBase.countmap([arr[i][keyname] for i in 1:length(arr)])
end

"""
    countmapnumvalues(arr::AbstractArray)

Assume `arr` is an array of `AbstractDict` objects with identical keys. Return
a countmap of the number of distinct values associated with each key.
"""
countmapnumvalues(arr::AbstractArray) = countmapnumvalues(arr, typeof(arr[1]))

countmapnumvalues(arr::AbstractArray, dicttype) = dicttype( k => length(countmapvalues(arr, k)) for k in keys(arr[1]))

"""
    countmaptypenumvalues(arr::AbstractArray)

Return a `AbstractDict` object whos values for each key are a tuple of
the corresponding values returned by `countmaptypes` and `countmapnumvalues`.
"""
function countmaptypenumvalues(arr::AbstractArray)
    cn = countmapnumvalues(arr)
    ct = countmaptypes(arr)
    dicttype = typeof(arr[1])
    dicttype( k => (ct[k], cn[k]) for k in keys(arr[1]))
end

"""
    isapprox(l::AbstractDict, r::AbstractDict)

Return true if `l` and `r` have approximately the same
keys and values.
"""
function Base.isapprox(l::AbstractDict, r::AbstractDict)
    l === r && return true
    if isa(l,ObjectIdDict) != isa(r,ObjectIdDict)
        return false
    end
    if length(l) != length(r) return false end
    for pair in l
        if !in(pair, r, isapprox)
            return false
        end
    end
    true
end

"""
    rgbtohex(r::Integer, g::Integer, b::Integer)

convert rgb color to hex format.
"""
rgbtohex(r::Integer, g::Integer, b::Integer) =  "#" * string(string.((r,g,b), base=16, pad=2)...)


text:
# compiler driver and main interface

# (::CompilerJob)
const compile_hook = Ref{Union{Nothing,Function}}(nothing)

"""
    compile(target::Symbol, cap::VersionNumber, f, tt, kernel=true;
            optimize=true, strip=false, ...)

Compile a function `f` invoked with types `tt` for device capability `cap` to one of the
following formats as specified by the `target` argument: `:julia` for Julia IR, `:llvm` for
LLVM IR, `:ptx` for PTX assembly and `:cuda` for CUDA driver objects. If the `kernel` flag
is set, specialized code generation and optimization for kernel functions is enabled.

The following keyword arguments are supported:
- `optimize`: optimize the code (default: true)
- `strip`: strip non-functional metadata and debug information  (default: false)

Other keyword arguments can be found in the documentation of [`cufunction`](@ref).
"""
compile(target::Symbol, cap::VersionNumber, @nospecialize(f::Core.Function), @nospecialize(tt),
        kernel::Bool=true; optimize::Bool=true, strip::Bool=false, kwargs...) =
    compile(target, CompilerJob(f, tt, cap, kernel; kwargs...); optimize=optimize, strip=strip)

function compile(target::Symbol, job::CompilerJob;
                 libraries::Bool=true, optimize::Bool=true, strip::Bool=false)
    @debug "(Re)compiling function" job

    if compile_hook[] != nothing
        global globalUnique
        previous_globalUnique = globalUnique

        compile_hook[](job)

        globalUnique = previous_globalUnique
    end

    return codegen(target, job; libraries=libraries, optimize=optimize, strip=strip)
end

function codegen(target::Symbol, job::CompilerJob; libraries::Bool=true,
                 optimize::Bool=true, strip::Bool=false)
    ## Julia IR

    @timeit to[] "Julia front-end" begin
        check_method(job)

        # get the method instance
        world = typemax(UInt)
        meth = which(job.f, job.tt)
        sig = Base.signature_type(job.f, job.tt)::Type
        (ti, env) = ccall(:jl_type_intersection_with_env, Any,
                          (Any, Any), sig, meth.sig)::Core.SimpleVector
        if VERSION >= v"1.2.0-DEV.320"
            meth = Base.func_for_method_checked(meth, ti, env)
        else
            meth = Base.func_for_method_checked(meth, ti)
        end
        linfo = ccall(:jl_specializations_get_linfo, Ref{Core.MethodInstance},
                      (Any, Any, Any, UInt), meth, ti, env, world)
    end

    target == :julia && return linfo

    ## LLVM IR

    # preload libraries
    if libraries
        libdevice = load_libdevice(job.cap)
        runtime = load_runtime(job.cap)
    end

    need_library(lib) = any(f -> isdeclaration(f) &&
                                 intrinsic_id(f) == 0 &&
                                 haskey(functions(lib), LLVM.name(f)),
                            functions(ir))

    @timeit to[] "LLVM middle-end" begin
        ir, kernel = @timeit to[] "IR generation" irgen(job, linfo, world)

        if libraries
            @timeit to[] "device library" if need_library(libdevice)
                link_libdevice!(job, ir, libdevice)
            end
        end

        if optimize
            kernel = @timeit to[] "optimization" optimize!(job, ir, kernel)
        end

        if libraries
            @timeit to[] "runtime library" if need_library(runtime)
                link_library!(job, ir, runtime)
            end
        end

        @timeit to[] "verification" verify(ir)

        if strip
            @timeit to[] "strip debug info" strip_debuginfo!(ir)
        end

        kernel_fn = LLVM.name(kernel)
        kernel_ft = eltype(llvmtype(kernel))
    end

    target == :llvm && return ir, kernel

    ## dynamic parallelism

    kernels = OrderedDict{CompilerJob, String}(job => kernel_fn)

    if haskey(functions(ir), "cudanativeCompileKernel")
        dyn_maker = functions(ir)["cudanativeCompileKernel"]

        # iterative compilation (non-recursive)
        changed = true
        while changed
            changed = false

            # find dynamic kernel invocations
            # TODO: recover this information earlier, from the Julia IR
            worklist = MultiDict{CompilerJob, LLVM.CallInst}()
            for use in uses(dyn_maker)
                # decode the call
                call = user(use)::LLVM.CallInst
                id = convert(Int, first(operands(call)))

                global delayed_cufunctions
                dyn_f, dyn_tt = delayed_cufunctions[id]
                dyn_job = CompilerJob(dyn_f, dyn_tt, job.cap, #=kernel=# true)
                push!(worklist, dyn_job => call)
            end

            # compile and link
            for dyn_job in keys(worklist)
                # cached compilation
                dyn_kernel_fn = get!(kernels, dyn_job) do
                    dyn_ir, dyn_kernel = codegen(:llvm, dyn_job; optimize=optimize, strip=strip)
                    dyn_kernel_fn = LLVM.name(dyn_kernel)
                    dyn_kernel_ft = eltype(llvmtype(dyn_kernel))
                    link!(ir, dyn_ir)
                    changed = true
                    dyn_kernel_fn
                end
                dyn_kernel = functions(ir)[dyn_kernel_fn]

                # insert a pointer to the function everywhere the kernel is used
                T_ptr = convert(LLVMType, Ptr{Cvoid})
                for call in worklist[dyn_job]
                    Builder(JuliaContext()) do builder
                        position!(builder, call)
                        fptr = ptrtoint!(builder, dyn_kernel, T_ptr)
                        replace_uses!(call, fptr)
                    end
                    unsafe_delete!(LLVM.parent(call), call)
                end
            end
        end

        # all dynamic launches should have been resolved
        @compiler_assert isempty(uses(dyn_maker)) job
        unsafe_delete!(ir, dyn_maker)
    end

    ## PTX machine code

    @timeit to[] "LLVM back-end" begin
        @timeit to[] "preparation" prepare_execution!(job, ir)

        check_invocation(job, kernel)
        check_ir(job, ir)

        asm = @timeit to[] "machine-code generation" mcgen(job, ir, kernel)
    end

    target == :ptx && return asm, kernel_fn

    ## CUDA objects

    @timeit to[] "CUDA object generation" begin
        # enable debug options based on Julia's debug setting
        jit_options = Dict{CUDAdrv.CUjit_option,Any}()
        if Base.JLOptions().debug_level == 1
            jit_options[CUDAdrv.GENERATE_LINE_INFO] = true
        elseif Base.JLOptions().debug_level >= 2
            jit_options[CUDAdrv.GENERATE_DEBUG_INFO] = true
        end

        # link the CUDA device library
        @timeit to[] "linking" begin
            linker = CUDAdrv.CuLink(jit_options)
            CUDAdrv.add_file!(linker, libcudadevrt, CUDAdrv.LIBRARY)
            CUDAdrv.add_data!(linker, kernel_fn, asm)
            image = CUDAdrv.complete(linker)
        end

        @timeit to[] "compilation" begin
            cuda_mod = CuModule(image, jit_options)
            cuda_fun = CuFunction(cuda_mod, kernel_fn)
        end
    end

    target == :cuda && return cuda_fun, cuda_mod

    error("Unknown compilation target $target")
end


text:
if isdefined(Main, :PyPlot)
  begin
  wh = [500,500]
  f = PyPlot.gcf()
  const pyplotplot = visualize(Texture(ARGB{Ufixed8}, wh))
  function visualize(style::Style, plot::Gadfly.Plot, customizations)
      ram  = convert(Array{Uint8},f[:canvas][:tostring_argb]())
      pyplotplot[:image][1:end, 1:end] = reinterpret(ARGB{Ufixed8}, ram, f[:canvas][:get_width_height]())
  end
  end
end
if isdefined(Main, :Gadfly)
  using Cairo, FixedPointNumbers
  wh = [500,500]
  const surface = Cairo.CairoARGBSurface(zeros(Uint32, wh...))
  const cairocontext = CairoContext(surface)
  global gadflyplot  = 0
  visualize(plot::Main.Gadfly.Plot, style::Style=Style(:Default); customizations...) = visualize(style, plot, Dict{Symbol, Any}(customizations))
  function redrawplot(plot::Main.Gadfly.Plot)
    set_source_rgba(cairocontext, 1.0,1.0,1.0,1.0)
    paint(cairocontext)
    Main.Gadfly.draw(Main.Gadfly.PNG(surface),  Main.Gadfly.render(plot))

  end
  function visualize(style::Style, plot::Main.Gadfly.Plot, customizations)
    global gadflyplot
    gadflyplot == 0 && (gadflyplot = visualize(Texture(BGRA{Ufixed8}, wh), screen=customizations[:screen]))
    redrawplot(plot)
    gadflyplot[:image][1:end, 1:end] = mapslices(reverse, reinterpret(BGRA{Ufixed8}, surface.data),2)
    gadflyplot
  end
end


text:
# This file is based on a file (julia/test/basic.jl) which is a part of Julia
# Further modifications and additions: Scott P. Jones & Stefan Schelm
# License is MIT: LICENSE.md

test_string_length = 1:256

const AllCharTypes = (ASCIIChr, LatinChr, UCS2Chr, UTF32Chr)

compat_types = Dict(ASCIIStr => (ASCIIChr, ),
                    LatinStr => (ASCIIChr, LatinChr),
                    UCS2Str => (ASCIIChr, LatinChr, UCS2Chr))

for T in (String, UTF8Str, UTF16Str, UTF32Str)
    compat_types[T] = AllCharTypes
end

string_types = keys(compat_types)

##  create type specific test strings
test_strings_base = Dict()
for T in AllCharTypes
    test_strings_base[T] = [String(rand(T, len)) for len in test_string_length]
end

@testset "constructors" begin
    for (ST, type_list) in compat_types, CT in type_list, str in test_strings_base[CT]
        @eval @test convert($ST, $str) == $str
    end
end

@testset "empty strings" begin
    for ST in keys(compat_types)
        @eval @test is_empty(convert($ST, ""))
    end
end

const titlelst = (0x1c4, 0x1c6, 0x1c7, 0x1c9, 0x1ca, 0x1cc, 0x1f1, 0x1f3) # 'ǅ', 'ǈ', 'ǲ', 'ǋ'

for ST in (ASCIIStr, LatinStr, UCS2Str, UTF32Str, UniStr, UTF8Str, UTF16Str)
    @testset "casefold string: $ST" begin
        C = eltype(ST)
        C == Char && (C = UTF32Chr)
        tm = typemax(C)
        for c = UInt32(0):UInt32(tm)
            # Skip surrogates
            0xd800 <= c < 0xe000 && continue
            # Handle 3 cases where LatinStr doesn't uppercase
            ST === LatinStr && c in (0xb5, 0xdf, 0xff) && continue
            ch = C(c)
            # Check to make sure this character would still fit uppercased
            cu = uppercase(ch)
            cu > tm && continue
            cl = lowercase(ch)
            for (i, str) in enumerate(("$ch", "$ch test Beg", "test End $ch", "test $ch Mid"))
                t = c >>> 9
                cvtstr = convert(ST, str)
                @test uppercase(str) == uppercase(cvtstr)
                @test lowercase(str) == lowercase(cvtstr)
                #@test titlecase(str) == titlecase(cvtstr)
                i > 2 && continue
                @test lowercase_first(str) == lowercase_first(cvtstr)
                #if flg
                #@test_broken uppercase_first(str) == uppercase_first(cvtstr)
                #else
                    @test uppercase_first(str) == uppercase_first(cvtstr)
                #end
            end
        end
    end
end

@testset "{starts,ends}_with" begin
    for (ST, type_list) in compat_types, CT in type_list, str in test_strings_base[CT]
        cvtstr = convert(ST, str)
        beg = lst = CT(' ')
        bty = lty = CT
        bch = lch = 0%UInt32
        try
            beg = str[1]   ; bty = typeof(beg) ; bch = beg%UInt32
            lst = str[end] ; lty = typeof(lst) ; lch = lst%UInt32
            @eval @test starts_with($cvtstr, $beg)
            starts_with(cvtstr, beg) ||
                println("starts_with($cvtstr, $beg): $ST, $CT, $bty, $bch")
            @eval @test ends_with($cvtstr, $lst)
            ends_with(cvtstr, lst) ||
                println("ends_with($cvtstr, $lst): $ST, $CT, $lty, $lch")
        catch ex
            println("Error: $cvtstr, $beg, $lst: $ST, $CT, $bty, $bch, $lty, $lch")
            println(sprint(showerror, ex, catch_backtrace()))
        end
        ##   TODO needs test which would run in case the start and end chars are the same
        if beg != lst
            @eval @test !starts_with($cvtstr, $lst)
            @eval @test !ends_with($cvtstr, $beg)
        end
    end
end

codegen_egal_of_strings(x, y) = (x===y, x!==y)

# test AbstractString functions at beginning of string.jl
struct tstStringType <: AbstractString
    data::Array{UInt8,1}
end
mutable struct CharStr <: AbstractString
    chars::Vector{Char}
    CharStr(x) = new(collect(x))
end
iterate(x::CharStr, i::Int=1) = iterate(x.chars, i)

lastindex(x::CharStr) = lastindex(x.chars)
ncodeunits(x::CharStr) = lastindex(x.chars)
codeunit(x::CharStr) = Char

function testbasic(::Type{ST}, ::Type{C}) where {ST, C}
    emptystr = ST("")
    a_str    = ST("a")
    ab_str   = ST("ab")
    abc_str  = ST("abc")
    abce_str = ST("abc!")
    abcd_str = ST("abcd")
    hello1   = ST("hello")
    hello2   = ST("hellø")

    c_chr    = cvtchar(C, 'c')

@testset "constructors" begin
    @test abce_str == "abc!"
    v = [0x61,0x62,0x63,0x21]
    @test ST(v) == abce_str # && isempty(v)
        if ST === String # IS_WORKING # Need to add constructor with range
            @test isempty(v)
            @test ST(0x61:0x63) == abc_str
        end

        # Check that resizing empty source vector does not corrupt string
        b = IOBuffer()
        write(b, ab_str)
        x = take!(b)
        s = ST(x)
        resize!(x, 0)
        empty!(x) # Another method which must be tested
        @test s == ab_str
        resize!(x, 1)
        @test s == ab_str

    @test isempty(ST(string()))
    @test eltype(GenericString) == Char
    @test firstindex(abc_str) == 1
    @test cmp(ab_str,abc_str) == -1

        if ST === String # IS_WORKING
            @test typemin(ST) === ST("")
            @test typemin(abc_str) === ST("")
            @test abc_str === abc_str
            @test ab_str  !== abc_str
            @test string(ab_str, c_chr) === abc_str
            @test string() === ""
            @test codegen_egal_of_strings(string(ab_str, c_chr), abc_str) === (true, false)
        end
        let strs = [emptystr, a_str, ST("a b c"), ST("до свидания")]
            for x in strs, y in strs
                @eval @test ($x === $y) == (objectid($x) == objectid($y))
            end
        end
end

@testset "{starts,ends}_with" begin
    @test starts_with(abcd_str, cvtchar(C,'a'))
    @test starts_with(abcd_str, a_str)
    @test starts_with(abcd_str, ab_str)
    @test !starts_with(ab_str, abcd_str)
    @test !starts_with(abcd_str, ST("bc"))
    @test ends_with(abcd_str, cvtchar(C,'d'))
    @test ends_with(abcd_str, ST("d"))
    @test ends_with(abcd_str, ST("cd"))
    @test !ends_with(abcd_str, ST("dc"))
    @test !ends_with(ST("cd"), abcd_str)
    @test starts_with(ST("ab\0cd"), ST("ab\0c"))
    @test !starts_with(ST("ab\0cd"), ST("ab\0d"))
end

@test filter(x -> x ∈ ['f', 'o'], "foobar") == "foo"

@testset "string iteration, and issue #1454" begin
    str = ST("é")
    str_a = vcat(str...)
    @test length(str_a)==1
    @test str_a[1] == str[1]

    str = ST("s\u2200")
    @test str[1:end] == str
end

@testset "sizeof" begin
    @test sizeof(abc_str) == 3
    @test sizeof(ST("\u2222")) == 3
end

# issue #3597
@test string(GenericString(ST("Test"))[1:1], ST("X")) == "TX"

@testset "parsing Int types" begin
    let b, n
    for T = (UInt8,Int8,UInt16,Int16,UInt32,Int32,UInt64,Int64,UInt128,Int128,BigInt),
            b = 2:62,
            _ = 1:10
        n = (T != BigInt) ? rand(T) : BigInt(rand(Int128))
        @test parse(T, ST(string(n, base = b)),  base = b) == n
    end
end

@testset "Symbol and gensym" begin
    @test Symbol("asdf") === :asdf
    @test Symbol(:abc,"def",'g',"hi",0) === :abcdefghi0
    @test :a < :b
    @test starts_with(string(gensym("asdf")),"##asdf#")
    @test gensym("asdf") != gensym("asdf")
    @test gensym() != gensym()
    @test starts_with(string(gensym()),"##")
    @test_throws ArgumentError Symbol("ab\0")
    @test_throws ArgumentError gensym("ab\0")
end
@testset "issue #6949" begin
    f = IOBuffer()
    x = split(ST("1 2 3"))
    for c in x
        print(f, c) # was write
    end
    @test f.size == 3
    @test ST(take!(f)) == "123"
end

@testset "issue #7248" begin
    @test_throws BoundsError length(hello1, 1, -1)
    @test_throws BoundsError prevind(hello1, 0, 1)
    @test_throws BoundsError length(hello2, 1, -1)
    @test_throws BoundsError prevind(hello2, 0, 1)
    @test_throws BoundsError length(hello1, 1, 10)
    ST === String && @test nextind(hello1, 0, 10) == 10
    @test_throws BoundsError length(hello2, 1, 10) == 9
    ST == String && @test nextind(ST("hellø"), 0, 10) == 11
    for ind in (0, 6, 0:3, 4:6, [0:3;], [4:6;])
        @eval @test_throws BoundsError checkbounds($hello1, $ind)
    end
    for ind in (1, 5, 1:3, 3:5, [1:3;], [3:5;])
        @eval @test checkbounds($hello1, $ind) === nothing
    end
    f = false
    t = true
    for (ind, p) in ((0, f), (1, t), (5, t), (6, f), (0:5, f), (1:6, f),
                     (1:5, t), ([0:5;], f), ([1:6;], f), ([1:5;], t))
        @eval @test checkbounds(Bool, $hello1, $ind) === $p
    end
end

@testset "issue #15624 (indexing with out of bounds empty range)" begin
    @test emptystr[10:9] == ""
    @test hello1[10:9] == ""
    @test hello2[10:9] == ""
    @test SubString(hello1, 1, 5)[10:9] == ""
    @test SubString(hello1, 1, 0)[10:9] == ""
    @test SubString(hello2, 1, 5)[10:9] == ""
    @test SubString(hello2, 1, 0)[10:9] == ""
    @test SubString(emptystr, 1, 0)[10:9] == ""
    @test_throws BoundsError SubString(emptystr, 1, 6)
    @test_throws BoundsError SubString(emptystr, 1, 1)
end

@testset "issue #22500 (using `get()` to index strings with default returns)" begin
    utf8_str = ST("我很喜欢Julia")

    # Test that we can index in at valid locations
    @test get(utf8_str, 1, cvtchar(C,'X')) == '我'
    @test get(utf8_str, 13, cvtchar(C,'X')) == 'J'

    # Test that obviously incorrect locations return the default
    @test get(utf8_str, -1, cvtchar(C,'X')) == 'X'
    @test get(utf8_str, 1000, cvtchar(C,'X')) == 'X'

    # Test that indexing into the middle of a character throws
    @test_throws StringIndexError get(utf8_str, 2, cvtchar(C,'X'))
end

# issue #7764
let
    srep = repeat("Σβ",2)
    s="Σβ"
    ss=SubString(s,1,lastindex(s))

    @test repeat(ss,2) == "ΣβΣβ"

    @test lastindex(srep) == 7

    @test str_next(srep, 3) == ('β',5)
    @test str_next(srep, 7) == ('β',9)

    @test srep[7] == 'β'
    @test_throws StringIndexError srep[8]
end

# make sure substrings do not accept code unit if it is not start of codepoint
let s = ST("x\u0302")
    @test s[1:2] == s
    @test_throws BoundsError s[0:3]
    @test_throws BoundsError s[1:4]
    @test_throws StringIndexError s[1:3]
end

@testset "issue #9781" begin
    # parse(Float64, SubString) wasn't tolerant of trailing whitespace, which was different
    # to "normal" strings. This also checks we aren't being too tolerant and allowing
    # any arbitrary trailing characters.
    @test parse(Float64, ST("1\n")) == 1.0
    @test [parse(Float64,x) for x in split(ST("0,1\n"),ST(","))][2] == 1.0
    @test_throws ArgumentError parse(Float64,split(ST("0,1 X\n"),ST(","))[2])
    @test parse(Float32,ST("1\n")) == 1.0
    @test [parse(Float32,x) for x in split(ST("0,1\n"),ST(","))][2] == 1.0
    @test_throws ArgumentError parse(Float32,split(ST("0,1 X\n"),ST(","))[2])
end

@testset "AbstractString functions" begin
    tstr = tstStringType(unsafe_wrap(Vector{UInt8},"12"))
    @test_throws MethodError ncodeunits(tstr)
    @test_throws MethodError codeunit(tstr)
    @test_throws MethodError codeunit(tstr, 1)
    @test_throws MethodError codeunit(tstr, true)
    @test_throws MethodError isvalid(tstr, 1)
    @test_throws MethodError isvalid(tstr, true)
    @test_throws MethodError str_next(tstr, 1)
    @test_throws MethodError str_next(tstr, true)
    @test_throws MethodError lastindex(tstr)

    gstr = GenericString("12")
    @test string(gstr) isa GenericString

    @test Array{UInt8}(gstr) == [49, 50]
    @test Array{Char,1}(gstr) == ['1', '2']

    @test gstr[1] == '1'
    @test gstr[1:1] == "1"
    @test gstr[[1]] == "1"

    @test s"∀∃"[big(1)] == '∀'
    @test_throws StringIndexError GenericString("∀∃")[Int8(2)]
    @test_throws BoundsError GenericString("∀∃")[UInt16(10)]

    foobar = ST("foobar")

    @test iterate(eachindex(foobar), 7) === nothing
    @test first(eachindex(foobar)) === 1
    @test first(eachindex(ST(""))) === 1
    @test last(eachindex(foobar)) === lastindex(foobar)
    @test nextind(ST("fóobar"), 0, 3) == 4
    @test Int == eltype(Base.EachStringIndex) ==
        eltype(Base.EachStringIndex{String}) ==
        eltype(Base.EachStringIndex{GenericString}) ==
        eltype(eachindex(foobar)) == eltype(eachindex(gstr))
    @test map(uppercase, ST("foó")) == ST("FOÓ")

    @test Symbol(gstr) == Symbol("12")

    @test sizeof(gstr) == 2
    @test ncodeunits(gstr) == 2
    @test length(gstr) == 2
    @test length(GenericString("")) == 0

    @test nextind(1:1, 1) == 2
    @test nextind([1], 1) == 2

    @test length(gstr, 1, 2) == 2

    # no string promotion
    let svec = [s"12", GenericString("12"), SubString("123", 1, 2)]
        @test all(x -> x == "12", svec)
        @test svec isa Vector{AbstractString}
    end
end

check_tryparse(T, v, r) = (tryparse(T, v) == r)

@testset "issue #10307" begin
    #@test typeof(map(x -> parse(Int16, x), AbstractString[])) == Vector{Int16}
    println(typeof(map(x -> parse(Int16, x), AbstractString[])))

    for T in [Int8, UInt8, Int16, UInt16, Int32, UInt32, Int64, UInt64, Int128, UInt128]
        for i in [typemax(T), typemin(T)]
            s = "$i"
            @test check_tryparse(T, s, i)
        end
    end

    for T in [Int8, Int16, Int32, Int64, Int128]
        for i in [typemax(T), typemin(T)]
            f = "$(i)0"
            @test check_tryparse(T, f, nothing)
        end
    end
end

@testset "issue #11142" begin
    s = ST("abcdefghij")
    sp = pointer(s)
    @test unsafe_string(sp) == s
    @test unsafe_string(sp,5) == ST("abcde")
    @test typeof(unsafe_string(sp)) == String
    s = ST("abcde\uff\u2000\U1f596")
    sp = pointer(s)
    @test unsafe_string(sp) == s
    @test unsafe_string(sp,5) == ST("abcde")
    @test typeof(unsafe_string(sp)) == String

    @test check_tryparse(BigInt, ST("1234567890"), BigInt(1234567890))
    @test check_tryparse(BigInt, ST("1234567890-"), nothing)

    @test check_tryparse(Float64, ST("64"), 64.0)
    @test check_tryparse(Float64, ST("64o"), nothing)
    @test check_tryparse(Float32, ST("32"), 32.0f0)
    @test check_tryparse(Float32, ST("32o"), nothing)
end

@testset "issue #10994: handle embedded NUL chars for string parsing" begin
    for T in [BigInt, Int8, UInt8, Int16, UInt16, Int32, UInt32, Int64, UInt64, Int128, UInt128]
        @test_throws ArgumentError parse(T, ST("1\0"))
    end
    for T in [BigInt, Int8, UInt8, Int16, UInt16, Int32, UInt32, Int64, UInt64, Int128, UInt128,
              Float64, Float32]
        @test check_tryparse(T, ST("1\0"), nothing)
    end
    let s = Unicode.normalize(ST("tést"), :NFKC)
        @test unsafe_string(Base.unsafe_convert(Cstring, Base.cconvert(Cstring, s))) == s
        @test unsafe_string(Base.unsafe_convert(Cstring, Symbol(s))) == s
    end
    @test_throws ArgumentError Base.unsafe_convert(Cstring, Base.cconvert(Cstring, ST("ba\0d")))

    cstrdup(s) =
        @static Base.Sys.KERNEL in (:Windows, :NT) ?
        ccall(:_strdup, Cstring, (Cstring,), s) :
        ccall(:strdup, Cstring, (Cstring,), s)

    let p = cstrdup(hello1)
        @test unsafe_string(p) == hello1
        Libc.free(p)
    end
end

@testset "iteration" begin
    str = ST("ḟøøƀäṙ")
    @test [c for c in str] == ['ḟ', 'ø', 'ø', 'ƀ', 'ä', 'ṙ']
    @test [i for i in eachindex(str)] == [1, 4, 6, 8, 10, 12]
    @test [x for x in enumerate(str)] ==
        [(1, 'ḟ'), (2, 'ø'), (3, 'ø'), (4, 'ƀ'), (5, 'ä'), (6, 'ṙ')]
end
@testset "isvalid edge conditions" begin
    for (val, pass) in (
            (String(b"\x00"), true),
            (String(b"\x7f"), true),
            (String(b"\x80"), false),
            (String(b"\xbf"), false),
            (String(b"\xc0"), false),
            (String(b"\xff"), false),
            (String(b"\xc0\x80"), false),
            (String(b"\xc1\x80"), false),
            (String(b"\xc2\x80"), true),
            (String(b"\xc2\xc0"), false),
            (String(b"\xed\x9f\xbf"), true),
            (String(b"\xed\xa0\x80"), false),
            (String(b"\xed\xbf\xbf"), false),
            (String(b"\xee\x80\x80"), true),
            (String(b"\xef\xbf\xbf"), true),
            (String(b"\xf0\x80\x80\x80"), false),
            (String(b"\xf0\x90\x80\x80"), true),
            (String(b"\xf4\x8f\xbf\xbf"), true),
            (String(b"\xf4\x90\x80\x80"), false),
            (String(b"\xf5\x80\x80\x80"), false),
            (String(b"\ud800\udc00"), false),
            (String(b"\udbff\udfff"), false),
            (String(b"\ud800\u0100"), false),
            (String(b"\udc00\u0100"), false),
            (String(b"\udc00\ud800"), false))
        is_valid(ST, val) == pass ||
            println(idx, ":", ST, " -> ", val)
        @test is_valid(ST, val) == pass
        @test is_valid(C, val[1]) == pass
    end

    # Issue #11203
    @test is_valid(ST, UInt8[]) == true == is_valid(ST(""))

    # Check UTF-8 characters
    # Check ASCII range (true),
    # then single continuation bytes and lead bytes with no following continuation bytes (false)
    for (rng,flg) in ((0:0x7f, true), (0x80:0xff, false))
        for byt in rng
            @test is_valid(ST, UInt8[byt]) == flg
        end
    end
    # Check overlong lead bytes for 2-character sequences (false)
    for byt = 0xc0:0xc1
        @test is_valid(ST, UInt8[byt,0x80]) == false
    end
    # Check valid lead-in to two-byte sequences (true)
    for byt = 0xc2:0xdf
        for (rng,flg) in ((0x00:0x7f, false), (0x80:0xbf, true), (0xc0:0xff, false))
            for cont in rng
                @test is_valid(ST, UInt8[byt, cont]) == flg
            end
        end
    end
    # Check for short three-byte sequences
    @test is_valid(ST, UInt8[0xe0]) == false
    for (rng, flg) in ((0x00:0x9f, false), (0xa0:0xbf, true), (0xc0:0xff, false))
        for cont in rng
            @test is_valid(ST, UInt8[0xe0, cont]) == false
            if false # ST === String && (0x80 <= cont <= 0x9f)
                @test_broken is_valid(ST, UInt8[0xe0, cont, 0x80]) == flg
            else
                is_valid(ST, UInt8[0xe0, cont, 0x80]) == flg ||
                    println("isvalid($ST, [0x80, $cont, 0x80])")
                @test is_valid(ST, UInt8[0xe0, cont, 0x80]) == flg
            end
        end
    end
    # Check three-byte sequences
    for r1 in (0xe1:0xec, 0xee:0xef), byt in r1
        # Check for short sequence
        @test is_valid(ST, UInt8[byt]) == false
        for (rng, flg) in ((0x00:0x7f, false), (0x80:0xbf, true), (0xc0:0xff, false))
            for cont in rng
                @test is_valid(ST, UInt8[byt, cont]) == false
                is_valid(ST, UInt8[byt, cont, 0x80]) == flg ||
                    println("isvalid(", ST, ", [", byt, ", ", cont, ", 0x80])")
                @test is_valid(ST, UInt8[byt, cont, 0x80]) == flg
            end
        end
    end
    # Check hangul characters (0xd000-0xd7ff) hangul
    # Check for short sequence, or start of surrogate pair
    for (rng,flg) in ((0x00:0x7f, false), (0x80:0x9f, true), (0xa0:0xff, false))
        for cont in rng
            @test is_valid(ST, UInt8[0xed, cont]) == false
            @test is_valid(ST, UInt8[0xed, cont, 0x80]) == flg
        end
    end
    # Check valid four-byte sequences
    for byt = 0xf0:0xf4
        if (byt == 0xf0)
            r0 = ((0x00:0x8f, false), (0x90:0xbf, true), (0xc0:0xff, false))
        elseif byt == 0xf4
            r0 = ((0x00:0x7f, false), (0x80:0x8f, true), (0x90:0xff, false))
        else
            r0 = ((0x00:0x7f, false), (0x80:0xbf, true), (0xc0:0xff, false))
        end
        for (rng,flg) in r0
            for cont in rng
                @test is_valid(ST, UInt8[byt, cont]) == false
                @test is_valid(ST, UInt8[byt, cont, 0x80]) == false
                is_valid(ST, UInt8[byt, cont, 0x80, 0x80]) == flg ||
                    println("isvalid(", ST, ", [", byt, ", ", cont, ", 0x80, 0x80])")
                @test is_valid(ST, UInt8[byt, cont, 0x80, 0x80]) == flg
            end
        end
    end
    # Check five-byte sequences, should be invalid
    for byt = 0xf8:0xfb
        @test is_valid(ST, UInt8[byt, 0x80, 0x80, 0x80, 0x80]) == false
    end
    # Check six-byte sequences, should be invalid
    for byt = 0xfc:0xfd
        @test is_valid(ST, UInt8[byt, 0x80, 0x80, 0x80, 0x80, 0x80]) == false
    end
    # Check seven-byte sequences, should be invalid
    @test is_valid(ST, UInt8[0xfe, 0x80, 0x80, 0x80, 0x80, 0x80]) == false
end

@testset "NULL pointers are handled consistently by String" begin
    @test_throws ArgumentError unsafe_string(Ptr{UInt8}(0))
    @test_throws ArgumentError unsafe_string(Ptr{UInt8}(0), 10)
end
@testset "ascii for ASCII strings and non-ASCII strings" begin
    s = "Hello, world"
    str = ST(s)
    @test ascii(str) == s
    @test typeof(ascii(str)) == String
    @test ascii(GenericString(str)) == s
    @test typeof(ascii(GenericString(str))) == String
    @test_throws ArgumentError ascii(ST("Hello, ∀"))
    @test_throws ArgumentError ascii(GenericString(ST("Hello, ∀")))
end
@testset "issue #17271: lastindex() doesn't throw an error even with invalid strings" begin
    @test lastindex(String(b"\x90")) == 1
    @test lastindex(String(b"\xce")) == 1
end
# issue #17624, missing getindex method for String
@test abc_str[:] == "abc"

@testset "issue #18280: next/nextind must return past String's underlying data" begin
    for st in ("Hello", "Σ", "こんにちは", "😊😁")
        local s
        s = ST(st)
        @test str_next(s, lastindex(s))[2] > sizeof(s)
        @test nextind(s, lastindex(s)) > sizeof(s)
    end
end
# Test cmp with AbstractStrings that don't index the same as UTF-8, which would include
# (LegacyString.)UTF16String and (LegacyString.)UTF32String, among others.

@testset "cmp without UTF-8 indexing" begin
    # Simple case, with just ANSI Latin 1 characters
    @test ST("áB") != CharStr("áá") # returns false with bug
    @test cmp(ST("áB"), CharStr("áá")) == -1 # returns 0 with bug

    # Case with Unicode characters
    @test cmp(ST("\U1f596\U1f596"), CharStr("\U1f596")) == 1   # Gives BoundsError with bug
    @test cmp(CharStr("\U1f596"), ST("\U1f596\U1f596")) == -1
end

@testset "repeat strings" begin
    @inferred repeat(GenericString("x"), 1)
    @test repeat("xx",3) == repeat("x",6) == repeat(GenericString("x"), 6) == "xxxxxx"
    @test repeat("αα",3) == repeat("α",6) == repeat(GenericString("α"), 6) == "αααααα"
    @test repeat("x",1)  == "x"^1 == GenericString("x")^1 == "x"
    @test repeat("x",0)  == "x"^0 == GenericString("x")^0 == ""

    for S in ["xxx", "ååå", "∀∀∀", "🍕🍕🍕"]
        s = string(S[1])
        @test_throws ArgumentError repeat(s, -1)
        @test_throws ArgumentError repeat(S, -1)
        @test repeat(s, 0) == ""
        @test repeat(S, 0) == ""
        @test repeat(s, 1) == s
        @test repeat(S, 1) == S
        @test repeat(s, 3) == S
        @test repeat(S, 3) == S*S*S
    end
end

@testset "repeat characters" begin
    maxch = Char(typemax(C))
    @test repeat(C('x'),6) == "xxxxxx"
    'α' > maxch || @test repeat(C('α'),6) == "αααααα"
    @test repeat(C('x'),1) == 'x'^1 == "x"
    @test repeat(C('x'),0) == 'x'^0 == ""

    for str in ["xxx", "ååå", "∀∀∀", "🍕🍕🍕"]
        str[1] > maxch && continue
        c = C(str[1])
        l = string(c)
        @test_throws ArgumentError repeat(c, -1)
        @test repeat(c, 0) == ""
        @test repeat(c, 1) == l
        @test repeat(c, 3) == str
    end
end

@testset "issue #12495: check that logical indexing attempt raises ArgumentError" begin
    @test_throws ArgumentError abc_str[[true, false, true]]
    @test_throws ArgumentError abc_str[BitArray([true, false, true])]
end

@testset "concatenation" begin
    @test ab_str * ST("cd") == abcd_str
    @test C('a') * ST("bc") == abc_str
    @test ab_str * C('c') == abc_str
    @test C('a') * C('b') == ab_str
    @test C('a') * ST("b") * C('c') == abc_str
    @test a_str * C('b') * C('c') == abc_str
end

@testset "unrecognized escapes in string/char literals" begin
    @test_throws Meta.ParseError parse(Expr, ST("\"\\.\""))
    @test_throws Meta.ParseError parse(Expr, ST("\'\\.\'"))
end

@testset "thisind" begin
    let strs = Any[ST("∀α>β:α+1>β"),
                   s"∀α>β:α+1>β",
                   SubString(ST("123∀α>β:α+1>β123"), 4, 18),
                   SubString(s"123∀α>β:α+1>β123", 4, 18)]
        for s in strs
            @test_throws BoundsError thisind(s, -2)
            @test_throws BoundsError thisind(s, -1)
            typeof(s) <: Str || typeof(s) <: SubString{<:Str} || @test thisind(s, 0) == 0
            @test thisind(s, 1) == 1
            @test thisind(s, 2) == 1
            @test thisind(s, 3) == 1
            @test thisind(s, 4) == 4
            @test thisind(s, 5) == 4
            @test thisind(s, 6) == 6
            @test thisind(s, 15) == 15
            @test thisind(s, 16) == 15
            typeof(s) <: Str || typeof(s) <: SubString{<:Str} || @test thisind(s, 17) == 17
            @test_throws BoundsError thisind(s, 18)
            @test_throws BoundsError thisind(s, 19)
        end
    end

    let strs = Any[ST(""), s"", SubString(ST("123"), 2, 1), SubString(s"123", 2, 1)]
        for s in strs
            @test_throws BoundsError thisind(s, -1)
            @test thisind(s, 0) == 0  # would prefer that this threw a BoundsError
            @test thisind(s, 1) == 1  # would prefer that this threw a BoundsError
            @test_throws BoundsError thisind(s, 2)
        end
    end
end

ST == String && @testset "prevind and nextind" begin
    for s in Any[ST("∀α>β:α+1>β"), GenericString(ST("∀α>β:α+1>β"))]
        @test_throws BoundsError prevind(s, 0)
        @test_throws BoundsError prevind(s, 0, 0)
        @test_throws BoundsError prevind(s, 0, 1)
        @test prevind(s, 1) == 0
        @test prevind(s, 1, 1) == 0
        @test prevind(s, 1, 0) == 1
        @test prevind(s, 2) == 1
        @test prevind(s, 2, 1) == 1
        @test prevind(s, 4) == 1
        @test prevind(s, 4, 1) == 1
        @test prevind(s, 5) == 4
        @test prevind(s, 5, 1) == 4
        @test prevind(s, 5, 2) == 1
        @test prevind(s, 5, 3) == 0
        @test prevind(s, 15) == 14
        @test prevind(s, 15, 1) == 14
        @test prevind(s, 15, 2) == 13
        @test prevind(s, 15, 3) == 12
        @test prevind(s, 15, 4) == 10
        @test prevind(s, 15, 10) == 0
        @test prevind(s, 15, 9) == 1
        @test prevind(s, 16) == 15
        @test prevind(s, 16, 1) == 15
        @test prevind(s, 16, 2) == 14
        @test prevind(s, 17) == 15
        @test prevind(s, 17, 1) == 15
        @test prevind(s, 17, 2) == 14
        @test_throws BoundsError prevind(s, 18)
        @test_throws BoundsError prevind(s, 18, 0)
        @test_throws BoundsError prevind(s, 18, 1)

        @test_throws BoundsError nextind(s, -1)
        @test_throws BoundsError nextind(s, -1, 0)
        @test_throws BoundsError nextind(s, -1, 1)
        @test nextind(s, 0, 2) == 4
        @test nextind(s, 0, 20) == 26
        @test nextind(s, 0, 10) == 15
        @test nextind(s, 1) == 4
        @test nextind(s, 1, 1) == 4
        @test nextind(s, 1, 2) == 6
        @test nextind(s, 1, 9) == 15
        @test nextind(s, 1, 10) == 17
        @test nextind(s, 2) == 4
        @test nextind(s, 2, 1) == 4
        @test nextind(s, 3) == 4
        @test nextind(s, 3, 1) == 4
        @test nextind(s, 4) == 6
        @test nextind(s, 4, 1) == 6
        @test nextind(s, 14) == 15
        @test nextind(s, 14, 1) == 15
        @test nextind(s, 15) == 17
        @test nextind(s, 15, 1) == 17
        @test nextind(s, 15, 2) == 18
        @test nextind(s, 16) == 17
        @test nextind(s, 16, 1) == 17
        @test nextind(s, 16, 2) == 18
        @test nextind(s, 16, 3) == 19
        @test_throws BoundsError nextind(s, 17)
        @test_throws BoundsError nextind(s, 17, 0)
        @test_throws BoundsError nextind(s, 17, 1)

        for x in 0:ncodeunits(s)+1
            n = p = x
            for j in 1:40
                if 1 ≤ p
                    p = prevind(s, p)
                    @test prevind(s, x, j) == p
                end
                if n ≤ ncodeunits(s)
                    n = nextind(s, n)
                    @test nextind(s, x, j) == n
                end
            end
        end
    end
end

@testset "first and last" begin
    s = ST("∀ϵ≠0: ϵ²>0")
    @test_throws ArgumentError first(s, -1)
    @test first(s, 0) == ""
    @test first(s, 1) == "∀"
    @test first(s, 2) == "∀ϵ"
    @test first(s, 3) == "∀ϵ≠"
    @test first(s, 4) == "∀ϵ≠0"
    @test first(s, length(s)) == s
    # This only works for String, Str does not allow out of range # of characters
    ST === String && @test first(s, length(s)+1) == s
    @test_throws ArgumentError last(s, -1)
    @test last(s, 0) == ""
    @test last(s, 1) == "0"
    @test last(s, 2) == ">0"
    @test last(s, 3) == "²>0"
    @test last(s, 4) == "ϵ²>0"
    @test last(s, length(s)) == s
    ST === String && @test last(s, length(s)+1) == s
end

@testset "ncodeunits" begin
    for (str, n) in [""     => 0, a_str   => 1, abc_str  => 3,
                   "α"    => 2, "abγ" => 4, "∀"    => 3,
                   "∀x∃y" => 8, "🍕"  => 4, "🍕∀" => 7]
        s = ST(str)
        @test ncodeunits(s) == n
        @test ncodeunits(GenericString(s)) == n
    end
end

@testset "0-step nextind and prevind" begin
    for T in [ST, SubString, Base.SubstitutionString, GenericString]
        e = convert(T, ST(""))
        @test nextind(e, 0, 0) == 0
        @test_throws BoundsError nextind(e, 1, 0)
        @test_throws BoundsError prevind(e, 0, 0)
        @test prevind(e, 1, 0) == 1

        s = convert(T, ST("∀x∃"))
        @test nextind(s, 0, 0) == 0
        @test nextind(s, 1, 0) == 1
        @test_throws StringIndexError nextind(s, 2, 0)
        @test_throws StringIndexError nextind(s, 3, 0)
        @test nextind(s, 4, 0) == 4
        @test nextind(s, 5, 0) == 5
        @test_throws StringIndexError nextind(s, 6, 0)
        @test_throws StringIndexError nextind(s, 7, 0)
        @test_throws BoundsError nextind(s, 8, 0)

        @test_throws BoundsError prevind(s, 0, 0)
        @test prevind(s, 1, 0) == 1
        @test_throws StringIndexError prevind(s, 2, 0)
        @test_throws StringIndexError prevind(s, 3, 0)
        @test prevind(s, 4, 0) == 4
        @test prevind(s, 5, 0) == 5
        @test_throws StringIndexError prevind(s, 6, 0)
        @test_throws StringIndexError prevind(s, 7, 0)
        @test prevind(s, 8, 0) == 8
    end
end
end

    # codeunit vectors

    let s = ST("∀x∃y"), u = codeunits(s)
        @test u isa CodeUnits{UInt8,ST}
        @test length(u) == ncodeunits(s) == 8
        @test sizeof(u) == sizeof(s)
        @test eltype(u) === UInt8
        @test size(u) == (length(u),)
        @test strides(u) == (1,)
        @test u[1] == 0xe2
        @test u[2] == 0x88
        @test u[8] == 0x79
        @test_throws ErrorException (u[1] = 0x00)
        @test collect(u) == b"∀x∃y"
    end

    # PR #25535
    let v = [0x40,0x41,0x42]
        @test ST(view(v, 2:3)) == "AB"
    end

    # make sure length for identical String and AbstractString return the same value, PR #25533
    let rng = MersenneTwister(1),
        strs = [ST("∀εa∀aε"*String(rand(rng, Char, 100))*"∀εa∀aε"), ST(rand(rng, Char, 200))]
        for s in strs, i in 1:ncodeunits(s)+1, j in 0:ncodeunits(s)
            length(s,i,j) == length(GenericString(s),i,j) || println("length(\"$s\",$i,$j)")
            @test length(s,i,j) == length(GenericString(s),i,j)
        end
        for i in 0:10, j in 1:100,
            s in [ST(randstring(rng, i)), ST(randstring(rng, "∀∃α1", i)), ST(rand(rng, Char, i))]
            @test length(s) == length(GenericString(s))
        end
    end

    # conversion of SubString to the same type, issue #25525
    let x = SubString(ab_str, 1, 1)
        y = convert(SubString{ST}, x)
        @test y === x
        chop(ab_str) === chop.([ab_str])[1]
    end
end

function testbin(::Type{ST}) where {ST}

    @test unsafe_wrap(Vector{UInt8},String(b"\xcc\xdd\xee\xff\x80")) ==
        [0xcc,0xdd,0xee,0xff,0x80]

    for lst in ((b"a", b"az", b"a\xb1", b"a\xb1z", b"a\xb1\x83", b"a\xb1\x83\x84",
                 b"a\xb1\x83\x84z"),
                (b"\x81", b"\x81z", b"\x81\xb1", b"\x81\xb1z", b"\x81\xb1\x83",
                 b"\x81\xb1\x83\x84", b"\x81\xb1\x83\x84z"),
                (b"\xf8", b"\xf8z", b"\xf8\x9f", b"\xf8\x9fz", b"\xf8\x9f\x98", b"\xf8\x9f\x98z",
                 b"\xf8\x9f\x98\x84", b"\xf8\x9f\x98\x84z")),
        s in lst
        st = ST(s)
        @test str_next(st, 1)[2] == 2
        @test nextind(st, 1) == 2
    end

    for lst in (((b"\xce", 2), (b"\xcez", 2), (b"\xce\xb1", 3), (b"\xce\xb1z", 3),
                 (b"\xce\xb1\x83", 3), (b"\xce\xb1\x83\x84", 3), (b"\xce\xb1\x83\x84z", 3)),
                ((b"\xe2", 2), (b"\xe2z", 2), (b"\xe2\x88", 3), (b"\xe2\x88z", 3),
                 (b"\xe2\x88\x83", 4), (b"\xe2\x88\x83z", 4), (b"\xe2\x88\x83\x84", 4),
                 (b"\xe2\x88\x83\x84z", 4)),
                ((b"\xf0", 2), (b"\xf0z", 2), (b"\xf0\x9f", 3), (b"\xf0\x9fz", 3),
                 (b"\xf0\x9f\x98", 4), (b"\xf0\x9f\x98z", 4), (b"\xf0\x9f\x98\x84", 5),
                 (b"\xf0\x9f\x98\x84z", 5))),
        (s, r) in lst
        st = ST(s)
        (ST === BinaryStr || ST === Text1Str) && (r = 2)
        @test str_next(st, 1)[2] == r
        @test nextind(st, 1) == r
    end
end

for ST in UnicodeStringTypes
    C = eltype(ST)
    @testset "Basic String Tests: $ST, $C" begin testbasic(ST, C) end
end
for ST in (BinaryStr, Text1Str, String)
    @testset "Binary String Tests: $ST" begin testbin(ST) end
end

# These only work for String (after #24999)
@testset "issue #6027 - make symbol with invalid char" begin
    sym = Symbol(Char(0xdcdb))
    @test string(sym) == string(Char(0xdcdb))
    @test String(sym) == string(Char(0xdcdb))
    @test Meta.lower(Main, sym) === sym
    res = string(Meta.parse(string(Char(0xdcdb)," = 1"),1,raise=false)[1])
    @test startswith(res, "\$(Expr(:error, \"invalid character \\\"\\udcdb\\\"")
    @test endswith(res,   "\"))")
end

@testset "invalid code point" begin
    s = String([0x61, 0xba, 0x41])
    @test !is_valid(s)
    # This has to do with the #24999 change to character representation
    @test s[2] == reinterpret(Char, UInt32(0xba) << 24)
end

@testset "issue #24388" begin
    let v = unsafe_wrap(Vector{UInt8}, "abc")
        s = String(v)
        @test_throws BoundsError v[1]
        push!(v, UInt8('x'))
        @test s == "abc"
    end
end

@testset "Unicode Strings" begin
    # Unicode errors
    let io = IOBuffer()
        show(io, StringError(StrErrors.SHORT, 1, 10))
        check = "$(StringError): invalid UTF-8 sequence starting at index 1 (0xa) missing one or more continuation bytes"
        @test String(take!(io)) == check
    end
end

@testset "CESU-8 sequences" begin
    ## UTF-8 tests

    # Test for CESU-8 sequences
    let ch = 0x10000
        for hichar = 0xd800:0xdbff, lochar = 0xdc00:0xdfff
            seq = string(Char(hichar), Char(lochar))
            # Normal conversion throws an error
            @test_throws StringError utf8(seq)
            # Unsafe conversions return invalid strings as Text*Str
            @test typeof(unsafe_str(seq)) == Text1Str
            # With accept_surrogates flag, return converted to valid string (_UTF32Str)
            @test unsafe_str(seq;accept_surrogates=true)[1]%UInt == ch
            ch += 1
        end
    end

end

@testset "Reverse of UTF8" begin
    # Reverse of UTF8Str
    @test reverse(UTF8Str("")) == ""
    @test reverse(UTF8Str("a")) == "a"
    @test reverse(UTF8Str("abc")) == "cba"
    @test reverse(UTF8Str("xyz\uff\u800\uffff\U10ffff")) == "\U10ffff\uffff\u800\uffzyx"
    for binstr in ([0xc1], [0xd0], [0xe0], [0xed, 0x80], [0xf0], [0xf0, 0x80], [0xf0, 0x80, 0x80])
        str = vcat(codeunits("xyz"), binstr)
        @test_throws StringError reverse(UTF8Str(str))
    end
end

# Specifically check UTF-8 string whose lead byte is same as a surrogate
@test convert(UTF8Str, [0xed, 0x9f, 0xbf]) == "\ud7ff"

# issue #8
@test !isempty(methods(string, Tuple{Char}))

@testset "Issue 12268" begin
# 12268
for (fun, S, T) in ((utf16, UInt16, UTF16Str), (utf32, UInt32, UTF32Str))
    # AbstractString
    str = "abcd\0\uff\u7ff\u7fff\U7ffff"
    tst = SubString(convert(T,str),4)
    cmp = Char['d','\0','\uff','\u7ff','\u7fff','\U7ffff']
    cmp32 = UInt32['d','\0','\uff','\u7ff','\u7fff','\U7ffff']
    cmp16 = UInt16[0x0064,0x0000,0x00ff,0x07ff,0x7fff,0xd9bf,0xdfff]
    x = fun(tst)
    cmpx = (S == UInt16 ? cmp16 : cmp32)
    @test typeof(tst) == SubString{T}
    @test convert(T, tst) == str[4:end]
    for (i, ch) in enumerate(cmp)
        @test ch == x[i]
    end
    # Vector{T} / Array{T}
    @test convert(Vector{S}, x) == cmpx
    #@test convert(Array{S}, x) == cmpx
    # Embedded nul checking
    @test Base.containsnul(x)
    @test Base.containsnul(tst)
    # map
    #@test_throws StringError map(islower, x)
    #@test_throws ArgumentError map(islower, tst)
    # SubArray conversion
    subarr = view(cmp, 1:6)
    @test convert(T, subarr) == str[4:end]
end
end

@test isvalid(UTF32Str, Char['d','\uff','\u7ff','\u7fff','\U7ffff'])
@test reverse(utf32("abcd \uff\u7ff\u7fff\U7ffff")) == utf32("\U7ffff\u7fff\u7ff\uff dcba")


text:
struct Policy
    p1::Int64
    p2::Int64
    letter::Char
    password::String
end

function readdata(line)
    interval, letter, passwd = replace(line, ":" => "") |> split
    a, b = map(x -> parse(Int64, x), split(interval, "-"))
    Policy(a, b, only(letter), passwd)
end

function is_valid(record)
    pwd = record.password
    xor(getindex(pwd, record.p1) == record.letter, getindex(pwd, record.p2) == record.letter)
end

function main()
    lines = readlines("../resources/input_02.txt")
    records = map(readdata, lines)
    result = foldl((acc, record) -> is_valid(record) ? acc + 1 : acc, records; init=0)
    println(result)
end

main()


text:
import BALL.STRUCTURE.breadthFirstSearch
using DataStructures

export BackpointingNode

"""
A specialization of [`SimpleMolecularGraph.Node`](@ref). Adds `Edge`s pointing back to the parent.
"""
mutable struct BackpointingNode <: AbstractNode
    adjacent_edges_ ::Vector{Edge}
    atom_           ::Union{Atom, DataFrameRow}
    parent_         ::BackpointingNode
    BackpointingNode(at::Union{Atom, DataFrameRow}) = (x = new(Edge[], at); x.parent_ = x)
end

"""
    collectPathToRoot(node::BackpointingNode) -> Vector{BackpointingNode}
Collects `BackpointingNode`s from `node` to the root of the tree `node` is in.
"""
collectPathToRoot(node::BackpointingNode) = begin
    path::Vector{BackpointingNode} = BackpointingNode[]
    cur::BackpointingNode = node
    while cur.parent_ != cur
        push!(path, cur)
        cur = cur.parent_
    end
    push!(path, cur)
    return path
end

partnerNodePredicate(edge::Edge, node::BackpointingNode)= begin
    ( (edge.source_ == node && edge.target_ == node.parent_) ||
        (edge.target_ == node && edge.source_ == node.parent_) )
end

"""
    collectBackpathEdges(path::Vector{BackpointingNode})
Collects the `Edge`s that connect the `BackpointingNode`s in `path`.
"""
collectBackpathEdges(path::Vector{BackpointingNode}) = begin
    #make sure path[1] contains a node whose parent you dont care about

    edge_path::Vector{Edge} = Edge[]
    for node in reverse(path[1:end-1])
        pos_in_vector = findfirst(x->partnerNodePredicate(x,node), node.adjacent_edges_)
        pushfirst!(edge_path, node.adjacent_edges_[pos_in_vector])
    end
    return edge_path
end

"""
    breadthFirstSearchMCB(graph::MolecularGraph, root::Node, deep::Bool=true)
A specialization of [`breadthFirstSearch`](@ref) of the [`minimum_cycle_basis`](@ref) algorithm.\n
It uses [`backpointingNode`](@ref)s and unless `deep` is `false` it will calculate a BFS of all
atoms in `graph`.
"""
breadthFirstSearchMCB(graph::MolecularGraph, root::T where T<:AbstractNode, deep::Bool=true) = begin
#iterating over a tree of node with type Node and making a bfs with nodetype BackpointingNode
    bfs = MolecularGraph(BackpointingNode)
    graph_node_type = typeof(getFirstNode(graph))
    q::Queue{graph_node_type} = Queue{graph_node_type}()
    visited_nodes::Set{graph_node_type} = Set{graph_node_type}()

    #init: the root node's parent is itself
    previous_bfs_node::BackpointingNode = newNode(bfs,root.atom_, BackpointingNode)
    temp::BackpointingNode = previous_bfs_node  #dummy initilization to keep temp alive through loop
    push!(visited_nodes, root)
    cur = root
    depth::Int64 = 0

    #do while loop
    while true
        for edge in eachPartnerEdge(cur)
            neighbour::Node = edge.source_ == cur ? edge.target_ : edge.source_
            if !(neighbour in visited_nodes)
                push!(visited_nodes, neighbour)
                enqueue!(q, neighbour)

                temp = newNode(bfs, neighbour.atom_, BackpointingNode)
                temp.parent_ = previous_bfs_node
                newEdge(bfs, edge.bond_)
            end
        end
        isempty(q) && break
        cur = dequeue!(q)
        previous_bfs_node = bfs.atoms_to_nodes_[cur.atom_]
        depth+=1
        if !deep && depth > BALL_HALF_OF_MAX_RING_SIZE
            break
        end
    end
    return bfs
end
breadthFirstSearch(graph::MolecularGraph, root::Node, BackpointingNode) = breadthFirstSearchMCB(graph,root)

"""
    minimum_cycle_basis(graph::MolecularGraph)
Finds the [Minimum Cycle Basis] of `graph` using [`Horton's Algorithm`](https://en.wikipedia.org/wiki/Cycle_basis#Polynomial_time_algorithms).
This algorithm is only correct for undirected Graphs with edgeweight equals 1 for all edges in the graph.
"""
minimum_cycle_basis(graph::MolecularGraph) = begin
    num_nodes = countNodes(graph)
    num_edges = countEdges(graph)

    mcb::Vector{Vector{Edge}} = Vector{Edge}[]
    tested_cycles::Set{Vector{Edge}} = Set{Edge}()

    #optimization: by constructing one big bfs with all the nodes, we can make the setdiff and find out
    #which edges are not in the bfs. Start horton's algo with these nodes, as these will be in a cycle
    bfs = breadthFirstSearchMCB(graph, first(values(graph.atoms_to_nodes_)),true)
    bfs_bonds =  Set([x.bond_ for x in eachEdge(bfs)])
    graph_bonds =  Set([x.bond_ for x in eachEdge(graph)])
    nodes_with_missing_edges = [graph.atoms_to_nodes_[getSource(bond)] for bond in setdiff(graph_bonds, bfs_bonds)]
    graph_nodes = filter(x->!in(x,nodes_with_missing_edges), collect(eachNode(graph)))
    graph_nodes = vcat(nodes_with_missing_edges, graph_nodes)
    i = 1
    #for node in graph_nodes
    for node in graph_nodes
        i += 1
        #only do a bfs of limited depth, as cycles can only have a limited number of atoms
        bfs = breadthFirstSearchMCB(graph, node,false)
        bfs_bonds =  Set([x.bond_ for x in eachEdge(bfs)])
        graph_bonds =  Set([x.bond_ for x in eachEdge(graph)])
        edges_not_in_bfs = [graph.bonds_to_edges_[x] for x in setdiff(graph_bonds, bfs_bonds)]
        #each edge that is not in the bfs will create a cycle if restored
        for edge in edges_not_in_bfs
            #create cycles and put them into mcb or prune them
            #let `edge` = (w,x). Make the cycle: Path(w to node) + Path(x to node) + (w,x)
            #but only if node is the lowest common ancestor of w,x

            w::BackpointingNode = bfs.atoms_to_nodes_[edge.source_.atom_]
            x::BackpointingNode = bfs.atoms_to_nodes_[edge.target_.atom_]
            w_nodes = collectPathToRoot(w)
            x_nodes = collectPathToRoot(x)
            #if node is not the lca then the 2nd-to-last node on the paths will be the same
            if w_nodes[end-1] == x_nodes[end-1]
                continue;
            end
            w_path = collectBackpathEdges(w_nodes)
            x_path = collect(reverse(collectBackpathEdges(x_nodes)))

            new_cycle = vcat(w_path, x_path, edge)
            (new_cycle in tested_cycles) && break
            push!(tested_cycles, new_cycle)

            #test if linearly independent
            for (i,cyc1) in enumerate(mcb)
                for cyc2 in mcb[i+1:end]
                    (new_cycle == symdiff(cyc1, cyc2)) && break
                end
            end

            pos_in_mcb = findfirst(x->length(x) > length(new_cycle), mcb)
            isnothing(pos_in_mcb) && (pos_in_mcb = 1)
            insert!(mcb, pos_in_mcb, new_cycle)

            if length(mcb) == num_edges - num_nodes +1
                return mcb
            end
        end
    end
end