In C++ how can I prevent a function from being called recursively

I have a function which makes use of memory on the heap and it will go badly wrong if it is called before another instance of the same function has completed. How can I prevent开发者_开发知识库 this from happening at compile time?

---

Detecting recursion with any amount determinism of at compile-time is going to be quite difficult. Some static code analysis tools might be able to do it, but even then you can get in to run-time scenarios involving threads that code analyzers won't be able to detect.

You need to detect recursion at run-time. Fundamentally, it's very simple to do this:

bool MyFnSimple()
{
    static bool entered = false;
    if( entered )
    {
        cout << "Re-entered function!" << endl;
        return false;
    }
    entered = true;

    // ...

    entered = false;
    return true;
}

The biggest problem with this, of course, is it is not thread safe. There are a couple of ways to make it thread safe, the simplest being to use a critical section and block the second entry until the first has left. Windows code (no error handling included):

bool MyFnCritSecBlocking()
{
    static HANDLE cs = CreateMutex(0, 0, 0);
    WaitForSingleObject(cs, INFINITE);
    // ... do stuff
    ReleaseMutex(cs);
    return true;
}

If you want the function to return an error when a function has been reentered, you can first test the critsec before grabbing it:

bool MyFnCritSecNonBlocking()
{
    static HANDLE cs = CreateMutex(0, 0, 0);
    DWORD ret = WaitForSingleObject(cs, 0);
    if( WAIT_TIMEOUT == ret )
        return false;   // someone's already in here
    // ... do stuff
    ReleaseMutex(cs);
    return true;
}

There are probably an infinite ways to skin this cat other than the use of static bools and critsecs. One that comes to mind is a combination of testing a local value with one of the Interlocked functions in Windows:

bool MyFnInterlocked()
{
    static LONG volatile entered = 0;
    LONG ret = InterlockedCompareExchange(&entered, 1, 0);
    if( ret == 1 )
        return false;   // someone's already in here
    // ... do stuff
    InterlockedExchange(&entered, 0);
    return false;
}

And, of course, you have to think about exception safety and deadlocks. You don't want a failure in your function to leave it un-enterable by any code. You can wrap any of the constructs above in RAII in order to ensure the release of a lock when an exception or early exit occurs in your function.

UPDATE:

After readong comments I realized I could have included code that illustrates how to implement an RAII solution, since any real code you write is going to use RAII to handle errors. Here is a simple RAII implementation that also illustrates what happens at runtime when things go wrong:

#include <windows.h>
#include <cstdlib>
#include <stdexcept>
#include <iostream>

class CritSecLock
{
public:
    CritSecLock(HANDLE cs) : cs_(cs)
    {
        DWORD ret = WaitForSingleObject(cs_, INFINITE);
        if( ret != WAIT_OBJECT_0 ) 
            throw std::runtime_error("Unable To Acquire Mutex");
        std::cout << "Locked" << std::endl;
    }
    ~CritSecLock()
    {
        std::cout << "Unlocked" << std::endl;
        ReleaseMutex(cs_);
    }
private:
    HANDLE cs_;
};

bool MyFnPrimitiveRAII()
{
    static HANDLE cs = CreateMutex(0, 0, 0);
    try
    {
        CritSecLock lock(cs);
        // ... do stuff
        throw std::runtime_error("kerflewy!");
        return true;
    }
    catch(...)
    {
        // something went wrong 
        // either with the CritSecLock instantiation
        // or with the 'do stuff' code
        std::cout << "ErrorDetected" << std::endl;
        return false;
    }
}

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

---

Your question is unclear, do you mean in a single-threaded scenario (recursion or mutual recursion) or a multi-threaded scenario (re-entrancy)?

In a multi-threaded scenario, there is no way to prevent this at compile time, since the compiler has no knoweldge of threads.

In a single-threaded scenario, I don't know of a way to prevent a recursive call at compile time other than using your brain. As long as you can analyze the control flow and prove that your function doesn't call itself and that none of the functions it calls will call it back, you should be safe.

---

You cannot do it at compile-time without static analysis. Here is an exception-safe recursive assertion:

#include <cassert>

class simple_lock
{
public:
    simple_lock(bool& pLock):
    mLock(pLock)
    {
        assert(!mLock && "recursive call");
        mLock = true;
    }

    ~simple_lock(void)
    {
        mLock = false;
    }

private:
    simple_lock(const simple_lock&);
    simple_lock& operator=(const simple_lock&);

    bool& mLock;
};

#define ASSERT_RECURSION static bool _lockFlag = false; \
                            simple_lock _lock(_lockFlag)

void foo(void)
{
    ASSERT_RECURSION;

    foo();
}

int main(void)
{
    foo();
    //foo();
}

---

Without some sort of static analyser, you cannot do this at compile time. However, a simple run-time check for this will work:

Note: for preventing multi-threaded concurrent but non-recursive invocation you need something a bit more robust.

void myFunc() {
  static int locked = 0;
  if (locked++)
  {
    printf("recursion detected\n!");
  }

  ....

  locked--;
}

Note: you should place this function in a .c or .cc file, not in a header.

If you do have multi-threading, I suggest you use pthread locks to control access to the shared variables it references.

---

That problem is undecidable in any turing complete language. I can't prove it though. I just know.

---

The function call stack is created at runtime, At compile time you can only check if your function is recursive itself or not i.e does it calls itself?.

---

c++-faq-lite has some nice advice in similar cases: write a comment that you expect problems when doing such a thing:

// We'll fire you if you try recursion here

I haven't looked whether the advice was also for recursion

---

Your best bet is to use a mutex. You could use a semaphore, but personally I prefer mutexs here. This will allow you to prevent it from being called by other threads.

* edit *

Ah you want it to happen at compile time?

You're on a hiding to nothing there my friend.

---

You can't do it at compile-time, you'd need to follow the complete control flow of the whole application to accomplish this (what if the function calls another function which invokes another function which invoes another function which in turn invokes the original function again ...).

Do it at think time instead. Add a huge comment to the function's documentation. Plus maybe one of the runtime solutions presented by the other responses - for debug builds.

Just to add another one: use a static mutex to protect the function body (boost's scoped_lock would greatly simplify it).

---

This compiles

#include <stdio.h>

int testFunc() {
#define testFunc
printf("Ok\n");
}
#undef testFunc
int main() { testFunc(); }

This doesn't

#include <stdio.h>

int testFunc() {
#define testFunc
printf("Ok\n");
testFunc();
}
#undef testFunc
int main() { testFunc(); }

Error: test.c:7: error: expected expression before ‘)’ token

It works on multi-function recursion too:

#include <stdio.h>

int testFunc1() {
#define testFunc1
printf("1\n");
testFunc2();
}

int testFunc2() {
#define testFunc2
printf("2\n");
//uncomment to cause error: `test.c:13: error: expected expression before ‘)’ token`
//testFunc1();
}

#undef testFunc1
#undef testFunc2

int main() { testFunc1(); }

---

Here is my solution for single threaded reentry prevention using RAII:

    struct NestingTracker
    {
        NestingTracker(uint32_t &cnt) : _cnt(cnt) { ++_cnt; }
        ~NestingTracker()                         { assert(_cnt); --_cnt; }
        uint32_t& _cnt;
    };

#define NO_REENTRY(x)                        \
    static uint32_t cur_nesting = 0;         \
    if (cur_nesting)                         \
        return (x);                             \
    NestingTracker nesting_track(cur_nesting)

use as

void f(...)
{
    NO_REENTRY(void());
    ...
}

---

The only way to do this is to make sure that client code has no way to reference the function you don't want to be reentered. This can be accomplished by making the function static or in an anonymous namespace or some similar technique.

Unfortunately, in order for this to be certain of working, all functions leading from main to your function must also be declared in this fashion, and that situation becomes really difficult to manage really quickly.

And, while C++ technically says that calls to main from your code are undefined and you shouldn't do them, most implementations will happily recurse main for you. And main has to have a name that is accessible from anywhere else in your program.

So, in reality it isn't really possible.

And I expected you wanted the compiler to give you an error when you tried anyway instead of just making sure there simple wasn't any possible way you could do it.