use lalrpop_util::ParseError;
use crate::assemble::{Elem, SpannedElem, assemble_constraints, assemble_objectives};
use crate::lexer::{Token, LexerError, RawCoefficient, RawConstraint, OptionalSection, ParseResult, SosEntryKind};
use crate::model::{ComparisonOp, SOSType, Sense, VariableType};
grammar<'input>;
extern {
type Location = usize;
type Error = LexerError;
enum Token<'input> {
// Keywords
"sense" => Token::SenseKw(<Sense>),
"subject to" => Token::SubjectTo,
"bounds" => Token::Bounds,
"generals" => Token::Generals,
"integers" => Token::Integers,
"binaries" => Token::Binaries,
"semi-continuous" => Token::SemiContinuous,
"sos" => Token::Sos,
"end" => Token::End,
"free" => Token::Free,
"sos_type" => Token::SosType(<SOSType>),
// Values
"infinity" => Token::Infinity(<f64>),
"number" => Token::Number(<f64>),
"identifier" => Token::Identifier(<&'input str>),
// Operators
"<=" => Token::Lte,
">=" => Token::Gte,
"<" => Token::Lt,
">" => Token::Gt,
"=" => Token::Eq,
"+" => Token::Plus,
"-" => Token::Minus,
":" => Token::Colon,
"::" => Token::DoubleColon,
}
}
pub LpProblem: ParseResult<'input> = {
<sense:"sense">
<obj_elems:ObjElem*>
"subject to"
<con_elems:ConElem*>
<sections:AnySection*>
"end"?
=>? {
// The objective and constraint bodies are collected as flat element
// lists and assembled in Rust: entry boundaries (e.g. a trailing
// constant vs. a coefficient of the next objective's name) need more
// than one token of lookahead. See `crate::assemble`.
let objectives = assemble_objectives(&obj_elems).map_err(|error| ParseError::User { error })?;
let constraints = assemble_constraints(&con_elems).map_err(|error| ParseError::User { error })?;
let mut bounds: Vec<(&'input str, VariableType)> = Vec::new();
let mut generals: Vec<&'input str> = Vec::new();
let mut integers: Vec<&'input str> = Vec::new();
let mut binaries: Vec<&'input str> = Vec::new();
let mut semi_continuous: Vec<&'input str> = Vec::new();
let mut sos: Vec<RawConstraint<'input>> = Vec::new();
for section in sections {
match section {
OptionalSection::Bounds(b) => bounds.extend(b),
OptionalSection::Generals(g) => generals.extend(g),
OptionalSection::Integers(i) => integers.extend(i),
OptionalSection::Binaries(b) => binaries.extend(b),
OptionalSection::SemiContinuous(s) => semi_continuous.extend(s),
OptionalSection::SOS(s) => sos.extend(s),
}
}
Ok(ParseResult { sense, objectives, constraints, bounds, generals, integers, binaries, semi_continuous, sos })
}
};
// Any optional section in any order
AnySection: OptionalSection<'input> = {
<b:BoundsSection> => OptionalSection::Bounds(b),
<g:GeneralsSection> => OptionalSection::Generals(g),
<i:IntegersSection> => OptionalSection::Integers(i),
<b:BinariesSection> => OptionalSection::Binaries(b),
<s:SemiSection> => OptionalSection::SemiContinuous(s),
<s:SosSection> => OptionalSection::SOS(s),
};
// One element of the objective section body. `name ":"` is folded into a
// single element so that a bare identifier is unambiguously a variable.
ObjElem: SpannedElem<'input> = {
<loc:@L> <id:"identifier"> ":" => (loc, Elem::Name(id)),
<loc:@L> <id:"identifier"> => (loc, Elem::Var(id)),
<loc:@L> <n:"number"> => (loc, Elem::Num(n)),
<loc:@L> <i:"infinity"> => (loc, Elem::Num(i)),
<loc:@L> "+" => (loc, Elem::Plus),
<loc:@L> "-" => (loc, Elem::Minus),
};
// One element of the constraint section body. Also admits `name "::"` and
// comparison operators.
ConElem: SpannedElem<'input> = {
<loc:@L> <id:"identifier"> ":" => (loc, Elem::Name(id)),
<loc:@L> <id:"identifier"> "::" => (loc, Elem::Name(id)),
<loc:@L> <id:"identifier"> => (loc, Elem::Var(id)),
<loc:@L> <n:"number"> => (loc, Elem::Num(n)),
<loc:@L> <i:"infinity"> => (loc, Elem::Num(i)),
<loc:@L> "+" => (loc, Elem::Plus),
<loc:@L> "-" => (loc, Elem::Minus),
<loc:@L> <op:CompOp> => (loc, Elem::Op(op)),
};
BoundsSection: Vec<(&'input str, VariableType)> = {
"bounds" <bounds:BoundSpec*> => bounds,
};
// `<` and `>` are treated as synonyms of `<=` / `>=` in bounds, per the
// CPLEX and Gurobi LP specifications.
Le: () = {
"<=" => (),
"<" => (),
};
Ge: () = {
">=" => (),
">" => (),
};
BoundSpec: (&'input str, VariableType) = {
// Free variable: "x1 free"
<var:"identifier"> "free" => (var, VariableType::Free),
// Double bound: "0 <= x1 <= 5"
<lb:NumericValue> Le <var:"identifier"> Le <ub:NumericValue> => {
(var, VariableType::DoubleBound(lb, ub))
},
// Reversed double bound: "5 >= x1 >= 0"
<ub:NumericValue> Ge <var:"identifier"> Ge <lb:NumericValue> => {
(var, VariableType::DoubleBound(lb, ub))
},
// Lower bound: "x1 >= 5" or "5 <= x1"
<var:"identifier"> Ge <bound:NumericValue> => (var, VariableType::LowerBound(bound)),
<bound:NumericValue> Le <var:"identifier"> => (var, VariableType::LowerBound(bound)),
// Upper bound: "x1 <= 5" or "5 >= x1"
<var:"identifier"> Le <bound:NumericValue> => (var, VariableType::UpperBound(bound)),
<bound:NumericValue> Ge <var:"identifier"> => (var, VariableType::UpperBound(bound)),
// Fixed value (equality bound): "x1 = 5" means x1 is fixed at 5
<var:"identifier"> "=" <bound:NumericValue> => (var, VariableType::DoubleBound(bound, bound)),
<bound:NumericValue> "=" <var:"identifier"> => (var, VariableType::DoubleBound(bound, bound)),
};
GeneralsSection: Vec<&'input str> = {
"generals" <vars:"identifier"*> => vars,
};
IntegersSection: Vec<&'input str> = {
"integers" <vars:"identifier"*> => vars,
};
BinariesSection: Vec<&'input str> = {
"binaries" <vars:"identifier"*> => vars,
};
SemiSection: Vec<&'input str> = {
"semi-continuous" <vars:"identifier"*> => vars,
};
SosSection: Vec<RawConstraint<'input>> = {
"sos" <entries:SosEntry*> => {
// Group entries into constraints
let mut constraints = Vec::new();
let mut current_name: Option<&'input str> = None;
let mut current_type: Option<SOSType> = None;
let mut current_offset: Option<usize> = None;
let mut current_weights: Vec<RawCoefficient<'input>> = Vec::new();
for entry in entries {
match entry {
SosEntryKind::Header(name, sos_type, offset) => {
// Save previous constraint if exists
if let (Some(n), Some(t)) = (current_name.take(), current_type.take()) {
if !current_weights.is_empty() {
constraints.push(RawConstraint::SOS {
name: std::borrow::Cow::Borrowed(n),
sos_type: t,
weights: std::mem::take(&mut current_weights),
byte_offset: current_offset,
});
}
}
current_name = Some(name);
current_type = Some(sos_type);
current_offset = Some(offset);
}
SosEntryKind::Weight(coeff) => {
current_weights.push(coeff);
}
}
}
// Save last constraint
if let (Some(n), Some(t)) = (current_name, current_type) {
if !current_weights.is_empty() {
constraints.push(RawConstraint::SOS {
name: std::borrow::Cow::Borrowed(n),
sos_type: t,
weights: current_weights,
byte_offset: current_offset,
});
}
}
constraints
},
};
// Entry in SOS section - either a constraint header or a weight
SosEntry: SosEntryKind<'input> = {
// Header: "name: S1::" or "name: S2::"
<loc:@L> <name:"identifier"> ":" <sos_type:"sos_type"> "::" => SosEntryKind::Header(name, sos_type, loc),
// Weight: "var:value"
<var:"identifier"> ":" <weight:NumericValue> => SosEntryKind::Weight(RawCoefficient { name: var, value: weight }),
};
CompOp: ComparisonOp = {
"<=" => ComparisonOp::LTE,
">=" => ComparisonOp::GTE,
"<" => ComparisonOp::LT,
">" => ComparisonOp::GT,
"=" => ComparisonOp::EQ,
};
NumericValue: f64 = {
<n:"number"> => n,
<n:"infinity"> => n,
"+" <n:"number"> => n,
"+" <n:"infinity"> => n,
"-" <n:"number"> => -n,
"-" <n:"infinity"> => -n,
};