///|
/// Errors from the textual front-end carry the statement index, not a byte
/// offset, because statements are the unit users edit.
priv enum Token {
TInt(Int64)
TVar(Int32)
TPlus
TMinus
TLe
TGe
TEq
TLBracket
TRBracket
TComma
TIn
TSep
TEnd
}
///|
fn tokenize(input : String) -> Array[Token] raise OctagonError {
let chars : Array[Char] = []
for ch in input.iter() {
chars.push(ch)
}
let tokens : Array[Token] = []
let mut i = 0
while i < chars.length() {
let ch = chars[i]
if ch == ' ' || ch == '\t' || ch == '\r' {
i = i + 1
} else if ch == '\n' || ch == ';' {
tokens.push(TSep)
i = i + 1
} else if ch == '#' {
while i < chars.length() && chars[i] != '\n' {
i = i + 1
}
} else if ch == '<' {
if i + 1 < chars.length() && chars[i + 1] == '=' {
tokens.push(TLe)
i = i + 2
} else {
raise Invalid("text: expected <= after '<'")
}
} else if ch == '>' {
if i + 1 < chars.length() && chars[i + 1] == '=' {
tokens.push(TGe)
i = i + 2
} else {
raise Invalid("text: expected >= after '>'")
}
} else if ch == '=' {
tokens.push(TEq)
i = i + 1
} else if ch == '+' {
tokens.push(TPlus)
i = i + 1
} else if ch == '-' {
tokens.push(TMinus)
i = i + 1
} else if ch == '[' {
tokens.push(TLBracket)
i = i + 1
} else if ch == ']' {
tokens.push(TRBracket)
i = i + 1
} else if ch == ',' {
tokens.push(TComma)
i = i + 1
} else if ch.is_ascii_digit() {
let mut value = 0L
while i < chars.length() && chars[i].is_ascii_digit() {
value = value * 10L + (chars[i].to_int() - 48).to_int64()
if value > 1000000000000000L {
raise Limit("text: integer literal exceeds 10^15")
}
i = i + 1
}
tokens.push(TInt(value))
} else if ch == 'x' {
i = i + 1
let mut value = 0
let mut digits = false
while i < chars.length() && chars[i].is_ascii_digit() {
value = value * 10 + (chars[i].to_int() - 48)
digits = true
if value > 1000000 {
raise Limit("text: variable index exceeds 1000000")
}
i = i + 1
}
if !digits {
raise Invalid("text: expected a decimal variable index after 'x'")
}
tokens.push(TVar(value))
} else if ch == 'i' &&
i + 1 < chars.length() &&
chars[i + 1] == 'n' &&
(i + 2 >= chars.length() || !chars[i + 2].is_ascii_alphabetic()) {
tokens.push(TIn)
i = i + 2
} else {
raise Invalid("text: unexpected character in constraint input")
}
}
tokens.push(TEnd)
tokens
}
///|
fn at(tokens : Array[Token], index : Int32) -> Token {
if index >= 0 && index < tokens.length() {
tokens[index]
} else {
TEnd
}
}
///|
fn check_separator(
tokens : Array[Token],
index : Int32,
statement : Int32,
) -> Unit raise OctagonError {
match at(tokens, index) {
TSep | TEnd => ()
_ => raise Invalid("text: statement \{statement} has trailing tokens")
}
}
///|
fn read_int(
tokens : Array[Token],
index : Int32,
) -> (Int64, Int32) raise OctagonError {
let mut cursor = index
let sign = match at(tokens, cursor) {
TMinus => {
cursor = cursor + 1
-1L
}
TPlus => {
cursor = cursor + 1
1L
}
_ => 1L
}
let value = match at(tokens, cursor) {
TInt(value) => value
_ => raise Invalid("text: expected an integer literal")
}
(sign * value, cursor + 1)
}
///|
fn parse_interval(
dimensions : Int32,
tokens : Array[Token],
start : Int32,
statement : Int32,
) -> (Array[Constraint], Int32) raise OctagonError {
let v = match at(tokens, start) {
TVar(v) => v
_ => raise Invalid("text: expected a variable")
}
variable(dimensions, v)
if !(at(tokens, start + 1) is TIn) {
raise Invalid("text: expected 'in' after the variable")
}
if !(at(tokens, start + 2) is TLBracket) {
raise Invalid("text: expected '[' in an interval")
}
let (lo, after_lo) = read_int(tokens, start + 3)
if !(at(tokens, after_lo) is TComma) {
raise Invalid("text: expected ',' in an interval")
}
let (hi, after_hi) = read_int(tokens, after_lo + 1)
if !(at(tokens, after_hi) is TRBracket) {
raise Invalid("text: expected ']' in an interval")
}
if lo > hi {
raise Invalid("text: interval lower bound exceeds its upper bound")
}
let next = after_hi + 1
check_separator(tokens, next, statement)
([lower(v, lo), upper(v, hi)], next)
}
///|
fn negate_constraint(c : Constraint) -> Constraint {
{
left: { variable: c.left.variable, sign: -c.left.sign, },
right: match c.right {
None => None
Some(t) => Some({ variable: t.variable, sign: -t.sign, })
},
bound: -c.bound,
}
}
///|
fn parse_expression(
dimensions : Int32,
tokens : Array[Token],
start : Int32,
statement : Int32,
) -> (Array[Constraint], Int32) raise OctagonError {
let mut index = start
let left_sign = match at(tokens, index) {
TMinus => {
index = index + 1
-1
}
TPlus => {
index = index + 1
1
}
_ => 1
}
let left_var = match at(tokens, index) {
TVar(v) => v
_ => raise Invalid("text: expected a variable in an expression")
}
variable(dimensions, left_var)
index = index + 1
let mut right_var : Int32? = None
let mut right_sign = 1
match at(tokens, index) {
TPlus | TMinus => {
right_sign = if at(tokens, index) is TPlus { 1 } else { -1 }
index = index + 1
let v = match at(tokens, index) {
TVar(v) => v
_ => raise Invalid("text: expected a variable after the sign")
}
variable(dimensions, v)
right_var = Some(v)
index = index + 1
}
_ => ()
}
let relation_token = at(tokens, index)
index = index + 1
if !(relation_token is TLe) &&
!(relation_token is TGe) &&
!(relation_token is TEq) {
raise Invalid("text: expected <=, >= or = before the bound")
}
let (raw_bound, after_bound) = read_int(tokens, index)
index = after_bound
check_separator(tokens, index, statement)
let positive = relation_token is TLe || relation_token is TEq
let sign = if positive { left_sign } else { -left_sign }
let bound = if positive { raw_bound } else { -raw_bound }
let left : Term = { variable: left_var, sign, }
let right : Term? = match right_var {
None => None
Some(v) =>
Some({
variable: v,
sign: if positive {
right_sign
} else {
-right_sign
},
})
}
let c : Constraint = { left, right, bound, }
validate_constraint(dimensions, c)
if relation_token is TEq {
let flipped = negate_constraint(c)
validate_constraint(dimensions, flipped)
([c, flipped], index)
} else {
([c], index)
}
}
///|
/// Parse a small line-oriented constraint language for the integer octagon
/// domain. Statements are separated by newlines or semicolons; '#' starts a
/// comment. Supported forms:
///
/// x0 in [0, 100]
/// x0 <= 100
/// x0 >= 0
/// x0 + x1 <= 100
/// x0 - x1 <= 2
/// -x0 + x1 <= 2
///
/// Dimensions are supplied by the caller; all indices and bounds are validated.
pub fn parse_constraints(
dimensions : Int32,
input : String,
) -> Array[Constraint] raise OctagonError {
validate_dimensions(dimensions)
if input.length() > 200000 {
raise Limit("text: input exceeds 200000 UTF-16 units")
}
let tokens = tokenize(input)
let result : Array[Constraint] = []
let mut index = 0
let mut statement = 0
while true {
while at(tokens, index) is TSep {
index = index + 1
}
if at(tokens, index) is TEnd {
break
}
let (parsed, next) = if at(tokens, index) is TVar(_) &&
at(tokens, index + 1) is TIn {
parse_interval(dimensions, tokens, index, statement)
} else {
parse_expression(dimensions, tokens, index, statement)
}
for c in parsed {
result.push(c)
}
if result.length() > 4096 {
raise Limit("text: at most 4096 constraints")
}
index = next
statement = statement + 1
}
result
}
///|
/// Serialise a non-empty domain as a parseable constraint text. The empty text
/// denotes the top domain. Bottom has no finite conjunction and raises Invalid.
pub fn Octagon::to_text(self : Octagon) -> String raise OctagonError {
if self.empty {
raise Invalid("bottom has no finite text form")
}
if self.is_top() {
return ""
}
let s = self.canonical()
let ranges = s.intervals()
let sb = StringBuilder()
let mut first = true
for i in 0.. ()
Some(r) =>
match (r.lower, r.upper) {
(Some(lo), Some(hi)) => {
if !first {
sb.write("\n")
}
first = false
sb.write("x\{i} in [\{lo}, \{hi}]")
}
(Some(lo), None) => {
if !first {
sb.write("\n")
}
first = false
sb.write("x\{i} >= \{lo}")
}
(None, Some(hi)) => {
if !first {
sb.write("\n")
}
first = false
sb.write("x\{i} <= \{hi}")
}
(None, None) => ()
}
}
}
for i in 0.. render_constraint(relation(positive(i), positive(j), forms[k]))
1 => render_constraint(relation(positive(i), negative(j), forms[k]))
2 => render_constraint(relation(negative(i), positive(j), forms[k]))
_ => render_constraint(relation(negative(i), negative(j), forms[k]))
}
sb.write(text)
}
}
}
}
sb.to_string()
}