granicus.if.org Git - postgresql/blob - src/backend/utils/adt/rangetypes.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * rangetypes.c
   4  *        I/O functions, operators, and support functions for range types.
   5  *
   6  * The stored (serialized) format of a range value is:
   7  *
   8  *      4 bytes: varlena header
   9  *      4 bytes: range type's OID
  10  *      Lower boundary value, if any, aligned according to subtype's typalign
  11  *      Upper boundary value, if any, aligned according to subtype's typalign
  12  *      1 byte for flags
  13  *
  14  * This representation is chosen to avoid needing any padding before the
  15  * lower boundary value, even when it requires double alignment.  We can
  16  * expect that the varlena header is presented to us on a suitably aligned
  17  * boundary (possibly after detoasting), and then the lower boundary is too.
  18  * Note that this means we can't work with a packed (short varlena header)
  19  * value; we must detoast it first.
  20  *
  21  *
  22  * Portions Copyright (c) 1996-2017, PostgreSQL Global Development Group
  23  * Portions Copyright (c) 1994, Regents of the University of California
  24  *
  25  *
  26  * IDENTIFICATION
  27  *        src/backend/utils/adt/rangetypes.c
  28  *
  29  *-------------------------------------------------------------------------
  30  */
  31 #include "postgres.h"
  32
  33 #include "access/hash.h"
  34 #include "lib/stringinfo.h"
  35 #include "libpq/pqformat.h"
  36 #include "miscadmin.h"
  37 #include "utils/builtins.h"
  38 #include "utils/date.h"
  39 #include "utils/int8.h"
  40 #include "utils/lsyscache.h"
  41 #include "utils/rangetypes.h"
  42 #include "utils/timestamp.h"
  43
  44
  45 #define RANGE_EMPTY_LITERAL "empty"
  46
  47 /* fn_extra cache entry for one of the range I/O functions */
  48 typedef struct RangeIOData
  49 {
  50         TypeCacheEntry *typcache;       /* range type's typcache entry */
  51         Oid                     typiofunc;              /* element type's I/O function */
  52         Oid                     typioparam;             /* element type's I/O parameter */
  53         FmgrInfo        proc;                   /* lookup result for typiofunc */
  54 } RangeIOData;
  55
  56
  57 static RangeIOData *get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid,
  58                                   IOFuncSelector func);
  59 static char range_parse_flags(const char *flags_str);
  60 static void range_parse(const char *input_str, char *flags, char **lbound_str,
  61                         char **ubound_str);
  62 static const char *range_parse_bound(const char *string, const char *ptr,
  63                                   char **bound_str, bool *infinite);
  64 static char *range_deparse(char flags, const char *lbound_str,
  65                           const char *ubound_str);
  66 static char *range_bound_escape(const char *value);
  67 static Size datum_compute_size(Size sz, Datum datum, bool typbyval,
  68                                    char typalign, int16 typlen, char typstorage);
  69 static Pointer datum_write(Pointer ptr, Datum datum, bool typbyval,
  70                         char typalign, int16 typlen, char typstorage);
  71
  72
  73 /*
  74  *----------------------------------------------------------
  75  * I/O FUNCTIONS
  76  *----------------------------------------------------------
  77  */
  78
  79 Datum
  80 range_in(PG_FUNCTION_ARGS)
  81 {
  82         char       *input_str = PG_GETARG_CSTRING(0);
  83         Oid                     rngtypoid = PG_GETARG_OID(1);
  84         Oid                     typmod = PG_GETARG_INT32(2);
  85         RangeType  *range;
  86         RangeIOData *cache;
  87         char            flags;
  88         char       *lbound_str;
  89         char       *ubound_str;
  90         RangeBound      lower;
  91         RangeBound      upper;
  92
  93         check_stack_depth();            /* recurses when subtype is a range type */
  94
  95         cache = get_range_io_data(fcinfo, rngtypoid, IOFunc_input);
  96
  97         /* parse */
  98         range_parse(input_str, &flags, &lbound_str, &ubound_str);
  99
 100         /* call element type's input function */
 101         if (RANGE_HAS_LBOUND(flags))
 102                 lower.val = InputFunctionCall(&cache->proc, lbound_str,
 103                                                                           cache->typioparam, typmod);
 104         if (RANGE_HAS_UBOUND(flags))
 105                 upper.val = InputFunctionCall(&cache->proc, ubound_str,
 106                                                                           cache->typioparam, typmod);
 107
 108         lower.infinite = (flags & RANGE_LB_INF) != 0;
 109         lower.inclusive = (flags & RANGE_LB_INC) != 0;
 110         lower.lower = true;
 111         upper.infinite = (flags & RANGE_UB_INF) != 0;
 112         upper.inclusive = (flags & RANGE_UB_INC) != 0;
 113         upper.lower = false;
 114
 115         /* serialize and canonicalize */
 116         range = make_range(cache->typcache, &lower, &upper, flags & RANGE_EMPTY);
 117
 118         PG_RETURN_RANGE(range);
 119 }
 120
 121 Datum
 122 range_out(PG_FUNCTION_ARGS)
 123 {
 124         RangeType  *range = PG_GETARG_RANGE(0);
 125         char       *output_str;
 126         RangeIOData *cache;
 127         char            flags;
 128         char       *lbound_str = NULL;
 129         char       *ubound_str = NULL;
 130         RangeBound      lower;
 131         RangeBound      upper;
 132         bool            empty;
 133
 134         check_stack_depth();            /* recurses when subtype is a range type */
 135
 136         cache = get_range_io_data(fcinfo, RangeTypeGetOid(range), IOFunc_output);
 137
 138         /* deserialize */
 139         range_deserialize(cache->typcache, range, &lower, &upper, &empty);
 140         flags = range_get_flags(range);
 141
 142         /* call element type's output function */
 143         if (RANGE_HAS_LBOUND(flags))
 144                 lbound_str = OutputFunctionCall(&cache->proc, lower.val);
 145         if (RANGE_HAS_UBOUND(flags))
 146                 ubound_str = OutputFunctionCall(&cache->proc, upper.val);
 147
 148         /* construct result string */
 149         output_str = range_deparse(flags, lbound_str, ubound_str);
 150
 151         PG_RETURN_CSTRING(output_str);
 152 }
 153
 154 /*
 155  * Binary representation: The first byte is the flags, then the lower bound
 156  * (if present), then the upper bound (if present).  Each bound is represented
 157  * by a 4-byte length header and the binary representation of that bound (as
 158  * returned by a call to the send function for the subtype).
 159  */
 160
 161 Datum
 162 range_recv(PG_FUNCTION_ARGS)
 163 {
 164         StringInfo      buf = (StringInfo) PG_GETARG_POINTER(0);
 165         Oid                     rngtypoid = PG_GETARG_OID(1);
 166         int32           typmod = PG_GETARG_INT32(2);
 167         RangeType  *range;
 168         RangeIOData *cache;
 169         char            flags;
 170         RangeBound      lower;
 171         RangeBound      upper;
 172
 173         check_stack_depth();            /* recurses when subtype is a range type */
 174
 175         cache = get_range_io_data(fcinfo, rngtypoid, IOFunc_receive);
 176
 177         /* receive the flags... */
 178         flags = (unsigned char) pq_getmsgbyte(buf);
 179
 180         /*
 181          * Mask out any unsupported flags, particularly RANGE_xB_NULL which would
 182          * confuse following tests.  Note that range_serialize will take care of
 183          * cleaning up any inconsistencies in the remaining flags.
 184          */
 185         flags &= (RANGE_EMPTY |
 186                           RANGE_LB_INC |
 187                           RANGE_LB_INF |
 188                           RANGE_UB_INC |
 189                           RANGE_UB_INF);
 190
 191         /* receive the bounds ... */
 192         if (RANGE_HAS_LBOUND(flags))
 193         {
 194                 uint32          bound_len = pq_getmsgint(buf, 4);
 195                 const char *bound_data = pq_getmsgbytes(buf, bound_len);
 196                 StringInfoData bound_buf;
 197
 198                 initStringInfo(&bound_buf);
 199                 appendBinaryStringInfo(&bound_buf, bound_data, bound_len);
 200
 201                 lower.val = ReceiveFunctionCall(&cache->proc,
 202                                                                                 &bound_buf,
 203                                                                                 cache->typioparam,
 204                                                                                 typmod);
 205                 pfree(bound_buf.data);
 206         }
 207         else
 208                 lower.val = (Datum) 0;
 209
 210         if (RANGE_HAS_UBOUND(flags))
 211         {
 212                 uint32          bound_len = pq_getmsgint(buf, 4);
 213                 const char *bound_data = pq_getmsgbytes(buf, bound_len);
 214                 StringInfoData bound_buf;
 215
 216                 initStringInfo(&bound_buf);
 217                 appendBinaryStringInfo(&bound_buf, bound_data, bound_len);
 218
 219                 upper.val = ReceiveFunctionCall(&cache->proc,
 220                                                                                 &bound_buf,
 221                                                                                 cache->typioparam,
 222                                                                                 typmod);
 223                 pfree(bound_buf.data);
 224         }
 225         else
 226                 upper.val = (Datum) 0;
 227
 228         pq_getmsgend(buf);
 229
 230         /* finish constructing RangeBound representation */
 231         lower.infinite = (flags & RANGE_LB_INF) != 0;
 232         lower.inclusive = (flags & RANGE_LB_INC) != 0;
 233         lower.lower = true;
 234         upper.infinite = (flags & RANGE_UB_INF) != 0;
 235         upper.inclusive = (flags & RANGE_UB_INC) != 0;
 236         upper.lower = false;
 237
 238         /* serialize and canonicalize */
 239         range = make_range(cache->typcache, &lower, &upper, flags & RANGE_EMPTY);
 240
 241         PG_RETURN_RANGE(range);
 242 }
 243
 244 Datum
 245 range_send(PG_FUNCTION_ARGS)
 246 {
 247         RangeType  *range = PG_GETARG_RANGE(0);
 248         StringInfo      buf = makeStringInfo();
 249         RangeIOData *cache;
 250         char            flags;
 251         RangeBound      lower;
 252         RangeBound      upper;
 253         bool            empty;
 254
 255         check_stack_depth();            /* recurses when subtype is a range type */
 256
 257         cache = get_range_io_data(fcinfo, RangeTypeGetOid(range), IOFunc_send);
 258
 259         /* deserialize */
 260         range_deserialize(cache->typcache, range, &lower, &upper, &empty);
 261         flags = range_get_flags(range);
 262
 263         /* construct output */
 264         pq_begintypsend(buf);
 265
 266         pq_sendbyte(buf, flags);
 267
 268         if (RANGE_HAS_LBOUND(flags))
 269         {
 270                 Datum           bound = PointerGetDatum(SendFunctionCall(&cache->proc,
 271                                                                                                                          lower.val));
 272                 uint32          bound_len = VARSIZE(bound) - VARHDRSZ;
 273                 char       *bound_data = VARDATA(bound);
 274
 275                 pq_sendint(buf, bound_len, 4);
 276                 pq_sendbytes(buf, bound_data, bound_len);
 277         }
 278
 279         if (RANGE_HAS_UBOUND(flags))
 280         {
 281                 Datum           bound = PointerGetDatum(SendFunctionCall(&cache->proc,
 282                                                                                                                          upper.val));
 283                 uint32          bound_len = VARSIZE(bound) - VARHDRSZ;
 284                 char       *bound_data = VARDATA(bound);
 285
 286                 pq_sendint(buf, bound_len, 4);
 287                 pq_sendbytes(buf, bound_data, bound_len);
 288         }
 289
 290         PG_RETURN_BYTEA_P(pq_endtypsend(buf));
 291 }
 292
 293 /*
 294  * get_range_io_data: get cached information needed for range type I/O
 295  *
 296  * The range I/O functions need a bit more cached info than other range
 297  * functions, so they store a RangeIOData struct in fn_extra, not just a
 298  * pointer to a type cache entry.
 299  */
 300 static RangeIOData *
 301 get_range_io_data(FunctionCallInfo fcinfo, Oid rngtypid, IOFuncSelector func)
 302 {
 303         RangeIOData *cache = (RangeIOData *) fcinfo->flinfo->fn_extra;
 304
 305         if (cache == NULL || cache->typcache->type_id != rngtypid)
 306         {
 307                 int16           typlen;
 308                 bool            typbyval;
 309                 char            typalign;
 310                 char            typdelim;
 311
 312                 cache = (RangeIOData *) MemoryContextAlloc(fcinfo->flinfo->fn_mcxt,
 313                                                                                                    sizeof(RangeIOData));
 314                 cache->typcache = lookup_type_cache(rngtypid, TYPECACHE_RANGE_INFO);
 315                 if (cache->typcache->rngelemtype == NULL)
 316                         elog(ERROR, "type %u is not a range type", rngtypid);
 317
 318                 /* get_type_io_data does more than we need, but is convenient */
 319                 get_type_io_data(cache->typcache->rngelemtype->type_id,
 320                                                  func,
 321                                                  &typlen,
 322                                                  &typbyval,
 323                                                  &typalign,
 324                                                  &typdelim,
 325                                                  &cache->typioparam,
 326                                                  &cache->typiofunc);
 327
 328                 if (!OidIsValid(cache->typiofunc))
 329                 {
 330                         /* this could only happen for receive or send */
 331                         if (func == IOFunc_receive)
 332                                 ereport(ERROR,
 333                                                 (errcode(ERRCODE_UNDEFINED_FUNCTION),
 334                                          errmsg("no binary input function available for type %s",
 335                                         format_type_be(cache->typcache->rngelemtype->type_id))));
 336                         else
 337                                 ereport(ERROR,
 338                                                 (errcode(ERRCODE_UNDEFINED_FUNCTION),
 339                                         errmsg("no binary output function available for type %s",
 340                                         format_type_be(cache->typcache->rngelemtype->type_id))));
 341                 }
 342                 fmgr_info_cxt(cache->typiofunc, &cache->proc,
 343                                           fcinfo->flinfo->fn_mcxt);
 344
 345                 fcinfo->flinfo->fn_extra = (void *) cache;
 346         }
 347
 348         return cache;
 349 }
 350
 351
 352 /*
 353  *----------------------------------------------------------
 354  * GENERIC FUNCTIONS
 355  *----------------------------------------------------------
 356  */
 357
 358 /* Construct standard-form range value from two arguments */
 359 Datum
 360 range_constructor2(PG_FUNCTION_ARGS)
 361 {
 362         Datum           arg1 = PG_GETARG_DATUM(0);
 363         Datum           arg2 = PG_GETARG_DATUM(1);
 364         Oid                     rngtypid = get_fn_expr_rettype(fcinfo->flinfo);
 365         RangeType  *range;
 366         TypeCacheEntry *typcache;
 367         RangeBound      lower;
 368         RangeBound      upper;
 369
 370         typcache = range_get_typcache(fcinfo, rngtypid);
 371
 372         lower.val = PG_ARGISNULL(0) ? (Datum) 0 : arg1;
 373         lower.infinite = PG_ARGISNULL(0);
 374         lower.inclusive = true;
 375         lower.lower = true;
 376
 377         upper.val = PG_ARGISNULL(1) ? (Datum) 0 : arg2;
 378         upper.infinite = PG_ARGISNULL(1);
 379         upper.inclusive = false;
 380         upper.lower = false;
 381
 382         range = make_range(typcache, &lower, &upper, false);
 383
 384         PG_RETURN_RANGE(range);
 385 }
 386
 387 /* Construct general range value from three arguments */
 388 Datum
 389 range_constructor3(PG_FUNCTION_ARGS)
 390 {
 391         Datum           arg1 = PG_GETARG_DATUM(0);
 392         Datum           arg2 = PG_GETARG_DATUM(1);
 393         Oid                     rngtypid = get_fn_expr_rettype(fcinfo->flinfo);
 394         RangeType  *range;
 395         TypeCacheEntry *typcache;
 396         RangeBound      lower;
 397         RangeBound      upper;
 398         char            flags;
 399
 400         typcache = range_get_typcache(fcinfo, rngtypid);
 401
 402         if (PG_ARGISNULL(2))
 403                 ereport(ERROR,
 404                                 (errcode(ERRCODE_DATA_EXCEPTION),
 405                            errmsg("range constructor flags argument must not be null")));
 406
 407         flags = range_parse_flags(text_to_cstring(PG_GETARG_TEXT_PP(2)));
 408
 409         lower.val = PG_ARGISNULL(0) ? (Datum) 0 : arg1;
 410         lower.infinite = PG_ARGISNULL(0);
 411         lower.inclusive = (flags & RANGE_LB_INC) != 0;
 412         lower.lower = true;
 413
 414         upper.val = PG_ARGISNULL(1) ? (Datum) 0 : arg2;
 415         upper.infinite = PG_ARGISNULL(1);
 416         upper.inclusive = (flags & RANGE_UB_INC) != 0;
 417         upper.lower = false;
 418
 419         range = make_range(typcache, &lower, &upper, false);
 420
 421         PG_RETURN_RANGE(range);
 422 }
 423
 424
 425 /* range -> subtype functions */
 426
 427 /* extract lower bound value */
 428 Datum
 429 range_lower(PG_FUNCTION_ARGS)
 430 {
 431         RangeType  *r1 = PG_GETARG_RANGE(0);
 432         TypeCacheEntry *typcache;
 433         RangeBound      lower;
 434         RangeBound      upper;
 435         bool            empty;
 436
 437         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 438
 439         range_deserialize(typcache, r1, &lower, &upper, &empty);
 440
 441         /* Return NULL if there's no finite lower bound */
 442         if (empty || lower.infinite)
 443                 PG_RETURN_NULL();
 444
 445         PG_RETURN_DATUM(lower.val);
 446 }
 447
 448 /* extract upper bound value */
 449 Datum
 450 range_upper(PG_FUNCTION_ARGS)
 451 {
 452         RangeType  *r1 = PG_GETARG_RANGE(0);
 453         TypeCacheEntry *typcache;
 454         RangeBound      lower;
 455         RangeBound      upper;
 456         bool            empty;
 457
 458         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 459
 460         range_deserialize(typcache, r1, &lower, &upper, &empty);
 461
 462         /* Return NULL if there's no finite upper bound */
 463         if (empty || upper.infinite)
 464                 PG_RETURN_NULL();
 465
 466         PG_RETURN_DATUM(upper.val);
 467 }
 468
 469
 470 /* range -> bool functions */
 471
 472 /* is range empty? */
 473 Datum
 474 range_empty(PG_FUNCTION_ARGS)
 475 {
 476         RangeType  *r1 = PG_GETARG_RANGE(0);
 477         char            flags = range_get_flags(r1);
 478
 479         PG_RETURN_BOOL(flags & RANGE_EMPTY);
 480 }
 481
 482 /* is lower bound inclusive? */
 483 Datum
 484 range_lower_inc(PG_FUNCTION_ARGS)
 485 {
 486         RangeType  *r1 = PG_GETARG_RANGE(0);
 487         char            flags = range_get_flags(r1);
 488
 489         PG_RETURN_BOOL(flags & RANGE_LB_INC);
 490 }
 491
 492 /* is upper bound inclusive? */
 493 Datum
 494 range_upper_inc(PG_FUNCTION_ARGS)
 495 {
 496         RangeType  *r1 = PG_GETARG_RANGE(0);
 497         char            flags = range_get_flags(r1);
 498
 499         PG_RETURN_BOOL(flags & RANGE_UB_INC);
 500 }
 501
 502 /* is lower bound infinite? */
 503 Datum
 504 range_lower_inf(PG_FUNCTION_ARGS)
 505 {
 506         RangeType  *r1 = PG_GETARG_RANGE(0);
 507         char            flags = range_get_flags(r1);
 508
 509         PG_RETURN_BOOL(flags & RANGE_LB_INF);
 510 }
 511
 512 /* is upper bound infinite? */
 513 Datum
 514 range_upper_inf(PG_FUNCTION_ARGS)
 515 {
 516         RangeType  *r1 = PG_GETARG_RANGE(0);
 517         char            flags = range_get_flags(r1);
 518
 519         PG_RETURN_BOOL(flags & RANGE_UB_INF);
 520 }
 521
 522
 523 /* range, element -> bool functions */
 524
 525 /* contains? */
 526 Datum
 527 range_contains_elem(PG_FUNCTION_ARGS)
 528 {
 529         RangeType  *r = PG_GETARG_RANGE(0);
 530         Datum           val = PG_GETARG_DATUM(1);
 531         TypeCacheEntry *typcache;
 532
 533         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
 534
 535         PG_RETURN_BOOL(range_contains_elem_internal(typcache, r, val));
 536 }
 537
 538 /* contained by? */
 539 Datum
 540 elem_contained_by_range(PG_FUNCTION_ARGS)
 541 {
 542         Datum           val = PG_GETARG_DATUM(0);
 543         RangeType  *r = PG_GETARG_RANGE(1);
 544         TypeCacheEntry *typcache;
 545
 546         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
 547
 548         PG_RETURN_BOOL(range_contains_elem_internal(typcache, r, val));
 549 }
 550
 551
 552 /* range, range -> bool functions */
 553
 554 /* equality (internal version) */
 555 bool
 556 range_eq_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 557 {
 558         RangeBound      lower1,
 559                                 lower2;
 560         RangeBound      upper1,
 561                                 upper2;
 562         bool            empty1,
 563                                 empty2;
 564
 565         /* Different types should be prevented by ANYRANGE matching rules */
 566         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 567                 elog(ERROR, "range types do not match");
 568
 569         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 570         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 571
 572         if (empty1 && empty2)
 573                 return true;
 574         if (empty1 != empty2)
 575                 return false;
 576
 577         if (range_cmp_bounds(typcache, &lower1, &lower2) != 0)
 578                 return false;
 579
 580         if (range_cmp_bounds(typcache, &upper1, &upper2) != 0)
 581                 return false;
 582
 583         return true;
 584 }
 585
 586 /* equality */
 587 Datum
 588 range_eq(PG_FUNCTION_ARGS)
 589 {
 590         RangeType  *r1 = PG_GETARG_RANGE(0);
 591         RangeType  *r2 = PG_GETARG_RANGE(1);
 592         TypeCacheEntry *typcache;
 593
 594         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 595
 596         PG_RETURN_BOOL(range_eq_internal(typcache, r1, r2));
 597 }
 598
 599 /* inequality (internal version) */
 600 bool
 601 range_ne_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 602 {
 603         return (!range_eq_internal(typcache, r1, r2));
 604 }
 605
 606 /* inequality */
 607 Datum
 608 range_ne(PG_FUNCTION_ARGS)
 609 {
 610         RangeType  *r1 = PG_GETARG_RANGE(0);
 611         RangeType  *r2 = PG_GETARG_RANGE(1);
 612         TypeCacheEntry *typcache;
 613
 614         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 615
 616         PG_RETURN_BOOL(range_ne_internal(typcache, r1, r2));
 617 }
 618
 619 /* contains? */
 620 Datum
 621 range_contains(PG_FUNCTION_ARGS)
 622 {
 623         RangeType  *r1 = PG_GETARG_RANGE(0);
 624         RangeType  *r2 = PG_GETARG_RANGE(1);
 625         TypeCacheEntry *typcache;
 626
 627         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 628
 629         PG_RETURN_BOOL(range_contains_internal(typcache, r1, r2));
 630 }
 631
 632 /* contained by? */
 633 Datum
 634 range_contained_by(PG_FUNCTION_ARGS)
 635 {
 636         RangeType  *r1 = PG_GETARG_RANGE(0);
 637         RangeType  *r2 = PG_GETARG_RANGE(1);
 638         TypeCacheEntry *typcache;
 639
 640         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 641
 642         PG_RETURN_BOOL(range_contained_by_internal(typcache, r1, r2));
 643 }
 644
 645 /* strictly left of? (internal version) */
 646 bool
 647 range_before_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 648 {
 649         RangeBound      lower1,
 650                                 lower2;
 651         RangeBound      upper1,
 652                                 upper2;
 653         bool            empty1,
 654                                 empty2;
 655
 656         /* Different types should be prevented by ANYRANGE matching rules */
 657         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 658                 elog(ERROR, "range types do not match");
 659
 660         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 661         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 662
 663         /* An empty range is neither before nor after any other range */
 664         if (empty1 || empty2)
 665                 return false;
 666
 667         return (range_cmp_bounds(typcache, &upper1, &lower2) < 0);
 668 }
 669
 670 /* strictly left of? */
 671 Datum
 672 range_before(PG_FUNCTION_ARGS)
 673 {
 674         RangeType  *r1 = PG_GETARG_RANGE(0);
 675         RangeType  *r2 = PG_GETARG_RANGE(1);
 676         TypeCacheEntry *typcache;
 677
 678         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 679
 680         PG_RETURN_BOOL(range_before_internal(typcache, r1, r2));
 681 }
 682
 683 /* strictly right of? (internal version) */
 684 bool
 685 range_after_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 686 {
 687         RangeBound      lower1,
 688                                 lower2;
 689         RangeBound      upper1,
 690                                 upper2;
 691         bool            empty1,
 692                                 empty2;
 693
 694         /* Different types should be prevented by ANYRANGE matching rules */
 695         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 696                 elog(ERROR, "range types do not match");
 697
 698         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 699         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 700
 701         /* An empty range is neither before nor after any other range */
 702         if (empty1 || empty2)
 703                 return false;
 704
 705         return (range_cmp_bounds(typcache, &lower1, &upper2) > 0);
 706 }
 707
 708 /* strictly right of? */
 709 Datum
 710 range_after(PG_FUNCTION_ARGS)
 711 {
 712         RangeType  *r1 = PG_GETARG_RANGE(0);
 713         RangeType  *r2 = PG_GETARG_RANGE(1);
 714         TypeCacheEntry *typcache;
 715
 716         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 717
 718         PG_RETURN_BOOL(range_after_internal(typcache, r1, r2));
 719 }
 720
 721 /*
 722  * Check if two bounds A and B are "adjacent", where A is an upper bound and B
 723  * is a lower bound. For the bounds to be adjacent, each subtype value must
 724  * satisfy strictly one of the bounds: there are no values which satisfy both
 725  * bounds (i.e. less than A and greater than B); and there are no values which
 726  * satisfy neither bound (i.e. greater than A and less than B).
 727  *
 728  * For discrete ranges, we rely on the canonicalization function to see if A..B
 729  * normalizes to empty. (If there is no canonicalization function, it's
 730  * impossible for such a range to normalize to empty, so we needn't bother to
 731  * try.)
 732  *
 733  * If A == B, the ranges are adjacent only if the bounds have different
 734  * inclusive flags (i.e., exactly one of the ranges includes the common
 735  * boundary point).
 736  *
 737  * And if A > B then the ranges are not adjacent in this order.
 738  */
 739 bool
 740 bounds_adjacent(TypeCacheEntry *typcache, RangeBound boundA, RangeBound boundB)
 741 {
 742         int                     cmp;
 743
 744         Assert(!boundA.lower && boundB.lower);
 745
 746         cmp = range_cmp_bound_values(typcache, &boundA, &boundB);
 747         if (cmp < 0)
 748         {
 749                 RangeType  *r;
 750
 751                 /*
 752                  * Bounds do not overlap; see if there are points in between.
 753                  */
 754
 755                 /* in a continuous subtype, there are assumed to be points between */
 756                 if (!OidIsValid(typcache->rng_canonical_finfo.fn_oid))
 757                         return false;
 758
 759                 /*
 760                  * The bounds are of a discrete range type; so make a range A..B and
 761                  * see if it's empty.
 762                  */
 763
 764                 /* flip the inclusion flags */
 765                 boundA.inclusive = !boundA.inclusive;
 766                 boundB.inclusive = !boundB.inclusive;
 767                 /* change upper/lower labels to avoid Assert failures */
 768                 boundA.lower = true;
 769                 boundB.lower = false;
 770                 r = make_range(typcache, &boundA, &boundB, false);
 771                 return RangeIsEmpty(r);
 772         }
 773         else if (cmp == 0)
 774                 return boundA.inclusive != boundB.inclusive;
 775         else
 776                 return false;                   /* bounds overlap */
 777 }
 778
 779 /* adjacent to (but not overlapping)? (internal version) */
 780 bool
 781 range_adjacent_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 782 {
 783         RangeBound      lower1,
 784                                 lower2;
 785         RangeBound      upper1,
 786                                 upper2;
 787         bool            empty1,
 788                                 empty2;
 789
 790         /* Different types should be prevented by ANYRANGE matching rules */
 791         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 792                 elog(ERROR, "range types do not match");
 793
 794         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 795         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 796
 797         /* An empty range is not adjacent to any other range */
 798         if (empty1 || empty2)
 799                 return false;
 800
 801         /*
 802          * Given two ranges A..B and C..D, the ranges are adjacent if and only if
 803          * B is adjacent to C, or D is adjacent to A.
 804          */
 805         return (bounds_adjacent(typcache, upper1, lower2) ||
 806                         bounds_adjacent(typcache, upper2, lower1));
 807 }
 808
 809 /* adjacent to (but not overlapping)? */
 810 Datum
 811 range_adjacent(PG_FUNCTION_ARGS)
 812 {
 813         RangeType  *r1 = PG_GETARG_RANGE(0);
 814         RangeType  *r2 = PG_GETARG_RANGE(1);
 815         TypeCacheEntry *typcache;
 816
 817         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 818
 819         PG_RETURN_BOOL(range_adjacent_internal(typcache, r1, r2));
 820 }
 821
 822 /* overlaps? (internal version) */
 823 bool
 824 range_overlaps_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 825 {
 826         RangeBound      lower1,
 827                                 lower2;
 828         RangeBound      upper1,
 829                                 upper2;
 830         bool            empty1,
 831                                 empty2;
 832
 833         /* Different types should be prevented by ANYRANGE matching rules */
 834         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 835                 elog(ERROR, "range types do not match");
 836
 837         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 838         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 839
 840         /* An empty range does not overlap any other range */
 841         if (empty1 || empty2)
 842                 return false;
 843
 844         if (range_cmp_bounds(typcache, &lower1, &lower2) >= 0 &&
 845                 range_cmp_bounds(typcache, &lower1, &upper2) <= 0)
 846                 return true;
 847
 848         if (range_cmp_bounds(typcache, &lower2, &lower1) >= 0 &&
 849                 range_cmp_bounds(typcache, &lower2, &upper1) <= 0)
 850                 return true;
 851
 852         return false;
 853 }
 854
 855 /* overlaps? */
 856 Datum
 857 range_overlaps(PG_FUNCTION_ARGS)
 858 {
 859         RangeType  *r1 = PG_GETARG_RANGE(0);
 860         RangeType  *r2 = PG_GETARG_RANGE(1);
 861         TypeCacheEntry *typcache;
 862
 863         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 864
 865         PG_RETURN_BOOL(range_overlaps_internal(typcache, r1, r2));
 866 }
 867
 868 /* does not extend to right of? (internal version) */
 869 bool
 870 range_overleft_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 871 {
 872         RangeBound      lower1,
 873                                 lower2;
 874         RangeBound      upper1,
 875                                 upper2;
 876         bool            empty1,
 877                                 empty2;
 878
 879         /* Different types should be prevented by ANYRANGE matching rules */
 880         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 881                 elog(ERROR, "range types do not match");
 882
 883         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 884         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 885
 886         /* An empty range is neither before nor after any other range */
 887         if (empty1 || empty2)
 888                 return false;
 889
 890         if (range_cmp_bounds(typcache, &upper1, &upper2) <= 0)
 891                 return true;
 892
 893         return false;
 894 }
 895
 896 /* does not extend to right of? */
 897 Datum
 898 range_overleft(PG_FUNCTION_ARGS)
 899 {
 900         RangeType  *r1 = PG_GETARG_RANGE(0);
 901         RangeType  *r2 = PG_GETARG_RANGE(1);
 902         TypeCacheEntry *typcache;
 903
 904         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 905
 906         PG_RETURN_BOOL(range_overleft_internal(typcache, r1, r2));
 907 }
 908
 909 /* does not extend to left of? (internal version) */
 910 bool
 911 range_overright_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
 912 {
 913         RangeBound      lower1,
 914                                 lower2;
 915         RangeBound      upper1,
 916                                 upper2;
 917         bool            empty1,
 918                                 empty2;
 919
 920         /* Different types should be prevented by ANYRANGE matching rules */
 921         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 922                 elog(ERROR, "range types do not match");
 923
 924         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 925         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 926
 927         /* An empty range is neither before nor after any other range */
 928         if (empty1 || empty2)
 929                 return false;
 930
 931         if (range_cmp_bounds(typcache, &lower1, &lower2) >= 0)
 932                 return true;
 933
 934         return false;
 935 }
 936
 937 /* does not extend to left of? */
 938 Datum
 939 range_overright(PG_FUNCTION_ARGS)
 940 {
 941         RangeType  *r1 = PG_GETARG_RANGE(0);
 942         RangeType  *r2 = PG_GETARG_RANGE(1);
 943         TypeCacheEntry *typcache;
 944
 945         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 946
 947         PG_RETURN_BOOL(range_overright_internal(typcache, r1, r2));
 948 }
 949
 950
 951 /* range, range -> range functions */
 952
 953 /* set difference */
 954 Datum
 955 range_minus(PG_FUNCTION_ARGS)
 956 {
 957         RangeType  *r1 = PG_GETARG_RANGE(0);
 958         RangeType  *r2 = PG_GETARG_RANGE(1);
 959         TypeCacheEntry *typcache;
 960         RangeBound      lower1,
 961                                 lower2;
 962         RangeBound      upper1,
 963                                 upper2;
 964         bool            empty1,
 965                                 empty2;
 966         int                     cmp_l1l2,
 967                                 cmp_l1u2,
 968                                 cmp_u1l2,
 969                                 cmp_u1u2;
 970
 971         /* Different types should be prevented by ANYRANGE matching rules */
 972         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
 973                 elog(ERROR, "range types do not match");
 974
 975         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
 976
 977         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
 978         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
 979
 980         /* if either is empty, r1 is the correct answer */
 981         if (empty1 || empty2)
 982                 PG_RETURN_RANGE(r1);
 983
 984         cmp_l1l2 = range_cmp_bounds(typcache, &lower1, &lower2);
 985         cmp_l1u2 = range_cmp_bounds(typcache, &lower1, &upper2);
 986         cmp_u1l2 = range_cmp_bounds(typcache, &upper1, &lower2);
 987         cmp_u1u2 = range_cmp_bounds(typcache, &upper1, &upper2);
 988
 989         if (cmp_l1l2 < 0 && cmp_u1u2 > 0)
 990                 ereport(ERROR,
 991                                 (errcode(ERRCODE_DATA_EXCEPTION),
 992                           errmsg("result of range difference would not be contiguous")));
 993
 994         if (cmp_l1u2 > 0 || cmp_u1l2 < 0)
 995                 PG_RETURN_RANGE(r1);
 996
 997         if (cmp_l1l2 >= 0 && cmp_u1u2 <= 0)
 998                 PG_RETURN_RANGE(make_empty_range(typcache));
 999
1000         if (cmp_l1l2 <= 0 && cmp_u1l2 >= 0 && cmp_u1u2 <= 0)
1001         {
1002                 lower2.inclusive = !lower2.inclusive;
1003                 lower2.lower = false;   /* it will become the upper bound */
1004                 PG_RETURN_RANGE(make_range(typcache, &lower1, &lower2, false));
1005         }
1006
1007         if (cmp_l1l2 >= 0 && cmp_u1u2 >= 0 && cmp_l1u2 <= 0)
1008         {
1009                 upper2.inclusive = !upper2.inclusive;
1010                 upper2.lower = true;    /* it will become the lower bound */
1011                 PG_RETURN_RANGE(make_range(typcache, &upper2, &upper1, false));
1012         }
1013
1014         elog(ERROR, "unexpected case in range_minus");
1015         PG_RETURN_NULL();
1016 }
1017
1018 /*
1019  * Set union.  If strict is true, it is an error that the two input ranges
1020  * are not adjacent or overlapping.
1021  */
1022 static RangeType *
1023 range_union_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2,
1024                                          bool strict)
1025 {
1026         RangeBound      lower1,
1027                                 lower2;
1028         RangeBound      upper1,
1029                                 upper2;
1030         bool            empty1,
1031                                 empty2;
1032         RangeBound *result_lower;
1033         RangeBound *result_upper;
1034
1035         /* Different types should be prevented by ANYRANGE matching rules */
1036         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
1037                 elog(ERROR, "range types do not match");
1038
1039         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
1040         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
1041
1042         /* if either is empty, the other is the correct answer */
1043         if (empty1)
1044                 return r2;
1045         if (empty2)
1046                 return r1;
1047
1048         if (strict &&
1049                 !DatumGetBool(range_overlaps_internal(typcache, r1, r2)) &&
1050                 !DatumGetBool(range_adjacent_internal(typcache, r1, r2)))
1051                 ereport(ERROR,
1052                                 (errcode(ERRCODE_DATA_EXCEPTION),
1053                                  errmsg("result of range union would not be contiguous")));
1054
1055         if (range_cmp_bounds(typcache, &lower1, &lower2) < 0)
1056                 result_lower = &lower1;
1057         else
1058                 result_lower = &lower2;
1059
1060         if (range_cmp_bounds(typcache, &upper1, &upper2) > 0)
1061                 result_upper = &upper1;
1062         else
1063                 result_upper = &upper2;
1064
1065         return make_range(typcache, result_lower, result_upper, false);
1066 }
1067
1068 Datum
1069 range_union(PG_FUNCTION_ARGS)
1070 {
1071         RangeType  *r1 = PG_GETARG_RANGE(0);
1072         RangeType  *r2 = PG_GETARG_RANGE(1);
1073         TypeCacheEntry *typcache;
1074
1075         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
1076
1077         PG_RETURN_RANGE(range_union_internal(typcache, r1, r2, true));
1078 }
1079
1080 /*
1081  * range merge: like set union, except also allow and account for non-adjacent
1082  * input ranges.
1083  */
1084 Datum
1085 range_merge(PG_FUNCTION_ARGS)
1086 {
1087         RangeType  *r1 = PG_GETARG_RANGE(0);
1088         RangeType  *r2 = PG_GETARG_RANGE(1);
1089         TypeCacheEntry *typcache;
1090
1091         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
1092
1093         PG_RETURN_RANGE(range_union_internal(typcache, r1, r2, false));
1094 }
1095
1096 /* set intersection */
1097 Datum
1098 range_intersect(PG_FUNCTION_ARGS)
1099 {
1100         RangeType  *r1 = PG_GETARG_RANGE(0);
1101         RangeType  *r2 = PG_GETARG_RANGE(1);
1102         TypeCacheEntry *typcache;
1103         RangeBound      lower1,
1104                                 lower2;
1105         RangeBound      upper1,
1106                                 upper2;
1107         bool            empty1,
1108                                 empty2;
1109         RangeBound *result_lower;
1110         RangeBound *result_upper;
1111
1112         /* Different types should be prevented by ANYRANGE matching rules */
1113         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
1114                 elog(ERROR, "range types do not match");
1115
1116         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
1117
1118         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
1119         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
1120
1121         if (empty1 || empty2 || !DatumGetBool(range_overlaps(fcinfo)))
1122                 PG_RETURN_RANGE(make_empty_range(typcache));
1123
1124         if (range_cmp_bounds(typcache, &lower1, &lower2) >= 0)
1125                 result_lower = &lower1;
1126         else
1127                 result_lower = &lower2;
1128
1129         if (range_cmp_bounds(typcache, &upper1, &upper2) <= 0)
1130                 result_upper = &upper1;
1131         else
1132                 result_upper = &upper2;
1133
1134         PG_RETURN_RANGE(make_range(typcache, result_lower, result_upper, false));
1135 }
1136
1137 /* Btree support */
1138
1139 /* btree comparator */
1140 Datum
1141 range_cmp(PG_FUNCTION_ARGS)
1142 {
1143         RangeType  *r1 = PG_GETARG_RANGE(0);
1144         RangeType  *r2 = PG_GETARG_RANGE(1);
1145         TypeCacheEntry *typcache;
1146         RangeBound      lower1,
1147                                 lower2;
1148         RangeBound      upper1,
1149                                 upper2;
1150         bool            empty1,
1151                                 empty2;
1152         int                     cmp;
1153
1154         check_stack_depth();            /* recurses when subtype is a range type */
1155
1156         /* Different types should be prevented by ANYRANGE matching rules */
1157         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
1158                 elog(ERROR, "range types do not match");
1159
1160         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r1));
1161
1162         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
1163         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
1164
1165         /* For b-tree use, empty ranges sort before all else */
1166         if (empty1 && empty2)
1167                 cmp = 0;
1168         else if (empty1)
1169                 cmp = -1;
1170         else if (empty2)
1171                 cmp = 1;
1172         else
1173         {
1174                 cmp = range_cmp_bounds(typcache, &lower1, &lower2);
1175                 if (cmp == 0)
1176                         cmp = range_cmp_bounds(typcache, &upper1, &upper2);
1177         }
1178
1179         PG_FREE_IF_COPY(r1, 0);
1180         PG_FREE_IF_COPY(r2, 1);
1181
1182         PG_RETURN_INT32(cmp);
1183 }
1184
1185 /* inequality operators using the range_cmp function */
1186 Datum
1187 range_lt(PG_FUNCTION_ARGS)
1188 {
1189         int                     cmp = range_cmp(fcinfo);
1190
1191         PG_RETURN_BOOL(cmp < 0);
1192 }
1193
1194 Datum
1195 range_le(PG_FUNCTION_ARGS)
1196 {
1197         int                     cmp = range_cmp(fcinfo);
1198
1199         PG_RETURN_BOOL(cmp <= 0);
1200 }
1201
1202 Datum
1203 range_ge(PG_FUNCTION_ARGS)
1204 {
1205         int                     cmp = range_cmp(fcinfo);
1206
1207         PG_RETURN_BOOL(cmp >= 0);
1208 }
1209
1210 Datum
1211 range_gt(PG_FUNCTION_ARGS)
1212 {
1213         int                     cmp = range_cmp(fcinfo);
1214
1215         PG_RETURN_BOOL(cmp > 0);
1216 }
1217
1218 /* Hash support */
1219
1220 /* hash a range value */
1221 Datum
1222 hash_range(PG_FUNCTION_ARGS)
1223 {
1224         RangeType  *r = PG_GETARG_RANGE(0);
1225         uint32          result;
1226         TypeCacheEntry *typcache;
1227         TypeCacheEntry *scache;
1228         RangeBound      lower;
1229         RangeBound      upper;
1230         bool            empty;
1231         char            flags;
1232         uint32          lower_hash;
1233         uint32          upper_hash;
1234
1235         check_stack_depth();            /* recurses when subtype is a range type */
1236
1237         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
1238
1239         /* deserialize */
1240         range_deserialize(typcache, r, &lower, &upper, &empty);
1241         flags = range_get_flags(r);
1242
1243         /*
1244          * Look up the element type's hash function, if not done already.
1245          */
1246         scache = typcache->rngelemtype;
1247         if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
1248         {
1249                 scache = lookup_type_cache(scache->type_id, TYPECACHE_HASH_PROC_FINFO);
1250                 if (!OidIsValid(scache->hash_proc_finfo.fn_oid))
1251                         ereport(ERROR,
1252                                         (errcode(ERRCODE_UNDEFINED_FUNCTION),
1253                                          errmsg("could not identify a hash function for type %s",
1254                                                         format_type_be(scache->type_id))));
1255         }
1256
1257         /*
1258          * Apply the hash function to each bound.
1259          */
1260         if (RANGE_HAS_LBOUND(flags))
1261                 lower_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
1262                                                                                                           typcache->rng_collation,
1263                                                                                                           lower.val));
1264         else
1265                 lower_hash = 0;
1266
1267         if (RANGE_HAS_UBOUND(flags))
1268                 upper_hash = DatumGetUInt32(FunctionCall1Coll(&scache->hash_proc_finfo,
1269                                                                                                           typcache->rng_collation,
1270                                                                                                           upper.val));
1271         else
1272                 upper_hash = 0;
1273
1274         /* Merge hashes of flags and bounds */
1275         result = hash_uint32((uint32) flags);
1276         result ^= lower_hash;
1277         result = (result << 1) | (result >> 31);
1278         result ^= upper_hash;
1279
1280         PG_RETURN_INT32(result);
1281 }
1282
1283 /*
1284  *----------------------------------------------------------
1285  * CANONICAL FUNCTIONS
1286  *
1287  *       Functions for specific built-in range types.
1288  *----------------------------------------------------------
1289  */
1290
1291 Datum
1292 int4range_canonical(PG_FUNCTION_ARGS)
1293 {
1294         RangeType  *r = PG_GETARG_RANGE(0);
1295         TypeCacheEntry *typcache;
1296         RangeBound      lower;
1297         RangeBound      upper;
1298         bool            empty;
1299
1300         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
1301
1302         range_deserialize(typcache, r, &lower, &upper, &empty);
1303
1304         if (empty)
1305                 PG_RETURN_RANGE(r);
1306
1307         if (!lower.infinite && !lower.inclusive)
1308         {
1309                 lower.val = DirectFunctionCall2(int4pl, lower.val, Int32GetDatum(1));
1310                 lower.inclusive = true;
1311         }
1312
1313         if (!upper.infinite && upper.inclusive)
1314         {
1315                 upper.val = DirectFunctionCall2(int4pl, upper.val, Int32GetDatum(1));
1316                 upper.inclusive = false;
1317         }
1318
1319         PG_RETURN_RANGE(range_serialize(typcache, &lower, &upper, false));
1320 }
1321
1322 Datum
1323 int8range_canonical(PG_FUNCTION_ARGS)
1324 {
1325         RangeType  *r = PG_GETARG_RANGE(0);
1326         TypeCacheEntry *typcache;
1327         RangeBound      lower;
1328         RangeBound      upper;
1329         bool            empty;
1330
1331         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
1332
1333         range_deserialize(typcache, r, &lower, &upper, &empty);
1334
1335         if (empty)
1336                 PG_RETURN_RANGE(r);
1337
1338         if (!lower.infinite && !lower.inclusive)
1339         {
1340                 lower.val = DirectFunctionCall2(int8pl, lower.val, Int64GetDatum(1));
1341                 lower.inclusive = true;
1342         }
1343
1344         if (!upper.infinite && upper.inclusive)
1345         {
1346                 upper.val = DirectFunctionCall2(int8pl, upper.val, Int64GetDatum(1));
1347                 upper.inclusive = false;
1348         }
1349
1350         PG_RETURN_RANGE(range_serialize(typcache, &lower, &upper, false));
1351 }
1352
1353 Datum
1354 daterange_canonical(PG_FUNCTION_ARGS)
1355 {
1356         RangeType  *r = PG_GETARG_RANGE(0);
1357         TypeCacheEntry *typcache;
1358         RangeBound      lower;
1359         RangeBound      upper;
1360         bool            empty;
1361
1362         typcache = range_get_typcache(fcinfo, RangeTypeGetOid(r));
1363
1364         range_deserialize(typcache, r, &lower, &upper, &empty);
1365
1366         if (empty)
1367                 PG_RETURN_RANGE(r);
1368
1369         if (!lower.infinite && !lower.inclusive)
1370         {
1371                 lower.val = DirectFunctionCall2(date_pli, lower.val, Int32GetDatum(1));
1372                 lower.inclusive = true;
1373         }
1374
1375         if (!upper.infinite && upper.inclusive)
1376         {
1377                 upper.val = DirectFunctionCall2(date_pli, upper.val, Int32GetDatum(1));
1378                 upper.inclusive = false;
1379         }
1380
1381         PG_RETURN_RANGE(range_serialize(typcache, &lower, &upper, false));
1382 }
1383
1384 /*
1385  *----------------------------------------------------------
1386  * SUBTYPE_DIFF FUNCTIONS
1387  *
1388  * Functions for specific built-in range types.
1389  *
1390  * Note that subtype_diff does return the difference, not the absolute value
1391  * of the difference, and it must take care to avoid overflow.
1392  * (numrange_subdiff is at some risk there ...)
1393  *----------------------------------------------------------
1394  */
1395
1396 Datum
1397 int4range_subdiff(PG_FUNCTION_ARGS)
1398 {
1399         int32           v1 = PG_GETARG_INT32(0);
1400         int32           v2 = PG_GETARG_INT32(1);
1401
1402         PG_RETURN_FLOAT8((float8) v1 - (float8) v2);
1403 }
1404
1405 Datum
1406 int8range_subdiff(PG_FUNCTION_ARGS)
1407 {
1408         int64           v1 = PG_GETARG_INT64(0);
1409         int64           v2 = PG_GETARG_INT64(1);
1410
1411         PG_RETURN_FLOAT8((float8) v1 - (float8) v2);
1412 }
1413
1414 Datum
1415 numrange_subdiff(PG_FUNCTION_ARGS)
1416 {
1417         Datum           v1 = PG_GETARG_DATUM(0);
1418         Datum           v2 = PG_GETARG_DATUM(1);
1419         Datum           numresult;
1420         float8          floatresult;
1421
1422         numresult = DirectFunctionCall2(numeric_sub, v1, v2);
1423
1424         floatresult = DatumGetFloat8(DirectFunctionCall1(numeric_float8,
1425                                                                                                          numresult));
1426
1427         PG_RETURN_FLOAT8(floatresult);
1428 }
1429
1430 Datum
1431 daterange_subdiff(PG_FUNCTION_ARGS)
1432 {
1433         int32           v1 = PG_GETARG_INT32(0);
1434         int32           v2 = PG_GETARG_INT32(1);
1435
1436         PG_RETURN_FLOAT8((float8) v1 - (float8) v2);
1437 }
1438
1439 Datum
1440 tsrange_subdiff(PG_FUNCTION_ARGS)
1441 {
1442         Timestamp       v1 = PG_GETARG_TIMESTAMP(0);
1443         Timestamp       v2 = PG_GETARG_TIMESTAMP(1);
1444         float8          result;
1445
1446         result = ((float8) v1 - (float8) v2) / USECS_PER_SEC;
1447         PG_RETURN_FLOAT8(result);
1448 }
1449
1450 Datum
1451 tstzrange_subdiff(PG_FUNCTION_ARGS)
1452 {
1453         Timestamp       v1 = PG_GETARG_TIMESTAMP(0);
1454         Timestamp       v2 = PG_GETARG_TIMESTAMP(1);
1455         float8          result;
1456
1457         result = ((float8) v1 - (float8) v2) / USECS_PER_SEC;
1458         PG_RETURN_FLOAT8(result);
1459 }
1460
1461 /*
1462  *----------------------------------------------------------
1463  * SUPPORT FUNCTIONS
1464  *
1465  *       These functions aren't in pg_proc, but are useful for
1466  *       defining new generic range functions in C.
1467  *----------------------------------------------------------
1468  */
1469
1470 /*
1471  * range_get_typcache: get cached information about a range type
1472  *
1473  * This is for use by range-related functions that follow the convention
1474  * of using the fn_extra field as a pointer to the type cache entry for
1475  * the range type.  Functions that need to cache more information than
1476  * that must fend for themselves.
1477  */
1478 TypeCacheEntry *
1479 range_get_typcache(FunctionCallInfo fcinfo, Oid rngtypid)
1480 {
1481         TypeCacheEntry *typcache = (TypeCacheEntry *) fcinfo->flinfo->fn_extra;
1482
1483         if (typcache == NULL ||
1484                 typcache->type_id != rngtypid)
1485         {
1486                 typcache = lookup_type_cache(rngtypid, TYPECACHE_RANGE_INFO);
1487                 if (typcache->rngelemtype == NULL)
1488                         elog(ERROR, "type %u is not a range type", rngtypid);
1489                 fcinfo->flinfo->fn_extra = (void *) typcache;
1490         }
1491
1492         return typcache;
1493 }
1494
1495 /*
1496  * range_serialize: construct a range value from bounds and empty-flag
1497  *
1498  * This does not force canonicalization of the range value.  In most cases,
1499  * external callers should only be canonicalization functions.  Note that
1500  * we perform some datatype-independent canonicalization checks anyway.
1501  */
1502 RangeType *
1503 range_serialize(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper,
1504                                 bool empty)
1505 {
1506         RangeType  *range;
1507         int                     cmp;
1508         Size            msize;
1509         Pointer         ptr;
1510         int16           typlen;
1511         bool            typbyval;
1512         char            typalign;
1513         char            typstorage;
1514         char            flags = 0;
1515
1516         /*
1517          * Verify range is not invalid on its face, and construct flags value,
1518          * preventing any non-canonical combinations such as infinite+inclusive.
1519          */
1520         Assert(lower->lower);
1521         Assert(!upper->lower);
1522
1523         if (empty)
1524                 flags |= RANGE_EMPTY;
1525         else
1526         {
1527                 cmp = range_cmp_bound_values(typcache, lower, upper);
1528
1529                 /* error check: if lower bound value is above upper, it's wrong */
1530                 if (cmp > 0)
1531                         ereport(ERROR,
1532                                         (errcode(ERRCODE_DATA_EXCEPTION),
1533                                          errmsg("range lower bound must be less than or equal to range upper bound")));
1534
1535                 /* if bounds are equal, and not both inclusive, range is empty */
1536                 if (cmp == 0 && !(lower->inclusive && upper->inclusive))
1537                         flags |= RANGE_EMPTY;
1538                 else
1539                 {
1540                         /* infinite boundaries are never inclusive */
1541                         if (lower->infinite)
1542                                 flags |= RANGE_LB_INF;
1543                         else if (lower->inclusive)
1544                                 flags |= RANGE_LB_INC;
1545                         if (upper->infinite)
1546                                 flags |= RANGE_UB_INF;
1547                         else if (upper->inclusive)
1548                                 flags |= RANGE_UB_INC;
1549                 }
1550         }
1551
1552         /* Fetch information about range's element type */
1553         typlen = typcache->rngelemtype->typlen;
1554         typbyval = typcache->rngelemtype->typbyval;
1555         typalign = typcache->rngelemtype->typalign;
1556         typstorage = typcache->rngelemtype->typstorage;
1557
1558         /* Count space for varlena header and range type's OID */
1559         msize = sizeof(RangeType);
1560         Assert(msize == MAXALIGN(msize));
1561
1562         /* Count space for bounds */
1563         if (RANGE_HAS_LBOUND(flags))
1564         {
1565                 /*
1566                  * Make sure item to be inserted is not toasted.  It is essential that
1567                  * we not insert an out-of-line toast value pointer into a range
1568                  * object, for the same reasons that arrays and records can't contain
1569                  * them.  It would work to store a compressed-in-line value, but we
1570                  * prefer to decompress and then let compression be applied to the
1571                  * whole range object if necessary.  But, unlike arrays, we do allow
1572                  * short-header varlena objects to stay as-is.
1573                  */
1574                 if (typlen == -1)
1575                         lower->val = PointerGetDatum(PG_DETOAST_DATUM_PACKED(lower->val));
1576
1577                 msize = datum_compute_size(msize, lower->val, typbyval, typalign,
1578                                                                    typlen, typstorage);
1579         }
1580
1581         if (RANGE_HAS_UBOUND(flags))
1582         {
1583                 /* Make sure item to be inserted is not toasted */
1584                 if (typlen == -1)
1585                         upper->val = PointerGetDatum(PG_DETOAST_DATUM_PACKED(upper->val));
1586
1587                 msize = datum_compute_size(msize, upper->val, typbyval, typalign,
1588                                                                    typlen, typstorage);
1589         }
1590
1591         /* Add space for flag byte */
1592         msize += sizeof(char);
1593
1594         /* Note: zero-fill is required here, just as in heap tuples */
1595         range = (RangeType *) palloc0(msize);
1596         SET_VARSIZE(range, msize);
1597
1598         /* Now fill in the datum */
1599         range->rangetypid = typcache->type_id;
1600
1601         ptr = (char *) (range + 1);
1602
1603         if (RANGE_HAS_LBOUND(flags))
1604         {
1605                 Assert(lower->lower);
1606                 ptr = datum_write(ptr, lower->val, typbyval, typalign, typlen,
1607                                                   typstorage);
1608         }
1609
1610         if (RANGE_HAS_UBOUND(flags))
1611         {
1612                 Assert(!upper->lower);
1613                 ptr = datum_write(ptr, upper->val, typbyval, typalign, typlen,
1614                                                   typstorage);
1615         }
1616
1617         *((char *) ptr) = flags;
1618
1619         return range;
1620 }
1621
1622 /*
1623  * range_deserialize: deconstruct a range value
1624  *
1625  * NB: the given range object must be fully detoasted; it cannot have a
1626  * short varlena header.
1627  *
1628  * Note that if the element type is pass-by-reference, the datums in the
1629  * RangeBound structs will be pointers into the given range object.
1630  */
1631 void
1632 range_deserialize(TypeCacheEntry *typcache, RangeType *range,
1633                                   RangeBound *lower, RangeBound *upper, bool *empty)
1634 {
1635         char            flags;
1636         int16           typlen;
1637         bool            typbyval;
1638         char            typalign;
1639         Pointer         ptr;
1640         Datum           lbound;
1641         Datum           ubound;
1642
1643         /* assert caller passed the right typcache entry */
1644         Assert(RangeTypeGetOid(range) == typcache->type_id);
1645
1646         /* fetch the flag byte from datum's last byte */
1647         flags = *((char *) range + VARSIZE(range) - 1);
1648
1649         /* fetch information about range's element type */
1650         typlen = typcache->rngelemtype->typlen;
1651         typbyval = typcache->rngelemtype->typbyval;
1652         typalign = typcache->rngelemtype->typalign;
1653
1654         /* initialize data pointer just after the range OID */
1655         ptr = (Pointer) (range + 1);
1656
1657         /* fetch lower bound, if any */
1658         if (RANGE_HAS_LBOUND(flags))
1659         {
1660                 /* att_align_pointer cannot be necessary here */
1661                 lbound = fetch_att(ptr, typbyval, typlen);
1662                 ptr = (Pointer) att_addlength_pointer(ptr, typlen, ptr);
1663         }
1664         else
1665                 lbound = (Datum) 0;
1666
1667         /* fetch upper bound, if any */
1668         if (RANGE_HAS_UBOUND(flags))
1669         {
1670                 ptr = (Pointer) att_align_pointer(ptr, typalign, typlen, ptr);
1671                 ubound = fetch_att(ptr, typbyval, typlen);
1672                 /* no need for att_addlength_pointer */
1673         }
1674         else
1675                 ubound = (Datum) 0;
1676
1677         /* emit results */
1678
1679         *empty = (flags & RANGE_EMPTY) != 0;
1680
1681         lower->val = lbound;
1682         lower->infinite = (flags & RANGE_LB_INF) != 0;
1683         lower->inclusive = (flags & RANGE_LB_INC) != 0;
1684         lower->lower = true;
1685
1686         upper->val = ubound;
1687         upper->infinite = (flags & RANGE_UB_INF) != 0;
1688         upper->inclusive = (flags & RANGE_UB_INC) != 0;
1689         upper->lower = false;
1690 }
1691
1692 /*
1693  * range_get_flags: just get the flags from a RangeType value.
1694  *
1695  * This is frequently useful in places that only need the flags and not
1696  * the full results of range_deserialize.
1697  */
1698 char
1699 range_get_flags(RangeType *range)
1700 {
1701         /* fetch the flag byte from datum's last byte */
1702         return *((char *) range + VARSIZE(range) - 1);
1703 }
1704
1705 /*
1706  * range_set_contain_empty: set the RANGE_CONTAIN_EMPTY bit in the value.
1707  *
1708  * This is only needed in GiST operations, so we don't include a provision
1709  * for setting it in range_serialize; rather, this function must be applied
1710  * afterwards.
1711  */
1712 void
1713 range_set_contain_empty(RangeType *range)
1714 {
1715         char       *flagsp;
1716
1717         /* flag byte is datum's last byte */
1718         flagsp = (char *) range + VARSIZE(range) - 1;
1719
1720         *flagsp |= RANGE_CONTAIN_EMPTY;
1721 }
1722
1723 /*
1724  * This both serializes and canonicalizes (if applicable) the range.
1725  * This should be used by most callers.
1726  */
1727 RangeType *
1728 make_range(TypeCacheEntry *typcache, RangeBound *lower, RangeBound *upper,
1729                    bool empty)
1730 {
1731         RangeType  *range;
1732
1733         range = range_serialize(typcache, lower, upper, empty);
1734
1735         /* no need to call canonical on empty ranges ... */
1736         if (OidIsValid(typcache->rng_canonical_finfo.fn_oid) &&
1737                 !RangeIsEmpty(range))
1738                 range = DatumGetRangeType(FunctionCall1(&typcache->rng_canonical_finfo,
1739                                                                                                 RangeTypeGetDatum(range)));
1740
1741         return range;
1742 }
1743
1744 /*
1745  * Compare two range boundary points, returning <0, 0, or >0 according to
1746  * whether b1 is less than, equal to, or greater than b2.
1747  *
1748  * The boundaries can be any combination of upper and lower; so it's useful
1749  * for a variety of operators.
1750  *
1751  * The simple case is when b1 and b2 are both finite and inclusive, in which
1752  * case the result is just a comparison of the values held in b1 and b2.
1753  *
1754  * If a bound is exclusive, then we need to know whether it's a lower bound,
1755  * in which case we treat the boundary point as "just greater than" the held
1756  * value; or an upper bound, in which case we treat the boundary point as
1757  * "just less than" the held value.
1758  *
1759  * If a bound is infinite, it represents minus infinity (less than every other
1760  * point) if it's a lower bound; or plus infinity (greater than every other
1761  * point) if it's an upper bound.
1762  *
1763  * There is only one case where two boundaries compare equal but are not
1764  * identical: when both bounds are inclusive and hold the same finite value,
1765  * but one is an upper bound and the other a lower bound.
1766  */
1767 int
1768 range_cmp_bounds(TypeCacheEntry *typcache, RangeBound *b1, RangeBound *b2)
1769 {
1770         int32           result;
1771
1772         /*
1773          * First, handle cases involving infinity, which don't require invoking
1774          * the comparison proc.
1775          */
1776         if (b1->infinite && b2->infinite)
1777         {
1778                 /*
1779                  * Both are infinity, so they are equal unless one is lower and the
1780                  * other not.
1781                  */
1782                 if (b1->lower == b2->lower)
1783                         return 0;
1784                 else
1785                         return b1->lower ? -1 : 1;
1786         }
1787         else if (b1->infinite)
1788                 return b1->lower ? -1 : 1;
1789         else if (b2->infinite)
1790                 return b2->lower ? 1 : -1;
1791
1792         /*
1793          * Both boundaries are finite, so compare the held values.
1794          */
1795         result = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
1796                                                                                          typcache->rng_collation,
1797                                                                                          b1->val, b2->val));
1798
1799         /*
1800          * If the comparison is anything other than equal, we're done. If they
1801          * compare equal though, we still have to consider whether the boundaries
1802          * are inclusive or exclusive.
1803          */
1804         if (result == 0)
1805         {
1806                 if (!b1->inclusive && !b2->inclusive)
1807                 {
1808                         /* both are exclusive */
1809                         if (b1->lower == b2->lower)
1810                                 return 0;
1811                         else
1812                                 return b1->lower ? 1 : -1;
1813                 }
1814                 else if (!b1->inclusive)
1815                         return b1->lower ? 1 : -1;
1816                 else if (!b2->inclusive)
1817                         return b2->lower ? -1 : 1;
1818                 else
1819                 {
1820                         /*
1821                          * Both are inclusive and the values held are equal, so they are
1822                          * equal regardless of whether they are upper or lower boundaries,
1823                          * or a mix.
1824                          */
1825                         return 0;
1826                 }
1827         }
1828
1829         return result;
1830 }
1831
1832 /*
1833  * Compare two range boundary point values, returning <0, 0, or >0 according
1834  * to whether b1 is less than, equal to, or greater than b2.
1835  *
1836  * This is similar to but simpler than range_cmp_bounds().  We just compare
1837  * the values held in b1 and b2, ignoring inclusive/exclusive flags.  The
1838  * lower/upper flags only matter for infinities, where they tell us if the
1839  * infinity is plus or minus.
1840  */
1841 int
1842 range_cmp_bound_values(TypeCacheEntry *typcache, RangeBound *b1,
1843                                            RangeBound *b2)
1844 {
1845         /*
1846          * First, handle cases involving infinity, which don't require invoking
1847          * the comparison proc.
1848          */
1849         if (b1->infinite && b2->infinite)
1850         {
1851                 /*
1852                  * Both are infinity, so they are equal unless one is lower and the
1853                  * other not.
1854                  */
1855                 if (b1->lower == b2->lower)
1856                         return 0;
1857                 else
1858                         return b1->lower ? -1 : 1;
1859         }
1860         else if (b1->infinite)
1861                 return b1->lower ? -1 : 1;
1862         else if (b2->infinite)
1863                 return b2->lower ? 1 : -1;
1864
1865         /*
1866          * Both boundaries are finite, so compare the held values.
1867          */
1868         return DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
1869                                                                                    typcache->rng_collation,
1870                                                                                    b1->val, b2->val));
1871 }
1872
1873 /*
1874  * Build an empty range value of the type indicated by the typcache entry.
1875  */
1876 RangeType *
1877 make_empty_range(TypeCacheEntry *typcache)
1878 {
1879         RangeBound      lower;
1880         RangeBound      upper;
1881
1882         lower.val = (Datum) 0;
1883         lower.infinite = false;
1884         lower.inclusive = false;
1885         lower.lower = true;
1886
1887         upper.val = (Datum) 0;
1888         upper.infinite = false;
1889         upper.inclusive = false;
1890         upper.lower = false;
1891
1892         return make_range(typcache, &lower, &upper, true);
1893 }
1894
1895
1896 /*
1897  *----------------------------------------------------------
1898  * STATIC FUNCTIONS
1899  *----------------------------------------------------------
1900  */
1901
1902 /*
1903  * Given a string representing the flags for the range type, return the flags
1904  * represented as a char.
1905  */
1906 static char
1907 range_parse_flags(const char *flags_str)
1908 {
1909         char            flags = 0;
1910
1911         if (flags_str[0] == '\0' ||
1912                 flags_str[1] == '\0' ||
1913                 flags_str[2] != '\0')
1914                 ereport(ERROR,
1915                                 (errcode(ERRCODE_SYNTAX_ERROR),
1916                                  errmsg("invalid range bound flags"),
1917                    errhint("Valid values are \"[]\", \"[)\", \"(]\", and \"()\".")));
1918
1919         switch (flags_str[0])
1920         {
1921                 case '[':
1922                         flags |= RANGE_LB_INC;
1923                         break;
1924                 case '(':
1925                         break;
1926                 default:
1927                         ereport(ERROR,
1928                                         (errcode(ERRCODE_SYNTAX_ERROR),
1929                                          errmsg("invalid range bound flags"),
1930                         errhint("Valid values are \"[]\", \"[)\", \"(]\", and \"()\".")));
1931         }
1932
1933         switch (flags_str[1])
1934         {
1935                 case ']':
1936                         flags |= RANGE_UB_INC;
1937                         break;
1938                 case ')':
1939                         break;
1940                 default:
1941                         ereport(ERROR,
1942                                         (errcode(ERRCODE_SYNTAX_ERROR),
1943                                          errmsg("invalid range bound flags"),
1944                         errhint("Valid values are \"[]\", \"[)\", \"(]\", and \"()\".")));
1945         }
1946
1947         return flags;
1948 }
1949
1950 /*
1951  * Parse range input.
1952  *
1953  * Input parameters:
1954  *      string: input string to be parsed
1955  * Output parameters:
1956  *      *flags: receives flags bitmask
1957  *      *lbound_str: receives palloc'd lower bound string, or NULL if none
1958  *      *ubound_str: receives palloc'd upper bound string, or NULL if none
1959  *
1960  * This is modeled somewhat after record_in in rowtypes.c.
1961  * The input syntax is:
1962  *      <range>   := EMPTY
1963  *                         | <lb-inc> <string>, <string> <ub-inc>
1964  *      <lb-inc>  := '[' | '('
1965  *      <ub-inc>  := ']' | ')'
1966  *
1967  * Whitespace before or after <range> is ignored.  Whitespace within a <string>
1968  * is taken literally and becomes part of the input string for that bound.
1969  *
1970  * A <string> of length zero is taken as "infinite" (i.e. no bound), unless it
1971  * is surrounded by double-quotes, in which case it is the literal empty
1972  * string.
1973  *
1974  * Within a <string>, special characters (such as comma, parenthesis, or
1975  * brackets) can be enclosed in double-quotes or escaped with backslash. Within
1976  * double-quotes, a double-quote can be escaped with double-quote or backslash.
1977  */
1978 static void
1979 range_parse(const char *string, char *flags, char **lbound_str,
1980                         char **ubound_str)
1981 {
1982         const char *ptr = string;
1983         bool            infinite;
1984
1985         *flags = 0;
1986
1987         /* consume whitespace */
1988         while (*ptr != '\0' && isspace((unsigned char) *ptr))
1989                 ptr++;
1990
1991         /* check for empty range */
1992         if (pg_strncasecmp(ptr, RANGE_EMPTY_LITERAL,
1993                                            strlen(RANGE_EMPTY_LITERAL)) == 0)
1994         {
1995                 *flags = RANGE_EMPTY;
1996                 *lbound_str = NULL;
1997                 *ubound_str = NULL;
1998
1999                 ptr += strlen(RANGE_EMPTY_LITERAL);
2000
2001                 /* the rest should be whitespace */
2002                 while (*ptr != '\0' && isspace((unsigned char) *ptr))
2003                         ptr++;
2004
2005                 /* should have consumed everything */
2006                 if (*ptr != '\0')
2007                         ereport(ERROR,
2008                                         (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2009                                          errmsg("malformed range literal: \"%s\"",
2010                                                         string),
2011                                          errdetail("Junk after \"empty\" key word.")));
2012
2013                 return;
2014         }
2015
2016         if (*ptr == '[')
2017         {
2018                 *flags |= RANGE_LB_INC;
2019                 ptr++;
2020         }
2021         else if (*ptr == '(')
2022                 ptr++;
2023         else
2024                 ereport(ERROR,
2025                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2026                                  errmsg("malformed range literal: \"%s\"",
2027                                                 string),
2028                                  errdetail("Missing left parenthesis or bracket.")));
2029
2030         ptr = range_parse_bound(string, ptr, lbound_str, &infinite);
2031         if (infinite)
2032                 *flags |= RANGE_LB_INF;
2033
2034         if (*ptr == ',')
2035                 ptr++;
2036         else
2037                 ereport(ERROR,
2038                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2039                                  errmsg("malformed range literal: \"%s\"",
2040                                                 string),
2041                                  errdetail("Missing comma after lower bound.")));
2042
2043         ptr = range_parse_bound(string, ptr, ubound_str, &infinite);
2044         if (infinite)
2045                 *flags |= RANGE_UB_INF;
2046
2047         if (*ptr == ']')
2048         {
2049                 *flags |= RANGE_UB_INC;
2050                 ptr++;
2051         }
2052         else if (*ptr == ')')
2053                 ptr++;
2054         else    /* must be a comma */
2055                 ereport(ERROR,
2056                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2057                                  errmsg("malformed range literal: \"%s\"",
2058                                                 string),
2059                                  errdetail("Too many commas.")));
2060
2061         /* consume whitespace */
2062         while (*ptr != '\0' && isspace((unsigned char) *ptr))
2063                 ptr++;
2064
2065         if (*ptr != '\0')
2066                 ereport(ERROR,
2067                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2068                                  errmsg("malformed range literal: \"%s\"",
2069                                                 string),
2070                                  errdetail("Junk after right parenthesis or bracket.")));
2071 }
2072
2073 /*
2074  * Helper for range_parse: parse and de-quote one bound string.
2075  *
2076  * We scan until finding comma, right parenthesis, or right bracket.
2077  *
2078  * Input parameters:
2079  *      string: entire input string (used only for error reports)
2080  *      ptr: where to start parsing bound
2081  * Output parameters:
2082  *      *bound_str: receives palloc'd bound string, or NULL if none
2083  *      *infinite: set true if no bound, else false
2084  *
2085  * The return value is the scan ptr, advanced past the bound string.
2086  */
2087 static const char *
2088 range_parse_bound(const char *string, const char *ptr,
2089                                   char **bound_str, bool *infinite)
2090 {
2091         StringInfoData buf;
2092
2093         /* Check for null: completely empty input means null */
2094         if (*ptr == ',' || *ptr == ')' || *ptr == ']')
2095         {
2096                 *bound_str = NULL;
2097                 *infinite = true;
2098         }
2099         else
2100         {
2101                 /* Extract string for this bound */
2102                 bool            inquote = false;
2103
2104                 initStringInfo(&buf);
2105                 while (inquote || !(*ptr == ',' || *ptr == ')' || *ptr == ']'))
2106                 {
2107                         char            ch = *ptr++;
2108
2109                         if (ch == '\0')
2110                                 ereport(ERROR,
2111                                                 (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2112                                                  errmsg("malformed range literal: \"%s\"",
2113                                                                 string),
2114                                                  errdetail("Unexpected end of input.")));
2115                         if (ch == '\\')
2116                         {
2117                                 if (*ptr == '\0')
2118                                         ereport(ERROR,
2119                                                         (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
2120                                                          errmsg("malformed range literal: \"%s\"",
2121                                                                         string),
2122                                                          errdetail("Unexpected end of input.")));
2123                                 appendStringInfoChar(&buf, *ptr++);
2124                         }
2125                         else if (ch == '"')
2126                         {
2127                                 if (!inquote)
2128                                         inquote = true;
2129                                 else if (*ptr == '"')
2130                                 {
2131                                         /* doubled quote within quote sequence */
2132                                         appendStringInfoChar(&buf, *ptr++);
2133                                 }
2134                                 else
2135                                         inquote = false;
2136                         }
2137                         else
2138                                 appendStringInfoChar(&buf, ch);
2139                 }
2140
2141                 *bound_str = buf.data;
2142                 *infinite = false;
2143         }
2144
2145         return ptr;
2146 }
2147
2148 /*
2149  * Convert a deserialized range value to text form
2150  *
2151  * Inputs are the flags byte, and the two bound values already converted to
2152  * text (but not yet quoted).  If no bound value, pass NULL.
2153  *
2154  * Result is a palloc'd string
2155  */
2156 static char *
2157 range_deparse(char flags, const char *lbound_str, const char *ubound_str)
2158 {
2159         StringInfoData buf;
2160
2161         if (flags & RANGE_EMPTY)
2162                 return pstrdup(RANGE_EMPTY_LITERAL);
2163
2164         initStringInfo(&buf);
2165
2166         appendStringInfoChar(&buf, (flags & RANGE_LB_INC) ? '[' : '(');
2167
2168         if (RANGE_HAS_LBOUND(flags))
2169                 appendStringInfoString(&buf, range_bound_escape(lbound_str));
2170
2171         appendStringInfoChar(&buf, ',');
2172
2173         if (RANGE_HAS_UBOUND(flags))
2174                 appendStringInfoString(&buf, range_bound_escape(ubound_str));
2175
2176         appendStringInfoChar(&buf, (flags & RANGE_UB_INC) ? ']' : ')');
2177
2178         return buf.data;
2179 }
2180
2181 /*
2182  * Helper for range_deparse: quote a bound value as needed
2183  *
2184  * Result is a palloc'd string
2185  */
2186 static char *
2187 range_bound_escape(const char *value)
2188 {
2189         bool            nq;
2190         const char *ptr;
2191         StringInfoData buf;
2192
2193         initStringInfo(&buf);
2194
2195         /* Detect whether we need double quotes for this value */
2196         nq = (value[0] == '\0');        /* force quotes for empty string */
2197         for (ptr = value; *ptr; ptr++)
2198         {
2199                 char            ch = *ptr;
2200
2201                 if (ch == '"' || ch == '\\' ||
2202                         ch == '(' || ch == ')' ||
2203                         ch == '[' || ch == ']' ||
2204                         ch == ',' ||
2205                         isspace((unsigned char) ch))
2206                 {
2207                         nq = true;
2208                         break;
2209                 }
2210         }
2211
2212         /* And emit the string */
2213         if (nq)
2214                 appendStringInfoChar(&buf, '"');
2215         for (ptr = value; *ptr; ptr++)
2216         {
2217                 char            ch = *ptr;
2218
2219                 if (ch == '"' || ch == '\\')
2220                         appendStringInfoChar(&buf, ch);
2221                 appendStringInfoChar(&buf, ch);
2222         }
2223         if (nq)
2224                 appendStringInfoChar(&buf, '"');
2225
2226         return buf.data;
2227 }
2228
2229 /*
2230  * Test whether range r1 contains range r2.
2231  *
2232  * Caller has already checked that they are the same range type, and looked up
2233  * the necessary typcache entry.
2234  */
2235 bool
2236 range_contains_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
2237 {
2238         RangeBound      lower1;
2239         RangeBound      upper1;
2240         bool            empty1;
2241         RangeBound      lower2;
2242         RangeBound      upper2;
2243         bool            empty2;
2244
2245         /* Different types should be prevented by ANYRANGE matching rules */
2246         if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
2247                 elog(ERROR, "range types do not match");
2248
2249         range_deserialize(typcache, r1, &lower1, &upper1, &empty1);
2250         range_deserialize(typcache, r2, &lower2, &upper2, &empty2);
2251
2252         /* If either range is empty, the answer is easy */
2253         if (empty2)
2254                 return true;
2255         else if (empty1)
2256                 return false;
2257
2258         /* Else we must have lower1 <= lower2 and upper1 >= upper2 */
2259         if (range_cmp_bounds(typcache, &lower1, &lower2) > 0)
2260                 return false;
2261         if (range_cmp_bounds(typcache, &upper1, &upper2) < 0)
2262                 return false;
2263
2264         return true;
2265 }
2266
2267 bool
2268 range_contained_by_internal(TypeCacheEntry *typcache, RangeType *r1, RangeType *r2)
2269 {
2270         return range_contains_internal(typcache, r2, r1);
2271 }
2272
2273 /*
2274  * Test whether range r contains a specific element value.
2275  */
2276 bool
2277 range_contains_elem_internal(TypeCacheEntry *typcache, RangeType *r, Datum val)
2278 {
2279         RangeBound      lower;
2280         RangeBound      upper;
2281         bool            empty;
2282         int32           cmp;
2283
2284         range_deserialize(typcache, r, &lower, &upper, &empty);
2285
2286         if (empty)
2287                 return false;
2288
2289         if (!lower.infinite)
2290         {
2291                 cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
2292                                                                                           typcache->rng_collation,
2293                                                                                           lower.val, val));
2294                 if (cmp > 0)
2295                         return false;
2296                 if (cmp == 0 && !lower.inclusive)
2297                         return false;
2298         }
2299
2300         if (!upper.infinite)
2301         {
2302                 cmp = DatumGetInt32(FunctionCall2Coll(&typcache->rng_cmp_proc_finfo,
2303                                                                                           typcache->rng_collation,
2304                                                                                           upper.val, val));
2305                 if (cmp < 0)
2306                         return false;
2307                 if (cmp == 0 && !upper.inclusive)
2308                         return false;
2309         }
2310
2311         return true;
2312 }
2313
2314
2315 /*
2316  * datum_compute_size() and datum_write() are used to insert the bound
2317  * values into a range object.  They are modeled after heaptuple.c's
2318  * heap_compute_data_size() and heap_fill_tuple(), but we need not handle
2319  * null values here.  TYPE_IS_PACKABLE must test the same conditions as
2320  * heaptuple.c's ATT_IS_PACKABLE macro.
2321  */
2322
2323 /* Does datatype allow packing into the 1-byte-header varlena format? */
2324 #define TYPE_IS_PACKABLE(typlen, typstorage) \
2325         ((typlen) == -1 && (typstorage) != 'p')
2326
2327 /*
2328  * Increment data_length by the space needed by the datum, including any
2329  * preceding alignment padding.
2330  */
2331 static Size
2332 datum_compute_size(Size data_length, Datum val, bool typbyval, char typalign,
2333                                    int16 typlen, char typstorage)
2334 {
2335         if (TYPE_IS_PACKABLE(typlen, typstorage) &&
2336                 VARATT_CAN_MAKE_SHORT(DatumGetPointer(val)))
2337         {
2338                 /*
2339                  * we're anticipating converting to a short varlena header, so adjust
2340                  * length and don't count any alignment
2341                  */
2342                 data_length += VARATT_CONVERTED_SHORT_SIZE(DatumGetPointer(val));
2343         }
2344         else
2345         {
2346                 data_length = att_align_datum(data_length, typalign, typlen, val);
2347                 data_length = att_addlength_datum(data_length, typlen, val);
2348         }
2349
2350         return data_length;
2351 }
2352
2353 /*
2354  * Write the given datum beginning at ptr (after advancing to correct
2355  * alignment, if needed).  Return the pointer incremented by space used.
2356  */
2357 static Pointer
2358 datum_write(Pointer ptr, Datum datum, bool typbyval, char typalign,
2359                         int16 typlen, char typstorage)
2360 {
2361         Size            data_length;
2362
2363         if (typbyval)
2364         {
2365                 /* pass-by-value */
2366                 ptr = (char *) att_align_nominal(ptr, typalign);
2367                 store_att_byval(ptr, datum, typlen);
2368                 data_length = typlen;
2369         }
2370         else if (typlen == -1)
2371         {
2372                 /* varlena */
2373                 Pointer         val = DatumGetPointer(datum);
2374
2375                 if (VARATT_IS_EXTERNAL(val))
2376                 {
2377                         /*
2378                          * Throw error, because we must never put a toast pointer inside a
2379                          * range object.  Caller should have detoasted it.
2380                          */
2381                         elog(ERROR, "cannot store a toast pointer inside a range");
2382                         data_length = 0;        /* keep compiler quiet */
2383                 }
2384                 else if (VARATT_IS_SHORT(val))
2385                 {
2386                         /* no alignment for short varlenas */
2387                         data_length = VARSIZE_SHORT(val);
2388                         memcpy(ptr, val, data_length);
2389                 }
2390                 else if (TYPE_IS_PACKABLE(typlen, typstorage) &&
2391                                  VARATT_CAN_MAKE_SHORT(val))
2392                 {
2393                         /* convert to short varlena -- no alignment */
2394                         data_length = VARATT_CONVERTED_SHORT_SIZE(val);
2395                         SET_VARSIZE_SHORT(ptr, data_length);
2396                         memcpy(ptr + 1, VARDATA(val), data_length - 1);
2397                 }
2398                 else
2399                 {
2400                         /* full 4-byte header varlena */
2401                         ptr = (char *) att_align_nominal(ptr, typalign);
2402                         data_length = VARSIZE(val);
2403                         memcpy(ptr, val, data_length);
2404                 }
2405         }
2406         else if (typlen == -2)
2407         {
2408                 /* cstring ... never needs alignment */
2409                 Assert(typalign == 'c');
2410                 data_length = strlen(DatumGetCString(datum)) + 1;
2411                 memcpy(ptr, DatumGetPointer(datum), data_length);
2412         }
2413         else
2414         {
2415                 /* fixed-length pass-by-reference */
2416                 ptr = (char *) att_align_nominal(ptr, typalign);
2417                 Assert(typlen > 0);
2418                 data_length = typlen;
2419                 memcpy(ptr, DatumGetPointer(datum), data_length);
2420         }
2421
2422         ptr += data_length;
2423
2424         return ptr;
2425 }