Implement `Base.replace` and `Base.replace!`

[goerz]

Continuing from the discussion on Discourse and in the context of implementing JuliaDocs/DocumenterCitations.jl#6, it would be extremely useful to implement the Base functions replace and replace! on AST trees.

I would propose the following implementation:

using Pkg
Pkg.activate(temp=true)
Pkg.add("MarkdownAST")

import MarkdownAST


"""
    replace(f::Function, root::Node)

Creates a copy of the tree where all child nodes of `root` are recursively
replaced by the result of `f(child)`.

The function `f(child::Node)` must return either a new `Node` to replace
`child` or a Vector of nodes that will be inserted as siblings, replacing
`child`.

Note that `replace` does not allow the construction of invalid trees, and
element replacements that require invalid parent-child relationships (e.g., a
block element as a child to an element expecting inlines) will throw an error.

# Example

The following snippet removes links from the given AST. That is, it replaces
`Link` nodes with their link text (which may contain nested inline markdown
elements):

```julia
new_mdast = replace(mdast) do node
    if node.element isa MarkdownAST.Link
        return [MarkdownAST.copy_tree(child) for child in node.children]
    else
        return node
    end
end
```
"""
function Base.replace(f::Function, root::MarkdownAST.Node{M}) where M
    new_root = MarkdownAST.Node{M}(root.element, deepcopy(root.meta))
    for child in root.children
        replaced_child = replace(f, child)
        transformed = f(replaced_child)
        if transformed isa MarkdownAST.Node
            push!(new_root.children, transformed)
        elseif transformed isa Vector
            append!(new_root.children, transformed)
        else
            error("Function `f` in `replace(f, root::MarkdownAST.Node)` must return either a Node or a Vector of nodes, not $(repr(typeof(transformed)))")
        end
    end
    return new_root
end


"""
    replace!(f::Function, root::Node)

Acts like `replace(f, root)`, but modifies `root` in-place.
"""
function Base.replace!(f::Function, root::MarkdownAST.Node{M}) where M
    new_root = replace(f, root)
    while !isempty(root.children)
        # `Base.empty!(root.children)` would be nice!
        MarkdownAST.unlink!(first(root.children))
    end
    append!(root.children, new_root.children)
    return root
end

It might be nice to also implement Base.empty(::MarkdownAST.NodeChildren) (see comment): is there a better way to do that than the loop that I implemented?

To test the behavior in the context of my original intent with DocumenterCitations:

## TEST  ######################################################################
#
# As a test, we're resolving simple citation links in a format similar to
# https://juliadocs.org/DocumenterCitations.jl/stable/gallery/#Custom-style:-Citation-key-labels
#
# That test replaces a single Link node with a list of new inline nodes that
# mix text and links to a `references.md` page.
#
# Also, to test the simpler transformation of a node with a single new node, we
# replace Strong (bold) nodes with Emph (italic) nodes – This could also be
# donw with MarkdownAST.copy_tree directly, but it's just a test.

Pkg.add(url="https://github.com/JuliaDocs/Documenter.jl", rev="master")
import Markdown
import Documenter

MD = raw"""
# Quantum Control

**[Quantum optimal control](https://qutip.org/docs/latest/guide/guide-control.html)**
[BrumerShapiro2003;BrifNJP2010;KochJPCM2016;SolaAAMOP2018;MorzhinRMS2019;
Wilhelm2003.10132;KochEPJQT2022](@cite) attempts to steer a quantum system in
some desired way.

## Methods used

We use the following methods:

* *[Krotov's method](https://github.com/JuliaQuantumControl/Krotov.jl)*
  [Krotov1996](@cite), and
* [**GRAPE** (*Gradient Ascent Pulse Engineering*)](https://github.com/JuliaQuantumControl/GRAPE.jl)
  [KhanejaJMR2005;FouquieresJMR2011](@cite).

This concludes the document.
"""

function parse_md_string(mdsrc)
    mdpage = Markdown.parse(mdsrc)
    return convert(MarkdownAST.Node, mdpage)
end

mdast = parse_md_string(MD)
println("====== IN =======")
println("AS AST:")
@show mdast
println("AS TEXT:")
print(string(convert(Markdown.MD, mdast)))
println("=== TRANSFORM ===")
replace!(mdast) do node
    if node.element == MarkdownAST.Link("@cite", "")
        text = first(node.children).element.text  # assume no nested markdown
        keys = [strip(key) for key in split(text, ";")]
        n = length(keys)
        if n == 1
            k = keys[1]
            new_md = "[[$k]](references.md#$k)"
        else
            k1 = keys[1]
            k2 = keys[end]
            if n > 2
                new_md = "[[$k1](references.md#$k1)-[$k2](references.md#$k2)]"
            else
                new_md = "[[$k1](references.md#$k1), [$k2](references.md#$k2)]"
            end
        end
        return Documenter.mdparse(new_md; mode=:span)
        # We probably wouldn't want to use `Documenter`, but it shouldn't be
        # hard to copy in a stripped-down version of `mdparse` here.
    elseif node.element == MarkdownAST.Strong()
        # Not sure if `copy_tree(f, node)` is really the most elegant way to do
        # this, but I wanted to try out how `copy_tree` can modify a node's
        # `element`.
        return MarkdownAST.copy_tree(node) do node, element
            element == MarkdownAST.Strong() ? MarkdownAST.Emph() : element
        end
    else
        return node
    end
end
println("====== OUT =======")
println("AS AST:")
@show mdast
println("AS TEXT:")
print(string(convert(Markdown.MD, mdast)))
println("====== END =======")

Second, to test the simple example from the docstring:

# TEST 2: delete links (example from the docstring)  ##########################
println("\n\n=====================================")
println("TEST2: ORIGINAL MD WITH LINKS REMOVED")
mdast = parse_md_string(MD)
replace!(mdast) do node
    if node.element isa MarkdownAST.Link
        return [MarkdownAST.copy_tree(child) for child in node.children]
    else
        return node
    end
end
print(string(convert(Markdown.MD, mdast)))
println("====== END =======")

@mortenpi Would you like me to start working a PR for this with proper testing and documentation?

Any comments on the prototype?

[goerz]

Here's a gist for the full prototype: https://gist.github.com/goerz/3b1eb0fdd161abb84f592149d0ec7659

It should be fully runnable directly as julia prototype.jl without any dependencies.