///|
/// m[i][j] bounds signed(i) - signed(j). Coherence is maintained by all constructors.
fn close(n : Int32, m : Array[Array[Int64]]) -> Octagon raise OctagonError {
let size = n * 2
for k in 0.. {
let v = m[i][complement(i)]
if v == INF {
INF
} else {
half_floor(v)
}
})
for i in 0.. Unit raise OctagonError {
validate_constraint(n, c)
let i = term_index(n, c.left)
let (j, b) = match c.right {
None => (complement(i), c.bound * 2L)
Some(t) => (complement(term_index(n, t)), c.bound)
}
if b < m[i][j] {
m[i][j] = b
m[complement(j)][complement(i)] = b
}
}
///|
pub fn from_constraints(
n : Int32,
constraints : Array[Constraint],
) -> Octagon raise OctagonError {
let s = top(n)
s.refine(constraints)
}
///|
/// Intersection with guards; all inputs validated even for an empty domain.
pub fn Octagon::refine(
self : Octagon,
constraints : Array[Constraint],
) -> Octagon raise OctagonError {
if constraints.length() > 4096 {
raise Limit(
"at most 4096 constraints per operation, got \{constraints.length()}",
)
}
let m = clone_matrix(self.matrix)
for c in constraints {
insert(m, self.dimensions, c)
}
if self.empty {
return self
}
close(self.dimensions, m)
}
///|
pub fn Octagon::interval(
self : Octagon,
i : Int32,
) -> Interval? raise OctagonError {
variable(self.dimensions, i)
if self.empty {
return None
}
let s = self.canonical()
let hi = s.matrix[i * 2][i * 2 + 1]
let lo = s.matrix[i * 2 + 1][i * 2]
Some({
lower: if lo == INF {
None
} else {
Some(-half_floor(lo))
},
upper: if hi == INF {
None
} else {
Some(half_floor(hi))
},
})
}
///|
/// All variable intervals from a single canonicalisation.
/// Entries are `None` only when the domain is empty.
pub fn Octagon::intervals(
self : Octagon,
) -> Array[Interval?] raise OctagonError {
let result : Array[Interval?] = []
if self.empty {
for _ in 0.. error.
/// None => expression is unbounded above.
pub fn Octagon::bound(
self : Octagon,
a : Term,
b : Term?,
) -> Int64? raise OctagonError {
let i = term_index(self.dimensions, a)
let j = match b {
Some(t) => complement(term_index(self.dimensions, t))
None => complement(i)
}
if self.empty {
raise Invalid("an empty domain has no expression bounds")
}
let s = self.canonical()
let v = s.matrix[i][j]
if v == INF {
None
} else {
Some(if b is None { half_floor(v) } else { v })
}
}
///|
pub fn Octagon::entails(
self : Octagon,
c : Constraint,
) -> Bool raise OctagonError {
validate_constraint(self.dimensions, c)
if self.empty {
return true
}
match self.bound(c.left, c.right) {
Some(b) => b <= c.bound
None => false
}
}
///|
/// Direct evaluation of a concrete integer vector, without solving or closure.
pub fn satisfies(
values : Array[Int64],
c : Constraint,
) -> Bool raise OctagonError {
validate_dimensions(values.length())
validate_constraint(values.length(), c)
for v in values {
if v < -MAX_FINITE || v > MAX_FINITE {
raise Limit("witness coordinate too large")
}
}
let a = values[c.left.variable] * c.left.sign.to_int64()
let b = match c.right {
None => 0L
Some(t) => values[t.variable] * t.sign.to_int64()
}
a + b <= c.bound
}
///|
pub fn Octagon::contains(
self : Octagon,
values : Array[Int64],
) -> Bool raise OctagonError {
if values.length() != self.dimensions {
raise Invalid("witness dimension mismatch")
}
for v in values {
if v < -MAX_FINITE || v > MAX_FINITE {
raise Limit("witness coordinate too large")
}
}
if self.empty {
return false
}
let signed = Array::makei(self.dimensions * 2, i => {
if i % 2 == 0 {
values[i / 2]
} else {
-values[i / 2]
}
})
for i in 0.. self.matrix[i][j] {
return false
}
}
}
true
}