Closed
Description
The following program (reduced from shepmaster/fuzzy-pickles#62) segfaults when compiled with optimizations in panic=abort mode using beta or nightly rustc.
code
// parse.rs
fn main() {
let tokens = &[Token::Ident, Token::AmpersandEquals, Token::Ident];
let _ = expression(Point::new(tokens));
}
struct Progress<'s, T> {
point: Point<'s>,
status: Result<T, ()>,
}
impl<'s, T> Progress<'s, T> {
pub fn success(point: Point<'s>, val: T) -> Self {
Progress { point: point, status: Ok(val) }
}
pub fn failure(point: Point<'s>) -> Self {
Progress { point: point, status: Err(()) }
}
pub fn map<F, T2>(self, f: F) -> Progress<'s, T2>
where F: FnOnce(T) -> T2
{
Progress { point: self.point, status: self.status.map(f) }
}
}
#[derive(Copy, Clone)]
enum Token {
AmpersandEquals,
Ident,
}
impl Token {
fn into_ident(self) -> Option<Extent> {
match self {
Token::Ident => Some((0,0)),
_ => None,
}
}
fn into_ampersand_equals(self) -> Option<Extent> {
match self {
Token::AmpersandEquals => Some((0,0)),
_ => None,
}
}
}
#[derive(Copy, Clone)]
struct Point<'s> {
pub offset: usize,
pub s: &'s [Token],
}
impl<'s> Point<'s> {
fn new(slice: &'s [Token]) -> Self {
Point {
offset: 0,
s: slice,
}
}
fn advance_by(&self, offset: usize) -> Self {
Point {
offset: self.offset + offset,
s: &self.s[offset..],
}
}
}
pub type Extent = (usize, usize);
enum Expression {
AsType(AsType),
Binary(Binary),
Call(Call),
FieldAccess(FieldAccess),
Slice(Slice),
Value(Value),
}
struct FieldAccess {
target: Box<Expression>,
}
pub struct Value;
pub struct Call {
extent: Extent,
target: Box<Expression>,
args: Vec<Expression>,
}
pub struct Binary {
lhs: Box<Expression>,
rhs: Box<Expression>,
}
struct AsType {
extent: Extent,
target: Box<Expression>,
}
struct Slice {
target: Box<Expression>,
index: Box<Expression>,
}
fn token<'s, F, T>(token_convert: F, pt: Point<'s>) ->
Progress<'s, T>
where F: Fn(Token) -> Option<T>,
{
let original_token = match pt.s.first() {
Some(&token) => token,
None => return Progress::failure(pt),
};
match token_convert(original_token) {
Some(v) => {
Progress::success(pt.advance_by(1), v)
}
None => {
Progress::failure(pt)
}
}
}
enum OperatorInfix {
BitwiseAndAssign(Extent),
}
enum OperatorPostfix {
AsType { typ: () },
Call { args: Vec<Expression> },
FieldAccess { field: () },
Slice { index: Expression },
}
enum OperatorKind {
Infix(OperatorInfix),
Postfix(OperatorPostfix),
}
impl OperatorKind {
fn precedence(&self) -> u8 {
match *self {
OperatorKind::Infix(_) => 10,
OperatorKind::Postfix(OperatorPostfix::Call { .. }) => 10,
OperatorKind::Postfix(_) => 20,
}
}
}
enum InfixOrPostfix {
Infix(OperatorInfix),
Postfix(OperatorPostfix),
}
struct ShuntCar<'s, T> {
value: T,
spt: Point<'s>,
ept: Point<'s>,
}
struct ShuntingYard<'s> {
operators: Vec<ShuntCar<'s, OperatorKind>>,
result: Vec<ShuntCar<'s, Expression>>,
}
type PointRange<'s> = std::ops::Range<Point<'s>>;
type ExprResult<'s, T> = std::result::Result<T, Point<'s>>;
impl<'s> ShuntingYard<'s> {
fn add_infix(&mut self, op: OperatorInfix, spt: Point<'s>, ept: Point<'s>) -> ExprResult<'s, ()>
{
let op = OperatorKind::Infix(op);
self.apply_precedence(&op)?;
self.operators.push(ShuntCar { value: op, spt, ept });
Ok(())
}
fn apply_precedence(&mut self, operator: &OperatorKind) -> ExprResult<'s, ()> {
let op_precedence = operator.precedence();
while self.operators.last().map_or(false, |&ShuntCar { value: ref top, .. }| top.precedence() > op_precedence) {
let ShuntCar { value: _, spt, ept } = self.operators.pop().unwrap();
self.apply_binary(spt..ept)?;
}
Ok(())
}
fn apply_all(&mut self) -> ExprResult<'s, ()> {
while let Some(ShuntCar { value: _, spt, ept }) = self.operators.pop() {
self.apply_binary(spt..ept)?;
}
Ok(())
}
fn apply_infix<F>(&mut self, op_range: PointRange<'s>, f: F) ->
ExprResult<'s, ()>
where F: FnOnce(Expression, Expression) -> Expression
{
let ShuntCar { value: rhs, ept: rexpr_ept, .. } = self.pop_expression(op_range.end)?;
let ShuntCar { value: lhs, spt: lexpr_spt, .. } = self.pop_expression(op_range.start)?;
let new_expr = f(lhs, rhs);
self.result.push(ShuntCar { value: new_expr, spt: lexpr_spt, ept: rexpr_ept });
Ok(())
}
fn apply_binary(&mut self, op_range: PointRange<'s>) ->
ExprResult<'s, ()>
{
self.apply_infix(op_range, |lhs, rhs| {
Expression::Binary(Binary {
lhs: Box::new(lhs),
rhs: Box::new(rhs),
})
})
}
fn pop_expression(&mut self, location: Point<'s>) ->
ExprResult<'s, ShuntCar<'s, Expression>>
{
self.result.pop().ok_or(location)
}
}
enum ExpressionState {
Prefix, // Also "beginning of expression"
Infix,
Atom,
}
fn expression<'s>(pt: Point<'s>) -> Progress<'s, Expression> {
match expression_x(pt) {
Ok(ShuntCar { value: expr, ept, .. }) => Progress::success(ept, expr),
Err(failure_point) => Progress::failure(failure_point),
}
}
fn expression_x<'s>(mut pt: Point<'s>) ->
ExprResult<'s, ShuntCar<'s, Expression>>
{
let mut shunting_yard = ShuntingYard { operators: Vec::new(), result: Vec::new() };
let mut state = ExpressionState::Prefix;
loop {
println!("expression_x loop");
match state {
ExpressionState::Prefix |
ExpressionState::Infix => {
println!("branch 1");
let Progress { point, .. } =
token(Token::into_ident, pt).map(|_| Value).map(Expression::Value);
state = ExpressionState::Atom;
pt = point;
}
ExpressionState::Atom => {
println!("branch 2");
match token(Token::into_ampersand_equals, pt)
.map(OperatorInfix::BitwiseAndAssign).map(InfixOrPostfix::Infix) {
Progress { status: Ok(infix_or_postfix), point } => {
match infix_or_postfix {
InfixOrPostfix::Infix(op) => {
shunting_yard.add_infix(op, pt, point)?;
state = ExpressionState::Infix;
}
InfixOrPostfix::Postfix(_) => unimplemented!(),
}
pt = point;
}
_ => shunting_yard.apply_all()?,
}
}
}
}
}$ rustc --version
rustc 1.18.0-beta.1 (4dce67253 2017-04-25)
$ rustc -C opt-level=1 -C panic=abort parse.rs
[...]
$ ./parse
expression_x loop
branch 1
expression_x loop
branch 2
expression_x loop
branch 1
expression_x loop
branch 2
Segmentation fault