Как построить граф потока управления программы

Содержание

графическое представление компьютерной программы или алгоритма Некоторые примеры CFG:. (a) если-то -else. (b) цикл while. (c) естественный цикл с двумя выходами, например в то время как с if. разрывом посередине; неструктурированный, но сводимый. (d) неприводимый CFG: цикл с двумя точками входа, например перейти в цикл while или for

В информатике граф потока управления (CFG ) является представлением, используя нотацию graph, всех путей, которые могут быть пройдены программой во время ее выполнения. График потока управления создан Фрэнсис Э. Аллен, которая отмечает, что Риз Т. Проссер раньше использовал логические матрицы связности для анализа потока.

Определение

В графе потока управления каждый узел в график представляет собой базовый блок, т.е. прямолинейный фрагмент кода без каких-либо переходов или целей перехода ; Цели прыжка начинают блок, а прыжки заканчивают блок. Направленные ребра используются для представления переходов в потоке управления . В большинстве презентаций есть два специально обозначенных блока: входной блок, через который управление входит в потоковый граф, и выходной блок, через который уходит весь управляющий поток.

20160131A Эквивалентное представление программ для анализа потока данных в потоке управления

Из-за процедуры его построения в a CFG, каждое ребро A → B имеет свойство:

outdegree (A)>1 или indegree (B)>1 (или оба).

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

Пример

Рассмотрим следующий фрагмент кода:

0: (A) t0 = read_num 1: (A) если t0 mod 2 == 0 2: (B) print t0 + «четное». 3: (B) goto 5 4: (C) выведите t0 + «нечетно». 5: (D) конечная программа

В приведенном выше примере у нас есть 4 основных блока: A от 0 до 1, B от 2 до 3, C на 4 и D на 5. В частности, в этом случае, A — «блок входа», D — «блок выхода», а строки 4 и 5 — цели перехода. Граф для этого фрагмента имеет ребра от A до B, от A до C, от B до D и от C до D.

Reachability

Reachability — это свойство графа, полезное при оптимизации.

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

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

Инструмент для получения и анализа графа потока управления открытых исходных текстов С/С++ …

Недостижимый код и бесконечные циклы возможны, даже если программист не кодирует их явно: такие оптимизации, как распространение констант и сворачивание констант с последующим переходом потоков может сворачивать несколько базовых блоков в один, вызывать удаление ребер из CFG и т. Д., Таким образом, возможно, разъединение частей графа.

Отношение доминирования

Блок M доминирует над блоком N, если каждый путь от записи, которая достигает блока N, должен проходить через блок M. Входной блок доминирует над всеми блоками.

В обратном направлении блок M постдоминирует блок N, если каждый путь от N до выхода должен проходить через блок M. Выходной блок постдоминирует все блоки.

Говорят, что блок M немедленно доминирует над блоком N, если M доминирует над N, и нет промежуточного блока P, такого, что M доминирует над P, а P доминирует над N. Другими словами, M является последним доминирующим элементом на всех пути от входа к N. Каждый блок имеет уникального непосредственного доминанта.

Точно так же есть понятие непосредственного постдоминатора, аналогично непосредственному господину.

дерево доминаторов — это вспомогательная структура данных, отображающая отношения доминаторов. Существует дуга от блока M до блока N, если M является непосредственным доминатором N. Этот граф является деревом, поскольку каждый блок имеет уникальный непосредственный доминатор. Это дерево базируется на входном блоке. Дерево доминаторов может быть эффективно вычислено с использованием алгоритма Ленгауэра – Тарьяна.

Дерево постдоминаторов аналогично дереву доминаторов. Это дерево укоренено в блоке выхода.

Специальные ребра

Заднее ребро — это ребро, которое указывает на блок, который уже встречался во время обхода графа в глубину (DFS ). Задние края типичны для петель.

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

Аномальный край — край, назначение которого неизвестно. Обработка исключений конструкции могут создавать их. Эти края обычно препятствуют оптимизации.

Невозможное ребро (также известное как поддельное ребро) — это ребро, которое было добавлено к графу исключительно для того, чтобы сохранить свойство, согласно которому выходной блок постдоминирует со всеми блоками. Через него невозможно пройти.

Управление циклом

Предположим, что блок M является доминатором с несколькими входящими ребрами, некоторые из которых являются задними ребрами (так что M — заголовок цикла). Для разделения M на два блока M pre и M loop выгодно выполнить несколько проходов оптимизации. Содержимое M и задних краев перемещается в M loop, остальные края перемещаются в точку M pre, а новый край из M pre в M цикл вставляется (так, чтобы M pre был непосредственным доминирующим элементом цикла M). Вначале M pre был бы пустым, но проходы, подобные движению кода с инвариантным циклом, могли бы его заполнить. M pre называется предварительным заголовком цикла, а M loop будет заголовком цикла.

Сводимость

Приводимая CFG — это группа с ребрами, которые могут быть разделены на два непересекающихся набора: передние края и задние края, так что:

Передние края образуют направленную ациклический граф со всеми узлами, доступными из входного узла.
Для всех задних ребер (A, B) узел B доминирует над узлом A.

Структурированное программирование языки часто проектируются так, что все производимые ими CFG могут быть сокращены, а общие операторы структурированного программирования, такие как IF, FOR, WHILE, BREAK и CONTINUE, создают сокращаемые графы. Для создания неприводимых графиков необходимы такие операторы, как GOTO. Неприводимые графы также могут быть получены с помощью некоторых оптимизаций компилятора.

Связность петель

Связность петель CFG определяется по отношению к заданному дереву поиска в глубину (DFST) CFG. Этот DFST должен быть основан на начальном узле и охватывать каждый узел CFG.

Ребра в CFG, которые идут от узла к одному из его предков DFST (включая его самого), называются задними ребрами.

Связность петель — это наибольшее количество задних ребер, обнаруженных в любом безцикловом пути CFG. В редуцируемом CFG связность петли не зависит от выбранного DFST.

Связность петли использовалась для объяснения временной сложности анализа потока данных.

График межпроцедурного управления

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

См. Также

Абстрактное синтаксическое дерево
Блок-схема
Диаграмма потока управления
Анализ потока управления
Анализ потока данных
Интервал (теория графов)
График зависимости программы
Цикломатическая сложность
Статическое одиночное назначение
Конструкция компилятора
Промежуточное представление

Ссылки

Внешние ссылки

Викискладе есть носители, связанные с График потока управления.

Библиотека графа потока управления Machine-SUIF
Коллекция компиляторов GNU Внутреннее устройство
Статья «Инфраструктура для оптимизации на основе профилей в компиляторе GCC » от Зденек Дворжак и др.

Exa mples

Avrora — Control-Flow Graph Tool

Источник: alphapedia.ru

Задание 2. Анализ потоков данных

В этом задании вам предлагается реализовать следующие виды анализа потоков данных:

Распространение целочисленных констант (домен Integer ).
Распространение констант с выводом примитивных типов (домен Value ).

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

Общая схема алгоритма

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

Примеры использования

1. Распространение целочисленных констант

mulua dataflow-analysis —type=integer-constant-propagation const.lua
b = true m = nil n = input() c = 1 if n > 0 then c = 3 — 2 end
[c → 1, n → Integer, _ → never]

Здесь _ обозначает «все остальное». Обратите внимание, что в выводе опущены связки b → never и m → never .

mulua dataflow-analysis —type=integer-constant-propagation division-by-zero.lua
division-by-zero.lua
n = input() c = 1 — 1 x = n // c
[c → 0, n → Integer, _ → never]

Обратите внимание, что в выводе опущена связка x → never .

2. Распространение констант с выводом примитивных типов

mulua dataflow-analysis —type=typed-constant-propagation alternative.lua
alternative.lua
m = nil x = input() if x >= 0 then n = x > 0 end if x >= 42 then n = 42 end
[n → nil | Boolean | 42, x → Integer, _ → nil]

Обратите внимание, что в выводе опущена связка m → nil .

mulua dataflow-analysis —type=typed-constant-propagation bool-from-int.lua
bool-from-int.lua
a = 2 + 2 b = a > 0
[a → 4, b → true, _ → nil]

Формат выходных данных

Выводится окружение, описывающее абстрактное состояние программы на момент завершения ее выполнения.
Переменные в окружении [x₁ → σ(x₁), …, xₙ → σ(xₙ), _ → default] перечисляются в лексикографическом порядке.
Для анализа распространения целочисленных констант не выводятся связки вида xᵢ → never , поскольку значение nil (которым обладают все переменные по умолчанию) соответствует абстрактному значению never (⊥) в домене Integer .
Для анализа распространения констант с выводом примитивных типов не выводятся связки вида xᵢ → nil , поскольку значение nil соответствует абстрактному значению nil в домене Value .

Библиотеки

В заготовке задания по разработке интерпретатора были описаны следующие библиотеки:

mulua.syntax — абстрактный синтаксис.
mulua.parser — парсер.
mulua.semantics — семантика языка и его интерпретатор.

В процессе решения этого задания у вас должны возникнуть как минимум следующие библиотеки:

mulua.lattice — решетки.
mulua.domain — абстрактные домены.
mulua.flowgraph — построение графа потока управления (control flow graph) по абстрактному синтаксису.
mulua.dataflow — анализатор потоков данных.

Создайте эти библиотеки по аналогии с другими библиотеками. Для этого необходимо создать соответствующие директории в lib/ и написать в каждой конфигурационный файл dune .

Решетки

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

CompleteLattice

Сигнатура полной решетки:

CompleteLattice.re

Constant

Для распространения констант нам потребуется плоская решетка:

Constant.re

open Base; module Make = (Value: Equal.S): < type t = | Any | Some(Value.t) | None; include CompleteLattice.S with type t := t; let of_option: option(Value.t) =>t; /* . */ > => < /* . */ >;

Map

Для представления абстрактного состояния программы нам потребуется функциональная решетка Key → Value , где Key — множество, а Value — полная решетка:

open Base; module Make = (Key: Comparable.S, Value: CompleteLattice.S): < include (module type of TotalMap.Make(Key, Value)); include CompleteLattice.S with type t := t; >=> < include TotalMap.Make(Key, Value); /* . */ >;

Использовать ее для анализа программ мы будем для представления абстрактного состояния (окружения) программы. В качестве множества Key мы будем использовать множество идентификаторов переменных Identifier . Решетка Value будет моделировать абстрактные значения этих переменных.

Домены

Домен (в т.ч. абстрактный) определяется решеткой значений и семантикой операций.

open MuLua_lattice; module type S = < include CompleteLattice.S; let of_value: MuLua_semantics.Value.t =>t; let to_string: t => string; let (+): (t, t) => t; /* . */ >;

Nil

Тип Nil имеет единственное значение — nil .

open MuLua_lattice; include (module type of Constant.Make(Base.Nothing)); include Domain.S with type t := t;

Поскольку тип Base.Nothing.t является ненаселенным, конструктором Some воспользоваться нельзя.

Boolean

Тип Boolean имеет два возможных значения — false и true .

Boolean.rei

open MuLua_lattice; include (module type of Constant.Make(Base.Bool)); include Domain.S with type t := t;

Integer

Тип Integer имеет целочисленные значения в некотором допустимом диапазоне.

Integer.rei

open MuLua_lattice; include (module type of Constant.Make(Base.Int)); include Domain.S with type t := t;

Value

В языке μLua существуют значения только следующих типов времени выполнения: Nil , Boolean и Integer . Все эти типы являются примитивными.

Нас интересует статический анализ, который позволит для каждой переменной узнать, каким примитивным типам может принадлежать ее значение. Более того, если переменная может принадлежать некоторому типу, то в таком случае также интересно, является ли эта переменная константой этого типа.

Произведение доменов, соответствующих примитивным типам, дает нам домен, который используется в решении данной задачи:

type t = < nil: Nil.t, boolean: Boolean.t, integer: Integer.t, >; include Domain.S with type t := t;

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

Реализация модуля Value пишется тривиальным образом.

Примеры строковых представлений абстрактных значений

Данные примеры должны помочь понять, как следует написать функцию Value.to_string .

Источник: khashaev.ru

Контроль диапазонов целых чисел в FindBugs

FindBugs — это статический анализатор кода для Java с открытым исходным кодом (под LGPL). Он содержит множество детекторов, которые определяют те или иные проблемы в коде. С недавних пор я являюсь участником проекта и пишу для него новые детекторы. Об одном из них я и расскажу в этой статье. Также мы посмотрим примеры багов, найденных в реальных проектах.

Устройство FindBugs

FindBugs анализирует не исходники, а байт-код. У этого метода есть некоторые недостатки. Нельзя написать детектор, который основан только на неправильном форматировании кода (например, возможно пропущенное else в else if, как V646 в PVS-Studio). Нельзя детектировать некоторые ситуации, в которых генерируется одинаковый байт-код. Например, хорошо бы детектировать такой странный код (на который выдаёт предупреждение IDEA и та же PVS-Studio):

Задача

Мне захотелось отлавливать логические ошибки вроде таких:

int test(int x) < if( x >10 x > 5 ) < return 1; >return 0; >

Здесь очевидно второе условие бесполезно, потому что если x больше 10, то он хоть как больше 5. Приведённый пример очень простой, хотя и такие ошибки встречаются в реальном коде. В целом задача состоит в том, чтобы найти условия на целые числа, которые для любого возможного значения числа всегда истинны или всегда ложны.

Граф потока управления

В теории компиляции есть такая штука — граф потока управления (control flow graph, CFG). Это похоже на старую добрую блок-схему, построенную по программному коду: вершины графа — это базовые блоки, код в которых выполняется линейно без всяких переходов, а рёбра — возможные направления перехода. Граф потока управления может быть довольно большим даже для простого метода, потому что большинство инструкций может сгенерировать исключение, для которого добавляется ребро. Граф потока управления для каждого метода уже строится в FindBugs, поэтому им можно пользоваться. Вот как бы выглядел такой граф для метода, приведённого выше:

Для нашей задачи сперва надо выбрать все параметры и локальные переменные, которые могут участвовать в анализе. Пока я ограничился только теми, которые никогда не меняются (возможно, в будущем ограничение будет ослаблено). То есть нас интересуют параметры, которые ни разу не присваивают, и переменные, которые присваивают ровно один раз.

Такой список легко составить, просто пробежавшись по инструкциям метода в поисках инструкций записи в локальную переменную. Для каждой переменной мы изначально устанавливаем допустимый диапазон значений. Например, для типа int это будет [Integer.MIN_VALUE..Integer.MAX_VALUE].

Далее мы перебираем те узлы CFG, которые содержат условие. Если это сравнение интересующей нас переменной с константой, то мы разбиваем соответствующий интервал согласно условию. Например, для условия x > 5 мы получим [Integer.MIN_VALUE..5] + [6..Integer.MAX_VALUE], а для x != 0 получим три интервала: [Integer.MIN_VALUE..-1] + + [1..Integer.MAX_VALUE]. Также для каждого такого условия сохраняется интервал, который условию удовлетворяет.

Затем для каждой интересующей нас переменной мы пробегаемся по всем интервалам области определения и для каждого интервала гуляем по графу потока, начиная от входного узла. При этом если мы попадаем в условный узел, связанный с данной переменной, то идём только по одному ребру в зависимости от того, выполняется ли условие на данном интервале, и помечаем, по какому мы прошли. Для всех прочих узлов мы проходим всевозможные исходящие рёбра. Наша маленький метод разбивает область определения x на три интервала, для которых обход графа будет выглядеть так:

Заметьте, что в первых двух случаях получилось одно и то же. В конце остаётся лишь найти рёбра, которых мы ни разу не достигли и сформировать по ним сообщение об ошибке. Если конечная вершина этого ребра также оказалась не достигнута, это означает, что у нас не просто бесполезное условие, но и имеется код, который никогда не будет выполнен. В этом случае я повышаю приоритет сообщения об ошибке. Для вышеприведённого примера имеется недостижимое ребро, но достижимы все вершины:

А вот простой метод, в котором появляется недостижимая вершина (тело оператора if):

int test(int x) < if( x >10 x < 5 ) < return 1; >return 0; >

CFG будет выглядеть так:

finally

Всё это классно работало, пока я не столкнулся с finally. Компиляторы дублируют finally-блоки в байт-коде, из-за чего появляются недостижимые условия, которых не было в исходнике. Скажем, такой простой пример:

int test(int x) < try < if( x >0 ) return -1; return 0; > finally < if( x >

Код вполне нормальный, но в процессе компиляции он превращается во что-то такое (без учёта возможных исключений):

int test(int x) < if( x >0 ) < if( x if( x

Найденные ошибки

Теперь самая весёлая часть. Я обычно для тестов анализирую пачку проектов с открытыми исходниками, поэтому примеры будут из разных проектов.

Ошибки из-за диапазона значений типа

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

public final static boolean isNameStartChar(char ch) < return (ch >bA ch < aZ) || (ch >ba ch < az) || (ch == ‘:’) || (ch == ‘_’) || (ch >0xBF ch < 0xD7) || (ch >0xD7 ch < 0xF7) || (ch >0xF7 ch < 0x300) || (ch >0x36F ch < 0x37E) || (ch >0x37E ch < 0x2000) || (ch >0x200B ch < 0x200E) || (ch >0x206F ch < 0x2190) || (ch >0x2BFF ch < 0x2FF0) || (ch >0x3000 ch < 0xD800) || (ch >0xF900 ch < 0xFDD0) || (ch >0xFDEF ch < 0xFFFE) || (ch >0x0FFFF ch < 0xF0000); // ch >0xFFFF всегда истинно >

Последняя пара условий бессмысленна: значение переменной типа char не может быть больше 0xFFFF. Если авторы планировали поддерживать такие символы, надо анализировать суррогатные пары UTF-16, анализом одного char тут не обойдёшься.

Вот более конкретное — Utility#encodeRun из проекта IBM ICU:

private static final char ESCAPE = ‘uA5A5’; private static final void encodeRun(T buffer, short value, int length) < try < if (length < 4) < for (int j=0; j> . >

ESCAPE при преобразовании в int равно 0xA5A5 (42405) и никак не может равняться переменной типа short, которая принимает значения от -32768 до 32767.

Использован вместо ||

Одна из частых грубых ошибок. Обычно встречается в проверке входных параметров, которая не всегда должным образом покрыта юнит-тестами. Вот, например, в SegmentArrayWithData#setElementAt в IntelliJ IDEA:

public void setElementAt(int i, int startOffset, int endOffset, int data) < if (data < 0 data >Short.MAX_VALUE) throw new IndexOutOfBoundsException(«data out of short range» + data); . >

Здесь data > Short.MAX_VALUE бессмысленно, потому что не может быть число одновременно меньше 0 и больше 32767. В результате формируется мёртвый код: исключение никогда не будет выкинуто. Подобная бага была найдена в различных проектах, но меня удивило увидеть это в IDEA: у них самих встроенный серьёзный статический анализатор, который наверняка должен ловить такое. Возможно, проглядели.

Использован || вместо

Такое встречается существенно реже. Вот снова из ICU — ULocale#parseAcceptLanguage:

case 8: // before q value fraction part if (‘0’ else < // invalid state = -1; >break;

Одно и то же условие в двух ветках

Пример из Eclipse Mylyn — DefaultXmlStreamWriter#printEscaped:
private static void printEscaped(PrintWriter writer, int ch, boolean attribute) throws IOException < String ref = getEntityRef(ch, attribute); if (ref != null) < writer.write(‘ writer.write(ref); writer.write(‘;’); >else if (ch == ‘r’ || ch == 0x0085 || ch == 0x2028) < printHex(writer, ch); >else if ((ch >= ‘ ‘ ch != 160 isUtf8Printable((char) ch) XML11Char.isXML11ValidLiteral(ch)) || ch == ‘t’ || ch == ‘n’ || ch == ‘r’) < // ch == ‘r’ всегда ложно writer.write((char) ch); >else < printHex(writer, ch); >>

Здесь условие ch == ‘r’ имеется в двух ветках else if. Сработает, конечно, только первое. Мёртвого кода нет, но неясно, что имел в виду автор.

Взаимоисключающие параграфы

Вот довольно свежий код из того же Mylyn — EscapeBlock#canStart:

public boolean canStart(String line, int lineOffset) < if (lineOffset == 0) < Matcher matcher = START_PATTERN.matcher(line); if (lineOffset >0) < // lineOffset >0 всегда ложно matcher.region(lineOffset, line.length()); > if (matcher.matches()) < return true; >> return false; >

Если уж lineOffset равен 0, то он никак не может быть больше 0.

Забыли, что было раньше?

for (int i = 0; i < modelAtomCount; ++i) < rd(); int len = line.length(); if (len != 44 len != 68) < Logger.warn(«line cannot be read for GROMACS atom data: » + line); continue; >. if (len < 69) // len

В начале цикла проверяется длина прочитанной из файла строки. Если она не равна 44 или 68, выдаём предупреждение и переходим к следующей итерации цикла. Ближе к концу итерации ещё одна проверка на len: теперь уже if (len < 69). Досюда могли дойти только два значения len: 44 или 68.

Оба они меньше 69, поэтому условие всегда сработает и последние 6 строчек цикла никогда не выполнятся.

Запутались в операторах сравнения

private static final boolean isJamo(char ch) < return (ch >= 0x1100 ch = 0x1175 ch = 0x11A8 ch

Средняя пара условий находит числа в диапазоне от 0x1175 до 0x1161. Разумеется, таких чисел быть не может, так как 0x1161 меньше, чем 0x1175. Здесь мы выдаём предупреждение, что условие ch

Переполнение при вычислениях

Вот Andrey2008 постоянно спрашивают, может ли он показать весёлые баги из кода PVS-Studio, найденные PVS-Studio, а он отвечает, что все баги обычно исправляются сразу, так как используется инкрементальная проверка, и они даже в репозиторий не попадают. В целом это справедливо и для FindBugs: Eclipse-проект в FindBugs настроен на инкрементальную проверку, так что трудно найти что-то серьёзное в FindBugs, проверяя его им же самим. Но всё меняется, когда разрабатываешь новый детектор. Тогда он действительно может найти очень вкусную багу в старом коде, что и случилось. Посмотрите метод DumbMethods#checkForCompatibleLongComparison

private void checkForCompatibleLongComparison(OpcodeStack.Item left, OpcodeStack.Item right) < if (left.getSpecialKind() == Item.RESULT_OF_I2L right.getConstant() != null) < long value = ((Number) right.getConstant()).longValue(); if ( (value >Integer.MAX_VALUE || value < Integer.MIN_VALUE)) < int priority = Priorities.HIGH_PRIORITY; if (value == Integer.MAX_VALUE+1 || value == Integer.MIN_VALUE -1) < // оба условия всегда ложны priority = Priorities.NORMAL_PRIORITY; >. >

Данный код (написанный, кстати, более четырёх лет назад) выполняется в случае, если в анализируемом исходнике число типа int сравнивается с числом типа long, которое не влезает в диапазон int. Такое сравнение бессмысленно, поэтому здесь генерируется предупреждение INT_BAD_COMPARISON_WITH_INT_VALUE.

Предполагалось установить приоритет пониже, если сравнение выполняется с числом, которое на границе диапазона целых чисел (Integer.MAX_VALUE+1 или Integer.MIN_VALUE-1). Дело однако в том, что эти выражения сами вычисляются в целых числах и возникает переполнение: вместо Integer.MAX_VALUE+1 мы получаем Integer.MIN_VALUE, а вместо Integer.MIN_VALUE-1 получаем Integer.MAX_VALUE. Причём это вычисление выполняет компилятор, и в байткод попадает уже результирующее число. Здесь-то мой новый детектор и блеснул: из вышестоящего условия следует, что ни Integer.MIN_VALUE, ни Integer.MAX_VALUE не может быть в value в данной точке. В результате условие никогда не выполнится, и приоритет никогда не будет понижен. Конечно, следовало написать

if (value == Integer.MAX_VALUE+1L || value == Integer.MIN_VALUE-1L)

Понятно, почему этот баг оставался незамеченным годами: пользователи могли и не догадываться о намерении авторов понизить приоритет в данном случае, а тесты в FindBugs обычно проверяют, есть ли определённое предупреждение на определённом коде или нет, но не проверяют его приоритет.

Перестраховка

Довольно много сообщений выдаётся о перестраховочных условиях вроде таких:

if( x > 0 ) < . >else if( x

Второе условие очевидно не нужно, хотя кто-то может поспорить, что оно дополнительно документирует код. Всё же я считаю, что если пояснение нужно, его лучше написать в комментарии. Во всяком случае, ранее FindBugs уже ругался на такой код:

if( obj == null ) < . >else if( obj != null )

Поэтому я считаю, что не нарушил общей концепции.

Ещё встречается такой код:

if( x > 0 ) < . // много строчек if( x >0 ) < . // ещё код >. >

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

Желающие испытать новый детектор могут выкачать код из нашего репозитория и скомпилировать ant’ом. Если кому-то лень компилировать, я сделал неофициальные сборки из текущего кода — findbugs.jar и Eclipse update site (к сожалению, официальный Eclipse daily site не работает). Новые предупреждения называются UC_USELESS_CONDITION и UC_USELESS_CONDITION_TYPE (категория Dodgy code).

Если кому интересна реализация, большая часть кода в классе ValueRangeAnalysisFactory, сам детектор — RedundantConditions, а поиск дублирующихся finally-блоков — FinallyDuplicatesInfoFactory. Код ещё неокончательный, но вполне рабочий. Могут быть ложные сработки в assert’ах, с этим будем бороться.

Ошибки есть в любой программе, а статический анализ — это хорошо.

findbugs
статический анализ кода
open source
граф потока управления

Разработка веб-сайтов
Программирование
Java

Источник: habr.com