Пособие по практике программирования
         

Отладка

bug ("жучок", "баг").
b. Дефект или/неполадка в машине, плане и т. п. Происх. — США.
"Пэл Мэл Газет", 1889, 11 марта, 1/1. Мистер Эдисон, как я слышал, провел две бессонных ночи, отыскивая "жучка" в своем фонографе, — это выражение означает решение сложной проблемы, его использование подразумевает, что где-то внутри спряталось какое-то воображаемое насекомое, которое и вызывает все проблемы.

Oxford English Dictionary, 2"d Edition



В предыдущих четырех главах мы продемонстрировали много различного кода и при этом притворялись, что весь этот код работал должным образом с первого раза. Естественно, это было не так: на самом деле было множество "багов". Слово "баг" появилось вовсе не среди программистов, но считается одним из самых распространенных терминов в программировании. Почему программирование столь сложно?

Одна из причин сложности программы заключается в большом количестве способов, с помощью которых могут взаимодействовать ее компоненты, а уж программы полны и компонентами, и взаимосвязями между ними. Многие технологии пытаются сократить связи между компонентами, чтобы уменьшить количество взаимодействий: например, используется сокрытие информации, абстрагирование и интерфейсы, а также все возможности языков, способствующие этим технологиям. Существуют также технологии для проверки целостности архитектуры программы: доказательства корректности программ, моделирование, анализ требований, формальные проверки. Ни одна из перечисленных технологий не изменила радикально способа создания программ: они работают лишь на небольших задачах. В реальности всегда будут ошибки, которые мы находим с помощью тестирования и устраняем с помощью отладки (debugging).

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

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

Какова роль языка? Основной движущей силой в эволюции языков программирования была попытка предотвратить ошибки с помощью возможностей языка. Некоторые такие возможности уменьшают шанс появления целых классов ошибок: проверка диапазонов индексов, ограничение использования указателей или полный отказ от них, сборка мусора, строковые типы данных, типизированный ввод-вывод, строгая проверка типов. Однако некоторые возможности языка напрашиваются на ошибку, например оператор goto, глобальные переменные, свободно используемые указатели, автоматические преобразования типов. Программистам следует знать зоны повышенного риска в своих языках и быть особенно осторожными при их использовании. Следует также включить все проверки компилятора и слушаться его предупреждений.

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

Как бы нам ни хотелось обратного, но основное время при программировании тратится на тестирование и отладку. В этой главе мы обсудим, как сократить время, которое вы тратите на отладку, и как использовать это время наиболее продуктивно; к вопросам тестирования мы вернемся в главе 6.

Отладчики

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

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

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

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

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

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

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


Хорошие подсказки, простые ошибки

Ой! Что-то случилось. Моя программа "свалилась", напечатала какой-то мусор или, кажется, "зависла". Что мне делать?

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

К счастью, в большинстве своем ошибки просты, и их можно обнаружить с помощью простых приемов. Изучите улики — неверные результаты работы и попытайтесь догадаться, как такие результаты могли возникнуть. Посмотрите на отладочную выдачу перед аварийным завершением; если возможно, получите у отладчика стек вызовов. Теперь вы уже кое-что знаете о том, что именно произошло и где. Остановитесь, подумайте. Как такое могло случиться? Рассуждайте, исходя из состояния "свалившейся" программы, чтобы определить причину.

Процесс отладки включает в себя обратную трассировку (backward reasoning) — прослеживание событий в обратном порядке, как в детективе. Случилось что-то невозможное, и единственное, что известно точно, — невозможное случилось. Для того чтобы раскрыть причины, нужно мысленно проходить обратный путь от результата к возможной причине. Когда у нас имеется полное объяснение, мы знаем, что именно исправлять и, по ходу дела, скорее всего, обнаружим несколько других вещей, которых мы не ожидали.

Ищите знакомые ситуации. Спросите себя, известна ли уже вам эта ситуация. "Я уже видел это" — с этой фразы часто начинается понимание, а иногда даже и возникает ответ. Обычные ошибки имеют четко различимые признаки. Например, начинающие программисты на С часто пишут 

? int n

вместо

 int n;
 scant ("$ &п);

При такой попытке ввода значения обычно возникает ошибка обращения за пределы доступной памяти. Преподаватели языка С немедленно узнают этот симптом.

Несовпадающие типы и преобразования при вызове printf и scant рождают бесконечный поток тривиальных ошибок:

Признаком этой ошибки иногда бывают абсурдные значения переменных: огромные целые, невероятно большие или невероятно маленькие значения с плавающей точкой. На Sun SPARC эта программа выводит огромное целое и астрономическое число с плавающей точкой (выдача отформатирована, чтобы не выходить за поля страницы):



Другой обычной ошибкой является использование %f вместо %lf, когда значение типа double читается с помощью scanf. Некоторые компиляторы ловят такие ошибки, проверяя, соответствуют ли типы аргументов scanf и printf параметрам форматной строки; если вывод всех предупреждений компилятора разрешен, то относительно приведенного выше обращения к printf компилятор GNU gcc сообщит

х.с:9: warning: int format, double arg (arg 2)
 x.c:9: warning: double format, different type arg (arg 3)

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

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

Не повторяйте дважды туже самую ошибку. После того как вы исправите ошибку, спросите себя, не совершали ли вы подобной ошибки когда-то раньше. Такая история случилась с нами буквально за несколько дней до того, как мы писали эту главу. Для нашего коллеги была написана программа-прототип, которая включала в себя стереотипную конструкцию для разборки опций:




Довольно скоро nocjje опробования программы наш коллега сообщил, что имя выходного файла всегда начиналось с -о. Это было обидно, но, как оказалось, легко исправимо: код следовало читать так:

outname = &argv[i][2];

Программа была исправлена и отослана обратно, а затем пришла опять с сообщением, что программа не обрабатывала должным образом аргументы типа - f 123: преобразованное числовое значение всегда содержало ноль. Это та же самая ошибка: следующая часть оператора выбора должна была звучать так:

 from = atoi(&argv[i][2]);

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

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

Не откладывайте отладку на потом. Чрезмерная торопливость может повредить и в других ситуациях. Не игнорируйте проявившуюся ошибку: отследите ее прямо сейчас, потому что потом она может и не возникнуть. Пример — знаменитая история, случившаяся при запуске космической станции "Mars Pathfinder". После безупречного "приземления" в июле 1997 года компьютеры станции имели обыкновение перезагружаться в среднем один раз в день, и это поставило инженеров в тупик. Когда они отследили ошибку, то поняли, что уже встречались с ней. Во время предпусковых проверок такие перезагрузки случались, но были проигнорированы, потому что инженеры работали над другими вопросами. Теперь они оказались вынуждены решать проблему, когда машина находится на расстоянии десятков миллионов километров, и исправить ошибку стало значительно труднее.

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

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

nt arr[N];
qsort(arr, N, sizeof (arr[0]), icmp);i

Предположим, что мы по недосмотру передаем вместо icmp функцию сравнения строк scmp:

?int arr[N];
? qsort(arr, sizeof(arr[0]), scmp);

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



Это означает, что программа "погибла" в функции st rcmp; при изучении ситуации становится ясно, что два указателя, переданных этой функции, слишком малы — явное указание на проблему. Строка 13 в нашел тестовом файле badqs. с содержит вызов который обнаруживает загубивший вызов и указывает на ошибку.

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

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

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

Боритесь с желанием начать исправлять немедленно: подумать — хорошая альтернатива.

Объясните свой код кому-нибудь еще. Другой эффективный способ — объяснить свой код кому-нибудь еще. Такое объяснение часто помогает самому увидеть свою ошибку. Иногда требуется буквально несколько предложений — и звучит смущенная фраза: "Ой, я вижу, где ошибка, извини, что побеспокоил". Это просто замечательный метод, причем в качестве слушателей можно использовать даже непрограммистов.1 В одном университетском компьютерном центре рядом с центром поддержки сидел плюшевый медвежонок. Студенты, встретившиеся с таинственными ошибками, должны были сначала объяснить их этому медвежонку и только затем могли обратиться к консультанту.


Трудные ошибки, нет зацепок

"Не за что зацепиться. Что происходит?" Если у вас действительно нет ни малейшей догадки о том, что же происходит, жизнь становится сложнее.

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

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

Если программа способна выдавать отладочную информацию, включите ее. Программа случайного моделирования, например программа markov из третьей главы, должна иметь ключ командной строки, выдаю- ! щий такую отладочную информацию, как, например, стартовое число ] генератора случайных чисел — это нужно для того, чтобы выдачу программы можно было воспроизвести; другой ключ должен позволять' устанавливать это стартовое значение. Многие программы имеют подобные ключи командной строки, неплохо и вам сделать так же.

Разделяй и властвуй. Можно ли уменьшить объем входных данных, приводящих к "падению" программы? Сужайте диапазон возможностей, создавая наименьший набор данных, при котором ошибка все еще проявляется. При каких изменениях ошибка исчезает? Попытайтесь обна- з ружить важные тестовые случаи, специально фокусирующиеся на ошибке. Каждый тест должен быть нацелен на получение определенного результата, который подтверждает или опровергает какую-нибудь гипотезу о происходящем.

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

Изучайте нумерологию ошибок. Иногда определенная регулярность чисел, сопровождающих ошибку, подсказывает, на что нужно обратить внимание. Однажды в новой главе этой книги мы обнаружили серию опечаток, заключавшихся в пропадании случайных букв. Ситуация выглядела таинственной. Текст]$ыл создан посредством вырезания и вставки кусков другого файла,лшэтому казалось, что проблемы были в этих самых командах вырезйния и вставки. Откуда начать поиск? Мы взглянули на данные и заметили, что пропавшие символы были равномерно распределены по тексту. При измерении интервалов оказалось, что расстояние между пропавшими буквами было равно 1023 байтам — подозрительно круглое значение. Поиск в исходном тексте редактора нашел несколько кандидатов — чисел в районе 1024. Одно из этих чисел находилось в новом коде, поэтому мы исследовали именно его и немедленно обнаружили классическую "ошибку на единицу", где нулевой байт перезаписывал последний символ в 1024-байтовом буфере.

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

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

Отображайте сообщения в компактной фиксированной форме, чтобы их можно было легко просматривать глазами или с помощью программ типа дгер. (Такие программы просто бесценны при поиске текста. В девятой главе приведена простая реализация такой программы.) Если вы отображаете значение переменных, форматируйте их одинаково. В С и C++ показывайте указатели в виде шестнадцатеричных чисел, например %х или %р; это поможет вам увидеть, равны ли два указателя, взаимосвязаны ли они. Научитесь читать значения указателей и распознавать возможные и невозможные значения, например ноль, отрицательные или нечетные числа, а также маленькие числа. Хорошее знакомство с видами адресов поможет также при использовании отладчика.

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

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

Мы сделали так, что check вызывает a bo rt, стандартную функцию библиотеки языка С, которая приводит к аварийному завершению работы программы, чтобы затем можно было проанализировать ее с отладчиком. В каком-нибудь другом случае можно просто продолжить выполнение.

Теперь добавьте вызовы функции check везде, где она может быть полезна:



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

В более запутанных случаях функция check может проводить проверку и отображать структуры данных. Этот подход можно обобщить, используя процедуры, проводящие постоянную проверку целостности структур данных и другой информации. В программе со сложными структурами данных полезно написать такие проверки, поместив их в саму программу до того, как возникнут какие-нибудь проблемы, чтобы их можно было просто включить в случае чего. Используйте их не только для отладки; пусть они будут включ'ены на всех стадиях разработки программы. Если они не сильно влияют на производительность, будет разумно оставить их включенными навсегда. Большие программы типа систем телефонной коммутации часто отводят значительные куски кода "аудитным" подсистемам, которые регулярно анализируют информацию и оборудование, сообщают о встреченных ошибках или даже исправляют их.

Ведите журнальный файл. Другая тактика — ведение журнального файла (log file), содержащего отладочную выдачу фиксированного формата. Когда случается "падение", журнал хранит записи, показывающие, что случилось непосредственно перед этим, web-серверы и другие сетевые программы ведут обширные журналы учета трафика, чтобы собирать информацию о клиентах и о работе программы. Вот такой фрагмент журнального файла можно было встретить на одной из наших машин:



Убедитесь, что вы сбрасываете буферы ввода-вывода, чтобы последние сообщения остались в журнальном файле. Функции вывода типа printf обычно буферизуют выводимые данные, чтобы делать вывод более эффективным; аварийное завершение приведет к потере этих буферизованных данных. В языке С вызов функции fflush гарантирует, что все выводимые данные будут записаны до внезапного завершения программы; в C++ и Java существуют аналогичные функции для выходных потоков. Если вы хотите избежать лишней работы, используйте для журнальных файлов небуферизованный ввод-вывод. Стандартные функции setbuf и setvbuf управляют буферизацией; setbuf (fp, NULL) отключает буферизацию потока fp. Стандартные потоки сообщений об ошибке (stderr, cerr, System, err) обычно небуферизованы.


Постройте график. Иногда, при тестировании и отладке, картинки эффективнее, чем текст. Как мы увидели во второй главе, картинки особенно полезны для понимания структур данных и, конечно же, при написании программ работы с графикой, но они также могут использоваться для любых программ. Диаграммы разброса данных демонстрируют неверные значения гораздо лучше, чем столбцы чисел. Гистограммы отражают странные места в экзаменационных оценках, случайных числах, размерах "корзин" операторов захвата памяти и хэш-таблиц и т. п.

Если вы не понимаете, что происходит в вашей программе, попробуйте собрать статистику о структуре данных в ней и представить результаты графически. На приводимых графиках изображена статистика цепочек в программе markov из главы 3: по оси х показана длина цепочек, а по оси у — количество элементов в цепочках этой длины. Входные данные — наш стандартный текст, Псалмы (42 685 слов, 22 482 префикса). Первые два графика соответствуют хорошим мультипликаторам, 31 и 37, а третий — кошмарному мультипликатору 128. В первых двух случаях нет ни одной цепочки длиною больше 15 или 16, а большинство элементов хранится в цепочках из 5 или 6 элементов. В третьем случае область распределения много больше, самая длинная цепочка содержит 187 элементов, а в цепочках длиною больше 20 содержатся тысячи элементов.


Используйте различные инструменты. Используйте возможности среды, в которой ведете отладку. Например, программа сравнения файлов, вроде (Jiff, может сравнить результаты успешного и неуспешного запусков, чтобы вы сфокусировали внимание на том, что именно изменилось. Если отладочная выдача очень длинна, используйте g rер для поиска в ней или текстовый редактор для ее исследования. Боритесь с желанием отправить отладочную выдачу на принтер: компьютеры обрабатывают объемистые данные гораздо лучше людей. Используйте языки скриптов и другие средства для автоматизации обработки вывода при отладочных запусках.

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



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

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


Последняя надежда

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

Иногда источник непонимания очень прост: неверный приоритет операторов, неверный оператор, выравнивание, не соответствующее действительной структуре программы, или же ошибка области видимости, когда локальная переменная прячет под собой глобальную или же глобальная переменная вторгается в локальную область видимости. Например, программисты часто забывают, что & и | имеют меньший приоритет, чем == и ! =. Они пишут так:

 ?if (х & 1 == 0)

? ....

и не могут понять- почему результат этого выражения — всегда "ложь". Иногда неверное движение пальца при наборе превращает одиночный символ = в двойной и наоборот:



Или после редактирования случайно остается лишний код:

 ? for (i=0; i < n; i++); 

? a[i++] = 0;

Или проблему создает спешка при наборе текста кода:



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

 memset(p, n, 0); /* записать п нулей в р */?

вместо

memset(p, 0, п); /* записать n нулей в р */


то транслятор такой ошибки не обнаружит.

Иногда незаметно/для вас что-то изменяется, например глобальные или общие переменные, а вы об этом ничего не знаете, пока какая-нибудь функция не обратится к ним.

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



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

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

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

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

Крайне редко проблема действительно заключается в компиляторе, библиотеке, операционной системе или даже в "железе", особенно если что-нибудь изменилось в конфигурации непосредственно перед тем, как появилась ошибка. Никогда нельзя сразу начинать винить все перечисленное, но если все остальные причины устранены, то можно начать думать в этом направлении. Однажды мы переносили большую программу форматирования текста из Unix-среды на PC. Программа отлично ском-пилировалась, но вела себя очень странно: теряла почти каждый второй символ входного текста. Нашей первой мыслью было, что это как-то связано с использованием 16-битовых целых вместо 32-битовых или, может быть, с другим порядком байтов в слове. Печатая символы, полученные во входном потоке, мы наконец нашли ошибку в стандартном заголовочном файле ctype.h, поставлявшемся вместе с компилятором. В этом файле функция isprint была реализована в виде макроса:

? «define isprint(c) ((с) >= 040 && (с) < 0177)

а в главном цикле было написано так:

 while (isprint(c = getchar()))

Каждый раз, когда входной символ был пробелом (восьмеричное 040, плохой способ записи ' ') или стоял в кодировке еще дальше, а это почти всегда так, функция getchar вызывалась еще раз, потому что макрос вычислял свой аргумент дважды, и первый входной символ пропадал. Исходный код был не столь чистым, как следовало бы, — слишком сложное условие цикла, — но заголовочный файл был непростительно неверен.

Сейчас все еще можно встретиться с такой проблемой: вот этот макрос можно найти в заголовочных файлах одного современного производителя:

 ? Odefine__iscsym(c) (isalrujm(c) |[ ((с) == ' „'))

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

Иногда отказывает само "железо". Ошибка в вычислениях с плавающей точкой в процессоре Pentium в 1994 году, которая приводила к неверным ответам при некоторых'вычислениях, была обширно освещена в печати и довольно дорого обошлась. После того как она была обнаружена, ее, конечно же, мржно было легко воспроизвести. Одна из самых странных ошибок, которую мы когда-либо видели, содержалась в программе-калькуляторе, некогда работавшем на двухпроцессорной машине. Иногда выражение 1/2 выдавало результат 0. 5, а иногда — постоянно появляющееся, но совершенно неправильное значение 0.7432; никаких закономерностей в появлении правильного или неправильного значений не было. В конце концов проблему обнаружили в модуле вычислений с плавающей точкой в одном из процессоров. Программа-калькулятор случайным образом выполнялась то на одном из них, то на другом, и в зависимости от этого ответы были либо верными, либо совершенно бессмысленными.

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


Невоспроизводимые ошибки

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

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

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

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



К тому моменту, когда указатель, возвращаемый функцией msg, используется, он уже не указывает на осмысленное место. Память нужно выделять с помощью функции malloc, использовать массив, объявленный как static, или требовать предоставления памяти вызывающей программой.

Использование динамически выделяемого значения после того, как оно было освобождено, имеет подобные симптомы. Мы уже упоминали об этом во второй главе, когда написали функцию f reeall. Вот этот код — неверен:

 ?for (р = listp; р != NULL; р = p->next)

? free(p);

После того как память была освобождена, она не должна использоваться, потому что ее содержимое могло измениться и нет гарантии, что p->next все еще указывает на правильное значение.

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

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

Упражнение 5-1

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


Средства отладки

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

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

Программа st rings полезна и для нахождения текста в других двоичных файлах. Файлы с изображениями часто содержат ASCII-строки, сообщающие, какая программа создала этот файл, а сжатые файлы и архивы (например, zip-файлы) могут содержать имена файлов: strings обнаружит и их.

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

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

 % strings *.ехе *.dll | grep 'mystery message'

Функция st rings читает файл и печатает каждую последовательность из как минимум MINLEN = 6 печатных символов.


Форматная строка %. *s в функции printf берет длину строки из следующего аргумента (i), потому что buf не завершается нулем.

Цикл do-whi|le находит и печатает каждую строку, заканчивая работу при обнаружении EOF. Проверка конца файла после тела цикла позволяет функции getc и циклу по строке иметь одинаковое условие завершения, а также с\ помощью единственного обращения к printf обрабатывать конец строки, конец файла и слишком длинные строки.

Стандартный внешний цикл с проверкой при входе или единственный цикл с getc и более сложным телом заставил бы использовать printf дважды. Эта функция сначала так и работала, но потом мы нашли ошибку в операторе printf. Исправив в одном месте, мы забыли исправить ее в двух других. ("А не делал ли я ту же самую ошибку где-нибудь еще?") Здесь нам стало ясно, что программу нужно переписать, чтобы дублирующегося кода было меньше; так появился цикл do-while.

Основная процедура программы strings вызывает функцию strings для каждого файла- аргумента:


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

Очевидный тест программы st rings — пропустить ее через саму себя. Это сработало отлично под Unix, но под Windows 95 команда

 С:\> strings <strings.exe

выдала ровно пять строк:

IThis program cannot be run in DOS mode.
 '. rdata
@.data
 .idata
 .reloc

Первая строка "!Эта программа не может исполняться под DOS" выглядела как сообщение об ошибке, и мы потеряли некоторое время, пока не I поняли, что это на самом деле строка из файла с программой, так что результат был правилен, по крайней мере до какого-то момента. Не секрет, что некоторые отладочные сессии терпели крушение из-за неверного понимания источника сообщения.

Но в любом случае должны быть еще строки! Где они? Однажды поздно ночью наконец забрезжил свет. ("Я где-то уже видел это!") Это — проблема с переносимостью, описанная подробнее в восьмой главе. Изначально мы написали программу так, чтобы она читала только из стандартного ввода, используя функцию getchar. Под Windows, однако, getchar возвращает EOF, когда она встречает определенный байт (0x1 А или Control-Z) в текстовом режиме ввода,4 и именно это и приводило к преждевременному завершению.

Это абсолютно законное поведение, но совсем не то, что ожидали мы, с нашим опытом работы с Unix. Было решено открывать файл в двоичном режиме, используя "rb". Но stdin уже открыт, а стандартного способа изменить режим его работы не существует. (Можно использовать функции fdopen или setmode, но они не являются частью стандарта.) Таким образом, мы столкнулись с набором неприятных альтернатив: заставить пользователя всегда задавать имя файла, чтобы программа работала под Windows за счет неудобства для пользователей Unix; без пред-] упреждения выдавать неправильный ответ, если пользователь Windows пытается задействовать стандартный ввод; использовать условную компиляцию, чтобы адаптировать поведение к различным системам ценой пониженной переносимости. Мы выбрали первый вариант, чтобы программа везде работала одинаково.

Упражнение 5-2

Программа strings печатает строки длиной MINLEN или более символов, и иногда при этом обнаруживается гораздо больше строк, чем надо. Реализуйте необязательный аргумент, устанавливающий минимальную длину строки.


Упражнение 5-3

Напишите программу vis, которая копирует стандартный ввод на стандартный вывод, отображая непечатаемые символы типа "забоя", контрольных символов и не-АЗСП-символов в виде\Хпп, где hh — шест-надцатеричное представление непечатаемого байта. В отличие от st ri ngs программа vis полезна при обработке файлов, содержащих лишь несколько непечатаемых символов.

Упражнение 5-4

Что выдает vis, если во входном потоке попадается строка \ХОА? Можете ли вы устранить двусмысленность результатов работы этой программы?

Упражнение 5-5

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


Чужие ошибки

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

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

Здесь очень сильно могут помочь инструментальные средства. Программы текстового поиска типа g rep помогут найти все места использования какого-нибудь имени. Перекрестные ссылки дают определенное представление о структуре программы. Граф, показывающий взаимные вызовы функций, ценен, если только он не очень велик. Пошаговый проход по программе с помощью отладчика поможет увидеть последовательность событий. Из истории ревизий программы можно узнать, что происходило в ней с течением времени. Частые изменения являются знаком того, что код был плохо понят или подвергался частой смене требований и поэтому потенциально содержит ошибки.

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

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

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

? i = -1; printfO

? i » 1);

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

Убедитесь, что ошибка не нова. Используете ли вы последнюю версию программы. Есть ли список исправленных в ней ошибок? Большая часть программного обеспечения проходит серию выпусков; если вы нашли ошибку в версии 4.0Ы, она может быть уже исправлена или заменена новой в версии 4.0Ь2. В любом случае немногие программисты испытывают достаточно энтузиазма, чтобы исправлять ошибки где-либо, кроме текущей версии программы.

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


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



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


Заключение

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

После того как вы увидите ошибку, первое, что нужно сделать, — понять, на что "намекает" эта ошибка. Откуда она могла взяться? Есть ли в ней что-нибудь знакомое? Не менялось ли что-нибудь в программе буквально только что? Есть ли какие-нибудь особенности у входных ? данных, которые привели к ошибке? Нескольких хорошо отобранных тестовых случаев и нескольких операторов печати в коде может быть достаточно.

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

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

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


Дополнительная литература

Много полезных советов по отладке содержится в книгах Стива Ма-гьюира "Создание надежного,кода" (Steve Maguire. Writing Solid Code. Microsoft Press, 1993) и Стива Мак-Коннелла "Все о коде" (Steve McConnell. Code Complete. Microsoft Press, 1993).