// Port of regex-syntax 0.8.11 src/hir/interval.rs.
//
// This module contains an *internal* implementation of interval sets.
//
// The primary invariant that interval sets guards is canonical ordering. That
// is, every interval set contains an ordered sequence of intervals where
// no two intervals are overlapping or adjacent. While this invariant is
// occasionally broken within the implementation, it should be impossible for
// callers to observe it.
//
// Since case folding (as implemented below) breaks that invariant, we roll
// that into this API even though it is a little out of place in an otherwise
// generic interval set. (Hence the reason why the `unicode` module is imported
// here.)
//
// Upstream's `Bound` trait (implemented by `char` and `u8`) is folded into
// `Interval` as the static `bound_*` methods; bounds are `Int`s.
///|
pub struct IntervalSet[I] {
/// A sorted set of non-overlapping ranges.
priv ranges : Array[I]
/// While not required at all for correctness, we keep track of whether an
/// interval set has been case folded or not. This helps us avoid doing
/// redundant work if, for example, a set has already been cased folded.
/// And note that whether a set is folded or not is preserved through
/// all of the pairwise set operations. That is, if both interval sets
/// have been case folded, then any of difference, union, intersection or
/// symmetric difference all produce a case folded set.
///
/// Note that when this is true, it *must* be the case that the set is case
/// folded. But when it's false, the set *may* be case folded.
///
/// Bottom line: this is a performance optimization.
priv mut folded : Bool
}
///|
/// We implement Eq manually so that we don't consider the set's internal
/// 'folded' property to be part of its identity. The 'folded' property is
/// strictly an optimization.
pub impl[I : Interval] Eq for IntervalSet[I] with fn equal(self, other) {
self.ranges == other.ranges
}
///|
pub impl[I : Debug] Debug for IntervalSet[I] with fn to_repr(self) {
Repr(self.ranges)
}
///|
/// Create a new set from a sequence of intervals. Each interval is
/// specified as a pair of bounds, where both bounds are inclusive.
///
/// The given ranges do not need to be in any specific order, and ranges
/// may overlap.
pub fn[I : Interval] IntervalSet::new(intervals : Array[I]) -> IntervalSet[I] {
let ranges = intervals.copy()
// An empty set is case folded.
let folded = ranges.is_empty()
let set = { ranges, folded, }
set.canonicalize()
set
}
///|
/// A copy of this set (Rust `Clone`).
pub fn[I] IntervalSet::copy(self : IntervalSet[I]) -> IntervalSet[I] {
{ ranges: self.ranges.copy(), folded: self.folded, }
}
///|
/// Add a new interval to this set.
pub fn[I : Interval] IntervalSet::push(
self : IntervalSet[I],
interval : I,
) -> Unit {
let i = match self.ranges.binary_search(interval) {
// Exact match, `interval` is already in the set.
Ok(_) => return
Err(i) => i
}
// The search finds us the first index where the previous interval
// start is less than or equal to the new interval start. Since the
// existing intervals are non-overlapping we only need to try to union
// this single preceding interval
let mut interval = interval
let mut start = i
if i > 0 {
let before_i = i - 1
let before = self.ranges[before_i]
if interval_union(before, interval) is Some(union) {
interval = union
start = before_i
}
}
// `interval` may overlap any number of intervals following the
// insertion point so will union each of them until we reach the
// first non-overlapping interval
let mut end = i
for after_i in i.. Iter[I] {
self.ranges.iter()
}
///|
/// Return an immutable slice of intervals in this set.
///
/// The sequence returned is in canonical ordering.
pub fn[I] IntervalSet::intervals(self : IntervalSet[I]) -> ArrayView[I] {
self.ranges[:]
}
///|
/// Expand this interval set such that it contains all case folded
/// characters. For example, if this class consists of the range `a-z`,
/// then applying case folding will result in the class containing both the
/// ranges `a-z` and `A-Z`.
///
/// This returns an error if the necessary case mapping data is not
/// available.
pub fn[I : Interval] IntervalSet::case_fold_simple(
self : IntervalSet[I],
) -> Unit raise CaseFoldError {
if self.folded {
return
}
let len = self.ranges.length()
for i in 0.. {
self.canonicalize()
raise err
}
}
}
self.canonicalize()
self.folded = true
}
///|
/// Union this set with the given set, in place.
pub fn[I : Interval] IntervalSet::union(
self : IntervalSet[I],
other : IntervalSet[I],
) -> Unit {
if other.ranges.is_empty() || self.ranges == other.ranges {
return
}
// This could almost certainly be done more efficiently.
for range in other.ranges {
self.ranges.push(range)
}
self.canonicalize()
self.folded = self.folded && other.folded
}
///|
/// Intersect this set with the given set, in place.
pub fn[I : Interval] IntervalSet::intersect(
self : IntervalSet[I],
other : IntervalSet[I],
) -> Unit {
if self.ranges.is_empty() {
return
}
if other.ranges.is_empty() {
self.ranges.clear()
// An empty set is case folded.
self.folded = true
return
}
// There should be a way to do this in-place with constant memory,
// but I couldn't figure out a simple way to do it. So just append
// the intersection to the end of this range, and then drain it before
// we're done.
let drain_end = self.ranges.length()
let mut a = 0
let mut b = 0
while true {
if interval_intersect(self.ranges[a], other.ranges[b]) is Some(ab) {
self.ranges.push(ab)
}
if self.ranges[a].upper() < other.ranges[b].upper() {
if a + 1 >= drain_end {
break
}
a += 1
} else {
if b + 1 >= other.ranges.length() {
break
}
b += 1
}
}
ignore(self.ranges.drain(0, drain_end))
self.folded = self.folded && other.folded
}
///|
/// Subtract the given set from this set, in place.
pub fn[I : Interval] IntervalSet::difference(
self : IntervalSet[I],
other : IntervalSet[I],
) -> Unit {
if self.ranges.is_empty() || other.ranges.is_empty() {
return
}
// This algorithm is (to me) surprisingly complex. A search of the
// interwebs indicate that this is a potentially interesting problem.
// Folks seem to suggest interval or segment trees, but I'd like to
// avoid the overhead (both runtime and conceptual) of that.
//
// The following is basically my Shitty First Draft. Therefore, in
// order to grok it, you probably need to read each line carefully.
// Simplifications are most welcome!
//
// Remember, we can assume the canonical format invariant here, which
// says that all ranges are sorted, not overlapping and not adjacent in
// each class.
let drain_end = self.ranges.length()
let mut a = 0
let mut b = 0
while a < drain_end && b < other.ranges.length() {
// Basically, the easy cases are when neither range overlaps with
// each other. If the `b` range is less than our current `a`
// range, then we can skip it and move on.
if other.ranges[b].upper() < self.ranges[a].lower() {
b += 1
continue
}
// ... similarly for the `a` range. If it's less than the smallest
// `b` range, then we can add it as-is.
if self.ranges[a].upper() < other.ranges[b].lower() {
let range = self.ranges[a]
self.ranges.push(range)
a += 1
continue
}
// Otherwise, we have overlapping ranges.
guard !interval_is_intersection_empty(self.ranges[a], other.ranges[b]) else {
abort("assertion failed")
}
// This part is tricky and was non-obvious to me without looking
// at explicit examples (see the tests). The trickiness stems from
// two things: 1) subtracting a range from another range could
// yield two ranges and 2) after subtracting a range, it's possible
// that future ranges can have an impact. The loop below advances
// the `b` ranges until they can't possible impact the current
// range.
//
// For example, if our `a` range is `a-t` and our next three `b`
// ranges are `a-c`, `g-i`, `r-t` and `x-z`, then we need to apply
// subtraction three times before moving on to the next `a` range.
let mut range = self.ranges[a]
let mut lost = false
while b < other.ranges.length() &&
!interval_is_intersection_empty(range, other.ranges[b]) {
let old_range = range
range = match interval_difference(range, other.ranges[b]) {
(None, None) => {
// We lost the entire range, so move on to the next
// without adding this one.
lost = true
break
}
(Some(range1), None) | (None, Some(range1)) => range1
(Some(range1), Some(range2)) => {
self.ranges.push(range1)
range2
}
}
// It's possible that the `b` range has more to contribute
// here. In particular, if it is greater than the original
// range, then it might impact the next `a` range *and* it
// has impacted the current `a` range as much as possible,
// so we can quit. We don't bump `b` so that the next `a`
// range can apply it.
if other.ranges[b].upper() > old_range.upper() {
break
}
// Otherwise, the next `b` range might apply to the current
// `a` range.
b += 1
}
if lost {
a += 1
continue
}
self.ranges.push(range)
a += 1
}
while a < drain_end {
let range = self.ranges[a]
self.ranges.push(range)
a += 1
}
ignore(self.ranges.drain(0, drain_end))
self.folded = self.folded && other.folded
}
///|
/// Compute the symmetric difference of the two sets, in place.
///
/// This computes the symmetric difference of two interval sets. This
/// removes all elements in this set that are also in the given set,
/// but also adds all elements from the given set that aren't in this
/// set. That is, the set will contain all elements in either set,
/// but will not contain any elements that are in both sets.
pub fn[I : Interval] IntervalSet::symmetric_difference(
self : IntervalSet[I],
other : IntervalSet[I],
) -> Unit {
// TODO(burntsushi): Fix this so that it amortizes allocation.
let intersection = self.copy()
intersection.intersect(other)
self.union(other)
self.difference(intersection)
}
///|
/// Negate this interval set.
///
/// For all `x` where `x` is any element, if `x` was in this set, then it
/// will not be in this set after negation.
pub fn[I : Interval] IntervalSet::negate(self : IntervalSet[I]) -> Unit {
if self.ranges.is_empty() {
let (min, max) = (I::bound_min_value(), I::bound_max_value())
self.ranges.push(I::create(min, max))
// The set containing everything must case folded.
self.folded = true
return
}
// There should be a way to do this in-place with constant memory,
// but I couldn't figure out a simple way to do it. So just append
// the negation to the end of this range, and then drain it before
// we're done.
let drain_end = self.ranges.length()
// We do checked arithmetic below because of the canonical ordering
// invariant.
if self.ranges[0].lower() > I::bound_min_value() {
let upper = I::bound_decrement(self.ranges[0].lower())
self.ranges.push(I::create(I::bound_min_value(), upper))
}
for i in 1.. Unit {
if self.is_canonical() {
return
}
self.ranges.sort()
guard !self.ranges.is_empty() else { abort("assertion failed") }
// Is there a way to do this in-place with constant memory? I couldn't
// figure out a way to do it. So just append the canonicalization to
// the end of this range, and then drain it before we're done.
let drain_end = self.ranges.length()
for oldi in 0.. drain_end {
let last = self.ranges.length() - 1
if interval_union(self.ranges[last], self.ranges[oldi]) is Some(union) {
self.ranges[last] = union
continue
}
}
let range = self.ranges[oldi]
self.ranges.push(range)
}
ignore(self.ranges.drain(0, drain_end))
}
///|
/// Returns true if and only if this class is in a canonical ordering.
fn[I : Interval] IntervalSet::is_canonical(self : IntervalSet[I]) -> Bool {
for i in 1..= p1 {
return false
}
if interval_is_contiguous(p0, p1) {
return false
}
}
true
}
///|
/// An inclusive interval with bounds of type `Int` (upstream `Interval`,
/// with `Interval::Bound` fixed to code points / byte values).
pub(open) trait Interval: Eq + Compare {
fn lower(Self) -> Int32
fn upper(Self) -> Int32
/// Create a new interval, ordering the bounds.
fn create(Int32, Int32) -> Self
fn case_fold_simple(Self, Array[Self]) -> Unit raise CaseFoldError
/// `Bound::min_value`.
fn bound_min_value() -> Int32
/// `Bound::max_value`.
fn bound_max_value() -> Int32
/// `Bound::increment`.
fn bound_increment(Int32) -> Int32
/// `Bound::decrement`.
fn bound_decrement(Int32) -> Int32
}
///|
/// Union the given overlapping range into this range.
///
/// If the two ranges aren't contiguous, then this returns `None`.
fn[I : Interval] interval_union(this : I, other : I) -> I? {
if !interval_is_contiguous(this, other) {
return None
}
let lower = @cmp.minimum(this.lower(), other.lower())
let upper = @cmp.maximum(this.upper(), other.upper())
Some(I::create(lower, upper))
}
///|
/// Intersect this range with the given range and return the result.
///
/// If the intersection is empty, then this returns `None`.
fn[I : Interval] interval_intersect(this : I, other : I) -> I? {
let lower = @cmp.maximum(this.lower(), other.lower())
let upper = @cmp.minimum(this.upper(), other.upper())
if lower <= upper {
Some(I::create(lower, upper))
} else {
None
}
}
///|
/// Subtract the given range from this range and return the resulting
/// ranges.
///
/// If subtraction would result in an empty range, then no ranges are
/// returned.
fn[I : Interval] interval_difference(this : I, other : I) -> (I?, I?) {
if interval_is_subset(this, other) {
return (None, None)
}
if interval_is_intersection_empty(this, other) {
return (Some(this), None)
}
let add_lower = other.lower() > this.lower()
let add_upper = other.upper() < this.upper()
// We know this because !this.is_subset(other) and the ranges have
// a non-empty intersection.
guard add_lower || add_upper else { abort("assertion failed") }
let mut ret0 = None
let mut ret1 = None
if add_lower {
let upper = I::bound_decrement(other.lower())
ret0 = Some(I::create(this.lower(), upper))
}
if add_upper {
let lower = I::bound_increment(other.upper())
let range = I::create(lower, this.upper())
if ret0 is None {
ret0 = Some(range)
} else {
ret1 = Some(range)
}
}
(ret0, ret1)
}
///|
/// Returns true if and only if the two ranges are contiguous. Two ranges
/// are contiguous if and only if the ranges are either overlapping or
/// adjacent.
fn[I : Interval] interval_is_contiguous(this : I, other : I) -> Bool {
let lower1 = this.lower()
let upper1 = this.upper()
let lower2 = other.lower()
let upper2 = other.upper()
@cmp.maximum(lower1, lower2) <= @cmp.minimum(upper1, upper2) + 1
}
///|
/// Returns true if and only if the intersection of this range and the
/// other range is empty.
fn[I : Interval] interval_is_intersection_empty(this : I, other : I) -> Bool {
let (lower1, upper1) = (this.lower(), this.upper())
let (lower2, upper2) = (other.lower(), other.upper())
@cmp.maximum(lower1, lower2) > @cmp.minimum(upper1, upper2)
}
///|
/// Returns true if and only if this range is a subset of the other range.
fn[I : Interval] interval_is_subset(this : I, other : I) -> Bool {
let (lower1, upper1) = (this.lower(), this.upper())
let (lower2, upper2) = (other.lower(), other.upper())
lower2 <= lower1 && lower1 <= upper2 && lower2 <= upper1 && upper1 <= upper2
}
///|
/// `Bound for char`: increment skipping the surrogate block.
fn char_increment(c : Int32) -> Int32 {
match c {
0xD7FF => 0xE000
c => {
guard c + 1 <= 0x10FFFF else { abort("char overflow") }
c + 1
}
}
}
///|
/// `Bound for char`: decrement skipping the surrogate block.
fn char_decrement(c : Int32) -> Int32 {
match c {
0xE000 => 0xD7FF
c => {
guard c - 1 >= 0 else { abort("char underflow") }
c - 1
}
}
}
///|
/// `Bound for u8`.
fn byte_increment(b : Int32) -> Int32 {
guard b + 1 <= 0xFF else { abort("u8 overflow") }
b + 1
}
///|
/// `Bound for u8`.
fn byte_decrement(b : Int32) -> Int32 {
guard b - 1 >= 0 else { abort("u8 underflow") }
b - 1
}