[tarantool-patches] Re: [PATCH v1 4/4] sql: got rid of redundant bitmask helpers

[Kirill Shcherbatov <kshcherbatov@tarantool.org>]

> 1. There is no nColumn variable.
Fixed.

> 2. You broke down the behaviour. Before your patch,
> mCol in case of j >= BMS was == 0 and the condition
> (mCol & colUsed) == false. Now it is possible that
> with j >= COLUMN_MASK_SIZE the condition is true.
It is not so.
The are few if ... continue branches before, 
if ((int)part_count < nExpr)
	continue;
if (part_count >= BITMASK_SIZE - 1)
	continue;

So,
nExpr <= part_count
part_count < BITMASK_SIZE - 1
=> nExpr < BITMASK_SIZE - 1
=> j <= nExpr < BITMASK_SIZE - 1
So our bitmasks work fine, but like not smart.

=============================================

The original SQLite code allowed the program to be compiled using
32-bit masks to save disk space. Since we are not going to
compile Tarantool in such way, we will get rid of these macros by
replacing them(where possible) with helpers from column_mask.h

Closes #3571
---
 src/box/sql/expr.c     |  31 +++++++-----
 src/box/sql/resolve.c  |  12 +----
 src/box/sql/sqlInt.h   |  26 ++--------
 src/box/sql/where.c    | 109 +++++++++++++++++++----------------------
 src/box/sql/whereInt.h |   3 +-
 5 files changed, 77 insertions(+), 104 deletions(-)

diff --git a/src/box/sql/expr.c b/src/box/sql/expr.c
index a72f986c6..a6c077fc4 100644
--- a/src/box/sql/expr.c
+++ b/src/box/sql/expr.c
@@ -2396,19 +2396,20 @@ sqlFindInIndex(Parse * pParse,	/* Parsing context */
 			     eType == 0; ++k) {
 				struct index *idx = space->index[k];
 				Bitmask colUsed; /* Columns of the index used */
-				Bitmask mCol;	/* Mask for the current column */
 				uint32_t part_count =
 					idx->def->key_def->part_count;
 				struct key_part *parts =
 					idx->def->key_def->parts;
 				if ((int)part_count < nExpr)
 					continue;
-				/* Maximum nColumn is BMS-2, not BMS-1, so that we can compute
-				 * BITMASK(nExpr) without overflowing
+				/*
+				 * Maximum fieldno is
+				 * BITMASK_SIZE-2, not
+				 * BITMASK_SIZE-1, so that we
+				 * can compute bitmask without
+				 * overflowing.
 				 */
-				testcase(part_count == BMS - 2);
-				testcase(part_count == BMS - 1);
-				if (part_count >= BMS - 1)
+				if (part_count >= BITMASK_SIZE - 1)
 					continue;
 				if (mustBeUnique &&
 				    ((int)part_count > nExpr ||
@@ -2444,19 +2445,23 @@ sqlFindInIndex(Parse * pParse,	/* Parsing context */
 					}
 					if (j == nExpr)
 						break;
-					mCol = MASKBIT(j);
-					if (mCol & colUsed)
-						break;	/* Each column used only once */
-					colUsed |= mCol;
+					/*
+					 * Each column used only
+					 * once.
+					 */
+					if (column_mask_fieldno_is_set(colUsed,
+								       j))
+						break;
+					column_mask_set_fieldno(&colUsed, j);
 					if (aiMap)
 						aiMap[i] = pRhs->iColumn;
 					else if (pSingleIdxCol && nExpr == 1)
 						*pSingleIdxCol = pRhs->iColumn;
 					}
 
-				assert(i == nExpr
-				       || colUsed != (MASKBIT(nExpr) - 1));
-				if (colUsed == (MASKBIT(nExpr) - 1)) {
+				assert(i == nExpr ||
+				       colUsed != (BITMASK_BIT(nExpr) - 1));
+				if (colUsed == (BITMASK_BIT(nExpr) - 1)) {
 					/* If we reach this point, that means the index pIdx is usable */
 					int iAddr = sqlVdbeAddOp0(v, OP_Once);
 					VdbeCoverage(v);
diff --git a/src/box/sql/resolve.c b/src/box/sql/resolve.c
index a9a167477..8940efd9d 100644
--- a/src/box/sql/resolve.c
+++ b/src/box/sql/resolve.c
@@ -440,13 +440,8 @@ lookupName(Parse * pParse,	/* The parsing context */
 	 * then set the high-order bit of the bitmask.
 	 */
 	if (pExpr->iColumn >= 0 && pMatch != 0) {
-		int n = pExpr->iColumn;
-		testcase(n == BMS - 1);
-		if (n >= BMS) {
-			n = BMS - 1;
-		}
 		assert(pMatch->iCursor == pExpr->iTable);
-		pMatch->colUsed |= ((Bitmask) 1) << n;
+		column_mask_set_fieldno(&pMatch->colUsed, pExpr->iColumn);
 	}
 
 	/* Clean up and return
@@ -488,10 +483,7 @@ sqlCreateColumnExpr(sql * db, SrcList * pSrc, int iSrc, int iCol)
 		p->space_def = pItem->space->def;
 		p->iTable = pItem->iCursor;
 		p->iColumn = (ynVar) iCol;
-		testcase(iCol == BMS);
-		testcase(iCol == BMS - 1);
-		pItem->colUsed |=
-			((Bitmask) 1) << (iCol >= BMS ? BMS - 1 : iCol);
+		column_mask_set_fieldno(&pItem->colUsed, iCol);
 		ExprSetProperty(p, EP_Resolved);
 	}
 	return p;
diff --git a/src/box/sql/sqlInt.h b/src/box/sql/sqlInt.h
index a9b7dfa4e..7d17e8753 100644
--- a/src/box/sql/sqlInt.h
+++ b/src/box/sql/sqlInt.h
@@ -2234,28 +2234,12 @@ struct IdList {
 };
 
 /*
- * The bitmask datatype defined below is used for various optimizations.
- *
- * Changing this from a 64-bit to a 32-bit type limits the number of
- * tables in a join to 32 instead of 64.  But it also reduces the size
- * of the library by 738 bytes on ix86.
- */
-#ifdef SQL_BITMASK_TYPE
-typedef SQL_BITMASK_TYPE Bitmask;
-#else
-typedef u64 Bitmask;
-#endif
-
-/*
- * The number of bits in a Bitmask.  "BMS" means "BitMask Size".
- */
-#define BMS  ((int)(sizeof(Bitmask)*8))
-
-/*
- * A bit in a Bitmask
+ * The bitmask datatype defined below is used for various
+ * optimizations.
  */
-#define MASKBIT(n)   (((Bitmask)1)<<(n))
-#define ALLBITS      ((Bitmask)-1)
+typedef uint64_t Bitmask;
+#define BITMASK_SIZE ((int)sizeof(Bitmask)*CHAR_BIT)
+#define BITMASK_BIT(n)   (((Bitmask)1)<<(n))
 
 /*
  * The following structure describes the FROM clause of a SELECT statement.
diff --git a/src/box/sql/where.c b/src/box/sql/where.c
index fc05c9f85..b8a9d6f31 100644
--- a/src/box/sql/where.c
+++ b/src/box/sql/where.c
@@ -219,9 +219,8 @@ sqlWhereGetMask(WhereMaskSet * pMaskSet, int iCursor)
 	int i;
 	assert(pMaskSet->n <= (int)sizeof(Bitmask) * 8);
 	for (i = 0; i < pMaskSet->n; i++) {
-		if (pMaskSet->ix[i] == iCursor) {
-			return MASKBIT(i);
-		}
+		if (pMaskSet->ix[i] == iCursor)
+			return BITMASK_BIT(i);
 	}
 	return 0;
 }
@@ -731,12 +730,10 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	int regRecord;		/* Register holding an index record */
 	int n;			/* Column counter */
 	int i;			/* Loop counter */
-	int mxBitCol;		/* Maximum column in pSrc->colUsed */
 	struct coll *pColl;		/* Collating sequence to on a column */
 	WhereLoop *pLoop;	/* The Loop object */
 	char *zNotUsed;		/* Extra space on the end of pIdx */
 	Bitmask idxCols;	/* Bitmap of columns used for indexing */
-	Bitmask extraCols;	/* Bitmap of additional columns */
 	u8 sentWarning = 0;	/* True if a warnning has been issued */
 	int iContinue = 0;	/* Jump here to skip excluded rows */
 	struct SrcList_item *pTabItem;	/* FROM clause term being indexed */
@@ -762,10 +759,8 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) {
 		if (termCanDriveIndex(pTerm, pSrc, notReady)) {
 			int iCol = pTerm->u.leftColumn;
-			Bitmask cMask =
-			    iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol);
-			testcase(iCol == BMS);
-			testcase(iCol == BMS - 1);
+			uint64_t column_mask;
+			column_mask_set_fieldno(&column_mask, iCol);
 			if (!sentWarning) {
 				sql_log(SQL_WARNING_AUTOINDEX,
 					    "automatic index on %s(%s)",
@@ -773,13 +768,13 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 					    pTable->aCol[iCol].zName);
 				sentWarning = 1;
 			}
-			if ((idxCols & cMask) == 0) {
+			if ((idxCols & column_mask) == 0) {
 				if (whereLoopResize
 				    (pParse->db, pLoop, nKeyCol + 1)) {
 					goto end_auto_index_create;
 				}
 				pLoop->aLTerm[nKeyCol++] = pTerm;
-				idxCols |= cMask;
+				idxCols |= column_mask;
 			}
 		}
 	}
@@ -796,17 +791,17 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	 * original table changes and the index and table cannot both be used
 	 * if they go out of sync.
 	 */
-	extraCols = pSrc->colUsed & (~idxCols | MASKBIT(BMS - 1));
-	mxBitCol = MIN(BMS - 1, pTable->def->field_count);
-	testcase(pTable->def->field_count == BMS - 1);
-	testcase(pTable->def->field_count == BMS - 2);
-	for (i = 0; i < mxBitCol; i++) {
-		if (extraCols & MASKBIT(i))
+	/* Bitmap of additional columns. */
+	uint64_t extra_cols = pSrc->colUsed &
+			     (~idxCols | BITMASK_BIT(BITMASK_SIZE - 1));
+	/* Maximum column in pSrc->colUsed. */
+	int max_col_idx = MIN(BITMASK_SIZE - 1, pTable->def->field_count);
+	for (i = 0; i < max_col_idx; i++) {
+		if (column_mask_fieldno_is_set(extra_cols, i))
 			nKeyCol++;
 	}
-	if (pSrc->colUsed & MASKBIT(BMS - 1)) {
-		nKeyCol += pTable->def->field_count - BMS + 1;
-	}
+	if (column_mask_is_overflowed(pSrc->colUsed))
+		nKeyCol += pTable->def->field_count - BITMASK_SIZE + 1;
 
 	/* Construct the Index object to describe this index */
 	pIdx = sqlDbMallocZero(pParse->db, sizeof(*pIdx));
@@ -820,13 +815,11 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	for (pTerm = pWC->a; pTerm < pWCEnd; pTerm++) {
 		if (termCanDriveIndex(pTerm, pSrc, notReady)) {
 			int iCol = pTerm->u.leftColumn;
-			Bitmask cMask =
-			    iCol >= BMS ? MASKBIT(BMS - 1) : MASKBIT(iCol);
-			testcase(iCol == BMS - 1);
-			testcase(iCol == BMS);
-			if ((idxCols & cMask) == 0) {
+			uint64_t column_mask;
+			column_mask_set_fieldno(&column_mask, iCol);
+			if ((idxCols & column_mask) == 0) {
 				Expr *pX = pTerm->pExpr;
-				idxCols |= cMask;
+				idxCols |= column_mask;
 				pIdx->aiColumn[n] = pTerm->u.leftColumn;
 				n++;
 			}
@@ -837,14 +830,15 @@ constructAutomaticIndex(Parse * pParse,			/* The parsing context */
 	/* Add additional columns needed to make the automatic index into
 	 * a covering index
 	 */
-	for (i = 0; i < mxBitCol; i++) {
-		if (extraCols & MASKBIT(i)) {
+	for (i = 0; i < max_col_idx; i++) {
+		if (column_mask_fieldno_is_set(extra_cols, i)) {
 			pIdx->aiColumn[n] = i;
 			n++;
 		}
 	}
-	if (pSrc->colUsed & MASKBIT(BMS - 1)) {
-		for (i = BMS - 1; i < (int)pTable->def->field_count; i++) {
+	if (column_mask_is_overflowed(pSrc->colUsed)) {
+		for (i = BITMASK_SIZE - 1;
+		     i < (int)pTable->def->field_count; i++) {
 			pIdx->aiColumn[n] = i;
 			n++;
 		}
@@ -3201,11 +3195,11 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		return 0;
 
 	nOrderBy = pOrderBy->nExpr;
-	testcase(nOrderBy == BMS - 1);
-	if (nOrderBy > BMS - 1)
-		return 0;	/* Cannot optimize overly large ORDER BYs */
+	/* Cannot optimize overly large ORDER BYs. */
+	if (nOrderBy > BITMASK_SIZE - 1)
+		return 0;
 	isOrderDistinct = 1;
-	obDone = MASKBIT(nOrderBy) - 1;
+	obDone = BITMASK_BIT(nOrderBy) - 1;
 	orderDistinctMask = 0;
 	ready = 0;
 	eqOpMask = WO_EQ | WO_ISNULL;
@@ -3230,7 +3224,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		 * loops.
 		 */
 		for (i = 0; i < nOrderBy; i++) {
-			if (MASKBIT(i) & obSat)
+			if (column_mask_fieldno_is_set(obSat, i))
 				continue;
 			pOBExpr = sqlExprSkipCollate(pOrderBy->a[i].pExpr);
 			if (pOBExpr->op != TK_COLUMN)
@@ -3270,7 +3264,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 				if (coll1 != coll2)
 					continue;
 			}
-			obSat |= MASKBIT(i);
+			column_mask_set_fieldno(&obSat, i);
 		}
 
 		if ((pLoop->wsFlags & WHERE_ONEROW) == 0) {
@@ -3369,7 +3363,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 				 */
 				isMatch = 0;
 				for (i = 0; bOnce && i < nOrderBy; i++) {
-					if (MASKBIT(i) & obSat)
+					if (column_mask_fieldno_is_set(obSat, i))
 						continue;
 					pOBExpr =
 					    sqlExprSkipCollate(pOrderBy-> a[i].pExpr);
@@ -3415,14 +3409,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 						rev =
 						    revIdx ^ pOrderBy->a[i].
 						    sort_order;
-						if (rev)
-							*pRevMask |=
-							    MASKBIT(iLoop);
+						if (rev) {
+							column_mask_set_fieldno(
+								pRevMask, iLoop);
+						}
 						revSet = 1;
 					}
 				}
 				if (isMatch) {
-					obSat |= MASKBIT(i);
+					column_mask_set_fieldno(&obSat, i);
 				} else {
 					/* No match found */
 					if (j == 0 || j < nColumn) {
@@ -3445,16 +3440,15 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 			for (i = 0; i < nOrderBy; i++) {
 				Expr *p;
 				Bitmask mTerm;
-				if (MASKBIT(i) & obSat)
+				if (column_mask_fieldno_is_set(obSat, i))
 					continue;
 				p = pOrderBy->a[i].pExpr;
 				mTerm =
 				    sqlWhereExprUsage(&pWInfo->sMaskSet, p);
 				if (mTerm == 0 && !sqlExprIsConstant(p))
 					continue;
-				if ((mTerm & ~orderDistinctMask) == 0) {
-					obSat |= MASKBIT(i);
-				}
+				if ((mTerm & ~orderDistinctMask) == 0)
+					column_mask_set_fieldno(&obSat, i);
 			}
 		}
 	}			/* End the loop over all WhereLoops from outer-most down to inner-most */
@@ -3462,7 +3456,7 @@ wherePathSatisfiesOrderBy(WhereInfo * pWInfo,	/* The WHERE clause */
 		return (i8) nOrderBy;
 	if (!isOrderDistinct) {
 		for (i = nOrderBy - 1; i > 0; i--) {
-			Bitmask m = MASKBIT(i) - 1;
+			uint32_t m = BITMASK_BIT(i) - 1;
 			if ((obSat & m) == m)
 				return i;
 		}
@@ -4269,8 +4263,7 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 	memset(&sWLB, 0, sizeof(sWLB));
 
 	/* An ORDER/GROUP BY clause of more than 63 terms cannot be optimized */
-	testcase(pOrderBy && pOrderBy->nExpr == BMS - 1);
-	if (pOrderBy && pOrderBy->nExpr >= BMS)
+	if (pOrderBy && pOrderBy->nExpr >= BITMASK_SIZE)
 		pOrderBy = 0;
 	sWLB.pOrderBy = pOrderBy;
 
@@ -4284,9 +4277,9 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 	/* The number of tables in the FROM clause is limited by the number of
 	 * bits in a Bitmask
 	 */
-	testcase(pTabList->nSrc == BMS);
-	if (pTabList->nSrc > BMS) {
-		sqlErrorMsg(pParse, "at most %d tables in a join", BMS);
+	if (pTabList->nSrc > BITMASK_SIZE) {
+		sqlErrorMsg(pParse, "at most %d tables in a join",
+			    BITMASK_SIZE);
 		return 0;
 	}
 
@@ -4388,7 +4381,7 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 	for (ii = 0; ii < pTabList->nSrc; ii++) {
 		Bitmask m =
 		    sqlWhereGetMask(pMaskSet, pTabList->a[ii].iCursor);
-		assert(m == MASKBIT(ii));
+		assert(m == BITMASK_BIT(ii));
 	}
 #endif
 
@@ -4455,7 +4448,7 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 	}
 	if (pWInfo->pOrderBy == 0 &&
 	    (user_session->sql_flags & SQL_ReverseOrder) != 0) {
-		pWInfo->revMask = ALLBITS;
+		pWInfo->revMask = COLUMN_MASK_FULL;
 	}
 	if (pParse->nErr || NEVER(db->mallocFailed)) {
 		goto whereBeginError;
@@ -4653,13 +4646,11 @@ sqlWhereBegin(Parse * pParse,	/* The parser context */
 							continue;
 						if (jj > 63)
 							jj = 63;
-						if ((pTabItem->
-						     colUsed & MASKBIT(jj)) ==
-						    0)
+						if (!column_mask_fieldno_is_set(
+							&pTabItem->colUsed, i))
 							continue;
-						colUsed |=
-						    ((u64) 1) << (ii <
-								  63 ? ii : 63);
+						column_mask_set_fieldno(&colUsed,
+									ii);
 					}
 					sqlVdbeAddOp4Dup8(v, OP_ColumnsUsed,
 							      iIndexCur, 0, 0,
diff --git a/src/box/sql/whereInt.h b/src/box/sql/whereInt.h
index 7a0312dfd..12a1dded6 100644
--- a/src/box/sql/whereInt.h
+++ b/src/box/sql/whereInt.h
@@ -379,7 +379,8 @@ struct WhereAndInfo {
  */
 struct WhereMaskSet {
 	int n;			/* Number of assigned cursor values */
-	int ix[BMS];		/* Cursor assigned to each bit */
+	/* Cursor assigned to each bit. */
+	int ix[BITMASK_SIZE];
 };
 
 /*
-- 
2.20.1