Определенный анализ назначения - Definite assignment analysis
В Информатика, анализ определенного назначения это анализ потока данных использован компиляторы чтобы консервативно гарантировать, что переменная или местоположение всегда назначаются перед их использованием.
Мотивация
В C и C ++ программ, источником особенно трудно диагностируемых ошибок является недетерминированное поведение, возникающее в результате чтения неинициализированные переменные; это поведение может различаться для разных платформ, сборок и даже от запуска к запуску.
Есть два распространенных способа решения этой проблемы. Один из них - убедиться, что все местоположения записаны до их чтения. Теорема Райса устанавливает, что эта проблема не может быть решена в целом для всех программ; однако можно создать консервативный (неточный) анализ, который будет принимать только программы, удовлетворяющие этому ограничению, и отвергать некоторые правильные программы, и таким анализом является анализ определенного назначения. В Ява[1] и C #[2] Спецификации языка программирования требуют, чтобы компилятор сообщал об ошибке времени компиляции, если анализ не удался. Оба языка требуют особой формы анализа, детально описанного. В Java этот анализ был формализован Stärk et al.,[3] а некоторые правильные программы отклоняются и должны быть изменены, чтобы ввести явные ненужные назначения. В C # этот анализ был формализован Fruja и является точным и надежным в том смысле, что все переменные, назначенные на всех путях потока управления, будут считаться определенно назначенными.[4] В Циклон язык также требует, чтобы программы проходили определенный анализ присваивания, но только для переменных с указательными типами, чтобы упростить перенос программ на C.[5]
Второй способ решения проблемы - автоматическая инициализация всех местоположений некоторым фиксированным, предсказуемым значением в точке, в которой они определены, но это вводит новые назначения, которые могут снизить производительность. В этом случае анализ определенного назначения позволяет оптимизация компилятора где избыточные назначения - назначения, за которыми следуют только другие назначения без возможных промежуточных чтений - могут быть устранены. В этом случае никакие программы не отклоняются, но программы, для которых анализ не может распознать определенное назначение, могут содержать избыточную инициализацию. В Инфраструктура общего языка полагается на этот подход.[6]
Терминология
Можно сказать, что переменная или местоположение находятся в одном из трех состояний в любой заданной точке программы:
- Определенно назначен: Переменная точно известно, что она будет назначена.
- Определенно не назначен: Переменная наверняка не назначена.
- Неизвестный: Переменная может быть присвоена или не назначена; анализ недостаточно точен, чтобы определить, какие именно.
Анализ
Нижеследующее основано на формализации Fruja внутрипроцедурного (одиночного метода) анализа определенного присваивания C #, который отвечает за обеспечение того, чтобы все локальные переменные были присвоены до их использования.[4] Он одновременно выполняет анализ определенного назначения и постоянное распространение логических значений. Мы определяем пять статических функций:
| Имя | Домен | Описание |
|---|---|---|
| перед | Все утверждения и выражения | Переменные, определенно присвоенные перед вычислением данного оператора или выражения. |
| после | Все утверждения и выражения | Переменные, определенно присвоенные после оценки данного оператора или выражения, при условии, что оно завершается нормально. |
| варс | Все утверждения и выражения | Все переменные, доступные в рамках данного оператора или выражения. |
| истинный | Все логические выражения | Переменные, определенно присвоенные после оценки данного выражения, при условии, что выражение оценивается как истинный. |
| ложный | Все логические выражения | Переменные, определенно присвоенные после оценки данного выражения, при условии, что выражение оценивается как ложный. |
Мы предоставляем уравнения потока данных, которые определяют значения этих функций в различных выражениях и утверждениях в терминах значений функций в их синтаксических подвыражениях. Предположим пока, что нет идти к, перемена, Продолжить, возвращаться, или же Обработка исключений заявления. Ниже приведены несколько примеров этих уравнений:
- Любое выражение или утверждение е это не влияет на набор определенных переменных: после(е) = перед(е)
- Позволять е быть выражением присваивания место = v. потом перед(v) = перед(е), и после(е) = после(v) U {loc}.
- Позволять е быть выражением истинный. потом истинный(е) = перед(е) и ложный(е) = варс(е). Другими словами, если е оценивает ложный, все переменные (бессмысленно ) определенно назначен, потому что е не оценивается как ложь.
- Поскольку аргументы метода оцениваются слева направо, перед (аргументя + 1) = после (аргументя). После завершения метода из параметры точно назначаются.
- Позволять s быть условным заявлением если (е) s1 еще s2. потом перед(е) = перед(s), перед(с1) = истинный(е), перед(s2) = ложный(е), и после(s) = после (s1) пересекаются после (s2).
- Позволять s быть оператором цикла while пока (е) s1. Тогда перед (е) = до (s), перед(s1) = истина (е), и после(s) = ложь (е).
- И так далее.
В начале метода никакие локальные переменные точно не назначаются. Проверяющий многократно перебирает абстрактное синтаксическое дерево и использует уравнения потока данных для переноса информации между наборами до тех пор, пока фиксированная точка может быть достигнуто. Затем проверяющий проверяет перед набор каждого выражения, использующего локальную переменную, чтобы гарантировать, что оно содержит эту переменную.
Алгоритм усложняется введением скачков потока управления типа идти к, перемена, Продолжить, возвращатьсяи обработка исключений. Любое утверждение, которое может стать целью одного из этих прыжков, должно пересекать его перед установлен с набором точно назначенных переменных в источнике перехода. Когда они вводятся, результирующий поток данных может иметь несколько фиксированных точек, как в этом примере:
1 int я = 1;2 L:3 идти к L;Поскольку метка L может быть достигнута из двух мест, уравнение потока управления для goto диктует, что перед(2) = после(1) пересечь перед(3). Но перед(3) = перед(2), поэтому перед(2) = после(1) пересечь перед(2). У этого есть две фиксированные точки для перед(2), {i} и пустое множество. Однако можно показать, что из-за монотонной формы уравнений потока данных существует уникальная максимальная фиксированная точка (фиксированная точка наибольшего размера), которая обеспечивает наиболее возможную информацию об определенно присвоенных переменных. Такую максимальную (или максимальную) фиксированную точку можно вычислить стандартными методами; видеть анализ потока данных.
Дополнительная проблема заключается в том, что скачок потока управления может сделать некоторые потоки управления невозможными; например, в этом фрагменте кода переменная я определенно назначается перед его использованием:
1 int я;2 если (j < 0) возвращаться; еще я = j;3 Распечатать(я);Уравнение потока данных для если Говорит, что после(2) = после (возвращаться) пересекаются после (я = j). Чтобы это сработало правильно, определим после(е) = варс(е) для всех скачков потока управления; это пусто справедливо в том же смысле, что и уравнение ложный(истинный) = варс(е) допустимо, потому что управление не может достичь точки сразу после перехода потока управления.
Рекомендации
- ^ Дж. Гослинг; Б. Радость; Г. Стил; Г. Браха. «Спецификация языка Java, 3-е издание». с. Глава 16 (стр.527–552). Получено 2 декабря, 2008.
- ^ «Стандартный ECMA-334, спецификация языка C #». ECMA International. стр. Раздел 12.3 (стр.122–133). Получено 2 декабря, 2008.
- ^ Stärk, Роберт Ф .; Э. Боргер; Иоахим Шмид (2001). Java и виртуальная машина Java: определение, проверка, проверка. Secaucus, NJ, USA: Springer-Verlag New York, Inc., стр. Раздел 8.3. ISBN 3-540-42088-6.
- ^ а б Фруя, Нику Г. (октябрь 2004 г.). «Правильность анализа с определенным назначением в C #». Журнал объектных технологий. 3 (9): 29–52. CiteSeerX 10.1.1.165.6696. Дои:10.5381 / jot.2004.3.9.a2. Получено 2008-12-02.
На самом деле мы доказываем больше, чем правильность: мы показываем, что решение анализа является идеальным решением (а не только безопасным приближением).
- ^ «Циклон: определенное назначение». Руководство пользователя Cyclone. Получено 16 декабря, 2008.
- ^ «Стандартный ECMA-335, Common Language Infrastructure (CLI)». ECMA International. стр. Раздел 1.8.1.1 (Раздел III, стр. 19). Получено 2 декабря, 2008.