third_party/rust/lalrpop/src/generate.rs
author Bastien Orivel <eijebong@bananium.fr>
Sat, 12 Jan 2019 03:19:31 +0200
changeset 453619 3c4b8e03e7221c6edc8651a13cd84cc344ce9b76
parent 412088 a97cccaa866a0fbd5721842ad8d8e862cd26ea65
child 453620 def9811f03111c1fe26bb578255cc30e56a87414
permissions -rw-r--r--
Bug 1516337 - Part 2: Revendor rust dependencies r=froydnj

//! Generate valid parse trees.

use grammar::repr::*;
use rand::{self, Rng};
use std::iter::Iterator;

#[derive(PartialEq, Eq)]
pub enum ParseTree {
    Nonterminal(NonterminalString, Vec<ParseTree>),
    Terminal(TerminalString),
}

pub fn random_parse_tree(grammar: &Grammar, symbol: NonterminalString) -> ParseTree {
    let mut gen = Generator {
        grammar: grammar,
        rng: rand::thread_rng(),
        depth: 0,
    };
    loop {
        // sometimes, the random walk overflows the stack, so we have a max, and if
        // it is exceeded, we just try again
        if let Some(result) = gen.nonterminal(symbol.clone()) {
            return result;
        }
        gen.depth = 0;
    }
}

struct Generator<'grammar> {
    grammar: &'grammar Grammar,
    rng: rand::ThreadRng,
    depth: u32,
}

const MAX_DEPTH: u32 = 10000;

impl<'grammar> Generator<'grammar> {
    fn nonterminal(&mut self, nt: NonterminalString) -> Option<ParseTree> {
        if self.depth > MAX_DEPTH {
            return None;
        }

        self.depth += 1;
        let productions = self.grammar.productions_for(&nt);
        let index: usize = self.rng.gen_range(0, productions.len());
        let production = &productions[index];
        let trees: Option<Vec<_>> = production
            .symbols
            .iter()
            .map(|sym| self.symbol(sym.clone()))
            .collect();
        trees.map(|trees| ParseTree::Nonterminal(nt, trees))
    }

    fn symbol(&mut self, symbol: Symbol) -> Option<ParseTree> {
        match symbol {
            Symbol::Nonterminal(nt) => self.nonterminal(nt),
            Symbol::Terminal(t) => Some(ParseTree::Terminal(t)),
        }
    }
}

impl ParseTree {
    pub fn terminals(&self) -> Vec<TerminalString> {
        let mut vec = vec![];
        self.push_terminals(&mut vec);
        vec
    }

    fn push_terminals(&self, vec: &mut Vec<TerminalString>) {
        match *self {
            ParseTree::Terminal(ref s) => vec.push(s.clone()),
            ParseTree::Nonterminal(_, ref trees) => {
                for tree in trees {
                    tree.push_terminals(vec);
                }
            }
        }
    }
}