Выход за пределы стринга

Модераторы: Duncon, Naeel Maqsudov, Хыиуду, Игорь Акопян

Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 17:14
Откуда: 71 RUS
Контактная информация:

09 мар 2007, 10:13

Уважаемые участники форума. Не так давно имел место спор
http://forum.developing.ru/showthread.php?t=8529&page=2
является ли код

Код: Выделить всё

for i := length(s) downto 1 do
	if s[i]=s[i+1] then
		delete(s,i,1);
работоспоспособным, т.е. работающим правильно (а именно, код удаляет идущие вподряд одинаковые буквы) в любых случаях при длине стринга более 1.
Из кода явно видно, что происходит обращение к элементу строки за ее пределами (s[i+1]). В разрезе доступа к ячейке памяти - никакой ошибки нет, но если S будет менятся (например, обрабатываются строки текстового файла) может возникнуть ситуация, что s[i+1] в первом проходе подцепит символ, который принадлежал предыдущему значению. Следовательно код будет работать неверно.
Просьба помочь и рассудить данный спор комментариями и объяснениями. Надеюсь, этот пример послужит уроком для многих начинающих программистов и объяснит почему не следует выходить за рамки выделенной памяти, даже в языках высокого уровня.
It's a long way to the top if you wanna rock'n'roll
BBB
Сообщения: 1272
Зарегистрирован: 27 дек 2005, 13:37

09 мар 2007, 10:50

somewhere, тут еще может иметь место следующий краевой эффект.

Если речь идет о Паскале, то там, как известно, SizeOf (Stirng) равен 256: 255 байт на символы строки плюс дополнительный символ, где хранится текущая длина строки.

Так вот, возможна ситуация (тот самый "краевой эффект"), когда строка s "забита под завязку", то есть имеет максимально возможную текущую длину (255)

Тогда в этом частоном случае вышеприведенный код при первом проходе цикла оператор в теле цикла "примет вид":

Код: Выделить всё

if s[255]=s[256] then
  delete(s,256,1);
То есть, будет иметь место не только выход за пределы текущей длины строки, но и вообще на пределы данной переменной.
И, если попытку чтения (s[256]) среда как-то еще и переживет, то что произойдет при
попытке выполнить оператор delete(s,256,1), сказать затрудняюсь.
Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 17:14
Откуда: 71 RUS
Контактная информация:

09 мар 2007, 10:59

&quot писал(а):выполнить оператор delete(s,256,1), сказать затрудняюсь
Все-таки delete(s, 255, 1) - т.к. Delete(s, i, 1), i = 255.
При таком раскладе, если в следующей переменной за S по каким-то причинам первый байт = ord(s[255]) - результат: потеря буквы
It's a long way to the top if you wanna rock'n'roll
BBB
Сообщения: 1272
Зарегистрирован: 27 дек 2005, 13:37

09 мар 2007, 11:15

somewhere писал(а):Все-таки delete(s, 255, 1) - т.к. Delete(s, i, 1), i = 255.
Ну да, тут я чуть спутал :) Но принципиально "эффект" выхода вообще за пределы данной строковой переменной все равно остается.
Аватара пользователя
Игорь Акопян
Сообщения: 1419
Зарегистрирован: 13 окт 2004, 17:11
Откуда: СПБ
Контактная информация:

11 мар 2007, 18:40

somewhere, категорически согласен, ибо нельзя применять заведомо неверные решения для конкретной задачи. Всё это шаблоны - кто-то в следующий раз возьмёт этот код для другой задачи и будет долго искать ошибку
Изображение
Аватара пользователя
Duncon
Сообщения: 1974
Зарегистрирован: 10 окт 2004, 14:11
Откуда: Питер
Контактная информация:

11 мар 2007, 21:12

Вообще-то компелятор не допустит выхода за пределы, но я бы не напрягался ибо эта проверка не даст результата (if s=s[i+1] then) равенство не будет true и круг пропустится, здесь вопрос чему равна s[i+1] - чисто теоритический интерес..
Жаль сей час Delphi 2006 не стоит, там если остоновить круг (поставить красную точку F5) будут отображены переменные на данный момент в заданной точке, кому не лень гляньте..
Хыиуду
Сообщения: 2388
Зарегистрирован: 06 мар 2005, 21:03
Откуда: Москва
Контактная информация:

12 мар 2007, 10:13

Глянул. После изменения длины строки в меньшую сторону Дельфи 7.0 автоматически забивает освободившееся место нулями. Так что на Дельфи вариант Максима скорее всего будет работать корректно. Однако полагаться на это в других средах программирования я бы не рискнул.
Искусство программирования - заставить компьютер делать все то, что вам делать лень.
Для "спасибо" есть кнопка "Спасибо" в виде звездочки внизу под ником автора поста.
BBB
Сообщения: 1272
Зарегистрирован: 27 дек 2005, 13:37

12 мар 2007, 11:00

Duncon писал(а):Вообще-то компилятор не допустит выхода за пределы,
Каким это, интересно, образом????
По-моему, компилятор ругнется, если попытаться индекстом массива написать КОНСТАНТУ (или констатное выражение), значение которой выходит за диапазон.
Вот во время выполнения МОЖЕТ случиться run-time error "Range check error", в слуае, если установлена соответствующая опция компилятора.
...но я бы не напрягался ибо эта проверка не даст результата (if s=s[i+1] then) равенство не будет true..
Здесь уже приводился пример (для Паскаля), когда это условие даст TRUE.
Аватара пользователя
somewhere
Сообщения: 1837
Зарегистрирован: 31 авг 2006, 17:14
Откуда: 71 RUS
Контактная информация:

12 мар 2007, 13:36

&quot писал(а):Глянул. После изменения длины строки в меньшую сторону Дельфи 7.0 автоматически забивает освободившееся место нулями.
ничего подобного

Код: Выделить всё

s := 'abcde';
s := 'abcd';
при отладке имеем

Код: Выделить всё

lea eax, [ebp+04] - загружаем ссылку на строку
mov edx, 0040EEF7 - новая ссылка, на 'abcd'
call LStrLDt - вызов процедуры присваивания стрингу константы, фактически меняет ссылку по адресу [ebp+04] (на стеке которая, локальная переменная) на новую с учетом проверок на длину и т.д.
Как видим, никаких забиваний 0-ей. Нуль после последнего символа - вопрос совместимости с null-terminated strings - хотя перед стрингом в памяти стоит 4-байта его длины. Это так, для справки. При доступе к s[5] - действительно 0, далее смотрим что дальше после s[5], а лучше всю строку:
'a', 'b', 'c', 'd', #0, 'r', '3', '2', '.', 'd', 'l', 'l', ' ', 'k', 'e', 'r', 'n' ... - дальше стоит продолжать?
По-сему не надо надеятся что там авось пусто, авось там #0 и т.д. Дали вам память, будте добры использовать именно ее.
It's a long way to the top if you wanna rock'n'roll
Аватара пользователя
Колядин Максим
Сообщения: 285
Зарегистрирован: 16 ноя 2006, 19:09
Откуда: Seattle, WA
Контактная информация:

12 мар 2007, 15:00

somewhere, для задачи с которой и началась вся эта "заморуха" (вот её ссылка http://forum.developing.ru/showthread.php?t=8529&page=1 ) мой вариант работает безотказно, согласись с этим. Но только для этой задачи, не более того. Если же судить, как судите вы: а вот если два раза стрингу значение присвоить, а вот если этот пример будут использовать как шаблон - конечно, мой вариант здесь неуместен. Когда я писал код, я рассчитывал только на поставленную задачу. Ты же, somewhere, протестовал, сказав, что этот вариант к ней не подходит.
Хватит вам уже обсуждать этот вопрос, лично я уже итак всё понял. Если быть чересчур правильным, то ты прав, но если же быть не слишком правильным, но предельно лаконичным - я.
Программист - это человек, который решает способом, который вы не понимаете, проблемы, о которых вы даже не подозревали...
Ответить