Re: range_adjacent and discrete ranges

Florian Pflug <fgp@phlo.org> writes:
> More formally, let there be two arbitrary ranges
>   a,b,i_a,i_b
>   c,d,i_c,i_d
> where the first two parameters are the lower respectively upper bound, and
> the last two are booleans saying whether the lower respectively upper bound
> is inclusive (true) or exclusive (false).

> These ranges are then adjacent exactly if the range
>   b,c,!i_b,!i_c
> is empty.

I tried to implement this, and I think it has a small bug.  It works as
stated if we have b < c.  However, if we have b == c, then we want to
consider the ranges adjacent if i_b != i_c (ie, only one of them claims
the common boundary point).  But a singleton range is empty unless it's
inclusive on both sides.  So we have to have a special case when the
bounds are equal.

(If b > c, then of course we have to consider the two ranges in the
opposite order.)

Attached is a draft patch for this.  It passes regression tests but I've
not tried to exercise it with a canonical function that actually does
something different.  It's going to be a bit slower than Jeff's
original, because it does not only range_cmp_bound_values but also a
make_range cycle (in most cases).  So I guess the question is how much
we care about supporting canonical functions with non-default policies.
Thoughts?

            regards, tom lane

diff --git a/src/backend/utils/adt/rangetypes.c b/src/backend/utils/adt/rangetypes.c
index 3326cb17c895273fd01c4eda5eb0d65a521d0168..890b6850cb6f5611e9afa922b85b0c64125f31bb 100644
*** a/src/backend/utils/adt/rangetypes.c
--- b/src/backend/utils/adt/rangetypes.c
*************** range_adjacent(PG_FUNCTION_ARGS)
*** 699,704 ****
--- 699,706 ----
                  upper2;
      bool        empty1,
                  empty2;
+     RangeType  *r3;
+     int            cmp;

      /* Different types should be prevented by ANYRANGE matching rules */
      if (RangeTypeGetOid(r1) != RangeTypeGetOid(r2))
*************** range_adjacent(PG_FUNCTION_ARGS)
*** 714,736 ****
          PG_RETURN_BOOL(false);

      /*
!      * For two ranges to be adjacent, the lower boundary of one range has to
!      * match the upper boundary of the other. However, the inclusivity of
!      * those two boundaries must also be different.
!      *
!      * The semantics for range_cmp_bounds aren't quite what we need here, so
!      * we do the comparison more directly.
       */
!     if (lower1.inclusive != upper2.inclusive)
      {
!         if (range_cmp_bound_values(typcache, &lower1, &upper2) == 0)
!             PG_RETURN_BOOL(true);
      }
!
!     if (upper1.inclusive != lower2.inclusive)
      {
!         if (range_cmp_bound_values(typcache, &upper1, &lower2) == 0)
!             PG_RETURN_BOOL(true);
      }

      PG_RETURN_BOOL(false);
--- 716,758 ----
          PG_RETURN_BOOL(false);

      /*
!      * Given two ranges A..B and C..D, where B < C, the ranges are adjacent
!      * if and only if the range B..C is empty, where inclusivity of these two
!      * bounds is inverted compared to the original bounds.  For discrete
!      * ranges, we have to rely on the canonicalization function to normalize
!      * B..C to empty if it contains no elements of the subtype.  If B == C,
!      * the ranges are adjacent only if these bounds have different inclusive
!      * flags (i.e., exactly one of the ranges includes the common boundary).
!      * And if B > C then the ranges cannot be adjacent in this order, but we
!      * must consider the other order (i.e., check D <= A).
       */
!     cmp = range_cmp_bound_values(typcache, &upper1, &lower2);
!     if (cmp < 0)
      {
!         upper1.inclusive = !upper1.inclusive;
!         upper1.lower = true;
!         lower2.inclusive = !lower2.inclusive;
!         lower2.lower = false;
!         r3 = make_range(typcache, &upper1, &lower2, false);
!         PG_RETURN_BOOL(RangeIsEmpty(r3));
      }
!     if (cmp == 0)
      {
!         PG_RETURN_BOOL(upper1.inclusive != lower2.inclusive);
!     }
!     cmp = range_cmp_bound_values(typcache, &upper2, &lower1);
!     if (cmp < 0)
!     {
!         upper2.inclusive = !upper2.inclusive;
!         upper2.lower = true;
!         lower1.inclusive = !lower1.inclusive;
!         lower1.lower = false;
!         r3 = make_range(typcache, &upper2, &lower1, false);
!         PG_RETURN_BOOL(RangeIsEmpty(r3));
!     }
!     if (cmp == 0)
!     {
!         PG_RETURN_BOOL(upper2.inclusive != lower1.inclusive);
      }

      PG_RETURN_BOOL(false);