Статический анализ (продолжение)

Оригинал: Static Analysis
Автор: Leah Hanson
Дата публикации: 22 сентября 2015
Перевод: Н.Ромоданов
Дата перевода: июль 2016 г.

Это продолжение статьи. Начало смотрите здесь

Интроспекция в языке Julia

Обнаруживаем и выделяем циклы

Мы собираемся найти циклы при помощи поиска выражений goto с переходами в обратном направлении.

Нам нужно найти метки и переходы, и выяснить, какие из них соответствуют друг другу. Я сначала хочу вам предоставить полную реализацию алгоритма поиска. После просмотра всего кода целиком, мы разделим его на части и изучим более мелкие куски.

# Эта функция пытается обнаружить циклы в теле метода # Возвращаются строки, которые находятся в одном или нескольких циклах function loopcontents(e::Expr) b = body(e) loops = Int[] nesting = 0 lines = {} for i in 1:length(b) if typeof(b[i]) == LabelNode l = b[i].label jumpback = findnext(x-> (typeof(x) == GotoNode && x.label == l) || (Base.is_expr(x,:gotoifnot) && x.args[end] == l), b, i) if jumpback != 0 push!(loops,jumpback) nesting += 1 end end if nesting > 0 push!(lines,(i,b[i])) end if typeof(b[i]) == GotoNode && in(i,loops) splice!(loops,findfirst(loops,i)) nesting -= 1 end end lines end

А теперь для того, чтобы объяснить по частям:

b = body(e)

Начнем с получения всех выражений в теле метода, т.к. Array.body является функцией, которую я уже реализовала:

# Возвращает тело метода. # Берет Expr, представляющее метод, # возвращает Vector{Expr}. function body(e::Expr) return e.args[3].args end

А затем:

  loops = Int[]
  nesting = 0
  lines = {}

Циклы loops являются массивом Array номеров строк меток, с помощью которых и с помощью goto создаются циклы. nesting указывает на количество циклов, в которых мы на данный момент находимся (т.е. вложенность циклов – прим.пер.). lines является массивом Array из кортежей (индекс, Expr).

for i in 1:length(b) if typeof(b[i]) == LabelNode l = b[i].label jumpback = findnext( x-> (typeof(x) == GotoNode && x.label == l) || (Base.is_expr(x,:gotoifnot) && x.args[end] == l), b, i) if jumpback != 0 push!(loops,jumpback) nesting += 1 end end

Мы взглянем на каждое выражение в теле выражения e. Если это метка, мы проверяем, есть ли переход goto на эту метку (и переход находится после метки). Если результат findnext больше нуля, то такой узел goto существует, поэтому мы добавим его в loops (массив Array циклов, внутри которых мы сейчас находимся) и увеличим наш уровень вложенности nesting.

    if nesting > 0
      push!(lines,(i,b[i]))
    end

Если мы в текущий момент находимся внутри цикла, мы помещаем текущую строку в массив строк, которые должны быть возвращены.

if typeof(b[i]) == GotoNode && in(i,loops) splice!(loops,findfirst(loops,i)) nesting -= 1 end end lines end

Если мы находимся в узле GotoNode, то мы проверяем, находимся мы в конце цикла. Если это так, мы удаляем запись из loops и сокращаем уровень вложенности.

Результат работы этой функции будет находиться массиве lines, т.е. массиве кортежей (индекс, значение). Это означает, что каждый элемент в массиве имеет индекс, указывающий на тело выражения Expr, и значение для этого индекса. Каждый элемент в lines является выражением, которое находится внутри цикла.

Поиск и типизация переменных

Мы только что завершили рассмотрение функции loopcontents, которая возвращает выражения Expr, находящиеся внутри циклов. Нашей следующей функцией будет функция loosetypes, которая берет список выражений Expr и возвращает список слабо типизированных переменных. Позже, мы передадим результат работы функции выход loopcontents в функцию loosetypes.

В каждом выражении, которое находится внутри цикла, loosetypes ищет вхождение символов и ассоциированные с ними типы. Использование переменных показывается как узлы SymbolNode в дереве АСТ; в узлах SymbolNode хранится имя переменной и выведенный тип переменной.

Мы не можем просто проверить каждое выражение, которое было найдено с помощью loopcontents, с тем, чтобы является ли оно узлом SymbolNode. Проблема в том, что каждое выражение Expr может содержать одно или большее количество выражений Expr; каждое выражение Expr может содержать один или большее количество узлов SymbolNodes. Это означает, что мы должны вытащить все вложенные выражения Expr с тем, что увидеть внутри них каждый из узлов SymbolNode.

# given `lr`, a Vector of expressions (Expr + literals, etc) # try to find all occurrences of a variables in `lr` # and determine their types function loosetypes(lr::Vector) symbols = SymbolNode[] for (i,e) in lr if typeof(e) == Expr es = copy(e.args) while !isempty(es) e1 = pop!(es) if typeof(e1) == Expr append!(es,e1.args) elseif typeof(e1) == SymbolNode push!(symbols,e1) end end end end loose_types = SymbolNode[] for symnode in symbols if !isleaftype(symnode.typ) && typeof(symnode.typ) == UnionType push!(loose_types, symnode) end end return loose_types end symbols = SymbolNode[] for (i,e) in lr if typeof(e) == Expr es = copy(e.args) while !isempty(es) e1 = pop!(es) if typeof(e1) == Expr append!(es,e1.args) elseif typeof(e1) == SymbolNode push!(symbols,e1) end end end end

Цикл while рекурсивно проходит через содержимое всех выражений Expr до тех пор, пока он не просмотрит все выражения Expr (и, надеюсь, все узлы SymbolNode). Каждый раз, когда цикл находит SymbolNode, он добавляет его в вектор symbols.

loose_types = SymbolNode[] for symnode in symbols if !isleaftype(symnode.typ) && typeof(symnode.typ) == UnionType push!(loose_types, symnode) end end return loose_types end

Теперь у нас есть список переменных и их типов, так что теперь легко проверить, возникает ли торможение из-за типов. Все, что делает loosetypes, это ищет неконкретный тип UnionType. Мы получаем гораздо больше "неправильных" результатов, когда мы рассматриваем все неконкретные типы, среди которых есть "неправильные". Это связано с тем, что мы выполняем оценку каждого метода с его аннотированными типами аргументов, которые могут быть абстрактными.

Используем

Теперь, когда мы можем выполнить проверку выражения, мы должны упростить обращение к коду пользователя. Мы создадим два способа вызова checklooptypes:

1. Для всей функции; будет проверятся каждый метод данной функции.
2. Для конкретного выражения; будет работать в случае, если пользователь получит результаты из code_typed.

## Для заданной функции запускаем checklooptypes на каждом методе function checklooptypes(f::Callable;kwargs...) lrs = LoopResult[] for e in code_typed(f) lr = checklooptypes(e) if length(lr.lines) > 0 push!(lrs,lr) end end LoopResults(f.env.name,lrs) end # Для выражения Expr, представляющего собой метод, # проверяем, что тип каждой переменной, используемой в цикле, # имеет конкретный тип checklooptypes(e::Expr;kwargs...) = LoopResult(MethodSignature(e),loosetypes(loopcontents(e)))

Мы видим, что для функции с одним методом оба варианта работают примерно одинаково:

julia> using TypeCheck julia> function foo(x::Int) s = 0 for i = 1:x s += i/2 end return s end foo (generic function with 1 method) julia> checklooptypes(foo) foo(Int64)::Union(Int64,Float64) s::Union(Int64,Float64) s::Union(Int64,Float64) julia> checklooptypes(code_typed(foo,(Int,))[1]) (Int64)::Union(Int64,Float64) s::Union(Int64,Float64) s::Union(Int64,Float64)

Красивая печать

Здесь я опустила детали реализации: как мы получаем в REPL результаты, чтобы они выглядели так, как показано выше?

Во-первых, я сделала несколько новых типов. Тип LoopResults является результатом проверки всей функции; здесь есть имя функции и результаты для каждого метода. Тип LoopResult является результатом проверки одного метода; в нем есть типы аргументов и слабо типизированные переменные.

Функция checklooptypes возвращает тип LoopResults. В этом типе есть функция, которая называется show. REPL вызывает функцию display для значения, которое необходимо отобразить; затем функция display вызовет нашу реализацию show.

Этот код имеет важное значение для того, чтобы можно было использовать статический, но он не выполняет статический анализ. Вы должны пользоваться тем методом выдачи красивой печати типов, которые будет более предпочтительным в вашем языке реализации; это выполняется точно также, как это делается в языке Julia.

type LoopResult msig::MethodSignature lines::Vector{SymbolNode} LoopResult(ms::MethodSignature,ls::Vector{SymbolNode}) = new(ms,unique(ls)) end function Base.show(io::IO, x::LoopResult) display(/x.msig) for snode in x.lines println(io,"\t",string(snode.name),"::",string(snode.typ)) end end type LoopResults name::Symbol methods::Vector{LoopResult} end function Base.show(io::IO, x::LoopResults) for lr in x.methods print(io,string(x.name)) display(lr) end end

Продолжение статьи смотрите здесь

---

---