grammartec 0.3.1

The Nautilus grammartec
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127

// Nautilus
// Copyright (C) 2020  Daniel Teuchert, Cornelius Aschermann, Sergej Schumilo

// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.

// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.

use rand::rngs::StdRng;
use rand::thread_rng;
use rand::SeedableRng;
use std::collections::HashMap;
use std::fmt;

use context::Context;
use loaded_dice::LoadedDiceSampler;
use newtypes::{NTermID, NodeID};
use tree::Tree;

pub struct RecursionInfo {
    recursive_parents: HashMap<NodeID, NodeID>,
    sampler: LoadedDiceSampler<StdRng>,
    depth_by_offset: Vec<usize>,
    node_by_offset: Vec<NodeID>,
}

impl fmt::Debug for RecursionInfo {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("RecursionInfo")
            .field("recursive_parents", &self.recursive_parents)
            .field("depth_by_offset", &self.depth_by_offset)
            .field("node_by_offset", &self.node_by_offset)
            .finish()
    }
}

impl RecursionInfo {
    #[must_use]
    pub fn new(t: &Tree, n: NTermID, ctx: &Context) -> Option<Self> {
        let (recursive_parents, node_by_offset, depth_by_offset) =
            RecursionInfo::find_parents(t, n, ctx)?;
        let sampler = RecursionInfo::build_sampler(&depth_by_offset);
        Some(Self {
            recursive_parents,
            sampler,
            depth_by_offset,
            node_by_offset,
        })
    }

    // constructs a tree where each node points to the first ancestor with the same nonterminal (e.g. each node points the next node above it, were the pair forms a recursive occurance of a nonterminal).
    // This structure is an ''inverted tree''. We use it later to sample efficiently from the set
    // of all possible recursive pairs without occuring n^2 overhead. Additionally, we return a
    // ordered vec of all nodes with nonterminal n and the depth of this node in the freshly
    // constructed 'recursion tree' (weight). Each node is the end point of exactly `weigth` many
    // differnt recursions. Therefore we use the weight of the node to sample the endpoint of a path trough the
    // recursion tree. Then we just sample the length of this path uniformly as (1.. weight). This
    // yields a uniform sample from the whole set of recursions inside the tree. If you read this, Good luck you are on your own.
    fn find_parents(
        t: &Tree,
        nt: NTermID,
        ctx: &Context,
    ) -> Option<(HashMap<NodeID, NodeID>, Vec<NodeID>, Vec<usize>)> {
        let mut stack = vec![(None, 0)];
        let mut res = None;
        for (i, rule) in t.rules.iter().enumerate() {
            let node = NodeID::from(i);
            let (mut maybe_parent, depth) = stack.pop().expect("RAND_3404900492");
            if ctx.get_nt(rule) == nt {
                if let Some(parent) = maybe_parent {
                    let (mut parents, mut ids, mut weights) =
                        res.unwrap_or_else(|| (HashMap::new(), vec![], vec![]));
                    parents.insert(node, parent);
                    ids.push(node);
                    weights.push(depth);
                    res = Some((parents, ids, weights));
                }
                maybe_parent = Some(node);
            }
            for _ in 0..ctx.get_num_children(rule) {
                stack.push((maybe_parent, depth + 1));
            }
        }
        res
    }

    fn build_sampler(depths: &[usize]) -> LoadedDiceSampler<StdRng> {
        let mut weights = depths.iter().map(|x| *x as f64).collect::<Vec<_>>();
        let norm: f64 = weights.iter().sum();
        assert!(norm > 0.0);
        for v in &mut weights {
            *v /= norm;
        }
        LoadedDiceSampler::new(
            weights,
            StdRng::from_rng(thread_rng()).expect("RAND_1769941938"),
        )
    }

    pub fn get_random_recursion_pair(&mut self) -> (NodeID, NodeID) {
        let offset = self.sampler.sample();
        self.get_recursion_pair_by_offset(offset)
    }

    #[must_use]
    pub fn get_recursion_pair_by_offset(&self, offset: usize) -> (NodeID, NodeID) {
        let node1 = self.node_by_offset[offset];
        let mut node2 = node1;
        for _ in 0..(self.depth_by_offset[offset]) {
            node2 = self.recursive_parents[&node1];
        }
        (node2, node1)
    }

    #[must_use]
    pub fn get_number_of_recursions(&self) -> usize {
        self.node_by_offset.len()
    }
}