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