WIP: In llcallbacklist.h, add singleton LLLater for time delays.

The big idea is to reduce the number of per-tick callbacks asking, "Is it time
yet? Is it time yet?" We do that for LLEventTimer and LLEventTimeout.

LLLater presents doAtTime(LLDate), with doAfterInterval() and doPeriodically()
methods implemented using doAtTime(). All return handles. The free functions
doAfterInterval() and doPeriodically() now forward to the corresponding
LLLater methods.

LLLater also presents isRunning(handle) and cancel(handle).

LLLater borrows the tactic of LLEventTimer: while there's at least one running
timer, it registers an LLCallbackList tick() callback to service ready timers.
But instead of looping over all of them asking, "Are you ready?" it keeps them
in a priority queue ordered by desired timestamp, and only touches those whose
timestamp has been reached. Also, it honors a maximum time slice: once the
ready timers have run for longer than the limit, it defers processing other
ready timers to the next tick() call. The intent is to consume fewer cycles
per tick() call, both by the management machinery and the timers themselves.

Revamp LLCallbackList to accept C++ callables in addition to (classic C
function pointer, void*) pairs. Make addFunction() return a handle (different
than LLLater handles) that can be passed to a new deleteFunction() overload,
since std::function instances can't be compared for equality.

In fact, implement LLCallbackList using boost::signals2::signal, which provides
almost exactly what we want.

LLCallbackList continues to accept (function pointer, void*) pairs, but now
we store a lambda that calls the function pointer with that void*. It takes
less horsing around to create a C++ callable from a (function pointer, void*)
pair than the other way around. For containsFunction() and deleteFunction(),
such pairs are the keys for a lookup table whose values are handles.

Instead of having a static global LLCallbackList gIdleCallbacks, make
LLCallbackList an LLSingleton to guarantee initialization. For backwards
compatibility, gIdleCallbacks is now a macro for LLCallbackList::instance().

Move doOnIdleOneTime() and doOnIdleRepeating() functions to LLCallbackList
methods, but for backwards compatibility continue providing free functions.

Reimplement LLEventTimer using LLLater::doPeriodically(). One implication is
that LLEventTimer need no longer be derived from LLInstanceTracker, which we
used to iterate over all instances every tick. Give it start() and stop()
methods, since some subclasses (e.g. LLFlashTimer) used to call its member
LLTimer's start() and stop(). Remove updateClass():
LLCallbackList::callFunctions() now takes care of that.

Remove LLToastLifeTimer::start() and stop(), since LLEventTimer now provides
those. Remove getRemainingTimeF32(), since LLLater does not (yet) provide that
feature.

While at it, make LLEventTimer::tick() return bool instead of BOOL, and change
existing overrides.

Make LLApp::stepFrame() call LLCallbackList::callFunctions() instead of
LLEventTimer::updateClass().

We could have refactored LLEventTimer to use the mechanism now built into
LLLater, but frankly the LLEventTimer API is rather clumsy. You MUST derive a
subclass and override tick(), and you must instantiate your subclass on the
heap because, when your tick() override returns false, LLEventTimer deletes
its subclass instance. The LLLater API is simpler to use, and LLEventTimer is
much simplified by using it.

Merge lleventfilter.h's LLEventTimeoutBase into LLEventTimeout, and likewise
merge LLEventThrottleBase into LLEventThrottle. The separation was for
testability, but now that they're no longer based on LLTimer, it becomes
harder to use dummy time for testing. Temporarily skip tests based on
LLEventTimeoutBase and LLEventThrottleBase.

Instead of listening for LLEventPump("mainloop") ticks and using LLTimer,
LLEventTimeout now uses LLLater::doAfterInterval(). Instead of LLTimer and
LLEventTimeout, LLEventThrottle likewise now uses LLLater::doAfterInterval().

Recast a couple local LLEventTimeout pre-lambda callable classes with lambdas.

Dignify F64 with a new typedef LLDate::timestamp. LLDate heavily depends on
that as its base time representation, but there are those who question use of
floating-point for time. This is a step towards insulating us from any future
change.

1 files changed, 193 insertions, 131 deletions

diff --git a/indra/llcommon/llcallbacklist.cpp b/indra/llcommon/llcallbacklist.cpp
index 9f23ce5317..7f7fdc7370 100644
--- a/indra/llcommon/llcallbacklist.cpp
+++ b/indra/llcommon/llcallbacklist.cpp
@@ -25,17 +25,14 @@
  */
 
 #include "llcallbacklist.h"
-#include "lleventtimer.h"
-#include "llerrorlegacy.h"
-
-// Globals
-//
-LLCallbackList gIdleCallbacks;
 
 //
 // Member functions
 //
 
+/*****************************************************************************
+*   LLCallbackList
+*****************************************************************************/
 LLCallbackList::LLCallbackList()
 {
 	// nothing
@@ -45,186 +42,251 @@ LLCallbackList::~LLCallbackList()
 {
 }
 
-
-void LLCallbackList::addFunction( callback_t func, void *data)
+LLCallbackList::handle_t LLCallbackList::addFunction( callback_t func, void *data)
 {
 	if (!func)
 	{
-		return;
+		return {};
 	}
 
 	// only add one callback per func/data pair
 	//
 	if (containsFunction(func, data))
 	{
-		return;
+		return {};
 	}
-	
-	callback_pair_t t(func, data);
-	mCallbackList.push_back(t);
+
+	auto handle = addFunction([func, data]{ func(data); });
+	mLookup.emplace(callback_pair_t(func, data), handle);
+	return handle;
 }
 
-bool LLCallbackList::containsFunction( callback_t func, void *data)
+LLCallbackList::handle_t LLCallbackList::addFunction( const callable_t& func )
 {
-	callback_pair_t t(func, data);
-	callback_list_t::iterator iter = find(func,data);
-	if (iter != mCallbackList.end())
-	{
-		return TRUE;
-	}
-	else
-	{
-		return FALSE;
-	}
+    return mCallbackList.connect(func);
 }
 
+bool LLCallbackList::containsFunction( callback_t func, void *data)
+{
+    return mLookup.find(callback_pair_t(func, data)) != mLookup.end();
+}
 
 bool LLCallbackList::deleteFunction( callback_t func, void *data)
 {
-	callback_list_t::iterator iter = find(func,data);
-	if (iter != mCallbackList.end())
+	auto found = mLookup.find(callback_pair_t(func, data));
+	if (found != mLookup.end())
 	{
-		mCallbackList.erase(iter);
-		return TRUE;
+		mLookup.erase(found);
+		deleteFunction(found->second);
+		return true;
 	}
 	else
 	{
-		return FALSE;
+		return false;
 	}
 }
 
-inline 
-LLCallbackList::callback_list_t::iterator
-LLCallbackList::find(callback_t func, void *data)
+void LLCallbackList::deleteFunction( const handle_t& handle )
 {
-	callback_pair_t t(func, data);
-	return std::find(mCallbackList.begin(), mCallbackList.end(), t);
+    handle.disconnect();
 }
 
 void LLCallbackList::deleteAllFunctions()
 {
-	mCallbackList.clear();
+	mCallbackList = {};
+	mLookup.clear();
 }
 
-
 void LLCallbackList::callFunctions()
 {
-	for (callback_list_t::iterator iter = mCallbackList.begin(); iter != mCallbackList.end(); )
-	{
-		callback_list_t::iterator curiter = iter++;
-		curiter->first(curiter->second);
-	}
+    mCallbackList();
 }
 
-// Shim class to allow arbitrary boost::bind
-// expressions to be run as one-time idle callbacks.
-class OnIdleCallbackOneTime
+LLCallbackList::handle_t LLCallbackList::doOnIdleOneTime( const callable_t& func )
 {
-public:
-	OnIdleCallbackOneTime(nullary_func_t callable):
-		mCallable(callable)
-	{
-	}
-	static void onIdle(void *data)
-	{
-		gIdleCallbacks.deleteFunction(onIdle, data);
-		OnIdleCallbackOneTime* self = reinterpret_cast<OnIdleCallbackOneTime*>(data);
-		self->call();
-		delete self;
-	}
-	void call()
-	{
-		mCallable();
-	}
-private:
-	nullary_func_t mCallable;
-};
+    // connect_extended() passes the connection to the callback
+    return mCallbackList.connect_extended(
+        [func](const handle_t& handle)
+        {
+            handle.disconnect();
+            func();
+        });
+}
 
-void doOnIdleOneTime(nullary_func_t callable)
+LLCallbackList::handle_t LLCallbackList::doOnIdleRepeating( const bool_func_t& func )
 {
-	OnIdleCallbackOneTime* cb_functor = new OnIdleCallbackOneTime(callable);
-	gIdleCallbacks.addFunction(&OnIdleCallbackOneTime::onIdle,cb_functor);
+    return mCallbackList.connect_extended(
+        [func](const handle_t& handle)
+        {
+            if (func())
+            {
+                handle.disconnect();
+            }
+        });
 }
 
-// Shim class to allow generic boost functions to be run as
-// recurring idle callbacks.  Callable should return true when done,
-// false to continue getting called.
-class OnIdleCallbackRepeating
-{
-public:
-	OnIdleCallbackRepeating(bool_func_t callable):
-		mCallable(callable)
-	{
-	}
-	// Will keep getting called until the callable returns true.
-	static void onIdle(void *data)
-	{
-		OnIdleCallbackRepeating* self = reinterpret_cast<OnIdleCallbackRepeating*>(data);
-		bool done = self->call();
-		if (done)
-		{
-			gIdleCallbacks.deleteFunction(onIdle, data);
-			delete self;
-		}
-	}
-	bool call()
-	{
-		return mCallable();
-	}
-private:
-	bool_func_t mCallable;
-};
+/*****************************************************************************
+*   LLLater
+*****************************************************************************/
+LLLater::LLLater() {}
 
-void doOnIdleRepeating(bool_func_t callable)
+// Call a given callable once at specified timestamp.
+LLLater::handle_t LLLater::doAtTime(nullary_func_t callable, LLDate::timestamp time)
 {
-	OnIdleCallbackRepeating* cb_functor = new OnIdleCallbackRepeating(callable);
-	gIdleCallbacks.addFunction(&OnIdleCallbackRepeating::onIdle,cb_functor);
+    bool first{ mQueue.empty() };
+    // Pick token FIRST to store a self-reference in mQueue's managed node as
+    // well as in mHandles. Pre-increment to distinguish 0 from any live
+    // handle_t.
+    token_t token{ ++mToken };
+    auto handle{ mQueue.emplace(callable, time, token) };
+    mHandles.emplace(token, handle);
+    if (first)
+    {
+        // If this is our first entry, register for regular callbacks.
+        mLive = LLCallbackList::instance().doOnIdleRepeating([this]{ return tick(); });
+    }
+    return handle_t{ token };
 }
 
-class NullaryFuncEventTimer: public LLEventTimer
+// Call a given callable once after specified interval.
+LLLater::handle_t LLLater::doAfterInterval(nullary_func_t callable, F32 seconds)
 {
-public:
-	NullaryFuncEventTimer(nullary_func_t callable, F32 seconds):
-		LLEventTimer(seconds),
-		mCallable(callable)
-	{
-	}
+    // Passing 0 is a slightly more expensive way of calling
+    // LLCallbackList::doOnIdleOneTime(). Are we sure the caller is correct?
+    // (If there's a valid use case, remove the llassert() and carry on.)
+    llassert(seconds > 0);
+    return doAtTime(callable, LLDate::now().secondsSinceEpoch() + seconds);
+}
 
-private:
-	BOOL tick()
-	{
-		mCallable();
-		return TRUE;
-	}
+// For doPeriodically(), we need a struct rather than a lambda because a
+// struct, unlike a lambda, has access to 'this'.
+struct Periodic
+{
+    LLLater* mLater;
+    bool_func_t mCallable;
+    LLDate::timestamp mNext;
+    F32 mSeconds;
 
-	nullary_func_t mCallable;
+    void operator()()
+    {
+        if (! mCallable())
+        {
+            // Returning false means please schedule another call.
+            // Don't call doAfterInterval(), which rereads LLDate::now(),
+            // since that would defer by however long it took us to wake
+            // up and notice plus however long callable() took to run.
+            mNext += mSeconds;
+            mLater->doAtTime(*this, mNext);
+        }
+    }
 };
 
-// Call a given callable once after specified interval.
-void doAfterInterval(nullary_func_t callable, F32 seconds)
+// Call a given callable every specified number of seconds, until it returns true.
+LLLater::handle_t LLLater::doPeriodically(bool_func_t callable, F32 seconds)
 {
-	new NullaryFuncEventTimer(callable, seconds);
+    // Passing seconds <= 0 will produce an infinite loop.
+    llassert(seconds > 0);
+    auto next{ LLDate::now().secondsSinceEpoch() + seconds };
+    return doAtTime(Periodic{ this, callable, next, seconds }, next);
 }
 
-class BoolFuncEventTimer: public LLEventTimer
+bool LLLater::isRunning(handle_t timer)
 {
-public:
-	BoolFuncEventTimer(bool_func_t callable, F32 seconds):
-		LLEventTimer(seconds),
-		mCallable(callable)
-	{
-	}
-private:
-	BOOL tick()
-	{
-		return mCallable();
-	}
+    // A default-constructed timer isn't running.
+    // A timer we don't find in mHandles has fired or been canceled.
+    return timer && mHandles.find(timer.token) != mHandles.end();
+}
 
-	bool_func_t mCallable;
-};
+// Cancel a future timer set by doAtTime(), doAfterInterval(), doPeriodically()
+bool LLLater::cancel(handle_t& timer)
+{
+    // For exception safety, capture and clear timer before canceling.
+    // Once we've canceled this handle, don't retain the live handle.
+    const handle_t ctimer{ timer };
+    timer = handle_t();
+    return cancel(ctimer);
+}
 
-// Call a given callable every specified number of seconds, until it returns true.
-void doPeriodically(bool_func_t callable, F32 seconds)
+bool LLLater::cancel(const handle_t& timer)
+{
+    if (! timer)
+    {
+        return false;
+    }
+
+    // fibonacci_heap documentation does not address the question of what
+    // happens if you call erase() twice with the same handle. Is it a no-op?
+    // Does it invalidate the heap? Is it UB?
+
+    // Nor do we find any documented way to ask whether a given handle still
+    // tracks a valid heap node. That's why we capture all returned handles in
+    // mHandles and validate against that collection. What about the pop()
+    // call in tick()? How to map from the top() value back to the
+    // corresponding handle_t? That's why we store func_at::mToken.
+
+    // fibonacci_heap provides a pair of begin()/end() methods to iterate over
+    // all nodes (NOT in heap order), plus a function to convert from such
+    // iterators to handles. Without mHandles, that would be our only chance
+    // to validate.
+    auto found{ mHandles.find(timer.token) };
+    if (found == mHandles.end())
+    {
+        // we don't recognize this handle -- maybe the timer has already
+        // fired, maybe it was previously canceled.
+        return false;
+    }
+
+    // erase from mQueue the handle_t referenced by timer.token
+    mQueue.erase(found->second);
+    // before erasing timer.token from mHandles
+    mHandles.erase(found);
+    if (mQueue.empty())
+    {
+        // If that was the last active timer, unregister for callbacks.
+        //LLCallbackList::instance().deleteFunction(mLive);
+        // Since we're in the source file that knows the true identity of an
+        // LLCallbackList::handle_t, we don't even need to call instance().
+        mLive.disconnect();
+    }
+    return true;
+}
+
+bool LLLater::tick()
 {
-	new BoolFuncEventTimer(callable, seconds);
+    // Fetch current time only on entry, even though running some mQueue task
+    // may take long enough that the next one after would become ready. We're
+    // sharing this thread with everything else, and there's a risk we might
+    // starve it if we have a sequence of tasks that take nontrivial time.
+    auto now{ LLDate::now().secondsSinceEpoch() };
+    auto cutoff{ now + TIMESLICE };
+    while (! mQueue.empty())
+    {
+        auto& top{ mQueue.top() };
+        if (top.mTime > now)
+        {
+            // we've hit an entry that's still in the future:
+            // done with this tick(), but schedule another call
+            return false;
+        }
+        if (LLDate::now().secondsSinceEpoch() > cutoff)
+        {
+            // we still have ready tasks, but we've already eaten too much
+            // time this tick() -- defer until next tick() -- call again
+            return false;
+        }
+
+        // Found a ready task. Hate to copy stuff, but -- what if the task
+        // indirectly ends up trying to cancel a handle referencing its own
+        // node in mQueue? If the task has any state, that would be Bad. Copy
+        // the node before running it.
+        auto current{ top };
+        // remove the mHandles entry referencing this task
+        mHandles.erase(current.mToken);
+        // before removing the mQueue task entry itself
+        mQueue.pop();
+        // okay, NOW run 
+        current.mFunc();
+    }
+    // queue is empty: stop callbacks
+    return true;
 }