+ return isIndexable;
+}
+
+/*
+ * expand_indexqual_conditions
+ * Given a list of (implicitly ANDed) indexqual clauses,
+ * expand any "special" index operators into clauses that the indexscan
+ * machinery will know what to do with. Clauses that were not
+ * recognized by match_special_index_operator() must be passed through
+ * unchanged.
+ */
+List *
+expand_indexqual_conditions(List *indexquals)
+{
+ List *resultquals = NIL;
+ List *q;
+
+ foreach(q, indexquals)
+ {
+ Expr *clause = (Expr *) lfirst(q);
+ /* we know these will succeed */
+ Var *leftop = get_leftop(clause);
+ Var *rightop = get_rightop(clause);
+ Oid expr_op = ((Oper *) clause->oper)->opno;
+ Datum constvalue;
+ char *patt;
+ char *prefix;
+ Prefix_Status pstatus;
+
+ switch (expr_op)
+ {
+ /*
+ * LIKE and regex operators are not members of any index opclass,
+ * so if we find one in an indexqual list we can assume that
+ * it was accepted by match_special_index_operator().
+ */
+ case OID_TEXT_LIKE_OP:
+ case OID_BPCHAR_LIKE_OP:
+ case OID_VARCHAR_LIKE_OP:
+ case OID_NAME_LIKE_OP:
+ /* the right-hand const is type text for all of these */
+ constvalue = ((Const *) rightop)->constvalue;
+ patt = textout((text *) DatumGetPointer(constvalue));
+ pstatus = like_fixed_prefix(patt, &prefix);
+ resultquals = nconc(resultquals,
+ prefix_quals(leftop, expr_op,
+ prefix, pstatus));
+ if (prefix) pfree(prefix);
+ pfree(patt);
+ break;
+
+ case OID_TEXT_REGEXEQ_OP:
+ case OID_BPCHAR_REGEXEQ_OP:
+ case OID_VARCHAR_REGEXEQ_OP:
+ case OID_NAME_REGEXEQ_OP:
+ /* the right-hand const is type text for all of these */
+ constvalue = ((Const *) rightop)->constvalue;
+ patt = textout((text *) DatumGetPointer(constvalue));
+ pstatus = regex_fixed_prefix(patt, false, &prefix);
+ resultquals = nconc(resultquals,
+ prefix_quals(leftop, expr_op,
+ prefix, pstatus));
+ if (prefix) pfree(prefix);
+ pfree(patt);
+ break;
+
+ case OID_TEXT_ICREGEXEQ_OP:
+ case OID_BPCHAR_ICREGEXEQ_OP:
+ case OID_VARCHAR_ICREGEXEQ_OP:
+ case OID_NAME_ICREGEXEQ_OP:
+ /* the right-hand const is type text for all of these */
+ constvalue = ((Const *) rightop)->constvalue;
+ patt = textout((text *) DatumGetPointer(constvalue));
+ pstatus = regex_fixed_prefix(patt, true, &prefix);
+ resultquals = nconc(resultquals,
+ prefix_quals(leftop, expr_op,
+ prefix, pstatus));
+ if (prefix) pfree(prefix);
+ pfree(patt);
+ break;
+
+ default:
+ resultquals = lappend(resultquals, clause);
+ break;
+ }
+ }
+
+ return resultquals;
+}
+
+/*
+ * Extract the fixed prefix, if any, for a LIKE pattern.
+ * *prefix is set to a palloc'd prefix string,
+ * or to NULL if no fixed prefix exists for the pattern.
+ * The return value distinguishes no fixed prefix, a partial prefix,
+ * or an exact-match-only pattern.
+ */
+static Prefix_Status
+like_fixed_prefix(char *patt, char **prefix)
+{
+ char *match;
+ int pos,
+ match_pos;
+
+ *prefix = match = palloc(strlen(patt)+1);
+ match_pos = 0;
+
+ for (pos = 0; patt[pos]; pos++)
+ {
+ /* % and _ are wildcard characters in LIKE */
+ if (patt[pos] == '%' ||
+ patt[pos] == '_')
+ break;
+ /* Backslash quotes the next character */
+ if (patt[pos] == '\\')
+ {
+ pos++;
+ if (patt[pos] == '\0')
+ break;
+ }
+ /*
+ * NOTE: this code used to think that %% meant a literal %,
+ * but textlike() itself does not think that, and the SQL92
+ * spec doesn't say any such thing either.
+ */
+ match[match_pos++] = patt[pos];
+ }
+
+ match[match_pos] = '\0';
+
+ /* in LIKE, an empty pattern is an exact match! */
+ if (patt[pos] == '\0')
+ return Prefix_Exact; /* reached end of pattern, so exact */
+
+ if (match_pos > 0)
+ return Prefix_Partial;
+ return Prefix_None;
+}
+
+/*
+ * Extract the fixed prefix, if any, for a regex pattern.
+ * *prefix is set to a palloc'd prefix string,
+ * or to NULL if no fixed prefix exists for the pattern.
+ * The return value distinguishes no fixed prefix, a partial prefix,
+ * or an exact-match-only pattern.
+ */
+static Prefix_Status
+regex_fixed_prefix(char *patt, bool case_insensitive,
+ char **prefix)
+{
+ char *match;
+ int pos,
+ match_pos;
+
+ *prefix = NULL;
+
+ /* Pattern must be anchored left */
+ if (patt[0] != '^')
+ return Prefix_None;
+
+ /* Cannot optimize if unquoted | { } is present in pattern */
+ for (pos = 1; patt[pos]; pos++)
+ {
+ if (patt[pos] == '|' ||
+ patt[pos] == '{' ||
+ patt[pos] == '}')
+ return Prefix_None;
+ if (patt[pos] == '\\')
+ {
+ pos++;
+ if (patt[pos] == '\0')
+ break;
+ }
+ }
+
+ /* OK, allocate space for pattern */
+ *prefix = match = palloc(strlen(patt)+1);
+ match_pos = 0;
+
+ /* note start at pos 1 to skip leading ^ */
+ for (pos = 1; patt[pos]; pos++)
+ {
+ if (patt[pos] == '.' ||
+ patt[pos] == '?' ||
+ patt[pos] == '*' ||
+ patt[pos] == '[' ||
+ patt[pos] == '$' ||
+ /* XXX I suspect isalpha() is not an adequately locale-sensitive
+ * test for characters that can vary under case folding?
+ */
+ (case_insensitive && isalpha(patt[pos])))
+ break;
+ if (patt[pos] == '\\')
+ {
+ pos++;
+ if (patt[pos] == '\0')
+ break;
+ }
+ match[match_pos++] = patt[pos];
+ }
+
+ match[match_pos] = '\0';
+
+ if (patt[pos] == '$' && patt[pos+1] == '\0')
+ return Prefix_Exact; /* pattern specifies exact match */
+
+ if (match_pos > 0)
+ return Prefix_Partial;
+ return Prefix_None;
+}
+
+/*
+ * Given a fixed prefix that all the "leftop" values must have,
+ * generate suitable indexqual condition(s). expr_op is the original
+ * LIKE or regex operator; we use it to deduce the appropriate comparison
+ * operators.
+ */
+static List *
+prefix_quals(Var *leftop, Oid expr_op,
+ char *prefix, Prefix_Status pstatus)
+{
+ List *result;
+ Oid datatype;
+ Oid oproid;
+ Const *con;
+ Oper *op;
+ Expr *expr;
+ char *greaterstr;
+
+ Assert(pstatus != Prefix_None);
+
+ switch (expr_op)
+ {
+ case OID_TEXT_LIKE_OP:
+ case OID_TEXT_REGEXEQ_OP:
+ case OID_TEXT_ICREGEXEQ_OP:
+ datatype = TEXTOID;
+ break;
+
+ case OID_BPCHAR_LIKE_OP:
+ case OID_BPCHAR_REGEXEQ_OP:
+ case OID_BPCHAR_ICREGEXEQ_OP:
+ datatype = BPCHAROID;
+ break;
+
+ case OID_VARCHAR_LIKE_OP:
+ case OID_VARCHAR_REGEXEQ_OP:
+ case OID_VARCHAR_ICREGEXEQ_OP:
+ datatype = VARCHAROID;
+ break;
+
+ case OID_NAME_LIKE_OP:
+ case OID_NAME_REGEXEQ_OP:
+ case OID_NAME_ICREGEXEQ_OP:
+ datatype = NAMEOID;
+ break;
+
+ default:
+ elog(ERROR, "prefix_quals: unexpected operator %u", expr_op);
+ return NIL;
+ }
+
+ /*
+ * If we found an exact-match pattern, generate an "=" indexqual.
+ */
+ if (pstatus == Prefix_Exact)
+ {
+ oproid = find_operator("=", datatype);
+ if (oproid == InvalidOid)
+ elog(ERROR, "prefix_quals: no = operator for type %u", datatype);
+ con = string_to_const(prefix, datatype);
+ op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
+ expr = make_opclause(op, leftop, (Var *) con);
+ result = lcons(expr, NIL);
+ return result;
+ }
+
+ /*
+ * Otherwise, we have a nonempty required prefix of the values.
+ *
+ * We can always say "x >= prefix".
+ */
+ oproid = find_operator(">=", datatype);
+ if (oproid == InvalidOid)
+ elog(ERROR, "prefix_quals: no >= operator for type %u", datatype);
+ con = string_to_const(prefix, datatype);
+ op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
+ expr = make_opclause(op, leftop, (Var *) con);
+ result = lcons(expr, NIL);
+
+ /*
+ * If we can create a string larger than the prefix, say "x < greaterstr".
+ */
+ greaterstr = make_greater_string(prefix, datatype);
+ if (greaterstr)
+ {
+ oproid = find_operator("<", datatype);
+ if (oproid == InvalidOid)
+ elog(ERROR, "prefix_quals: no < operator for type %u", datatype);
+ con = string_to_const(greaterstr, datatype);
+ op = makeOper(oproid, InvalidOid, BOOLOID, 0, NULL);
+ expr = make_opclause(op, leftop, (Var *) con);
+ result = lappend(result, expr);
+ pfree(greaterstr);
+ }
+
+ return result;
+}
+
+/*
+ * Try to generate a string greater than the given string or any string it is
+ * a prefix of. If successful, return a palloc'd string; else return NULL.
+ *
+ * To work correctly in non-ASCII locales with weird collation orders,
+ * we cannot simply increment "foo" to "fop" --- we have to check whether
+ * we actually produced a string greater than the given one. If not,
+ * increment the righthand byte again and repeat. If we max out the righthand
+ * byte, truncate off the last character and start incrementing the next.
+ * For example, if "z" were the last character in the sort order, then we
+ * could produce "foo" as a string greater than "fonz".
+ *
+ * This could be rather slow in the worst case, but in most cases we won't
+ * have to try more than one or two strings before succeeding.
+ *
+ * XXX in a sufficiently weird locale, this might produce incorrect results?
+ * For example, in German I believe "ss" is treated specially --- if we are
+ * given "foos" and return "foot", will this actually be greater than "fooss"?
+ */
+static char *
+make_greater_string(const char * str, Oid datatype)
+{
+ char *workstr;
+ int len;
+
+ /* Make a modifiable copy, which will be our return value if successful */
+ workstr = pstrdup((char *) str);
+
+ while ((len = strlen(workstr)) > 0)
+ {
+ unsigned char *lastchar = (unsigned char *) (workstr + len - 1);
+
+ /*
+ * Try to generate a larger string by incrementing the last byte.
+ */
+ while (*lastchar < (unsigned char) 255)
+ {
+ (*lastchar)++;
+ if (string_lessthan(str, workstr, datatype))
+ return workstr; /* Success! */
+ }
+ /*
+ * Truncate off the last character, which might be more than 1 byte
+ * in MULTIBYTE case.
+ */
+#ifdef MULTIBYTE
+ len = pg_mbcliplen((const unsigned char *) workstr, len, len-1);
+ workstr[len] = '\0';
+#else
+ *lastchar = '\0';
+#endif
+ }
+
+ /* Failed... */
+ pfree(workstr);
+ return NULL;
+}
+
+/*
+ * Handy subroutines for match_special_index_operator() and friends.
+ */
+
+/* See if there is a binary op of the given name for the given datatype */
+static Oid
+find_operator(const char * opname, Oid datatype)
+{
+ HeapTuple optup;
+
+ optup = SearchSysCacheTuple(OPERNAME,
+ PointerGetDatum(opname),
+ ObjectIdGetDatum(datatype),
+ ObjectIdGetDatum(datatype),
+ CharGetDatum('b'));
+ if (!HeapTupleIsValid(optup))
+ return InvalidOid;
+ return optup->t_data->t_oid;
+}
+
+/*
+ * Generate a Datum of the appropriate type from a C string.
+ * Note that all of the supported types are pass-by-ref, so the
+ * returned value should be pfree'd if no longer needed.
+ */
+static Datum
+string_to_datum(const char * str, Oid datatype)
+{
+ /* We cheat a little by assuming that textin() will do for
+ * bpchar and varchar constants too...
+ */
+ if (datatype == NAMEOID)
+ return PointerGetDatum(namein((char *) str));
+ else
+ return PointerGetDatum(textin((char *) str));
+}
+
+/*
+ * Generate a Const node of the appropriate type from a C string.
+ */
+static Const *
+string_to_const(const char * str, Oid datatype)
+{
+ Datum conval = string_to_datum(str, datatype);
+
+ return makeConst(datatype, ((datatype == NAMEOID) ? NAMEDATALEN : -1),
+ conval, false, false, false, false);
+}
+
+/*
+ * Test whether two strings are "<" according to the rules of the given
+ * datatype. We do this the hard way, ie, actually calling the type's
+ * "<" operator function, to ensure we get the right result...
+ */
+static bool
+string_lessthan(const char * str1, const char * str2, Oid datatype)
+{
+ Datum datum1 = string_to_datum(str1, datatype);
+ Datum datum2 = string_to_datum(str2, datatype);
+ bool result;
+
+ switch (datatype)
+ {
+ case TEXTOID:
+ result = text_lt((text *) datum1, (text *) datum2);
+ break;
+
+ case BPCHAROID:
+ result = bpcharlt((char *) datum1, (char *) datum2);
+ break;
+
+ case VARCHAROID:
+ result = varcharlt((char *) datum1, (char *) datum2);
+ break;
+
+ case NAMEOID:
+ result = namelt((NameData *) datum1, (NameData *) datum2);
+ break;
+
+ default:
+ elog(ERROR, "string_lessthan: unexpected datatype %u", datatype);
+ result = false;
+ break;
+ }
+
+ pfree(DatumGetPointer(datum1));
+ pfree(DatumGetPointer(datum2));
+
+ return result;