text:
module QuComputStates

import QuBase: AbstractQuVector,AbstractFiniteBasis,FiniteBasis,Orthonormal,rawcoeffs,coefftype,rawbases,show,similar_type,bases
import Base: copy
export ComputState, CHPState, rawcoeffs, rawbases, AbstractQC, AbstractQuCircuit, ComputBasis, comput_basis, bases, BellState

abstract AbstractQC{N}
abstract AbstractQuCircuit{N} <: AbstractQC{N}

# general computing basis
typealias ComputBasis FiniteBasis{Orthonormal}
comput_basis(n::Int) = FiniteBasis(ntuple(x->2,n))

type ComputState{A<:AbstractVector,B<:AbstractFiniteBasis,T,N} <: AbstractQuVector{B,T}
    coeffs::A
    bases::B
end

# constructors
ComputState{A<:AbstractVector,B<:AbstractFiniteBasis}(state_vec::A,bases::B) = ComputState{A,B,eltype(A),length(state_vec)|>log2|>Int}(state_vec,bases)
ComputState{A<:AbstractVector}(state_vec::A) = ComputState{A,ComputBasis,eltype(A),length(state_vec)|>log2|>Int}(state_vec,state_vec|>length|>comput_basis)

# Hints
BellState(n::Int) = ComputState(Complex128[1/sqrt(2^n) for i=1:2^n],comput_basis(n))

# QuBase functions overload
coefftype{A,B,T,N}(state::ComputState{A,B,T,N}) = A
rawcoeffs(state::ComputState) = state.coeffs
rawbases(state::ComputState) = state.bases
rawbases(state::ComputState, i) = state.bases

# Base functions overload
copy(state::ComputState) = ComputState(copy(state.coeffs),copy(state.bases))
similar_type{Q<:ComputState}(::Type{Q}) = ComputState

# This file is for types in chp.c

type CHPState{N}<:AbstractQuVector{N}
    X::AbstractMatrix # (2n+1)*n matrix for stabilizer/destabilizer x bits
    Z::AbstractMatrix # (2n+1)*n matrix for z bits
    R::AbstractVector # phase bits: 0 for +1, 1 for i, 2 for -1, 3 for -i. Normally either 0 or 2
end

CHPState(X::BitMatrix,Z::BitMatrix,R::BitVector) = CHPState{length(R)/2}(X,Z,R)

function CHPState(n::Int)
    X = spzeros(Bool,2n,n)
    Z = spzeros(Bool,2n,n)
    R = spzeros(Bool,2n)

    X[1:n,:] = speye(n)
    Z[n+1:2n,:] = speye(n)

    return CHPState{n}(X,Z,R)
end

function copy!(A::CHPState,B::CHPState)
    copy!(A.X,B.X)
    copy!(A.Z,B.Z)
    copy!(A.R,B.R)

    return A
end

# Graph States

end # module


text:
module CategoricalAlgebra

include("ShapeDiagrams.jl")
include("FinSets.jl")
include("Permutations.jl")

end

ext: jl


text:
using BERT
using Knet
import Base: length, iterate
using Random
using CSV
using PyCall
using Dates

VOCABFILE = "bert-base-uncased-vocab.txt"
NUM_CLASSES = 2
LEARNING_RATE = 2e-5
NUM_OF_EPOCHS = 30
TRAIN = true

token2int = Dict()
f = open(VOCABFILE) do file
    lines = readlines(file)
    for (i,line) in enumerate(lines)
        token2int[line] = i
    end
end
int2token = Dict(value => key for (key, value) in token2int)
VOCABSIZE = length(token2int)

# include("preprocess.jl")
# include("optimizer.jl")

function convert_to_int_array(text, dict; lower_case=true)
    tokens = bert_tokenize(text, dict, lower_case=lower_case)
    out = Int[]
    for token in tokens
        if token in keys(dict)
            push!(out, dict[token])
        else
            push!(out, dict["[UNK]"])
        end
    end
    return out
end

function read_and_process(filename, dict; lower_case=true)
    data = CSV.File(filename, delim="\t")
    x = Array{Int,1}[]
    y = Int8[]
    for i in data
        push!(x, convert_to_int_array(i.sentence, dict, lower_case=lower_case))
        push!(y, Int8(i.label + 1)) # negative 1, positive 2
    end

    # Padding to maximum
#     max_seq = findmax(length.(x))[1]
#     for i in 1:length(x)
#         append!(x[i], fill(1, max_seq - length(x[i]))) # 1 is for "[PAD]"
#     end

    return (x, y)
end

mutable struct ClassificationData
    input_ids
    input_mask
    segment_ids
    labels
    batchsize
    ninstances
    shuffled
end

function ClassificationData(input_file, token2int; batchsize=8, shuffled=true, seq_len=64)
    input_ids = []
    input_mask = []
    segment_ids = []
    labels = []
    (x, labels) = read_and_process(input_file, token2int)
    for i in 1:length(x)
        if length(x[i]) >= seq_len
            x[i] = x[i][1:seq_len]
            mask = Array{Int64}(ones(seq_len))
        else
            mask = Array{Int64}(ones(length(x[i])))
            append!(x[i], fill(1, seq_len - length(x[i]))) # 1 is for "[PAD]"
            append!(mask, fill(0, seq_len - length(mask))) # 0's vanish with masking operation
        end
        push!(input_ids, x[i])
        push!(input_mask, mask)
        push!(segment_ids, Array{Int64}(ones(seq_len)))
    end
    ninstances = length(input_ids)
    return ClassificationData(input_ids, input_mask, segment_ids, labels, batchsize, ninstances, shuffled)
end

function length(d::ClassificationData)
    d, r = divrem(d.ninstances, d.batchsize)
    return r == 0 ? d : d+1
end

function iterate(d::ClassificationData, state=ifelse(d.shuffled, randperm(d.ninstances), 1:d.ninstances))

    state === nothing && return nothing

    if length(state) > d.batchsize
        new_state = state[d.batchsize+1:end]
        input_ids = hcat(d.input_ids[state[1:d.batchsize]]...)
        input_mask = hcat(d.input_mask[state[1:d.batchsize]]...)
        segment_ids = hcat(d.segment_ids[state[1:d.batchsize]]...)
        labels = hcat(d.labels[state[1:d.batchsize]]...)
    else
        new_state = nothing
        input_ids = hcat(d.input_ids[state]...)
        input_mask = hcat(d.input_mask[state]...)
        segment_ids = hcat(d.segment_ids[state]...)
        labels = hcat(d.labels[state]...)
    end

    return ((input_ids, input_mask, segment_ids, labels), new_state)
end

# mutable struct ClassificationData2
#     input_ids
#     input_mask
#     segment_ids
#     labels
#     batchsize
#     ninstances
#     shuffled
# end

# function ClassificationData2(input_file; batchsize=8, shuffled=true, seq_len=64)
#     input_ids = []
#     input_mask = []
#     segment_ids = []
#     labels = []
#     f = open(input_file)
#     tmp = split.(readlines(f), "\t")
#     for i in 1:length(tmp)
#         instance = eval.(Meta.parse.(tmp[i]))
#         push!(input_ids, (instance[1] .+ 1)[1:seq_len])
#         push!(input_mask, instance[2][1:seq_len])
#         push!(segment_ids, (instance[3] .+ 1)[1:seq_len])
#         push!(labels, (instance[4] + 1))
#     end
#     ninstances = length(input_ids)
#     return ClassificationData2(input_ids, input_mask, segment_ids, labels, batchsize, ninstances, shuffled)
# end

# function length(d::ClassificationData2)
#     d, r = divrem(d.ninstances, d.batchsize)
#     return r == 0 ? d : d+1
# end

# function iterate(d::ClassificationData2, state=ifelse(d.shuffled, randperm(d.ninstances), 1:d.ninstances))

#     state === nothing && return nothing

#     if length(state) > d.batchsize
#         new_state = state[d.batchsize+1:end]
#         input_ids = hcat(d.input_ids[state[1:d.batchsize]]...)
#         input_mask = hcat(d.input_mask[state[1:d.batchsize]]...)
#         segment_ids = hcat(d.segment_ids[state[1:d.batchsize]]...)
#         labels = hcat(d.labels[state[1:d.batchsize]]...)
#     else
#         new_state = nothing
#         input_ids = hcat(d.input_ids[state]...)
#         input_mask = hcat(d.input_mask[state]...)
#         segment_ids = hcat(d.segment_ids[state]...)
#         labels = hcat(d.labels[state]...)
#     end

#     return ((input_ids, input_mask, segment_ids, labels), new_state)
# end

# include("model.jl")

# Embedding Size, Vocab Size, Intermediate Hidden Size, Max Sequence Length, Sequence Length, Num of Segments, Num of Heads in Attention, Num of Encoders in Stack, Batch Size, Matrix Type, General Dropout Rate, Attention Dropout Rate, Activation Function
config = BertConfig(768, 30522, 3072, 512, 64, 2, 12, 12, 8, KnetArray{Float32}, 0.1, 0.1, "gelu")

if TRAIN
    dtrn = ClassificationData("../project/mytrain.tsv", token2int, batchsize=config.batchsize, seq_len=config.seq_len)
    ddev = ClassificationData("../project/dev.tsv", token2int, batchsize=config.batchsize, seq_len=config.seq_len)
else
    dtst = ClassificationData("../project/mytest.tsv", token2int, batchsize=config.batchsize, seq_len=config.seq_len)
end

if TRAIN
    model = BertClassification(config, NUM_CLASSES)

    @pyimport torch
    torch_model = torch.load("../project/pytorch_model.bin")

    model = load_from_torch_base(model, config.num_encoder, config.atype, torch_model)
end

function accuracy2(model, dtst)
    true_count = 0
    all_count = 0
    for (x, attention_mask, segment_ids, y) in dtst
        probs = model(x, segment_ids, attention_mask=attention_mask)
        preds = map(x -> x[1], argmax(Array{Float32}(probs),dims=1))
        true_count += sum(y .== preds)
        all_count += length(y)
    end
    return true_count/all_count
end

function initopt!(model, t_total; lr=0.001, warmup=0.1)
    for par in params(model)
        if length(size(value(par))) === 1
            par.opt = BertAdam(lr=lr, warmup=warmup, t_total=t_total, w_decay_rate=0.01)
        else
            par.opt = BertAdam(lr=lr, warmup=warmup, t_total=t_total)
        end
    end
end

function mytrain!(model, dtrn, ddev, best_acc)
    losses = []
    accs = []
    for (k, (x, attention_mask, segment_ids, labels)) in enumerate(dtrn)
        J = @diff model(x, segment_ids, labels, attention_mask=attention_mask)
        for par in params(model)
            g = grad(J, par)
            update!(value(par), g, par.opt)
        end
        push!(losses, value(J))
        if k % 500 == 0
            print(Dates.format(now(), "HH:MM:SS"), "  ->  ")
            println("Training loss up to $k iteration is : ", Knet.mean(losses))
            flush(stdout)
            acc = accuracy2(model, ddev)
            push!(accs, acc)
            print(Dates.format(now(), "HH:MM:SS"), "  ->  ")
            println("Accuracy at $k iteration : ", acc)
            flush(stdout)
            if acc > best_acc
                best_acc = acc
                print(Dates.format(now(), "HH:MM:SS"), "  ->  ")
                println("Saving...")
                Knet.save("model_bert.jld2", "model", model)
                flush(stdout)
            end
        end
    end
    return (best_acc, Knet.mean(losses), accs)
end

if TRAIN
    t_total = length(dtrn) * NUM_OF_EPOCHS
    initopt!(model, t_total, lr=LEARNING_RATE)

    dev_accs = [0.0]
    best_acc = 0.0
    for epoch in 1:NUM_OF_EPOCHS
        global best_acc
        print(Dates.format(now(), "HH:MM:SS"), "  ->  ")
        println("Epoch : ", epoch)
        flush(stdout)
        (best_acc, lss, acc) = mytrain!(model, dtrn, ddev, best_acc)
        append!(dev_accs, acc)
        print(Dates.format(now(), "HH:MM:SS"), "  ->  ")
        println("Training loss for $epoch epoch is : $lss")
        println(dev_accs)
        flush(stdout)
        #=
        acc = accuracy2(model, ddev)
        println("Accuracy : ", acc)
        if acc > best_acc
            best_acc = acc
            println("Saving...")
            Knet.save("model_bert.jld2", "model", model)
        end
        =#
    end

    Knet.save("accuracies.jld2", "dev_accs", dev_accs)
else
    model = Knet.load("model_bert.jld2", "model")
    result = accuracy2(model, dtst)
    print(Dates.format(now(), "HH:MM:SS"), "  ->  ")
    println("Test accuracy is : $result")
end

max_issues_repo_name: OsmanMutlu/BERT-in-Knet

max_forks_repo_name: OsmanMutlu/BERT-in-Knet


text:
abstract type AbstractVariable{T<:Real} end

"A parameter to vary, without bounds."
struct UnboundedVariable{T} <: AbstractVariable{T}
    value::T
end

struct BoundedVariable{T} <: AbstractVariable{T}
    value::T
    bounds::Tuple{T,T}
end

function BoundedVariable(value::T) where {T <: Real}
	ten_pct = value / 10
	BoundedVariable{T}(value, (value-ten_pct,value+ten_pct))
end

const MaybeVariable{T} = Union{T,AbstractVariable{T}}

Base.zero(::Type{<:MaybeVariable{T}}) where T <: Number = zero(T)
default_value(var::V) where V <: AbstractVariable = var.value
bounds(var::V) where V <: BoundedVariable = var.bounds

"""
    deconstruct(ad::AbstractDeconstructor, param)

Deconstruct a parameter into nested tuples of the form `(type,value)`.

```
    Parameter{Varying{T}} |> deconstruct |> reconstruct # isa Parameter{Varying{T}}
```
"""
function deconstruct(m::M, ad::AbstractDeconstructor=Deconstructor()) where {M <: AbstractParameter}
    deconstruction = Tuple{Type,Any}[]
    for i_field in 1:nfields(m)
        substruct = ad(getfield(m, i_field))
        push!(deconstruction, substruct)
    end
    return (typeof(m), deconstruction)
end

"""
	deconstruct(..., DeconstructorFixingVariables())

Deconstructs as normal (i.e. [Deconstructor](@ref)) except on [AbstractVariable](@ref) parameters, which are fixed to their default value.
"""
struct DeconstructorFixingVariables <: AbstractDeconstructor end

function deconstruct(val::AbstractVariable, ad::AbstractDeconstructor=Deconstructor())
    return (typeof(val), val)
end
function deconstruct(v::AbstractVariable, deconstructor::DeconstructorFixingVariables)
    val = default_value(v)
    return (typeof(val), val)
end

function base_type(::Type{P}) where {P <: AbstractParameter}
    BTs = map(base_type, P.parameters)
    return (P.name.wrapper){BTs...}
end

function base_type(::Type{V}) where {T, V<: Union{AbstractVariable{T}, T}}
    return T
end

struct VariableDeconstruction{OBJ} <: AbstractDeconstruction{OBJ}
    source::OBJ
    deconstruction::Tuple{Type,Array}
    dxs_map
    default_values
    bounds
end

function VariableDeconstruction(obj)
	dxs_map, default_values, bounds = variables(obj)
	deconstruction = deconstruct(obj, DeconstructorFixingVariables())
	VariableDeconstruction(obj, deconstruction, dxs_map, default_values, bounds)
end

"""Takes model with variable parameters,
and returns default variable values and indices to those variables."""
function variables(variable_parameter::P) where {T,
											P <: AbstractParameter{<:MaybeVariable{T}}}
    deconstructed = deconstruct(variable_model)
    default_value, dxs_map, bounds = variables(deconstructed, T)
    return dxs_map, default_value, bounds
end

"Initialize all variables to their default value."
function variables(deconstructed::Tuple{Type,<:AbstractArray}, T::Type)
    dxs_map = []
    default_values = T[]
    bounds = Tuple{T,T}[]
    for dx in CartesianIndices(size(deconstructed[2]))
        (typ, val) = deconstructed[2][dx]
        if typ <: AbstractVariable
            push!(dxs_map, [dx])
            push!(default_values, default_value(val))
            push!(bounds, bounds(val))
        elseif val isa AbstractArray
            dxs, ps, bds = variables((typ, val), T)
            @assert length(ps) == length(dxs)
            push!(dxs_map, [vcat(dx, x) for x in dxs]...)
            push!(default_values, ps...)
            push!(bounds, bds...)
        end
    end
    return dxs_map, default_values, bounds
end

function param_from_vec(var_deconstruction::VariableDeconstruction, values_vec)
    target = deepcopy(var_deconstruction.deconstruction)
	for (dxs, value) in zip(var_deconstruction.dxs_map, values_vec)
		set_deep_dx!(target, dxs, value)
	end
	reconstruct(target)
end

function param_from_vec(varying_param::AbstractParameter{MaybeVariable{T}}, values_vec) where T
    varying_param_deconstruction = VariableDeconstruction(varying_param)
    param_from_vec(varying_param_deconstruction, values_vec)
end


text:
using Distributed
@everywhere include_string(Main, $(read("count_heads.jl", String)), "count_heads.jl")

a = @spawn count_heads(100000000) # runs on an available processor
b = @spawn count_heads(100000000) # runs on another available processor

println(fetch(a)+fetch(b)) # total heads of 200 million coin flips, half on each CPU

max_stars_repo_name: ethansaxenian/RosettaDecode

max_issues_repo_name: ethansaxenian/RosettaDecode

max_forks_repo_name: ethansaxenian/RosettaDecode


text:
#=
day9:
- Julia version: 1.7.0
- Author: Paul.Mealor
- Date: 2021-12-09
=#

using AoC, Test

parseCaveMap(lines) = hcat([[parse(Int, c) for c in line] for line in lines]...)
@test parseCaveMap(["123","567"]) == [[1,2,3] [5,6,7]]

NEIGHBOURS=CartesianIndex.([(1,0),(-1,0),(0,-1),(0,1)])

getOrMax(A,I) = checkbounds(Bool,A,I) ? A[I] : typemax(eltype(A))
@test getOrMax([[1,2] [5,7]], CartesianIndex(1,1)) == 1
@test getOrMax([[1,2] [5,7]], CartesianIndex(2,1)) == 2
@test getOrMax([[1,2] [5,7]], CartesianIndex(1,2)) == 5
@test getOrMax([[1,2] [5,7]], CartesianIndex(2,2)) == 7
@test getOrMax([[1,2] [5,7]], CartesianIndex(0,1)) == typemax(Int)
@test getOrMax([[1,2] [5,7]], CartesianIndex(3,1)) == typemax(Int)

lowpointLocations(caveMap) = vcat(filter(CartesianIndices(caveMap)) do i
    h = caveMap[i]
    return all(getOrMax(caveMap, i+j) > h for j in NEIGHBOURS)
end...)
@test lowpointLocations(parseCaveMap(exampleLines(9,1))) == CartesianIndex.([(2,1),(10,1),(3,3),(7,5)])

lowpointHeights(caveMap) = caveMap[lowpointLocations(caveMap)]
@test lowpointHeights(parseCaveMap(exampleLines(9,1))) == [1,0,5,5]

part1(lines) = parseCaveMap(lines) |> lowpointHeights |> hh -> sum(h+1 for h in hh)
@test part1(exampleLines(9,1)) == 15

function findBasin(A, I, basin=Set())
    if I ∈ basin || !checkbounds(Bool, A, I) || A[I] >= 9
        return basin
    else
        basin = union(basin, [I])
        for J in [I+n for n in NEIGHBOURS]
            basin = findBasin(A, J, basin)
        end
        return basin
    end
end

basinSize(A, I) = length(findBasin(A, I))
@test basinSize(exampleLines(9,1) |> parseCaveMap, CartesianIndex((2,1))) == 3
@test basinSize(exampleLines(9,1) |> parseCaveMap, CartesianIndex((10,1))) == 9
@test basinSize(exampleLines(9,1) |> parseCaveMap, CartesianIndex((3,3))) == 14
@test basinSize(exampleLines(9,1) |> parseCaveMap, CartesianIndex((7,5))) == 9

function part2(lines)
    caveMap = parseCaveMap(lines)
    basinSizes = [basinSize(caveMap, I) for I in lowpointLocations(caveMap)]
    return *(sort(basinSizes; lt = >)[1:3]...)
end
@test part2(exampleLines(9,1)) == 1134

lines(9) |> ll -> @time part1(ll) |> show
lines(9) |> ll -> @time part2(ll) |> show


text:
using .Pairs

"""
    safer_joinpath(basepart, parts...)
A variation on `joinpath`, that is more resistant to directory traversal attacks.
The parts to be joined (excluding the `basepart`),
are not allowed to contain `..`, or begin with a `/`.
If they do then this throws an `DomainError`.
"""
function safer_joinpath(basepart, parts...)
    explain =  "Possible directory traversal attack detected."
    for part in parts
        occursin("..", part) && throw(DomainError(part, "contains \"..\". $explain"))
        startswith(part, '/') && throw(DomainError(part, "begins with \"/\". $explain"))
    end
    joinpath(basepart, parts...)
end

function try_get_filename_from_headers(hdrs)
    for content_disp in hdrs
        # extract out of Content-Disposition line
        # rough version of what is needed in https://github.com/JuliaWeb/HTTP.jl/issues/179
        filename_part = match(r"filename\s*=\s*(.*)", content_disp)
        if filename_part !== nothing
            filename = filename_part[1]
            quoted_filename = match(r"\"(.*)\"", filename)
            if quoted_filename !== nothing
                # It was in quotes, so it will be double escaped
                filename = unescape_string(quoted_filename[1])
            end
            return filename == "" ? nothing : filename
        end
    end
    return nothing
end

function try_get_filename_from_request(req)
    function file_from_target(t)
        t == "" && return nothing
        f = basename(URI(t).path) # URI(...).path to strip out e.g. query parts
        return (f == "" ? file_from_target(dirname(t)) : f)
    end

    # First try to get file from the original request URI
    oreq = req
    while oreq.parent !== nothing
        oreq = oreq.parent.request
    end
    f = file_from_target(oreq.target)
    f !== nothing && return f

    # Secondly try to get file from the last request URI
    return file_from_target(req.target)
end

determine_file(::Nothing, resp, hdrs) = determine_file(tempdir(), resp, hdrs)
# ^ We want to the filename if possible because extension is useful for FileIO.jl

function determine_file(path, resp, hdrs)
    # get the name
    name = if isdir(path)
        # we have been given a path to a directory
        # got to to workout what file to put there
        filename = something(
                        try_get_filename_from_headers(hdrs),
                        try_get_filename_from_request(resp.request),
                        basename(tempname())  # fallback, basically a random string
                    )
        safer_joinpath(path, filename)
    else
        # We have been given a full filepath
        path
    end

    # get the extension, if we are going to save it in encoded form.
    if header(resp, "Content-Encoding") == "gzip"
        name *= ".gz"
    end
    name
end

"""
    download(url, [local_path], [headers]; update_period=1, kw...)

Similar to `Base.download` this downloads a file, returning the filename.
If the `local_path`:
 - is not provided, then it is saved in a temporary directory
 - if part to a directory is provided then it is saved into that directory
 - otherwise the local path is uses as the filename to save to.

When saving into a directory, the filename is determined (where possible),
from the rules of the HTTP.

 - `update_period` controls how often (in seconds) to report the progress.
    - set to `Inf` to disable reporting
 - `headers` specifies headers to be used for the HTTP GET request
 - any additional keyword args (`kw...`) are passed on to the HTTP request.
"""
function download(url::AbstractString, local_path=nothing, headers=Header[]; update_period=1, kw...)
    format_progress(x) = round(x, digits=4)
    format_bytes(x) = !isfinite(x) ? "∞ B" : Base.format_bytes(round(Int, x))
    format_seconds(x) = "$(round(x; digits=2)) s"
    format_bytes_per_second(x) = format_bytes(x) * "/s"

    @debug 1 "downloading $url"
    local file
    hdrs = String[]
    HTTP.open("GET", url, headers; kw...) do stream
        resp = startread(stream)
        # Store intermediate header from redirects to use for filename detection
        content_disp = header(resp, "Content-Disposition")
        !isempty(content_disp) && push!(hdrs, content_disp)
        eof(stream) && return  # don't do anything for streams we can't read (yet)

        file = determine_file(local_path, resp, hdrs)
        total_bytes = parse(Float64, header(resp, "Content-Length", "NaN"))
        downloaded_bytes = 0
        start_time = now()
        prev_time = now()

        function report_callback()
            prev_time = now()
            taken_time = (prev_time - start_time).value / 1000 # in seconds
            average_speed = downloaded_bytes / taken_time
            remaining_bytes = total_bytes - downloaded_bytes
            remaining_time = remaining_bytes / average_speed
            completion_progress = downloaded_bytes / total_bytes

            @info("Downloading",
                  source=url,
                  dest = file,
                  progress = completion_progress |> format_progress,
                  time_taken = taken_time |> format_seconds,
                  time_remaining = remaining_time |> format_seconds,
                  average_speed = average_speed |> format_bytes_per_second,
                  downloaded = downloaded_bytes |> format_bytes,
                  remaining = remaining_bytes |> format_bytes,
                  total = total_bytes |> format_bytes,
                 )
        end

        Base.open(file, "w") do fh
            while(!eof(stream))
                downloaded_bytes += write(fh, readavailable(stream))
                if !isinf(update_period)
                    if now() - prev_time > Millisecond(round(1000update_period))
                        report_callback()
                    end
                end
            end
        end
        if !isinf(update_period)
            report_callback()
        end
    end
    file
end


text:
aschannel(input::Channel, _) = input
function aschannel(input, size)
    if Base.IteratorEltype(input) isa Base.HasEltype
        T = eltype(input)
    else
        T = Any
    end
    return _Channel(T, size) do ch
        for x in input
            put!(ch, x)
        end
    end
end

maybe_popfirst!(input::AbstractChannel) =
    try
        Some(take!(input))
    catch err
        if isa(err, InvalidStateException) && err.state === :closed
            nothing
        else
            rethrow()
        end
    end

# This function assumes that `tasks` does not grow.
function _unsafe_sync_end(tasks)
    exceptions = []
    for t in tasks
        try
            wait(t)
        catch err
            push!(exceptions, err)
        end
    end
    if !isempty(exceptions)
        throw(CompositeException(exceptions))
    end
end

if VERSION < v"1.5-"
    const sync_end = Base.sync_end
else
    const sync_end = _unsafe_sync_end
end

function transduce_commutative!(
    xform::Transducer,
    step,
    init,
    input;
    simd::SIMDFlag = Val(false),
    ntasks::Integer = Threads.nthreads(),
    basesize::Integer = 1,
)
    @argcheck ntasks > 0
    @argcheck basesize > 0
    rf = reducingfunction(xform, step; simd = simd)
    stop = Threads.Atomic{Bool}(false)
    tasks = map(1:ntasks) do _
        @spawn try
            acc′ = start(rf, init)
            finished = false
            while !finished
                acc′, finished = let acc′′ = acc′
                    @spawn begin
                        acc = acc′′
                        for _ in 1:basesize
                            x = maybe_popfirst!(input)
                            x === nothing && return acc, true
                            acc = next(rf, acc, something(x))
                            if isreduced(acc)
                                stop[] = true
                                return acc, true
                            end
                        end
                        return acc, false
                    end
                end |> fetch
                finished |= stop[]
            end
            return acc′
        catch
            stop[] = true
            rethrow()
        end
    end
    sync_end(tasks)
    return foldl(combine_step(rf), Map(fetch), tasks)
end

reduce_commutative!(step, xform::Transducer, itr; init = DefaultInit, kwargs...) =
    unreduced(transduce_commutative!(xform, Completing(step), init, itr; kwargs...))

reduce_commutative(
    step,
    xform::Transducer,
    itr;
    ntasks::Integer = Threads.nthreads(),
    basesize::Integer = 1,
    kwargs...,
) = reduce_commutative!(
    step,
    xform,
    aschannel(itr, ntasks * basesize);
    ntasks = ntasks,
    basesize = basesize,
    kwargs...,
)

function _push!(output, x)
    push!(output, x)
    return output
end

_push!(output) = output  # complete
function combine(::typeof(_push!), a, b)
    @assert a === b
    return a
end

"""
    append_unordered!(output, xf, input; ntasks, basesize)
    append_unordered!(output, itr; ntasks, basesize)

Process `input` elements through a transducer `xf` and then `push!` them
into `output` in undefined order.

Binary method `append_unordered!(output, itr)` is like
`append!(output, itr)` but without order guarantee.  Iterator
comprehensions and [`eduction`](@ref)s can be passed as the input
`itr`.

`output` (typically a `Channel`) must implement thread-safe
`push!(output, x)` method.

See also [`channel_unordered`](@ref).

!!! compat "Transducers.jl 0.4.8"

    New in version 0.4.8.

!!! compat "Transducers.jl 0.4.9"

    Binary method `append_unordered!(output, itr)` requires Transducers.jl 0.4.9.

$_experimental_warning

# Examples
```jldoctest
julia> using Transducers: Map, append_unordered!

julia> input = Channel(Map(identity), 1:3);

julia> output = Channel{Int}(0);

julia> task = @async try
           append_unordered!(output, Map(x -> x + 1), input)
       finally
           close(output)
       end;

julia> sort!(collect(output))
3-element Array{Int64,1}:
 2
 3
 4

julia> input = Channel(Map(identity), 1:3);

julia> output = Channel{Int}(0);

julia> task = @async try
           append_unordered!(output, (y for x in input if isodd(x) for y in 1:x))
       finally
           close(output)
       end;

julia> sort!(collect(output))
4-element Array{Int64,1}:
 1
 1
 2
 3
```
"""
function append_unordered!(
    output,
    xf,
    input;
    ntasks::Integer = Threads.nthreads(),
    basesize::Integer = 1,
    kwargs...,
)
    transduce_commutative!(
        xf,
        _push!,
        output,
        aschannel(input, ntasks * basesize);
        ntasks = ntasks,
        basesize = basesize,
        kwargs...,
    )
    return output
end
# Strictly speaking, this invocation of `transduce_commutative!` does
# not make sense as `_push!` is not even a magma/groupoid (let alone a
# commutative monoid).  It should really be written as (roughly
# speaking)
#
#     xf′ = xf |> Map(x -> [x])
#     step(a, b) = foldl(_push!, b; init=a)
#     transduce_commutative!(xf′, step, input; init = channel)
#
# "Fusing" the `Map` and `step` yields the invocation of
# `transduce_commutative!` in `append_unordered!`.

append_unordered!(output, itr; kwargs...) =
    append_unordered!(output, extract_transducer(itr)...; kwargs...)

"""
    channel_unordered(xf, input; eltype, size, ntasks, basesize) :: Channel{eltype}
    channel_unordered(itr; eltype, size, ntasks, basesize) :: Channel{eltype}

Provide elements in `input` processed by a transducer `xf` through a
`Channel`.

Unary method `channel_unordered(itr)` produces a `Channel` that
provides elements in the input iterator `itr` with possibly different
order.  Iterator comprehensions and [`eduction`](@ref)s can be passed
as the input `itr`.

Use [`append_unordered!`](@ref) to send outputs to an existing channel.

!!! compat "Transducers.jl 0.4.8"

    New in version 0.4.8.

!!! compat "Transducers.jl 0.4.9"

    Unary method `channel_unordered(itr)` requires Transducers.jl 0.4.9.

$_experimental_warning

# Keyword Arguments
- `eltype::Type`: element type of returned channel
- `size`: The size of `Channel`. A non-negative `Int` or `Inf`.
- `ntasks::Int`: Number of concurrent tasks.  Default to
  `Threads.nthreads()`.
- `basesize`: The "batch size" of the processing; i.e., the number of
  elements to be processed in a single task.  Default to 1.

# Examples
```jldoctest
julia> using Transducers: Map, channel_unordered

julia> sort!(collect(channel_unordered(Map(x -> x + 1), 1:3)))
3-element Array{Any,1}:
 2
 3
 4

julia> sort!(collect(channel_unordered(x + 1 for x in 1:3 if isodd(x))))
2-element Array{Any,1}:
 2
 4
```
"""
channel_unordered(xf, input; eltype=Any, size=Inf, kwargs...) =
    _Channel(eltype, size) do output
        append_unordered!(output, xf, input; kwargs...)
        return
    end

channel_unordered(itr; kwargs...) =
    channel_unordered(extract_transducer(itr)...; kwargs...)


text:
if VERSION >= v"0.5-"
    using Base.Test
else
    using BaseTestNext
    const Test = BaseTestNext
end

@testset "widgets.jl" begin
    include("widgets.jl")
end

@testset "ijulia.jl" begin
    include("ijulia.jl")
end


text:
ZXDiagram(bir::BlockIR) = convert_to_zxd(bir)
Chain(zxd::ZXDiagram) = convert_to_chain(zxd)

convert_to_gate(::Val{:X}, loc) = Gate(X, Locations(loc))
convert_to_gate(::Val{:Z}, loc) = Gate(Z, Locations(loc))
convert_to_gate(::Val{:H}, loc) = Gate(H, Locations(loc))
convert_to_gate(::Val{:S}, loc) = Gate(S, Locations(loc))
convert_to_gate(::Val{:Sdag}, loc) = Gate(AdjointOperation(S), Locations(loc))
convert_to_gate(::Val{:T}, loc) =  Gate(T, Locations(loc))
convert_to_gate(::Val{:Tdag}, loc) = Gate(AdjointOperation(S), Locations(loc))
convert_to_gate(::Val{:SWAP}, loc1, loc2) = Gate(SWAP, Locations((loc1, loc2)))
convert_to_gate(::Val{:CNOT}, loc, ctrl) = Ctrl(Gate(X, Locations(loc)), CtrlLocations(ctrl))
convert_to_gate(::Val{:CZ}, loc, ctrl) = Ctrl(Gate(Z, Locations(loc)), CtrlLocations(ctrl))
function convert_to_gate(::Val{:Rz}, loc, theta)
    if theta isa Phase
        theta = theta * π
        theta = theta.ex
    end
    return Gate(Rz(theta), Locations(loc))
end
function convert_to_gate(::Val{:Rx}, loc, theta)
    if theta isa Phase
        theta = theta * π
        theta = theta.ex
    end
    return Gate(Rx(theta), Locations(loc))
end
function convert_to_gate(::Val{:shift}, loc, theta)
    if theta isa Phase
        theta = theta * π
        theta = theta.ex
    end
    return Gate(shift(theta), Locations(loc))
end

function push_gate!(circ::Chain, gargs...)
    push!(circ.args, convert_to_gate(gargs...))
    return circ
end
function pushfirst_gate!(circ::Chain, gargs...)
    pushfirst!(circ.args, convert_to_gate(gargs...))
    return circ
end

function unwrap_ssa_phase(theta, ir::Core.Compiler.IRCode)
    if theta isa Core.SSAValue
        return Phase(theta, ir.stmts[theta.id][:type])
    elseif theta isa QuoteNode
        return theta.value
    elseif theta isa Core.Const
        return theta.val
    elseif theta isa Number
        return theta
    else
        error("expect SSAValue or Number")
    end
end

function canonicalize_single_location(ir::YaoHIR.Chain)
    Chain(map(canonicalize_single_location, ir.args)...)
end

function canonicalize_single_location(node::YaoHIR.Ctrl)
    if node.ctrl isa CtrlLocations && length(node.ctrl) == 1
        ctrl = CtrlLocations(node.ctrl.storage[1], node.ctrl.flags)
    else
        ctrl = node.ctrl
    end
    return YaoHIR.Ctrl(canonicalize_single_location(node.gate), node.ctrl)
end

function canonicalize_single_location(node::YaoHIR.Gate)
    length(node.locations) == 1 || return node
    return YaoHIR.Gate(node.operation, node.locations[1])
end

function convert_to_zxd(root::YaoHIR.BlockIR)
    circ = ZXDiagram(root.nqubits)

    circuit = canonicalize_single_location(root.circuit)
    for gate in YaoHIR.leaves(circuit)
        @switch gate begin
            @case Gate(&Z, loc::Locations{Int})
                push_gate!(circ, Val(:Z), plain(loc), 1//1)
            @case Gate(&X, loc::Locations{Int})
                push_gate!(circ, Val(:X), plain(loc), 1//1)
            @case Gate(&H, loc::Locations{Int})
                push_gate!(circ, Val(:H), plain(loc))
            @case Gate(&S, loc::Locations{Int})
                push_gate!(circ, Val(:Z), plain(loc), 1//2)
            @case Gate(&T, loc::Locations{Int})
                push_gate!(circ, Val(:Z), plain(loc), 1//4)
            @case Gate(shift(theta), loc::Locations{Int})
                theta = unwrap_ssa_phase(theta, root.parent)
                push_gate!(circ, Val(:Z), plain(loc), (1/π)*theta)
            @case Gate(Rx(theta), loc::Locations{Int})
                theta = unwrap_ssa_phase(theta, root.parent)
                push_gate!(circ, Val(:X), plain(loc), (1/π)*theta)
            @case Gate(Ry(theta), loc::Locations{Int})
                theta = unwrap_ssa_phase(theta, root.parent)
                push_gate!(circ, Val(:X), plain(loc),  1//2)
                push_gate!(circ, Val(:Z), plain(loc),  (1/π) * theta)
                push_gate!(circ, Val(:X), plain(loc), -1//2)
            @case Gate(Rz(theta), loc::Locations{Int})
                theta = unwrap_ssa_phase(theta, root.parent)
                push_gate!(circ, Val(:Z), plain(loc), (1/π)*theta)
            @case Gate(AdjointOperation(&S), loc::Locations{Int})
                push_gate!(circ, Val(:Z), plain(loc), 3//2)
            @case Gate(AdjointOperation(&T), loc::Locations{Int})
                push_gate!(circ, Val(:Z), plain(loc), 7//4)
            @case Ctrl(Gate(&X, loc::Locations), ctrl::CtrlLocations) # CNOT
                if length(loc) == 1 && length(ctrl) == 1
                    push_gate!(circ, Val(:CNOT), plain(loc)[1], plain(ctrl)[1])
                else
                    error("Multi qubits controlled gates are not supported")
                end
            @case Ctrl(Gate(&Z, loc::Locations), ctrl::CtrlLocations) # CZ
                if length(loc) == 1 && length(ctrl) == 1
                    push_gate!(circ, Val(:CZ), plain(loc)[1], plain(ctrl)[1])
                else
                    error("Multi qubits controlled gates are not supported")
                end
            @case _
                error("$gate is not supported")
        end
    end
    return circ
end

function convert_to_chain(circ::ZXDiagram{TT, P}) where {TT, P}
    spider_seq = spider_sequence(circ)
    qc = []
    for vs in spider_seq
        if length(vs) == 1
            v = vs
            q = Int(qubit_loc(circ, v))
            push_spider_to_chain!(qc, q, phase(circ, v), spider_type(circ, v))
        elseif length(vs) == 2
            v1, v2 = vs
            q1 = Int(qubit_loc(circ, v1))
            q2 = Int(qubit_loc(circ, v2))
            push_spider_to_chain!(qc, q1, phase(circ, v1), spider_type(circ, v1))
            push_spider_to_chain!(qc, q2, phase(circ, v2), spider_type(circ, v2))
            if spider_type(circ, v1) == SpiderType.Z && spider_type(circ, v2) == SpiderType.X
                push!(qc, Ctrl(Gate(X, Locations(q2)), CtrlLocations(q1)))
            elseif spider_type(circ, v1) == SpiderType.X && spider_type(circ, v2) == SpiderType.Z
                push!(qc, Ctrl(Gate(X, Locations(q1)), CtrlLocations(q2)))
            else
                error("Spiders ($v1, $v2) should represent a CNOT")
            end
        elseif length(vs) == 3
            v1, h, v2 = vs
            spider_type(circ, h) == SpiderType.H || error("The spider $h should be a H-box")
            q1 = Int(qubit_loc(circ, v1))
            q2 = Int(qubit_loc(circ, v2))
            push_spider_to_chain!(qc, q1, phase(circ, v1), spider_type(circ, v1))
            push_spider_to_chain!(qc, q2, phase(circ, v2), spider_type(circ, v2))
            if spider_type(circ, v1) == SpiderType.Z && spider_type(circ, v2) == SpiderType.Z
                push!(qc, Ctrl(Gate(Z, Locations(q2)), CtrlLocations(q1)))
            else
                error("Spiders ($v1, $h, $v2) should represent a CZ")
            end
        else
            error("ZXDiagram's without circuit structure are not supported")
        end
    end
    return Chain(qc...)
end

function push_spider_to_chain!(qc, q, ps, st)
    if ps != 0
        if st == SpiderType.Z
            if ps == 1
                push!(qc, Gate(Z, Locations(q)))
            elseif ps == 1//2
                push!(qc, Gate(S, Locations(q)))
            elseif ps == 3//2
                push!(qc, Gate(AdjointOperation(S), Locations(q)))
            elseif ps == 1//4
                push!(qc, Gate(T, Locations(q)))
            elseif ps == 7//4
                push!(qc, Gate(AdjointOperation(T), Locations(q)))
            elseif ps != 0
                θ = ps * π
                if θ isa Phase
                    θ = θ.ex
                end
                push!(qc, Gate(shift(θ), Locations(q)))
            end
        elseif st == SpiderType.X
            if ps == 1
                push!(qc, Gate(X, Locations(q)))
            else ps != 0
                θ = ps * π
                if θ isa Phase
                    θ = θ.ex
                end
                push!(qc, Gate(Rx(θ), Locations(q)))
            end
        elseif st == SpiderType.H
            push!(qc, Gate(H, Locations(q)))
        end
    end
end


text:
@benchset "finite" begin
    @benchset "FiniteMean" begin
        for N in Ns()
            μ = FiniteMean(CustomMean(sin), randn(N))
            @benchset(
                "CustomMean(sin) $N",
                create_benchmarks(μ; grads=false, x=1, x̄s=[1:N-1, 1:N,]),
            )
        end
    end
    @benchset "FiniteKernel" begin
        for N in Ns()
            k = FiniteKernel(EQ(), randn(N))
            @benchset(
                "EQ() $N",
                create_benchmarks(k; grads=false, x=1, x′=2, x̄s=[1:N,], x̄′s=[1:N,]),
            )
        end
    end
    @benchset "LhsFiniteCrossKernel" begin
        for N in Ns()
            k = LhsFiniteCrossKernel(EQ(), randn(N))
            @benchset(
                "EQ() $N",
                create_benchmarks(k; grads=false, x=1, x′=2.0, x̄s=[1:N,], x̄′s=[randn(N),]),
            )
        end
    end
    @benchset "RhsFiniteCrossKernel" begin
        for N in Ns()
            k = RhsFiniteCrossKernel(EQ(), randn(N))
            @benchset(
                "EQ() $N",
                create_benchmarks(k; grads=false, x=1.0, x′=2, x̄s=[randn(N),], x̄′s=[1:N,]),
            )
        end
    end
    @benchset "FiniteCrossKernel" begin
        for N in Ns()
            k = FiniteCrossKernel(EQ(), randn(N), randn(N))
            @benchset(
                "EQ() $N",
                create_benchmarks(k; grads=false, x=1, x′=2, x̄s=[1:N,], x̄′s=[1:N,]),
            )
        end
    end
end


text:
module Units
  export AbstractPipelineUnit,
    AbstractSentenceSplitter,
    AbstractTokenizer,
    AbstractPOSTagger,
    AbstractDepParser

  abstract type AbstractPipelineUnit end;

  abstract type AbstractSentenceSplitter <: AbstractPipelineUnit end
  abstract type AbstractTokenizer <: AbstractPipelineUnit end;
  abstract type AbstractPOSTagger <: AbstractPipelineUnit end;
  abstract type AbstractDepParser <: AbstractPipelineUnit end;
end

max_stars_repo_name: LarsWl/DependencyParser

max_issues_repo_name: LarsWl/DependencyParser

max_forks_repo_name: LarsWl/DependencyParser


text:
module CompilerPluginTools

using MLStyle
using Expronicon

export
    # interp
    NewCodeInfo,
    NewSlotNumber,
    JuliaLikeInterpreter,
    AbstractInterpreter,
    isintrinsic,
    # reexport SSA nodes from Core
    MethodInstance,
    CodeInfo,
    SSAValue,
    Const,
    PartialStruct,
    Slot,
    GotoIfNot,
    GotoNode,
    SlotNumber,
    Argument,
    NewvarNode,
    ReturnNode,
    InferenceState,
    InferenceParams,
    MethodResultPure,
    CallMeta,
    widenconst,
    argtypes_to_type,
    # reexport IRCode types from Core
    NativeInterpreter,
    IRCode,
    IncrementalCompact,
    NewSSAValue,
    obtain_codeinfo,
    obtain_const,
    obtain_const_or_stmt,
    isconstType,
    compact!,
    # reflections
    code_ircode,
    code_ircode_by_mi,
    code_ircode_by_signature,
    method_instances,
    # builtin pass
    default_julia_pass,
    no_pass,
    # extra pass
    inline_const!,
    permute_stmts!,
    const_invoke!,
    contains_const_invoke,
    finish,
    IntrinsicError,
    # utils
    method_instance,
    @make_codeinfo,
    @make_ircode,
    @test_codeinfo,
    @intrinsic_stub

using Base:
    method_instances

using Base.Meta: ParseError

using Core:
    CodeInfo,
    SSAValue,
    Const,
    PartialStruct,
    Slot,
    GotoIfNot,
    GotoNode,
    SlotNumber,
    Argument,
    NewvarNode,
    ReturnNode,
    IntrinsicFunction,
    Builtin

using Core.Compiler:
    MethodInstance,
    InferenceParams,
    InferenceResult,
    OptimizationParams,
    OptimizationState,
    Bottom,
    AbstractInterpreter,
    NativeInterpreter,
    VarTable,
    InferenceState,
    CFG,
    NewSSAValue,
    Signature,
    IRCode,
    InstructionStream,
    CallMeta,
    IncrementalCompact,
    JLOptions

using Core.Compiler:
    get_world_counter,
    get_inference_cache,
    # typeinf interfaces
    typeinf,
    # optimization interfaces
    run_passes,
    may_optimize,
    isconstType,
    isconcretetype,
    widenconst,
    isdispatchtuple,
    is_inlineable_constant,
    copy_exprargs,
    convert_to_ircode,
    coverage_enabled,
    argtypes_to_type,
    userefs,
    UseRefIterator,
    UseRef,
    MethodResultPure,
    is_pure_intrinsic_infer,
    intrinsic_nothrow,
    quoted,
    # Julia passes
    compact!,
    ssa_inlining_pass!,
    adce_pass!,
    type_lift_pass!,
    verify_linetable,
    verify_ir,
    retrieve_code_info,
    slot2reg

include("compat.jl")
include("utils.jl")
include("patches.jl")
include("codeinfo.jl")
include("interp.jl")
include("typeinf.jl")
include("ircode.jl")
include("passes.jl")
include("intrinsic.jl")

end


text:
function ueberpruefef_nahfehler(f_nahfehler,A,MesswerteMitFehler,p)
mr = MesswerteMitFehler;

if almostequal(f_nahfehler(MesswerteMitFehler), (transpose(A)*A+p*I)\(transpose(A)*MesswerteMitFehler))
    println("Eure Formel für das nächste Objekt am Original ist korrekt!");
else
    println("Eure Formel für f_nahfehler ist noch nicht korrekt. Überprüft erneut eure Umformungen und nehmt eine Hilfekarte zur Hilfe.")
end

end


text:
using AWSSDK.Batch: describe_compute_environments

struct ComputeEnvironment
    arn::String

    function ComputeEnvironment(ce::AbstractString)
        arn = compute_environment_arn(ce)
        arn === nothing && error("No compute environment ARN found for $ce")
        new(arn)
    end
end

Base.:(==)(a::ComputeEnvironment, b::ComputeEnvironment) = a.arn == b.arn

describe(ce::ComputeEnvironment) = describe_compute_environment(ce)
max_vcpus(ce::ComputeEnvironment) = describe(ce)["computeResources"]["maxvCpus"]

function compute_environment_arn(ce::AbstractString)
    startswith(ce, "arn:") && return ce
    json = describe_compute_environment(ce)
    isempty(json) ? nothing : json["computeEnvironmentArn"]
end

describe_compute_environment(ce::ComputeEnvironment) = describe_compute_environment(ce.arn)

function describe_compute_environment(ce::AbstractString)::OrderedDict
    json = @mock describe_compute_environments(Dict("computeEnvironments" => [ce]))
    envs = json["computeEnvironments"]
    len = length(envs)::Int
    @assert len <= 1
    return len == 1 ? first(envs) : OrderedDict()
end


text:
using HMCExamples

HMCExamples.main_FVGQ_1_kalman()


text:
"""
    UnstructuredQuadMesh{RealT<:Real} <: AbstractMesh{2}

An unstructured (possibly curved) quadrilateral mesh.

    UnstructuredQuadMesh(filename, periodic; RealT=Float64)

All mesh information, neighbour coupling, and boundary curve information is read in
from a mesh file `filename`.

!!! warning "Experimental code"
    This mesh type is experimental and can change any time.
"""
struct UnstructuredQuadMesh{RealT<:Real, CurvedSurfaceT<:CurvedSurface{RealT}} <: AbstractMesh{2}
  filename             ::String
  n_corners            ::Int
  n_surfaces           ::Int # total number of surfaces
  n_interfaces         ::Int # number of interior surfaces
  n_boundaries         ::Int # number of surfaces on the physical boundary
  n_elements           ::Int
  polydeg              ::Int
  corners              ::Array{RealT, 2}  # [ndims, n_corners]
  neighbour_information::Array{Int, 2}  # [neighbour node/element/edge ids, n_surfaces]
  boundary_names       ::Array{String, 2} # [local sides, n_elements]
  periodicity          ::Bool
  element_node_ids     ::Array{Int, 2} # [node ids, n_elements]
  element_is_curved    ::Vector{Bool}
  surface_curves       ::Array{CurvedSurfaceT, 2} # [local sides, n_elements]
end

# constructor for an unstructured mesh read in from a file
# TODO: this mesh file parsing and construction of the mesh skeleton can likely be improved in terms
#       of performance
function UnstructuredQuadMesh(filename, periodic; RealT=Float64)

  # readin all the information from the mesh file into a string array
  file_lines = readlines(open(filename))

  # readin the number of nodes, number of interfaces, number of elements and local polynomial degree
  current_line = split(file_lines[1])
  n_corners    = parse(Int, current_line[1])
  n_surfaces   = parse(Int, current_line[2])
  n_elements   = parse(Int, current_line[3])
  mesh_polydeg = parse(Int, current_line[4])

  mesh_nnodes = mesh_polydeg + 1

  # The types of structs used in the following depend on information read from
  # the mesh file. Thus, this cannot be type stable at all. Hence, we allocate
  # the memory now and introduce a function barrier before continuing to read
  # data from the file.
  corner_nodes      = Array{RealT}(undef, (2, n_corners))
  interface_info    = Array{Int}(undef, (6, n_surfaces))
  element_node_ids  = Array{Int}(undef, (4, n_elements))
  curved_check      = Vector{Int}(undef, 4)
  cornerNodeVals    = Array{RealT}(undef, (4, 2))
  tempNodes         = Array{RealT}(undef, (4, 2))
  curve_vals        = Array{RealT}(undef, (mesh_nnodes, 2))
  element_is_curved = Array{Bool}(undef, n_elements)
  CurvedSurfaceT    = CurvedSurface{RealT}
  surface_curves    = Array{CurvedSurfaceT}(undef, (4, n_elements))
  bndy_names        = Array{String}(undef, (4, n_elements))

  # create the Chebyshev-Gauss-Lobatto nodes used to represent any curved boundaries that are
  # required to construct the sides
  cheby_nodes_, _ = chebyshev_gauss_lobatto_nodes_weights(mesh_nnodes)
  bary_weights_   = barycentric_weights(cheby_nodes_)
  cheby_nodes  = SVector{mesh_nnodes}(cheby_nodes_)
  bary_weights = SVector{mesh_nnodes}(bary_weights_)

  arrays = (; corner_nodes, interface_info, element_node_ids, curved_check,
              cornerNodeVals, tempNodes, curve_vals,
              element_is_curved, surface_curves, bndy_names)
  counters = (; n_corners, n_surfaces, n_elements)

  n_boundaries = parse_mesh_file!(arrays, RealT, CurvedSurfaceT, file_lines, counters, cheby_nodes, bary_weights)

  # get the number of internal interfaces in the mesh
  if periodic
    n_interfaces = n_surfaces
  else
    n_interfaces = n_surfaces - n_boundaries
  end

  return UnstructuredQuadMesh{RealT, CurvedSurfaceT}(
    filename, n_corners, n_surfaces, n_interfaces, n_boundaries,
    n_elements, mesh_polydeg, corner_nodes,
    interface_info, bndy_names, periodic,
    element_node_ids, element_is_curved, surface_curves)
end

function parse_mesh_file!(arrays, RealT, CurvedSurfaceT, file_lines, counters, cheby_nodes, bary_weights)
  @unpack ( corner_nodes, interface_info, element_node_ids, curved_check,
            cornerNodeVals, tempNodes, curve_vals,
            element_is_curved, surface_curves, bndy_names ) = arrays
  @unpack n_corners, n_surfaces, n_elements = counters
  mesh_nnodes = length(cheby_nodes)

  # counter to step through the mesh file line by line
  file_idx = 2

  # readin an store the nodes that dictate the corners of the elements needed to construct the
  # element geometry terms
  for j in 1:n_corners
    current_line       = split(file_lines[file_idx])
    corner_nodes[1, j] = parse(RealT, current_line[1])
    corner_nodes[2, j] = parse(RealT, current_line[2])
    file_idx += 1
  end

  # readin an store the nodes that dictate the interfaces, neighbour data, and orientations contains
  # the following:
  #    interface_info[1] = start node ID
  #    interface_info[2] = end node ID
  #    interface_info[3] = ID of the primary element
  #    interface_info[4] = ID of the secondary element (if 0 then it is a physical boundary)
  #    interface_info[5] = local side ID on the primary element
  #    interface_info[6] = local side ID on the secondary element
  # container to for the interface neighbour information and connectivity
  n_boundaries = 0
  for j in 1:n_surfaces
    current_line   = split(file_lines[file_idx])
    interface_info[1, j] = parse(Int, current_line[1])
    interface_info[2, j] = parse(Int, current_line[2])
    interface_info[3, j] = parse(Int, current_line[3])
    interface_info[4, j] = parse(Int, current_line[4])
    interface_info[5, j] = parse(Int, current_line[5])
    interface_info[6, j] = parse(Int, current_line[6])

    # count the number of physical boundaries
    if interface_info[4,j] == 0
      n_boundaries += 1
    end
    file_idx += 1
  end

  # work arrays to pull to correct corners of a given element (agnostic to curvature) and local
  # copies of the curved boundary information

  # readin an store the curved boundary information of the elements

  for j in 1:n_elements
    # pull the corner node IDs
    current_line           = split(file_lines[file_idx])
    element_node_ids[1, j] = parse(Int, current_line[1])
    element_node_ids[2, j] = parse(Int, current_line[2])
    element_node_ids[3, j] = parse(Int, current_line[3])
    element_node_ids[4, j] = parse(Int, current_line[4])
    for i in 1:4
      # pull the (x,y) values of these corners out of the nodes array
      cornerNodeVals[i, :] .= corner_nodes[:, element_node_ids[i, j]]
    end
    # pull the information to check if boundary is curved in order to read in additional data
    file_idx += 1
    current_line    = split(file_lines[file_idx])
    curved_check[1] = parse(Int, current_line[1])
    curved_check[2] = parse(Int, current_line[2])
    curved_check[3] = parse(Int, current_line[3])
    curved_check[4] = parse(Int, current_line[4])
    if sum(curved_check) == 0
      # quadrilateral element is straight sided
      element_is_curved[j] = false
      file_idx  += 1
      # read all the boundary names
      bndy_names[:, j] = split(file_lines[file_idx])
    else
      # quadrilateral element has at least one curved side
      element_is_curved[j] = true

      # flip node ordering to make sure the element is right-handed for the interpolations
      m1 = 1
      m2 = 2
      @views tempNodes[1, :] .= cornerNodeVals[4, :]
      @views tempNodes[2, :] .= cornerNodeVals[2, :]
      @views tempNodes[3, :] .= cornerNodeVals[3, :]
      @views tempNodes[4, :] .= cornerNodeVals[1, :]
      for i in 1:4
        if curved_check[i] == 0
          # when curved_check[i] is 0 then the "curve" from cornerNode(i) to cornerNode(i+1) is a
          # straight line. So we must construct the interpolant for this line
          for k in 1:mesh_nnodes
            curve_vals[k, 1] = tempNodes[m1, 1] + 0.5 * (cheby_nodes[k] + 1.0) * ( tempNodes[m2, 1]
                                                                                - tempNodes[m1, 1])
            curve_vals[k, 2] = tempNodes[m1, 2] + 0.5 * (cheby_nodes[k] + 1.0) * ( tempNodes[m2, 2]
                                                                                - tempNodes[m1, 2])
          end
        else
          # when curved_check[i] is 1 this curved boundary information is supplied by the mesh
          # generator. So we just read it into a work array
          for k in 1:mesh_nnodes
            file_idx      += 1
            current_line   = split(file_lines[file_idx])
            curve_vals[k, 1] = parse(RealT,current_line[1])
            curve_vals[k, 2] = parse(RealT,current_line[2])
          end
        end
        # construct the curve interpolant for the current side
        surface_curves[i, j] = CurvedSurfaceT(cheby_nodes, bary_weights, copy(curve_vals))
        # indexing update that contains a "flip" to ensure correct element orientation
        # if we need to construct the straight line "curves" when curved_check[i] == 0
        m1 += 1
        if i == 3
          m2 = 1
        else
          m2 += 1
        end
      end
      # finally read in the boundary names where "---" means an internal connection
      file_idx  += 1
      bndy_names[:, j] = split(file_lines[file_idx])
    end
    # one last increment to the global index to read the next piece of element information
    file_idx += 1
  end

  return n_boundaries
end

@inline Base.ndims(::UnstructuredQuadMesh) = 2
@inline Base.real(::UnstructuredQuadMesh{RealT}) where {RealT} = RealT

# Check if mesh is periodic
isperiodic(mesh::UnstructuredQuadMesh) = mesh.periodicity

Base.length(mesh::UnstructuredQuadMesh) = mesh.n_elements

function Base.show(io::IO, ::UnstructuredQuadMesh{RealT, CurvedSurfaceT}) where {RealT, CurvedSurfaceT}
  print(io, "UnstructuredQuadMesh{2, ", RealT, ", ", CurvedSurfaceT, "}")
end

function Base.show(io::IO, ::MIME"text/plain", mesh::UnstructuredQuadMesh{RealT, CurvedSurfaceT}) where {RealT, CurvedSurfaceT}
  if get(io, :compact, false)
    show(io, mesh)
  else
    summary_header(io, "UnstructuredQuadMesh{" * string(2) * ", " * string(RealT) * ", " * string(CurvedSurfaceT) * "}")
    summary_line(io, "mesh file", mesh.filename)
    summary_line(io, "number of elements", length(mesh))
    summary_line(io, "faces", mesh.n_surfaces)
    summary_line(io, "mesh polynomial degree", mesh.polydeg)
    summary_footer(io)
  end
end


text:
using IncrementalInference

##

@testset "test fourdoor early example" begin

## example parameters
# Number of kernels representing each marginal belief
N=100

# prior knowledge of four possible door locations
cv = 3.0
doorPrior = Mixture(Prior,
                    [Normal(-100,cv);Normal(0,cv);Normal(100,cv);Normal(300,cv)],
                    [1/4;1/4;1/4;1/4] )

## Build the factor graph object
fg = initfg()
getSolverParams(fg).useMsgLikelihoods = true

# first pose location
v1 = addVariable!(fg,:x1,ContinuousScalar,N=N)
# see a door for the first time
addFactor!(fg,[:x1], doorPrior)

# first solution with only one variable and factor (may take a few moments on first JIT compiling)
solveTree!(fg)

## drive to second pose location

addVariable!(fg,:x2, ContinuousScalar, N=N)
addFactor!(fg,[:x1;:x2],LinearRelative(Normal(50.0,2.0)))

# drive to third pose location
v3=addVariable!(fg,:x3,ContinuousScalar, N=N)
addFactor!(fg,[:x2;:x3], LinearRelative( Normal(50.0,4.0)))

# see a door for the second time
addFactor!(fg,[:x3], doorPrior)

# second solution should be much quicker
solveTree!(fg)

# drive to forth and final pose location
addVariable!(fg,:x4,ContinuousScalar, N=N)
addFactor!(fg,[:x3;:x4], LinearRelative( Normal(200.0,4.0)))

## make a third door sighting
addFactor!(fg,[:x4], doorPrior)

# solve over all data
tree = solveTree!(fg)

##

end

# # HMM computed ground truth, extended for 7 poses with landmark
# global gt = Dict{Symbol, Array{Float64,2}}()
# gt[:x0]=reshape(Float64[0.0;1.97304 ],2,1) # -0.0342366
# gt[:x2]=reshape(Float64[50.0; 2.83153 ],2,1) # 49.8797
# gt[:x3]=reshape(Float64[100.0; 1.65557 ],2,1) # 99.8351
# gt[:x4]=reshape(Float64[150.0; 1.64945 ],2,1) # 148.637
# gt[:x5]=reshape(Float64[200.0; 1.77992 ],2,1) # 198.62
# gt[:x6]=reshape(Float64[240.0; 2.20466 ],2,1) # 238.492
# gt[:x7]=reshape(Float64[300.0; 2.14353 ],2,1) # 298.467
# gt[:l1]=reshape(Float64[165.0; 1.17284 ],2,1) # 164.102
#


text:
#this example is modified from https://numericalenvironmental.wordpress.com/2018/05/26/a-steady-state-variably-saturated-flow-model-in-vertical-cross-section-a-finite-difference-approach-using-julia/
using BenchmarkTools
using DiffEqSensitivity
import DifferentiableBackwardEuler
import NonlinearEquations
using OrdinaryDiffEq
#import PyPlot
import Zygote

#include("ex.jl")
include("utilities.jl")
include("inputdeck.jl")

@NonlinearEquations.equations exclude=(coords, dirichletnodes, neighbors, areasoverlengths) function req(psi, Ks, neighbors, areasoverlengths, dirichletnodes, dirichletpsis, coords, alphas, Ns, Qs, specificstorage, volumes)
	NonlinearEquations.setnumequations(length(psi))
	for i = 1:length(psi)
		if i in dirichletnodes
			NonlinearEquations.addterm(i, psi[i] - dirichletpsis[i])
		else
			NonlinearEquations.addterm(i, Qs[i] / (specificstorage[i] * volumes[i]))
		end
	end
	for (i, (node_a, node_b)) in enumerate(neighbors)
		for (node1, node2) in [(node_a, node_b), (node_b, node_a)]
			if !(node1 in dirichletnodes) && !(node2 in dirichletnodes)
				NonlinearEquations.addterm(node1, hm(kr(psi[node1], alphas[i], Ns[i]), kr(psi[node2], alphas[i], Ns[i])) * Ks[i] * (psi[node2] + coords[2, node2] - psi[node1] - coords[2, node1]) * areasoverlengths[i] / (specificstorage[node1] * volumes[node1]))
			elseif !(node1 in dirichletnodes) && node2 in dirichletnodes
				NonlinearEquations.addterm(node1, hm(kr(psi[node1], alphas[i], Ns[i]), kr(dirichletpsis[node2], alphas[i], Ns[i])) * Ks[i] * (dirichletpsis[node2] + coords[2, node2] - psi[node1] - coords[2, node1]) * areasoverlengths[i] / (specificstorage[node1] * volumes[node1]))
			end
		end
	end
end

req_residuals(us, Ks, Qs) = req_residuals(us, Ks, neighbors, areasoverlengths, dirichletnodes, dirichletpsis, coords, alphas, Ns, Qs, specificstorage, volumes)
req_psi(us, Ks, Qs) = req_psi(us, Ks, neighbors, areasoverlengths, dirichletnodes, dirichletpsis, coords, alphas, Ns, Qs, specificstorage, volumes)
req_Ks(us, Ks, Qs) = req_Ks(us, Ks, neighbors, areasoverlengths, dirichletnodes, dirichletpsis, coords, alphas, Ns, Qs, specificstorage, volumes)
req_Qs(us, Ks, Qs) = req_Qs(us, Ks, neighbors, areasoverlengths, dirichletnodes, dirichletpsis, coords, alphas, Ns, Qs, specificstorage, volumes)

@Zygote.adjoint function req_residuals(us, Ks, Qs)
	residuals = req_residuals(us, Ks, Qs)
	back = delta->begin
		retval = ((delta' * req_psi(us, Ks, Qs))', (delta' * req_Ks(us, Ks, Qs))', (delta' * req_Qs(us, Ks, Qs))')
		return retval
	end
	return residuals, back
end

function unpack(p)
	@assert length(p) == length(neighbors)
	Ks = p[1:length(neighbors)]
	return Ks
	#=
	@assert length(p) == length(neighbors) + size(coords, 2)
	Ks = p[1:length(neighbors)]
	Qs = p[length(neighbors) + 1:end]
	return Ks, Qs
	=#
end

function f(u, p, t)
	Ks = unpack(p)
	return req_residuals(u, Ks, Qs)
end

function f_u(u, p, t)
	Ks = unpack(p)
	return req_psi(u, Ks, neighbors, areasoverlengths, dirichletnodes, dirichletpsis, coords, alphas, Ns, Qs, specificstorage, volumes)
end

function f_p(u, p, t)
	Ks = unpack(p)
	return req_Ks(u, Ks, neighbors, areasoverlengths, dirichletnodes, dirichletpsis, coords, alphas, Ns, Qs, specificstorage, volumes)
end

f_t(u, p, t) = zeros(length(u))

psi0 = fill(-5.0, size(coords, 2))
psi0[dirichletnodes] = dirichletpsis[dirichletnodes]
p = Ks
tspan = [0, 1e2]
odef = ODEFunction(f; jac=f_u, jac_prototype=f_u(psi0, p, 0.0))
prob = ODEProblem(odef, psi0, tspan, p)
@time soln_diffeq = solve(prob, ImplicitEuler())
@time soln_dbe = DifferentiableBackwardEuler.steps(psi0, f, f_u, f_p, f_t, p, tspan[1], tspan[2]; ftol=1e-12, method=:newton)
@show sum((soln_diffeq[:, :] .- soln_dbe) .^ 2)
@show sum(soln_diffeq[:, :] .^ 2)
obsnode = div(3 * length(psi0), 4)
g(p) = DifferentiableBackwardEuler.steps(psi0, f, f_u, f_p, f_t, p, tspan[1], tspan[2]; ftol=1e-12, method=:newton)[obsnode, end]
g(p)
@time g(p)
grad_zygote = Zygote.gradient(g, p)[1]
@time grad_zygote = Zygote.gradient(g, p)[1]

function naivegradient(f, x0s...; delta::Float64=1e-8)
	f0 = f(x0s...)
	gradient = map(x->zeros(size(x)), x0s)
	for j = 1:length(x0s)
		x0 = copy(x0s[j])
		for i = 1:length(x0)
			x = copy(x0)
			x[i] += delta
			xs = (x0s[1:j - 1]..., x, x0s[j + 1:length(x0s)]...)
			fval = f(xs...)
			gradient[j][i] = (fval - f0) / delta
		end
	end
	return gradient
end

function checkgradientquickly(f, x0, gradf, n; delta::Float64=1e-8)
	indicestocheck = sort(collect(1:length(x0)), by=i->abs(gradf[i]), rev=true)[1:n]
	indicestocheck = [indicestocheck; rand(1:length(x0), n)]
	f0 = f(x0)
	for i in indicestocheck
		x = copy(x0)
		x[i] += delta
		fval = f(x)
		grad_f_i = (fval - f0) / delta
		@show i
		@show grad_f_i
		@show gradf[i]
	end
end
checkgradientquickly(g, p, grad_zygote, 5; delta=1e-4)

#@show length(p)
#@time grad_naive = naivegradient(g, p)[1]
#@show sqrt(sum((grad_zygote .- grad_naive) .^ 2) / sum(grad_naive .^ 2))
#@show sum(grad_naive .^ 2)


text:
"""
    ContextManagers.SharedResource(source)

Create a sharable resource that is closed once the "last" context using the
shared resource is closed.

!!! warning
    The `source` itself should produce "thread-safe" API if this is shared
    between `@spawn`ed task.

`SharedResource` supports the following pattern

```jldoctest
using Base.Threads: @spawn
using ContextManagers: @with, SharedResource

output = Int[]
@sync begin
    ch = Channel()
    @with(handle = SharedResource(ch)) do       # (1) create a `handle`
        for x in 1:3
            context = open(handle)              # (2) refcount++
            @spawn begin
                @with(ch = context) do          # (3) obtain the `ch` value
                    put!(ch, x)
                end                             # (4a) refcount--; maybe cleanup
            end
        end
    end                                         # (4b) refcount--; maybe cleanup
    append!(output, ch)
end

sort!(output)

# output
3-element Vector{Int64}:
 1
 2
 3
```

# Extended help

(1) The underling `source` is entered when `SharedResource` is entered.  A
`handle` to this shared resource can be obtained by entering the context of the
`SharedResource`.

(2) A `context` for obtaining the value of the context of the original `source`
can be obtained by `open` the `handle`. When sharing the resource across tasks,
it typically has to be done *before* spawning the task.

(3) The `value` from the original `source` can be obtained by entering the
`context`.

(4) The last shared context exitting the `@with` block ends the original
context.  In the above pattern, the context of the `source` may exit at the
`end` (4b) of the outer `@with` if `xs` is empty or all the child tasks exit
first.

## Notes

This is inspired by Nathaniel J. Smith's comment:
<https://github.com/python-trio/trio/issues/719#issuecomment-462119589>
"""
ContextManagers.SharedResource

struct SharedHandle{Context}
    context::Context
    nopens::Threads.Atomic{Int}
end

struct RootSharedContext{Handle<:SharedHandle}
    handle::Handle
end

struct SharedContext{Handle<:SharedHandle}
    handle::Handle
end

ContextManagers.maybeenter(shared::SharedResource) =
    RootSharedContext(SharedHandle(_enter(shared.source), Threads.Atomic{Int}(1)))

ContextManagers.value(context::RootSharedContext) = context.handle

Base.open(handle::SharedHandle) = ContextManagers.maybeenter(handle)
function ContextManagers.maybeenter(handle::SharedHandle)
    # TODO: maybe store `current_task` in `handle` to makesure that it is opened
    # in the same task?
    n = handle.nopens[]
    while n > 0
        old = Threads.atomic_cas!(handle.nopens, n, n + 1)
        old == n && break
        n = old
    end
    if n == 0
        error("already closed")
    end
    return SharedContext(handle)
end

ContextManagers.maybeenter(context::SharedContext) = context

ContextManagers.value(context::SharedContext) =
    ContextManagers.value(context.handle.context)

# TODO: What to do when there is an error? Immediately close? But what when
# there are multiple errors? See also:
# https://github.com/python-trio/trio/issues/719#issuecomment-427317591
function ContextManagers.exit(context::Union{SharedContext,RootSharedContext})
    nopens = context.handle.nopens
    context = context.handle.context
    if Threads.atomic_sub!(nopens, 1) == 1
        ContextManagers.exit(context)
    end
    return
end

# TODO: close should be idempotent
# Base.close(context::SharedContext) = ContextManagers.exit(context)