text:
export CTC
export CTCGreedySearch
export CTCGreedySearchWithTimestamp
export indexbounds

"""
    indexbounds(lengthArray)
`lengthArray` records length of each sequence, i.e. labels or features
# example
    julia> indexbounds([2,0,3,2])
    ([1; 3; 3; 6], [2; 2; 5; 7])
"""
function indexbounds(lengthArray)
    acc = 0
    num = length(lengthArray)
    s = ones(Int,num,1)
    e = ones(Int,num,1)
    for i = 1:num
        s[i] += acc
        e[i] = s[i] + lengthArray[i] - 1
        acc += lengthArray[i]
    end
    return (s,e)
end

"""
    CTC(p::Array{T,2}, seq; blank=1) where T -> (target, lossvalue)
# Inputs
    p   : probability of softmax output\n
    seq : label seq like [9 3 6 15] which contains no blank. If p
          has no label (e.g. pure noise or oov) then seq is []
# Outputs
    target    : target of softmax's output\n
    lossvalue : negative log-likelyhood
"""
function CTC(p::Array{TYPE,2}, seq; blank=1) where TYPE
    Log0 = LogZero(TYPE)   # approximate -Inf of TYPE
    ZERO = TYPE(0)         # typed zero,e.g. Float32(0)
    S, T = size(p)         # assert p is a 2-D tensor
    L = length(seq)*2 + 1  # topology length with blanks
    r = fill!(Array{TYPE,2}(undef,S,T), ZERO)    # 𝜸 = p(s[k,t] | x[1:T]), k in softmax's indexing

    if L == 1
        r[blank,:] .= TYPE(1)
        return r, - sum(log.(p[blank,:]))
    end

    a = fill!(Array{TYPE,2}(undef,L,T), Log0)    # 𝜶 = p(s[k,t], x[1:t]), k in CTC topology's indexing
    b = fill!(Array{TYPE,2}(undef,L,T), Log0)    # 𝛃 = p(x[t+1:T] | s[k,t]), k in CTC topology's indexing
    a[1,1] = log(p[blank, 1])
    a[2,1] = log(p[seq[1],1])
    b[L-1,T] = ZERO
    b[L-0,T] = ZERO

    # --- forward in log scale ---
    for t = 2:T
        first = max(1,L-2*(T-t)-1);
        lasst = min(2*t,L);
        for s = first:lasst
            i = div(s,2);
            if s==1
                a[s,t] = a[s,t-1] + log(p[blank,t])
            elseif mod(s,2)==1
                a[s,t] = LogSum2Exp(a[s,t-1], a[s-1,t-1]) + log(p[blank,t])
            elseif s==2
                a[s,t] = LogSum2Exp(a[s,t-1], a[s-1,t-1]) + log(p[seq[i],t])
            elseif seq[i]==seq[i-1]
                a[s,t] = LogSum2Exp(a[s,t-1], a[s-1,t-1]) + log(p[seq[i],t])
            else
                a[s,t] = LogSum3Exp(a[s,t-1], a[s-1,t-1], a[s-2,t-1]) + log(p[seq[i],t])
            end
        end
    end

    # --- backward in log scale ---
    for t = T-1:-1:1
        first = max(1,L-2*(T-t)-1)
        lasst = min(2*t,L)
        for s = first:lasst
            i = div(s,2)
            j = div(s+1,2)
            if s==L
                b[s,t] = b[s,t+1] + log(p[blank,t+1])
            elseif mod(s,2)==1
                b[s,t] = LogSum2Exp(b[s,t+1] + log(p[blank,t+1]), b[s+1,t+1] + log(p[seq[j],t+1]))
            elseif s==L-1
                b[s,t] = LogSum2Exp(b[s,t+1] + log(p[seq[i],t+1]), b[s+1,t+1] + log(p[blank,t+1]))
            elseif seq[i]==seq[i+1]
                b[s,t] = LogSum2Exp(b[s,t+1] + log(p[seq[i],t+1]), b[s+1,t+1] + log(p[blank,t+1]))
            else
                b[s,t] = LogSum3Exp(b[s,t+1] + log(p[seq[i],t+1]), b[s+1,t+1] + log(p[blank,t+1]), b[s+2,t+1] + log(p[seq[i+1],t+1]))
            end
        end
    end

    logsum = LogSum3Exp(Log0, a[1,1] + b[1,1], a[2,1] + b[2,1])
    g = exp.((a + b) .- logsum)

    # reduce first line of g
    r[blank,:] .+= g[1,:]
    # reduce rest lines of g
    for n = 1:length(seq)
        s = n<<1
        r[seq[n],:] .+= g[s,  :]
        r[blank, :] .+= g[s+1,:]
    end

    return r, -logsum
end

"""
    CTCGreedySearch(x::Array; blank=1, dims=1) -> hypothesis
remove repeats and blanks of argmax(x, dims=dims)
"""
function CTCGreedySearch(x::Array; blank::Int=1, dims=1)
    hyp = Vector{Int}(undef, 0)
    idx = argmax(x, dims=dims)
    for t = 1:length(idx)
        previous = idx[t≠1 ? t-1 : t][1]
        current  = idx[t][1]
        if !((t≠1 && current==previous) || (current==blank))
            push!(hyp, current)
        end
    end
    return hyp
end

"""
    CTCGreedySearchWithTimestamp(x::Array; blank::Int=1, dims=1) -> hypothesis, timestamp
"""
function CTCGreedySearchWithTimestamp(x::Array; blank::Int=1, dims=1)
    hyp = Vector{Int}(undef, 0)
    stp = Vector{Float32}(undef, 0)
    idx = argmax(x, dims=dims)
    T   = length(idx)
    for t = 1:T
        previous = idx[t≠1 ? t-1 : t][1]
        current  = idx[t][1]
        if !((t≠1 && current==previous) || (current==blank))
            push!(hyp, current)
            push!(stp, t / T)
        end
    end
    return hyp, stp
end

max_stars_repo_name: sonosole/Delta

max_issues_repo_name: sonosole/Delta

max_forks_repo_name: sonosole/Delta


text:
### A Pluto.jl notebook ###
# v0.14.2

using Markdown
using InteractiveUtils

# ╔═╡ caa2cdba-a76b-11eb-3461-bb8695eb2e3b
using Revise, Curiosity, Plots, PlutoUI, Statistics, Random

# ╔═╡ 0af438b0-ffe6-4f8e-9077-2f7d37b3bf3f
using ProgressMeter

# ╔═╡ cfb65788-a6be-4d5e-a404-3ebd38a1c539
include("../experiments/1d-tmaze.jl")

# ╔═╡ dfd01378-0c1d-4385-b84c-d06fb049364e
ODTMU = Curiosity.OneDTMazeUtils

# ╔═╡ 578231af-8b90-4f2f-9745-989eae047a38
default_args(ϵ) =
Dict(
	"logger_interval" => 100,

	# Behaviour Items
	# "behaviour_eta" => 0.1/8,
	"behaviour_gamma" => 0.95,
	"behaviour_learner" => "Q",
	"behaviour_update" => "ESARSA",
	"behaviour_reward_projector" => "base",
	"behaviour_rp_tilings" => 1,
	"behaviour_rp_tiles" => 16,
	"behaviour_trace" => "ReplacingTraces",
	"behaviour_opt" => "Auto",
	"behaviour_lambda" => 0.9,
	"behaviour_alpha_init" => 0.1,
	"exploration_param" => ϵ,
	"exploration_strategy" => "epsilon_greedy",
	"ϵ_range" => (0.4,0.1),
	"decay_period" => 5000,
	"warmup_steps" => 1000,
	"behaviour_w_init" => 10,

	# Demon Attributes
	"demon_alpha_init" => 0.1,
	# "demon_eta" => 0.1/8,
	"demon_discounts" => 0.9,
	"demon_learner" => "SR",
	"demon_update" => "TB",
	"demon_policy_type" => "greedy_to_cumulant",
	"demon_opt" => "Auto",
	"demon_lambda" => 0.9,
	"demon_trace"=> "AccumulatingTraces",
	"demon_beta_m" => 0.99,
	"demon_beta_v" => 0.99,

	#shared
	"num_tiles" => 8,
	"num_tilings" =>2,
	"demon_rep" => "ideal_martha",
	# "demon_rep" => "tilecoding",
	"demon_num_tiles" => 6,
	"demon_num_tilings" => 1,
	"eta" => 0.2,

	# Environment Config
	"constant_target"=> [-10.0,10.0],
	"cumulant_schedule" => "DrifterDistractor",
	"distractor" => (1.0, 5.0),
	"drifter" => (1.0, sqrt(0.01)),
	"exploring_starts"=>"beg",
	"env_step_penalty" => -0.01,

	# Agent and Logger
	"horde_type" => "regular",
	"random_first_action" => false,
	"intrinsic_reward" => "weight_change",
	# "logger_keys" => [LoggerKey.TTMAZE_ERROR],
	"save_dir" => "OneDTMazeExperiment",
	"seed" => 1,
	"steps" => 10000,
	"use_external_reward" => true,

	"logger_keys" => [LoggerKey.ONEDTMAZEERROR, LoggerKey.ONED_GOAL_VISITATION, LoggerKey.EPISODE_LENGTH, LoggerKey.INTRINSIC_REWARD]
)

# ╔═╡ 6d51db0c-72b1-47ed-8ce2-8822f15473cc
env = OneDTMaze(Curiosity.TMazeCumulantSchedules.Constant(1), "beg")

# ╔═╡ db493356-572c-4475-93ac-f9c785d8cefd
let
	@show MinimalRLCore.step!(env, 1)
	plot(env)
end

# ╔═╡ 99ad1698-d4f7-449d-8865-18a5917bb47c
function main_experiment(parsed=default_args(); progress=false, working=false)

    num_steps = parsed["steps"]
    Random.seed!(parsed["seed"])

    cumulant_schedule = ODTMU.get_cumulant_schedule(parsed)

    # exploring_starts = parsed["exploring_starts"]
    env = OneDTMaze(cumulant_schedule, parsed["exploring_starts"], parsed["env_step_penalty"])

    agent = OneDTmazeExperiment.construct_agent(parsed)
	@show parsed["behaviour_learner"],parsed["demon_learner"]

    goal_visitations = zeros(4)

	anim = Animation()

    eps = 1
    max_num_steps = num_steps
    steps = Int[]

    prg_bar = ProgressMeter.Progress(num_steps, "Step: ")
    while sum(steps) < max_num_steps
        cur_step = 0
        max_episode_steps = max_num_steps - sum(steps)
        tr, stp =
            run_episode!(env, agent, max_episode_steps) do (s, a, s_next, r, t)
                #This is a callback for every timestep where logger can go
                # agent is accesible in this scope
				plot(env)
                if t == true && working==true
                    goals = s_next[3:end]
                    f = findfirst(!iszero, goals)
                    goal_visitations[f] += 1
                end

                if progress
                    next!(prg_bar)
                end
                cur_step+=1
				frame(anim)

            end
        push!(steps, stp)
        eps += 1
    end
    if working == true
        println("Goal Visitation: ", goal_visitations)
    end
	anim
end

# ╔═╡ 15a72300-bd1a-4476-a3b6-d108035d0f25
anim = main_experiment(default_args(0.1),progress=true)

# ╔═╡ bcea5162-66e6-4e1f-8bcc-b4d738277213
mp4(anim,"../plotting/plots/tst2.mp4")

# ╔═╡ Cell order:
# ╠═caa2cdba-a76b-11eb-3461-bb8695eb2e3b
# ╠═cfb65788-a6be-4d5e-a404-3ebd38a1c539
# ╠═dfd01378-0c1d-4385-b84c-d06fb049364e
# ╠═578231af-8b90-4f2f-9745-989eae047a38
# ╠═6d51db0c-72b1-47ed-8ce2-8822f15473cc
# ╠═db493356-572c-4475-93ac-f9c785d8cefd
# ╠═99ad1698-d4f7-449d-8865-18a5917bb47c
# ╠═0af438b0-ffe6-4f8e-9077-2f7d37b3bf3f
# ╠═15a72300-bd1a-4476-a3b6-d108035d0f25
# ╠═bcea5162-66e6-4e1f-8bcc-b4d738277213

ext: jl

max_stars_repo_name: MatthewMcLeod/curiosity

max_issues_repo_name: MatthewMcLeod/curiosity

max_forks_repo_name: MatthewMcLeod/curiosity


text:
export CBSSolver

"""
    CBSSolver

Path planner that employs Conflict-Based Search.
"""
@with_kw struct CBSSolver{L,C} <: AbstractCBSSolver
    low_level_planner::L    = VanillaAStar()
    logger::SolverLogger{C} = SolverLogger{cost_type(low_level_planner)}(
        iteration_limit=1000,
    )
end
CBSSolver(planner) = CBSSolver(low_level_planner=planner)
# CBSSolver(mapf::AbstractMAPF) = CBSSolver(low_level_planner=AStar{cost_type(mapf)}())
for op in [:set_deadline!,:set_runtime_limit!,:set_verbosity!]
    eval(quote
        $op(solver::CBSSolver,args...) = begin
            $op(get_logger(solver),args...)
            $op(solver.low_level_planner,args...)
        end
    end)
end

################################################################################
############################# CBS Logger Interface #############################
################################################################################
function enter_cbs!(solver)
    reset_solver!(solver)
end
function logger_cbs_add_constraint!(solver,new_node,constraint) end
function logger_dequeue_cbs_node!(solver,mapf,node)
    @log_info(1,verbosity(solver),
        "CBS: iter ",iterations(solver)," - node ",node.trace,
        " - Current paths: \n",
        sprint_indexed_list_array(convert_to_vertex_lists(node.solution);leftaligned=true),
        # sprint_route_plan(node.solution;leftaligned=true),
        )
    @log_info(2,verbosity(solver),"CBS: constraints in node ",node.trace,": \n",
        map(c->string("\t",string(c),"\n"),sorted_state_constraints(mapf,node))...,
        map(c->string("\t",string(c),"\n"),sorted_action_constraints(mapf,node))...,
        )
    # if verbosity(solver) >= 1
    #     println("CBS: iter ",iterations(solver)," - node ",node.trace," - Current paths: ")
    #     for (i,path) in enumerate(get_paths(node.solution))
    #         println("\t",i,": ",convert_to_vertex_lists(path))
    #     end
    # end
    enforce_iteration_limit!(solver)
end
function logger_exit_cbs_optimal!(solver,node)
    set_best_cost!(solver,get_cost(node))
    @log_info(0,verbosity(solver),"Optimal solution found by CBS! Cost = $(get_cost(node))")
    # if verbosity(solver) >= 0
    #     println("Optimal Solution Found! Cost = $(get_cost(node))")
    # end
end
function logger_cbs_add_constraint!(solver,node,constraint,mapf)
    increment_iteration_count!(solver)
    enforce_time_limit!(solver)
    enforce_iteration_limit!(solver)
    @log_info(1,verbosity(solver),"CBS: adding constraint to node ",node.trace,": ",string(constraint))
    # @log_info(2,verbosity(solver),"CBS: constraints in node ",node.trace,": \n",
    #     map(c->string("\t",string(c),"\n"),sorted_state_constraints(mapf,node))...,
    #     map(c->string("\t",string(c),"\n"),sorted_action_constraints(mapf,node))...,
    #     )
    # if verbosity(solver) == 1
    #     println("CBS: adding constraint ",string(constraint))
    # elseif verbosity(solver) >= 2
    #     # println("CBS: adding constraint:")
    #     # println("\t",string(constraint))
    #     println("CBS: constraints in node:")
    #     for i in 1:num_agents(mapf)
    #         for constraint in sorted_state_constraints(mapf,node,i)
    #             println("\t",string(constraint))
    #         end
    #         for constraint in sorted_action_constraints(mapf,node,i)
    #             println("\t",string(constraint))
    #         end
    #     end
    # end
end

################################################################################
################################ CBS Interface #################################
################################################################################
export low_level_search!

"""
    `low_level_search!(
        solver,
        mapf::AbstractMAPF,
        node::ConstraintTreeNode,
        idxs=collect(1:num_agents(mapf)),
        path_finder=a_star!)`

    Returns a low level solution for a MAPF with constraints. The heuristic
    function for cost-to-go is user-defined and environment-specific
"""
function low_level_search!(
    solver, mapf::M, node::N, idxs=collect(1:num_agents(mapf));
    path_finder=a_star!
    ) where {M<:AbstractMAPF,N<:ConstraintTreeNode}
    # Only compute a path for the indices specified by idxs
    for i in idxs
        env = build_env(solver, mapf, node, i)
        reset_solver!(low_level(solver))
        path, cost = path_finder(low_level(solver), env, get_start(mapf,env,i))
        set_solution_path!(node.solution, path, i)
        set_path_cost!(node.solution, cost, i)
    end
    set_cost!(node, aggregate_costs(get_cost_model(mapf.env),get_path_costs(node.solution)))
    return is_consistent(node.solution,mapf)
end
# low_level_search!(solver::CBSSolver,args...) = low_level_search!(low_level(solver),args...)
build_env(solver, mapf, node, i) = build_env(mapf, node, i)

"""
    get_agent_idxs(solver,node,mapf,constraint)

Part of CBS interface. Defaults to return the index of a single agent affected
by a constraint. Can be overridden to return the index of e.g., a "meta-agent"
(group of agents).
"""
function get_agent_idxs(solver,node,mapf,constraint)
    [get_agent_id(constraint)]
end

"""
    cbs_bypass!(solver,mapf,node,conflict,priority_queue)

Part of CBS interface. Defaults to false, but can be overridden to modify the
priority_queue and/or bypass the branching step of CBS
"""
cbs_bypass!(solver,mapf,node,priority_queue) = false

"""
    cbs_update_conflict_table!(solver,mapf,node,constraint)

Allows for flexible conflict-updating dispatch. This function is called within
    within the default `cbs_branch!()` method.
"""
function cbs_update_conflict_table!(solver,mapf,node,constraint)
    detect_conflicts!(node,[get_agent_id(constraint)]) # update conflicts related to this agent
end

"""
    cbs_branch!(solver,mapf,node,conflict,priority_queue)

Part of CBS interface. Defaults to splitting on the conflict and adding two
nodes to the priority_queue, where each of the child nodes has one of the new
complementary constraints.
"""
function cbs_branch!(solver,mapf,node,conflict,priority_queue)
    constraints = generate_constraints_from_conflict(conflict)
    for (i,constraint) in enumerate(constraints)
        new_node = initialize_child_search_node(solver,mapf,node)
        set_trace!(new_node,node,i)
        logger_cbs_add_constraint!(solver,new_node,constraint,mapf)
        if add_constraint!(mapf,new_node,constraint)
            consistent_flag = low_level_search!(solver, mapf, new_node,[get_agent_id(constraint)])
            if consistent_flag
                cbs_update_conflict_table!(solver,mapf,new_node,constraint)
                enqueue!(priority_queue, new_node => get_cost(new_node))
            end
        end
    end
    priority_queue
end

"""
    Conflict-Based Search

    Sharon et al 2012
    https://www.aaai.org/ocs/index.php/AAAI/AAAI12/paper/viewFile/5062/5239
"""
function cbs!(solver,mapf)
    enter_cbs!(solver)
    node = initialize_root_node(solver,mapf)
    priority_queue = PriorityQueue{typeof(node),cost_type(node)}()
    consistent_flag = low_level_search!(solver,mapf,node)
    if consistent_flag
        detect_conflicts!(node)
        enqueue!(priority_queue, node => get_cost(node))
    end

    try
        while ~isempty(priority_queue)
            # node = cbs_dequeue_and_preprocess!(solver,priority_queue,mapf)
            node = dequeue!(priority_queue)
            set_lower_bound!(solver,get_cost(node))
            logger_dequeue_cbs_node!(solver,mapf,node)
            # check for conflicts
            conflict = get_next_conflict(node.conflict_table)
            if !is_valid(conflict)
                logger_exit_cbs_optimal!(solver,node)
                return node.solution, get_cost(node)
            elseif ~cbs_bypass!(solver,mapf,node,priority_queue)
                cbs_branch!(solver,mapf,node,conflict,priority_queue)
            end
        end
    catch e
        isa(e, SolverException) ? handle_solver_exception(solver,e) : rethrow(e)
    end
    @log_info(-1,verbosity(solver),"CBS: No Solution Found. Returning default solution")
    return default_solution(mapf)
end

function solve!(solver::CBSSolver, mapf::M where {M<:AbstractMAPF}, path_finder=a_star!;verbose=false)
    cbs!(solver,mapf)
end


text:
"""
    EasyIO

Quick I/O APIs, covers extra pacakge-import from other enviroments
"""
module EasyIO
    # 1. 3rd-party APIs
    import Dates  # for time tags
    import DelimitedFiles  # std lib, delimited files e.g. csv

# ------------------------------------------------------------------------------
"""
   LogTag()

generates a tag of logging; the tag can be used to mark time or name files.
returns a String.
"""
function LogTag()
   local tagstr = replace(string(Dates.now()), "-" => "_" )
   tagstr = replace( tagstr, "T" => "_" )
   tagstr = replace( tagstr, ":" => "_" )
   tagstr = replace( tagstr, "." => "_" )
   return tagstr::String
end
# ----------
# Two IO functions from Julia 0.6
# NOTE: well ... the readcsv() & writecsv() before Julai 0.6 are SO convenient in some ways ...
#       I re-define the two functions here; (directly copied from base Julia 0.6)
readcsv(io; opts...)          = DelimitedFiles.readdlm(io, ','; opts...)
readcsv(io, T::Type; opts...) = DelimitedFiles.readdlm(io, ',', T; opts...)
"""
    writecsv(filename, A; opts)
Equivalent to [`writedlm`](@ref) with `delim` set to comma.
"""
writecsv(io, a; opts...) = DelimitedFiles.writedlm(io, a, ','; opts...)
# ---------

"""
    SaveModel( OutPath::String, Dt::Dict, Dst::Dict, Pt::Dict, Ps::Dict, Pc::Dict, env::NamedTuple )

Save a model (datasets) to a specific folder indicated with :OutPath.
:OutPath should be a FOLDER-level directory, please use '/' rather than "\\";
and, please use "/" to end the :OutPath string!
if not existed, a new folder will be auto created
returns nothing.
"""
function SaveModel( OutPath::String, Dt::Dict, Dst::Dict, Pt::Dict, Ps::Dict, Pc::Dict, env::NamedTuple )
    # check OutPath
    # @assert( isdir(OutPath) , "requries a path, not file or something else" )
    @assert( OutPath[end] == '/' , "requries a '/' to end your path" )
    # check if the assigned folder exists
    try
        mkdir( OutPath )
    catch
    end

    # Part 1: parameters
        # 1. demography
        writecsv( string(OutPath,"Population.csv"), Ps[:N] )
        writecsv( string(OutPath,"Mortality.csv"), Ps[:F] )
        # NOTE: save two vectors, total & labor popualtions, to plot
        writecsv(   string(OutPath,"AggDemography.csv"),
                    Dict(   "TotalPopu" => Dt[:N],
                            "LaborPopu" => sum(Ps[:N][:,1:env.Sr],dims=2)[:],  # using [:] to get a one-way vector
                            "AgingPopu_65plus" => sum(Ps[:N][:, (65 - env.START_AGE + 1):env.S],dims=2)[:]
                        )
                )
        # 2. age-specific
        writecsv( string(OutPath,"Index_Age.csv"), Dst[:Age] )
        writecsv( string(OutPath,"ma2mb.csv"), Ps[:p] )
        writecsv( string(OutPath,"WageProfile.csv"), Ps[:ε] )
        writecsv( string(OutPath,"ProfiledQ_m2c.csv"), Ps[:q] )
        # 3. constants
        writecsv( string(OutPath,"ConstParameters.csv"), Pc )
        # 4. year-related parameters
        writecsv( string(OutPath,"YearParameters.csv"), Pt )

    # Part 2: year-related data
        writecsv( string(OutPath,"Index_Year.csv"), Dst[:Year] )
        writecsv( string(OutPath,"YearData.csv"), Dt )

    # Part 3: matrix data
        writecsv( string(OutPath,"Mat_Consumption.csv"), Dst[:c] )
        writecsv( string(OutPath,"Mat_Labor.csv"), Dst[:Lab] )
        writecsv( string(OutPath,"Mat_MedicalExp.csv"), Dst[:m] )
        writecsv( string(OutPath,"Mat_OutpatientExp.csv"), Dst[:MA] )
        writecsv( string(OutPath,"Mat_InpatientExp.csv"), Dst[:MB] )
        writecsv( string(OutPath,"Mat_Capital.csv"), Dst[:𝒜] )
        writecsv( string(OutPath,"Mat_Asset.csv"), Dst[:a] )
        writecsv( string(OutPath,"Mat_UEBMI_Indi.csv"), Dst[:Φ] )
        writecsv( string(OutPath,"Mat_Wage.csv"), Dst[:w] )

    return nothing
end

end   #module ends
#


text:
struct CurlSingleLayerDP3D{T,U} <: MaxwellOperator3D
    gamma::T
    alpha::U
end

function integrand(op::CurlSingleLayerDP3D, kernel_vals,
    test_vals, test_nbhd, trial_vals, trial_nbhd)

    α = op.alpha

    gx = test_vals.value
    fy = trial_vals.value

    ∇G = kernel_vals.gradgreen
    nx = normal(test_nbhd)

    return -α * dot(nx × gx, ∇G * fy)
end

function momintegrals!(op::CurlSingleLayerDP3D,
    test_local_space::RTRefSpace, trial_local_space::LagrangeRefSpace,
    test_triangular_element, trial_triangular_element, out, strat::SauterSchwabStrategy)

    I, J, K, L = SauterSchwabQuadrature.reorder(
        test_triangular_element.vertices,
        trial_triangular_element.vertices, strat)

    test_triangular_element  = simplex(test_triangular_element.vertices[I]...)
    trial_triangular_element = simplex(trial_triangular_element.vertices[J]...)

    function igd(u,v)
        α = op.alpha
        γ = op.gamma

        x = neighborhood(test_triangular_element,u)
        y = neighborhood(trial_triangular_element,v)

        nx = normal(x)

        r = cartesian(x) - cartesian(y)
        R = norm(r)
        G = exp(-γ*R)/(4π*R)
        GG = -(γ + 1/R) * G / R * r

        f = test_local_space(x)
        g = trial_local_space(y)

        jx = jacobian(x)
        jy = jacobian(y)
        j = jx*jy

        αjGG = α*j*GG

        R = @SVector[αjGG*g[i].value for i in 1:3]
        return @SMatrix[dot(f[i].value × nx, R[j]) for i in 1:3, j in 1:3]
    end

    Q = sauterschwab_parameterized(igd, strat)
    for j ∈ 1:3
        for i ∈ 1:3
            out[i,j] += Q[K[i],L[j]]
        end
    end

    nothing
end

function quadrule(op::BEAST.CurlSingleLayerDP3D,
    test_local_space::BEAST.RTRefSpace, trial_local_space::BEAST.RTRefSpace,
    test_index, test_chart, trial_index, trial_chart, quadrature_data)

    qrdf(op, test_local_space, trial_local_space, test_index, test_chart, trial_index, trial_chart, quadrature_data)
end


text:
using BenchmarkTools
using LinearAlgebra
using StaticArrays

add!(C, A, B) = (C .= A .+ B)

function simple_bench(N, T=Float64)
    A = rand(T,N,N)
    A = A'*A
    B = copy(A)
    SA = SMatrix{N,N}(A)
    MA = MMatrix{N,N}(A)
    MB = copy(MA)

    print("""
============================================
    Benchmarks for $N×$N $T matrices
============================================
""")
    ops = [
           ("Matrix multiplication              ", *,        (A, A),     (SA, SA)),
           ("Matrix multiplication (mutating)   ", mul!,     (B, A, A),  (MB, MA, MA)),
           ("Matrix addition                    ", +,        (A, A),     (SA, SA)),
           ("Matrix addition (mutating)         ", add!,     (B, A, A),  (MB, MA, MA)),
           ("Matrix determinant                 ", det,      (A,),       (SA,)),
           ("Matrix inverse                     ", inv,      (A,),       (SA,)),
           ("Matrix symmetric eigendecomposition", eigen,    (A,),       (SA,)),
           ("Matrix Cholesky decomposition      ", cholesky, (A,),       (SA,)),
           ("Matrix LU decomposition            ", lu,       (A,),       (SA,)),
           ("Matrix QR decomposition            ", qr,       (A,),       (SA,)),
    ]
    for (name, op, Aargs, SAargs) in ops
        # We load from Ref's here to avoid the compiler completely removing the
        # benchmark in some cases.
        #
        # Like any microbenchmark, the speedups you see here should only be
        # taken as roughly indicative of the speedup you may see in real code.
        if length(Aargs) == 1
            A1  = Ref(Aargs[1])
            SA1 = Ref(SAargs[1])
            speedup = @belapsed($op($A1[])) / @belapsed($op($SA1[]))
        elseif length(Aargs) == 2
            A1  = Ref(Aargs[1])
            A2  = Ref(Aargs[2])
            SA1 = Ref(SAargs[1])
            SA2 = Ref(SAargs[2])
            speedup = @belapsed($op($A1[], $A2[])) / @belapsed($op($SA1[], $SA2[]))
        elseif length(Aargs) == 3
            A1  = Ref(Aargs[1])
            A2  = Ref(Aargs[2])
            A3  = Ref(Aargs[3])
            SA1 = Ref(SAargs[1])
            SA2 = Ref(SAargs[2])
            SA3 = Ref(SAargs[3])
            speedup = @belapsed($op($A1[], $A2[], $A3[])) / @belapsed($op($SA1[], $SA2[], $SA3[]))
        else
        end
        println(name*" -> $(round(speedup, digits=1))x speedup")
    end
end

simple_bench(3)

simple_bench(256)

N=50
T=Float64

A = rand(T,N,N)
A = A'*A
B = copy(A)
SA = SMatrix{N,N}(A)
MA = MMatrix{N,N}(A)
MB = copy(MA)

@benchmark SMatrix{N,N}(A)
@benchmark rand(T,N,N)

function random_access(data::Vector{UInt}, N::Integer)
    n = rand(UInt)
    mask = length(data) - 1
    @inbounds for i in 1:N
        n = (n >>> 7) ⊻ data[n & mask + 1]
    end
    return n
end

function linear_access(data::Vector{UInt}, N::Integer)
    n = rand(UInt)
    mask = length(data) - 1
    for i in 1:N
        n = (n >>> 7) ⊻ data[i & mask + 1]
    end
    return n
end


text:
module CCallHelp

export free_ptr, string_from_ptr, vec_string_from_ptr

"""
    free_ptr(ptr; free=true)
Free the given ptr if not C_NULL.
# Arguments
- `ptr` the C pointer to be freed
- `free` a conditional flag to prevent an `if` at the call site
"""
free_ptr(ptr; free=true) = if free && ptr != C_NULL ccall(:free, Cvoid, (Ptr{Cvoid},), Ptr{Cvoid}(ptr)) end

"""
    string_from_ptr(ptr::Ptr{Cuchar}; free=true)
Create a Julia String from a memory location a byte at a time.
# Arguments
- `ptr` pointer to use
- `free` flag to determine if the memory should be freed once copied
"""
function string_from_ptr(ptr::Ptr{Cuchar}; free=true)
    if ptr == C_NULL
        return ""
    end
    uchars = Vector{UInt8}()
    i = 1
    while (c = unsafe_load(ptr, i)) != 0
        push!(uchars, c)
        i += 1
    end
    free_ptr(ptr; free)
    String(uchars)
end

"""
    vec_string_from_ptr(ptr_ptr_uchar; free=true)
Create a Vector{String} from the supplied list of uchar*
# Arguments
- `ptr` the pointer to the list
- `free` flag to determine if the memory of both the strings and the list should be freed once copied
"""
function vec_string_from_ptr(ptr::Ptr{Ptr{Cuchar}}; free=true)
    if ptr == C_NULL
        return String[]
    end
    strings = Vector{String}()
    i = 1
    while (stringp = unsafe_load(ptr,i)) != C_NULL
        push!(strings, string_from_ptr(stringp; free))
        i += 1
    end
    free_ptr(ptr; free)
    strings
end

"""
 untested

"""
function vec_from_ptr(ptr, type, n)
    v = Vector{type}(undef, n)
    for i in 1:n
        v[i] = unsafe_load(ptr, n)
    end
    v
end

###
end


text:
"""
A module for rendering `Document` objects to HTML.

# Keywords

[`HTMLWriter`](@ref) uses the following additional keyword arguments that can be passed to
[`Documenter.makedocs`](@ref): `authors`, `pages`, `sitename`, `version`.
The behavior of [`HTMLWriter`](@ref) can be further customized by setting the `format`
keyword of [`Documenter.makedocs`](@ref) to a [`HTML`](@ref), which accepts the following
keyword arguments: `analytics`, `assets`, `canonical`, `disable_git`, `edit_branch` and
`prettyurls`.

**`sitename`** is the site's title displayed in the title bar and at the top of the
*navigation menu. This argument is mandatory for [`HTMLWriter`](@ref).

**`pages`** defines the hierarchy of the navigation menu.

# Experimental keywords

**`version`** specifies the version string of the current version which will be the
selected option in the version selector. If this is left empty (default) the version
selector will be hidden. The special value `git-commit` sets the value in the output to
`git:{commit}`, where `{commit}` is the first few characters of the current commit hash.

# `HTML` `Plugin` options

The [`HTML`](@ref) [`Documenter.Plugin`](@ref) provides additional customization options
for the [`HTMLWriter`](@ref). For more information, see the [`HTML`](@ref) documentation.

# Page outline

The [`HTMLWriter`](@ref) makes use of the page outline that is determined by the
headings. It is assumed that if the very first block of a page is a level 1 heading,
then it is intended as the page title. This has two consequences:

1. It is then used to automatically determine the page title in the navigation menu
   and in the `<title>` tag, unless specified in the `.pages` option.
2. If the first heading is interpreted as being the page title, it is not displayed
   in the navigation sidebar.
"""
module HTMLWriter

import Markdown
import JSON

import ...Documenter:
    Anchors,
    Builder,
    Documents,
    Expanders,
    Documenter,
    Utilities,
    Writers

import ...Utilities.DOM: DOM, Tag, @tags
using ...Utilities.MDFlatten

export HTML

"""
    HTML(kwargs...)

Sets the behavior of [`HTMLWriter`](@ref).

# Keyword arguments

**`prettyurls`** (default `true`) -- allows toggling the pretty URLs feature.

By default (i.e. when `prettyurls` is set to `true`), Documenter creates a directory
structure that hides the `.html` suffixes from the URLs (e.g. by default `src/foo.md`
becomes `src/foo/index.html`, but can be accessed with via `src/foo/` in the browser). This
structure is preferred when publishing the generate HTML files as a website (e.g. on GitHub
Pages), which is Documenter's primary use case.

If `prettyurls = false`, then Documenter generates `src/foo.html` instead, suitable for
local documentation builds, as browsers do not normally resolve `foo/` to `foo/index.html`
for local files.

To have pretty URLs disabled in local builds, but still have them enabled for the automatic
CI deployment builds, you can set `prettyurls = get(ENV, "CI", nothing) == "true"` (the
specific environment variable you will need to check may depend on the CI system you are
using, but this will work on Travis CI).

**`disable_git`** can be used to disable calls to `git` when the document is not
in a Git-controlled repository. Without setting this to `true`, Documenter will throw
an error and exit if any of the Git commands fail. The calls to Git are mainly used to
gather information about the current commit hash and file paths, necessary for constructing
the links to the remote repository.

**`edit_branch`** specifies which branch, tag or commit the "Edit on GitHub" links
point to. It defaults to `master`. If it set to `nothing`, the current commit will be used.

**`canonical`** specifies the canonical URL for your documentation. We recommend
you set this to the base url of your stable documentation, e.g. `https://juliadocs.github.io/Documenter.jl/stable`.
This allows search engines to know which version to send their users to. [See
wikipedia for more information](https://en.wikipedia.org/wiki/Canonical_link_element).
Default is `nothing`, in which case no canonical link is set.

**`analytics`** can be used specify the Google Analytics tracking ID.

**`assets`** can be used to include additional assets (JS, CSS, ICO etc. files). See below
for more information.

# Default and custom assets

Documenter copies all files under the source directory (e.g. `/docs/src/`) over
to the compiled site. It also copies a set of default assets from `/assets/html/`
to the site's `assets/` directory, unless the user already had a file with the
same name, in which case the user's files overrides the Documenter's file.
This could, in principle, be used for customizing the site's style and scripting.

The HTML output also links certain custom assets to the generated HTML documents,
specifically a logo and additional javascript files.
The asset files that should be linked must be placed in `assets/`, under the source
directory (e.g `/docs/src/assets`) and must be on the top level (i.e. files in
the subdirectories of `assets/` are not linked).

For the **logo**, Documenter checks for the existence of `assets/logo.{svg,png,webp,gif,jpg,jpeg}`,
in this order. The first one it finds gets displayed at the top of the navigation sidebar.

Additional JS, ICO, and CSS assets can be included in the generated pages using the
`assets` keyword for `makedocs`. `assets` must be a `Vector{String}` and will include
each listed asset in the `<head>` of every page in the order in which they are listed.
The type of the asset (i.e. whether it is going to be included with a `<script>` or a
`<link>` tag) is determined by the file's extension -- either `.js`, `.ico`, or `.css`.
Adding an ICO asset is primarilly useful for setting a custom `favicon`.
"""
struct HTML <: Documenter.Plugin
    prettyurls  :: Bool
    disable_git :: Bool
    edit_branch :: Union{String, Nothing}
    canonical   :: Union{String, Nothing}
    assets      :: Vector{String}
    analytics   :: String

    function HTML(;
        prettyurls::Bool = true,
        disable_git::Bool = false,
        edit_branch::Union{String, Nothing} = "master",
        canonical::Union{String, Nothing} = nothing,
        assets::Vector{String} = String[],
        analytics::String = "")
        new(prettyurls, disable_git, edit_branch, canonical, assets, analytics)
    end
end

const requirejs_cdn = "https://cdnjs.cloudflare.com/ajax/libs/require.js/2.2.0/require.min.js"
const normalize_css = "https://cdnjs.cloudflare.com/ajax/libs/normalize/4.2.0/normalize.min.css"
const google_fonts = "https://fonts.googleapis.com/css?family=Lato|Roboto+Mono"
const fontawesome_css = "https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.6.3/css/font-awesome.min.css"
const highlightjs_css = "https://cdnjs.cloudflare.com/ajax/libs/highlight.js/9.12.0/styles/default.min.css"

struct SearchRecord
    src :: String
    page :: Documents.Page
    loc :: String
    category :: String
    title :: String
    page_title :: String
    text :: String
end

"""
[`HTMLWriter`](@ref)-specific globals that are passed to [`domify`](@ref) and
other recursive functions.
"""
mutable struct HTMLContext
    doc :: Documents.Document
    settings :: HTML
    logo :: String
    scripts :: Vector{String}
    documenter_js :: String
    search_js :: String
    search_index :: Vector{SearchRecord}
    search_index_js :: String
    search_navnode :: Documents.NavNode
    local_assets :: Vector{String}
end

HTMLContext(doc, settings=HTML()) = HTMLContext(doc, settings, "", [], "", "", [], "", Documents.NavNode("search", "Search", nothing), [])

function SearchRecord(ctx::HTMLContext, navnode; loc="", title=nothing, category="page", text="")
    page_title = mdflatten(pagetitle(ctx, navnode))
    if title === nothing
        title = page_title
    end
    SearchRecord(
        pretty_url(ctx, get_url(ctx, navnode.page)),
        getpage(ctx, navnode),
        loc,
        lowercase(category),
        title,
        page_title,
        text
    )
end

function SearchRecord(ctx::HTMLContext, navnode, node::Markdown.Header)
    a = getpage(ctx, navnode).mapping[node]
    SearchRecord(ctx, navnode;
        loc="$(a.id)-$(a.nth)",
        title=mdflatten(node),
        category="section")
end

function SearchRecord(ctx, navnode, node)
    SearchRecord(ctx, navnode; text=mdflatten(node))
end

function JSON.lower(rec::SearchRecord)
    # Replace any backslashes in links, if building the docs on Windows
    src = replace(rec.src, '\\' => '/')
    ref = string(src, '#', rec.loc)
    Dict{String, String}(
        "location" => ref,
        "page" => rec.page_title,
        "title" => rec.title,
        "category" => rec.category,
        "text" => rec.text
    )
end

"""
Returns a page (as a [`Documents.Page`](@ref) object) using the [`HTMLContext`](@ref).
"""
getpage(ctx, path) = ctx.doc.internal.pages[path]
getpage(ctx, navnode::Documents.NavNode) = getpage(ctx, navnode.page)

function render(doc::Documents.Document, settings::HTML=HTML())
    @info "HTMLWriter: rendering HTML pages."
    !isempty(doc.user.sitename) || error("HTML output requires `sitename`.")

    ctx = HTMLContext(doc, settings)
    ctx.search_index_js = "search_index.js"

    copy_asset("arrow.svg", doc)

    for logoext in ["svg", "png", "webp", "gif", "jpg", "jpeg"]
        logo = joinpath("assets", "logo.$(logoext)")
        if isfile(joinpath(doc.user.build, logo))
            ctx.logo = logo
            break
        end
    end

    ctx.documenter_js = copy_asset("documenter.js", doc)
    ctx.search_js = copy_asset("search.js", doc)

    push!(ctx.local_assets, copy_asset("documenter.css", doc))
    append!(ctx.local_assets, settings.assets)

    for navnode in doc.internal.navlist
        render_page(ctx, navnode)
    end

    render_search(ctx)

    open(joinpath(doc.user.build, ctx.search_index_js), "w") do io
        println(io, "var documenterSearchIndex = {\"docs\":")
        # convert Vector{SearchRecord} to a JSON string, and escape two Unicode
        # characters since JSON is not a JS subset, and we want JS here
        # ref http://timelessrepo.com/json-isnt-a-javascript-subset
        escapes = ('\u2028' => "\\u2028", '\u2029' => "\\u2029")
        js = reduce(replace, escapes, init=JSON.json(ctx.search_index))
        println(io, js, "\n}")
    end
end

"""
Copies an asset from Documenters `assets/html/` directory to `doc.user.build`.
Returns the path of the copied asset relative to `.build`.
"""
function copy_asset(file, doc)
    src = joinpath(Utilities.assetsdir(), "html", file)
    alt_src = joinpath(doc.user.source, "assets", file)
    dst = joinpath(doc.user.build, "assets", file)
    isfile(src) || error("Asset '$file' not found at $(abspath(src))")

    # Since user's alternative assets are already copied over in a previous build
    # step and they should override documenter's original assets, we only actually
    # perform the copy if <source>/assets/<file> does not exist. Note that checking
    # the existence of <build>/assets/<file> is not sufficient since the <build>
    # directory might be dirty from a previous build.
    if isfile(alt_src)
        @warn "not copying '$src', provided by the user."
    else
        ispath(dirname(dst)) || mkpath(dirname(dst))
        ispath(dst) && @warn "overwriting '$dst'."
        cp(src, dst, force=true)
    end
    assetpath = normpath(joinpath("assets", file))
    # Replace any backslashes in links, if building the docs on Windows
    return replace(assetpath, '\\' => '/')
end

# Page
# ------------------------------------------------------------------------------

"""
Constructs and writes the page referred to by the `navnode` to `.build`.
"""
function render_page(ctx, navnode)
    @tags html body

    page = getpage(ctx, navnode)

    head = render_head(ctx, navnode)
    navmenu = render_navmenu(ctx, navnode)
    article = render_article(ctx, navnode)

    htmldoc = DOM.HTMLDocument(
        html[:lang=>"en"](
            head,
            body(navmenu, article)
        )
    )

    open_output(ctx, navnode) do io
        print(io, htmldoc)
    end
end

function render_head(ctx, navnode)
    @tags head meta link script title
    src = get_url(ctx, navnode)

    page_title = "$(mdflatten(pagetitle(ctx, navnode))) · $(ctx.doc.user.sitename)"
    css_links = [
        normalize_css,
        google_fonts,
        fontawesome_css,
        highlightjs_css,
    ]
    head(
        meta[:charset=>"UTF-8"],
        meta[:name => "viewport", :content => "width=device-width, initial-scale=1.0"],
        title(page_title),

        analytics_script(ctx.settings.analytics),

        canonical_link_element(ctx.settings.canonical, src),

        # Stylesheets.
        map(css_links) do each
            link[:href => each, :rel => "stylesheet", :type => "text/css"]
        end,

        script("documenterBaseURL=\"$(relhref(src, "."))\""),
        script[
            :src => requirejs_cdn,
            Symbol("data-main") => relhref(src, ctx.documenter_js)
        ],

        script[:src => relhref(src, "siteinfo.js")],
        script[:src => relhref(src, "../versions.js")],

        # Custom user-provided assets.
        asset_links(src, ctx.local_assets)
    )
end

function asset_links(src::AbstractString, assets::Vector)
    @tags link script
    links = DOM.Node[]
    for each in assets
        ext = splitext(each)[end]
        url = relhref(src, each)
        node =
            ext == ".ico" ? link[:href  => url, :rel => "icon", :type => "image/x-icon"] :
            ext == ".css" ? link[:href  => url, :rel => "stylesheet", :type => "text/css"] :
            ext == ".js"  ? script[:src => url] : continue # Skip non-js/css files.
        push!(links, node)
    end
    return links
end

analytics_script(tracking_id::AbstractString) =
    isempty(tracking_id) ? Tag(Symbol("#RAW#"))("") : Tag(:script)(
        """
        (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
        (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
        m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
        })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');

        ga('create', '$(tracking_id)', 'auto');
        ga('send', 'pageview');
        """
    )

function canonical_link_element(canonical_link, src)
   @tags link
   if canonical_link === nothing
      return Tag(Symbol("#RAW#"))("")
   else
      canonical_link_stripped = rstrip(canonical_link, '/')
      href = "$canonical_link_stripped/$src"
      return link[:rel => "canonical", :href => href]
   end
end

## Search page
# ------------

function render_search(ctx)
    @tags article body h1 header hr html li nav p span ul script

    src = get_url(ctx, ctx.search_navnode)

    head = render_head(ctx, ctx.search_navnode)
    navmenu = render_navmenu(ctx, ctx.search_navnode)
    article = article(
        header(
            nav(ul(li("Search"))),
            hr(),
            render_topbar(ctx, ctx.search_navnode),
        ),
        h1("Search"),
        p["#search-info"]("Number of results: ", span["#search-results-number"]("loading...")),
        ul["#search-results"]
    )

    htmldoc = DOM.HTMLDocument(
        html[:lang=>"en"](
            head,
            body(navmenu, article),
            script[:src => relhref(src, ctx.search_index_js)],
            script[:src => relhref(src, ctx.search_js)],
        )
    )
    open_output(ctx, ctx.search_navnode) do io
        print(io, htmldoc)
    end
end

# Navigation menu
# ------------------------------------------------------------------------------

function render_navmenu(ctx, navnode)
    @tags a form h1 img input nav div select option

    src = get_url(ctx, navnode)

    navmenu = nav[".toc"]
    if !isempty(ctx.logo)
        push!(navmenu.nodes,
            # the logo will point to the first page in the navigation menu
            a[:href => navhref(ctx, first(ctx.doc.internal.navlist), navnode)](
                img[
                    ".logo",
                    :src => relhref(src, ctx.logo),
                    :alt => "$(ctx.doc.user.sitename) logo"
                ]
            )
        )
    end
    push!(navmenu.nodes, h1(ctx.doc.user.sitename))
    let version_selector = select["#version-selector", :onChange => "window.location.href=this.value"]()
        if isempty(ctx.doc.user.version)
            push!(version_selector.attributes, :style => "visibility: hidden")
        else
            push!(version_selector.nodes,
                option[
                    :value => "#",
                    :selected => "selected",
                ](ctx.doc.user.version)
            )
        end
        push!(navmenu.nodes, version_selector)
    end
    push!(navmenu.nodes,
        form[".search#search-form", :action => navhref(ctx, ctx.search_navnode, navnode)](
            input[
                "#search-query",
                :name => "q",
                :type => "text",
                :placeholder => "Search docs",
            ],
        )
    )
    push!(navmenu.nodes, navitem(ctx, navnode))
    navmenu
end

"""
[`navitem`](@ref) returns the lists and list items of the navigation menu.
It gets called recursively to construct the whole tree.

It always returns a [`DOM.Node`](@ref). If there's nothing to display (e.g. the node is set
to be invisible), it returns an empty text node (`DOM.Node("")`).
"""
navitem(ctx, current) = navitem(ctx, current, ctx.doc.internal.navtree)
function navitem(ctx, current, nns::Vector)
    nodes = map(nn -> navitem(ctx, current, nn), nns)
    filter!(node -> node.name !== DOM.TEXT, nodes)
    isempty(nodes) ? DOM.Node("") : DOM.Tag(:ul)(nodes)
end
function navitem(ctx, current, nn::Documents.NavNode)
    @tags ul li span a

    # We'll do the children first, primarily to determine if this node has any that are
    # visible. If it does not and it itself is not visible (including current), then
    # we'll hide this one as well, returning an empty string Node.
    children = navitem(ctx, current, nn.children)
    if nn !== current && !nn.visible && children.name === DOM.TEXT
        return DOM.Node("")
    end

    # construct this item
    title = mdconvert(pagetitle(ctx, nn); droplinks=true)
    link = if nn.page === nothing
        span[".toctext"](title)
    else
        a[".toctext", :href => navhref(ctx, nn, current)](title)
    end
    item = (nn === current) ? li[".current"](link) : li(link)

    # add the subsections (2nd level headings) from the page
    if (nn === current) && current.page !== nothing
        subs = collect_subsections(ctx.doc.internal.pages[current.page])
        internal_links = map(subs) do s
            istoplevel, anchor, text = s
            _li = istoplevel ? li[".toplevel"] : li[]
            _li(a[".toctext", :href => anchor](mdconvert(text; droplinks=true)))
        end
        push!(item.nodes, ul[".internal"](internal_links))
    end

    # add the visible subsections, if any, as a single list
    (children.name === DOM.TEXT) || push!(item.nodes, children)

    item
end

# Article (page contents)
# ------------------------------------------------------------------------------

function render_article(ctx, navnode)
    @tags article header footer nav ul li hr span a

    header_links = map(Documents.navpath(navnode)) do nn
        title = mdconvert(pagetitle(ctx, nn); droplinks=true)
        nn.page === nothing ? li(title) : li(a[:href => navhref(ctx, nn, navnode)](title))
    end

    topnav = nav(ul(header_links))

    # Set the logo and name for the "Edit on.." button.
    host_type = Utilities.repo_host_from_url(ctx.doc.user.repo)
    if host_type == Utilities.RepoGitlab
        host = "GitLab"
        logo = "\uf296"
    elseif host_type == Utilities.RepoGithub
        host = "GitHub"
        logo = "\uf09b"
    elseif host_type == Utilities.RepoBitbucket
        host = "BitBucket"
        logo = "\uf171"
    else
        host = ""
        logo = "\uf15c"
    end
    hoststring = isempty(host) ? " source" : " on $(host)"

    if !ctx.settings.disable_git
        pageurl = get(getpage(ctx, navnode).globals.meta, :EditURL, getpage(ctx, navnode).source)
        if Utilities.isabsurl(pageurl)
            url = pageurl
        else
            if !(pageurl == getpage(ctx, navnode).source)
                # need to set users path relative the page itself
                pageurl = joinpath(first(splitdir(getpage(ctx, navnode).source)), pageurl)
            end
            url = Utilities.url(ctx.doc.user.repo, pageurl, commit=ctx.settings.edit_branch)
        end
        if url !== nothing
            edit_verb = (ctx.settings.edit_branch === nothing) ? "View" : "Edit"
            push!(topnav.nodes, a[".edit-page", :href => url](span[".fa"](logo), " $(edit_verb)$hoststring"))
        end
    end
    art_header = header(topnav, hr(), render_topbar(ctx, navnode))

    # build the footer with nav links
    art_footer = footer(hr())
    if navnode.prev !== nothing
        direction = span[".direction"]("Previous")
        title = span[".title"](mdconvert(pagetitle(ctx, navnode.prev); droplinks=true))
        link = a[".previous", :href => navhref(ctx, navnode.prev, navnode)](direction, title)
        push!(art_footer.nodes, link)
    end

    if navnode.next !== nothing
        direction = span[".direction"]("Next")
        title = span[".title"](mdconvert(pagetitle(ctx, navnode.next); droplinks=true))
        link = a[".next", :href => navhref(ctx, navnode.next, navnode)](direction, title)
        push!(art_footer.nodes, link)
    end

    pagenodes = domify(ctx, navnode)
    article["#docs"](art_header, pagenodes, art_footer)
end

function render_topbar(ctx, navnode)
    @tags a div span
    page_title = string(mdflatten(pagetitle(ctx, navnode)))
    return div["#topbar"](span(page_title), a[".fa .fa-bars", :href => "#"])
end

# expand the versions argument from the user
# and return entries and needed symlinks
function expand_versions(dir, versions)
    # output: entries and symlinks
    entries = String[]
    symlinks = Pair{String,String}[]

    # read folders and filter out symlinks
    available_folders = readdir(dir)
    cd(() -> filter!(!islink, available_folders), dir)

    # filter and sort release folders
    vnum(x) = VersionNumber(x)
    version_folders = [x for x in available_folders if occursin(Base.VERSION_REGEX, x)]
    sort!(version_folders, lt = (x, y) -> vnum(x) < vnum(y), rev = true)
    release_folders = filter(x -> (v = vnum(x); v.prerelease == () && v.build == ()), version_folders)
    # pre_release_folders = filter(x -> (v = vnum(x); v.prerelease != () || v.build != ()), version_folders)
    major_folders = filter!(x -> (v = vnum(x); v.major != 0),
                            unique(x -> (v = vnum(x); v.major), release_folders))
    minor_folders = filter!(x -> (v = vnum(x); !(v.major == 0 && v.minor == 0)),
                            unique(x -> (v = vnum(x); (v.major, v.minor)), release_folders))
    patch_folders = unique(x -> (v = vnum(x); (v.major, v.minor, v.patch)), release_folders)

    filter!(x -> vnum(x) !== 0, major_folders)

    # populate output
    for entry in versions
        if entry == "v#" # one doc per major release
            for x in major_folders
                vstr = "v$(vnum(x).major).$(vnum(x).minor)"
                push!(entries, vstr)
                push!(symlinks, vstr => x)
            end
        elseif entry == "v#.#" # one doc per minor release
            for x in minor_folders
                vstr = "v$(vnum(x).major).$(vnum(x).minor)"
                push!(entries, vstr)
                push!(symlinks, vstr => x)
            end
        elseif entry == "v#.#.#" # one doc per patch release
            for x in patch_folders
                vstr = "v$(vnum(x).major).$(vnum(x).minor).$(vnum(x).patch)"
                push!(entries, vstr)
                push!(symlinks, vstr => x)
            end
        elseif entry == "v^" || (entry isa Pair && entry.second == "v^")
            if !isempty(release_folders)
                x = first(release_folders)
                vstr = isa(entry, Pair) ? entry.first : "v$(vnum(x).major).$(vnum(x).minor)"
                push!(entries, vstr)
                push!(symlinks, vstr => x)
            end
        elseif entry isa Pair
            k, v = entry
            i = findfirst(==(v), available_folders)
            if i === nothing
                @warn "no match for `versions` entry `$(repr(entry))`"
            else
                push!(entries, k)
                push!(symlinks, k => v)
            end
        else
            @warn "no match for `versions` entry `$(repr(entry))`"
        end
    end
    unique!(entries) # remove any duplicates

    # generate remaining symlinks
    foreach(x -> push!(symlinks, "v$(vnum(x).major)" => x), major_folders)
    foreach(x -> push!(symlinks, "v$(vnum(x).major).$(vnum(x).minor)" => x), minor_folders)
    foreach(x -> push!(symlinks, "v$(vnum(x).major).$(vnum(x).minor).$(vnum(x).patch)" => x), patch_folders)
    filter!(x -> x.first != x.second, unique!(symlinks))

    # assert that none of the links point to another link
    for link in symlinks
        i = findfirst(x -> link.first == x.second, symlinks)
        if i !== nothing
            throw(ArgumentError("link `$(link)` incompatible with link `$(symlinks[i])`."))
        end
    end

    return entries, symlinks
end

# write version file
function generate_version_file(versionfile::AbstractString, entries)
    open(versionfile, "w") do buf
        println(buf, "var DOC_VERSIONS = [")
        for folder in entries
            println(buf, "  \"", folder, "\",")
        end
        println(buf, "];")
    end
end

function generate_siteinfo_file(dir::AbstractString, version::AbstractString)
    open(joinpath(dir, "siteinfo.js"), "w") do buf
        println(buf, "var DOCUMENTER_CURRENT_VERSION = \"$(version)\";")
    end
end

## domify(...)
# ------------

"""
Converts recursively a [`Documents.Page`](@ref), `Markdown` or Documenter
`*Node` objects into HTML DOM.
"""
function domify(ctx, navnode)
    page = getpage(ctx, navnode)
    map(page.elements) do elem
        rec = SearchRecord(ctx, navnode, elem)
        push!(ctx.search_index, rec)
        domify(ctx, navnode, page.mapping[elem])
    end
end

function domify(ctx, navnode, node)
    fixlinks!(ctx, navnode, node)
    mdconvert(node, Markdown.MD())
end

function domify(ctx, navnode, anchor::Anchors.Anchor)
    @tags a
    aid = "$(anchor.id)-$(anchor.nth)"
    if isa(anchor.object, Markdown.Header)
        h = anchor.object
        fixlinks!(ctx, navnode, h)
        DOM.Tag(Symbol("h$(Utilities.header_level(h))"))(
            a[".nav-anchor", :id => aid, :href => "#$aid"](mdconvert(h.text, h))
        )
    else
        a[".nav-anchor", :id => aid, :href => "#$aid"](domify(ctx, navnode, anchor.object))
    end
end

struct ListBuilder
    es::Vector
end
ListBuilder() = ListBuilder([])

import Base: push!
function push!(lb::ListBuilder, level, node)
    @assert level >= 1
    if level == 1
        push!(lb.es, node)
    else
        if isempty(lb.es) || typeof(last(lb.es)) !== ListBuilder
            push!(lb.es, ListBuilder())
        end
        push!(last(lb.es), level-1, node)
    end
end

function domify(lb::ListBuilder)
    @tags ul li
    ul(map(e -> isa(e, ListBuilder) ? domify(e) : li(e), lb.es))
end

function domify(ctx, navnode, contents::Documents.ContentsNode)
    @tags a
    navnode_dir = dirname(navnode.page)
    navnode_url = get_url(ctx, navnode)
    lb = ListBuilder()
    for (count, path, anchor) in contents.elements
        path = joinpath(navnode_dir, path) # links in ContentsNodes are relative to current page
        path = pretty_url(ctx, relhref(navnode_url, get_url(ctx, path)))
        header = anchor.object
        url = string(path, '#', anchor.id, '-', anchor.nth)
        node = a[:href=>url](mdconvert(header.text; droplinks=true))
        level = Utilities.header_level(header)
        push!(lb, level, node)
    end
    domify(lb)
end

function domify(ctx, navnode, index::Documents.IndexNode)
    @tags a code li ul
    navnode_dir = dirname(navnode.page)
    navnode_url = get_url(ctx, navnode)
    lis = map(index.elements) do el
        object, doc, path, mod, cat = el
        path = joinpath(navnode_dir, path) # links in IndexNodes are relative to current page
        path = pretty_url(ctx, relhref(navnode_url, get_url(ctx, path)))
        url = string(path, "#", Utilities.slugify(object))
        li(a[:href=>url](code("$(object.binding)")))
    end
    ul(lis)
end

function domify(ctx, navnode, docs::Documents.DocsNodes)
    [domify(ctx, navnode, node) for node in docs.nodes]
end

function domify(ctx, navnode, node::Documents.DocsNode)
    @tags a code div section span

    # push to search index
    rec = SearchRecord(ctx, navnode;
        loc=node.anchor.id,
        title=string(node.object.binding),
        category=Utilities.doccat(node.object),
        text = mdflatten(node.docstr))

    push!(ctx.search_index, rec)

    section[".docstring"](
        div[".docstring-header"](
            a[".docstring-binding", :id=>node.anchor.id, :href=>"#$(node.anchor.id)"](code("$(node.object.binding)")),
            " — ", # —
            span[".docstring-category"]("$(Utilities.doccat(node.object))"),
            "."
        ),
        domify_doc(ctx, navnode, node.docstr)
    )
end

function domify_doc(ctx, navnode, md::Markdown.MD)
    @tags a
    if haskey(md.meta, :results)
        # The `:results` field contains a vector of `Docs.DocStr` objects associated with
        # each markdown object. The `DocStr` contains data such as file and line info that
        # we need for generating correct source links.
        map(zip(md.content, md.meta[:results])) do md
            markdown, result = md
            ret = Any[domify(ctx, navnode, Writers.MarkdownWriter.dropheaders(markdown))]
            # When a source link is available then print the link.
            if !ctx.settings.disable_git
                url = Utilities.url(ctx.doc.internal.remote, ctx.doc.user.repo, result)
                if url !== nothing
                    push!(ret, a[".source-link", :target=>"_blank", :href=>url]("source"))
                end
            end
            ret
        end
    else
        # Docstrings with no `:results` metadata won't contain source locations so we don't
        # try to print them out. Just print the basic docstring.
        domify(ctx, navnode, Writers.MarkdownWriter.dropheaders(md))
    end
end

function domify(ctx, navnode, node::Documents.EvalNode)
    node.result === nothing ? DOM.Node[] : domify(ctx, navnode, node.result)
end

# nothing to show for MetaNodes, so we just return an empty list
domify(ctx, navnode, node::Documents.MetaNode) = DOM.Node[]

function domify(ctx, navnode, raw::Documents.RawNode)
    raw.name === :html ? Tag(Symbol("#RAW#"))(raw.text) : DOM.Node[]
end

# Utilities
# ------------------------------------------------------------------------------

"""
Opens the output file of the `navnode` in write node. If necessary, the path to the output
file is created before opening the file.
"""
function open_output(f, ctx, navnode)
    path = joinpath(ctx.doc.user.build, get_url(ctx, navnode))
    isdir(dirname(path)) || mkpath(dirname(path))
    open(f, path, "w")
end

"""
Get the relative hyperlink between two [`Documents.NavNode`](@ref)s. Assumes that both
[`Documents.NavNode`](@ref)s have an associated [`Documents.Page`](@ref) (i.e. `.page`
is not `nothing`).
"""
navhref(ctx, to, from) = pretty_url(ctx, relhref(get_url(ctx, from), get_url(ctx, to)))

"""
Calculates a relative HTML link from one path to another.
"""
function relhref(from, to)
    pagedir = dirname(from)
    # The regex separator replacement is necessary since otherwise building the docs on
    # Windows will result in paths that have `//` separators which break asset inclusion.
    replace(relpath(to, isempty(pagedir) ? "." : pagedir), r"[/\\]+" => "/")
end

"""
Returns the full path corresponding to a path of a `.md` page file. The the input and output
paths are assumed to be relative to `src/`.
"""
function get_url(ctx, path::AbstractString)
    if ctx.settings.prettyurls
        d = if basename(path) == "index.md"
            dirname(path)
        else
            first(splitext(path))
        end
        isempty(d) ? "index.html" : "$d/index.html"
    else
        # change extension to .html
        string(splitext(path)[1], ".html")
    end
end

"""
Returns the full path of a [`Documents.NavNode`](@ref) relative to `src/`.
"""
get_url(ctx, navnode::Documents.NavNode) = get_url(ctx, navnode.page)

"""
If `prettyurls` for [`HTML`](@ref Documenter.HTML) is enabled, returns a "pretty" version of
the `path` which can then be used in links in the resulting HTML file.
"""
function pretty_url(ctx, path::AbstractString)
    if ctx.settings.prettyurls
        dir, file = splitdir(path)
        if file == "index.html"
            return length(dir) == 0 ? "" : "$(dir)/"
        end
    end
    return path
end

"""
Tries to guess the page title by looking at the `<h1>` headers and returns the
header contents of the first `<h1>` on a page (or `nothing` if the algorithm
was unable to find any `<h1>` headers).
"""
function pagetitle(page::Documents.Page)
    title = nothing
    for element in page.elements
        if isa(element, Markdown.Header{1})
            title = element.text
            break
        end
    end
    title
end

function pagetitle(ctx, navnode::Documents.NavNode)
    if navnode.title_override !== nothing
        # parse title_override as markdown
        md = Markdown.parse(navnode.title_override)
        # Markdown.parse results in a paragraph so we need to strip that
        if !(length(md.content) === 1 && isa(first(md.content), Markdown.Paragraph))
            error("Bad Markdown provided for page title: '$(navnode.title_override)'")
        end
        return first(md.content).content
    end

    if navnode.page !== nothing
        title = pagetitle(getpage(ctx, navnode))
        title === nothing || return title
    end

    "-"
end

"""
Returns an ordered list of tuples, `(toplevel, anchor, text)`, corresponding to level 1 and 2
headings on the `page`. Note that if the first header on the `page` is a level 1 header then
it is not included -- it is assumed to be the page title and so does not need to be included
in the navigation menu twice.
"""
function collect_subsections(page::Documents.Page)
    sections = []
    title_found = false
    for element in page.elements
        if isa(element, Markdown.Header) && Utilities.header_level(element) < 3
            toplevel = Utilities.header_level(element) === 1
            # Don't include the first header if it is `h1`.
            if toplevel && isempty(sections) && !title_found
                title_found = true
                continue
            end
            anchor = page.mapping[element]
            push!(sections, (toplevel, "#$(anchor.id)-$(anchor.nth)", element.text))
        end
    end
    return sections
end

# mdconvert
# ------------------------------------------------------------------------------

const md_block_nodes = [Markdown.MD, Markdown.BlockQuote]
push!(md_block_nodes, Markdown.List)
push!(md_block_nodes, Markdown.Admonition)

"""
[`MDBlockContext`](@ref) is a union of all the Markdown nodes whose children should
be blocks. It can be used to dispatch on all the block-context nodes at once.
"""
const MDBlockContext = Union{md_block_nodes...}

"""
Convert a markdown object to a `DOM.Node` object.

The `parent` argument is passed to allow for context-dependant conversions.
"""
mdconvert(md; kwargs...) = mdconvert(md, md; kwargs...)

mdconvert(text::AbstractString, parent; kwargs...) = DOM.Node(text)

mdconvert(vec::Vector, parent; kwargs...) = [mdconvert(x, parent; kwargs...) for x in vec]

mdconvert(md::Markdown.MD, parent; kwargs...) = Tag(:div)(mdconvert(md.content, md; kwargs...))

mdconvert(b::Markdown.BlockQuote, parent; kwargs...) = Tag(:blockquote)(mdconvert(b.content, b; kwargs...))

mdconvert(b::Markdown.Bold, parent; kwargs...) = Tag(:strong)(mdconvert(b.text, parent; kwargs...))

function mdconvert(c::Markdown.Code, parent::MDBlockContext; kwargs...)
    @tags pre code
    language = isempty(c.language) ? "none" : c.language
    pre(code[".language-$(language)"](c.code))
end
mdconvert(c::Markdown.Code, parent; kwargs...) = Tag(:code)(c.code)

mdconvert(h::Markdown.Header{N}, parent; kwargs...) where {N} = DOM.Tag(Symbol("h$N"))(mdconvert(h.text, h; kwargs...))

mdconvert(::Markdown.HorizontalRule, parent; kwargs...) = Tag(:hr)()

mdconvert(i::Markdown.Image, parent; kwargs...) = Tag(:img)[:src => i.url, :alt => i.alt]

mdconvert(i::Markdown.Italic, parent; kwargs...) = Tag(:em)(mdconvert(i.text, i; kwargs...))

mdconvert(m::Markdown.LaTeX, ::MDBlockContext; kwargs...)   = Tag(:div)(string("\\[", m.formula, "\\]"))
mdconvert(m::Markdown.LaTeX, parent; kwargs...) = Tag(:span)(string('$', m.formula, '$'))

mdconvert(::Markdown.LineBreak, parent; kwargs...) = Tag(:br)()

function mdconvert(link::Markdown.Link, parent; droplinks=false, kwargs...)
    link_text = mdconvert(link.text, link; droplinks=droplinks, kwargs...)
    droplinks ? link_text : Tag(:a)[:href => link.url](link_text)
end

mdconvert(list::Markdown.List, parent; kwargs...) = (Markdown.isordered(list) ? Tag(:ol) : Tag(:ul))(map(Tag(:li), mdconvert(list.items, list; kwargs...)))

mdconvert(paragraph::Markdown.Paragraph, parent; kwargs...) = Tag(:p)(mdconvert(paragraph.content, paragraph; kwargs...))

# For compatibility with versions before Markdown.List got the `loose field, Julia PR #26598
const list_has_loose_field = :loose in fieldnames(Markdown.List)
function mdconvert(paragraph::Markdown.Paragraph, parent::Markdown.List; kwargs...)
    content = mdconvert(paragraph.content, paragraph; kwargs...)
    return (list_has_loose_field && !parent.loose) ? content : Tag(:p)(content)
end

function mdconvert(t::Markdown.Table, parent; kwargs...)
    @tags table tr th td
    alignment_style = map(t.align) do align
        if align == :r
            "text-align: right"
        elseif align == :c
            "text-align: center"
        else
            "text-align: left"
        end
    end
    table(
        tr(map(enumerate(t.rows[1])) do (i, x)
            th[:style => alignment_style[i]](mdconvert(x, t; kwargs...))
        end),
        map(t.rows[2:end]) do x
            tr(map(enumerate(x)) do (i, y) # each cell in a row
                td[:style => alignment_style[i]](mdconvert(y, x; kwargs...))
            end)
        end
    )
end

mdconvert(expr::Union{Expr,Symbol}, parent; kwargs...) = string(expr)

mdconvert(f::Markdown.Footnote, parent; kwargs...) = footnote(f.id, f.text, parent; kwargs...)
footnote(id, text::Nothing, parent; kwargs...) = Tag(:a)[:href => "#footnote-$(id)"]("[$id]")
function footnote(id, text, parent; kwargs...)
    Tag(:div)[".footnote#footnote-$(id)"](
        Tag(:a)[:href => "#footnote-$(id)"](Tag(:strong)("[$id]")),
        mdconvert(text, parent; kwargs...),
    )
end

function mdconvert(a::Markdown.Admonition, parent; kwargs...)
    @tags div
    div[".admonition.$(a.category)"](
        div[".admonition-title"](a.title),
        div[".admonition-text"](mdconvert(a.content, a; kwargs...))
    )
end

mdconvert(html::Documents.RawHTML, parent; kwargs...) = Tag(Symbol("#RAW#"))(html.code)

# Select the "best" representation for HTML output.
mdconvert(mo::Documents.MultiOutput, parent; kwargs...) =
    Base.invokelatest(mdconvert, mo.content, parent; kwargs...)
function mdconvert(d::Dict{MIME,Any}, parent; kwargs...)
    if haskey(d, MIME"text/html"())
        out = Documents.RawHTML(d[MIME"text/html"()])
    elseif haskey(d, MIME"image/svg+xml"())
        out = Documents.RawHTML(d[MIME"image/svg+xml"()])
    elseif haskey(d, MIME"image/png"())
        out = Documents.RawHTML(string("<img src=\"data:image/png;base64,", d[MIME"image/png"()], "\" />"))
    elseif haskey(d, MIME"image/webp"())
        out = Documents.RawHTML(string("<img src=\"data:image/webp;base64,", d[MIME"image/webp"()], "\" />"))
    elseif haskey(d, MIME"image/gif"())
        out = Documents.RawHTML(string("<img src=\"data:image/gif;base64,", d[MIME"image/gif"()], "\" />"))
    elseif haskey(d, MIME"image/jpeg"())
        out = Documents.RawHTML(string("<img src=\"data:image/jpeg;base64,", d[MIME"image/jpeg"()], "\" />"))
    elseif haskey(d, MIME"text/latex"())
        out = Utilities.mdparse(d[MIME"text/latex"()]; mode = :single)
    elseif haskey(d, MIME"text/markdown"())
        out = Markdown.parse(d[MIME"text/markdown"()])
    elseif haskey(d, MIME"text/plain"())
        out = Markdown.Code(d[MIME"text/plain"()])
    else
        error("this should never happen.")
    end
    return mdconvert(out, parent; kwargs...)
end

# fixlinks!
# ------------------------------------------------------------------------------

"""
Replaces URLs in `Markdown.Link` elements (if they point to a local `.md` page) with the
actual URLs.
"""
function fixlinks!(ctx, navnode, link::Markdown.Link)
    fixlinks!(ctx, navnode, link.text)
    Utilities.isabsurl(link.url) && return

    # links starting with a # are references within the same file -- there's nothing to fix
    # for such links
    startswith(link.url, '#') && return

    s = split(link.url, "#", limit = 2)
    if Sys.iswindows() && ':' in first(s)
        @warn "invalid local link: colons not allowed in paths on Windows in $(Utilities.locrepr(navnode.page))" link = link.url
        return
    end
    path = normpath(joinpath(dirname(navnode.page), first(s)))

    if endswith(path, ".md") && path in keys(ctx.doc.internal.pages)
        # make sure that links to different valid pages are correct
        path = pretty_url(ctx, relhref(get_url(ctx, navnode), get_url(ctx, path)))
    elseif isfile(joinpath(ctx.doc.user.build, path))
        # update links to other files that are present in build/ (e.g. either user
        # provided files or generated by code examples)
        path = relhref(get_url(ctx, navnode), path)
    else
        @warn "invalid local link: unresolved path in $(Utilities.locrepr(navnode.page))" link = link.url
    end

    # Replace any backslashes in links, if building the docs on Windows
    path = replace(path, '\\' => '/')
    link.url = (length(s) > 1) ? "$path#$(last(s))" : String(path)
end

function fixlinks!(ctx, navnode, img::Markdown.Image)
    Utilities.isabsurl(img.url) && return

    if Sys.iswindows() && ':' in img.url
        @warn "invalid local image: colons not allowed in paths on Windows in $(Utilities.locrepr(navnode.page))" link = img.url
        return
    end

    path = joinpath(dirname(navnode.page), img.url)
    if isfile(joinpath(ctx.doc.user.build, path))
        path = relhref(get_url(ctx, navnode), path)
        # Replace any backslashes in links, if building the docs on Windows
        img.url = replace(path, '\\' => '/')
    else
        @warn "invalid local image: unresolved path in $(Utilities.locrepr(navnode.page))" link = img.url
    end
end

fixlinks!(ctx, navnode, md::Markdown.MD) = fixlinks!(ctx, navnode, md.content)
function fixlinks!(ctx, navnode, a::Markdown.Admonition)
    fixlinks!(ctx, navnode, a.title)
    fixlinks!(ctx, navnode, a.content)
end
fixlinks!(ctx, navnode, b::Markdown.BlockQuote) = fixlinks!(ctx, navnode, b.content)
fixlinks!(ctx, navnode, b::Markdown.Bold) = fixlinks!(ctx, navnode, b.text)
fixlinks!(ctx, navnode, f::Markdown.Footnote) = fixlinks!(ctx, navnode, f.text)
fixlinks!(ctx, navnode, h::Markdown.Header) = fixlinks!(ctx, navnode, h.text)
fixlinks!(ctx, navnode, i::Markdown.Italic) = fixlinks!(ctx, navnode, i.text)
fixlinks!(ctx, navnode, list::Markdown.List) = fixlinks!(ctx, navnode, list.items)
fixlinks!(ctx, navnode, p::Markdown.Paragraph) = fixlinks!(ctx, navnode, p.content)
fixlinks!(ctx, navnode, t::Markdown.Table) = fixlinks!(ctx, navnode, t.rows)

fixlinks!(ctx, navnode, mds::Vector) = map(md -> fixlinks!(ctx, navnode, md), mds)
fixlinks!(ctx, navnode, md) = nothing

# TODO: do some regex-magic in raw HTML blocks? Currently ignored.
#fixlinks!(ctx, navnode, md::Documents.RawHTML) = ...

end


text:
using ConfParser
using Test

conf = ConfParse(joinpath(@__DIR__, "confs", "config.ini"))
parse_conf!(conf)

@test retrieve(conf, "database", "user") == "dbuser"
@test retrieve(conf, "database", "password") == "abc123"
@test retrieve(conf, "database", "speed of light (m/s)") == "3e8"
@test commit!(conf, "default", "database", "newuser")
@test erase!(conf, "foobarness")
@test haskey(conf, "database", "user") == true
@test haskey(conf, "database", "nothere") == false
@test haskey(conf, "nothere", "foo") == false
@test retrieve(conf, "Database", "user") == "dbuser"
@test retrieve(conf, "Case", "bar") == "foo"
@test erase!(conf, "Case", "bye")
@test_throws KeyError retrieve(conf, "Case", "bye")
@test haskey(conf, "Case", "bar") == true
@test haskey(conf, "case", "bar") == true
save!(conf, joinpath(@__DIR__, "confs", "out.conf"))

# validate new conf write
conf = ConfParse(joinpath(@__DIR__, "confs", "out.conf"))
parse_conf!(conf)
@test retrieve(conf, "database", "user") == "dbuser"
@test retrieve(conf, "default", "database") == "newuser"


text:
@testset "folder.jl" begin
    dir = pwd()
    opts = (join = true, )
    fs = readdir(dir; opts...)
    @test folderlist(dir; opts...) == fs[.~isfile.(fs)]
    @test isequal(folderlist(dir; join=false), basename.(folderlist(dir; join=true)))
    @test isequal(folderlist(dir), FileTools.datalist(r".*",dir;find="folder").fullpath)
    @test isequal(sort(folderlistall(dir)), sort(FileTools.datalist(r".*",dir;find="folder", method="walkdir").fullpath))
end


text:
function _check_call_inbook(callinfo::LineNumberNode, obj::RBObject)
    csrc, bdir = srcfile(callinfo), bookdir(obj)
    !startswith(csrc, bdir) && error(
        "The call file is outside the book.\n",
        "book at: '", bdir, "'\n",
        "call at: '", csrc, ":", srcline(callinfo), "'"
    )
end

function _check_bang_call(callinfo::LineNumberNode, obj::RBObject)
    csrc, osrc = srcfile(callinfo), srcfile(obj)
    (csrc != osrc) && error(
        "Object modification outside its definition file:\n",
        "obj at: '", osrc, ":", srcline(obj), "'\n",
        "call at: '", csrc, ":", srcline(callinfo), "'"
    )
end

function _add_secobj!(f::Function, callinfo::LineNumberNode)

    # sec
    sec = _check_currsec()

    # TODO: Update book but just if necessary

    # checks
    _check_call_inbook(callinfo, sec)
    _check_bang_call(callinfo, sec)

    obj = f()
    set_sec!(obj, sec)
    srcfile!(obj, srcfile(callinfo))
    srcline!(obj, srcline(callinfo))

    # add to section
    add_obj!(sec, obj)

    currobj!(obj)
end

function _insert_label!(macroname::String, ex::Tuple, callinfo::LineNumberNode)

    if isempty(ex)
        # Insert random label
        macroreg = _macro_call_regex(macroname)
        label = genlabel()
        newcall = string("@", macroname, "(\"", label, "\")")
        _replace_line(callinfo, macroreg, newcall)
    elseif length(ex) == 1 && first(ex) isa String
        label = string(first(ex))
    else
        error("Too many arguments!. Expected either 0 or 1.")
    end
    return label
end


text:
"""
    rankUpdate!(C, A)
    rankUpdate!(C, A, α)
    rankUpdate!(C, A, α, β)

A rank-k update, C := β*C + α*A'A, of a Hermitian (Symmetric) matrix.

`α` and `β` both default to 1.0.  When `α` is -1.0 this is a downdate operation.
The name `rankUpdate!` is borrowed from [https://github.com/andreasnoack/LinearAlgebra.jl]
The order of the arguments
"""
function rankUpdate! end

function rankUpdate!(C::HermOrSym{T,S}, a::StridedVector{T},
        α=true) where {T<:BlasReal,S<:StridedMatrix}
    BLAS.syr!(C.uplo, T(α), a, C.data)
    C  ## to ensure that the return value is HermOrSym
end

function rankUpdate!(C::HermOrSym{T,S}, A::StridedMatrix{T},
        α=true, β=true) where {T<:BlasReal,S<:StridedMatrix}
    BLAS.syrk!(C.uplo, 'N', T(α), A, T(β), C.data)
    C
end

function rankUpdate!(C::HermOrSym{T,Matrix{T}}, A::SparseMatrixCSC{T}, α=true, β=true) where {T}
    m, n = size(A)
    m == size(C, 2) || throw(DimensionMismatch(""))
    C.uplo == 'L' || throw(ArgumentError("C.uplo must be 'L'"))
    Cd = C.data
    isone(β) || rmul!(LowerTriangular(Cd), β)
    rv = rowvals(A)
    nz = nonzeros(A)
    @inbounds for jj in 1:n
        rangejj = nzrange(A, jj)
        lenrngjj = length(rangejj)
        for (k, j) in enumerate(rangejj)
            anzj = α * nz[j]
            rvj = rv[j]
            for i in k:lenrngjj
                kk = rangejj[i]
                Cd[rv[kk], rvj] += nz[kk] * anzj
            end
        end
    end
    C
end

rankUpdate!(C::HermOrSym, A::BlockedSparse, α=true, β=true) = rankUpdate!(C, sparse(A), α, β)

function rankUpdate!(C::Diagonal{T}, A::SparseMatrixCSC{T}, α=true, β=true) where {T <: Number}
    m, n = size(A)
    dd = C.diag
    length(dd) == m || throw(DimensionMismatch(""))
    isone(β) || rmul!(dd, β)
    nz = nonzeros(A)
    rv = rowvals(A)
    @inbounds for j in 1:n
        nzr = nzrange(A, j)
        if !isempty(nzr)
            length(nzr) == 1 || throw(ArgumentError("A*A' has off-diagonal elements"))
            k = nzr[1]
            dd[rv[k]] += α * abs2(nz[k])
        end
    end
    C
end

rankUpdate!(C::Diagonal{T}, A::BlockedSparse{T}, α=true, β=true) where {T <: Number} = rankUpdate!(C, sparse(A), α, β)

function rankUpdate!(C::HermOrSym{T,UniformBlockDiagonal{T}}, A::BlockedSparse{T,S},
        α=true) where {T,S}
    Ac = A.cscmat
    cp = Ac.colptr
    all(diff(cp) .== S) ||
        throw(ArgumentError("Each column of A must contain exactly S nonzeros"))
    j,k,l = size(C.data.data)
    S == j == k && div(Ac.m, S) == l ||
        throw(DimensionMismatch("div(A.cscmat.m, S) ≠ length(C.data.facevec)"))
    nz = Ac.nzval
    rv = Ac.rowval
    Cdf = C.data.facevec
    for j in 1:Ac.n
        nzr = nzrange(Ac, j)
        BLAS.syr!('L', α, view(nz, nzr), Cdf[div(rv[last(nzr)], S)])
    end
    C
end

rankUpdate!(C::HermOrSym{T,Matrix{T}}, A::BlockedSparse{T}, α=true) where {T} = rankUpdate!(C, A.cscmat, α)

function rankUpdate!(C::Diagonal{T,S}, A::Diagonal{T,S}, α::Number=true, β::Number=true) where {T, S}
    length(C.diag) == length(A.diag) ||
        throw(DimensionMismatch("length(C.diag) ≠ length(A.diag)"))

    C.diag .= β .* C.diag .+ α .* abs2.(A.diag)
    C
end


text: Dict{String, Any}("strings" => Any[Dict{String, Any}("value" => "a", "type" => "string"), Dict{String, Any}("value" => "b", "type" => "string"), Dict{String, Any}("value" => "c", "type" => "string")], "dates" => Any[Dict{String, Any}("value" => "1987-07-05T17:45:00Z", "type" => "datetime"), Dict{String, Any}("value" => "1979-05-27T07:32:00Z", "type" => "datetime"), Dict{String, Any}("value" => "2006-06-01T11:00:00Z", "type" => "datetime")], "comments" => Any[Dict{String, Any}("value" => "1", "type" => "integer"), Dict{String, Any}("value" => "2", "type" => "integer")], "ints" => Any[Dict{String, Any}("value" => "1", "type" => "integer"), Dict{String, Any}("value" => "2", "type" => "integer"), Dict{String, Any}("value" => "3", "type" => "integer")], "floats" => Any[Dict{String, Any}("value" => "1.1", "type" => "float"), Dict{String, Any}("value" => "2.1", "type" => "float"), Dict{String, Any}("value" => "3.1", "type" => "float")])


text:
export fetchval

const SHOULD_SEND = Dict(:PATCH => true, :POST => true, :PUT => true)
const RATE_LIMITED = ErrorException("Rate limited")

const EVENTS_FIRED = Dict(
    :DELETE => [
        (r"^/channels/\d+$", ChannelDelete),
        (r"^/channels/\d+$", ChannelUpdate),
        (r"^/channels/\d+/messages/\d+/reactions/.+/@me$", MessageReactionRemove),
        (r"^/channels/\d+/messages/\d+/reactions/.+/\d+$", MessageReactionRemove),
        (r"^/channels/\d+/messages/\d+/reactions$", MessageReactionRemoveAll),
        (r"^/channels/\d+/messages/\d+$", MessageDelete),
        (r"^/channels/\d+/messages/bulk-delete$", MessageDeleteBulk),
        (r"^/channels/\d+/permissions/\d+$", ChannelUpdate),
        (r"^/channels/\d+/pins/\d+$", ChannelPinsUpdate),
        (r"^/channels/\d+/pins/\d+$", MessageUpdate),
        (r"^/channels/\d+/recipients/\d+$", ChannelUpdate),  # Untested.
        (r"^/guilds/\d+/emojis/\d+$", GuildEmojisUpdate),
        (r"^/guilds/\d+$", GuildDelete),
        (r"^/guilds/\d+/members/\d+/roles/\d+$", GuildMemberUpdate),
        (r"^/guilds/\d+/members/\d+/$", GuildMemberRemove),
        (r"^/guilds/\d+/bans/\d+$", GuildBanRemove),
        (r"^/guilds/\d+/roles/\d+$", GuildRoleDelete),
        (r"^/guilds/\d+/integrations$", GuildIntegrationsUpdate),
        (r"^/users/@me/guilds/\d+$", GuildMemberRemove),
        (r"^/users/@me/guilds/\d+$", PresenceUpdate),
        (r"^/webhooks/\d+$", WebhooksUpdate),
        (r"^/webhooks/\d+/.+$", WebhooksUpdate),
    ],
    :POST => [
        (r"^/channels/\d+/messages$", MessageCreate),
        (r"^/channels/\d+/typing$", TypingStart),
        (r"^/guilds/\d+/emojis$", GuildEmojisUpdate),
        (r"^/guilds$", GuildCreate),
        (r"^/guilds/\d+/channels$", ChannelCreate),
        (r"^/guilds/\d+/roles$", GuildRoleCreate),
        (r"^/guilds/\d+/prune$", GuildMemberRemove),
        (r"^/guilds/\d+/integrations$", GuildIntegrationsUpdate),
        (r"^/users/@me/channels$", ChannelCreate),
        (r"^/channels/\d+/webhooks$", WebhooksUpdate),
    ],
    :PUT => [
        (r"^/channels/\d+$", ChannelUpdate),
        (r"^/channels/\d+/messages/\d+/reactions/.+/@me$", MessageReactionAdd),
        (r"^/channels/\d+/permissions/\d+$", ChannelUpdate),
        (r"^/channels/\d+/pins/\d+$", ChannelPinsUpdate),
        (r"^/channels/\d+/pins/\d+$", MessageUpdate),
        (r"^/channels/\d+/recipients/\d+$", ChannelUpdate),  # Untested.
        (r"^/guilds/\d+/members/\d+$", GuildMemberAdd),
        (r"^/guilds/\d+/members/\d+/roles/\d+$", GuildMemberUpdate),
        (r"^/guilds/\d+/bans/\d+$", GuildBanAdd),
    ],
    :PATCH => [
        (r"^/channels/\d+$", ChannelUpdate),
        (r"^/channels/\d+/messages/\d+$", MessageUpdate),
        (r"^/guilds/\d+/emojis/\d+$", GuildEmojisUpdate),
        (r"^/guilds/\d+$", GuildUpdate),
        (r"^/guilds/\d+/channels$", ChannelUpdate),
        (r"^/guilds/\d+/members/\d+$", GuildMemberUpdate),
        (r"^/guilds/\d+/members/@me/nick$", GuildMemberUpdate),
        (r"^/guilds/\d+/roles$", GuildRoleUpdate),
        (r"^/guilds/\d+/roles/\d+$", GuildRoleUpdate),
        (r"^/guilds/\d+/integrations$", GuildIntegrationsUpdate),
        (r"^/users/@me$", UserUpdate),
        (r"^/webhooks/\d+$", WebhooksUpdate),
        (r"^/webhooks/\d+/.+$", WebhooksUpdate),
    ],
)

"""
A wrapper around a response from the REST API. Every function which wraps a Discord REST
API endpoint returns a `Future` which will contain a value of this type. To retrieve the
`Response` from the `Future`, use `fetch` or [`fetchval`](@ref).

# Fields
- `val::Union{T, Nothing}`: The object contained in the HTTP response. For example, for a
  call to [`get_channel_message`](@ref), this value will be a [`Message`](@ref).
- `ok::Bool`: The state of the request. If `true`, then it is safe to access `val`.
- `http_response::Union{HTTP.Messages.Response, Nothing}`: The underlying HTTP response, if
  a request was made.
- `exception::Union{Exception, Nothing}`: The caught exception, if one is thrown.

# Example
```julia-repl
julia> using Discord; c = Client("token"); ch = 1234567890;

julia> fs = map(i -> Discord.create_message(c, ch; content=string(i)), 1:10);

julia> typeof(first(fs))
Distributed.Future

julia> typeof(fetch(first(fs)))
Discord.Response{Message}
```
"""
struct Response{T}
    val::Union{T, Nothing}
    ok::Bool
    http_response::Union{HTTP.Messages.Response, Nothing}
    exception::Union{Exception, Nothing}
end

# HTTP response with no body.
function Response{Nothing}(r::HTTP.Messages.Response)
    return Response{Nothing}(nothing, r.status < 300, r, nothing)
end

# HTTP response with body (maybe).
function Response{T}(c::Client, r::HTTP.Messages.Response) where T
    r.status == 429 && throw(RATE_LIMITED)
    r.status == 204 && return Response{T}(nothing, true, r, nothing)
    r.status >= 300 && return Response{T}(nothing, false, r, nothing)

    data = if HTTP.header(r, "Content-Type") == "application/json"
        JSON.parse(String(copy(r.body)))
    else
        copy(r.body)
    end

    val, e = tryparse(c, T, data)
    return Response{T}(val, e === nothing, r, e)
end

# HTTP request with no expected response body.
function Response(
    c::Client,
    method::Symbol,
    endpoint::AbstractString;
    body="",
    kwargs...
)
    return Response{Nothing}(c, method, endpoint; body=body, kwargs...)
end

# HTTP request.
function Response{T}(
    c::Client,
    method::Symbol,
    endpoint::AbstractString;
    headers=Dict(),
    body=HTTP.nobody,
    kwargs...
) where T
    f = Future()

    @async begin
        kws = (
            channel=cap("channels", endpoint),
            guild=cap("guilds", endpoint),
            message=cap("messages", endpoint),
            user=cap("users", endpoint),
        )

        if c.use_cache && method === :GET
            val = get(c.state, T; kws...)
            if val !== nothing
                put!(f, Response{T}(val, true, nothing, nothing))
                return
            end
        end

        url = "$DISCORD_API/v$(c.version)$endpoint"
        isempty(kwargs) || (url *= "?" * HTTP.escapeuri(kwargs))
        headers = merge(Dict(
            "User-Agent" => "Discord.jl $DISCORD_JL_VERSION",
            "Content-Type" => "application/json",
            "Authorization" => c.token,
        ), Dict(headers))
        args = [method, url, headers]
        if get(SHOULD_SEND, method, false)
            push!(args, headers["Content-Type"] == "application/json" ? json(body) : body)
        end

        # Acquire the lock, then check if we're rate limited. If we are, then release the
        # lock and wait for the reset. Once we get the lock back and we're not rate
        # limited, we can go through with the request (at that point we know we're the only
        # task requesting from that endpoint). We update the bucket (we are still the only
        # task touching the bucket) and then release the lock.

        b = Bucket(c.limiter, method, endpoint)
        while true
            lock(b)

            if islimited(c.limiter, b)
                unlock(b)
                wait(c.limiter, b)
            else
                local http_r = nothing
                try
                    http_r = HTTP.request(args...; status_exception=false)
                    r = Response{T}(c, http_r)
                    if r.ok && r.val !== nothing && should_put(c, method, endpoint)
                        r = @set r.val = put!(c.state, r.val; kws...)
                    end
                    put!(f, r)
                    update!(c.limiter, b, http_r)
               catch e
                    # If we're rate limited, then just go back to the top.
                    e == RATE_LIMITED && continue
                    logmsg(c, ERROR, catchmsg(e))
                    put!(f, Response{T}(nothing, false, http_r, e))
                finally
                    unlock(b)
                end

                break  # If we reached here, it means we got the request through.
            end
        end
    end

    return f
end

Base.eltype(::Response{T}) where T = T
Base.eltype(::Type{Response{T}}) where T = T

"""
    fetchval(f::Future{Response{T}}) -> Union{T, Nothing}

Shortcut for `fetch(f).val`: Fetch a [`Response`](@ref) and return its value. Note that
there are no guarantees about the response's success and the value being returned, and it
discards context that can be useful for debugging, such as HTTP responses and caught
exceptions.
"""
fetchval(f::Future) = fetch(f).val

function cap(path::AbstractString, s::AbstractString)
    m = match(Regex("/$path/(\\d+)"), s)
    return m === nothing ? nothing : parse(Snowflake, first(m.captures))
end

function should_put(c::Client, method::Symbol, endpoint::AbstractString)
    # TODO: Maybe we could use the type of the Response value to be more granular.
    # e.g. if we got a Message, then only check handlers for types with a Message field.
    c.use_cache || return false
    isopen(c) || return true
    method === :GET && return true

    Ts = map(last, filter(t -> match(t[1], endpoint) !== nothing, EVENTS_FIRED[method]))
    return !all(T -> hasdefault(c, T), Ts)
end

include(joinpath("rest", "audit_log.jl"))
include(joinpath("rest", "channel.jl"))
include(joinpath("rest", "emoji.jl"))
include(joinpath("rest", "guild.jl"))
include(joinpath("rest", "invite.jl"))
include(joinpath("rest", "user.jl"))
include(joinpath("rest", "voice.jl"))
include(joinpath("rest", "webhook.jl"))


text:
using Omega
using UnicodePlots
using Flux
using Rotations
# using Plots

function relandscapeexample()
  x = normal(0.0, 1.0)
  y = normal(0.0, 1.0)
  isxy = x ==ₛ y
  ΩT =  SimpleΩ{Vector{Int}, Flux.TrackedArray}
  rand((x, y), isxy, 100, alg = Relandscape, ΩT = ΩT)
end

# samples = relandscapeexample()
# UnicodePlots.densityplot(ntranspose(samples)...)

function relandscapeexample(n = 100)
  x = uniform(0.0, 1.0)
  y = uniform(0.0, 1.0)
  isxy = x >=ₛ y
  ΩT =  SimpleΩ{Vector{Int}, Flux.TrackedArray}
  rand((x, y), isxy, n, alg = Relandscape, ΩT = ΩT), x, y
end

function relandscapeexample(n = 100)
  x = uniform(0.0, 1.0)
  y = uniform(0.0, 1.0)
  isxy = abs(x - y) <ₛ 0.01
  ΩT =  SimpleΩ{Vector{Int}, Flux.TrackedArray}
  rand((x, y), isxy, n, alg = Relandscape, ΩT = ΩT), x, y
end

# samples, x, y = relandscapeexample(3)
# xy = randtuple((x, y))
# xysamples = xy.(samples)
# xyflat = map(tpl -> map(Flux.data, tpl), xysamples)
# UnicodePlots.densityplot(ntranspose(xyflat)...)

mat(f; r = 0.1) = [f(x, y) for x in 0:r:1, y in 0:r:1]
epsa = 1e-5
function matw(f; r = 0.1, ω = rand(defΩ()))
  n = length(0+epsa:r:1-epsa)
  arr = Array{Float64}(undef, n, n)
  f(ω) # init
  xid, yid = keys(ω)
  for x in 1:n, y in 1:n
    ω.vals[xid] = x/n
    ω.vals[yid] = y/n
    arr[x, y] = f(ω)
  end
  arr
end

samples, x, y = relandscapeexample(2)
ω = rand(defΩ())
U_grab(ω)
wave_grab(ω)
r = 0.001
mata = matw(U_grab; r=r, ω = ω)
# mata = matw(wave_grab; r=r, ω = ω)

@show argmax(mata)
@show maximum(mata)
# contour(exp.(mata))
# contour(mata)

rng = 0+epsa:r:1-epsa

using Makie: surface
import Makie

Makie.surface!(
  rng, rng, exp.(mata),
  # colormap = :Spectral
)

Makie.contour(
  rng, rng, exp.(mata),
  colormap = :Spectral
)


text:
struct QuerySynthesisGMMOracle <: Oracle
    gmm::GMM
    threshold::Float64
end

function QuerySynthesisGMMOracle(data::Array{T, 2}, labels::Vector{Symbol}, params::Dict{Symbol, Any}=Dict{Symbol, Any}()) where T <: Real
    haskey(params, :file) || throw(ArgumentError("Parameter `:file` missing for loading QuerySynthesisGMMOracle from."))
    f = open(params[:file])
    oracle = deserialize(f)
    close(f)
    isa(oracle, QuerySynthesisGMMOracle) || throw(ErrorException("Unexpected type $(typeof(oracle)) (expected: QuerySynthesisGMMOracle)."))
    return oracle
end

function ask_oracle(oracle::QuerySynthesisGMMOracle, query_objects::Array{T, 2})::Vector{Symbol} where T <: Real
    return ifelse.(Distributions.pdf(Distributions.MixtureModel(oracle.gmm), query_objects) .< oracle.threshold, :outlier, :inlier)
end


text:
"""
Return derived fields of `P_conv`
* for `freq`, do zero padding, and then rFFT to return
"""
function Base.getindex(pa::P_conv, s::Symbol)
	@assert s in [:sfreq, :dfreq, :gfreq, :S,:G,:D]

	if(s==:sfreq)
		initialize_s!(pa)
		mul!(pa.sfreq, pa.sfftp, pa.spad)
		return pa.sfreq
	elseif(s==:gfreq)
		initialize_g!(pa)
		mul!(pa.gfreq, pa.gfftp, pa.gpad)
		return pa.gfreq
	elseif(s==:dfreq)
		initialize_d!(pa)
		mul!(pa.dfreq, pa.dfftp, pa.dpad)
		return pa.dfreq
	elseif(s==:S)
		return operator(pa, S())
	elseif(s==:G)
		return operator(pa, G())
	elseif(s==:D)
		return operator(pa, D())
	end
end

function S(s; args...)
	pa=P_conv(s=s; ssize=vcat(size(s)...), args...);
	return pa[:S]
end


text:
## pil.jl (c) 2015 David A. van Leeuwen and others
## This file is licensed under the MIT software license.

## Various algorithms to compute π in many (hexa)decimal digits.

## We count digits after the period, e.g., for ndigits=2, π ≈ 3.14

nbits(ndigits::Int) = ceil(Int, log(2,10) * (ndigits+1))

## Ivar Nesje, diverting problem to mpfr
function mpfr_pi(ndigits::Int)
    with_bigfloat_precision(nbits(ndigits)) do
        big(π)
    end
end

## seems to give identical result
function atan_pi(ndigits::Int)
    with_bigfloat_precision(nbits(ndigits)) do
        4atan(BigFloat(1))
    end
end

## spigot, after Rabinowitz and Wagon.  This computes π one decimal digit at the time.
## Adapted from Hans W Borgers:
function spigot_pi(n)
    p = 0
    Pi = fill(UInt8('0'), n+6)
    no_nines = 0
    d = n + 2
    N = floor(Int, 10*d/3.0 + 1)
    a = fill(2, N+1)
    ci = 1
    for l in 1:d
        for i=1:length(a)
            a[i] *= 10
        end
        for i in (N+1):-1:2
            j = 2*i - 1
            q, a[i] = divrem(a[i], j)
            a[i-1] += q * (i-1)
        end
        q, a[1] = divrem(a[1], 10)
        if q < 9
            Pi[ci] = UInt8('0')+p
            for i = 1:no_nines
                Pi[ci+i] = UInt8('9')
            end
            ci += no_nines+1
            p = q
            no_nines = 0
        elseif q == 9
            no_nines += 1
        elseif q == 10
            p += 1
            Pi[ci] = UInt('0')+p
            for i = 1:no_nines
                Pi[ci+i] = UInt8('0')
            end
            ci += no_nines+1
            p = 0
            no_nines = 0
        else
            error("spigot_pi: algorithm error!")
        end
    end
    Pi[1], Pi[2] = Pi[2], UInt8('.') # remove first 0 and insert decimal point
    ASCIIString(Pi[1:n+2])
end

## from numerical recipes, Borwein & Borwein
function borwein2_pi(ndigits::Int)
    with_bigfloat_precision(nbits(ndigits)) do
        ɛ = BigFloat(10) ^ -ndigits
        x = √ BigFloat(2)
        p = 2 + x
        y = sx = √x
        while true
            lastp = p
            x = 0.5(sx + 1/sx)
            p *= (x+1)/(y+1)
            if abs(p-lastp) < ɛ break end
            sx = √x
            y = (y*sx + 1/sx) / (y+1)
        end
        p
    end
end

## from Wikipedia http://en.wikipedia.org/wiki/Borwein%27s_algorithm
function borwein_1984_pi(ndigits::Integer)
    with_bigfloat_precision(nbits(ndigits)) do
        ɛ = BigFloat(10) ^ -ndigits
        a = √ BigFloat(2)
        b = BigFloat(0)
        p = a + 2
        while true
            lastp = p
            sa = √a
            b = (b+1)sa / (a+b)
            a = 0.5(sa + 1/sa)
            p *= (1+a)b / (1+b)
            if abs(p-lastp) < ɛ break end
        end
        p
    end
end

function chudnovsky2_1989_pi(ndigits::Int)
    with_bigfloat_precision(nbits(ndigits)) do
        ɛ = BigFloat(10) ^ -ndigits
        threek = sixk = k = s = BigFloat(0)
        sign = k!3 = threek! = sixk! = BigFloat(1)
        denfact = BigFloat(640320) ^ 3
        den = √denfact
        while true
            lasts = s
            s += sign * sixk! * (13591409 + 545140134k) / (threek! * k!3 * den)
            if abs(lasts - s) < ɛ break end
            k += 1
            for i=1:3
                threek += 1
                threek! *= threek
            end
            for i=1:6
                sixk += 1
                sixk! *= sixk
            end
            k!3 *= k*k*k
            den *= denfact
            sign = -sign
        end
        1 / 12s
    end
end

## Johan Sigfrids
function gaussLegendre_pi(ndigits::Integer)
    with_bigfloat_precision(nbits(ndigits)) do
        n = ceil(Int, log2(ndigits))
        a = BigFloat(1)
        b = a / √ BigFloat(2)
        t = a / BigFloat(4)
        x = a
        while n > 0
            y = a
            a = (a + b) / 2
            b = √(b * y)
            t -= x * (y - a)^2
            x *= 2
            n -= 1
        end
        (a + b)^2 / (4 * t)
    end
end

## helper function for BBP alorithm
function modpow(b, n::Integer, c)
    ## wikipedia
    r = 1 % c
    b %= c
    while n > 0
        if isodd(n)
            r = (r*b) % c
        end
        n >>= 1
        b = (b*b) % c
    end
    return r
    ## Bailey, Borwein, Borwein, Plouffe (incorrect?)
    t = nextpow2(n+1) >> 1
    r = 1
    while true
        if n ≥ t
            r = (b*r) % c
            n -= t
        end
        t = t ÷ 2
        if t < 1
            break
        end
        r = (r*r) % c
    end
    return r
    ## Straightforward (slow)
    r = 1
    while n > 0
        r = (r*b) % c
        n -= 1
    end
    r
end

## compute 1 digit according to the Borwein, Borwein, and Plouffe algorithm.
## http://crd-legacy.lbl.gov/~dhbailey/dhbpapers/pi-quest.pdf
function bbp_pi_digit(n::Int)
    if n == 0
        return 3
    else
        n -= 1
    end
    const o = [1, 4, 5, 6]
    const w = [4, -2, -1, -1]
    frac = 0.
    for k=0:n
        for i=1:4
            den = 8k+o[i]
            frac += (w[i] * modpow(16, n-k, den)) / den
        end
    end
    floor(Int, mod(frac, 1) * 16)::Int
end

## The Borwein, Borwein and Plouffe formula of a hex digit of pi.
## This can be run in parallel, and can start at any digit.
## cf. table 3 from the publication: `bbp_pi(14, 10^6)`
function bbp_pi(n::Int, start::Int=0)
    if start==0
        range = 0:n
    else
        range = start + (0:n-1)
    end
    digits = @parallel (vcat) for i in range
        digit = bbp_pi_digit(i)
        if digit < 10
            d = '0'+digit
        else
            d = 'a'+digit-10
        end
        if i==0
            map(UInt8, vcat(d,'.'))
        else
            UInt8(d)
        end
    end
    ASCIIString(vcat(digits))
end

function bbp_pi_float(n::Int)
    digits = @parallel (vcat) for i in 0:n
        digit = bbp_pi_digit(i)
        nibble = BitArray(4)
        for i = 1:4
            nibble[5-i] = isodd(digit)
            digit >>= 1
        end
        nibble
    end
    bigfloat(digits, 2)
end

## This function interprets a bitvector as mantissa for a BigFloat number.
## Admittedy, somewhat clumsy.
function bigfloat(x::BitVector, exp=1)
    ## remove leading falses and reverse
    nb = length(x)
    x = reverse(x)
    while length(x)>1 && !last(x)
        pop!(x)
    end
    if length(x)==1
        return with_bigfloat_precision(()->big(0.), nb)
    end
    ## shift bits until a leading true is found
    nb = length(x)
    firstbit = reinterpret(Uint, typemin(Int)) ## 0x8000000000000000
    while last(x.chunks) & firstbit == 0
        insert!(x, 1, false)
    end
    with_bigfloat_precision(nb) do
        f = big(1.)
        f.exp = exp
        for i=1:length(x.chunks)
            unsafe_store!(f.d, x.chunks[i], i)
        end
        return f
    end
end

# Helper to check bbp algorithm, converts float to hexadecimal string.
function base16(x, n::Int)
    digits = Uint8[]
    nbefore = max(0,ifloor(log(16,x)))+1
    for i=1:nbefore
        x *= 16
    end
    for i = -nbefore:n
        if i==0
            push!(digits, '.')
            continue
        end
        d, r = divrem(x, 16)
        if d<10
            push!(digits, '0'+d)
        else
            push!(digits, 'a'+d-10)
        end
        x = 16r
    end
    ASCIIString(digits)
end