Нарезка программы

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

Техника нарезки получила быстрое развитие со времени первоначального определения Марка Вейзера . Сначала нарезка была только статической, т. е. применялась к исходному коду без какой-либо другой информации, кроме исходного кода. Богдан Корель и Януш Ласки представили динамическую нарезку , которая работает при конкретном выполнении программы (для заданной трассировки выполнения). ^[1] Существуют и другие формы нарезки, например нарезка пути. ^[2]

Статическая нарезка

Согласно первоначальному определению Вейзера, ^[3] неофициально, статический фрагмент программы S состоит из всех операторов программы P, которые могут повлиять на значение переменной v в операторе x. Срез определяется для критерия среза C=(x,v), где x — оператор в программе P, а v — переменная в x. Статический срез включает в себя все операторы, которые могут повлиять на значение переменной v в операторе x для любого возможного ввода. Статические срезы вычисляются путем обратного отслеживания зависимостей между операторами. Точнее, чтобы вычислить статический срез для (x,v), мы сначала находим все операторы, которые могут напрямую повлиять на значение v, прежде чем встретится оператор x. Рекурсивно для каждого оператора y, который может повлиять на значение v в операторе x, мы вычисляем срезы для всех переменных z в y, которые влияют на значение v. Объединение всех этих срезов представляет собой статический срез для (x,v). .

Пример

Например, рассмотрим программу на языке C ниже. Давайте вычислим срез для ( write(sum), sum ). На значение суммы напрямую влияют утверждения «sum = sum + i + w», если N>1, и «int sum = 0», если N <= 1. Таким образом, срез (write(sum), sum) — это объединение из трех срезов и оператора «int sum = 0», который не имеет зависимостей:

срез (сумма = сумма + я + ш, сумма),
срез (сумма = сумма + я + ш, я),
срез (сумма = сумма + я + ш, ш), и
{интервал суммы=0}.

Довольно легко увидеть, что срез( sum = sum + i + w, sum) состоит из «sum = sum + i + w» и «int sum = 0», поскольку это единственные два предыдущих утверждения, которые могут повлиять на значение суммы в «сумма = сумма + я + ш». Аналогично, срез (сумма = сумма + я + w, i) содержит только «for(i = 1; i < N; ++i) {», а срез (сумма = сумма + я + w, w) содержит только оператор "интервал ш = 7".

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

int i;
int sum = 0;
int product = 1;
int w = 7;
for(i = 1; i < N; ++i) {
  sum = sum + i + w;
  product = product * i;
}
write(sum);
write(product);

Статический исполняемый фрагмент для критериев ( write(sum), sum) — это новая программа, показанная ниже.

int i;
int sum = 0;
int w = 7;
for(i = 1; i < N; ++i) {
  sum = sum + i + w;

}
write(sum);

Фактически, большинство методов статической нарезки, включая собственную технику Вейзера, также удаляют write(sum) заявление. Поскольку по заявлению write(sum), значение sum не зависит от самого утверждения. Часто срез для конкретного оператора x будет включать более одной переменной. Если V — это набор переменных в утверждении x, то срез для (x, V) — это объединение всех срезов с критериями (x, v), где v — переменная из множества V.

Облегченный метод прямой статической нарезки

Очень быстрый и масштабируемый, но немного менее точный подход к нарезке чрезвычайно полезен по ряду причин. Разработчики получат очень дешевые и практичные средства для оценки последствий изменения за считанные минуты, а не дни. Это очень важно для планирования внедрения новых функций и понимания того, как изменение связано с другими частями системы. Это также обеспечит недорогой тест, чтобы определить, оправдан ли полный и более дорогой анализ системы. Подход быстрого срезирования откроет новые возможности для исследований метрик и анализа историй на основе срезов. То есть теперь нарезку можно проводить на очень больших системах и на целых историях версий в очень практичные сроки. Это открывает двери для ряда экспериментов и эмпирических исследований, которые раньше были слишком дорогостоящими. ^[4]

Динамическая нарезка

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

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

См. также

Обслуживание программного обеспечения
Анализ зависимостей
Достижение определения
Зависимость данных
Frama-C — инструмент, реализующий алгоритмы нарезки в программах на языке C.
Частичное устранение мертвого кода

Примечания

^ Корель, Богдан; Ласки, Януш (1988). «Динамическая нарезка программы». Письма об обработке информации . 29 (3): 155–163. CiteSeerX 10.1.1.158.9078 . дои : 10.1016/0020-0190(88)90054-3 .
^ Джала, Ранджит; Маджумдар, Рупак (2005). «Нарезка пути». Материалы конференции ACM SIGPLAN 2005 года по проектированию и реализации языков программирования . ПЛДИ '05. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 38–47. дои : 10.1145/1065010.1065016 . ISBN 9781595930569 . S2CID 5065847 .
^ Вайзер, Марк Дэвид (1979). Срезы программы: формальные, психологические и практические исследования метода автоматической абстракции программ (кандидатская диссертация). Анн-Арбор, Мичиган, США: Мичиганский университет.
^ Аломари, Хакам В.; Коллард, Майкл Л.; Малетик, Джонатан И.; Альхиндави, Нух; Мекдади, Омар (19 мая 2014 г.). «srcSlice: очень эффективная и масштабируемая прямая статическая нарезка». Журнал программного обеспечения: эволюция и процесс . 26 (11): 931–961. CiteSeerX 10.1.1.641.8891 . дои : 10.1002/смр.1651 . ISSN 2047-7473 . S2CID 18520643 .

Ссылки

Марк Вайзер . «Программная нарезка». Материалы 5-й Международной конференции по разработке программного обеспечения, страницы 439–449, IEEE Computer Society Press, март 1981 г.
Марк Вайзер . «Программная нарезка». Транзакции IEEE по разработке программного обеспечения, том 10, выпуск 4, страницы 352–357, IEEE Computer Society Press, июль 1984 г.
Сьюзен Хорвиц , Томас Репс и Дэвид Бинкли, Межпроцедурное нарезка с использованием графов зависимостей, Транзакции ACM в языках и системах программирования, том 12, выпуск 1, страницы 26–60, январь 1990 г.
Фрэнк Тип. «Обзор методов нарезки программ». Журнал языков программирования, том 3, выпуск 3, страницы 121–189, сентябрь 1995 г.
Дэвид Бинкли и Кит Брайан Галлахер. «Программная нарезка». Достижения в области компьютеров, том 43, страницы 1–50, Academic Press , 1996.
Андреа де Люсия. «Нарезка программ: методы и приложения», Международный семинар по анализу и манипулированию исходным кодом, страницы 142–149, 2001, IEEE Computer Society Press.
Марк Харман и Роберт Хиронс. «Обзор нарезки программ», Software Focus, том 2, выпуск 3, страницы 85–92, январь 2001 г.
Дэвид Бинкли и Марк Харман. «Обзор эмпирических результатов по нарезке программ», «Достижения в области компьютеров», том 62, страницы 105–178, Academic Press , 2004.
Йенс Кринке. «Нарезка программ», В Справочнике по разработке программного обеспечения и инженерии знаний, Том 3: Последние достижения. Мировое научное издательство , 2005 г.
Сильва, Хосеп. «Словарь методов на основе срезов программ», ACM Computing Surveys, том 44, выпуск 3, Ассоциация вычислительной техники , июнь 2012 г.
Аломари Х.В. и др. «srcSlice: очень эффективная и масштабируемая прямая статическая нарезка». Wiley Journal of Software: Evolution and Process ( JSEP ), DOI: 10.1002/smr.1651, Vol. 26, № 11, стр. 931-961, 2014.

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

ВАЛСОФТ/Проект Джоана
Инд Проект (часть Бандеровской шашки)
Проект разделения программ штата Висконсин

[1] Корель, Богдан; Ласки, Януш (1988). «Динамическая нарезка программы». Письма об обработке информации . 29 (3): 155–163. CiteSeerX 10.1.1.158.9078 . дои : 10.1016/0020-0190(88)90054-3 .

[2] Джала, Ранджит; Маджумдар, Рупак (2005). «Нарезка пути». Материалы конференции ACM SIGPLAN 2005 года по проектированию и реализации языков программирования . ПЛДИ '05. Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 38–47. дои : 10.1145/1065010.1065016 . ISBN 9781595930569 . S2CID 5065847 .

[3] Вайзер, Марк Дэвид (1979). Срезы программы: формальные, психологические и практические исследования метода автоматической абстракции программ (кандидатская диссертация). Анн-Арбор, Мичиган, США: Мичиганский университет.

[4] Аломари, Хакам В.; Коллард, Майкл Л.; Малетик, Джонатан И.; Альхиндави, Нух; Мекдади, Омар (19 мая 2014 г.). «srcSlice: очень эффективная и масштабируемая прямая статическая нарезка». Журнал программного обеспечения: эволюция и процесс . 26 (11): 931–961. CiteSeerX 10.1.1.641.8891 . дои : 10.1002/смр.1651 . ISSN 2047-7473 . S2CID 18520643 .

[1]

[2]

[3]

[4]