text:
module LPA

using Graphs
export nsdlpa, nsdlpa1, nmi, voi, modularity, avedegree, similarity, triangle, quadrangle, triquadrsim

include("labelpropagation.jl")
include("modularity.jl")
include("nmi.jl")
include("voi.jl")
include("utils.jl")
include("rankedge.jl")

end # module

max_stars_repo_name: afternone/LPA

max_issues_repo_name: afternone/LPA

max_forks_repo_name: afternone/LPA


text:
"""
fprintTeX(headers,formats,data)

Print a LaTeX table from a Julia array.

Inputs:
headers: the titles for the columns
          example: headers=["foo", "bar"]
formats: c-style formatting for the columns.
          fprintTeX will add the carriage returns for you.
          example: formats="%d & %7.2e";
"""
function fprintTeX(headers, formats, data)
    (mr, mc) = size(data)
    @printf("\\begin{tabular}{")
    for i = 1:mc
        @printf("l")
    end
    @printf("} \n")
    for i = 1:mc-1
        @printf("%9s &", headers[i])
    end
    @printf("%9s \\\\ \n" , headers[mc])
    @printf("\\hline \n")
    #
    # I am not sure why @printf needs this, but it does.
    # See https://github.com/JuliaLang/julia/issues/4248
    #
    printf(fmt::String, args...) = @eval @printf($fmt, $(args...))
    #
    bigform = string(formats, "   \\\\ \n")
    for i = 1:mr
        printf(bigform, data[i, :]...)
    end
    @printf("\\hline \n")
    @printf("\\end{tabular} \n")
end

ext: jl

max_stars_repo_name: ctkelley/MPResults


text:
using FnMatch
using Test

const filenames = [
    ".git",
    ".gitignore",
    "LICENSE",
    "Manifest.toml",
    "Project.toml",
    "README.md",
    "src",
    "test",
]

function test_filter_match(pat, expected, reference)
    for n in reference
        if n in expected
            @test fnmatchcase(n, pat)
        else
            @test !fnmatchcase(n, pat)
        end
    end
    @test all(fnfilter(reference, pat) .== expected)
end

@testset "FnMatch.jl" begin
    @testset "single range" begin
        pat = "[--P]*"
        expected =
            [".git", ".gitignore", "LICENSE", "Manifest.toml", "Project.toml"]
        test_filter_match(pat, expected, filenames)
    end  # Ranges open left

    @testset "multiple ranges" begin
        pat = "[L-Ns-t]*"
        expected = ["LICENSE", "Manifest.toml", "src", "test"]
        test_filter_match(pat, expected, filenames)
    end

    @testset "? wilcard" begin
        source = ["x1", "x2", "x", "xyz"]
        pat = "x?"
        expected = ["x1", "x2"]
        test_filter_match(pat, expected, source)
    end

    @testset "* wildcard" begin
        source = ["x12", "x22z", "abc", "xyz"]
        pat = "x*z"
        expected = ["x22z", "xyz"]
        test_filter_match(pat, expected, source)
    end

    @testset "negated character set" begin
        pat = "[!LMP]*"
        expected = [".git", ".gitignore", "README.md", "src", "test"]
        test_filter_match(pat, expected, filenames)
    end

    # TODO: Support character classes.
    #       http://www.tldp.org/LDP/Bash-Beginners-Guide/html/sect_04_03.html
    # @testset ":lower: character class" begin
    #     pat = "[[:lower:]]*"
    #     expected = ["src", "test"]
    #     test_filter_match(pat, expected, filenames)
    # end

    @testset "literal brackets 1" begin
        source = ["[.txt", "].txt", "[].txt"]
        pat = "[]]*"
        expected = ["].txt"]
        test_filter_match(pat, expected, source)
    end
end  # FnMatch


text:
@ghdef mutable struct Label
    name::Union{String, Nothing}
    default::Union{Bool, Nothing}
    id::Union{Int, Nothing}
    color::Union{String, Nothing}
    node_id::Union{String, Nothing}
    url::Union{String, Nothing}
    description::Union{String, Nothing}
end

namefield(label::Label) = label.name

Label(name::AbstractString) = Label(Dict("name" => name))

@api_default function labels(api::GitHubAPI, repo, issue; options...)
    result = gh_get_json(api, "/repos/$(name(repo))/issues/$(name(issue))/labels"; options...)
    return Label.(result)
end

@api_default function add_labels(api::GitHubAPI, repo, issue, labels; options...)
    result = gh_post_json(api, "/repos/$(name(repo))/issues/$(name(issue))/labels";
                          params=Dict("labels" => name.(labels)), options...)
    return Label.(result)
end

@api_default function set_labels(api::GitHubAPI, repo, issue, labels; options...)
    result = gh_put_json(api, "/repos/$(name(repo))/issues/$(name(issue))/labels";
                         params=Dict("labels" => name.(labels)), options...)
    return Label.(result)
end

@api_default function remove_all_labels(api::GitHubAPI, repo, issue; options...)
    return gh_delete(api, "/repos/$(name(repo))/issues/$(name(issue))/labels"; options...)
end

@api_default function remove_label(api::GitHubAPI, repo, issue, label; options...)
    return gh_delete(api, "/repos/$(name(repo))/issues/$(name(issue))/labels/$(name(label))"; options...)
end


text:
module DemoPackageNML

print_greeting() = print("Hello, world")

end


text:
# ---
# title: 1513. Number of Substrings With Only 1s
# id: problem1513
# author: Tian Jun
# date: 2020-10-31
# difficulty: Medium
# categories: Math, String
# link: <https://leetcode.com/problems/number-of-substrings-with-only-1s/description/>
# hidden: true
# ---
#
# Given a binary string `s` (a string consisting only of '0' and '1's).
#
# Return the number of substrings with all characters 1's.
#
# Since the answer may be too large, return it modulo 10^9 + 7.
#
#
#
# **Example 1:**
#
#
#
#     Input: s = "0110111"
#     Output: 9
#     Explanation: There are 9 substring in total with only 1's characters.
#     "1" -> 5 times.
#     "11" -> 3 times.
#     "111" -> 1 time.
#
# **Example 2:**
#
#
#
#     Input: s = "101"
#     Output: 2
#     Explanation: Substring "1" is shown 2 times in s.
#
#
# **Example 3:**
#
#
#
#     Input: s = "111111"
#     Output: 21
#     Explanation: Each substring contains only 1's characters.
#
#
# **Example 4:**
#
#
#
#     Input: s = "000"
#     Output: 0
#
#
#
#
# **Constraints:**
#
#   * `s[i] == '0'` or `s[i] == '1'`
#   * `1 <= s.length <= 10^5`
#
#
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end


text:
module BadLongRunningExample

using Matte

const title = "Matte Example :: How Not To Do Long-running Computations"

function ui()
    sidebar_layout(
        side_panel(
            h1("Choose two numbers"),
            br(),
            slider("slider1", "Number 1", 0, 100),
            slider("slider2", "Number 2", 0, 100)
        ),
        main_panel(
            h1("The sum of your numbers is:"),
            br(),
            text_output("my_sum")
        )
    )
end

module Server

function my_sum(slider1, slider2)
    sleep(10)
    slider1 + slider2
end

end

end


text:
using Contexts
using Test

function foo(ctx::AbstractContext, x)
    # Use of @defer with explicit context
    @defer ctx push!(x, :A)
end

@testset "Cleanup ordering" begin
    cleanups = []
    @context begin
        @! foo(cleanups)
        @defer push!(cleanups, :B)
        @test cleanups == []
    end
    @test cleanups == [:B, :A]
end

@testset "Exceptions during cleanup" begin
    try
        @context begin
            @defer error("A")
            @defer error("B")
        end
    catch exc
        stack = Base.catch_stack()
        @test stack[1][1] == ErrorException("B")
        @test stack[2][1] == ErrorException("A")
    end
end

@testset "Base interop" begin
    @testset "open() and mktemp()" begin
        path = ""
        io1 = nothing
        io2 = nothing
        io3 = nothing
        io4 = nothing
        @context begin
            (path,io1) = @! mktemp()
            msg = "hi from Contexts.jl"
            write(io1, msg)
            flush(io1)
            # Test various forms of open()
            io2 = @! open(path)
            @test read(io2, String) == msg
            io3 = @! open(path, "r")
            @test read(io3, String) == msg
            io4 = @! open(path, read=true)
            @test read(io4, String) == msg
        end
        @test !isempty(path) && !ispath(path)
        @test !isopen(io1)
        @test !isopen(io2)
        @test !isopen(io3)
        @test !isopen(io4)
    end

    @testset "mktemp() and mktempdir()" begin
        parent_dir = nothing
        dir2 = nothing
        filepath = nothing
        @context begin
            parent_dir = @! mktempdir()
            # forms with parent dirs
            dir2 = @! mktempdir(parent_dir)
            (filepath,_) = @! mktemp(parent_dir)
            # All resources are created
            @test isdir(parent_dir)
            @test isdir(dir2)
            @test isfile(filepath)
            @test parent_dir == dirname(dir2)
            @test parent_dir == dirname(filepath)
        end
        # All resources are cleaned up
        @test !ispath(parent_dir)
        @test !ispath(dir2)
        @test !ispath(filepath)
    end

    @testset "lock()" begin
        lk = ReentrantLock()
        @context begin
            @! lock(lk)
            @test islocked(lk)
        end
        @test !islocked(lk)
    end

    @testset "redirect_stdout / stderr / stdin" begin
        orig_stdin = stdin
        orig_stdout = stdout
        orig_stderr = stderr

        stdout_result = nothing
        @context begin
            (_,io) = @! mktemp()
            @! redirect_stdout(io)
            println("hi")
            flush(io)
            seek(io, 0)
            stdout_result = readline(io)
        end
        @test stdout_result == "hi"

        stderr_result = nothing
        @context begin
            (_,io) = @! mktemp()
            @! redirect_stderr(io)
            println(stderr, "hi")
            flush(io)
            seek(io, 0)
            stderr_result = readline(io)
        end
        if VERSION < v"1.7-DEV"
            @test stderr_result == "hi"
        else
            @test_broken stderr_result == "hi"
        end

        stdin_result = nothing
        @context begin
            (_,io) = @! mktemp()
            println(io, "hi")
            flush(io)
            seek(io,0)
            @! redirect_stdin(io)
            stdin_result = readline()
        end
        if VERSION < v"1.7-DEV"
            @test stdin_result == "hi"
        else
            @test_broken stdin_result == "hi"
        end

        @test orig_stdin == stdin
        @test orig_stdout == stdout
        @test orig_stderr == stderr
    end

    @testset "cd()" begin
        oldpath = pwd()
        @context begin
            @! cd()
            # Can't just compare paths here due to the fact that some of these
            # could be symlinks on macOS.  Instead use `samefile` with an alias
            # for @test pretty printing
            ≃(a,b) = Base.Filesystem.samefile(a,b)
            @test pwd() ≃ homedir()
            path = @! mktempdir()
            @! cd(path)
            @test pwd() ≃ path
        end
        @test pwd() == oldpath
    end
end


text:
using SparseArrays, LinearAlgebra
"""
    as_to_bs(a1, a2)

Calculate reciprocal lattice vectors, `b1` and `b2`, from the real space lattice
vectors, `a1` and `a2`.
"""
function as_to_bs(a1, a2)
    b1 = 2pi * [+a2[2],-a2[1]] / (+a1[1]*a2[2]-a1[2]*a2[1])
    b2 = 2pi * [-a1[2],+a1[1]] / (-a2[1]*a1[2]+a2[2]*a1[1])
    return b1, b2
end

"""
    bs_to_as(b1, b2)

Calculate real space lattice vectors, `a1` and `a2`, from reciprocal lattice
vectors, `b1` and `b2`.

This is actually the same as `as_to_bs`, but I think having both functions makes
the intention of the code more obvious.
"""
function bs_to_as(b1, b2)
    return as_to_bs(b1, b2)
end

"""
    DEX, DEY, DHX, DHY = diff_yee2(NGRID,RES,BC,kinc=nothing)
=================
- `NGRID`: [Nx Ny] grid size.
- `RES`: [dx dy] grid resolution of the 1X grid.
- `BC`: [xbc ybc] boundary conditions, `-2`: periodic (requires kinc), `0`: Dirichlet.
- `kinc`: [kx ky] incident wave vector. This argument is only needed for periodic boundaries.
Position on the grid: m = (ny - 1)*Nx + nx
"""
function diff_yee2(NGRID::Matrix{Float64}, RES::Matrix{Float64}, BC::Matrix{Int64}, a1::Array{<:Real,1}, a2::Array{<:Real,1}, kinc=nothing)
    if kinc != nothing
        kinc0 = kinc
    end
    p(nx,ny,NX)::Int64 = nx+NX*(ny-1)
    dx = RES[1]; dy = RES[2]
    NX = NGRID[1]; NY = NGRID[2]; N = NX*NY;
    Lamx = NX * dx
    Lamy = NY * dy
    N = convert(Int64,N);NX = convert(Int64,NX);NY = convert(Int64,NY)
    if NX == 1
        if BC[1] == 0
            DEX = spzeros(N, N)
        else
            DEX = spdiagm(0 => im*kinc0[2]*ones(N))
        end
    else
        DEX = spdiagm(0 => -1 ./ dx .* ones(ComplexF64, N), 1 => 1 ./ dx .* ones(ComplexF64, N - 1))
        for ny=1:(NY-1)
            DEX[p(NX,ny,NX),p(NX+1,ny,NX)] = 0  # Dirichlet BC
        end
        if BC[1]==-2
            for ny=1:NY
                DEX[p(NX,ny,NX),p(1,ny,NX)]=exp(-im*transpose(kinc0)*a1*Lamx)/dx # periodic BC
            end

        end
    end

    if NY==1
        if BC[2] == 0
            DEY = spzeros(N,N)
        else
            DEY = spdiagm(0 => im*kinc0[1]*ones(N))
        end
    else
        DEY = spdiagm(0 => -1 ./dy.*ones(N), NX => 1 ./dy.*ones(N - NX)) .+ 0*im
        if BC[2]==-2
            for nx=1:NX
                DEY[p(nx,NY,NX),p(nx,1,NX)]=exp(-im*transpose(kinc0)*a2*Lamy)/dy # periodic BC
            end
        end
    end

    DHX=-DEX'
    DHY=-DEY'
    return DEX,DEY,DHX,DHY
end

# """
#     DiagonalMatrix(diag::AbstractVector{ComplexF64})

# A sparse diagonal matrix that can be used in left division (D \\ X)
# """
# struct DiagonalMatrix <: AbstractMatrix{ComplexF64}
#     diag::AbstractVector{ComplexF64}
# end
# Base.size(A::DiagonalMatrix) = (length(A.diag), length(A.diag))
# Base.getindex(A::DiagonalMatrix, I::Vararg{Int,2}) = I[1]==I[2] ? A.diag[I[1]] : 0

eye(M) = Matrix{ComplexF64}(I, M, M)
diag_R(mat) = mat[diagind(mat)]

function mask(M)
    mat = zeros(M,M)
    for i = -(M-1):M-1
        mat = mat + diagm(i=>(-1)^(i)*ones(M-abs(i)))
    end
    return mat
end


text:
mutable struct MIPNode <: AbstractNode
    std :: BnBNodeInfo
    lbs :: Vector{Float64}
    ubs :: Vector{Float64}
    status :: MOI.TerminationStatusCode
end

function BB.get_relaxed_values(tree::BnBTree{MIPNode, JuMP.Model}, node)
    vids = MOI.get(tree.root ,MOI.ListOfVariableIndices())
    vars = VariableRef.(tree.root, vids)
    return JuMP.value.(vars)
end

function BB.get_branching_indices(model::JuMP.Model)
    # every variable should be discrete
    vis = MOI.get(model, MOI.ListOfVariableIndices())
    return 1:length(vis)
end

function BB.evaluate_node!(tree::BnBTree{MIPNode, JuMP.Model}, node::MIPNode)
    m = tree.root
    vids = MOI.get(m ,MOI.ListOfVariableIndices())
    vars = VariableRef.(m, vids)
    for vidx in eachindex(vars)
        if isfinite(node.lbs[vidx])
            JuMP.set_lower_bound(vars[vidx], node.lbs[vidx])
        elseif node.lbs[vidx] == -Inf && JuMP.has_lower_bound(vars[vidx])
            JuMP.delete_lower_bound(vars[vidx])
        elseif node.lbs[vidx] == Inf # making problem infeasible
            error("Invalid lower bound for variable $vidx: $(node.lbs[vidx])")
        end
        if isfinite(node.ubs[vidx])
            JuMP.set_upper_bound(vars[vidx], node.ubs[vidx])
        elseif node.ubs[vidx] == Inf && JuMP.has_upper_bound(vars[vidx])
            JuMP.delete_upper_bound(vars[vidx])
        elseif node.ubs[vidx] == -Inf # making problem infeasible
            error("Invalid upper bound for variable $vidx: $(node.lbs[vidx])")
        end
    end

    optimize!(m)
    status = termination_status(m)
    node.status = status
    if status != MOI.OPTIMAL
        return NaN,NaN
    end

    obj_val = objective_value(m)
    if all(BB.is_approx_feasible.(tree, value.(vars)))
        node.ub = obj_val
        return obj_val, obj_val
    end
    return obj_val, NaN
end

function BB.get_branching_nodes_info(tree::BnBTree{MIPNode, JuMP.Model}, node::MIPNode, vidx::Int)
    m = tree.root
    node_info = NamedTuple[]

    var = VariableRef(m, MOI.VariableIndex(vidx))

    # first variable which is not discrete
    lbs = copy(node.lbs)
    ubs = copy(node.ubs)

    val = JuMP.value(var)

    # left child set upper bound
    ubs[vidx] = floor(Int, val)

    push!(node_info, (
        lbs = copy(node.lbs),
        ubs = ubs,
        status = MOI.OPTIMIZE_NOT_CALLED,
    ))

    # right child set lower bound
    lbs[vidx] = ceil(Int, val)

    push!(node_info, (
        lbs = lbs,
        ubs = copy(node.ubs),
        status = MOI.OPTIMIZE_NOT_CALLED,
    ))
    return node_info
end

@testset "MIP Problem with 3 variables" begin
    m = Model(HiGHS.Optimizer)
    set_optimizer_attribute(m, "log_to_console", false)
    @variable(m, x[1:3] >= 0)
    @constraint(m, 0.5x[1]+3.1x[2]+4.2x[3] <= 6.1)
    @constraint(m, 1.9x[1]+0.7x[2]+0.2x[3] <= 8.1)
    @constraint(m, 2.9x[1]-2.3x[2]+4.2x[3] <= 10.5)
    @objective(m, Max, x[1]+1.2x[2]+3.2x[3])

    bnb_model = BB.initialize(;
        traverse_strategy = BB.BFS(),
        Node = MIPNode,
        root = m,
        sense = objective_sense(m) == MOI.MAX_SENSE ? :Max : :Min
    )
    BB.set_root!(bnb_model, (
        lbs = zeros(length(x)),
        ubs = fill(Inf, length(x)),
        status = MOI.OPTIMIZE_NOT_CALLED
    ))

    BB.optimize!(bnb_model)

    sol_x = convert.(Int, BB.get_solution(bnb_model))

    @test sol_x == [2,0,1]
    @test BB.get_objective_value(bnb_model) ≈ 5.2
end

@testset "MIP Problem with 3 variables minimize" begin
    m = Model(HiGHS.Optimizer)
    set_optimizer_attribute(m, "log_to_console", false)
    @variable(m, x[1:3] >= 0)
    @constraint(m, 0.5x[1]+3.1x[2]+4.2x[3] >= 6.1)
    @constraint(m, 1.9x[1]+0.7x[2]+0.2x[3] >= 8.1)
    @constraint(m, 2.9x[1]-2.3x[2]+4.2x[3] >= 10.5)
    @objective(m, Min, x[1]+1.2x[2]+3.2x[3])

    bnb_model = BB.initialize(;
        branch_strategy = BB.MOST_INFEASIBLE(),
        Node = MIPNode,
        root = m,
        sense = objective_sense(m) == MOI.MAX_SENSE ? :Max : :Min
    )
    BB.set_root!(bnb_model, (
        lbs = zeros(length(x)),
        ubs = fill(Inf, length(x)),
        status = MOI.OPTIMIZE_NOT_CALLED
    ))

    BB.optimize!(bnb_model)

    sol_x = BB.get_solution(bnb_model)

    @test sol_x ≈ [6.0,1.0,0.0]
    @test BB.get_objective_value(bnb_model) ≈ 7.2
end


text:
module MLIR

using Libdl
using LLVM
using LLVM: @runtime_ccall, @checked, refcheck

const libmlir = Ref{Symbol}()
const libmlir_private = Ref{Symbol}()

# ------------ Initialization ------------ #

function __init__()

    # Find the libMLIR public *.so.
    libmlir[] = if VERSION >= v"1.6.0-DEV.1429"
        path = joinpath(String(Base.libllvm_path()), "..", "libMLIRPublicAPI.so") |> normpath
        if path === nothing
            error("""Cannot find the LLVM library loaded by Julia.
                  Please use a version of Julia that has been built with USE_LLVM_SHLIB=1 (like the official binaries).
                  If you are, please file an issue and attach the output of `Libdl.dllist()`.""")
        end
        Symbol(path)
    else
        error("Please use a version of Julia with `versioninfo` > 1.6, built with LLVM 12 + MLIR enabled.")
    end

    # Find the private *.so.
    libmlir_private[] = if VERSION >= v"1.6.0-DEV.1429"
        path = joinpath(String(Base.libllvm_path()), "..", "libMLIR.so") |> normpath
        if path === nothing
            error("""Cannot find the LLVM library loaded by Julia.
                  Please use a version of Julia that has been built with USE_LLVM_SHLIB=1 (like the official binaries).
                  If you are, please file an issue and attach the output of `Libdl.dllist()`.""")
        end
        Symbol(path)
    else
        error("Please use a version of Julia with `versioninfo` > 1.6, built with LLVM 12 + MLIR enabled.")
    end
end

# ------------ C API ------------ #

module API
using CEnum
using ..MLIR
using ..MLIR: libmlir, libmlir_private
using ..LLVM: @checked, refcheck
const intptr_t = Int
libdir = joinpath(@__DIR__, "..", "lib")
include(joinpath(libdir, "ctypes.jl"))
export Ctm, Ctime_t, Cclock_t
include(joinpath(libdir, "libmlir_common.jl"))
include(joinpath(libdir, "libmlir_api.jl"))
end

# ----------- Core ------------ #

# Builds off C API.

include("core/IR.jl")

# ------------ Standard dialects ------------ #

include("dialects/affine.jl")

end # module


text:
using ArgusWrapper

camera_provider = ArgusWrapper.create_camera_provider()
argus_version = ArgusWrapper.get_argus_version(camera_provider)
println("Argus version: $(argus_version)")
camera_devices = ArgusWrapper.get_camera_devices(camera_provider)
if isempty(camera_devices)
    println("No cameras available!")
    exit(1)
end
camera_device = first(camera_devices)
@show camera_device
sensor_modes = ArgusWrapper.get_all_sensor_modes(camera_device)
for sensor_mode in sensor_modes
    @show Int.(ArgusWrapper.get_resolution(sensor_mode))
end


text:
# ---
# title: 1247. Minimum Swaps to Make Strings Equal
# id: problem1247
# author: Tian Jun
# date: 2020-10-31
# difficulty: Medium
# categories: String, Greedy
# link: <https://leetcode.com/problems/minimum-swaps-to-make-strings-equal/description/>
# hidden: true
# ---
#
# You are given two strings `s1` and `s2` of equal length consisting of letters
# `"x"` and `"y"` **only**. Your task is to make these two strings equal to each
# other. You can swap any two characters that belong to **different** strings,
# which means: swap `s1[i]` and `s2[j]`.
#
# Return the minimum number of swaps required to make `s1` and `s2` equal, or
# return `-1` if it is impossible to do so.
#
#
#
# **Example 1:**
#
#
#
#     Input: s1 = "xx", s2 = "yy"
#     Output: 1
#     Explanation: Swap s1[0] and s2[1], s1 = "yx", s2 = "yx".
#
# **Example 2:  **
#
#
#
#     Input: s1 = "xy", s2 = "yx"
#     Output: 2
#     Explanation: Swap s1[0] and s2[0], s1 = "yy", s2 = "xx".
#     Swap s1[0] and s2[1], s1 = "xy", s2 = "xy".
#     Note that you can't swap s1[0] and s1[1] to make s1 equal to "yx", cause we can only swap chars in different strings.
#
# **Example 3:**
#
#
#
#     Input: s1 = "xx", s2 = "xy"
#     Output: -1
#
#
# **Example 4:**
#
#
#
#     Input: s1 = "xxyyxyxyxx", s2 = "xyyxyxxxyx"
#     Output: 4
#
#
#
#
# **Constraints:**
#
#   * `1 <= s1.length, s2.length <= 1000`
#   * `s1, s2` only contain `'x'` or `'y'`.
#
#
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end


text:
using CRCBS, GraphUtils, CairoMakie, Makie, FactoryRendering

vtx_grid = initialize_dense_vtx_grid(4,4)
#  1   2   3   4
#  5   6   7   8
#  9  10  11  12
# 13  14  15  16
starts = [1,2,3,4,5,6,7,8]
goals = [13,14,15,16,9,10,11,12]
# graph = initialize_grid_graph_from_vtx_grid(vtx_grid)
graph = construct_factory_env_from_vtx_grid(vtx_grid)
mapf = init_mapf_problem(graph,starts,goals)

solver = PIBTPlanner{Float64}()
set_iteration_limit!(solver,10)
set_verbosity!(solver,4)
solution, valid = pibt!(solver, mapf)
@show valid, convert_to_vertex_lists(solution)

vtx_lists = convert_to_vertex_lists(solution)
grid_vtxs = map(v->[v[1],v[2]], mapf.env.graph.vtxs)
paths = map(p->map(v->grid_vtxs[v],p),vtx_lists)
# scene = Scene()
scene = Scene(show_axis=false,scale_plot=false,resolution=(200,200))
t0 = 0.0
tf = length(paths[1]) + 1.0
pad = 0.75
corners = FactoryRendering.bbox_corners(grid_vtxs,pad)
poly!(scene,Point2f0.(corners), color=:gray)
scene = FactoryRendering.plot_grid_world!(scene,grid_vtxs)

t = Node(t0) # This is the life signal
positions = lift(t->FactoryRendering.env_state_snapshot(paths,t),t)
x = lift(positions->map(p->p[1],positions),positions)
y = lift(positions->map(p->p[2],positions),positions)
text_positions = map(i->lift(positions->tuple(positions[i]...),positions),1:length(paths))
scatter!(scene,x,y,marker=:circle,markersize=0.8,color=:red)
for i in 1:length(paths)
    text!(scene,string(i),textsize=0.4,align=(:center,:center), position=text_positions[i])
end
for (i,g) in enumerate(goals)
    text!(scene,string(i),textsize=0.2,align=(:left,:top),position=tuple((grid_vtxs[g] .+ [-0.45,0.48])...),overdraw=true)
end
scene

record(scene, "robots_moving.webm", 0:0.1:tf; framerate = 20) do dt
    t[] = t0 + dt
end


text:
# This file is a part of Julia. License is MIT: http://julialang.org/license

module LibGit2

import Base: merge!, cat, ==

export with, GitRepo, GitConfig

const GITHUB_REGEX =
    r"^(?:git@|git://|https://(?:[\w\.\+\-]+@)?)github.com[:/](([^/].+)/(.+?))(?:\.git)?$"i

const REFCOUNT = Threads.Atomic{UInt}()

include("utils.jl")
include("consts.jl")
include("types.jl")
include("error.jl")
include("signature.jl")
include("oid.jl")
include("reference.jl")
include("commit.jl")
include("repository.jl")
include("config.jl")
include("walker.jl")
include("remote.jl")
include("strarray.jl")
include("index.jl")
include("merge.jl")
include("tag.jl")
include("blob.jl")
include("diff.jl")
include("rebase.jl")
include("status.jl")
include("tree.jl")
include("callbacks.jl")

using .Error

immutable State
    head::GitHash
    index::GitHash
    work::GitHash
end

"""
    head(pkg::AbstractString) -> String

Return current HEAD [`GitHash`](@ref) of
the `pkg` repo as a string.
"""
function head(pkg::AbstractString)
    with(GitRepo, pkg) do repo
        string(head_oid(repo))
    end
end

"""
    need_update(repo::GitRepo)

Equivalent to `git update-index`. Returns `true`
if `repo` needs updating.
"""
function need_update(repo::GitRepo)
    if !isbare(repo)
        # read updates index from filesystem
        read!(repo, true)
    end
end

"""
    iscommit(id::AbstractString, repo::GitRepo) -> Bool

Checks if commit `id` (which is a [`GitHash`](@ref) in string form)
is in the repository.
"""
function iscommit(id::AbstractString, repo::GitRepo)
    res = true
    try
        c = GitCommit(repo, id)
        if c === nothing
            res = false
        else
            close(c)
        end
    catch
        res = false
    end
    return res
end

"""
    LibGit2.isdirty(repo::GitRepo, pathspecs::AbstractString=""; cached::Bool=false) -> Bool

Checks if there have been any changes to tracked files in the working tree (if
`cached=false`) or the index (if `cached=true`).
`pathspecs` are the specifications for options for the diff.

Equivalent to `git diff-index HEAD [-- <pathspecs>]`.
"""
isdirty(repo::GitRepo, paths::AbstractString=""; cached::Bool=false) =
    isdiff(repo, Consts.HEAD_FILE, paths, cached=cached)

"""
    LibGit2.isdiff(repo::GitRepo, treeish::AbstractString, pathspecs::AbstractString=""; cached::Bool=false)

Checks if there are any differences between the tree specified by `treeish` and the
tracked files in the working tree (if `cached=false`) or the index (if `cached=true`).
`pathspecs` are the specifications for options for the diff.

Equivalent to `git diff-index <treeish> [-- <pathspecs>]`.
"""
function isdiff(repo::GitRepo, treeish::AbstractString, paths::AbstractString=""; cached::Bool=false)
    tree_oid = revparseid(repo, "$treeish^{tree}")
    result = false
    tree = GitTree(repo, tree_oid)
    try
        diff = diff_tree(repo, tree, paths, cached=cached)
        result = count(diff) > 0
        close(diff)
    finally
        close(tree)
    end
    return result
end

""" git diff --name-only --diff-filter=<filter> <branch1> <branch2> """
function diff_files(repo::GitRepo, branch1::AbstractString, branch2::AbstractString;
                    filter::Set{Cint}=Set([Consts.DELTA_ADDED, Consts.DELTA_MODIFIED, Consts.DELTA_DELETED]))
    b1_id = revparseid(repo, branch1*"^{tree}")
    b2_id = revparseid(repo, branch2*"^{tree}")
    tree1 = GitTree(repo, b1_id)
    tree2 = GitTree(repo, b2_id)
    files = AbstractString[]
    try
        diff = diff_tree(repo, tree1, tree2)
        for i in 1:count(diff)
            delta = diff[i]
            delta === nothing && break
            if delta.status in filter
                push!(files, unsafe_string(delta.new_file.path))
            end
        end
        close(diff)
    finally
        close(tree1)
        close(tree2)
    end
    return files
end

"""
    is_ancestor_of(a::AbstractString, b::AbstractString, repo::GitRepo) -> Bool

Returns `true` if `a`, a [`GitHash`](@ref) in string form, is an ancestor of
`b`, a [`GitHash`](@ref) in string form.
"""
function is_ancestor_of(a::AbstractString, b::AbstractString, repo::GitRepo)
    A = revparseid(repo, a)
    merge_base(repo, a, b) == A
end

"""
    set_remote_url(repo::GitRepo, url::AbstractString; remote::AbstractString="origin")

Set the `url` for `remote` for the git repository `repo`.
The default name of the remote is `"origin"`.
"""
function set_remote_url(repo::GitRepo, url::AbstractString; remote::AbstractString="origin")
    with(GitConfig, repo) do cfg
        set!(cfg, "remote.$remote.url", url)

        m = match(GITHUB_REGEX,url)
        if m !== nothing
            push = "git@github.com:$(m.captures[1]).git"
            if push != url
                set!(cfg, "remote.$remote.pushurl", push)
            end
        end
    end
end

"""
    set_remote_url(path::AbstractString, url::AbstractString; remote::AbstractString="origin")

Set the `url` for `remote` for the git repository located at `path`.
The default name of the remote is `"origin"`.
"""
function set_remote_url(path::AbstractString, url::AbstractString; remote::AbstractString="origin")
    with(GitRepo, path) do repo
        set_remote_url(repo, url, remote=remote)
    end
end

function make_payload{P<:AbstractCredentials}(payload::Nullable{P})
    Ref{Nullable{AbstractCredentials}}(payload)
end

"""
    fetch(repo::GitRepo; remote::AbstractString="origin", remoteurl::AbstractString="", refspecs=AbstractString[], payload=Nullable{AbstractCredentials}())

Equivalent to `git fetch [<remoteurl>|<repo>] [<refspecs>]`.
Fetches updates from the upstream `remote` with URL `remoteurl` of the repository `repo`.
Uses the provided fetch `refspecs` to determine properties of the fetch.
`payload` provides credentials if necessary, for instance if `remote` is a private
repository.
"""
function fetch{T<:AbstractString, P<:AbstractCredentials}(repo::GitRepo;
                                  remote::AbstractString="origin",
                                  remoteurl::AbstractString="",
                                  refspecs::Vector{T}=AbstractString[],
                                  payload::Nullable{P}=Nullable{AbstractCredentials}())
    rmt = if isempty(remoteurl)
        get(GitRemote, repo, remote)
    else
        GitRemoteAnon(repo, remoteurl)
    end
    try
        payload = make_payload(payload)
        fo = FetchOptions(callbacks=RemoteCallbacks(credentials_cb(), payload))
        fetch(rmt, refspecs, msg="from $(url(rmt))", options = fo)
    finally
        close(rmt)
    end
end

"""
    push(repo::GitRepo; remote::AbstractString="origin", remoteurl::AbstractString="", refspecs=AbstractString[], force::Bool=false, payload=Nullable{AbstractCredentials}())

Equivalent to `git push [<remoteurl>|<repo>] [<refspecs>]`.
Pushes updates to the `remote` upstream of `repo`, with URL `remoteurl`.
Uses the provided push `refspecs` to determine properties of the push.
`force` determines if the push will be a force push, overwriting the remote branch.
`payload` provides credentials if necessary, for instance if `remote` is a private
repository.
"""
function push{T<:AbstractString, P<:AbstractCredentials}(repo::GitRepo;
              remote::AbstractString="origin",
              remoteurl::AbstractString="",
              refspecs::Vector{T}=AbstractString[],
              force::Bool=false,
              payload::Nullable{P}=Nullable{AbstractCredentials}())
    rmt = if isempty(remoteurl)
        get(GitRemote, repo, remote)
    else
        GitRemoteAnon(repo, remoteurl)
    end
    try
        payload = make_payload(payload)
        push_opts=PushOptions(callbacks=RemoteCallbacks(credentials_cb(), payload))
        push(rmt, refspecs, force=force, options=push_opts)
    finally
        close(rmt)
    end
end

"""
    branch(repo::GitRepo)

Equivalent to `git branch`.
Create a new branch from the current HEAD.
"""
function branch(repo::GitRepo)
    head_ref = head(repo)
    try
        branch(head_ref)
    finally
        close(head_ref)
    end
end

"""
    branch!(repo::GitRepo, branch_name::AbstractString, commit::AbstractString=""; track::AbstractString="", force::Bool=false, set_head::Bool=true)

Equivalent to `git checkout [-b|-B] <branch_name> [<commit>] [--track <track>]`.
Checkout a new git branch in the `repo` repository. `commit` is the [`GitHash`](@ref),
in string form, which will be the start of the new branch. `track` is the name of the
remote branch this new branch should track, if any. If empty (the default), no remote branch
will be tracked. If `force` is `true`, branch creation will be forced. If `set_head` is
`true`, after the branch creation finishes the branch head will be set as the HEAD of `repo`.
"""
function branch!(repo::GitRepo, branch_name::AbstractString,
                 commit::AbstractString = ""; # start point
                 track::AbstractString  = "", # track remote branch
                 force::Bool=false,           # force branch creation
                 set_head::Bool=true)         # set as head reference on exit
    # try to lookup branch first
    branch_ref = force ? Nullable{GitReference}() : lookup_branch(repo, branch_name)
    if isnull(branch_ref)
        branch_rmt_ref = isempty(track) ? Nullable{GitReference}() : lookup_branch(repo, "$track/$branch_name", true)
        # if commit is empty get head commit oid
        commit_id = if isempty(commit)
            if isnull(branch_rmt_ref)
                with(head(repo)) do head_ref
                    with(peel(GitCommit, head_ref)) do hrc
                        GitHash(hrc)
                    end
                end
            else
                tmpcmt = with(peel(GitCommit, Base.get(branch_rmt_ref))) do hrc
                    GitHash(hrc)
                end
                close(Base.get(branch_rmt_ref))
                tmpcmt
            end
        else
            GitHash(commit)
        end
        iszero(commit_id) && return
        cmt =  GitCommit(repo, commit_id)
        new_branch_ref = nothing
        try
            new_branch_ref = Nullable(create_branch(repo, branch_name, cmt, force=force))
        finally
            close(cmt)
            isnull(new_branch_ref) && throw(GitError(Error.Object, Error.ERROR, "cannot create branch `$branch_name` with `$commit_id`"))
            branch_ref = new_branch_ref
        end
    end
    try
        #TODO: what if branch tracks other then "origin" remote
        if !isempty(track) # setup tracking
            try
                with(GitConfig, repo) do cfg
                    set!(cfg, "branch.$branch_name.remote", Consts.REMOTE_ORIGIN)
                    set!(cfg, "branch.$branch_name.merge", name(Base.get(branch_ref)))
                end
            catch
                warn("Please provide remote tracking for branch '$branch_name' in '$(path(repo))'")
            end
        end

        if set_head
            # checkout selected branch
            with(peel(GitTree, Base.get(branch_ref))) do btree
                checkout_tree(repo, btree)
            end

            # switch head to the branch
            head!(repo, Base.get(branch_ref))
        end
    finally
        close(Base.get(branch_ref))
    end
    return
end

"""
    checkout!(repo::GitRepo, commit::AbstractString=""; force::Bool=true)

Equivalent to `git checkout [-f] --detach <commit>`.
Checkout the git commit `commit` (a [`GitHash`](@ref) in string form)
in `repo`. If `force` is `true`, force the checkout and discard any
current changes. Note that this detaches the current HEAD.
"""
function checkout!(repo::GitRepo, commit::AbstractString = "";
                  force::Bool = true)
    # nothing to do
    isempty(commit) && return

    # grab head name
    head_name = Consts.HEAD_FILE
    try
        with(head(repo)) do head_ref
            head_name = shortname(head_ref)
            # if it is HEAD use short OID instead
            if head_name == Consts.HEAD_FILE
                head_name = string(GitHash(head_ref))
            end
        end
    end

    # search for commit to get a commit object
    obj = GitObject(repo, GitHash(commit))
    peeled = peel(GitCommit, obj)

    opts = force ? CheckoutOptions(checkout_strategy = Consts.CHECKOUT_FORCE) : CheckoutOptions()
    # detach commit
    obj_oid = GitHash(peeled)
    ref = GitReference(repo, obj_oid, force=force,
                       msg="libgit2.checkout: moving from $head_name to $(string(obj_oid))")

    # checkout commit
    checkout_tree(repo, peeled, options = opts)
end

""" git clone [-b <branch>] [--bare] <url> <dir> """
function clone{P<:AbstractCredentials}(repo_url::AbstractString, repo_path::AbstractString;
               branch::AbstractString="",
               isbare::Bool = false,
               remote_cb::Ptr{Void} = C_NULL,
               payload::Nullable{P}=Nullable{AbstractCredentials}())
    # setup clone options
    lbranch = Base.cconvert(Cstring, branch)
    payload = make_payload(payload)
    fetch_opts=FetchOptions(callbacks = RemoteCallbacks(credentials_cb(), payload))
    clone_opts = CloneOptions(
                bare = Cint(isbare),
                checkout_branch = isempty(lbranch) ? Cstring(C_NULL) : Base.unsafe_convert(Cstring, lbranch),
                fetch_opts=fetch_opts,
                remote_cb = remote_cb
            )
    return clone(repo_url, repo_path, clone_opts)
end

""" git reset [<committish>] [--] <pathspecs>... """
function reset!(repo::GitRepo, committish::AbstractString, pathspecs::AbstractString...)
    obj = GitObject(repo, isempty(committish) ? Consts.HEAD_FILE : committish)
    # do not remove entries in the index matching the provided pathspecs with empty target commit tree
    reset!(repo, Nullable(obj), pathspecs...)
end

""" git reset [--soft | --mixed | --hard] <id> """
reset!(repo::GitRepo, id::GitHash, mode::Cint = Consts.RESET_MIXED) =
    reset!(repo, GitObject(repo, id), mode)

""" git cat-file <commit> """
function cat(repo::GitRepo, spec)
    obj = GitObject(repo, spec)
    if isa(obj, GitBlob)
        content(obj)
    else
        nothing
    end
end

""" git rev-list --count <commit1> <commit2> """
function revcount(repo::GitRepo, fst::AbstractString, snd::AbstractString)
    fst_id = revparseid(repo, fst)
    snd_id = revparseid(repo, snd)
    base_id = merge_base(repo, string(fst_id), string(snd_id))
    fc = with(GitRevWalker(repo)) do walker
        count((i,r)->i!=base_id, walker, oid=fst_id, by=Consts.SORT_TOPOLOGICAL)
    end
    sc = with(GitRevWalker(repo)) do walker
        count((i,r)->i!=base_id, walker, oid=snd_id, by=Consts.SORT_TOPOLOGICAL)
    end
    return (fc-1, sc-1)
end

""" git merge [--ff-only] [<committish> | FETCH_HEAD] """
function merge!(repo::GitRepo;
                committish::AbstractString = "",
                branch::AbstractString = "",
                fastforward::Bool = false,
                merge_opts::MergeOptions = MergeOptions(),
                checkout_opts::CheckoutOptions = CheckoutOptions())
    # merge into head branch
    upst_anns = if !isempty(committish) # merge committish into HEAD
        if committish == Consts.FETCH_HEAD # merge FETCH_HEAD
            fheads = fetchheads(repo)
            filter!(fh->fh.ismerge, fheads)
            if isempty(fheads)
                throw(GitError(Error.Merge, Error.ERROR,
                               "There is no fetch reference for this branch."))
            end
            map(fh->GitAnnotated(repo,fh), fheads)
        else # merge commitish
            [GitAnnotated(repo, committish)]
        end
    else
        if !isempty(branch) # merge provided branch into HEAD
            with(GitReference(repo, branch)) do brn_ref
                [GitAnnotated(repo, brn_ref)]
            end
        else # try to get tracking remote branch for the head
            if !isattached(repo)
                throw(GitError(Error.Merge, Error.ERROR,
                               "Repository HEAD is detached. Remote tracking branch cannot be used."))
            end
            if isorphan(repo)
                # this isn't really a merge, but really moving HEAD
                # https://github.com/libgit2/libgit2/issues/2135#issuecomment-35997764
                # try to figure out remote tracking of orphan head

                m = with(GitReference(repo, Consts.HEAD_FILE)) do head_sym_ref
                    match(r"refs/heads/(.*)", fullname(head_sym_ref))
                end
                if m === nothing
                    throw(GitError(Error.Merge, Error.ERROR,
                                   "Unable to determine name of orphan branch."))
                end
                branchname = m.captures[1]
                remotename = with(GitConfig, repo) do cfg
                    LibGit2.get(String, cfg, "branch.$branchname.remote")
                end
                oid = with(GitReference(repo, "refs/remotes/$remotename/$branchname")) do ref
                    LibGit2.GitHash(ref)
                end
                with(GitCommit(repo, oid)) do cmt
                    LibGit2.create_branch(repo, branchname, cmt)
                end
                return true
            else
                with(head(repo)) do head_ref
                    tr_brn_ref = upstream(head_ref)
                    if isnull(tr_brn_ref)
                        throw(GitError(Error.Merge, Error.ERROR,
                                       "There is no tracking information for the current branch."))
                    end
                    try
                        [GitAnnotated(repo, Base.get(tr_brn_ref))]
                    finally
                        close(Base.get(tr_brn_ref))
                    end
                end
            end
        end
    end
    try
        merge!(repo, upst_anns, fastforward,
               merge_opts=merge_opts,
               checkout_opts=checkout_opts)
    finally
        map(close, upst_anns)
    end
end

"""
    LibGit2.rebase!(repo::GitRepo, upstream::AbstractString="", newbase::AbstractString="")

Attempt an automatic merge rebase of the current branch, from `upstream` if provided, or
otherwise from the upstream tracking branch.
`newbase` is the branch to rebase onto. By default this is `upstream`.

If any conflicts arise which cannot be automatically resolved, the rebase will abort,
leaving the repository and working tree in its original state, and the function will throw
a `GitError`. This is roughly equivalent to the following command line statement:

    git rebase --merge [<upstream>]
    if [ -d ".git/rebase-merge" ]; then
        git rebase --abort
    fi

"""
function rebase!(repo::GitRepo, upstream::AbstractString="", newbase::AbstractString="")
    with(head(repo)) do head_ref
        head_ann = GitAnnotated(repo, head_ref)
        upst_ann = if isempty(upstream)
            brn_ref = LibGit2.upstream(head_ref)
            if isnull(brn_ref)
                throw(GitError(Error.Rebase, Error.ERROR,
                               "There is no tracking information for the current branch."))
            end
            try
                GitAnnotated(repo, Base.get(brn_ref))
            finally
                close(brn_ref)
            end
        else
            GitAnnotated(repo, upstream)
        end
        onto_ann  = Nullable{GitAnnotated}(isempty(newbase) ? nothing : GitAnnotated(repo, newbase))
        try
            sig = default_signature(repo)
            try
                rbs = GitRebase(repo, head_ann, upst_ann, onto=onto_ann)
                try
                    while (rbs_op = next(rbs)) !== nothing
                        commit(rbs, sig)
                    end
                    finish(rbs, sig)
                catch err
                    abort(rbs)
                    rethrow(err)
                finally
                    close(rbs)
                end
            finally
                #!isnull(onto_ann) && close(get(onto_ann))
                close(sig)
            end
        finally
            if !isempty(newbase)
                close(Base.get(onto_ann))
            end
            close(upst_ann)
            close(head_ann)
        end
    end
    return head_oid(repo)
end

""" Returns all commit authors """
function authors(repo::GitRepo)
    return with(GitRevWalker(repo)) do walker
        map((oid,repo)->with(GitCommit(repo, oid)) do cmt
                            author(cmt)::Signature
                        end,
            walker) #, by = Consts.SORT_TIME)
    end
end

function snapshot(repo::GitRepo)
    head = GitHash(repo, Consts.HEAD_FILE)
    index = with(GitIndex, repo) do idx; write_tree!(idx) end
    work = try
        with(GitIndex, repo) do idx
            if length(readdir(path(repo))) > 1
                add!(idx, ".")
                write!(idx)
            end
            write_tree!(idx)
        end
    finally
        # restore index
        with(GitIndex, repo) do idx
            read_tree!(idx, index)
            write!(idx)
        end
    end
    State(head, index, work)
end

function restore(s::State, repo::GitRepo)
    head = reset!(repo, Consts.HEAD_FILE, "*")  # unstage everything
    with(GitIndex, repo) do idx
        read_tree!(idx, s.work)            # move work tree to index
        opts = CheckoutOptions(
                checkout_strategy = Consts.CHECKOUT_FORCE |     # check the index out to work
                                    Consts.CHECKOUT_REMOVE_UNTRACKED) # remove everything else
        checkout_index(repo, Nullable(idx), options = opts)

        read_tree!(idx, s.index)  # restore index
    end
    reset!(repo, s.head, Consts.RESET_SOFT) # restore head
end

function transact(f::Function, repo::GitRepo)
    state = snapshot(repo)
    try f(repo) catch
        restore(state, repo)
        rethrow()
    finally
        close(repo)
    end
end

function set_ssl_cert_locations(cert_loc)
    cert_file = isfile(cert_loc) ? cert_loc : Cstring(C_NULL)
    cert_dir  = isdir(cert_loc) ? cert_loc : Cstring(C_NULL)
    cert_file == C_NULL && cert_dir == C_NULL && return
    # TODO FIX https://github.com/libgit2/libgit2/pull/3935#issuecomment-253910017
    #ccall((:git_libgit2_opts, :libgit2), Cint,
    #      (Cint, Cstring, Cstring),
    #      Cint(Consts.SET_SSL_CERT_LOCATIONS), cert_file, cert_dir)
    ENV["SSL_CERT_FILE"] = cert_file
    ENV["SSL_CERT_DIR"] = cert_dir
end

function __init__()
    # Look for OpenSSL env variable for CA bundle (linux only)
    # windows and macOS use the OS native security backends
    old_ssl_cert_dir = Base.get(ENV, "SSL_CERT_DIR", nothing)
    old_ssl_cert_file = Base.get(ENV, "SSL_CERT_FILE", nothing)
    @static if is_linux()
        cert_loc = if "SSL_CERT_DIR" in keys(ENV)
            ENV["SSL_CERT_DIR"]
        elseif "SSL_CERT_FILE" in keys(ENV)
            ENV["SSL_CERT_FILE"]
        else
            # If we have a bundled ca cert file, point libgit2 at that so SSL connections work.
            abspath(ccall(:jl_get_julia_home, Any, ()),Base.DATAROOTDIR,"julia","cert.pem")
        end
        set_ssl_cert_locations(cert_loc)
    end

    err = ccall((:git_libgit2_init, :libgit2), Cint, ())
    err > 0 || throw(ErrorException("error initializing LibGit2 module"))
    REFCOUNT[] = 1

    atexit() do
        if Threads.atomic_sub!(REFCOUNT, UInt(1)) == 1
            # refcount zero, no objects to be finalized
            ccall((:git_libgit2_shutdown, :libgit2), Cint, ())
        end
    end

    @static if is_linux()
        if old_ssl_cert_dir != Base.get(ENV, "SSL_CERT_DIR", "")
            if old_ssl_cert_dir === nothing
                delete!(ENV, "SSL_CERT_DIR")
            else
                ENV["SSL_CERT_DIR"] = old_ssl_cert_dir
            end
        end
        if old_ssl_cert_file != Base.get(ENV, "SSL_CERT_FILE", "")
            if old_ssl_cert_file === nothing
                delete!(ENV, "SSL_CERT_FILE")
            else
                ENV["SSL_CERT_FILE"] = old_ssl_cert_file
            end
        end
    end
end

end # module

max_stars_repo_name: oxinabox/julia

max_issues_repo_name: oxinabox/julia

max_forks_repo_name: oxinabox/julia


text:
# # ## model
# include("ci_model.jl")
# model = RoboDojo.centroidal_quadruped

# # ## horizon
# T = 101
# Tm = 51
# T_fix = 10

# # ## Time step
# tf = 1.0
# h = 0.01

# # ## feet templates
# include("template.jl")

# function configuration(model;
#     body_position=[0.0; 0.0; 0.15],
#     body_orientation=[0.0; 0.0; 0.0],
#     foot1_position=[0.15 - 0.025; 0.1; 0.0],
#     foot2_position=[0.1 - 0.025;-0.1; 0.0],
#     foot3_position=[-0.1 - 0.025; 0.1; 0.0],
#     foot4_position=[-0.05 - 0.025;-0.1; 0.0])
#     [
#         body_position;
#         body_orientation;
#         foot1_position;
#         foot2_position;
#         foot3_position;
#         foot4_position;
#     ]
# end

# q1 = configuration(model)

# # ## visualize
# vis = Visualizer()
# render(vis)
# # q_sol = state_to_configuration([x[1:nx] for x in x_sol])
# RoboDojo.visualize!(vis, RoboDojo.centroidal_quadruped, [q1], Δt=h);

# # feet positions
# pf1 = q1[6 .+ (1:3)]
# pf2 = q1[9 .+ (1:3)]

# pf3 = q1[12 .+ (1:3)]
# pf4 = q1[15 .+ (1:3)]

# strd = 2 * (pf1 - pf2)[1]

# q_shift1 = zeros(model.nq)
# q_shift1[1] = 0.5 * strd
# q_shift1[10] = strd
# q_shift1[13] = strd

# qM = copy(q1) + q_shift1

# q_shift2 = zeros(model.nq)
# q_shift2[1] = 0.5 * strd
# q_shift2[7] = strd
# q_shift2[16] = strd

# qT = copy(qM) + q_shift2

# q_ref = [q1, linear_interpolation(q1, qM, 30)..., linear_interpolation(qM, qT, 30)...]
# visualize!(vis, model, q_ref)

# zh = 0.05
# xf1_el, zf1_el = ellipse_traj(pf1[1], pf1[1] + strd, zh, Tm - T_fix)
# xf1 = [[pf1[1] for t = 1:Tm + T_fix + 1]..., xf1_el[2:end]...]
# zf1 = [[pf1[3] for t = 1:Tm + T_fix + 1]..., zf1_el[2:end]...]
# pf1_ref = [[xf1[t]; pf1[2];  zf1[t]] for t = 1:T + 1]

# xf4_el, zf4_el = ellipse_traj(pf4[1], pf4[1] + strd, zh, Tm - T_fix)
# xf4 = [[pf4[1] for t = 1:Tm + T_fix + 1]..., xf4_el[2:end]...]
# zf4 = [[pf4[3] for t = 1:Tm + T_fix + 1]..., zf4_el[2:end]...]
# pf4_ref = [[xf4[t]; pf4[2]; zf4[t]] for t = 1:T + 1]

# xf2_el, zf2_el = ellipse_traj(pf2[1], pf2[1] + strd, zh, Tm - T_fix)
# xf2 = [[xf2_el[1] for t = 1:T_fix + 1]..., xf2_el..., [xf2_el[end] for t = 1:Tm-1 + T_fix]...]
# zf2 = [[zf2_el[1] for t = 1:T_fix + 1]..., zf2_el..., [zf2_el[end] for t = 1:Tm-1 + T_fix]...]
# pf2_ref = [[xf2[t]; pf2[2]; zf2[t]] for t = 1:T + 1]

# xf3_el, zf3_el = ellipse_traj(pf3[1], pf3[1] + strd, zh, Tm - T_fix)
# xf3 = [[xf3_el[1] for t = 1:T_fix + 1]..., xf3_el..., [xf3_el[end] for t = 1:Tm-1]...]
# zf3 = [[zf3_el[1] for t = 1:T_fix + 1]..., zf3_el..., [zf3_el[end] for t = 1:Tm-1]...]
# pf3_ref = [[xf3[t]; pf3[2]; zf3[t]] for t = 1:T + 1]

# using Plots
# tr = range(0, stop = tf, length = T+1)
# plot(tr, hcat(pf1_ref...)')
# plot!(tr, hcat(pf4_ref...)')

# plot!(tr, hcat(pf2_ref...)')
# plot!(tr, hcat(pf3_ref...)')

# q_ref = [q1, linear_interpolation(q1, qM, Tm)[1:end-1]..., linear_interpolation(qM, qT, Tm)...,]

# for (t, q) in enumerate(q_ref)
#     q[6 .+ (1:3)] = pf1_ref[t]
#     q[9 .+ (1:3)] = pf2_ref[t]
#     q[12 .+ (1:3)] = pf3_ref[t]
#     q[15 .+ (1:3)] = pf4_ref[t]
# end

# x_ref = [[q_ref[t]; q_ref[t+1]] for t = 1:length(q_ref)-1]
# visualize!(vis, model, q_ref, Δt=h)

# # ## centroidal_quadruped
# model = RoboDojo.centroidal_quadruped
# nx = 2 * model.nq
# nc = 4 # model.nc
# nu = model.nu + nc + 4 * nc + nc + 4 * nc + 1
# nθ = 5

# RoboDojo.mass_matrix(model, ones(model.nq))
# RoboDojo.dynamics_bias(model, ones(model.nq), ones(model.nq))
# RoboDojo.contact_jacobian(model, ones(model.nq))[1:12, :]

# # ## model
# d1 = DTO.Dynamics((y, x, u, w) -> centroidal_quadruped_dyn1(model, RoboDojo.mass_matrix, RoboDojo.dynamics_bias, [h], y, x, u, w), nx + nθ + nx + model.nu, nx, nu)
# dt = DTO.Dynamics((y, x, u, w) -> centroidal_quadruped_dynt(model, RoboDojo.mass_matrix, RoboDojo.dynamics_bias, [h], y, x, u, w), nx + nθ + nx + model.nu, nx + nθ + nx + model.nu, nu)

# dyn = [d1, [dt for t = 2:T-1]...]

# # ## objective
# obj = DTO.Cost{Float64}[]

# for t = 1:T

#     if t == 1
#         function obj1(x, u, w)
#             J = 0.0
#             v = (x[model.nq .+ (1:model.nq)] - x[1:model.nq]) ./ h
#             J += 0.5 * 1.0 * dot(v, v)
#             J += 0.5 * transpose(x[1:nx] - x_ref[t]) * Diagonal(100.0 * ones(nx)) * (x[1:nx] - x_ref[t])
#             J += 0.5 * transpose(u) * Diagonal([ones(model.nu); zeros(nu - model.nu)]) * u
#             J += 1000.0 * u[end] # slack
#             return J
#         end
#         push!(obj, DTO.Cost(obj1, nx, nu))
#     elseif t == T
#         function objT(x, u, w)
#             J = 0.0
#             v = (x[model.nq .+ (1:model.nq)] - x[1:model.nq]) ./ h
#             J += 0.5 * 1.0 * dot(v, v)
#             J += 0.5 * transpose(x[1:nx] - x_ref[t]) * Diagonal(100.0 * ones(nx)) * (x[1:nx] - x_ref[t])
#             return J
#         end
#         push!(obj, DTO.Cost(objT, nx + nθ + nx + model.nu, 0))
#     else
#         function objt(x, u, w)
#             J = 0.0
#             v = (x[model.nq .+ (1:model.nq)] - x[1:model.nq]) ./ h
#             J += 0.5 * 1.0 * dot(v, v)
#             J += 0.5 * transpose(x[1:nx] - x_ref[t]) * Diagonal(100.0 * ones(nx)) * (x[1:nx] - x_ref[t])
#             J += 0.5 * transpose(u) * Diagonal([ones(model.nu); zeros(nu - model.nu)]) * u
#             J += 1000.0 * u[end] # slack
#             return J
#         end
#         push!(obj, DTO.Cost(objt, nx + nθ + nx + model.nu, nu))
#     end
# end

# # ## constraints
# # initial condition
# xl1 = x_ref[1]
# xu1 = [q_ref[1]; q_ref[1]]

# # stage
# xlt = [-Inf * ones(nx); -Inf * ones(nθ); -Inf * ones(nx); -Inf * ones(model.nu)]
# xut = [Inf * ones(nx); Inf * ones(nθ); Inf * ones(nx); Inf * ones(model.nu)]

# # final condition
# xlT = [q_ref[end]; q_ref[end]; -Inf * ones(nθ); -Inf * ones(nx); -Inf * ones(model.nu)]
# xuT = [q_ref[end]; q_ref[end]; Inf * ones(nθ); Inf * ones(nx); Inf * ones(model.nu)]

# ul = [-Inf * ones(model.nu); zeros(nu - model.nu)]
# uu = [Inf * ones(model.nu); Inf * ones(nu - model.nu)]

# bnd1 = DTO.Bound(nx, nu, state_lower=xl1, state_upper=xu1, action_lower=ul, action_upper=uu)
# bndt = DTO.Bound(nx + nθ + nx + model.nu, nu, state_lower=xlt, state_upper=xut, action_lower=ul, action_upper=uu)
# bndT = DTO.Bound(nx + nθ + nx + model.nu, 0, state_lower=xlT, state_upper=xuT)
# bnds = [bnd1, [bndt for t = 2:T-1]..., bndT];

# function constraints_1(x, u, w)
#     [
#      # equality (16)
#      contact_constraints_equality(model, h, x, u, w);
#      # inequality (28)
#      contact_constraints_inequality_1(model, h, x, u, w);
#     ]
# end

# function constraints_t(x, u, w)
#     [
#      # equality (16)
#      contact_constraints_equality(model, h, x, u, w);
#      # inequality (32)
#      contact_constraints_inequality_t(model, h, x, u, w);
#     ]
# end

# function constraints_T(x, u, w)
#     [
#      # inequality (8)
#      contact_constraints_inequality_T(model, h, x, u, w);
#     ]
# end

# con1 = DTO.Constraint(constraints_1, nx, nu, idx_ineq=collect(16 .+ (1:28)))
# cont = DTO.Constraint(constraints_t, nx + nθ + nx + model.nu, nu, idx_ineq=collect(16 .+ (1:32)))
# conT = DTO.Constraint(constraints_T, nx + nθ + nx + model.nu, nu, idx_ineq=collect(0 .+ (1:8)))
# cons = [con1, [cont for t = 2:T-1]..., conT];

# # ## problem
# p = DTO.solver(dyn, obj, cons, bnds,
#     options=DTO.Options(
#         tol=1.0e-2,
#         constr_viol_tol=1.0e-2,
#         ))

# # ## initialize
# x_interpolation = [x1, [[x1; zeros(nθ); zeros(nx); zeros(model.nu)] for t = 2:T]...]
# u_guess = [1.0e-4 * rand(nu) for t = 1:T-1] # may need to run more than once to get good trajectory
# DTO.initialize_states!(p, x_interpolation)
# DTO.initialize_controls!(p, u_guess)

# # ## solve
# @time DTO.solve!(p)

# # ## solution
# x_sol, u_sol = DTO.get_trajectory(p)
# @show x_sol[1]
# @show x_sol[T]
# sum([u[end] for u in u_sol[1:end-1]])

# # ## visualize
# vis = Visualizer()
# render(vis)
# # q_sol = state_to_configuration([x[1:nx] for x in x_sol])
# RoboDojo.visualize!(vis, RoboDojo.centroidal_quadruped, x_sol, Δt=h);


text:
# Note that this script can accept some limited command-line arguments, run
# `julia build_tarballs.jl --help` to see a usage message.
using BinaryBuilder, Pkg
using Base.BinaryPlatforms

name = "libpolymake_julia"
version = v"0.5.0"

julia_versions = [v"1.6.0", v"1.7.0", v"1.8.0"]

# Collection of sources required to build libpolymake_julia
sources = [
    ArchiveSource("https://github.com/oscar-system/libpolymake-julia/archive/v$(version).tar.gz",
                  "5af8ccce9928b05c2c30f6adcddc7f07bdbef79d69d7d28aa6671846e742d2fb"),
]

# Bash recipe for building across all platforms
script = raw"""
# remove $libdir from LD_LIBRARY_PATH as this causes issues with perl
if [[ -n "$LD_LIBRARY_PATH" ]]; then
LD_LIBRARY_PATH=$(echo -n $LD_LIBRARY_PATH | sed -e "s|[:^]$libdir\w*|:|g")
fi

cmake libpolymake-j*/ -B build \
   -DJulia_PREFIX="$prefix" \
   -DCMAKE_INSTALL_PREFIX="$prefix" \
   -DCMAKE_FIND_ROOT_PATH="$prefix" \
   -DCMAKE_TOOLCHAIN_FILE="${CMAKE_TARGET_TOOLCHAIN}" \
   -DCMAKE_BUILD_TYPE=Release

VERBOSE=ON cmake --build build --config Release --target install -- -j${nproc}

install_license libpolymake-j*/LICENSE.md
"""

# These are the platforms we will build for by default, unless further
# platforms are passed in on the command line
platforms = [
    Platform("x86_64", "linux"; libc="glibc"),
    Platform("x86_64", "macos"),
]
platforms = expand_cxxstring_abis(platforms)

# expand julia platforms
julia_platforms = []
foreach(platforms) do platform
    foreach(julia_versions) do jv
        p = deepcopy(platform)
        BinaryPlatforms.add_tag!(p.tags, "julia_version", string(jv))
        push!(julia_platforms, p)
    end
end

# The products that we will ensure are always built
products = [
    ExecutableProduct("polymake_run_script", :polymake_run_script),
    LibraryProduct("libpolymake_julia", :libpolymake_julia),
    FileProduct("share/libpolymake_julia/type_translator.jl",:type_translator),
]

# Dependencies that must be installed before this package can be built
dependencies = [
    BuildDependency("libjulia_jll"),
    BuildDependency("GMP_jll"),
    BuildDependency("MPFR_jll"),
    Dependency("CompilerSupportLibraries_jll"),
    Dependency("FLINT_jll", compat = "~200.800"),
    Dependency("libcxxwrap_julia_jll"),
    Dependency("polymake_jll"; compat = "~400.500.0"),
]

# Build the tarballs, and possibly a `build.jl` as well.
build_tarballs(ARGS, name, version, sources, script, julia_platforms, products, dependencies;
    preferred_gcc_version=v"8",
    julia_compat = "1.6")

max_stars_repo_name: plut/Yggdrasil

max_issues_repo_name: plut/Yggdrasil

max_forks_repo_name: plut/Yggdrasil


text:
module MuZero

    include("common.jl")
    include("action.jl")
    include("network_output.jl")
    include("node.jl")
    include("target.jl")
    include("abstract_game.jl")
    include("abstract_state.jl")
    include("min_max_stats.jl")
    include("muzero_game.jl")
    include("muzero_config.jl")
    include("replay_buffer.jl")
    include("replay_buffers.jl")
    include("network.jl")
    include("networks/uniform_policy.jl")
    include("training_batch_tensor.jl")
    include("training_sample.jl")
    include("training_sample_result.jl")
    include("training_batch.jl")
    include("action_history.jl")
    include("target_loss.jl")
    include("loss.jl")
    include("networks/incremental.jl")
    include("training_tests/training_tests.jl")
    include("training_tests/policy_tests.jl")
    include("training_tests/policyreward_tests.jl")
    include("training_tests/policyvalue_tests.jl")
    include("training_tests/policyvaluereward_tests.jl")
    include("training_tests/reward_tests.jl")
    include("training_tests/value_tests.jl")
    include("training_tests/valuereward_tests.jl")
    include("training_tests/recurrent_rvp_test.jl")
    include("training_tests/recurrent_rvp_tests.jl")
    include("training_tests/recurrent_rvp_test_result.jl")
    include("training_tests/recurrent_rvp_test_results.jl")
    include("policy_test_result.jl")
    include("policy_test_results.jl")
    include("policy_value_test_result.jl")
    include("policy_value_test_results.jl")
    include("policy_acc.jl")
    include("learner.jl")
    include("mu.jl")
    include("image.jl")
    include("piece.jl")
    include("abstract_board_state.jl")
    include("abstract_board_game.jl")
    include("marker.jl")

    export AbstractState, AbstractEnv, Network, AbstractImage,
        ReplayBuffer, TrainingSample, selfplay!, fit!,
        Node, MuZeroConfig, make_board_game_config, Incremental,
        current_image, Image, next_to_play, legal_actions,
        last_reward, next_state, action_space_size, action_image, islegal,
        apply!, make_image, get_state, make_image_label, to_play_at, uniform_policy,
        discount, initial_inference, recurrent_inference, SingleNetworkOutput, NetworkOutput,
        value, reward, policy_logit, policy, hidden_state, value_iteration, getstatesplus,
        getstates, Counter, increment!, hex_str, key, get_df, encode, getlosses,
        Learner, randtrainingbatch, randgame, getnumactors, getconfig, gettestfn,
        losses, accuracy, Counter, losses_png, svg, TrainingSampleSVG, to_play,
        cartesian_coords_to_action, calc_cell_states, training_result, PolicyTests,
        PolicyTest, state_type, policy_testset,
        PLAYER_1, PLAYER_2, PolicyTestResult, PolicyTestResultSVG, tests, getpolicytestresults,
        PolicyTestResults, PolicyTestResultsSVG, gridsvg, policypredsvg, policytestsvg,
        targetsvg, Target, randtrainingsample, new_training_batch!, decode,
        AbstractBoardState, num_rows, num_cols, get_marker,
        player1_markers, player2_markers, player1_markers, all_markers, get_marker,
        step!, init_game, Marker, Piece, plain, AbstractBoardStateSVG,
        image_scale, image_title_offset, BoardGameSVG, piece_idx, game_is_won,
        get_winner, get_piece, get_image, get_coordinate, actions, uniformpolicy,
        get_boardgame_config, piece_matrix, get_action_image, num_cells, copy_at,
        diff_coord, MuZeroGame, get_coord, get_pieces, get_piece_idx, piece_count, piece,
        init_state, Action, num_players, AbstractAction, getpolicytests, show_policy_tests,
        show_tests, show_pv_tests, PolicyValueTest, gettraindf, gettraindfall,
        PolicyValueTests, show_policyvalue_tests, show_reward_tests, RewardTest,
        RewardTestSVG, RewardTests, RewardTestsSVG, get_reward,
        show_game, getdir, ensure_pathto_exists, save!, load!,
        StepRecord, tensor, images, getmodelpath, get_loss, get_accuracy,
        get_steps, tensorize, get_tests_cb, TargetLoss, Loss, mean10, makepolicytests,
        mean100, mean1000, mean10000, meanx, df_cols, PolicyAcc, runtests!, getpct,
        test_network, training_network, LearnerCallback, AbstractEnv, df, PolicyTestSVG,
        MuZeroGameSVG, randpolicytest, randpolicytestresult, showresults, showpolicytestresults,
        getresults, showlosses, new_test_network, getpolicy, clearreplaybuffer!, stopplaying!,
        stoptraining!, getresultsfull, showresultsfull, AbstractLearner, saveconfig, load,
        getconfigpath, savewritablereplaybuffer, loadreplaybuffers!, play!, randpolicyvaluetest,
        getpolicyvaluetests, getpolicyvaluetestresults, getpolicyvaluetestresult, getpvtestresult,
        findmuzerogames, getpolicy, runtests, get_nets, getpolicyacc, getpolicyfails,
        new_training_network, loadtrain!, reanalyzebuffer, showpolicyvaluetestresults, getdf,
        getvalue, getlosses, reanalyze!, getstate, runpvtests, RecurrentRVPTest, RecurrentRVPTests,
        trianglelr, updateschedule!, newcycleschedule, cycleschedule, AbstractEnvAction, calcnumreanalyzed

    export getrrvptests, randrrvptest, runrrvptests, showrrvptestresults, ReplayBuffers, updatecallback!

    export RecurrentRVPTestResult, RecurrentRVPTestResults, getplaynet, newgames, is_terminal, alltrue,
    movesmaxedout, getgame, add_exploration_noise, store_search_statistics, history, select_action,
    action_history, run_mcts, expand_node!, policy_logits

    export RecurrentRVPTestResult, RecurrentRVPTestResults, gettotalreanalyses, valormissing, savegameplaystats!

    # @todo Temporary. Should make private
    export byte_idx_to_coord, coord_to_byte_idx, ReplayBufferOld, savemodel, enable_test_mode_if_needed!,
    getreplaybuffersdir, getwritablereplaybuffer, play_game, loadplayifnewer!, atcapacity,
    needsreanalyze, reanalyze, findbuffertoreanalyze, playgames, timetoreanalyze

    export reward_matrix, value_matrix, policy_matrix, readdirexpanduser, getbufferstats, getavggamestep,
    get_summary, getlatestsummaryondisk, getreplaybuffersdir, getgamestepquality, getplaysummary,
    saveplaysummary, loadplaysummary, deserializeexpanduser, getstatspath, savereplaybufferstats

end


text:
module AzSessions

using Base64, Dates, HTTP, JSON, JSONWebTokens, MbedTLS, Sockets

const _manifest = Dict("client_id"=>"", "client_secret"=>"", "tenant"=>"", "protocal"=>"")

manifestpath() = joinpath(homedir(), ".azsessions")
manifestfile() = joinpath(manifestpath(), "manifest.json")

"""
    AzSessions.write_manifest(;client_id="", client_secret="", tenant="", protocal="")

Write an AzSessions manifest file (~/.azsessions/manifest.json).  The
manifest file contains account specific credentials.

# Notes

## client secret
The client can be configured such that the `client_secret` is not
required for the authorization-code-flow and device-code-flow.  In this
scenario, one may choose to omit setting the `client_secret` in the manifest.
For example:
```julia
AzSessions.write_manifest(;client_id="myclientid", tenant="mytenant")
```

## protocal
The protocal is one of "AzAuthCodeFlowCredentials", "AzDeviceCodeFlowCredentials", "AzClientCredentials"
and "AzVMCredentials".  If the default `protocal=""` is chosen for the manifest, then `AzSession()` will
default to `AzDeviceCodeFlowCredentials`.  The protocal in the manifest can always be over-ridden using
the `protocal` argument to `AzSession`.
"""
function write_manifest(;client_id="", client_secret = "", tenant="", protocal="")
    manifest = Dict("client_id"=>client_id, "client_secret"=>client_secret, "tenant"=>tenant, "protocal"=>string(protocal))
    try
        isdir(manifestpath()) || mkdir(manifestpath(); mode=0o700)
        write(manifestfile(), json(manifest, 1))
        chmod(manifestfile(), 0o600)
    catch e
        @error "Failed to write manifest file, $(AzSessions.manifestfile())"
        throw(e)
    end
end

function load_manifest()
    if isfile(manifestfile())
        try
            manifest = JSON.parse(read(manifestfile(), String))
            for key in keys(_manifest)
                _manifest[key] = get(manifest, key, "")
            end
        catch e
            @error "Manifest file ($(AzSessions.manifestfile())) is not valid JSON"
            throw(e)
        end
    else
        @error "Manifest file ($(AzSessions.manifestfile())) does not exist.  Use AzSessions.write_manifest to generate a manifest file."
    end
end

#
# retry logic
#
function isretryable(e::HTTP.StatusError)
    e.status ∈ (404,429) && (return true)
    e.status >= 500 && (return true)
    false
end
isretryable(e::Base.IOError) = true
isretryable(e::HTTP.IOExtras.IOError) = isretryable(e.e)
isretryable(e::Base.EOFError) = true
isretryable(e::Sockets.DNSError) = true
isretryable(e) = false

function retrywarn(i, s, e)
    if isa(e, HTTP.StatusError)
        _e = JSON.parse(String(e.response.body))
        msg = get(_e, "error", "")
        @warn "$(e.status): $msg -- sleeping for $s seconds"
    else
        @warn "$(typeof(e)) -- sleeping for $s seconds"
    end
end

macro retry(retries, ex::Expr)
    quote
        local r
        for i = 1:$(esc(retries))
            try
                r = $(esc(ex))
                break
            catch e
                (i <= $(esc(retries)) && isretryable(e)) || rethrow(e)
                maximum_backoff = 60
                s = min(2.0^(i-1), maximum_backoff) + rand()
                retrywarn(i, s, e)
                sleep(s)
            end
        end
        r
    end
end

abstract type AzSessionAbstract end

"""
    token(session)

Return the OAuth2 token associate with `session`.
"""
function token end

"""
    scrub!(session)

Remove sensitive information from `session` (e.g. token, client secret)
"""
function scrub! end

#
# Client credentials
#
struct AzClientCredentials end
mutable struct AzClientCredentialsSession <: AzSessionAbstract
    protocal::String
    client_id::String
    client_secret::String
    expiry::DateTime
    resource::String
    tenant::String
    token::String
end
function AzClientCredentialsSession(;
        client_id = _manifest["client_id"],
        client_secret = _manifest["client_secret"],
        resource = "https://management.azure.com/",
        tenant = _manifest["tenant"])
    client_secret == "" && error("AzClientCredentials requires client_secret, but got client_secret=\"\"")
    AzClientCredentialsSession(string(AzClientCredentials), client_id, client_secret, now(Dates.UTC), resource, tenant, "")
end
function AzClientCredentialsSession(d::Dict)
    AzClientCredentialsSession(
        d["protocal"],
        d["client_id"],
        d["client_secret"],
        DateTime(d["expiry"]),
        d["resource"],
        d["tenant"],
        d["token"])
end

function Base.copy(session::AzClientCredentialsSession)
    AzClientCredentialsSession(
        session.protocal,
        session.client_id,
        session.client_secret,
        session.expiry,
        session.resource,
        session.tenant,
        session.token)
end

function samesession(session1::AzClientCredentialsSession, session2::AzClientCredentialsSession)
    session1.protocal == session2.protocal &&
        session1.client_id == session2.client_id &&
        session1.client_secret == session2.client_secret &&
        session1.resource == session2.resource &&
        session1.tenant == session2.tenant
end

function token(session::AzClientCredentialsSession)
    session.token != "" && now(Dates.UTC) < session.expiry && return session.token

    r = @retry 10 HTTP.request(
        "POST",
        "https://login.microsoft.com/$(session.tenant)/oauth2/token",
        Dict("Content-Type" => "application/x-www-form-urlencoded"),
        "grant_type=client_credentials&client_id=$(session.client_id)&client_secret=$(HTTP.escapeuri(session.client_secret))&resource=$(HTTP.escapeuri(session.resource))",
        retry = false)

    rbody = JSON.parse(String(r.body))
    session.token = rbody["access_token"]
    session.expiry = now(Dates.UTC) + Dates.Second(rbody["expires_in"])

    session.token
end

function scrub!(session::AzClientCredentialsSession)
    session.token = ""
    session.client_secret = ""
    session
end

Base.show(io::IO, session::AzClientCredentialsSession) = write(io, "Azure client credentials session")

#
# VirtualMachine credentials
#
struct AzVMCredentials end
mutable struct AzVMSession <: AzSessionAbstract
    protocal::String
    expiry::DateTime
    resource::String
    token::String
end
function AzVMSession(;resource = "https://management.azure.com/")
    AzVMSession(string(AzVMCredentials), now(Dates.UTC), resource, "")
end
function AzVMSession(d::Dict)
    AzVMSession(
        d["protocal"],
        DateTime(d["expiry"]),
        d["resource"],
        d["token"])
end

function Base.copy(session::AzVMSession)
    AzVMSession(
        session.protocal,
        session.expiry,
        session.resource,
        session.token)
end

function samesession(session1::AzVMSession, session2::AzVMSession)
    session1.protocal == session2.protocal && session1.resource == session2.resource
end

function token(session::AzVMSession)
    session.token != "" && now(Dates.UTC) < session.expiry && return session.token

    r = @retry 10 HTTP.request(
        "GET",
        "http://169.254.169.254/metadata/identity/oauth2/token?api-version=2018-02-01&resource=$(session.resource)",
        Dict("Metadata"=>"true"),
        retry = false)

    rbody = JSON.parse(String(r.body))
    session.token = rbody["access_token"]
    session.expiry = now(Dates.UTC) + Dates.Second(rbody["expires_in"])

    session.token
end

function scrub!(session::AzVMSession)
    session.token = ""
    session
end

Base.show(io::IO, session::AzVMSession) = write(io, "Azure virtual machine credentials session")

function mergescopes(scope1, scope2)
    scopes1 = split(scope1, (' ', '+'))
    scopes2 = split(scope2, (' ', '+'))
    join(union(scopes1, scopes2), '+')
end

#
# Authorization code flow credentials
#
struct AzAuthCodeFlowCredentials end
mutable struct AzAuthCodeFlowSession <: AzSessionAbstract
    protocal::String
    client_id::String
    expiry::DateTime
    id_token::String
    lock::Bool
    redirect_uri::String
    refresh_token::String
    scope::String
    scope_auth::String
    tenant::String
    token::String
end
function AzAuthCodeFlowSession(;
        client_id = _manifest["client_id"],
        redirect_uri = "http://localhost:44300/reply",
        scope = "openid+offline_access+https://management.azure.com/user_impersonation",
        scope_auth = "openid+offline_access+https://management.azure.com/user_impersonation+https://storage.azure.com/user_impersonation",
        tenant = _manifest["tenant"])
    AzAuthCodeFlowSession(string(AzAuthCodeFlowCredentials), client_id, now(Dates.UTC), "", false, redirect_uri, "", scope, mergescopes(scope, scope_auth), tenant, "")
end
function AzAuthCodeFlowSession(d::Dict)
    AzAuthCodeFlowSession(
        d["protocal"],
        d["client_id"],
        DateTime(d["expiry"]),
        d["id_token"],
        d["lock"],
        d["redirect_uri"],
        d["refresh_token"],
        d["scope"],
        d["scope_auth"],
        d["tenant"],
        d["token"])
end

function AzSession(session::AzAuthCodeFlowSession; scope="", lazy=false)
    scope == "" && (scope = session.scope)
    _session = AzAuthCodeFlowSession(
        session.protocal,
        session.client_id,
        session.expiry,
        session.id_token,
        session.lock,
        session.redirect_uri,
        session.refresh_token,
        scope,
        session.scope_auth,
        session.tenant,
        session.token)
    lazy || token(_session)
    _session
end

function Base.copy(session::AzAuthCodeFlowSession)
    AzAuthCodeFlowSession(
        session.protocal,
        session.client_id,
        session.expiry,
        session.id_token,
        session.lock,
        session.redirect_uri,
        session.refresh_token,
        session.scope,
        session.scope_auth,
        session.tenant,
        session.token)
end

function samesession(session1::AzAuthCodeFlowSession, session2::AzAuthCodeFlowSession)
    session1.protocal == session2.protocal &&
        session1.client_id == session2.client_id &&
        session1.redirect_uri == session2.redirect_uri &&
        samescope(session1.scope, session2.scope) &&
        samescope(session1.scope_auth, session2.scope_auth) &&
        session1.tenant == session2.tenant
end

session_has_tokens(session::AzAuthCodeFlowSession) = session.token != "" && session.refresh_token != ""

function update_session_from_cached_session!(session::AzAuthCodeFlowSession, cached_session::AzAuthCodeFlowSession)
    session.expiry = cached_session.expiry
    session.id_token = cached_session.id_token
    session.refresh_token = cached_session.refresh_token
    session.token = cached_session.token
end

function audience_from_token(token)
    local audience
    try
        decodedJWT = JSONWebTokens.decode(JSONWebTokens.None(), token)
        audience = get(decodedJWT, "aud", "")
    catch
        @warn "Unable to retrieve audience from token."
        audience = ""
    end
    audience
end

function audience_from_scope(scope)
    scopes = split(scope, ('+',' '))
    i = findfirst(_scope->startswith(_scope, "https://"), scopes)
    "https://"*split(replace(scopes[i], "https://"=>""), '/')[1]
end

function token(session::AzAuthCodeFlowSession, bootstrap=false)
    while session.lock
        sleep(1)
    end
    session.lock = true

    # use the existing token:
    if session.token != "" && now(Dates.UTC) < session.expiry && audience_from_token(session.token) == audience_from_scope(session.scope)
        session.lock = false
        return session.token
    end

    # use the refresh token to get a new token:
    if session.refresh_token != "" && refresh_token(session)
        session.lock = false
        return session.token
    end

    if bootstrap_token_from_cache!(session, bootstrap)
        session.lock = false
        return ""
    end

    # otherwise, user is required to authenticate:
    port = parse(Int, parse(HTTP.URI, session.redirect_uri).port)
    state = rand(Int)
    auth_code = ""

    @debug "starting server..."
    local server
    try
        server = Sockets.listen(Sockets.localhost, port)
    catch
        error("AzSessions: there is already a server listening on port $port")
    end
    tsk = @async HTTP.serve(Sockets.localhost, port; server=server) do request::HTTP.Request
        queries = split(parse(HTTP.URI, request.target).query, '&')
        for query in queries
            q = split(query, '=')
            if q[1] == "code"
                auth_code = q[2]
                break
            end
        end
        HTTP.Response(200, "Logged in via AzSessions.jl")
    end

    authcode_uri = "https://login.microsoft.com/$(session.tenant)/oauth2/v2.0/authorize?client_id=$(session.client_id)&response_type=code&redirect_uri=$(session.redirect_uri)&response_mode=query&scope=$(session.scope_auth)&state=$state&prompt=select_account"

    exitcode = 1
    if Sys.iswindows()
        cmd = get(ENV, "COMSPEC", "cmd")
        _authcode_uri = replace(authcode_uri, "&"=>"^&")
        c = open(`$cmd /c start $_authcode_uri`)
        wait(c)
        exitcode = c.exitcode
    elseif Sys.islinux()
        c = open(`gio open $authcode_uri`)
        wait(c)
        exitcode = c.exitcode
    end

    if exitcode != 0
        @info "Failed to open browser. To authenticate, please open the following url on the local machine:\n\t$authcode_uri"
    end

    while auth_code == ""
        sleep(1)
    end
    close(server)

    token_uri = "https://login.microsoftonline.com/$(session.tenant)/oauth2/v2.0/token"
    token_body = "client_id=$(session.client_id)&scope=$(session.scope)&code=$auth_code&redirect_uri=$(session.redirect_uri)&grant_type=authorization_code"

    @debug "trading auth code for token..."
    r = @retry 10 HTTP.request(
        "POST",
        token_uri,
        Dict("Content-Type"=>"application/x-www-form-urlencoded"),
        token_body;
        retry = false)

    rbody = JSON.parse(String(r.body))
    session.token = rbody["access_token"]
    session.id_token = get(rbody, "id_token", "") # only exists if openid is used in the scope
    session.refresh_token = get(rbody, "refresh_token", "") # online exists if offline_access is used in the scope
    session.expiry = now(Dates.UTC) + Dates.Second(rbody["expires_in"])

    session_has_tokens(session) && record_session(session)
    session.lock = false
    session.token
end

function scrub!(session::AzAuthCodeFlowSession)
    session.token = ""
    session.id_token = ""
    session.refresh_token = ""
    session
end

Base.show(io::IO, session::AzAuthCodeFlowSession) = write(io, "Azure authorization code flow session")

#
# Device code flow credentials
#
struct AzDeviceCodeFlowCredentials end
mutable struct AzDeviceCodeFlowSession <: AzSessionAbstract
    protocal::String
    client_id::String
    expiry::DateTime
    id_token::String
    lock::Bool
    refresh_token::String
    scope::String
    scope_auth::String
    tenant::String
    token::String
end
function AzDeviceCodeFlowSession(;
        client_id = _manifest["client_id"],
        scope = "openid+offline_access+https://management.azure.com/user_impersonation",
        scope_auth = "openid+offline_access+https://management.azure.com/user_impersonation+https://storage.azure.com/user_impersonation",
        tenant = _manifest["tenant"])
    AzDeviceCodeFlowSession(string(AzDeviceCodeFlowCredentials), client_id, now(Dates.UTC), "", false, "", scope, mergescopes(scope, scope_auth), tenant, "")
end
function AzDeviceCodeFlowSession(d::Dict)
    AzDeviceCodeFlowSession(
        d["protocal"],
        d["client_id"],
        DateTime(d["expiry"]),
        d["id_token"],
        d["lock"],
        d["refresh_token"],
        d["scope"],
        d["scope_auth"],
        d["tenant"],
        d["token"])
end

function AzSession(session::AzDeviceCodeFlowSession; scope="", lazy=false)
    scope == "" && (scope = session.scope)
    _session = AzDeviceCodeFlowSession(
        session.protocal,
        session.client_id,
        session.expiry,
        session.id_token,
        session.lock,
        session.refresh_token,
        scope,
        session.scope_auth,
        session.tenant,
        session.token)
    lazy || token(_session)
    _session
end

function Base.copy(session::AzDeviceCodeFlowSession)
    AzDeviceCodeFlowSession(
        session.protocal,
        session.client_id,
        session.expiry,
        session.id_token,
        session.lock,
        session.refresh_token,
        session.scope,
        session.scope_auth,
        session.tenant,
        session.token)
end

function samesession(session1::AzDeviceCodeFlowSession, session2::AzDeviceCodeFlowSession)
    session1.protocal == session2.protocal &&
        session1.client_id == session2.client_id &&
        samescope(session1.scope, session2.scope) &&
        session1.tenant == session2.tenant
end

session_has_tokens(session::AzDeviceCodeFlowSession) = session.token != "" && session.refresh_token != ""

function update_session_from_cached_session!(session::AzDeviceCodeFlowSession, cached_session::AzDeviceCodeFlowSession)
    session.expiry = cached_session.expiry
    session.id_token = cached_session.id_token
    session.refresh_token = cached_session.refresh_token
    session.token = cached_session.token
end

function token(session::AzDeviceCodeFlowSession, bootstrap=false)
    while session.lock
        sleep(1)
    end
    session.lock = true

    # use the existing token:
    if session.token != "" && now(Dates.UTC) < session.expiry && audience_from_scope(session.scope) == audience_from_token(session.token)
        session.lock = false
        return session.token
    end

    # use the refresh token to get a new token:
    if session.refresh_token != "" && refresh_token(session)
        session.lock = false
        return session.token
    end

    if bootstrap_token_from_cache!(session, bootstrap)
        session.lock = false
        return session.token
    end

    devicecode_uri = "https://login.microsoft.com/$(session.tenant)/oauth2/v2.0/devicecode"
    _r = HTTP.request(
        "POST",
        "https://login.microsoft.com/$(session.tenant)/oauth2/v2.0/devicecode",
        Dict("Content-Type"=>"application/x-www-form-urlencoded"),
        "client_id=$(session.client_id)&scope=$(session.scope)")
    r = JSON.parse(String(_r.body))

    device_code = r["device_code"]
    @info r["message"]

    local _r
    while true
        _r = HTTP.request(
            "POST",
            "https://login.microsoft.com/$(session.tenant)/oauth2/v2.0/token",
            Dict("Content-Type"=>"application/x-www-form-urlencoded"),
            "grant_type=urn:ietf:params:oauth:grant-type:device_code&client_id=$(session.client_id)&device_code=$device_code";
            status_exception = false,
            retry = false)

        _r.status == 200 && break

        __r = String(_r.body)
        r = JSON.parse(__r)
        if r["error"] == "authorization_pending"
            sleep(5)
        else
            error(__r)
        end
    end

    r = JSON.parse(String(_r.body))

    session.id_token = get(r, "id_token", "") # only exists if openid is used in scope
    session.refresh_token = get(r, "refresh_token", "") # only exists if offline_access is used in scope
    session.token = r["access_token"]
    session.expiry = now(Dates.UTC) + Dates.Second(r["expires_in"])

    session_has_tokens(session) && record_session(session)
    session.lock = false
    session.token
end

function refresh_token(session::Union{AzAuthCodeFlowSession, AzDeviceCodeFlowSession})
    resource = audience_from_scope(session.scope)
    body = "client_id=$(session.client_id)&refresh_token=$(session.refresh_token)&grant_type=refresh_token&scope=$(session.scope)&resource=$resource"

    r = @retry 10 HTTP.request(
        "POST",
        "https://login.microsoftonline.com/$(session.tenant)/oauth2/token",
        Dict("Content-Type"=>"application/x-www-form-urlencoded"),
        body;
        retry = false)

    rbody = JSON.parse(String(r.body))

    local status
    if haskey(rbody, "error")
        status = false
    else
        status = true
        session.token = rbody["access_token"]
        session.refresh_token = rbody["refresh_token"]
        session.expiry = now(Dates.UTC) + Dates.Second(rbody["expires_in"])
    end
    status
end

function scrub!(session::AzDeviceCodeFlowSession)
    session.token = ""
    session.id_token = ""
    session.refresh_token = ""
    session
end

Base.show(io::IO, session::AzDeviceCodeFlowSession) = write(io, "Azure device code flow credentials session")

function AzCredentials(protocal::AbstractString)
    protocals = Dict("AzClientCredentials"=>AzClientCredentials, "AzDeviceCodeCredentials"=>AzDeviceCodeFlowCredentials, "AzAuthCodeFlowCredentials"=>AzAuthCodeFlowCredentials, "AzVMCredentials"=>AzVMCredentials, ""=>nothing)
    if !haskey(protocals, protocal)
        error("Authentication protocal, $protocal, is not recognized.")
    end
    protocals[protocal]
end

#
# Recording sessions to disk
#
sessionpath() = joinpath(homedir(), ".azsessions")
sessionfile() = joinpath(sessionpath(), "sessions.json")

function bootstrap_token_from_cache!(session, bootstrap)
    cached_session, session_is_recorded = get_recorded_session(session)
    if session_is_recorded
        if bootstrap == false
            update_session_from_cached_session!(session, cached_session)
            session.lock = false
            token(session, true)
            return true
        else
            @warn "failed to use cached token, token cache may be corrupted."
        end
    end
    false
end

function recorded_sessions()
    local rsessions
    if isfile(sessionfile())
        rsessions = JSON.parse(read(sessionfile(), String))
    else
        rsessions = Dict("sessions"=>[])
    end
    rsessions
end

function write_sessions(rsessions)
    rm(sessionfile(); force=true)
    write(sessionfile(), json(rsessions))
    chmod(sessionfile(), 0o400)
end

function record_session(session)
    if !isdir(sessionpath())
        try
            mkdir(sessionpath(); mode=0o700)
        catch
            @warn "unable to make directory $(sessionpath()): will not record sessions"
            return
        end
    end

    rsessions = recorded_sessions()
    has_session = false
    for (i,rsession) in enumerate(rsessions)
        if samesession(session, rsession)
            rsessions[i] = json(session)
            has_session = true
        end
    end
    if !has_session
        pushfirst!(rsessions["sessions"], json(session))
    end
    write_sessions(rsessions)
end

samesession(session1, session2) = false

function samescope(scope1, scope2)
    scopes1 = split(scope1, '+')
    scopes2 = split(scope2, '+')

    if length(scopes1) != length(scopes2)
        return false
    else
        for _scope1 in scopes1
            if _scope1 ∉ scopes2
                return false
            end
        end
    end
    true
end

function get_recorded_session(session)
    rsessions = recorded_sessions()
    for json_recorded_session in rsessions["sessions"]
        recorded_session = AzSession(json_recorded_session)
        if samesession(session, recorded_session)
            return recorded_session, true
        end
    end
    session, false
end

function delete_session(session)
    rsessions = recorded_sessions()
    i = 0
    for (isession, json_recorded_session) in enumerate(rsessions["sessions"])
        recorded_session = AzSession(json_recorded_session)
        if samesession(session, recorded_session)
            i = isession
            break
        end
    end
    if i > 0
        deleteat!(rsessions["sessions"], i)
    end
    write_sessions(rsessions)
end

#
# API
#
"""
    session = AzSession([; kwargs...])

Create an Azure session for authentication using a specific authentication
protocal.  The available protocals and their `kwargs` are as follows.

## Authorization code flow
```julia
session = AzSession(;
    protocal = _manifest["protocal"] | AzDeviceCodeFlowCredentials, # default, so can be ommitted.
    client_id = AzSessions._manifest["client_id"],
    redirect_uri = "http://localhost:44300/reply",
    scope = "openid+offline_access+https://storage.azure.com/user_impersonation",
    scope_auth = "openid+offline_access+https://management.azure.com/user_impersonation+https://storage.azure.com/user_impersonation",
    tenant = AzSessions._manifest["tenant"],
    lazy = false,
    clearcache = false)
```

## Device code flow
```julia
session = AzSession(;
    protocal = AzDeviceCodeCredentials
    client_id = AzSessions._manifest["client_id"],
    scope = "openid+offline_access+https://management.azure.com/user_impersonation",
    scope_auth = "openid+offline_access+https://management.azure.com/user_impersonation+https://storage.azure.com/user_impersonation",
    tenant = AzSessions._manifest["tenant"],
    clearcache = false)
```

## Client Credentials
```julia
session = AzSession(;
    protocal = AzClientCredentials,
    tenant="chevron.onmicrosoft.com",
    client_id=AzSessions._manifest["client_id"],
    client_secret=AzSessions._manifest["client_secret"],
    resource="https://management.azure.com/",
    clearcache = false)
```

## VM Credentials
```julia
session = AzSession(;
    protocal = AzVMCredentials,
    resource = "https://management.azure.com/",
    clearcache = false)
```

## New audience
Create a session from an existing auth code flow session or device code flow session,
but with a new scope.  This means that we can get a session with a new audience without
requiring re-authentication.  Note that the new scope must be in `session.scope_auth`.

```julia
session = AzSession(;
    protocal=AzAuthCodeFlowCredentials,
    scope_auth="openid+offline_access+https://management.azure.com/user_impersonation+https://storage.azure.com/user_impersonation",
    scope="openid+offline_access+https://management.azure.com/user_impersonation")

t = token(session) # token for `https://management.azure.com` audience
session = AzSession(session; scope="openid+offline_access+https://storage.azure.com/user_impersonation")
t = token(session) # token for `https://storage.azure.com` audience without needing to re-authenticate
```
# Notes
* If `lazy=false`, then authenticate at the time of construction.  Otherwise, wait until the first use of the session before authenticating.
* If `clearcache=false`, then check the session-cache for an existing token rather than re-authenticating.  The cache is stored in a JSON file (`~/.azsessions/sessions.json`).
* The default protocal can be set in the manifest (see the `AzSessions.write_manifest` method for more information).
"""
function AzSession(; protocal=nothing, lazy=false, clearcache=false, kwargs...)
    load_manifest()
    protocal == nothing && (protocal = AzCredentials(get(_manifest, "protocal", "")))
    protocal == nothing && (protocal = AzDeviceCodeFlowCredentials)

    local session
    if protocal == AzClientCredentials
        session = AzClientCredentialsSession(;kwargs...)
    elseif protocal == AzVMCredentials
        session = AzVMSession(;kwargs...)
    elseif protocal == AzAuthCodeFlowCredentials
        session = AzAuthCodeFlowSession(;kwargs...)
    elseif protocal == AzDeviceCodeFlowCredentials
        session = AzDeviceCodeFlowSession(;kwargs...)
    else
        error("Unknown credentials protocal.")
    end

    clearcache && delete_session(session)
    lazy || token(session)
    session
end

function AzSession(d::Dict)
    protocal = d["protocal"]
    if protocal ∈ ("AzClientCredentials", "AzSessions.AzClientCredentials")
        AzClientCredentialsSession(d)
    elseif protocal ∈ ("AzVMCredentials", protocal == "AzSessions.AzVMCredentials")
        AzVMSession(d)
    elseif protocal ∈ ("AzAuthCodeFlowCredentials", "AzSessions.AzAuthCodeFlowCredentials")
        AzAuthCodeFlowSession(d)
    elseif protocal ∈ ("AzDeviceCodeFlowCredentials", "AzSessions.AzDeviceCodeFlowCredentials")
        AzDeviceCodeFlowSession(d)
    else
        error("Unknown credentials protocal: $protocal.")
    end
end
AzSession(jsonobject::String) = AzSession(JSON.parse(jsonobject))

AzSession(session::AzSessionAbstract) = session

export AzAuthCodeFlowCredentials, AzClientCredentials, AzDeviceCodeFlowCredentials, AzSession, AzSessionAbstract, AzVMCredentials, scrub!, token

end


text:
__precompile__(false)

module Dolo

using Printf

import Dolang: SymExpr, list_syms

# model import utils
using DataStructures: OrderedDict
import YAML; using YAML: load_file, load

import IterTools
import HTTP
using StaticArrays

# solvers
using NLsolve
using Optim

# QuantEcon
using QuantEcon; import QuantEcon: simulate
const QE = QuantEcon

# Dolang
using Dolang
using Dolang: _to_expr, inf_to_Inf, solution_order, solve_triangular_system, _get_oorders
import Dolang: Language, add_language_elements!, FromGreek

# Numerical Tools
using MacroTools  # used for eval_with
import Distributions
import BasisMatrices
const BM = BasisMatrices

# Simulation/presentation
using AxisArrays
using StringDistances

# Compat across julia versions
using Compat; import Compat: String, view, @__dot__

using StaticArrays
using IterativeSolvers

# Functions from base we extend
# import Base.A_mul_B!
import Base.size
import Base.eltype
import Base.*

using LinearAlgebra

# exports
       # model functions
export arbitrage, transition, auxiliary, value, expectation,
       direct_response, controls_lb, controls_ub, arbitrage_2, felicity,

       # mutating version of model functions
       arbitrage!, transition!, auxiliary!, value!, expectation!,
       direct_response, controls_lb!, controls_ub!, arbitrage_2!, felicity!,
       evaluate_definitions

       # dolo functions
export lint, yaml_import, eval_with, evaluate, evaluate!, model_type, name, filename, id, features, set_calibration!

export time_iteration, improved_time_iteration, value_iteration, residuals,
        response, simulate, perfect_foresight, time_iteration_direct, find_deterministic_equilibrium, perturb, tabulate

export ModelCalibration, FlatCalibration, GroupedCalibration
export AbstractModel, AbstractDecisionRule, Model

# set up core typesr
# abstract type AbstractSymbolicModel{ID} end
# abstract type AbstractModel{ID} <: AbstractSymbolicModel{ID} end

abstract type AbstractModel{ID} end

const AModel = AbstractModel

id(::AbstractModel{ID}) where {ID} = ID

Expression = Union{Expr, Symbol, Float64, Int64}

# conventions for list of points
Point{d} = SVector{d,Float64}
Value{n} = SVector{n,Float64}
ListOfPoints{d} = Vector{Point{d}}
ListOfValues{n} = Vector{Value{n}}

# recursively make all keys at any layer of nesting a symbol
# included here instead of util.jl so we can call it on RECIPES below
_symbol_dict(x) = x
_symbol_dict(d::AbstractDict) =
    Dict{Symbol,Any}([(Symbol(k), _symbol_dict(v)) for (k, v) in d])

const src_path = dirname(@__FILE__)
const pkg_path = dirname(src_path)
const RECIPES = _symbol_dict(load_file(joinpath(src_path, "recipes.yaml")))

# define these _functions_ so users can add their own _methods_ to extend them
for f in [:arbitrage, :transition, :auxiliary, :value, :expectation,
          :direct_response, :controls_lb, :controls_ub, :arbitrage_2,
          :arbitrage!, :transition!, :auxiliary!, :value!, :expectation!,
          :direct_response, :controls_lb!, :controls_ub!, :arbitrage_2!]
    Core.eval(Dolo, Expr(:function, f))
end

include("numeric/splines/splines.jl")
import .splines
import .splines: eval_UC_spline, eval_UC_spline!, prefilter!

include("util.jl")

include("numeric/complementarities.jl")
include("numeric/newton.jl")
include("numeric/grids.jl")
include("numeric/processes.jl")

minilang = Language(Dict())
add_language_elements!(minilang, Dict(
    "!Normal"=>Normal,
    "!UNormal"=>UNormal,
    "!MarkovChain"=>MarkovChain,
    "!Product"=>Product,
    "!PoissonProcess"=>PoissonProcess,
    "!DeathProcess"=>DeathProcess,
    "!AgingProcess"=>AgingProcess,
    "!VAR1"=>VAR1,
))

# include("linter.jl")
include("calibration.jl")
include("minilang.jl")
include("model.jl")
# include("printing.jl")

include("numeric/decision_rules/core.jl")
include("numeric/decision_rules/csplines.jl")
include("numeric/decision_rules/constructor.jl")
include("numeric/decision_rules/compat.jl")
include("numeric/decision_rules/smolyak.jl")
include("numeric/decision_rules/complete.jl")

include("algos/steady_state.jl")
include("algos/time_iteration.jl")
include("algos/improved_time_iteration.jl")
include("algos/time_iteration_direct.jl")
include("algos/value_iteration.jl")
include("algos/perturbation.jl")
include("algos/simulation.jl")
include("algos/perfect_foresight.jl")

include("algos/ergodic.jl")

end # module


text:
include("euler/euler.jl")
using .Primes: prime_sieve
using BenchmarkTools
BenchmarkTools.DEFAULT_PARAMETERS.samples = 100

function compute()::String
    sieve = prime_sieve(10_000)
    primes = findall(sieve)
    for prime ∈ primes[primes .> 4_817]
        first, third = prime - 3_330, prime + 3_330
        if sieve[first] && sieve[third] && (sort(∪(string(prime))) == sort(∪(string(first)))) && (sort(∪(string(prime))) == sort(∪(string(third))))
            return string(first, prime, third)
        end
    end
end

compute()

@benchmark compute()

max_stars_repo_name: Dynortice/Project-Euler

max_issues_repo_name: Dynortice/Project-Euler

max_forks_repo_name: Dynortice/Project-Euler