peephole.rs

//! Optimisations that replace parts of the BF AST with faster
//! equivalents.

use std::collections::{HashMap, HashSet};
use std::hash::Hash;
use std::num::Wrapping;

use itertools::Itertools;

use crate::diagnostics::Warning;

use crate::bfir::AstNode::*;
use crate::bfir::{get_position, AstNode, BfValue, Combine, Position};

const MAX_OPT_ITERATIONS: u64 = 40;

/// Given a sequence of BF instructions, apply peephole optimisations
/// (repeatedly if necessary).
pub fn optimize(
    instrs: Vec<AstNode>,
    pass_specification: &Option<String>,
) -> (Vec<AstNode>, Vec<Warning>) {
    // Many of our individual peephole optimisations remove
    // instructions, creating new opportunities to combine. We run
    // until we've found a fixed-point where no further optimisations
    // can be made.
    let mut prev = instrs.clone();
    let mut warnings = vec![];

    let (mut result, warning) = optimize_once(instrs, pass_specification);

    if let Some(warning) = warning {
        warnings.push(warning);
    }

    for _ in 0..MAX_OPT_ITERATIONS {
        if prev == result {
            return (result, warnings);
        } else {
            prev = result.clone();

            let (new_result, new_warning) = optimize_once(result, pass_specification);

            if let Some(warning) = new_warning {
                warnings.push(warning);
            }
            result = new_result;
        }
    }

    // TODO: use proper Info here.
    eprintln!(
        "Warning: ran peephole optimisations {} times but did not reach a fixed point!",
        MAX_OPT_ITERATIONS
    );

    (result, warnings)
}

/// Apply all our peephole optimisations once and return the result.
fn optimize_once(
    instrs: Vec<AstNode>,
    pass_specification: &Option<String>,
) -> (Vec<AstNode>, Option<Warning>) {
    let pass_specification = pass_specification.clone().unwrap_or_else(|| {
        "combine_inc,combine_ptr,known_zero,\
         multiply,zeroing_loop,combine_set,\
         dead_loop,redundant_set,read_clobber,\
         pure_removal,offset_sort"
            .to_owned()
    });
    let passes: Vec<_> = pass_specification.split(',').collect();

    let mut instrs = instrs;

    if passes.contains(&"combine_inc") {
        instrs = combine_increments(instrs);
    }
    if passes.contains(&"combine_ptr") {
        instrs = combine_ptr_increments(instrs);
    }
    if passes.contains(&"known_zero") {
        instrs = annotate_known_zero(instrs);
    }
    if passes.contains(&"multiply") {
        instrs = extract_multiply(instrs);
    }
    if passes.contains(&"zeroing_loop") {
        instrs = zeroing_loops(instrs);
    }
    if passes.contains(&"combine_set") {
        instrs = combine_set_and_increments(instrs);
    }
    if passes.contains(&"dead_loop") {
        instrs = remove_dead_loops(instrs);
    }
    if passes.contains(&"redundant_set") {
        instrs = remove_redundant_sets(instrs);
    }
    if passes.contains(&"read_clobber") {
        instrs = remove_read_clobber(instrs);
    }
    let warning = if passes.contains(&"pure_removal") {
        let (removed, pure_warning) = remove_pure_code(instrs);
        instrs = removed;
        pure_warning
    } else {
        None
    };

    if passes.contains(&"offset_sort") {
        instrs = sort_by_offset(instrs);
    }

    (instrs, warning)
}

/// Defines a method on iterators to map a function over all loop bodies.
trait MapLoopsExt: Iterator<Item = AstNode> {
    fn map_loops<F>(&mut self, f: F) -> Vec<AstNode>
    where
        F: Fn(Vec<AstNode>) -> Vec<AstNode>,
    {
        self.map(|instr| match instr {
            Loop { body, position } => Loop {
                body: f(body),
                position,
            },
            other => other,
        })
        .collect()
    }
}

impl<I> MapLoopsExt for I where I: Iterator<Item = AstNode> {}

/// Given an index into a vector of instructions, find the index of
/// the previous instruction that modified the current cell. If we're
/// unsure, or there isn't one, return None.
///
/// Note this totally ignores the instruction at the index given, even
/// if it has an offset. E.g. if the instruction is
/// Set {amount:100, offset: 1}, we're still considering previous instructions that
/// modify the current cell, not the (cell_index + 1)th cell.
fn previous_cell_change(instrs: &[AstNode], index: usize) -> Option<usize> {
    assert!(index < instrs.len());

    let mut needed_offset = 0;
    for i in (0..index).rev() {
        match instrs[i] {
            Increment { offset, .. } | Set { offset, .. } => {
                if offset == needed_offset {
                    return Some(i);
                }
            }
            PointerIncrement { amount, .. } => {
                needed_offset += amount;
            }
            MultiplyMove { ref changes, .. } => {
                // These cells are written to.
                let mut offsets: Vec<isize> = changes.keys().cloned().collect();
                // This cell is zeroed.
                offsets.push(0);

                if offsets.contains(&needed_offset) {
                    return Some(i);
                }
            }
            // No cells changed, so just keep working backwards.
            Write { .. } => {}
            // These instructions may have modified the cell, so
            // we return None for "I don't know".
            Read { .. } | Loop { .. } => return None,
        }
    }
    None
}

/// Inverse of `previous_cell_change`.
///
/// This is very similar to `previous_cell_change` and previous
/// implementations called `previous_cell_change` on the reversed
/// vector. This proved extremely hard to reason about. Instead, we
/// have copied the body of `previous_cell_change` and highlighted the
/// differences.
fn next_cell_change(instrs: &[AstNode], index: usize) -> Option<usize> {
    assert!(index < instrs.len());

    let mut needed_offset = 0;
    // Unlike previous_cell_change, we iterate forward.
    for (i, instr) in instrs.iter().enumerate().skip(index + 1) {
        match *instr {
            Increment { offset, .. } | Set { offset, .. } => {
                if offset == needed_offset {
                    return Some(i);
                }
            }
            PointerIncrement { amount, .. } => {
                // Unlike previous_cell_change we must subtract the desired amount.
                needed_offset -= amount;
            }
            MultiplyMove { ref changes, .. } => {
                // These cells are written to.
                let mut offsets: Vec<isize> = changes.keys().cloned().collect();
                // This cell is zeroed.
                offsets.push(0);

                if offsets.contains(&needed_offset) {
                    return Some(i);
                }
            }
            // No cells changed, so just keep working backwards.
            Write { .. } => {}
            // These instructions may have modified the cell, so
            // we return None for "I don't know".
            Read { .. } | Loop { .. } => return None,
        }
    }
    None
}

/// Combine consecutive increments into a single increment
/// instruction.
fn combine_increments(instrs: Vec<AstNode>) -> Vec<AstNode> {
    instrs
        .into_iter()
        .coalesce(|prev_instr, instr| {
            // Collapse consecutive increments.
            if let Increment {
                amount: prev_amount,
                offset: prev_offset,
                position: prev_pos,
            } = prev_instr
            {
                if let Increment {
                    amount,
                    offset,
                    position,
                } = instr
                {
                    if prev_offset == offset {
                        return Ok(Increment {
                            amount: amount + prev_amount,
                            offset,
                            position: prev_pos.combine(position),
                        });
                    }
                }
            }
            Err((prev_instr, instr))
        })
        .filter(|instr| {
            // Remove any increments of 0.
            if let Increment {
                amount: Wrapping(0),
                ..
            } = *instr
            {
                return false;
            }
            true
        })
        .map_loops(combine_increments)
}

fn combine_ptr_increments(instrs: Vec<AstNode>) -> Vec<AstNode> {
    instrs
        .into_iter()
        .coalesce(|prev_instr, instr| {
            // Collapse consecutive increments.
            if let PointerIncrement {
                amount: prev_amount,
                position: prev_pos,
            } = prev_instr
            {
                if let PointerIncrement { amount, position } = instr {
                    return Ok(PointerIncrement {
                        amount: amount + prev_amount,
                        position: prev_pos.combine(position),
                    });
                }
            }
            Err((prev_instr, instr))
        })
        .filter(|instr| {
            // Remove any pointer increments of 0.
            if let PointerIncrement { amount: 0, .. } = *instr {
                return false;
            }
            true
        })
        .map_loops(combine_ptr_increments)
}

/// Don't bother updating cells if they're immediately overwritten
/// by a value from stdin.
// TODO: this should generate a warning too.
fn remove_read_clobber(instrs: Vec<AstNode>) -> Vec<AstNode> {
    let mut redundant_instr_positions = HashSet::new();
    let mut last_write_index = None;

    for (index, instr) in instrs.iter().enumerate() {
        match *instr {
            Read { .. } => {
                // If we can find the time this cell was modified:
                if let Some(prev_modify_index) = previous_cell_change(&instrs, index) {
                    // This modify instruction is not redundant if we
                    // wrote anything afterwards.
                    if let Some(write_index) = last_write_index {
                        if write_index > prev_modify_index {
                            continue;
                        }
                    }

                    // MultiplyMove instructions are not redundant,
                    // because they affect other cells too.
                    if matches!(instrs[prev_modify_index], MultiplyMove { .. }) {
                        continue;
                    }

                    redundant_instr_positions.insert(prev_modify_index);
                }
            }
            Write { .. } => {
                last_write_index = Some(index);
            }
            _ => {}
        }
    }

    instrs
        .into_iter()
        .enumerate()
        .filter(|&(index, _)| !redundant_instr_positions.contains(&index))
        .map(|(_, instr)| instr)
        .map_loops(remove_read_clobber)
}

/// Convert [-] to Set 0.
fn zeroing_loops(instrs: Vec<AstNode>) -> Vec<AstNode> {
    instrs
        .into_iter()
        .map(|instr| {
            if let Loop { ref body, position } = instr {
                // If the loop is [-]
                if body.len() == 1 {
                    if let Increment {
                        amount: Wrapping(-1),
                        offset: 0,
                        ..
                    } = body[0]
                    {
                        return Set {
                            amount: Wrapping(0),
                            offset: 0,
                            position,
                        };
                    }
                }
            }
            instr
        })
        .map_loops(zeroing_loops)
}

/// Remove any loops where we know the current cell is zero.
fn remove_dead_loops(instrs: Vec<AstNode>) -> Vec<AstNode> {
    instrs
        .clone()
        .into_iter()
        .enumerate()
        .filter(|&(index, ref instr)| {
            if !matches!(instr, Loop { .. }) {
                // Keep all instructions that aren't loops.
                return true;
            }

            // Find the previous change instruction:
            if let Some(prev_change_index) = previous_cell_change(&instrs, index) {
                let prev_instr = &instrs[prev_change_index];
                // If the previous instruction set to zero, our loop is dead.
                // TODO: MultiplyMove also zeroes the current cell.
                // TODO: define an is_set_zero() helper.
                if matches!(
                    prev_instr,
                    Set {
                        amount: Wrapping(0),
                        offset: 0,
                        ..
                    }
                ) {
                    return false;
                }
            }
            true
        })
        .map(|(_, instr)| instr)
        .map_loops(remove_dead_loops)
}

/// Reorder flat sequences of instructions so we use offsets and only
/// have one pointer increment at the end. For example, given "+>+>+<"
/// we return:
/// Increment { amount: 1, offset: 0 }
/// Increment { amount: 1, offset: 1 }
/// Increment { amount: 2, offset: 2 }
/// PointerIncrement(1)
fn sort_by_offset(instrs: Vec<AstNode>) -> Vec<AstNode> {
    let mut sequence = vec![];
    let mut result = vec![];

    for instr in instrs {
        if matches!(
            instr,
            Increment { .. } | Set { .. } | PointerIncrement { .. }
        ) {
            sequence.push(instr);
        } else {
            if !sequence.is_empty() {
                result.extend(sort_sequence_by_offset(sequence));
                sequence = vec![];
            }
            if let Loop { body, position } = instr {
                result.push(Loop {
                    body: sort_by_offset(body),
                    position,
                });
            } else {
                result.push(instr);
            }
        }
    }

    if !sequence.is_empty() {
        result.extend(sort_sequence_by_offset(sequence));
    }

    result
}

/// Given a `HashMap` with orderable keys, return the values according to
/// the key order.
/// {2: 'foo': 1: 'bar'} => vec!['bar', 'foo']
fn ordered_values<K: Ord + Hash + Eq, V>(map: HashMap<K, V>) -> Vec<V> {
    let mut items: Vec<_> = map.into_iter().collect();
    items.sort_by(|a, b| a.0.cmp(&b.0));
    items.into_iter().map(|(_, v)| v).collect()
}

/// Given a BF program, combine sets/increments using offsets so we
/// have single `PointerIncrement` at the end.
fn sort_sequence_by_offset(instrs: Vec<AstNode>) -> Vec<AstNode> {
    let mut instrs_by_offset: HashMap<isize, Vec<AstNode>> = HashMap::new();
    let mut current_offset = 0;
    let mut last_ptr_inc_pos = None;

    for instr in instrs {
        match instr {
            Increment {
                amount,
                offset,
                position,
            } => {
                let new_offset = offset + current_offset;
                let same_offset_instrs = instrs_by_offset.entry(new_offset).or_default();
                same_offset_instrs.push(Increment {
                    amount,
                    offset: new_offset,
                    position,
                });
            }
            Set {
                amount,
                offset,
                position,
            } => {
                let new_offset = offset + current_offset;
                let same_offset_instrs = instrs_by_offset.entry(new_offset).or_default();
                same_offset_instrs.push(Set {
                    amount,
                    offset: new_offset,
                    position,
                });
            }
            PointerIncrement { amount, position } => {
                current_offset += amount;
                last_ptr_inc_pos = Some(position);
            }
            // We assume that we were only given a Vec of
            // Increment/Set/PointerIncrement instructions. It's
            // the job of this function to create instructions with
            // offset.
            _ => unreachable!(),
        }
    }

    // Append the increment/set instructions, in offset order.
    let mut results: Vec<AstNode> = vec![];
    for same_offset_instrs in ordered_values(instrs_by_offset) {
        results.extend(same_offset_instrs.into_iter());
    }

    // Add a single PointerIncrement at the end, reflecting the net
    // pointer movement in this instruction sequence.
    if current_offset != 0 {
        results.push(PointerIncrement {
            amount: current_offset,
            position: last_ptr_inc_pos.unwrap(),
        });
    }
    results
}

/// Combine set instructions with other set instructions or
/// increments.
fn combine_set_and_increments(instrs: Vec<AstNode>) -> Vec<AstNode> {
    // It's sufficient to consider immediately adjacent instructions
    // as sort_sequence_by_offset ensures that if the offset is the
    // same, the instruction is adjacent.
    instrs
        .into_iter()
        .coalesce(|prev_instr, instr| {
            // TODO: Set, Write, Increment -> Set, Write, Set
            // Inc x, Set y -> Set y
            if let (
                &Increment {
                    offset: inc_offset,
                    position: inc_pos,
                    ..
                },
                &Set {
                    amount: set_amount,
                    offset: set_offset,
                    position: set_pos,
                },
            ) = (&prev_instr, &instr)
            {
                if inc_offset == set_offset {
                    return Ok(Set {
                        amount: set_amount,
                        offset: set_offset,
                        // Whilst the Inc is dead here, by including
                        // it in the position tracking we can show better warnings.
                        position: set_pos.combine(inc_pos),
                    });
                }
            }
            Err((prev_instr, instr))
        })
        .coalesce(|prev_instr, instr| {
            // Set x, Inc y -> Set x+y
            if let Set {
                amount: set_amount,
                offset: set_offset,
                position: set_pos,
            } = prev_instr
            {
                if let Increment {
                    amount: inc_amount,
                    offset: inc_offset,
                    position: inc_pos,
                } = instr
                {
                    if inc_offset == set_offset {
                        return Ok(Set {
                            amount: set_amount + inc_amount,
                            offset: set_offset,
                            position: set_pos.combine(inc_pos),
                        });
                    }
                }
            }
            Err((prev_instr, instr))
        })
        .coalesce(|prev_instr, instr| {
            // Set x, Set y -> Set y
            if let (
                &Set {
                    offset: offset1,
                    position: position1,
                    ..
                },
                &Set {
                    amount,
                    offset: offset2,
                    position: position2,
                },
            ) = (&prev_instr, &instr)
            {
                if offset1 == offset2 {
                    return Ok(Set {
                        amount,
                        offset: offset1,
                        // Whilst the first Set is dead here, by including
                        // it in the position tracking we can show better warnings.
                        position: position1.combine(position2),
                    });
                }
            }
            Err((prev_instr, instr))
        })
        .map_loops(combine_set_and_increments)
}

fn remove_redundant_sets(instrs: Vec<AstNode>) -> Vec<AstNode> {
    let mut reduced = remove_redundant_sets_inner(instrs);

    // Remove a set zero at the beginning of the program, since cells
    // are initialised to zero anyway.
    if matches!(
        reduced.first(),
        Some(Set {
            amount: Wrapping(0),
            offset: 0,
            ..
        })
    ) {
        reduced.remove(0);
    }

    reduced
}

fn remove_redundant_sets_inner(instrs: Vec<AstNode>) -> Vec<AstNode> {
    let mut redundant_instr_positions = HashSet::new();

    for (index, instr) in instrs.iter().enumerate() {
        if matches!(instr, Loop { .. } | MultiplyMove { .. }) {
            // There's no point setting to zero after a loop, as
            // the cell is already zero.
            if let Some(next_index) = next_cell_change(&instrs, index) {
                if let Set {
                    amount: Wrapping(0),
                    offset: 0,
                    ..
                } = instrs[next_index]
                {
                    redundant_instr_positions.insert(next_index);
                }
            }
        }
    }

    instrs
        .into_iter()
        .enumerate()
        .filter(|&(index, _)| !redundant_instr_positions.contains(&index))
        .map(|(_, instr)| instr)
        .map_loops(remove_redundant_sets_inner)
}

fn annotate_known_zero(instrs: Vec<AstNode>) -> Vec<AstNode> {
    let mut result = vec![];

    let position = if instrs.is_empty() {
        None
    } else {
        get_position(&instrs[0]).map(|first_instr_pos| Position {
            start: first_instr_pos.start,
            end: first_instr_pos.start,
        })
    };

    // Cells in BF are initialised to zero, so we know the current
    // cell is zero at the start of execution.
    let set_instr = Set {
        amount: Wrapping(0),
        offset: 0,
        position,
    };
    // Insert the set instruction unless there is one already present.
    if instrs.first() != Some(&set_instr) {
        result.push(set_instr);
    }

    result.extend(annotate_known_zero_inner(&instrs));
    result
}

fn annotate_known_zero_inner(instrs: &[AstNode]) -> Vec<AstNode> {
    let mut result = Vec::with_capacity(instrs.len());

    for (i, instr) in instrs.iter().enumerate() {
        let instr = instr.clone();

        match instr {
            // After a loop, we know the cell is currently zero.
            Loop { body, position } => {
                result.push(Loop {
                    body: annotate_known_zero_inner(&body),
                    position,
                });
                // Treat this set as positioned at the ].
                let set_pos = position.map(|loop_pos| Position {
                    start: loop_pos.end,
                    end: loop_pos.end,
                });

                let set_instr = Set {
                    amount: Wrapping(0),
                    offset: 0,
                    position: set_pos,
                };
                if instrs.get(i + 1) != Some(&set_instr) {
                    result.push(set_instr.clone());
                }
            }
            _ => {
                result.push(instr);
            }
        }
    }

    result
}

/// Remove code at the end of the program that has no side
/// effects. This means we have no write commands afterwards, nor
/// loops (which may not terminate so we should not remove).
fn remove_pure_code(mut instrs: Vec<AstNode>) -> (Vec<AstNode>, Option<Warning>) {
    let mut pure_instrs = vec![];

    while let Some(last_instr) = instrs.pop() {
        match last_instr {
            Read { .. } | Write { .. } | Loop { .. } => {
                instrs.push(last_instr);
                break;
            }
            _ => {
                pure_instrs.push(last_instr);
            }
        }
    }

    let warning = if pure_instrs.is_empty() {
        None
    } else {
        let position = pure_instrs
            .into_iter()
            .map(|instr| get_position(&instr))
            .filter(|pos| pos.is_some())
            .reduce(|pos1, pos2| pos1.combine(pos2))
            .map(|pos| pos.unwrap());
        Some(Warning {
            message: "These instructions have no effect.".to_owned(),
            position,
        })
    };

    (instrs, warning)
}

/// Does this loop body represent a multiplication operation?
/// E.g. "[->>>++<<<]" sets cell #3 to 2*cell #0.
fn is_multiply_loop_body(body: &[AstNode]) -> bool {
    // A multiply loop may only contain increments and pointer increments.
    for body_instr in body {
        match *body_instr {
            Increment { .. } | PointerIncrement { .. } => {}
            _ => return false,
        }
    }

    // A multiply loop must have a net pointer movement of
    // zero.
    let mut net_movement = 0;
    for body_instr in body {
        if let PointerIncrement { amount, .. } = *body_instr {
            net_movement += amount;
        }
    }
    if net_movement != 0 {
        return false;
    }

    let changes = cell_changes(body);
    // A multiply loop must decrement cell #0.
    if let Some(&Wrapping(-1)) = changes.get(&0) {
    } else {
        return false;
    }

    changes.len() >= 2
}

/// Return a hashmap of all the cells that are affected by this
/// sequence of instructions, and how much they change.
/// E.g. "->>+++>+" -> {0: -1, 2: 3, 3: 1}
fn cell_changes(instrs: &[AstNode]) -> HashMap<isize, BfValue> {
    let mut changes = HashMap::new();
    let mut cell_index: isize = 0;

    for instr in instrs {
        match *instr {
            Increment { amount, offset, .. } => {
                let current_amount = *changes.get(&(cell_index + offset)).unwrap_or(&Wrapping(0));
                changes.insert(cell_index, current_amount + amount);
            }
            PointerIncrement { amount, .. } => {
                cell_index += amount;
            }
            // We assume this is only called from is_multiply_loop.
            _ => unreachable!(),
        }
    }

    changes
}

fn extract_multiply(instrs: Vec<AstNode>) -> Vec<AstNode> {
    instrs
        .into_iter()
        .map(|instr| {
            match instr {
                Loop { body, position } => {
                    if is_multiply_loop_body(&body) {
                        let mut changes = cell_changes(&body);
                        // MultiplyMove is for where we move to, so ignore
                        // the cell we're moving from.
                        changes.remove(&0);

                        MultiplyMove { changes, position }
                    } else {
                        Loop {
                            body: extract_multiply(body),
                            position,
                        }
                    }
                }
                i => i,
            }
        })
        .collect()
}

#[cfg(test)]
mod tests {
    use super::*;

    use std::collections::HashMap;
    use std::num::Wrapping;

    use pretty_assertions::assert_eq;
    use quickcheck::quickcheck;
    use quickcheck::{Arbitrary, Gen, TestResult};

    use crate::bfir::parse;
    use crate::bfir::{AstNode, Position};
    use crate::diagnostics::Warning;

    impl Arbitrary for AstNode {
        fn arbitrary<G: Gen>(g: &mut G) -> AstNode {
            arbitrary_instr(g, 5)
        }
    }

    // We define a separate function so we can recurse on max_depth.
    // See https://github.com/BurntSushi/quickcheck/issues/23
    fn arbitrary_instr<G: Gen>(g: &mut G, max_depth: usize) -> AstNode {
        let modulus = if max_depth == 0 { 8 } else { 9 };

        // If max_depth is zero, don't create loops.
        match g.next_u32() % modulus {
            // TODO: use arbitrary offsets.
            0 => Increment {
                amount: Wrapping(Arbitrary::arbitrary(g)),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            1 => PointerIncrement {
                amount: Arbitrary::arbitrary(g),
                position: Some(Position { start: 0, end: 0 }),
            },
            // TODO: use arbitrary offsets.
            2 => Set {
                amount: Wrapping(Arbitrary::arbitrary(g)),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            3 => Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            4 => Write {
                position: Some(Position { start: 0, end: 0 }),
            },
            5 => {
                let mut changes = HashMap::new();
                changes.insert(1, Wrapping(-1));
                MultiplyMove {
                    changes,
                    position: Some(Position { start: 0, end: 0 }),
                }
            }
            6 => {
                let mut changes = HashMap::new();
                changes.insert(1, Wrapping(2));
                changes.insert(4, Wrapping(10));
                MultiplyMove {
                    changes,
                    position: Some(Position { start: 0, end: 0 }),
                }
            }
            7 => {
                // A multiply by 2 loop that accesses a previous
                // cell. Quickcheck doesn't seem to generate these by
                // chance, but they often expose interesting bugs.
                let body = vec![
                    Increment {
                        amount: Wrapping(-1),
                        offset: 0,
                        position: None,
                    },
                    PointerIncrement {
                        amount: -1,
                        position: None,
                    },
                    Increment {
                        amount: Wrapping(2),
                        offset: 0,
                        position: None,
                    },
                    PointerIncrement {
                        amount: 1,
                        position: None,
                    },
                ];
                Loop {
                    body,
                    position: None,
                }
            }
            8 => {
                assert!(max_depth > 0);
                let loop_length = g.next_u32() % 10;
                let mut body: Vec<_> = vec![];
                for _ in 0..loop_length {
                    body.push(arbitrary_instr(g, max_depth - 1));
                }
                Loop {
                    body,
                    position: Some(Position { start: 0, end: 0 }),
                }
            }
            _ => unreachable!(),
        }
    }

    #[test]
    fn combine_increments_flat() {
        let initial = parse("++").unwrap();
        let expected = vec![Increment {
            amount: Wrapping(2),
            offset: 0,
            position: Some(Position { start: 0, end: 1 }),
        }];
        assert_eq!(combine_increments(initial), expected);
    }

    #[test]
    fn combine_increments_unrelated() {
        let initial = parse("+>+.").unwrap();
        let expected = initial.clone();
        assert_eq!(combine_increments(initial), expected);
    }

    #[test]
    fn combine_increments_nested() {
        let initial = parse("[++]").unwrap();
        let expected = vec![Loop {
            body: vec![Increment {
                amount: Wrapping(2),
                offset: 0,
                position: Some(Position { start: 1, end: 2 }),
            }],
            position: Some(Position { start: 0, end: 3 }),
        }];
        assert_eq!(combine_increments(initial), expected);
    }

    #[test]
    fn combine_increments_remove_redundant() {
        let initial = parse("+-").unwrap();
        assert_eq!(combine_increments(initial), vec![]);
    }

    #[test]
    fn quickcheck_combine_increments_remove_zero_any_offset() {
        fn combine_increments_remove_zero_any_offset(offset: isize) -> bool {
            let initial = vec![Increment {
                amount: Wrapping(0),
                offset,
                position: Some(Position { start: 0, end: 0 }),
            }];
            combine_increments(initial) == vec![]
        }
        quickcheck(combine_increments_remove_zero_any_offset as fn(isize) -> bool);
    }

    #[test]
    fn combine_increment_sum_to_zero() {
        let initial = vec![
            Increment {
                amount: Wrapping(-1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(combine_increments(initial), vec![]);
    }

    #[test]
    fn should_combine_ptr_increments() {
        let initial = parse(">>").unwrap();
        let expected = vec![PointerIncrement {
            amount: 2,
            position: Some(Position { start: 0, end: 1 }),
        }];
        assert_eq!(combine_ptr_increments(initial), expected);
    }

    #[test]
    fn combine_set_sum_to_zero() {
        let initial = vec![
            Set {
                amount: Wrapping(-1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(
            combine_set_and_increments(initial),
            vec![Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            }]
        );
    }

    #[test]
    fn should_combine_before_read() {
        // The increment before the read is dead and can be removed.
        let initial = parse("+,.").unwrap();
        let expected = vec![
            Read {
                position: Some(Position { start: 1, end: 1 }),
            },
            Write {
                position: Some(Position { start: 2, end: 2 }),
            },
        ];
        assert_eq!(optimize(initial, &None).0, expected);
    }

    #[test]
    fn dont_combine_before_read_different_offset() {
        // The read does not affect the increment here.
        let initial = vec![
            Increment {
                amount: Wrapping(1),
                offset: 2,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(remove_read_clobber(initial.clone()), initial);
    }

    #[test]
    fn should_combine_before_read_nested() {
        // The read clobbers the increment here.
        let initial = parse("+[+,]").unwrap();
        let expected = vec![
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![Read {
                    position: Some(Position { start: 3, end: 3 }),
                }],
                position: Some(Position { start: 1, end: 4 }),
            },
        ];
        assert_eq!(optimize(initial, &None).0, expected);
    }

    #[test]
    fn combine_before_read_not_consecutive() {
        // The increment before the read is dead and can be removed.
        let initial = parse("+>-<,").unwrap();
        let expected = vec![
            PointerIncrement {
                amount: 1,
                position: Some(Position { start: 1, end: 1 }),
            },
            Increment {
                amount: Wrapping(-1),
                offset: 0,
                position: Some(Position { start: 2, end: 2 }),
            },
            PointerIncrement {
                amount: -1,
                position: Some(Position { start: 3, end: 3 }),
            },
            Read {
                position: Some(Position { start: 4, end: 4 }),
            },
        ];
        assert_eq!(remove_read_clobber(initial), expected);
    }

    #[test]
    fn no_combine_before_read_after_write() {
        let initial = vec![
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: None,
            },
            Write { position: None },
            Read { position: None },
        ];
        // TODO: write an assert_unchanged! macro.
        let expected = initial.clone();
        assert_eq!(remove_read_clobber(initial), expected);
    }

    #[test]
    fn no_combine_before_read_after_multiply() {
        let mut changes = HashMap::new();
        changes.insert(1, Wrapping(-1));
        let initial = vec![
            MultiplyMove {
                changes,
                position: None,
            },
            Read { position: None },
        ];
        let expected = initial.clone();
        assert_eq!(remove_read_clobber(initial), expected);
    }

    #[test]
    fn simplify_zeroing_loop() {
        let initial = parse("[-]").unwrap();
        let expected = vec![Set {
            amount: Wrapping(0),
            offset: 0,
            position: Some(Position { start: 0, end: 2 }),
        }];
        assert_eq!(zeroing_loops(initial), expected);
    }

    #[test]
    fn simplify_nested_zeroing_loop() {
        let initial = parse("[[-]]").unwrap();
        let expected = vec![Loop {
            body: vec![Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 1, end: 3 }),
            }],
            position: Some(Position { start: 0, end: 4 }),
        }];
        assert_eq!(zeroing_loops(initial), expected);
    }

    #[test]
    fn dont_simplify_multiple_decrement_loop() {
        // A user who wrote this probably meant '[-]'. However, if the
        // current cell has the value 3, we would actually wrap around
        // (although BF does not specify this).
        let initial = parse("[--]").unwrap();
        assert_eq!(zeroing_loops(initial.clone()), initial);
    }

    #[test]
    fn remove_repeated_loops() {
        let initial = vec![
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        let expected = vec![
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(optimize(initial, &None).0, expected);
    }

    #[test]
    fn remove_dead_loops_after_set() {
        let initial = vec![
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        let expected = vec![Set {
            amount: Wrapping(0),
            offset: 0,
            position: Some(Position { start: 0, end: 0 }),
        }];
        assert_eq!(remove_dead_loops(initial), expected);
    }

    #[test]
    fn remove_dead_loops_nested() {
        let initial = vec![Loop {
            body: vec![
                Set {
                    amount: Wrapping(0),
                    offset: 0,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Loop {
                    body: vec![],
                    position: Some(Position { start: 0, end: 0 }),
                },
            ],
            position: Some(Position { start: 0, end: 0 }),
        }];
        let expected = vec![Loop {
            body: vec![Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            }],
            position: Some(Position { start: 0, end: 0 }),
        }];
        assert_eq!(remove_dead_loops(initial), expected);
    }

    #[test]
    fn remove_dead_loops_not_adjacent() {
        let initial = vec![
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Set {
                amount: Wrapping(1),
                offset: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        let expected = vec![
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Set {
                amount: Wrapping(1),
                offset: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(remove_dead_loops(initial), expected);
    }

    #[test]
    fn quickcheck_should_combine_set_and_increment() {
        fn should_combine_set_and_increment(
            offset: isize,
            set_amount: i8,
            increment_amount: i8,
        ) -> bool {
            let set_amount = Wrapping(set_amount);
            let increment_amount = Wrapping(increment_amount);

            let initial = vec![
                Set {
                    amount: set_amount,
                    offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Increment {
                    amount: increment_amount,
                    offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            let expected = vec![Set {
                amount: set_amount + increment_amount,
                offset,
                position: Some(Position { start: 0, end: 0 }),
            }];
            combine_set_and_increments(initial) == expected
        }
        quickcheck(should_combine_set_and_increment as fn(isize, i8, i8) -> bool);
    }

    // TODO: rename our quickcheck property functions to something shorter.
    #[test]
    fn quickcheck_combine_set_and_increment_different_offsets() {
        fn combine_set_and_increment_different_offsets(
            set_offset: isize,
            set_amount: i8,
            inc_offset: isize,
            inc_amount: i8,
        ) -> TestResult {
            if set_offset == inc_offset {
                return TestResult::discard();
            }

            let initial = vec![
                Set {
                    amount: Wrapping(set_amount),
                    offset: set_offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Increment {
                    amount: Wrapping(inc_amount),
                    offset: inc_offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            let expected = initial.clone();

            TestResult::from_bool(combine_set_and_increments(initial) == expected)
        }
        quickcheck(
            combine_set_and_increment_different_offsets as fn(isize, i8, isize, i8) -> TestResult,
        );
    }

    #[test]
    fn quickcheck_combine_increment_and_set_different_offsets() {
        fn combine_increment_and_set_different_offsets(
            set_offset: isize,
            set_amount: i8,
            inc_offset: isize,
            inc_amount: i8,
        ) -> TestResult {
            if set_offset == inc_offset {
                return TestResult::discard();
            }

            let initial = vec![
                Increment {
                    amount: Wrapping(inc_amount),
                    offset: inc_offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Set {
                    amount: Wrapping(set_amount),
                    offset: set_offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            let expected = initial.clone();

            TestResult::from_bool(combine_set_and_increments(initial) == expected)
        }
        quickcheck(
            combine_increment_and_set_different_offsets as fn(isize, i8, isize, i8) -> TestResult,
        );
    }

    #[test]
    fn quickcheck_combine_set_and_set() {
        fn combine_set_and_set(offset: isize, set_amount_before: i8, set_amount_after: i8) -> bool {
            let initial = vec![
                Set {
                    amount: Wrapping(set_amount_before),
                    offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Set {
                    amount: Wrapping(set_amount_after),
                    offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            let expected = vec![Set {
                amount: Wrapping(set_amount_after),
                offset,
                position: Some(Position { start: 0, end: 0 }),
            }];
            combine_set_and_increments(initial) == expected
        }
        quickcheck(combine_set_and_set as fn(isize, i8, i8) -> bool);
    }

    #[test]
    fn quickcheck_combine_set_and_set_different_offsets() {
        fn combine_set_and_set_different_offsets(
            offset1: isize,
            amount1: i8,
            offset2: isize,
            amount2: i8,
        ) -> TestResult {
            if offset1 == offset2 {
                return TestResult::discard();
            }

            let initial = vec![
                Set {
                    amount: Wrapping(amount1),
                    offset: offset1,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Set {
                    amount: Wrapping(amount2),
                    offset: offset2,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            let expected = initial.clone();

            TestResult::from_bool(combine_set_and_increments(initial) == expected)
        }
        quickcheck(combine_set_and_set_different_offsets as fn(isize, i8, isize, i8) -> TestResult);
    }

    #[test]
    fn should_combine_set_and_set_nested() {
        let initial = vec![Loop {
            body: vec![
                Set {
                    amount: Wrapping(0),
                    offset: 0,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Set {
                    amount: Wrapping(1),
                    offset: 0,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ],
            position: Some(Position { start: 0, end: 0 }),
        }];
        let expected = vec![Loop {
            body: vec![Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            }],
            position: Some(Position { start: 0, end: 0 }),
        }];
        assert_eq!(combine_set_and_increments(initial), expected);
    }

    #[test]
    fn quickcheck_should_combine_increment_and_set() {
        fn should_combine_increment_and_set(offset: isize) -> bool {
            let initial = vec![
                Increment {
                    amount: Wrapping(2),
                    offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Set {
                    amount: Wrapping(3),
                    offset,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            let expected = vec![Set {
                amount: Wrapping(3),
                offset,
                position: Some(Position { start: 0, end: 0 }),
            }];
            combine_set_and_increments(initial) == expected
        }
        quickcheck(should_combine_increment_and_set as fn(isize) -> bool);
    }

    #[test]
    fn should_remove_redundant_set() {
        let initial = vec![
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
            Set {
                amount: Wrapping(0),
                offset: -1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        let expected = vec![
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
            Set {
                amount: Wrapping(0),
                offset: -1,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(remove_redundant_sets(initial), expected);
    }

    #[test]
    fn should_remove_redundant_set_multiply() {
        let mut changes = HashMap::new();
        changes.insert(1, Wrapping(1));

        let initial = vec![
            MultiplyMove {
                changes: changes.clone(),
                position: Some(Position { start: 0, end: 0 }),
            },
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        let expected = vec![MultiplyMove {
            changes,
            position: Some(Position { start: 0, end: 0 }),
        }];
        assert_eq!(remove_redundant_sets(initial), expected);
    }

    /// After a loop, if we set to a value other than zero, we shouldn't
    /// remove it.
    #[test]
    fn not_redundant_set_when_nonzero() {
        let instrs = vec![
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(remove_redundant_sets(instrs.clone()), instrs);
    }

    fn is_pure(instrs: &[AstNode]) -> bool {
        for instr in instrs {
            match *instr {
                Loop { .. } => {
                    return false;
                }
                Read { .. } => {
                    return false;
                }
                Write { .. } => {
                    return false;
                }
                _ => (),
            }
        }
        true
    }

    #[test]
    fn quickcheck_should_annotate_known_zero_at_start() {
        fn should_annotate_known_zero_at_start(instrs: Vec<AstNode>) -> bool {
            let annotated = annotate_known_zero(instrs);
            matches!(
                annotated[0],
                Set {
                    amount: Wrapping(0),
                    offset: 0,
                    ..
                }
            )
        }
        quickcheck(should_annotate_known_zero_at_start as fn(Vec<AstNode>) -> bool);
    }

    #[test]
    fn annotate_known_zero_idempotent() {
        fn is_idempotent(instrs: Vec<AstNode>) -> bool {
            let annotated = annotate_known_zero(instrs);
            let annotated_again = annotate_known_zero(annotated.clone());
            if annotated == annotated_again {
                true
            } else {
                println!("intermediate: {:?}", annotated);
                println!("final: {:?}", annotated_again);
                false
            }
        }
        quickcheck(is_idempotent as fn(Vec<AstNode>) -> bool);
    }

    #[test]
    fn should_annotate_known_zero() {
        let initial = parse("+[]").unwrap();
        let expected = vec![
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![],
                position: Some(Position { start: 1, end: 2 }),
            },
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 2, end: 2 }),
            },
        ];
        assert_eq!(annotate_known_zero(initial), expected);
    }

    #[test]
    fn should_annotate_known_zero_nested() {
        let initial = parse("[[]]").unwrap();
        let expected = vec![
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![
                    Loop {
                        body: vec![],
                        position: Some(Position { start: 1, end: 2 }),
                    },
                    Set {
                        amount: Wrapping(0),
                        offset: 0,
                        position: Some(Position { start: 2, end: 2 }),
                    },
                ],
                position: Some(Position { start: 0, end: 3 }),
            },
            Set {
                amount: Wrapping(0),
                offset: 0,
                position: Some(Position { start: 3, end: 3 }),
            },
        ];
        assert_eq!(annotate_known_zero(initial), expected);
    }

    /// When we annotate known zeroes, we have new opportunities for
    /// combining instructions and loop removal. However, we should later
    /// remove the Set 0 if we haven't combined it.
    #[test]
    fn should_annotate_known_zero_cleaned_up() {
        let initial = vec![Write {
            position: Some(Position { start: 0, end: 0 }),
        }];
        assert_eq!(optimize(initial.clone(), &None).0, initial);
    }

    #[test]
    fn should_preserve_set_0_in_loop() {
        // Regression test.
        let initial = vec![
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![Set {
                    amount: Wrapping(0),
                    offset: 0,
                    position: Some(Position { start: 0, end: 0 }),
                }],
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(optimize(initial.clone(), &None).0, initial);
    }

    #[test]
    fn should_remove_pure_code() {
        // The final increment here is side-effect free and can be
        // removed.
        let initial = parse("+.+").unwrap();
        let expected = vec![
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Write {
                position: Some(Position { start: 1, end: 1 }),
            },
        ];

        let (result, warnings) = optimize(initial, &None);

        assert_eq!(result, expected);
        assert_eq!(
            warnings,
            vec![Warning {
                message: "These instructions have no effect.".to_owned(),
                position: Some(Position { start: 2, end: 2 }),
            }]
        );
    }

    #[test]
    fn quickcheck_should_remove_dead_pure_code() {
        fn should_remove_dead_pure_code(instrs: Vec<AstNode>) -> TestResult {
            if !is_pure(&instrs) {
                return TestResult::discard();
            }
            TestResult::from_bool(optimize(instrs, &None).0 == vec![])
        }
        quickcheck(should_remove_dead_pure_code as fn(Vec<AstNode>) -> TestResult);
    }

    #[test]
    fn quickcheck_optimize_should_be_idempotent() {
        fn optimize_should_be_idempotent(instrs: Vec<AstNode>) -> bool {
            // Once we've optimized once, running again shouldn't reduce the
            // instructions further. If it does, we're probably running our
            // optimisations in the wrong order.
            let minimal = optimize(instrs, &None).0;
            optimize(minimal.clone(), &None).0 == minimal
        }
        quickcheck(optimize_should_be_idempotent as fn(Vec<AstNode>) -> bool);
    }

    #[test]
    fn pathological_optimisation_opportunity() {
        let instrs = vec![
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: -1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(-1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: -1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(-1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Write {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];

        let expected = vec![
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            Write {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];

        assert_eq!(optimize(instrs, &None).0, expected);
    }

    fn count_instrs(instrs: &[AstNode]) -> u64 {
        let mut count = 0;
        for instr in instrs {
            if let Loop { ref body, .. } = *instr {
                count += count_instrs(body);
            }
            count += 1;
        }
        count
    }

    #[test]
    fn quickcheck_optimize_should_decrease_size() {
        fn optimize_should_decrease_size(instrs: Vec<AstNode>) -> bool {
            // The result of optimize() should never increase the number of
            // instructions.
            let result = optimize(instrs.clone(), &None).0;
            count_instrs(&result) <= count_instrs(&instrs)
        }
        quickcheck(optimize_should_decrease_size as fn(Vec<AstNode>) -> bool);
    }

    #[test]
    fn should_extract_multiply_simple() {
        let instrs = parse("[->+++<]").unwrap();

        let mut dest_cells = HashMap::new();
        dest_cells.insert(1, Wrapping(3));
        let expected = vec![MultiplyMove {
            changes: dest_cells,
            position: Some(Position { start: 0, end: 7 }),
        }];

        assert_eq!(extract_multiply(instrs), expected);
    }

    #[test]
    fn should_extract_multiply_nested() {
        let instrs = parse("[[->+<]]").unwrap();

        let mut dest_cells = HashMap::new();
        dest_cells.insert(1, Wrapping(1));
        let expected = vec![Loop {
            body: vec![MultiplyMove {
                changes: dest_cells,
                position: Some(Position { start: 1, end: 6 }),
            }],
            position: Some(Position { start: 0, end: 7 }),
        }];

        assert_eq!(extract_multiply(instrs), expected);
    }

    #[test]
    fn should_extract_multiply_negative_number() {
        let instrs = parse("[->--<]").unwrap();

        let mut dest_cells = HashMap::new();
        dest_cells.insert(1, Wrapping(-2));
        let expected = vec![MultiplyMove {
            changes: dest_cells,
            position: Some(Position { start: 0, end: 6 }),
        }];

        assert_eq!(extract_multiply(instrs), expected);
    }

    #[test]
    fn should_extract_multiply_multiple_cells() {
        let instrs = parse("[->+++>>>+<<<<]").unwrap();

        let mut dest_cells = HashMap::new();
        dest_cells.insert(1, Wrapping(3));
        dest_cells.insert(4, Wrapping(1));
        let expected = vec![MultiplyMove {
            changes: dest_cells,
            position: Some(Position { start: 0, end: 14 }),
        }];

        assert_eq!(extract_multiply(instrs), expected);
    }

    #[test]
    fn should_not_extract_multiply_net_movement() {
        let instrs = parse("[->+++<<]").unwrap();
        assert_eq!(extract_multiply(instrs.clone()), instrs);
    }

    #[test]
    fn should_not_extract_multiply_from_clear_loop() {
        let instrs = parse("[-]").unwrap();
        assert_eq!(extract_multiply(instrs.clone()), instrs);
    }

    #[test]
    fn should_not_extract_multiply_with_inner_loop() {
        let instrs = parse("[->+++<[]]").unwrap();
        assert_eq!(extract_multiply(instrs.clone()), instrs);
    }

    /// We need to decrement the initial cell in order for this to be a
    /// multiply.
    #[test]
    fn should_not_extract_multiply_without_decrement() {
        let instrs = parse("[+>++<]").unwrap();
        assert_eq!(extract_multiply(instrs.clone()), instrs);
    }

    #[test]
    fn should_not_extract_multiply_with_read() {
        let instrs = parse("[+>++<,]").unwrap();
        assert_eq!(extract_multiply(instrs.clone()), instrs);
    }

    #[test]
    fn should_not_extract_multiply_with_write() {
        let instrs = parse("[+>++<.]").unwrap();
        assert_eq!(extract_multiply(instrs.clone()), instrs);
    }

    #[test]
    fn sort_by_offset_increment() {
        let instrs = parse("+>+>").unwrap();
        let expected = vec![
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 1,
                position: Some(Position { start: 2, end: 2 }),
            },
            PointerIncrement {
                amount: 2,
                position: Some(Position { start: 3, end: 3 }),
            },
        ];
        assert_eq!(sort_by_offset(instrs), expected);
    }

    #[test]
    fn sort_by_offset_increment_nested() {
        let instrs = parse("[+>+>]").unwrap();
        let expected = vec![Loop {
            body: (vec![
                Increment {
                    amount: Wrapping(1),
                    offset: 0,
                    position: Some(Position { start: 1, end: 1 }),
                },
                Increment {
                    amount: Wrapping(1),
                    offset: 1,
                    position: Some(Position { start: 3, end: 3 }),
                },
                PointerIncrement {
                    amount: 2,
                    position: Some(Position { start: 4, end: 4 }),
                },
            ]),
            position: Some(Position { start: 0, end: 5 }),
        }];
        assert_eq!(sort_by_offset(instrs), expected);
    }

    #[test]
    fn sort_by_offset_remove_redundant() {
        let initial = parse("><").unwrap();
        assert_eq!(sort_by_offset(initial), vec![]);
    }

    // If there's a read instruction, we should only combine before and
    // after.
    #[test]
    fn sort_by_offset_read() {
        let instrs = parse(">>,>>").unwrap();
        let expected = vec![
            PointerIncrement {
                amount: 2,
                position: Some(Position { start: 1, end: 1 }),
            },
            Read {
                position: Some(Position { start: 2, end: 2 }),
            },
            PointerIncrement {
                amount: 2,
                position: Some(Position { start: 4, end: 4 }),
            },
        ];
        assert_eq!(sort_by_offset(instrs), expected);
    }

    #[test]
    fn quickcheck_sort_by_offset_set() {
        fn sort_by_offset_set(amount1: i8, amount2: i8) -> bool {
            let instrs = vec![
                Set {
                    amount: Wrapping(amount1),
                    offset: 0,
                    position: Some(Position { start: 0, end: 0 }),
                },
                PointerIncrement {
                    amount: -1,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Set {
                    amount: Wrapping(amount2),
                    offset: 0,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];

            let expected = vec![
                Set {
                    amount: Wrapping(amount2),
                    offset: -1,
                    position: Some(Position { start: 0, end: 0 }),
                },
                Set {
                    amount: Wrapping(amount1),
                    offset: 0,
                    position: Some(Position { start: 0, end: 0 }),
                },
                PointerIncrement {
                    amount: -1,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            sort_by_offset(instrs) == expected
        }
        quickcheck(sort_by_offset_set as fn(i8, i8) -> bool);
    }

    #[test]
    fn quickcheck_sort_by_offset_pointer_increments() {
        fn sort_by_offset_pointer_increments(amount1: isize, amount2: isize) -> TestResult {
            // Although in principle our optimisations would work outside
            // MAX_CELL_INDEX, we restrict the range to avoid overflow.
            if amount1 < -30000 || amount1 > 30000 || amount2 < -30000 || amount2 > 30000 {
                return TestResult::discard();
            }
            // We should discard the pointer increment if the two cancel out,
            // but we don't test that here.
            if amount1 + amount2 == 0 {
                return TestResult::discard();
            }

            let instrs = vec![
                PointerIncrement {
                    amount: amount1,
                    position: Some(Position { start: 0, end: 0 }),
                },
                PointerIncrement {
                    amount: amount2,
                    position: Some(Position { start: 0, end: 0 }),
                },
            ];
            let expected = vec![PointerIncrement {
                amount: amount1 + amount2,
                position: Some(Position { start: 0, end: 0 }),
            }];
            TestResult::from_bool(sort_by_offset(instrs) == expected)
        }
        quickcheck(sort_by_offset_pointer_increments as fn(isize, isize) -> TestResult);
    }

    // Don't combine instruction positions when they weren't originally
    // adjacent.
    #[test]
    fn combine_increments_non_adjacent_instrs() {
        let instrs = vec![
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 2, end: 2 }),
            },
        ];
        let expected = vec![Increment {
            amount: Wrapping(2),
            offset: 0,
            position: Some(Position { start: 2, end: 2 }),
        }];
        assert_eq!(combine_increments(instrs), expected);
    }

    // Don't combine instruction positions when they weren't originally
    // adjacent.
    #[test]
    fn combine_set_and_increment_non_adjacent_instrs() {
        let instrs = vec![
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 2, end: 2 }),
            },
        ];
        let expected = vec![Set {
            amount: Wrapping(2),
            offset: 0,
            position: Some(Position { start: 2, end: 2 }),
        }];
        assert_eq!(combine_set_and_increments(instrs), expected);
    }

    /// Ensure that we combine after sorting, since sorting creates new
    /// combination opportunities.
    #[test]
    fn combine_increments_after_sort() {
        let instrs = parse(",+>+<+.").unwrap();
        let expected = vec![
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(2),
                offset: 0,
                position: Some(Position { start: 5, end: 5 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 1,
                position: Some(Position { start: 3, end: 3 }),
            },
            Write {
                position: Some(Position { start: 6, end: 6 }),
            },
        ];
        assert_eq!(optimize(instrs, &None).0, expected);
    }

    #[test]
    fn prev_mutate_loop() {
        // If we see a loop, we don't know when the current cell was last
        // mutated.
        let instrs = vec![
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 1), None);
    }

    #[test]
    fn prev_mutate_increment() {
        let instrs = vec![
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 1), Some(0));
    }

    #[test]
    fn prev_mutate_ignores_offset_at_index() {
        let instrs = vec![
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            // The fact that this instruction is at offset 1 should be irrelevant.
            Increment {
                amount: Wrapping(2),
                offset: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 1), Some(0));
    }

    #[test]
    fn prev_mutate_multiply_offset_matches() {
        let mut changes = HashMap::new();
        changes.insert(-1, Wrapping(-1));

        let instrs = vec![
            MultiplyMove {
                changes,
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: -1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 2), Some(0));
    }

    #[test]
    fn prev_mutate_multiply_offset_doesnt_match() {
        let mut changes = HashMap::new();
        changes.insert(1, Wrapping(2));

        let instrs = vec![
            MultiplyMove {
                changes,
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: 2,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 2), None);
    }

    /// MultiplyMove zeroes the current cell, so it counts as a mutation
    /// of the current value.
    #[test]
    fn prev_mutate_multiply_ignore_offset() {
        let mut changes = HashMap::new();
        changes.insert(1, Wrapping(-1));

        let instrs = vec![
            MultiplyMove {
                changes,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 1), Some(0));
    }

    #[test]
    fn prev_mutate_no_predecessors() {
        let instrs = vec![Read {
            position: Some(Position { start: 0, end: 0 }),
        }];
        assert_eq!(previous_cell_change(&instrs, 0), None);
    }

    #[test]
    fn prev_mutate_increment_matching_offset() {
        let instrs = vec![
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(10),
                offset: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 2), Some(0));
    }

    #[test]
    fn prev_mutate_ignore_write() {
        let instrs = vec![
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Write {
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 2), Some(0));
    }

    #[test]
    fn prev_mutate_consider_pointer_increment() {
        let instrs = vec![
            Increment {
                amount: Wrapping(1),
                offset: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 2), Some(0));
    }

    #[test]
    fn prev_mutate_set() {
        let instrs = vec![
            Set {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(previous_cell_change(&instrs, 1), Some(0));
    }

    #[test]
    fn next_mutate_loop() {
        // If we see a loop, we don't know when the current cell is next
        // mutated.
        let instrs = vec![
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            Loop {
                body: vec![],
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(next_cell_change(&instrs, 0), None);
    }

    #[test]
    fn next_mutate_increment() {
        let instrs = vec![
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: -1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 0,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];
        assert_eq!(next_cell_change(&instrs, 0), Some(2));
    }

    #[test]
    fn next_mutate_consider_pointer_increment() {
        let instrs = vec![
            Read {
                position: Some(Position { start: 0, end: 0 }),
            },
            PointerIncrement {
                amount: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: 1,
                position: Some(Position { start: 0, end: 0 }),
            },
            Increment {
                amount: Wrapping(1),
                offset: -1,
                position: Some(Position { start: 0, end: 0 }),
            },
        ];

        assert_eq!(next_cell_change(&instrs, 0), Some(3));
    }
}

#[cfg(test)]
mod soundness_tests {
    use super::*;

    use quickcheck::{quickcheck, TestResult};

    use crate::bfir::AstNode;
    use crate::execution::Outcome::*;
    use crate::execution::{execute_with_state, ExecutionState};

    fn transform_is_sound<F>(
        instrs: Vec<AstNode>,
        transform: F,
        check_cells: bool,
        dummy_read_value: Option<i8>,
    ) -> TestResult
    where
        F: Fn(Vec<AstNode>) -> Vec<AstNode>,
    {
        let max_steps = 1000;

        // First, we execute the program given.
        let mut state = ExecutionState::initial(&instrs[..]);
        let result = execute_with_state(&instrs[..], &mut state, max_steps, dummy_read_value);

        // Optimisations may change malformed programs to well-formed
        // programs, so we ignore programs that don't terminate nicely.
        match result {
            RuntimeError(_) | OutOfSteps => return TestResult::discard(),
            _ => (),
        }

        // Next, we execute the program after transformation.
        let optimised_instrs = transform(instrs.clone());
        // Deliberately start our state from the original instrs, so we
        // get the same number of cells. Otherwise we could get in messy
        // situations where a dead loop that makes us think we use
        // MAX_CELLS so state2 has fewer cells.
        let mut state2 = ExecutionState::initial(&instrs[..]);
        let result2 = execute_with_state(
            &optimised_instrs[..],
            &mut state2,
            max_steps,
            dummy_read_value,
        );

        // Compare the outcomes: they should be the same.
        match (result, result2) {
            // If the first result completed, the second should have
            // completed too. We allow them to take a different amount of
            // steps.
            (Completed(_), Completed(_)) => (),
            (ReachedRuntimeValue, ReachedRuntimeValue) => (),
            // Any other situation means that the first program terminated
            // but the optimised program did not.
            (_, _) => {
                println!("Optimised program did not terminate properly!");
                return TestResult::failed();
            }
        }

        // Likewise we should have written the same outputs.
        if state.outputs != state2.outputs {
            println!(
                "Different outputs! Original outputs: {:?} Optimised: {:?}",
                state.outputs, state2.outputs
            );
            return TestResult::failed();
        }

        // If requested, compare that the cells at the end are the same
        // too. This is true of most, but not all, of our optimisations.
        if check_cells && state.cells != state2.cells {
            println!(
                "Different cell states! Optimised state: {:?} Optimised: {:?}",
                state.cells, state2.cells
            );
            return TestResult::failed();
        }

        TestResult::passed()
    }

    #[test]
    fn combine_increments_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, combine_increments, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    fn discard_positions(instrs: Vec<AstNode>) -> Vec<AstNode> {
        instrs
            .into_iter()
            .map(|instr| match instr {
                Increment { amount, offset, .. } => Increment {
                    amount,
                    offset,
                    position: None,
                },
                PointerIncrement { amount, .. } => PointerIncrement {
                    amount,
                    position: None,
                },
                Read { .. } => Read { position: None },
                Write { .. } => Write { position: None },
                Loop { body, .. } => Loop {
                    body,
                    position: None,
                },
                Set { amount, offset, .. } => Set {
                    amount,
                    offset,
                    position: None,
                },
                MultiplyMove { changes, .. } => MultiplyMove {
                    changes,
                    position: None,
                },
            })
            .map_loops(discard_positions)
    }

    /// Optimisations should not be affected by the presence or
    /// absence of position data.
    #[test]
    fn discard_positions_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, discard_positions, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn combine_ptr_increments_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, combine_ptr_increments, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn annotate_known_zero_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, annotate_known_zero, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn extract_multiply_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, extract_multiply, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn simplify_loops_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, zeroing_loops, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn combine_set_and_increments_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, combine_set_and_increments, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn remove_dead_loops_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, remove_dead_loops, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn remove_redundant_sets_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, remove_redundant_sets, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn combine_before_read_is_sound() {
        fn is_sound(instrs: Vec<AstNode>, read_value: Option<i8>) -> TestResult {
            // remove_read_clobber can change the value of cells when we
            // reach a runtime value. Consider `+,` to `,` -- the `,`
            // overwrites the cell, but when we reach the runtime value
            // the cells are different.
            transform_is_sound(instrs, remove_read_clobber, false, read_value)
        }
        quickcheck(is_sound as fn(Vec<AstNode>, Option<i8>) -> TestResult)
    }

    #[test]
    fn remove_pure_code_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            // We can't compare cells after this pass. Consider `.+` to
            // `.` -- the outputs are the same, but the cell state is
            // different at termination.
            transform_is_sound(instrs, |instrs| remove_pure_code(instrs).0, false, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn sort_by_offset_is_sound() {
        fn is_sound(instrs: Vec<AstNode>) -> TestResult {
            transform_is_sound(instrs, sort_by_offset, true, None)
        }
        quickcheck(is_sound as fn(Vec<AstNode>) -> TestResult)
    }

    #[test]
    fn test_overall_optimize_is_sound() {
        fn optimize_ignore_warnings(instrs: Vec<AstNode>) -> Vec<AstNode> {
            optimize(instrs, &None).0
        }

        fn optimizations_sound_together(
            instrs: Vec<AstNode>,
            read_value: Option<i8>,
        ) -> TestResult {
            // Since sort_by_offset and remove_read_clobber can change
            // cell values at termination, the overall optimize can change
            // cells values at termination.
            transform_is_sound(instrs, optimize_ignore_warnings, false, read_value)
        }

        quickcheck(optimizations_sound_together as fn(Vec<AstNode>, Option<i8>) -> TestResult);
    }
}