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

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

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

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

Поиск неиспользуемых переменных

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

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

Ниже приведен пример кода небольшого размера с одной опечаткой.

function foo(variable_name::Int) sum = 0 for i=1:variable_name sum += variable_name end variable_nme = sum return variable_name end

Этот вид ошибки может вызвать проблемы в коде, которые можно обнаружить только тогда, когда код будет запущен. Давайте предположим, что вы неправильно написали имя каждой переменной только один раз. Мы можем разделить переменные на те, что используются для записи значений, и те, что используются для чтения значений. Если неправильно написана переменная, используемая для записи (например, worng = 5), то ошибки не будет выдана; вы просто поместите значение не в ту переменную — и ошибку будет искать неприятно. Если неправильно написана переменная, используемая при чтении (например, right = worng + 2), то, когда код выполняется, вы получите сообщение об ошибке времени выполнения; вам, вероятно, хотелось бы получить для этого случая статическое предупреждение с тем, чтобы найти эту ошибку раньше, но вам все равно для того, чтобы увидеть проблему, придется ждать, пока вы не запустите код.

По мере того, как код будет удлиняться и усложняться, обнаружить ошибку становится все труднее — до тех пор, пока вы не воспользуетесь статическим анализом.

Левая и правая стороны выражения

Еще один способ выяснить, "читается" и "записывается" переменная, называется способом выяснить, используется ли переменная "в правой части" ("right-hand side" - RHS) или "в левой части" ("left-hand side" - LHS) выражения. Он указывает, где находится переменная по отношению к знаку равенства "="

Ниже показаны несколько случаев использования переменной х:

• Левая сторона:
  • x = 2
  • x = y + 22
  • x = x + y + 2
  • x += 2 (без синтаксического сахара преобразуется в x = x + 2)

• Правая сторона:
  • y = x + 22
  • x = x + y + 2
  • x += 2 (без синтаксического сахара преобразуется в x = x + 2)

• 2 * x
• x

Обратите внимание, что такие выражения, как x = x + y + 2 и x += 2, появляются в обоих случаях, так как переменная х есть по обе стороны знака =.

Поиск переменных, используемых один раз

Необходимо найти две ситуации:

1. Переменные, используемые один раз.
2. Переменные, используемые только в левой или только в правой части выражения.

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

Поиск в левой части выражения

Чтобы переменная находилась в левой части выражения, она должна быть слева от знака =. Это означает, что для того, чтобы найти соответствующую переменную, мы можем в дереве AST искать знак = , а продолжать поиск в левой ветви от него.

В дереве AST знак = является выражением Expr с головной частью head :(=). (Скобки здесь используются для того, чтобы было ясно, что это символ =, а не другой оператор :=). Первое значение в args будет именем переменной, которая находится в левой части. Поскольку мы выполняем поиск в дереве AST, компилятор уже убрал все ненужного и слева от символа = (почти) всегда будет только один символ.

Давайте посмотрим, что это означает в коде:

julia> :(x = 5) :(x = 5) julia> :(x = 5).head :(=) julia> :(x = 5).args 2-element Array{Any,1}: :x 5 julia> :(x = 5).args[1] :x

Ниже приведена полная реализация, за которой следует пояснение.

# Возвращает список всех переменных, используемых слева от символа присваивания (=) # # Аргументы: # e: выражение Expr представляет собой метод Method # # Возвращаемые значения: # набор символов Set{Symbol}, в котором каждый элемент является переменной из левой части выражения e. # function find_lhs_variables(e::Expr) output = Set{Symbol}() for ex in body(e) if Base.is_expr(ex,:(=)) push!(output,ex.args[1]) end end return output end output = Set{Symbol}()

У нас есть набор символов; в нем находятся имена переменных, находящиеся в левой части выражения.

for ex in body(e)
    if Base.is_expr(ex,:(=))
      push!(output,ex.args[1])
    end
  end

Мы не будем в выражениях копать глубже, поскольку дерево AST для кода code_typed довольно примитивное; циклы и операции if преобразованы в примитивные инструкции с операторами goto, управляющими потоком выполнения. Внутри аргументов, с которыми вызывается функция, нет никаких присваиваний. Этот код не сработает в случае, если слева от знака равенства будет что-нибудь больше, чем символ. Здесь пропущены два конкретных случая: доступ к массиву (например, a[5], что будет представлено в виде некоторого выражения :ref) и к свойствам (например, a.head, что будет представлено в виде некоторого выражения :.). В этих случаях в args по-прежнему в качестве первого значения всегда есть соответствующий символ, получить который будет немного сложнее (например, в случае a.property.name.head.other_property). Этот код не обрабатывает такие случаи, но эту ситуацию можно исправить с помощью пары строк кода внутри инструкции if.

push!(output,ex.args[1])

Когда мы находим переменную в правой части, мы для имени переменной выполняем операцию push! для набора Set. И надо будет проверить, что в наборе Set у нас есть только один экземпляр каждого имени.

Поиск в правой части выражения

Чтобы найти все другие случаи использования переменных, нам также нужно просмотреть каждое выражение Expr. Это немного посложнее, поскольку нам нужно будет проверить почти все выражения Expr, а не только выражения :(=), а также потому, что мы должны проанализировать вложенные выражения Expr (для обработки вложенных вызовов функций).

Ниже приведена полная реализация с последующим пояснением.

# Дано выражение, ищем используемые в нем переменные (справа от символа присваивания) # # Аргументы: e: выражение # # Возвращаемые значения: # набор символов Set{Symbol}, в котором каждый элемент является переменной из правой части выражения e. # function find_rhs_variables(e::Expr) output = Set{Symbol}() if e.head == :lambda for ex in body(e) union!(output,find_rhs_variables(ex)) end elseif e.head == :(=) for ex in e.args[2:end] # skip lhs union!(output,find_rhs_variables(ex)) end elseif e.head == :return output = find_rhs_variables(e.args[1]) elseif e.head == :call start = 2 # skip function name e.args[1] == TopNode(:box) && (start = 3) # skip type name for ex in e.args[start:end] union!(output,find_rhs_variables(ex)) end elseif e.head == :if for ex in e.args # want to check condition, too union!(output,find_rhs_variables(ex)) end elseif e.head == :(::) output = find_rhs_variables(e.args[1]) end return output end

Основная часть структуры этой функции представляет собой огромную инструкцию if-else, в которой в каждой ветви обрабатывается свой заголовочный символ head.

output = Set{Symbol}()

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

if e.head == :lambda for ex in body(e) union!(output,find_rhs_variables(ex)) end

Это первое условие в инструкции if-else. :lambda представляет собой тело функции. Мы рекурсивно следуем по телу определения, что нужно для получения всех переменных, используемых в правой части в определении.

elseif e.head == :(=)
    for ex in e.args[2:end]  # skip lhs
      union!(output,find_rhs_variables(ex))
    end

Если заголовочным символом является символ :(=), то выражение является инструкцией присваивания. Мы пропускаем первый элемент в аргументах args, т. к. это переменная, которой выполняется присваивание. Для каждого из оставшихся выражений, мы рекурсивно ищем переменные, используемые в правой части выражения, и добавляем их в наше множество.

 elseif e.head == :return
    output = find_rhs_variables(e.args[1])

Если это оператор возврата return, то первый элемент аргументов args является выражением, значение которого возвращается; здесь мы можем добавить в наше множество любые переменные.

elseif e.head == :call
    # skip function name
    for ex in e.args[2:end]
      union!(output,find_rhs_variables(ex))
    end

Для вызовов функций нам нужно получить все переменные, используемые во всех аргументах вызова функции. Мы пропустить имя функции, которое является первым элементом аргументов args.

elseif e.head == :if
   for ex in e.args # want to check condition, too
     union!(output,find_rhs_variables(ex))
   end

Выражение Expr, представляющее собой инструкцию if, имеет значение head, равное :if. Мы хотим узнать, какие переменные используются во всех выражениях в теле инструкций if, поэтому мы рекурсивно обрабатываем каждому элемент аргументов args.

elseif e.head == :(::)
    output = find_rhs_variables(e.args[1])
  end

Оператор :(::) используется для добавления аннотаций типов. Первым аргументом является выражение или переменная, для которых указана аннотация; мы проверяем использование переменных с помощью аннотированного выражения.

 return output

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

Можно еще чуть-чуть улучшить код метода, приведенного выше. Поскольку версия, приведенная выше, обрабатывает только выражения Expr, но некоторые из значений, которые мы получаем рекурсивно, могут не быть выражениями, нам соответственно нужно еще несколько методов для обработки других возможных типов.

# Рекурсивные базовые случаи, упрощающие порядка обработки версии выражения find_rhs_variables(a) = Set{Symbol}() # unhandled, should be immediate val e.g. Int find_rhs_variables(s::Symbol) = Set{Symbol}([s]) find_rhs_variables(s::SymbolNode) = Set{Symbol}([s.name])

Собираем все вмест

Теперь, когда у нас есть две функции, представленные выше, мы можем ими воспользоваться для того, чтобы найти переменные, которые используются только для чтения или только для записи значений. Функция, которая находит их, будет называться unused_locals (неиспользуемые локальные переменные).

function unused_locals(e::Expr)
  lhs = find_lhs_variables(e)
  rhs = find_rhs_variables(e)
  setdiff(lhs,rhs)
end

Функция unused_locals вернет набор имен переменных. Легко написать функцию, которая по результатам, выданным функции unused_locals, определяет, «прошла» ли проверка или нет. Если множество пусто, то проверка прошла. Если проверка всех методов проходит, то проверка с помощью функции прошла. Функция check_locals, приведенная ниже, реализует эту логику.

check_locals(f::Callable) = all([check_locals(e) for e in code_typed(f)]) check_locals(e::Expr) = isempty(unused_locals(e))

Заключение

Мы показали два способа статического анализа кода на языке Julia: один основан на использовании типов и один - на анализе использования переменных.

В статически типизированных языках уже используется некоторый вариант нашего анализа на основе сравнения типов данных; дополнительный анализана основе сравнения типов данных используется, в основном, в динамически типизированных языках. Есть (в основном исследовательские) проекты по созданию статических систем выводов на основе типов данных для таких языков, как Python, Ruby и Lisp. Эти системы, как правило, строится вокруг дополнительных аннотаций типов; вы можете использовать статические типы, если они вам нужны, и можете вернуться к динамической типизации в случае, когда это вам не нужно. Это особенно полезно при добавлении некоторой статической типизации в уже существующий код.

Проверки, в которых не используются типы, такие как наш случай проверки использования переменных, можно применять как в динамических, так и в статически типизированных языках. Однако во многих статически типизированных языках, таких как C++ и Java, требуется объявлять переменные, а это уже основа для проверок, похожих на те, которые мы создали. Можно еще написать некоторые специальные варианты проверок; например, проверять соответствие стилю программирования, принятому в вашем проекте, или выполнение дополнительные мер, основанных на политиках безопасности.

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

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

Дополнение

Перевод данной главы сделан по тексту преварительной публикации. 12 июля 2016 был выпущен и опубликован на сайте AOSA окончательный вариант сборника "500 строк или меньше", четвертой книги из серии книг "Архитектура приложений с открытым исходным кодом". Окончательный вариант данной главы можно найти по следующей ссылке.

Вернуться к началу статьи.

---

---