Lecture03 (Лекции в ПДФ), страница 3

Среди них найдем такие пары, что в них меняется значение только одногоэлементарного условия и всего условия в целом.x>0x == 0 y > 0 z == null Ix>0x == 0 y > 0z == null00000C0001000100AD00110B01001CG01010G01101DH01110H10000E10010F10101AE10111BFСоответствующие комбинации помечены в последних четырех столбцах таблицы. Двестроки помечены одной буквой, когда они входят в одну пару комбинаций. Эта букванаходится в столбце, соответствующем элементарному условию, которое меняет своезначение. Чтобы обеспечить полное покрытие по MC/DC для первого условия, необходимовыбрать по паре комбинаций, соответствующих хотя бы одной букве в каждом из последнихчетырех столбцов.

Достаточно, например, выбрать комбинации, помеченные буквами A, D,E, H. Это всего лишь 5 комбинаций. Или B, C, F, G — это 6 комбинаций.Ниже приведена аналогичная таблица для второго условия ветвления. Условия (z == null)и (z != null) однозначно определяют значения друг друга, поэтому можно рассматриватьтолько одно из них. Кроме того, нельзя изменить значение (z == null) и не изменить значенияz.isEmpty() — это условие вычислимо только при одном значении первого.

Можно, однако,считать, что неопределенное значение формулы z.isEmpty() соответствует любому еезначению из другой комбинации.x < 0 z == nullz != null z.isEmpty() II x < 0 z == null z.isEmpty()10100C10111C1101 A00100D00111BD0100 ABТаким образом, можно выбрать набор комбинаций, помеченных буквами A, B и D —всего 4 комбинации.Итоговый полный набор комбинаций по метрике MC/DC помечен звездочками вследующей таблице.x>0x == 0 x < 0 y > 0z == null z != null z.isEmpty() III1***0010010002001001101300101001400110100050011011016***001110017***01000101080100011119***0100100010010101010110101011111201011000131000010001410000110115*** 1000100016*** 10010101017*** 10010111118*** 10011010Заметим, что из 18 возможных комбинаций достаточно отобрать только 8, чтобыполучить полное покрытие по MC/DC.•Пара комбинаций 1 и 7 показывает, что изменение значения (x == 0) может изменитьвыполняемую ветвь в первом ветвлении.•Пара комбинаций 6 и 18 показывает то же для условия (x > 0).•Пара комбинаций 7 и 9 — то же для условия (z == null).•Пара комбинаций 15 и 18 — то же для условия (y > 0).•Пара комбинаций 16 и 17 — то же для условия z.isEmpty() и второго ветвления.Пара комбинаций 6 и 18 — то же для условия (x < 0) и второго ветвления.•Пара комбинаций 17 и 18 — то же для условия (z == null) и второго ветвления.В общем случае метрика MC/DC позволяет вместо 2n комбинаций условий использовать2n различных ситуаций.Другая метрика покрытия, более сильная, чем покрытие ветвей, основана наиспользовании короткой логики.

Различные ситуации по этой метрике соответствуютразличным коротким дизъюнктам, то есть комбинациям значений элементарных условийоднозначно, с учетом короткой логики, определяющим выполнение всех ветвлений в кодепрограммы. Соответственно, покрытие считается как доля покрытых дизъюнктов среди всехвозможных.Снова используем пример с двумя ветвлениями, определяемыми условиями (x > 0) && (y> 0) || (x == 0) && (z != null) и (x < 0) && (z == null) || (z != null) && z.isEmpty().

Пусть , дляопределенности, код программы имеет примерно такой вид.if((x > 0) && (y > 0) || (x == 0) && (z != null)) …else ……if((x < 0) && (z == null) || (z != null) && z.isEmpty()) …else …Таблица комбинаций значений элементарных условий, которые однозначно определяютход ее выполнения в соответствии с короткой логикой, показана ниже. Эти комбинацииотличаются от всех возможных комбинаций тем, что значение (y < 0) при (x <= 0) не важно,поскольку это условие не будет оцениваться по правилам короткой логики. Вместо звездочекможно подставить произвольные значения.x>0x == 0 x < 0 y > 0z == null z != null z.isEmpty() III001*01000001*01101001*1001010*01010010*01111010*10001000010001000011011000100010010101010010111110011010Строится такая таблица следующим образом.Элементарные условия, входящие в программу, выстраиваются в некоторойпоследовательности.

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

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

Если же всеформулы равны 1, таблица построена.Ниже приведена схема отношения «сильнее» для метрик покрытия, основанных напотоке управления.Покрытие комбинацийусловийМодифицированное покрытиеветвей и условий (MC/DC)Покрытие короткихдизъюнктовПокрытие ветвей и условийПокрытие ветвейПокрытие условийПокрытие инструкцийМетрики покрытия на основе потоков данныхМетрики покрытия на основе потоков данных определяются использованием в программеразличных значений данных.

Поскольку задача метрики покрытия — выделениеразнообразных ситуаций, основной интерес представляют переменные программы, которыемогут в разных сценариях ее выполнения представлять различные значения. В качествепеременных рассматриваются и параметры функции.Следующие два понятия нужны только для определения ряда метрик покрытий.Инструкция, в которой используется некоторая переменная, называется ее использованием(use). Инструкция, в которой определяется новое значение для некоторой переменной,называется ее определением (definition).Точка входа в функцию считается определением для всех ее параметров.Примеры.Инструкция if(x > 0 && y <= z) …; использует три переменных — x, y, z.Инструкция x = y++ – 12*(t = z+1) + t*t; использует переменные y, z, t и определяетпеременные x, y, t. Для переменной y порядок определения и использования заданоднозначно — она сначала используется, потом определяется.

Для переменной t этотпорядок зависит от языка и компилятора: для Java он задан однозначно — используетсятолько что определенное значение t, равное z+1, для С или С++ этот порядок, а вместе с ними результата всего выражения, зависит от конкретного компилятора и даже от того,собиралась ли содержащая эту инструкцию программа с оптимизациями или нет.du-путь или путь от определения к использованию для заданной переменной — путь пографу потока управления, начинающийся с вершины, соответствующей инструкции,определяющей значение переменной, заканчивающийся вершиной, соответствующейинструкции ее использования, и не содержащий вершин для инструкций определения этойпеременной, кроме первой.Инструкции использования переменной могут входить в du-путь много раз.Рассмотрим снова пример функции, вычисляющей наибольший общий делитель.1int gcd(int a, int b)23456789101112131415161718192021222324{if(a == 0)return b;if(b == 0)return a;if(a > 0 && b < 0 || a < 0 && b > 0)b = -b;while(b != 0){if(b > a && a > 0 || b < a && a < 0){a = b-a;b = b-a;a = a+b;}b = a-b;a = a-b;}return a;}Чтобы аккуратно определять места определения и использования переменных нужнопостроить полный граф потока управления с учетом короткой логики.

В этом графесоставному условию ветвления может соответствовать несколько ветвлений — ровностолько, сколько разных сценариев вычисления этого условия с учетом короткой логики.354677’10231212’В нашем примере две переменных — a и b. Места определения значений a помечены награфе белыми ромбами, а места использования — белыми кружками. Для b определенияпомечены черными ромбами, а использования — черными кружками.du-путь считается покрытым, если он был полностью пройден при выполнениипрограммы.

Недостижимым называется du-путь, который не может быть покрыт ни прикаком выполнении программы. Использование переменной считается покрытым, если длякаждого определения этой переменной, для которого есть хотя бы один du-путь,начинающийся в этом определении и ведущий к этому использованию, один из таких путейбыл покрыт.Метрика покрытия использований (all-uses coverage) — доля покрытых использованийвсех переменных по отношению к количеству достижимых использований.Метрика покрытия du-путей (du-path coverage) — доля покрытых du-путей для всехпеременных программы по отношению к достижимым du-путям.Метрика покрытия du-путей сильнее метрики покрытия использований. Она являетсяодной из самых сильных метрик покрытия, используемых на практике.

Хотя кажется, чтоколичество тестов в полном наборе по такой метрике может быть очень большим, вбольшинстве случаев это не так — один тест часто покрывает сразу много du-путей.Замечание. Обычно в учебниках и статьях, касающихся метрик покрытия на основе потока управления ина основе потоков данных, утверждается, что полное покрытие использований (и, тем более, du-путей)влечет полное покрытие ветвей.