Document some reverse-engineered invariants and pragmatic hints.

1 files changed, 17 insertions, 2 deletions

diff --git a/Modules/collectionsmodule.c b/Modules/collectionsmodule.c
index 5856b11..03e09c9 100644
--- a/Modules/collectionsmodule.c
+++ b/Modules/collectionsmodule.c
@@ -9,6 +9,21 @@
 
 #define BLOCKLEN 46
 
+/* A `dequeobject` is composed of a doubly-linked list of `block` nodes.
+ * This list is not circular (the leftmost block has leftlink==NULL,
+ * and the rightmost block has rightlink==NULL).  A deque d's first
+ * element is at d.leftblock[leftindex] and its last element is at
+ * d.rightblock[rightindex]; note that, unlike as for Python slice
+ * indices, this indices are inclusive on both ends.
+ * The list of blocks is never empty.  An empty deque d has
+ * d.leftblock == d.rightblock != NULL; d.len == 0; and
+ * d.leftindex > d.rightindex; checking for d.len == 0 is the intended
+ * way to see whether d is empty.
+ * Note that since d.leftindex and d.rightindex may be indices into
+ * distinct blocks (and certainly are, for and d with len(d) > BLOCKLEN),
+ * it's not generally true that d.leftindex <= d.rightindex.
+ */
+
 typedef struct BLOCK {
 	struct BLOCK *leftlink;
 	struct BLOCK *rightlink;
@@ -31,8 +46,8 @@ typedef struct {
 	PyObject_HEAD
 	block *leftblock;
 	block *rightblock;
-	int leftindex;
-	int rightindex;
+	int leftindex;	/* in range(BLOCKLEN) */
+	int rightindex;	/* in range(BLOCKLEN) */
 	int len;
 	PyObject *weakreflist; /* List of weak references */
 } dequeobject;