Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

AST Search [feature] #283

Open
LilithHafner opened this issue May 15, 2023 · 3 comments
Open

AST Search [feature] #283

LilithHafner opened this issue May 15, 2023 · 3 comments

Comments

@LilithHafner
Copy link
Member

I would like to be able to ask questions like "find all occurrences in General and Base of a string literal immediately preceding a function declaration in a block environment not at the top level without @doc preceding the string literal" (c.f. JuliaLang/julia#14962).

This feature probably belongs in a downstream repo, but I'm opening it here because that downstream repo does not exist afaict.

@c42f
Copy link
Member

c42f commented May 15, 2023

Yes! I'd like this too and I even started writing some code for it a month ago. I'd be happy to have it here in the tools directory until we figure out what to do with it. Let me dig up my incomplete code and see what state it's in :-)

@c42f
Copy link
Member

c42f commented May 19, 2023

Here's some very basic matching code. It really doesn't do much yet, but might give you the flavor of what I was thinking.

Patterns are specified as Julia source code with interpolations $x as matching any syntax, $(xs...) matching the tail of a children list, and $(x; pred(x)) matching any syntax for which pred returns true.

We'll need some regex-like wildcard syntax for specifying multiple matches within a block but I haven't implemented that in this version. I guess that's a bunch of work so I thought I'd just post what I have so far.

using JuliaSyntax
using JuliaSyntax: SyntaxNode, @K_str, children, child, haschildren, kind, head, sourcetext, highlight
using ReplMaker

function single_match(matches, ex, pat)
    matched = false
    if kind(pat[1]) == K"Identifier"
        name = pat[1].val
        matched = true
    elseif kind(pat[1]) == K"block"
        @assert length(children(pat[1])) == 2
        name = pat[1][1].val
        pred = Expr(pat[1][2])
        # lol `eval`. we need pattern compilation
        matched = eval(:(let $name = $ex
                              $pred
                          end))
    end
    if matched
        push!(matches, name=>ex)
    end
    return matched
end

function match_syntax(matches, ex, pat)
    if kind(pat) == K"$"
        return single_match(matches, ex, pat)
    elseif head(ex) == head(pat)
        if !haschildren(ex) && !haschildren(pat)
            # Is this right?
            return ex.val == pat.val
        end
        ex_cs  = children(ex)
        pat_cs = children(pat)
        i = 1
        j = 1
        while i <= length(ex_cs) && j <= length(pat_cs)
            pc = pat_cs[j]
            ec = ex_cs[i]
            if kind(pc) == K"$"
                if kind(pc[1]) == K"..."
                    # TODO: Slurp will need some tricky handling for patterns like, eg,
                    # f(x, $(as...), z, $(bs...))
                    push!(matches, pc[1][1].val=>ex_cs[i:end])
                    i = length(ex_cs)
                else
                    if !single_match(matches, ec, pc)
                        return false
                    end
                end
            else
                if !match_syntax(matches, ec, pc)
                    return false
                end
            end
            i += 1
            j += 1
        end
        return j == length(pat_cs) + 1
    else
        return false
    end
end

function _find_syntax(match_set, ex, pat)
    matches = []
    if match_syntax(matches, ex, pat)
        push!(match_set, (node=ex, bindings=matches))
    else
        for c in children(ex)
            _find_syntax(match_set, c, pat)
        end
    end
end

function find_syntax(pat::SyntaxNode, ex::SyntaxNode)
    match_set = []
    _find_syntax(match_set, ex, pat)
    return match_set
end

function find_syntax(pat::AbstractString, ex::AbstractString)
    find_syntax(JuliaSyntax.parsestmt(SyntaxNode, pat),
                JuliaSyntax.parseall(SyntaxNode, ex))
end

function find_and_highlight_matches(pat, ex)
    matches = find_syntax(pat, ex)
    for (node, bindings) in matches
        code = sprint(context=:color=>true) do io
            JuliaSyntax.highlight(io, node.source, range(node), context_lines_inner=5)
        end
        @info "Match" bindings Text(code)
    end
end

# find_syntax(raw"$x + $y",
#     """
#     function foo()
#         a + b * c
#         for i = 1:10
#             println(i)
#             println(i + 3)
#         end
#     end
#     """)

@info "# Simple matching"
find_and_highlight_matches(raw"a => $y",
    """
    function foo()
        a=>b
    end

    function bar()
        c=>d
        a=>x+1
        e=>f
    end
    """)

@info "# Underscore bindings match but are ignored"
find_and_highlight_matches(raw"$x + $_",
    """
    function foo()
        a + b * c
        for i = 1:10
            println(i)
            println(i + 3)
        end
    end
    """)

@info "# A pattern like `\$(xs...)` matches remaining arguments"
find_and_highlight_matches(raw"foo(a, $(xs...))",
    """
    let a=1
        foo(a, b, c)
        foo(x, b, c)
    end
    """)


@info """# Custom predicate patterns"""
find_and_highlight_matches(raw"""$(x; kind(x) == K"string")""",
    """
    let a=1
        foo(a, b, "c")
        foo(x, b, c)
        "some string"
    end
    """)

@c42f
Copy link
Member

c42f commented Jun 28, 2023

So it turns out that Julia already has a tree-matching pattern language - in flisp though, written by Jeff in 2009!

Might be nice to steal those old ideas 😆

https://github.com/JuliaLang/julia/blob/e6d67a77000870249eb9434fd431da226c8d7276/src/match.scm#L1-L34

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants