Автор Тема: Найдите ошибку, если она есть.  (Прочитано 33802 раз)

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #15 : Сентябрь 15, 2016, 05:26:51 pm »
ну так чо, правильный ответ или как? ))
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #16 : Сентябрь 15, 2016, 05:30:33 pm »
Ну как минимум вот в этой строке:
int x = s[i] - '0';у тебя x становится отрицательной, когда i становится равной 2 и из строки s ты считываешь терминатор строки (число ноль).
Далее в строке:
if (tr[v].mp[x] == 0)у тебя происходит обращение к элементу массива mp с отрицательным индексом, это, видимо, и приводит к падению программы.

Не показывай такой говнокод своему работодателю -- он будет обязан уволить тебя )))

ЗЫ. Накапай работодатюлю своих знакомых -- пусть их уволят )))

Нет, дело не в этом. Не становится там индекс отрицательным.
Y = λf.(λx.f (x x)) (λx.f (x x))

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #17 : Сентябрь 15, 2016, 06:24:13 pm »
Короче, непонятно, чего она падает на выходе из третьего захода в процедуру add, вроде предпосылок для этого нет...
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #18 : Сентябрь 15, 2016, 06:53:10 pm »
Короче, непонятно, чего она падает на выходе из третьего захода в процедуру add, вроде предпосылок для этого нет...

Нишмагла :-)
Y = λf.(λx.f (x x)) (λx.f (x x))

Geniepro

  • Hero Member
  • *****
  • Сообщений: 1955
  • Знайте- истина в том, что повторено трижды подряд!
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #19 : Сентябрь 15, 2016, 07:50:50 pm »
Короче, непонятно, чего она падает на выходе из третьего захода в процедуру add, вроде предпосылок для этого нет...

Нишмагла :-)
А нинада отлаживать какую-то хрень, у которой даже ТЗ нету )))
to iterate is human, to recurse, divine

Салат «рекурсия»: помидоры, огурцы, салат…

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #20 : Сентябрь 15, 2016, 08:44:04 pm »
Короче, непонятно, чего она падает на выходе из третьего захода в процедуру add, вроде предпосылок для этого нет...

Нишмагла :-)
А нинада отлаживать какую-то хрень, у которой даже ТЗ нету )))

ТЗ есть, но оно тут не важно. Не привожу его, чтобы просто не отвлекать на всякие глупости.
Y = λf.(λx.f (x x)) (λx.f (x x))

Romiras

  • Sr. Member
  • ****
  • Сообщений: 264
    • Просмотр профиля
    • Romiras Dev Lab
Re: Найдите ошибку, если она есть.
« Ответ #21 : Сентябрь 24, 2016, 08:23:00 pm »
У кого есть PVS-Studio? Прогоните на нём.

kemiisto

  • Jr. Member
  • **
  • Сообщений: 64
    • Просмотр профиля
    • kemiisto.ru
Re: Найдите ошибку, если она есть.
« Ответ #22 : Сентябрь 26, 2016, 11:10:34 am »
У кого есть PVS-Studio? Прогоните на нём.
А то мы не догадались...  ;)  Ничего.

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #23 : Сентябрь 26, 2016, 03:34:31 pm »
У кого есть PVS-Studio? Прогоните на нём.
А то мы не догадались...  ;)  Ничего.

:-)

У меня, заняло около часа разобраться что там и как, после того, как попросили помочь. Программа естественно не моя, и к ней я отношения не имею.
Y = λf.(λx.f (x x)) (λx.f (x x))

Romiras

  • Sr. Member
  • ****
  • Сообщений: 264
    • Просмотр профиля
    • Romiras Dev Lab
Re: Найдите ошибку, если она есть.
« Ответ #24 : Сентябрь 26, 2016, 10:40:29 pm »
Переведи на Оберон - сразу станет ясно где ошибка.  ;)

ilovb

  • Hero Member
  • *****
  • Сообщений: 2538
  • just another nazi test
    • Просмотр профиля
    • Oberon systems
Re: Найдите ошибку, если она есть.
« Ответ #25 : Сентябрь 27, 2016, 10:49:05 pm »
Как же мерзко выглядят плюсы...

Не шарю, но может тут обрезается чего при большом size()?:
if (i == static_cast<int>(s.size()))ну и зацикливание происходит...

зы Будто в канализацию нырнул :D

kkkk

  • Full Member
  • ***
  • Сообщений: 135
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #26 : Сентябрь 28, 2016, 09:54:53 am »
Решил глянуть на этот код.
Собрал "g++-5 -std=gnu++11 -g", запустил. Программа нормально завершилась выдав:
go 1 0
in 0 1 0 2
go in
1 0
go 2 1
2 0
go out
in 0 2 1 2
go in
2 0
go 3 2
3 0
go out
in 0 3 2 2
Я что-то упустил из виду?
Собрал по-другому - "g++ -std=c++11 -g -fsanitize=address -fsanitize=undefined" . Запустил - теперь она грохнулась на использовании освобождённой памяти
go 1 0
in 0 1 0 2
go in
1 0
go 2 1
=================================================================
==5542==ERROR: AddressSanitizer: heap-use-after-free on address 0x60200000eff0 at pc 0x000000402abf bp 0x7fff0f67c930 sp 0x7fff0f67c920
WRITE of size 4 at 0x60200000eff0 thread T0
    #0 0x402abe in add(int, int, int) /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:36
    #1 0x40301a in main /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:47
    #2 0x7f3bee08082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
    #3 0x4018c8 in _start (/home/konstantin/projects/github/bubble_test/cpp-strange-error/a.out+0x4018c8)

0x60200000eff0 is located 0 bytes inside of 12-byte region [0x60200000eff0,0x60200000effc)
freed by thread T0 here:
    #0 0x7f3bef767b2a in operator delete(void*) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99b2a)
    #1 0x404a5b in __gnu_cxx::new_allocator<bor>::deallocate(bor*, unsigned long) /usr/include/c++/5/ext/new_allocator.h:110
    #2 0x4044bb in std::allocator_traits<std::allocator<bor> >::deallocate(std::allocator<bor>&, bor*, unsigned long) /usr/include/c++/5/bits/alloc_traits.h:517
    #3 0x403ce2 in std::_Vector_base<bor, std::allocator<bor> >::_M_deallocate(bor*, unsigned long) /usr/include/c++/5/bits/stl_vector.h:178
    #4 0x4041f2 in void std::vector<bor, std::allocator<bor> >::_M_emplace_back_aux<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:438
    #5 0x403b35 in void std::vector<bor, std::allocator<bor> >::emplace_back<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:101
    #6 0x403498 in std::vector<bor, std::allocator<bor> >::push_back(bor&&) /usr/include/c++/5/bits/stl_vector.h:932
    #7 0x401a62 in go() /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:16
    #8 0x402a5e in add(int, int, int) /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:36
    #9 0x40301a in main /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:47
    #10 0x7f3bee08082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

previously allocated by thread T0 here:
    #0 0x7f3bef767532 in operator new(unsigned long) (/usr/lib/x86_64-linux-gnu/libasan.so.2+0x99532)
    #1 0x404d73 in __gnu_cxx::new_allocator<bor>::allocate(unsigned long, void const*) /usr/include/c++/5/ext/new_allocator.h:104
    #2 0x404c03 in std::allocator_traits<std::allocator<bor> >::allocate(std::allocator<bor>&, unsigned long) /usr/include/c++/5/bits/alloc_traits.h:491
    #3 0x404920 in std::_Vector_base<bor, std::allocator<bor> >::_M_allocate(unsigned long) /usr/include/c++/5/bits/stl_vector.h:170
    #4 0x403e0a in void std::vector<bor, std::allocator<bor> >::_M_emplace_back_aux<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:412
    #5 0x403b35 in void std::vector<bor, std::allocator<bor> >::emplace_back<bor>(bor&&) /usr/include/c++/5/bits/vector.tcc:101
    #6 0x403498 in std::vector<bor, std::allocator<bor> >::push_back(bor&&) /usr/include/c++/5/bits/stl_vector.h:932
    #7 0x401a62 in go() /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:16
    #8 0x402ff7 in main /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:45
    #9 0x7f3bee08082f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)

SUMMARY: AddressSanitizer: heap-use-after-free /home/konstantin/projects/github/bubble_test/cpp-strange-error/mistake.cpp:36 add(int, int, int)
Shadow bytes around the buggy address:
  0x0c047fff9da0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9db0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9dc0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9dd0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9de0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
=>0x0c047fff9df0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa[fd]fd
  0x0c047fff9e00: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e10: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e20: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e30: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff9e40: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07
  Heap left redzone:       fa
  Heap right redzone:      fb
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack partial redzone:   f4
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
==5542==ABORTING
Похоже, такое действительно не во всех языках возможно. Налицо избыточная сложность "универсального хорошо отлаженного" решения,  и поэтому трудно понять, что оно там внутри делает. По-моему, тут не с ошибкой надо разбираться, а навелосипедить более простое, хотя и более объёмное решение.

« Последнее редактирование: Сентябрь 28, 2016, 09:57:49 am от kkkk »

kkkk

  • Full Member
  • ***
  • Сообщений: 135
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #27 : Сентябрь 28, 2016, 11:14:57 am »
tr[v].mp[x] = go();
Очевидная проблема в этом месте, так как go() изменяет tr.
Если изменить на
int tmp = go();
tr[v].mp[x] = tmp;
То всё нормально. Да, проблема в плохом понимании работы универсальных решений. И в наличии состояния, конечно  :D

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #28 : Сентябрь 28, 2016, 11:16:25 am »
Не шарю, но может тут обрезается чего при большом size()?:
if (i == static_cast<int>(s.size()))ну и зацикливание происходит...
Неа.

Как же мерзко выглядят плюсы...
...
зы Будто в канализацию нырнул :D
Тут сам код выглядит относительно мерзко, ибо писался очень быстро (час-два), на скорость. При этом сама задача не сказать чтобы совсем тривиальная.

А придирки к языку на уровне {} VS begin/end, == VS =, := VS = and so on - не принимаются :-)
Y = λf.(λx.f (x x)) (λx.f (x x))

valexey_u

  • Hero Member
  • *****
  • Сообщений: 3013
    • Просмотр профиля
Re: Найдите ошибку, если она есть.
« Ответ #29 : Сентябрь 28, 2016, 11:23:14 am »
tr[v].mp[x] = go();
Очевидная проблема в этом месте, так как go() изменяет tr.
Если изменить на
int tmp = go();
tr[v].mp[x] = tmp;
То всё нормально. Да, проблема в плохом понимании работы универсальных решений. И в наличии состояния, конечно  :D

Бинго! :-)

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

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

Теперь осталось ответить на второй вопрос - на вашем любимом ЯП возможна ли подобная ошибка?
Y = λf.(λx.f (x x)) (λx.f (x x))