Bug #788520: Queue class has logic error when non-blocking

I don't agree it had a bug (see the report), so this is *not* a candidate
for backporting, but the docs were confusing and the Queue implementation
was old enough to vote.

Rewrote put/put_nowait/get/get_nowait from scratch, to use a pair of
Conditions (not_full and not_empty), sharing a common mutex.  The code
is 1/4 the size now, and 6.25x easier to understand.  For blocking
with timeout, we also get to reuse (indirectly) the tedious timeout
code from threading.Condition.  The Full and Empty exceptions raised
by non-blocking calls are now easy (instead of nearly impossible) to
explain truthfully:  Full is raised if and only if the Queue truly
is full when the non-blocking put call checks the queue size, and
similarly for Empty versus non-blocking get.

What I don't know is whether the new implementation is slower (or
faster) than the old one.  I don't really care.  Anyone who cares
a lot is encouraged to check that.

1 files changed, 11 insertions, 0 deletions

diff --git a/Misc/NEWS b/Misc/NEWS
index 5593f00..c736a70 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -29,6 +29,17 @@ Extension modules
 Library
 -------
 
+- Bug #788520.  Queue.{get, get_nowait, put, put_nowait} have new
+  implementations, exploiting Conditions (which didn't exist at the time
+  Queue was introduced).  A minor semantic change is that the Full and
+  Empty exceptions raised by non-blocking calls now occur only if the
+  queue truly was full or empty at the instant the queue was checked (of
+  course the Queue may no longer be full or empty by the time a calling
+  thread sees those exceptions, though).  Before, the exceptions could
+  also be raised if it was "merely inconvenient" for the implementation
+  to determine the true state of the Queue (because the Queue was locked
+  by some other method in progress).
+
 - Bugs #979794 and #980117: difflib.get_grouped_opcodes() now handles the
   case of comparing two empty lists.  This affected both context_diff() and
   unified_diff(),