интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.
берем простой пример:

void f(){
   f();
}

int main()
{
    f();
    return 0;
}

компилим, запускаем: "segmentation fault: 11 (core dumped)".
stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть, введя директиву для установления максимальной глубины вызовов, плюс прицепить вызов а-ля abort() при превышении этого значения.
или же создатели С/C++ руководствовались правилом "если вы хотите выстрелить себе в ногу, окей, мы не будем вам в этом мешать"? (вольный пересказ известного крылатого высказывания).
спрашиваю из чистого любопытства. спасибо за инфу.

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.
V>берем простой пример:

Я не хочу платить за то что не заказывал.

V>компилим, запускаем: "segmentation fault: 11 (core dumped)".
V>stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть, введя директиву для установления максимальной глубины вызовов, плюс прицепить вызов а-ля abort() при превышении этого значения.
V>или же создатели С/C++ руководствовались правилом "если вы хотите выстрелить себе в ногу, окей, мы не будем вам в этом мешать"? (вольный пересказ известного крылатого высказывания).
V>спрашиваю из чистого любопытства. спасибо за инфу.

А быть может другой код этой программы следит за тем когда (например от windows) придет очередной pagefault для стека и что-нибудь сделает.

Как ты думаешь должен ли компилятор ограничивать такой код:

char* ptr = NULL;
ptr[0] = 0xEB
...

В определенных условиях этот код правильный.

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.

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

з.ы. для тривиальных случаев, как в примере, хороший компилятор (msvc) выдаст варнинг во время компиляции.

Здравствуйте, remark, Вы писали:

R>Во-вторых, невозможно определять глубину рекурсии (полный статический анализ невозможен сразу по ряду серьёзных причин).
в других языках ведь она присутствует.
R>В-третих, она определяется (ты сам получил уведомление о детектировании бесконечной рекурсии).
если считать что уведомление == "segmentation fault (core dumped)", то да, получил.
R>з.ы. для тривиальных случаев, как в примере, хороший компилятор (msvc) выдаст варнинг во время компиляции.
ясно дело, что должен выдать. видимо, gcc 4.2.1 плохой варнингов не выдал, даже будучи вызван с "-Wall"

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.

Потому что в С/С++ неопределённое поведение реализуется самым дешёвым из доступных способов

V>stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть, введя директиву для установления максимальной глубины вызовов, плюс прицепить вызов а-ля abort() при превышении этого значения.

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

void foo()
{
    if(.....)
        foo();
}

void bar()
{
    int local_data[1000];
    if(.....)
        bar();
}

Предельное количество вызовов до исчерпания стека различается, навскидку, в 500 раз (обычно кадр стека отъедает 2*sizeof(intptr_t)).

Далее, размер стека варьируется в широких пределах: каждому потоку выделяется свой стек, необязательно с дефолтным размером.
А на архитектурах со стеком в виде списка блоков (смолток-машины, лисп-машины) стек принципиально не отличается от динамической памяти. Ты же не требуешь ограничение максимального количества вызовов new?
Впрочем, с динамической памятью всё просто — метнётся исключение. А со стеком — бабахнет, и дело с концом.

Практически же, мы стараемся не допускать рекурсию с асимптотикой глубины >= O(n), если количество операций n неограничено или заведомо велико.
Да и O(n^0.5) я бы побоялся...
То есть, в учебных целях оббежать дерево или массив рекурсивно — можно, но на практике это самоубийство. Вдруг огромное дерево выродится в список?
Просто используются другие алгоритмы; хвостовая рекурсия преобразуется в итерации (руками или компилятором, если у него хватит ума).

Здравствуйте, varnie, Вы писали:

R>>Во-вторых, невозможно определять глубину рекурсии (полный статический анализ невозможен сразу по ряду серьёзных причин).
V>в других языках ведь она присутствует.

Языки в студию?

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

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, varnie, Вы писали:

R>>>Во-вторых, невозможно определять глубину рекурсии (полный статический анализ невозможен сразу по ряду серьёзных причин).
V>>в других языках ведь она присутствует.

К>Языки в студию?
скажем, в Питоне у нас имеется:

sys.setrecursionlimit

setrecursionlimit( limit)

Set the maximum depth of the Python interpreter stack to limit. This limit prevents infinite recursion from causing an overflow of the C stack and crashing Python.

The highest possible limit is platform-dependent. A user may need to set the limit higher when she has a program that requires deep recursion and a platform that supports a higher limit. This should be done with care, because a too-high limit can lead to a crash.

собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

V>компилим, запускаем: "segmentation fault: 11 (core dumped)".
это и есть ограничение

Здравствуйте, varnie, Вы писали:

V>собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

У тебя был выход по segmentation fault. Это такая форма abort().
А какой вариант выхода тебе нужен?

Здравствуйте, c-smile, Вы писали:

CS>Здравствуйте, varnie, Вы писали:

V>>собственно, я про что-то подобное применительно к миру С/С++ и осведомлялса изначально.

CS>У тебя был выход по segmentation fault. Это такая форма abort().
CS>А какой вариант выхода тебе нужен?
такой, чтобы я имел возможность его перехватить в самой программе и корректно его отработать.

Здравствуйте, varnie, Вы писали:

V>интересуюсь, почему в языках С/C++ никаким образом не предусмотрено предотвращение бесконечной рекурсии. в инете искал, не нашел инфы.
V>берем простой пример:
V>

V>void f(){
V>   f();
V>}

V>int main()
V>{
V>    f();
V>    return 0;
V>}
V>

V>компилим, запускаем: "segmentation fault: 11 (core dumped)".
V>stack overflow, но разве нельзя было на уровне языка(ов) это предуcмотреть, введя директиву для установления максимальной глубины вызовов, плюс прицепить вызов а-ля abort() при превышении этого значения.
V>или же создатели С/C++ руководствовались правилом "если вы хотите выстрелить себе в ногу, окей, мы не будем вам в этом мешать"? (вольный пересказ известного крылатого высказывания).
V>спрашиваю из чистого любопытства. спасибо за инфу.

напишите

void f()
{
static int cnt=0;
if (cnt++ > maxRecursion) throw(bla-bla);

ваш код

cnt--;
};

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

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

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

Здравствуйте, merk, Вы писали:

M>напишите
//skipped
M>так глубина рекурсии и ловится самым общим образом.
вестимо.
как выше уже заметили, это идеология языка С/C++ — не делать лишних телодвижений походу этим все и объясняется.
в питоне мы используем ф-цию, указанную мной выше, в С/C++ при подобной задаче прибегаем к симуляции подсчета вызовов ф-ций из самой себя, или к чему-то подобному. жаль что С++ не бросает исключения при сабже — все было бы проще ИМХО.
M>компилятор обнаружить беск. рекурсию не может кроме случая безусловного вызова функцией самой себя.
gcc не обнаружил.

V>как выше уже заметили, это идеология языка С/C++ — не делать лишних телодвижений походу этим все и объясняется.
V>в питоне мы используем ф-цию, указанную мной выше, в С/C++ при подобной задаче прибегаем к симуляции подсчета вызовов ф-ций из самой себя, или к чему-то подобному. жаль что С++ не бросает исключения при сабже — все было бы проще ИМХО.
M>>компилятор обнаружить беск. рекурсию не может кроме случая безусловного вызова функцией самой себя.
V>gcc не обнаружил.
Реализация стека и его защиты отдана на откуп операционной системе. Точно так же как обращение к мусорным указателям и прочие проблемы неверного использования платформы, под которой работаетп программа. Т.е. в винде/MSVS в принципе вы можете сделать так:

void trans_func( unsigned int u, EXCEPTION_POINTERS* pExp )
{
    throw (unsigned int)pExp->ExceptionRecord->ExceptionCode;
}

void foo()
{
    volatile char c;
    foo();
}

int main()
{
    _set_se_translator(trans_func);
    try
    {
        foo();
    }
    catch(unsigned int code)
    {
        printf("caught code 0x%x\n", code);
    }

    return 0;
}

Либо так:

int main()
{
    __try
         {
         foo();
         }__except(EXCEPTION_EXECUTE_HANDLER)
         {
         }
         return 0;
}

При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
Кстати конечно ничего особо сильно не мешало разработчикам ОС не вводить такие драконовские меры (убивание) при возникновении AV/stack overflow а например молча возвращать мусорное значение из мусорного указателя... Подуймате на досуге, почему так не было сделано.

Здравствуйте, Аноним, Вы писали:

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

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

А>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.

А>Кстати конечно ничего особо сильно не мешало разработчикам ОС не вводить такие драконовские меры (убивание) при возникновении AV/stack overflow а например молча возвращать мусорное значение из мусорного указателя... Подуймате на досуге, почему так не было сделано.
я лично подумал. я подумал, что это чистый бред, вводящий задачу в совершенно непредсказуемое состояние.

M>это сработала аппаратная защита с выходом за границу сегмента. ос просто привинтила свой обработчик к этому прерыванию. но верно, что именно дело ос определять политику работы приложения, если происходят такие грубые нарушения целостности задачи
stack overflow тоже растет из page fault'а на последней зарезервированной странице стека потока (на обычный платформах).

А>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
Системные функции работают на системном стеке ядреного "лика" потока. Выплюнутая же в юзер мод ntdll!KiUserExceptionDispatcher работает на стеке и в контексте потока в котором собственно произошел обвал, что легко проверить поставив бряку в обработчике исключения. В случае венды, если вы позовете ExitThread оттуда приложение продолжить себе работать, а тред просто тихо уйдет. А 4кб — потому что в случае stack overflow юзермодный обработчик исключения работает на той самой последней странице стека, при guard page exeption на которой ядро поднимает stack overflow. Кстати если потом ваш ESP стек выйдет за границы и этой последней страницы и у вас выпадет какой нить еще системной исключение — KiUserExceptionDispatcher вызван не будет и ядро молча убьет процесс. Просто перед вызовом KiUserExceptionDispatcher ядро проверяет то что ESP юзермодного контекста укладывается между base и limit стека потока, которые записаны в TEB'е. Это собственно и является причиной тому, что процессы в венде от stack overflow обычно тихо дохнут — дефолтовый UnhandledExceptionFilter попросту не укладывается в эти 4 кб.

А>>Кстати конечно ничего особо сильно не мешало разработчикам ОС не вводить такие драконовские меры (убивание) при возникновении AV/stack overflow а например молча возвращать мусорное значение из мусорного указателя... Подуймате на досуге, почему так не было сделано.
M>я лично подумал. я подумал, что это чистый бред, вводящий задачу в совершенно непредсказуемое состояние.
Вот именно. stack overflow тоже.

Здравствуйте, Аноним, Вы писали:

M>>это сработала аппаратная защита с выходом за границу сегмента. ос просто привинтила свой обработчик к этому прерыванию. но верно, что именно дело ос определять политику работы приложения, если происходят такие грубые нарушения целостности задачи
А>stack overflow тоже растет из page fault'а на последней зарезервированной странице стека потока (на обычный платформах).

А>>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
А>Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
я чета слабо уверен, что разговор касается майкрософта
стек при бесконечной рекурсии обвалится в любой уважающей себя ос, и потому курить майкрософта тут не совсем корректно. тут можно даже категорически наплевать на эти тонкости от MS.
в своем высказывании я лишь имел ввиду, что ос не станет пускать тут свои функции на стеке текущего пользовательского треда, просто в силу некоректности такого подхода. так делать, короче, нельзя.

А>Системные функции работают на системном стеке ядреного "лика" потока. Выплюнутая же в юзер мод ntdll!KiUserExceptionDispatcher работает на стеке и в контексте потока в котором собственно произошел обвал, что легко проверить поставив бряку в обработчике исключения.
это уже выход код пользователя, а я говорил о работе кода оси по выпутыванию из ситуации. естессно при уходе в код юзера, ос обязана каким-то образом "добавить" ему стека для работы, и продолжить код текущего треда.

А>>>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>>>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>>>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
А>>Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
M>я чета слабо уверен, что разговор касается майкрософта
M>стек при бесконечной рекурсии обвалится в любой уважающей себя ос, и потому курить майкрософта тут не совсем корректно. тут можно даже категорически наплевать на эти тонкости от MS.
M>в своем высказывании я лишь имел ввиду, что ос не станет пускать тут свои функции на стеке текущего пользовательского треда, просто в силу некоректности такого подхода. так делать, короче, нельзя.
Добропорядочная ОС и так не "пускает свои функции" на пользовательском стеке. В случае венды и линуха у каждого потока есть специальный, ядреный стек. Аж целых 12кб, а иногда даже больше
А stack overflow это ОС-specific исключительнаы ситуация. В случае венды при этом кидается обычный SEH с кодом 0xc00000fd, в случае линуха процессу шлется kill, или как там у них принято... И ловить такие вещи нужно средствами ОС, а лучше — не допускать их возникновения.

А>>Системные функции работают на системном стеке ядреного "лика" потока. Выплюнутая же в юзер мод ntdll!KiUserExceptionDispatcher работает на стеке и в контексте потока в котором собственно произошел обвал, что легко проверить поставив бряку в обработчике исключения.
M>это уже выход код пользователя, а я говорил о работе кода оси по выпутыванию из ситуации. естессно при уходе в код юзера, ос обязана каким-то образом "добавить" ему стека для работы, и продолжить код текущего треда.
О чем спорим тогда? Спать пора...

Кстати вот занятный код:

class SehException
{
public:
    DWORD code;
    PVOID stk_handler, stk_exception, address;

    SehException(EXCEPTION_POINTERS* pExp)
        : code(pExp->ExceptionRecord->ExceptionCode),
        address(pExp->ExceptionRecord->ExceptionAddress)
    {
        stk_handler = (PVOID)&pExp;
        stk_exception = (PVOID)pExp->ContextRecord->Esp;
    }
};

void trans_func( unsigned int u, EXCEPTION_POINTERS* pExp )
{
    throw SehException(pExp);
}


void foo()
{
    volatile char c;
    foo();
}

int main()
{
    volatile char stk;
    MEMORY_BASIC_INFORMATION mbi = {0};
    VirtualQuery((LPCVOID)&stk, &mbi, sizeof(mbi));
    ULONG size = 0;
    for(;;size+=0x1000)
    {
        MEMORY_BASIC_INFORMATION mbi_test = {0};
        VirtualQuery((PCHAR)mbi.AllocationBase+size, &mbi_test, sizeof(mbi_test));
        if (mbi_test.AllocationBase!=mbi.AllocationBase)  break;
    }
    _set_se_translator(trans_func);
    try
    {
        foo();
    }
    catch(SehException &seh)
    {
        printf("caught code=0x%x address=0x%x\nstack: base=0x%x before=0x%x handler=0x%x exception=0x%x remain=0x%x size=0x%x\n", 
            seh.code, seh.address, mbi.AllocationBase, &stk, seh.stk_handler, seh.stk_exception, 
            (unsigned int)seh.stk_exception - (unsigned int)mbi.AllocationBase, size);
    }

    return 0;
}

результат у меня
[quote]
caught code=0xc00000fd address=0x401060
stack: base=0x30000 before=0x12ff18 handler=0x32ab8 exception=0x33000 remain=0x3000 size=0x100000
[/quote]
Походу я ошибся насчет 4 кб, ядро венды кидает SEH на 3й странице от базы, обработчику остается 12кб

Здравствуйте, Аноним, Вы писали:

А>>>>>При этом надо понимать, что функция трансляции исключений ОС в исключения С++ будет работать на огрызке стека размером 4кб.
M>>>>это к чему??? вряд ли ос вообще пользуется тут стеком текущей задачи.
M>>>>думаю у разработчиков ос хватит ума заниматься системными функциями на собственном стеке. в собственном сегменте.
А>>>Срочно читать crash course — http://www.microsoft.com/msj/0197/Exception/Exception.aspx
M>>я чета слабо уверен, что разговор касается майкрософта
M>>стек при бесконечной рекурсии обвалится в любой уважающей себя ос, и потому курить майкрософта тут не совсем корректно. тут можно даже категорически наплевать на эти тонкости от MS.
M>>в своем высказывании я лишь имел ввиду, что ос не станет пускать тут свои функции на стеке текущего пользовательского треда, просто в силу некоректности такого подхода. так делать, короче, нельзя.
А>Добропорядочная ОС и так не "пускает свои функции" на пользовательском стеке. В случае венды и линуха у каждого потока есть специальный, ядреный стек. Аж целых 12кб, а иногда даже больше

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

А>А stack overflow это ОС-specific исключительнаы ситуация. В случае венды при этом кидается обычный SEH с кодом 0xc00000fd, в случае линуха процессу шлется kill, или как там у них принято... И ловить такие вещи нужно средствами ОС, а лучше — не допускать их возникновения.
ну винду я особо изнутри не знаю... я рассуждаю концептульно. типа вот есть некая ос, вот она должна делать то-то и то-то..как это должно работать, чтобы оно работало.
и фсе.