Looking at the Queue class, I noticed that it might
incorrectly raise a Full/Empty Exception when called
with block=False.

This leads to the following undesirable behaviour:
 * Full exception raised when Queue not full
 * Full exception raised when Queue has no maxsize

Here's my logic (for put(), but get() is similar):

First part of code for put, in Queue.py:
    def put(self, item, block=1):
        if block:
            self.fsema.acquire()
        elif not self.fsema.acquire(0):
            raise Full

Now, for the purposes of raising a Full exception, we
are assuming that fsema is locked if and only if the
Queue is full.

BUT, it seems that fsema is locked every time an item
is added to the Queue, even if that item would not make
the Queue full.

Hence, it might be possible for a Full exception to be
raised, when fsema is locked due to adding an item that
would not  actually make the Queue full. 

An example...

 * Queue with maxsize 10, currently 5 objects in it.
 * Threads T1 and T2, both trying to add an item with
Queue.put(item, block=True).
 * This should obviously be fine, resulting in a Queue
with 7 items.
 [1] Call T1.put(item1, block=True)
 [2] Call T2.put(item2, block=True)
 [3] T1 grabs fsema and mutex, but then the current
thread changes before they are released...
 [4] T2 cannot acquire fsema (since T1 currently has
it), and so raises the Full exception (incorrectly)

Of course, I may have misunderstood something, since I
haven't been able to consistently reproduce the problem
(threading errors are so vexing).

I have no easy solution to this issue (redo the class
using a threading.BoundedSemaphore to count the Queue
length?).

My python version:
Python 2.2.2 (#1, Feb 24 2003, 17:36:09)
[GCC 3.0.4 (Mandrake Linux 8.2 3.0.4-2mdk)] on linux2

Logged In: YES 
user_id=31435

As the docs say (ALL CAPS emphasis added),

"""
exception Full 

Exception raised when non-blocking put() (or put_nowait()) is 
called on a Queue object which is full OR LOCKED. 
"""

and similarly for Empty.  The primary point of a non-blocking 
call is never to block, and that's why "or locked" is in the 
docs.  A BoundedSemaphore (or any other "reliable" 
synchronization gimmick) could block, so cannot be used.

In practice, it doesn't matter:  a Queue user who wants to 
use non-blocking calls has to be prepared for Full or Empty 
exceptions, and that's the end of it.

Logged In: YES 
user_id=80475

Can this be closed as invalid?

Logged In: YES 
user_id=31435

Yes, but unless it's a screamingly obvious non-bug I like to 
wait at least a week to see whether somebody else has a 
clever approach that works as well but without the surprising 
parts.  The docs in this case aren't terribly clear, because 
they really can't explain the whole truth without explaining 
the implementation.

Logged In: YES 
user_id=693152

Sorry - my fault. I didn't read that part of the doco well
enough.

However, is it an issue that important behaviour of a
function is described separately to the function (ie. in the
exception)? Could we put a general note in the put/get
documentation also (Eg. "In the current implementation the
Full exception may sometimes be raised incorrectly.")

Also, I may have the wrong expectations for how this class
should behave. My assumption was that put(block=False) means
 don't block waiting for a slot in the queue, but it's
implicitly okay to block for other reasons (eg. internal
data sharing, as actually happens with mutex). Was this
incorrect?

I'll see if I can think up an alternative implementation
over the next few days.

Logged In: YES 
user_id=31435

The primary point of a non-blocking call is never to block.  
That's the common meaning of "non-blocking" (in or out of 
Python).  After all, a "non-blocking" call that *could* block is 
useless for apps that need not to block.  If you're willing to 
block, use the blocking methods (which most apps do use, 
BTW -- using the non-blocking methods is unusual).

The Full exception isn't raised incorrectly.  "Full" is just 4 
letters strung together, and is only meant to be suggestive 
and convenient -- its full meaning is explained in the docs, 
albeit somewhat cryptically.  I don't think it would be a real 
improvement to, e.g., rename this exception to 
FullOrMaybeNotFullButCheckingForThatCouldPotentiallyBlockSo
WeSkippedThat <wink>.

Logged In: YES 
user_id=693152

First up, you're right that non-blocking calls are unusual.
This isn't exactly a critical matter for me :-)

Okay, I have misunderstood the meaning of non-blocking calls
- so it actually means "ensure we never under any
circumstances block". Why then do we acquire mutex with a
blocking call?

I am not suggesting there's anything wrong with the naming
of Full (amusing as your suggestion is :-). Of course you
can't completely describe how an exception will be used in
it's name.

It just seems more intuitive for put's documentation to
fully and unambiguously describe when an exception is
raised, rather than to have part of the function
documentation ("or locked") in the Exception documentation.
More straightforward, etc.

Logged In: YES 
user_id=31435

We acquire a mutex with a blocking call because the use of a 
blocking call announces that the client is *willing* to block, 
and nothing about the state of a Queue can be changed 
without acquiring a lock first.  So it wouldn't make sense not 
to acquire a lock in that case.

I have no objection at all to improving the docs.  They appear 
to be what they are now because the original version of the 
Queue module didn't have a non-blocking put() method, or a 
Full exception.  I added those 7(!) years later, in 1999.  
Development was done by emailing changes to Guido at that 
time, though, and doc changes were often dropped on the 
floor.

If you can work up a doc patch to supply words that would 
make better sense to you, that would be great.

Logged In: YES 
user_id=693152

Whoops - let's try that question in a clearer way:

When you do a non-blocking call to put(), why does it
acquire mutex in a blocking way (ie. "put(block=False)" will
call "mutex.acquire()", which could block whilst acquiring
mutex). I thought the theory was that you *never* block
anywhere.

Logged In: YES 
user_id=31435

It depends on what you mean by "blocking" <wink>.  If the 
thread implementation schedules fairly, it's impossible for 
self.mutex to be held for a "long" time by any thread -- unlike 
esema and fsema, self.mutex is used only for mutual exclusion 
over brief sections of code that don't wait for anything, and 
nothing Queue clients do can cause self.mutex to be held for 
an arbitrarily long time (a spectacularly bad OS 
implementation of thread scheduling could, but that's out of 
the user's-- and out of Python's --hands).

The usual meaning of "blocking" is that clients *can* do 
something to get the system into a state where a call can 
take arbitrarily long to complete (while assuming fair thread 
scheduling).  The obvious example here is that Queue.get() 
can take forever if the Queue is empty and the app stops 
adding anything to the Queue.  There's nothing (sane) the 
app can do that can make Queue.get_nowait() take forever.

BTW, I hope you're looking at the 2.3 code here!  Queue is 
more complicated in 2.3 because these methods have also 
grown optional timeout arguments.  If you're really worried 
about "spurious" Full exceptions, doing a blocking 2.3 
Queue.put() call with a short timeout will try to grab fsema 
several times before giving up.

Logged In: YES 
user_id=693152

Okay, that makes more sense. So, loosely expressed,
non-blocking means there's no way the user can put the Queue
in a blocked state (and especially not deadlocked) - as with
your example of waiting forever on a get call. But,
obviously, internal locks can always be used (in a careful
manner).

I think that's closer to my implicit understand of blocking
that I was trying to express. In the case of put/get, I had
a slightly different expectation about what we were blocking
for (as we have already dicscussed at length :-). Anyway,
I've knocked up some modifications to the documentation,
which you're welcome to use, abuse, or reject out of hand.

I've done this in the form of modifications to the source
code. I assume that's the correct approach, but the 2.3
source code and 2.3 HTML documentation seem to be a bit
different (so I ended up incorporating the relevant HTML
doco into the python source doco, then modifying that).

The patch is the output from:
% diff Queue_v2_3.py Queue_doc_change.py

Logged In: YES 
user_id=880241

A Full exception is returned when the queue is NOT FULL. 
This is a bug!  The lack of an immediate solution is not an
excuse to accept incorrect code.

Logged In: YES 
user_id=31435

berryman77, as the first comment in this report suggested, 
read the documentation:

"""
Full

Exception raised when non-blocking put() (or put_nowait()) is 
called on a Queue object which is full or locked. 
"""

Note the "OR LOCKED" part, a natural counterpoint to 
your "NOT FULL" screaming <wink>.

When code functions as designed and as documented, you 
can argue about the design, or about the quality of the docs, 
but you can't call it "a bug" (well, not if you want to be taken 
seriously).

The name of the exception is simply briefly suggestive, as are 
the names of most exceptions; 
FULL_OR_NOT_FULL_BUT_LOCKED would be more accurate, 
but too clumsy.

Logged In: YES 
user_id=880241

Rather than reiterating here, I agree with this post: 

Date: 2003-08-17 21:55
Sender: gazzadee

I did read the docs for the put method, but not for the Full
Exception, as I assumed it means the queue is full. 
Although the documentation of the Full exception makes the
code technically correct, I found (as several of the posters
here did) that it is unintuitive.  So much so that it
appears to be a bug (hence this bug report).  As I see it,
the documentation simply documents the bug.

"""
The name of the exception is simply briefly suggestive, as are 
the names of most exceptions; 
FULL_OR_NOT_FULL_BUT_LOCKED would be more accurate, 
but too clumsy.
"""

The programmer is not aware of the internal blocking unless
s/he has looked at the source of Queue.  S/he is most likely
expecting put_nowait() to not wait on the queue to free a
slot.  This is to me the intuitive functionality of this
method. According to the comments here,  there is
disagreement on this issue.  So if put_nowait means there is
to be no blocking internally or by the queue, then there
should be 2 exceptions, Full and Locked, so that the user
can distinguish between the two.

Logged In: YES 
user_id=31435

Well, there aren't "several posters" here:  before you jumped 
in, there were exactly three in this report's history:  the 
person who filed the original report (gazzadee), me, and 
Raymond Hettinger (who asked once whether to close the 
report as invalid).  In the 11 months this has been open, 
nobody else has cared enough to comment, let alone produce 
a different implementation.

The reasons the current implementation is reasonable have 
already been explained here at some length, so I'm not going 
over them again.  If you can't tolerate the Full or Empty 
exceptions. don't use non-blocking calls.  It's typical of non-
blocking calls (in and out of Python) that they may return for 
no other reason than that they cannot succeed immediately, 
so honor their contract not to block by returning at once but 
without a useful response.

I still agree the docs could stand improvement.

Logged In: YES 
user_id=31435

I rewrote the Queue put() and get() methods completely for 
2.4.  Since there wasn't "a bug" here, it won't get 
backported.  Full and Empty now mean that the queue was 
indeed full or empty (respectively) at the instant the queue 
was checked, but of course there's no guarantee (and never 
can be) that the queue is still full or empty by the time a 
caller sees those exceptions.

Doc/lib/libqueue.tex; new revision: 1.15
Lib/Queue.py; new revision: 1.21
Misc/NEWS; new revision: 1.1039