Boost logo

Boost :

From: Douglas Gregor (gregod_at_[hidden])
Date: 2003-09-18 17:12:19


My apologies for the (very) late reply. Today is catch-up-with-Boost day, just
in case nobody noticed :)

On Sunday 14 September 2003 08:34 pm, Edward Diener wrote:
> 1) Group values are stilled used and they are still 'int's.
> 2) Group values can go from the greatest negative 'int' to the greatest
> positive
> 'int'.

The Group type defaults to int, but it can be anything that models
CopyConstructible. One can also override the GroupCompare type, which
defaults to std::less<Group>. There are two questions that come to mind (and
will be recurring in my response):
        1) Can we just devise a better type for "Group" that gives us the same
semantics you are proposing?
        2) Can we get these semantics for any Group type, without imposing additional
restrictions on the type?

> 3) A group value of a given name, which let us call SIGNALS_GROUP_TOP,
> specifies the greatest positive 'int' value and may be passed. This value
> places that slot at the top of the list for a given signal.
> 4) A group value of a given name, which let us call SIGNALS_GROUP_BOTTOM,
> specifies the greatest negative 'int' value and may be passed. This value
> places that slot at the bottom of the list for a given signal.

I like these, although I'd prefer to call them "front" and "back" (with
appropriate syntactic modifications depending if they are
constants/macros/types/etc.). I believe it's better to think of the slots as
a queue (front/back terminology) than as a stack (top/bottom terminology).

The answers to my questions #1 and #2 are "yes" and "yes".

> 5) A slot which does not pass a group value automatically gets a group
> value of 0, which places it in the middle of the list and not at the end as
> the current implementation does.

Yes, I can understand the reasoning behind this, and it seems like reasonable
semantics to me. For my questions:
        1) The answer is "yes": there are lots of types like 'int' for which there's
an obvious middle value.
        2) The answer is "mostly": what to do about types where we don't know the
middle value? One easy fallback is to say that the default-constructed group
value is given to any slot connection without specifying a group.

> Slots for a given signal are called in the order of their group value from
> highest 'int' to lowest 'int'.

FWIW, this is the opposite of the current behavior (lowest groups are called
first). Just passing GroupCompare = std::greater<Group> would switch the
behavior, of course.

> The interesting question, obviously, is in
> what
> order slots, which have the same group value, are called. What follows is a
> design suggestion for that occurrence.
>
> 1) Ordering for a given signal for slots with the same group number may be
> random, FIFO ( first in, first out ), LIFO ( last in, first out ), and
> user defined. This can be done with an enum with values such as
> SIGNALS_ORDER_RANDOM, SIGNALS_ORDER_FIFO, SIGNALS_ORDER_LIFO, and
> SIGNALS_ORDER_USER. A function of the connection can let the user change
> this value from the default. The default should be SIGNALS_ORDER_FIFO
> and not SIGNALS_ORDER_RANDOM which is essentially the current
> implementation.

The current implementation should be at least deterministic, unless the
underlying multimap implementation is truly crazy :)

I don't see the point of random ordering. The current ordering is unspecified
to give implementers (err, well, me) some freedom in the implementation. If
we're going to take away that freedom with lifo/fifo/user ordering, there's
no reason to leave random.

> 2) If SIGNALS_ORDER_USER is specified the user should pass into the
> connection
> a Boost::Function as his callback which takes two const references to
> the appropriate Boost::Function for the signal and returns a bool.
>
> Each time the Signals library has to decide in what order slots
> should be called for a specific signal, when the slots have the same group
> number, it starts with the first slot in its list for that group number
> and begins comparing it to every other slot after it using the above
> Boost::function callback. If the callback returns true, it keeps the order.
> If the callback returns false, it moves the other slot in front of it
> in the order but continues to compare the original slot in the same way
> with all other uncompared slots.
>
> Then it goes to the next slot at the beginning of the list and does the
> same, making sure not to compare again with any slot that has already been
> previously compared. It follows this algorithm until the final list order
> is determined and then calls each slot in that order.

This is an O(n^2) algorithm, and that's going to hurt at run-time more than we
can justify. However, that doesn't really matter: implementing the suggested
semantics amounts to changing the group-based ordering to a lexicographical
ordering on (group, function object). But there is a caveat:
boost::function<> objects cannot be compared, nor can the underlying object
be queried. Because of this, I'm not sure how users could ever compare two
slots, unless they replace boost::function<> with a different SlotFunction
type (the last template parameter for the signal class).

So here's my question: where could the user get an ordering on slots that
couldn't be done by using, e.g., std::pair<int, foo> instead of int as the
Group type? I can't think of any instances.

> An obvious alternative to the above is to pass the entire list as a vector
> of slots and let the end-user reorder it as he wants. However I do prefer
> the previous method as being easier, from the end-user's point of view,
> to use, although obviously more iterative ( multiple calls versus a single
> call ).

This would seriously break the encapsulation of the Signals library, and put a
huge burden on the user. If we're to do user ordering, using a
lexicographical order is the right way.

With respect to the in-group ordering, I think then the only two choices left
are LIFO and FIFO, i.e., connect at either the beginning or the end of the
group, respectively. We know we need:
        1) Guaranteed ordering
        2) A sensible default (FIFO)

The question I can't adequately answer is: Does the usefulness of the option
to use LIFO ordering within groups outweigh the cost of the extra interfaces
we'll need to support it?

The benefit of allowing both LIFO and FIFO ordering is that users get more
control over slot ordering. There may be uses where this is absolutely
necessary; I'm not sure.

The cost is that we will need more connect() overloads, and we'll have some
duplication in the slot interface: you can order slots via group names and
with fifo/lifo subgroup ordering. One could argue that this completely
redundant, because one can use a pair<group, foo> instead of group slot
ordering to achieve the same thing.

Here's a counter-proposal, that I think captures most of the semantics of your
proposal. I'll note differences at the end:
        1) Connecting a slot without specifying a group name uses a
default-constructed group name.
        2) There are two special values "at_front" and "at_back", located in
namespace boost::signals, that connect to the front or back of the slot
ordering. (We can spell these any way we want, of course, I just dislike
ALL_CAPS if it's avoidable). This will add one new connect( ) overload:
                connection connect(front_or_back fob, const slot_type& slot);
        3) Slots are connected at the back of their group (except when connecting
at_front, of course), i.e., using FIFO ordering.

This (semantically) differs from your proposal in several ways:
        1) at_front would go before, e.g., numeric_limits<int>::min() and at_back
would go after numeric_limits<int>::max(), because they are part of an
ordering applied before the group's ordering.
        2) "random"/"unspecified" in-group ordering doesn't exist (it isn't useful,
nor does it give implementors any useful lattitude).
        3) "user" in-group ordering doesn't exist (because I don't think it's
feasible from an implementation perspective)
        4) "lifo" ordering doesn't exist, because I'm guessing it isn't work the
addition of more connect() overloads. This is the change for which I have the
least rationale.

Thank you for starting this discussion. It's one we really need to have to
improve Signals.

        Doug


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk