Add direct tree manipulations

[Whebon]

Tree manipulations are done using the path of a hole. For example:

"""
    remove_below!(solver::GenericSolver, path::Vector{Int}, rule_index::Int)

Reduce the domain of the hole located at the `path` by removing all rules indices below `rule_index`
Example:
`rule_index` = 2. 
`hole` with domain [1, 1, 0, 1] gets reduced to [0, 1, 0, 1]
"""
function remove_below!(solver::GenericSolver, path::Vector{Int}, rule_index::Int)
    hole = get_hole_at_location(solver, path)
    lowest_ind = findfirst(hole.domain)
    if lowest_ind >= rule_index
        # e.g. domain: [0, 1, 0, 1, 1, 0] rule_index: 2
        # The tree manipulation won't have any effect, ignore the tree manipulation
        return
    end
    for r ∈ 1:rule_index-1
        hole.domain[r] = false
    end
    simplify_hole!(solver, path)
    notify_tree_manipulation(solver, path)
    fix_point!(solver)
end

The first line of a tree manipulation is often hole = get_hole_at_location(solver, path).
This takes takes O(n) and is not needed if the actual hole is known by the caller.

For example, in make_less_than_or_equal!, the hole is known, but the path is not. The signature of the tree manipulation requires the path, so the path is retrieved by a dfs (get_node_path). Then in remove_below!, the path is immediately converted back to the hole. (get_hole_at_location).

function make_less_than_or_equal!(
    solver::Solver,
    node::RuleNode,
    hole::Hole
)
    path = get_node_path(get_tree(solver), hole) #TODO: optimize. very inefficient to go from hole->path->hole
    remove_below!(solver, path, get_rule(node))
    if !isfeasible(solver)
        return LessThanOrEqualHardFail()
    end
    #the hole might be replaced with a node, so we need to get whatever is at that location now
    @match get_node_at_location(solver, path) begin
        filledhole::RuleNode => return make_less_than_or_equal!(solver, node, filledhole)
        hole::Hole => return LessThanOrEqualSoftFail(hole)
    end
end

Why is this unsafe?

Consider the a fixed shaped hole (red) located at path=[2]. Then consider two consecutive remove! calls that remove values 5 and 6 respectively. In the first remove! function, the variable shaped hole (red) will be simplified to a fixed shaped hole (orange).

Scenario 1: path-based tree manipulations (safe)
remove! traverses the path and finds the hole at that location. This results in the intended behavior.

Scenario 2: direct tree manipulations (unsafe)
remove! is called with a reference to an actual hole instance. For the first manipulation this works fine. The variable shaped hole instance (red) is replaced with another fixed shaped hole instance (orange).
The second remove! call will not affect the tree, since the referenced hole is no longer inside the tree. This is unwanted behavior.
remove! traverses the path and finds the hole at that location. This results in the intended behavior.

Target implementation

Add an optional argument to the tree manipulation that takes a hole directly. The caller should ensure that the hole is actually inside the tree.

function remove_below!(solver::GenericSolver, path::Vector{Int}, rule_index::Int; hole=nothing)
    if isnothing(hole)
        hole = get_hole_at_location(solver, path)
    end
    #....
end

Why is this not here yet

The solver can change states. This means that directly referenced hole may not be part of the current state. Calling tree manipulations with a directly reference hole should be used very carefully.
Either:

• The caller should make sure the hole is inside the current state.
• The solver should verify if the hole is inside the current state by traversing the tree. (bad solution, as this requires a traversal which we were trying to avoid)