LICENSE.md

MIT License

Copyright (c) 2019-2020 Matthew Schinckel

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

patch_ranges.py

"""
This module overrides the Range.__and__ function, so that it returns a boolean value
based on if the two objects overlap.

The rationale behind this is that it mirrors the `range && range` operator in postgres.

There are tests for this, that hit the database with randomly generated ranges and ensure
that the database and this method agree upon the results.

There is also a more complete `isempty()` method, which examines the bounds types and values,
and determines if the object is indeed empty. This is required when python-created range objects
are dealt with, as these are not normalised the same way that postgres does.
"""
import datetime

from psycopg2.extras import Range

OFFSET = {
    int: 1,
    datetime.date: datetime.timedelta(1),
}


def normalise(instance):
    """
    In the case of discrete ranges (integer, date), then we normalise the values
    so it is in the form [start,finish), the same way that postgres does.

    If the lower value is None, we normalise this to (None,finish)
    """
    if instance.isempty:
        return instance

    lower = instance.lower
    upper = instance.upper
    bounds = list(instance._bounds)

    if lower is not None and lower == upper and instance._bounds != '[]':
        return instance.__class__(empty=True)

    if lower is None:
        bounds[0] = '('
    elif bounds[0] == '(' and type(lower) in OFFSET:
        lower += OFFSET[type(lower)]
        bounds[0] = '['

    if upper is None:
        bounds[1] = ')'
    elif bounds[1] == ']' and type(upper) in OFFSET:
        upper += OFFSET[type(upper)]
        bounds[1] = ')'

    if lower is not None and lower == upper and bounds != ['[', ']']:
        return instance.__class__(empty=True)

    return instance.__class__(lower, upper, ''.join(bounds))


def __and__(self, other):
    if not isinstance(other, self.__class__):
        raise TypeError("unsupported operand type(s) for &: '{}' and '{}'".format(
            self.__class__.__name__, other.__class__.__name__
        ))

    self = normalise(self)
    other = normalise(other)

    # If _either_ object is empty, then it will never overlap with any other one.
    if self.isempty or other.isempty:
        return False

    if other < self:
        return other & self

    # Because we can't compare None with a datetime.date(), we need to deal
    # with the cases where one (or both) of the parts are None first.
    if self.lower is None:
        if self.upper is None or other.lower is None:
            return True
        if self.upper_inc and other.lower_inc:
            return self.upper >= other.lower
        return self.upper > other.lower

    if self.upper is None:
        if other.upper is None:
            return True
        if self.lower_inc and other.upper_inc:
            return self.lower <= other.upper
        return self.lower < other.upper

    # Now, all we care about is self.upper_inc and other.lower_inc
    if self.upper_inc and other.lower_inc:
        return self.upper >= other.lower
    else:
        return self.upper > other.lower


def __eq__(self, other):
    if not isinstance(other, Range):
        return False

    self = normalise(self)
    other = normalise(other)

    return (self._lower == other._lower and
            self._upper == other._upper and
            self._bounds == other._bounds)


def range_merge(self, other):
    "Union"
    self = normalise(self)
    other = normalise(other)
    bounds = [None, None]

    if self.isempty:
        return self

    if other.isempty:
        return other

    if self > other:
        self, other = other, self

    if self.upper is not None and other.lower is not None:
        if not self.upper_inc and other.lower <= self.upper:
            # They overlap.
            pass
        else:
            raise ValueError('Result of range union would not be contiguous')

    if self.lower is None:
        lower = None
        bounds[0] = '('
    elif self.lower_inc != other.lower_inc:
        # The bounds differ, so we need to use the complicated logic.
        raise NotImplementedError()
    else:
        # The bounds are the same, so we can just use the lower value.
        lower = min(self.lower, other.lower)
        bounds[0] = self._bounds[0]

    if self.upper is None or other.upper is None:
        upper = None
        bounds[1] = ')'
    elif self.upper_inc != other.upper_inc:
        raise NotImplementedError()
    else:
        upper = max(self.upper, other.upper)
        bounds[1] = self._bounds[1]

    return normalise(self.__class__(lower, upper, ''.join(bounds)))


def range_intersection(self, other):
    self = normalise(self)
    other = normalise(other)

    if not self & other:
        return self.__class__(empty=True)

    # We need to use custom comparisons because non-number range types will fail to compare.
    # Also, min(X, None) means min(X, Infinity), really.
    if self.lower is None:
        lower = other.lower
    elif other.lower is None:
        lower = self.lower
    else:
        lower = max(self.lower, other.lower)

    if self.upper is None:
        upper = other.upper
    elif other.upper is None:
        upper = self.upper
    else:
        upper = min(self.upper, other.upper)

    return normalise(self.__class__(lower, upper, '[)'))


def range_contains(self, other):
    if self._bounds is None:
        return False

    if type(self) == type(other):
        return self & other and self + other == self

    # We have two tests to make in each case - is the value out of the lower bound,
    # and is the value out on the upper bound. We can make a series of tests, and if we ever find
    # a situation where we _are_ out of bounds, return at that point.

    if self.lower is not None:
        if self.lower_inc:
            if other < self.lower:
                return False
        elif other <= self.lower:
            return False

    if self.upper is not None:
        if self.upper_inc:
            if other > self.upper:
                return False
        elif other >= self.upper:
            return False

    return True


def deconstruct(self):
    return (
        '{}.{}'.format(self.__class__.__module__, self.__class__.__name__),
        [self.lower, self.upper, self._bounds],
        {}
    )


Range.__add__ = range_merge
Range.__and__ = __and__
Range.__eq__ = __eq__
Range.__mul__ = range_intersection
Range.__contains__ = range_contains

Range.deconstruct = deconstruct


_BOUNDS_SWAP = {
    '[': ')',
    ']': '(',
    '(': ']',
    ')': '[',
}.get


def safe_subtract(initial, subtract):
    """
    Subtract the range "subtract" from the range "initial".

    Always return an array of ranges (which may be empty).
    """
    _Range = initial.__class__
    sub_bounds = ''.join(map(_BOUNDS_SWAP, subtract._bounds))

    # Simplest case - ranges are the same, or the source one is fully contained within
    # the subtracting one, then we get an empty list of ranges.
    if subtract == initial or initial in subtract:
        return []

    # If the ranges don't overlap, then we retain the source.
    if not initial & subtract:
        return [initial]

    # We will have either one or two objects, depending upon if the subtractor overlaps one of the bounds or not.
    # We know that both of them will not overlap the bounds, because that case has already been dealt with.

    if initial.upper in subtract or (not initial.upper_inc and initial.upper == subtract.upper):
        return [_Range(initial.lower, subtract.lower, '{}{}'.format(
            initial._bounds[0],
            sub_bounds[0],
        ))]
    elif initial.lower in subtract or (not initial.lower_inc and initial.lower == subtract.lower):
        return [_Range(subtract.upper, initial.upper, '{}{}'.format(
            sub_bounds[1],
            initial._bounds[1]
        ))]
    else:
        return [
            _Range(initial.lower, subtract.lower, '{}{}'.format(
                initial._bounds[0],
                sub_bounds[0]
            )),
            _Range(subtract.upper, initial.upper, '{}{}'.format(
                sub_bounds[1],
                initial._bounds[1]
            ))
        ]


def array_subtract(initial, subtract):
    """
    subtract the range from each item in the initial array.
    """
    result = []
    for _range in initial:
        result.extend(safe_subtract(_range, subtract))
    return result


def array_subtract_all(initial, subtract):
    """
    Subtract all overlapping ranges in subtract from all ranges in initial.
    """
    result = list(initial)
    for other in subtract:
        result = array_subtract(result, other)
    return result

test_patch_ranges.py

import datetime
from decimal import Decimal

from django.db import connection

from hypothesis import given
from hypothesis.extra.django import TestCase
from hypothesis.strategies import dates, datetimes, integers, none, one_of, sampled_from, tuples
# from hypothesis.extra.datetime import dates, datetimes
from psycopg2.extras import DateRange, DateTimeRange, NumericRange, Range

from .patch_ranges import array_subtract_all, safe_subtract


def valid_range(obj):
    return obj[0] is None or obj[1] is None or obj[0] <= obj[1]

BOUNDS = sampled_from(['[]', '()', '[)', '(]'])
BIGINT = one_of(
    integers(min_value=-9223372036854775807,
             max_value=+9223372036854775806),
    none()
)
DATES = one_of(dates(), none())
DATETIMES = one_of(datetimes(), none())

num_range = tuples(BIGINT, BIGINT, BOUNDS).filter(valid_range)
date_range = tuples(DATES, DATES, BOUNDS).filter(valid_range)
datetime_range = tuples(DATETIMES, DATETIMES, BOUNDS).filter(valid_range)


class TestRange__and__(TestCase):

    def test_normalised(self):
        from core.monkey_patch.ranges import normalise
        self.assertTrue(normalise(NumericRange(0, 1, '()')).isempty)
        self.assertFalse(normalise(DateRange(datetime.date(2000, 1, 9), datetime.date(2000, 1, 10), '(]')).isempty)
        self.assertTrue(normalise(NumericRange(2, 2, '()')).isempty)

    @given(num_range)
    def test_normalise_hypothesis(self, a):
        from core.monkey_patch.ranges import normalise
        a = NumericRange(*a)
        cursor = connection.cursor()
        cursor.execute("SELECT %s::int8range", [a])
        self.assertEqual(cursor.fetchone()[0], normalise(a), a)

    @given(date_range)
    def test_normalise_hypothesis_daterange(self, a):
        from core.monkey_patch.ranges import normalise
        a = DateRange(*a)
        cursor = connection.cursor()
        cursor.execute("SELECT %s::daterange", [a])
        self.assertEqual(cursor.fetchone()[0], normalise(a), a)

    @given(datetime_range)
    def test_normalise_hypothesis_tsrange(self, a):
        from core.monkey_patch.ranges import normalise
        a = DateTimeRange(*a)
        cursor = connection.cursor()
        cursor.execute("SELECT %s::tsrange", [a])
        self.assertEqual(cursor.fetchone()[0], normalise(a), a)

    def test_can_query_db(self):
        cursor = connection.cursor()
        cursor.execute('SELECT %s::int8range && %s::int8range', [NumericRange(), NumericRange()])
        self.assertTrue(cursor.fetchone()[0])

    def test_may_not_compare_different_range_types(self):
        with self.assertRaises(TypeError):
            NumericRange() & DateRange()

    def test_empty_ranges_do_not_overlap(self):
        self.assertFalse(NumericRange(0, 0, '()') & NumericRange())
        self.assertFalse(NumericRange(0, 1, '()') & NumericRange(None, None, '[]'))

    def test_two_full_ranges_overlap(self):
        self.assertTrue(NumericRange() & NumericRange())
        self.assertTrue(NumericRange(None, None, '[]') & NumericRange(None, None, '[]'))

    def test_full_range_overlaps_non_full_range(self):
        self.assertTrue(NumericRange() & NumericRange(-12, 55))
        self.assertTrue(NumericRange(-12, 55) & NumericRange())

    def test_ends_touch(self):
        self.assertFalse(NumericRange(10, 20) & NumericRange(20, 30))
        self.assertTrue(NumericRange(10, 20, '[]') & NumericRange(20, 30))
        self.assertFalse(NumericRange(20, 30) & NumericRange(10, 20))
        self.assertTrue(NumericRange(20, 30) & NumericRange(10, 20, '[]'))

        self.assertFalse(NumericRange(10, 20) & NumericRange(20, None))
        self.assertTrue(NumericRange(10, 20, '[]') & NumericRange(20, None))
        self.assertFalse(NumericRange(20, None) & NumericRange(10, 20))
        self.assertTrue(NumericRange(20, None) & NumericRange(10, 20, '[]'))

        self.assertFalse(NumericRange(None, 20) & NumericRange(20, 30))
        self.assertTrue(NumericRange(None, 20, '[]') & NumericRange(20, 30))
        self.assertFalse(NumericRange(20, 30) & NumericRange(None, 20))
        self.assertTrue(NumericRange(20, 30) & NumericRange(None, 20, '[]'))

        self.assertFalse(NumericRange(None, 20) & NumericRange(20, None))
        self.assertTrue(NumericRange(None, 20, '[]') & NumericRange(20, None))
        self.assertFalse(NumericRange(20, None) & NumericRange(None, 20))
        self.assertTrue(NumericRange(20, None) & NumericRange(None, 20, '[]'))

        self.assertFalse(NumericRange(0, 2, '()') & NumericRange(0, 0, '[]'))

    def test_both_upper_None(self):
        self.assertTrue(NumericRange(1, None), NumericRange(100, None))

    @given(num_range, num_range)
    def test_with_hypothesis(self, a, b):
        a = NumericRange(*a)
        b = NumericRange(*b)
        cursor = connection.cursor()
        cursor.execute('SELECT %s::int8range && %s::int8range', [a, b])
        self.assertEqual(cursor.fetchone()[0], a & b, '{} && {}'.format(a, b))

    @given(date_range, date_range)
    def test_with_hypothesis_dates(self, a, b):
        a = DateRange(*a)
        b = DateRange(*b)
        cursor = connection.cursor()
        cursor.execute('SELECT %s::daterange && %s::daterange', [a, b])
        self.assertEqual(cursor.fetchone()[0], a & b, '{} && {}'.format(a, b))

    @given(datetime_range, datetime_range)
    def test_with_hypothesis_datetimes(self, a, b):
        a = DateTimeRange(*a)
        b = DateTimeRange(*b)
        cursor = connection.cursor()
        cursor.execute('SELECT %s::tsrange && %s::tsrange', [a, b])
        self.assertEqual(cursor.fetchone()[0], a & b, '{} && {}'.format(a, b))

    def test_with_values_found_by_hypothesis(self):
        from core.monkey_patch.ranges import normalise
        self.assertEqual(NumericRange(None, 1, '()'), normalise(NumericRange(None, 0, '[]')))
        self.assertFalse(NumericRange(0, None, '()') & NumericRange(None, 1, '()'))

    @given(datetime_range)
    def test_equality(self, a):
        self.assertNotEqual(a, None)
        self.assertNotEqual(a, 1)
        self.assertNotEqual(a, [])
        self.assertEqual(a, a)

    def test_manual_equality(self):
        self.assertFalse(NumericRange(0, 2, '[]') is None)

    def test_timedelta_ranges(self):
        a = Range(datetime.timedelta(0), datetime.timedelta(1))
        b = Range(datetime.timedelta(hours=5), datetime.timedelta(hours=9))

        self.assertTrue(a & b)
        self.assertTrue(b & a)
        self.assertTrue(b.lower in a)
        self.assertTrue(b.upper in a)
        self.assertFalse(a.lower in b)
        self.assertFalse(a.upper in b)


class TestRangeContains(TestCase):
    def test_out_of_bounds(self):
        self.assertFalse(2 in Range(7, 12))
        self.assertFalse(6 in Range(1, 4))
        self.assertFalse(2 in Range(6, None))
        self.assertFalse(22 in Range(None, 20))

        self.assertFalse(Decimal('8.01') in Range(0, 8, '[]'))
        self.assertFalse(Decimal(8) in Range(0, 8, '[)'))

    def test_in_bounds(self):
        self.assertTrue(4 in Range(0, 8))
        self.assertTrue(4 in Range(None, 8))
        self.assertTrue(4 in Range(0, None))
        self.assertTrue(4 in Range(None, None))

    def test_in_on_lower_bounds_inclusive(self):
        self.assertTrue(2 in Range(2, 7))
        self.assertTrue(2 in Range(2, None))

    def test_out_on_lower_bounds_exclusive(self):
        self.assertFalse(2 in Range(2, 7, '()'))
        self.assertFalse(2 in Range(2, None, '()'))
        self.assertFalse(2 in Range(2, 7, '(]'))

    def test_in_on_upper_bounds_inclusive(self):
        self.assertTrue(10 in Range(0, 10, '[]'))
        self.assertTrue(10 in Range(0, 10, '(]'))
        self.assertTrue(10 in Range(None, 10, '(]'))

    def test_out_on_upper_bounds_exclusive(self):
        self.assertFalse(10 in Range(0, 10, '[)'))
        self.assertFalse(10 in Range(None, 10, '()'))
        self.assertFalse(10 in Range(0, 10, '()'))

    def test_no_overlap(self):
        self.assertFalse(Range(2, 4) in Range(8, 12))

    def test_partial_overlap(self):
        self.assertFalse(Range(2, 10) in Range(8, 12))

    def test_in_is_larger(self):
        self.assertFalse(Range(2, 14) in Range(8, 12))

    def test_match(self):
        self.assertTrue(Range(2, 4) in Range(2, 4))
        self.assertTrue(Range(2, 4, '[)') in Range(2, 4, '[]'))
        self.assertFalse(Range(2, 4, '[]') in Range(2, 4, '[)'))


class TestRangeMerge(TestCase):
    def test_contained(self):
        self.assertEqual(Range(1, 12) + Range(2, 5), Range(1, 12))
        self.assertEqual(Range(2, 5) + Range(1, 12), Range(1, 12))
        self.assertEqual(Range(None, None) + Range(2, 44), Range(None, None))
        self.assertEqual(Range(2, 44) + Range(None, None), Range(None, None))
        self.assertEqual(Range(None, 44) + Range(None, None), Range(None, None))

    def test_intersect(self):
        self.assertEqual(Range(None, 5) + Range(2, None), Range(None, None))

    def test_adjacent(self):
        self.assertEqual(Range(2, 22, '[]') + Range(23, 44), Range(2, 44))

    def test_distinct(self):
        with self.assertRaises(ValueError):
            Range(2, 6) + Range(8, 12)


class TestRangeIntersect(TestCase):
    def test_intersects(self):
        self.assertEqual(Range(22, 25, '[]') * Range(23, 28, '[]'), Range(23, 25, '[]'))
        self.assertEqual(Range(None, 25, '(]') * Range(23, None, '[)'), Range(23, 25, '[]'))


class TestRangeSubtract(TestCase):
    def test_source_within_subtract(self):
        """
           [ source )
        [    subtract    )
        [    subtract    ]
        (    subtract    )
        (    subtract    ]
        """
        self.assertEqual([], safe_subtract(Range(11, 16, '[)'), Range(0, 44, '[)')))
        self.assertEqual([], safe_subtract(Range(11, 16, '[)'), Range(0, 44, '(]')))
        self.assertEqual([], safe_subtract(Range(11, 16, '[)'), Range(0, 44, '()')))
        self.assertEqual([], safe_subtract(Range(11, 16, '[)'), Range(0, 44, '[]')))

        """
            (source)
        [   subtract   ]
           ... etc
        """

        self.assertEqual([], safe_subtract(Range(11, 16, '()'), Range(0, 44, '[)')))
        self.assertEqual([], safe_subtract(Range(11, 16, '()'), Range(0, 44, '(]')))
        self.assertEqual([], safe_subtract(Range(11, 16, '()'), Range(0, 44, '()')))
        self.assertEqual([], safe_subtract(Range(11, 16, '()'), Range(0, 44, '[]')))

        self.assertEqual([], safe_subtract(Range(11, 16, '[]'), Range(0, 44, '[)')))
        self.assertEqual([], safe_subtract(Range(11, 16, '[]'), Range(0, 44, '(]')))
        self.assertEqual([], safe_subtract(Range(11, 16, '[]'), Range(0, 44, '()')))
        self.assertEqual([], safe_subtract(Range(11, 16, '[]'), Range(0, 44, '[]')))

        self.assertEqual([], safe_subtract(Range(11, 16, '(]'), Range(0, 44, '[)')))
        self.assertEqual([], safe_subtract(Range(11, 16, '(]'), Range(0, 44, '(]')))
        self.assertEqual([], safe_subtract(Range(11, 16, '(]'), Range(0, 44, '()')))
        self.assertEqual([], safe_subtract(Range(11, 16, '(]'), Range(0, 44, '[]')))

    def test_subtract_upper_bound_matches_source_lower_bound(self):
        """

                 [ source )
        [subtract]

        """
        self.assertEqual(
            [Range(4, 7, '()')],
            safe_subtract(Range(4, 7, '[)'), Range(0, 4, '[]'))
        )

    def test_subtract_lower_bound_below_bounds_only(self):
        """

                 [source)
        [subtract)
        (subtract)

        """
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(0, 4, '[)')))
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(0, 4, '()')))

        """
                 (source)
        (subtract]
        """
        self.assertEqual(
            [Range(4, 7, '()')],
            safe_subtract(Range(4, 7, '()'), Range(0, 4, '[]'))
        )

    def test_subtract_lower_bound_below_completely(self):
        """
                    [source)
        [subtract]
        [subtract)
        [subtract]
        (subtract)

        """
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(0, 3, '[)')))
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(0, 3, '()')))
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(0, 3, '[]')))
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(0, 3, '(]')))

        # Other source bounds types
        self.assertEqual([Range(4, 7, '[]')], safe_subtract(Range(4, 7, '[]'), Range(0, 3, '[)')))
        self.assertEqual([Range(4, 7, '[]')], safe_subtract(Range(4, 7, '[]'), Range(0, 3, '()')))
        self.assertEqual([Range(4, 7, '[]')], safe_subtract(Range(4, 7, '[]'), Range(0, 3, '[]')))
        self.assertEqual([Range(4, 7, '[]')], safe_subtract(Range(4, 7, '[]'), Range(0, 3, '(]')))

        self.assertEqual([Range(4, 7, '(]')], safe_subtract(Range(4, 7, '(]'), Range(0, 3, '[)')))
        self.assertEqual([Range(4, 7, '(]')], safe_subtract(Range(4, 7, '(]'), Range(0, 3, '()')))
        self.assertEqual([Range(4, 7, '(]')], safe_subtract(Range(4, 7, '(]'), Range(0, 3, '[]')))
        self.assertEqual([Range(4, 7, '(]')], safe_subtract(Range(4, 7, '(]'), Range(0, 3, '(]')))

        self.assertEqual([Range(4, 7, '()')], safe_subtract(Range(4, 7, '()'), Range(0, 3, '[)')))
        self.assertEqual([Range(4, 7, '()')], safe_subtract(Range(4, 7, '()'), Range(0, 3, '()')))
        self.assertEqual([Range(4, 7, '()')], safe_subtract(Range(4, 7, '()'), Range(0, 3, '[]')))
        self.assertEqual([Range(4, 7, '()')], safe_subtract(Range(4, 7, '()'), Range(0, 3, '(]')))

    def test_upper_bound_above_bounds_only(self):
        """

        [source)
               [subtract]

        [source]
               (subtract)
        """
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(7, 10, '[)')))
        self.assertEqual([Range(4, 7, '[]')], safe_subtract(Range(4, 7, '[]'), Range(7, 10, '()')))

        """
        [source]
               [subtract]
        """
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[]'), Range(7, 12, '[]')))

    def test_upper_bound_above_completely(self):
        """

        [source)
                    [subtract]
                    (subtract)
                    [subtract)
                    (subtract]

        """
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(10, 14, '[]')))
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(10, 14, '()')))
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(10, 14, '[)')))
        self.assertEqual([Range(4, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(10, 14, '(]')))

    def test_intersects_lower_bounds(self):
        """

                 [source)
        [subtract]
             [subtract]
             [subtract)
             (subtract)

        """
        self.assertEqual([Range(4, 7, '()')], safe_subtract(Range(4, 7, '[)'), Range(0, 4, '[]')))
        self.assertEqual([Range(5, 7, '()')], safe_subtract(Range(4, 7, '[)'), Range(0, 5, '[]')))
        self.assertEqual([Range(5, 7, '[)')], safe_subtract(Range(4, 7, '[)'), Range(0, 5, '[)')))
        self.assertEqual([Range(5, 7, '()')], safe_subtract(Range(4, 7, '[)'), Range(0, 5, '[]')))

    def test_lower_bounds_same(self):
        """

        [source        )

        [subtract]
        [subtract)
        (subtract)
        (subtract]
        (   subtract   )
        (   subtract   ]
        """

        self.assertEqual([Range(6, 8, '()')], safe_subtract(Range(4, 8), Range(4, 6, '[]')))
        self.assertEqual([Range(6, 8, '[)')], safe_subtract(Range(4, 8), Range(4, 6, '[)')))

        self.assertEqual([Range(4, 4, '[]'), Range(6, 8, '[)')], safe_subtract(Range(4, 8), Range(4, 6, '()')))
        self.assertEqual([Range(4, 4, '[]'), Range(6, 8, '()')], safe_subtract(Range(4, 8), Range(4, 6, '(]')))

    def test_lower_bound_inclusive_difference_only(self):
        """
        [source   )
        (subtract )
        (subtract ]
        """
        self.assertEqual([Range(4, 4, '[]')], safe_subtract(Range(4, 8, '[)'), Range(4, 8, '(]')))
        self.assertEqual([Range(4, 4, '[]')], safe_subtract(Range(4, 8, '[)'), Range(4, 8, '()')))

    def test_intersects_upper_bound(self):
        """
        [source)

            [subtract]
            (subtract)
        """
        self.assertEqual([Range(4, 6, '[)')], safe_subtract(Range(4, 8), Range(6, 12, '[]')))
        self.assertEqual([Range(4, 6, '[]')], safe_subtract(Range(4, 8), Range(6, 12, '()')))

    def test_exact_match(self):
        """

        [  source  )
        [ subtract )


        (  source  )
        ( subtract )

        [  source  ]
        [ subtract ]

        (  source  ]
        ( subtract ]

        """
        self.assertEqual([], safe_subtract(Range(4, 8, '[)'), Range(4, 8, '[)')))
        self.assertEqual([], safe_subtract(Range(4, 8, '[]'), Range(4, 8, '[]')))
        self.assertEqual([], safe_subtract(Range(4, 8, '()'), Range(4, 8, '()')))
        self.assertEqual([], safe_subtract(Range(4, 8, '(]'), Range(4, 8, '(]')))

    def test_upper_bounds_match(self):
        """

        [  source  )
          [subtract)
          (subtract)
        """

        self.assertEqual([Range(4, 5, '[)')], safe_subtract(Range(4, 8, '[)'), Range(5, 8, '[)')))
        self.assertEqual([Range(4, 5, '[]')], safe_subtract(Range(4, 8, '[)'), Range(5, 8, '()')))

        """
        [  source  )
          [subtract]
          (subtract]
        """

        self.assertEqual([Range(4, 5, '[)')], safe_subtract(Range(4, 8, '[)'), Range(5, 8, '[]')))
        self.assertEqual([Range(4, 5, '[]')], safe_subtract(Range(4, 8, '[)'), Range(5, 8, '(]')))

    def test_subtract_within(self):
        """
        [    source    )
           [subtract]
           (subtract)
           [subtract)
           (subtract]
        """

        self.assertEqual(
            [Range(4, 5, '[)'), Range(7, 8, '()')],
            safe_subtract(Range(4, 8, '[)'), Range(5, 7, '[]'))
        )
        self.assertEqual(
            [Range(4, 5, '[]'), Range(7, 8, '[)')],
            safe_subtract(Range(4, 8, '[)'), Range(5, 7, '()'))
        )
        self.assertEqual(
            [Range(4, 5, '[)'), Range(7, 8, '[)')],
            safe_subtract(Range(4, 8, '[)'), Range(5, 7, '[)'))
        )
        self.assertEqual(
            [Range(4, 5, '[]'), Range(7, 8, '()')],
            safe_subtract(Range(4, 8, '[)'), Range(5, 7, '(]'))
        )

    def test_bounds_only_differ(self):
        """
        [ source ]
        (subtract)
        [subtract)
        (subtract]
        """
        self.assertEqual(
            [Range(4, 4, '[]'), Range(8, 8, '[]')],
            safe_subtract(Range(4, 8, '[]'), Range(4, 8, '()'))
        )
        self.assertEqual(
            [Range(8, 8, '[]')],
            safe_subtract(Range(4, 8, '[]'), Range(4, 8, '[)'))
        )
        self.assertEqual(
            [Range(4, 4, '[]')],
            safe_subtract(Range(4, 8, '[]'), Range(4, 8, '(]'))
        )

        """
        ( source )
        [subtract]
        [subtract)
        (subtract]
        """
        self.assertEqual(
            [],
            safe_subtract(Range(4, 8, '()'), Range(4, 8, '[]'))
        )
        self.assertEqual(
            [],
            safe_subtract(Range(4, 8, '()'), Range(4, 8, '(]'))
        )
        self.assertEqual(
            [],
            safe_subtract(Range(4, 8, '()'), Range(4, 8, '[)'))
        )

    def test_subtract_ranges(self):
        self.assertEqual(
            [Range(2, 6), Range(8, 12)],
            array_subtract_all([Range(0, 6), Range(7, 18)], [Range(0, 2), Range(6, 8), Range(12, None)])
        )