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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

/*******************************************************************************
 * Copyright (c) 2017 Association Cénotélie (cenotelie.fr)
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser 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 Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General
 * Public License along with this program.
 * If not, see <http://www.gnu.org/licenses/>.
 ******************************************************************************/

//! Module for AST subtree in parsers

use super::TREE_ACTION_REPLACE_BY_CHILDREN;
use super::TreeAction;
use super::super::ast::Ast;
use super::super::ast::AstCell;
use super::super::ast::TableElemRef;

/// Represents a sub-tree in an AST
/// A sub-tree is composed of a root with its children.
/// The children may also have children.
/// The maximum depth of a sub-tree is 2 (root, children and children's children), in which case the root is always a replaceable node.
/// The internal representation of a sub-tree is based on arrays.
/// The organization is that a node's children are immediately following it in the array.
/// For example, the tree `A(B(CD)E(FG))` is represented as `[ABCDEFG]`.
#[derive(Clone)]
pub struct SubTree {
    /// The nodes in this buffer
    nodes: Vec<AstCell>,
    /// The tree actions for the nodes
    actions: Vec<TreeAction>
}

impl SubTree {
    /// Creates a new sub-tree with the expected size
    pub fn new(size: usize) -> SubTree {
        SubTree {
            nodes: Vec::<AstCell>::with_capacity(size),
            actions: Vec::<TreeAction>::with_capacity(size)
        }
    }

    /// Gets the label of the node at the given index
    pub fn get_label_at(&self, index: usize) -> TableElemRef {
        self.nodes[index].label
    }

    /// Sets the label of the node at the given index
    pub fn set_label_at(&mut self, index: usize, label: TableElemRef) {
        self.nodes[index].label = label;
    }

    /// Gets the tree action applied onto the node at the given index
    pub fn get_action_at(&self, index: usize) -> TreeAction {
        self.actions[index]
    }

    /// Sets the tree action applied onto the node at the given index
    pub fn set_action_at(&mut self, index: usize, action: TreeAction) {
        self.actions[index] = action;
    }

    /// Gets the number of children of the node at the given index
    pub fn get_children_count_at(&self, index: usize) -> usize {
        self.nodes[index].count as usize
    }

    /// Sets the number of children of the node at the given index
    pub fn set_children_count_at(&mut self, index: usize, count: usize) {
        self.nodes[index].count = count as u32;
    }

    /// Gets the total number of nodes in this sub-tree
    pub fn get_size(&self) -> usize {
        if self.actions[0] == TREE_ACTION_REPLACE_BY_CHILDREN {
            let mut size = 1;
            for _i in 0..self.nodes[0].count {
                size += self.nodes[size].count as usize + 1;
            }
            size
        } else {
            self.nodes[0].count as usize
        }
    }

    /// Initializes the root of this sub-tree
    pub fn setup_root(&mut self, symbol: TableElemRef, action: TreeAction) {
        self.nodes.push(AstCell {
            label: symbol,
            count: 0,
            first: 0
        });
        self.actions.push(action);
    }

    /// Copy the content of this sub-tree to the given sub-tree's buffer beginning at the given index
    /// This methods only applies in the case of a depth 1 sub-tree (only a root and its children).
    /// The results of this method in the case of a depth 2 sub-tree is undetermined.
    pub fn copy_to(&self, destination: &mut SubTree) -> usize {
        let result = destination.nodes.len();
        destination.nodes.push(self.nodes[0]);
        destination.actions.push(self.actions[0]);
        for i in 0..self.nodes[0].count as usize {
            destination.nodes.push(self.nodes[i + 1]);
            destination.actions.push(self.actions[i + 1]);
        }
        result
    }

    /// Copy the root's children of this sub-tree to the given sub-tree's buffer beginning at the given index
    /// This methods only applies in the case of a depth 2 sub-tree.
    pub fn copy_children_to(&self, destination: &mut SubTree) -> usize {
        let result = destination.nodes.len();
        let mut index = 1;
        for _i in 0..self.nodes[0].count {
            // for all direct children
            destination.nodes.push(self.nodes[index]);
            destination.actions.push(self.actions[index]);
            let count = self.nodes[index].count as usize;
            for j in 0..count {
                // for all sub-children
                destination.nodes.push(self.nodes[index + j + 1]);
                destination.actions.push(self.actions[index + j + 1]);
            }
            index += count + 1;
        }
        result
    }

    /// Commits the children of a sub-tree in this buffer to the final ast
    /// If the index is 0, the root's children are committed, assuming this is a depth-1 sub-tree.
    /// If not, the children of the child at the given index are committed.
    pub fn commit_children_of(&mut self, index: usize, ast: &mut Ast) {
        self.nodes[index].first =
            ast.store(&self.nodes, index + 1, self.nodes[index].count as usize) as u32;
    }

    /// Commits this buffer to the final ast
    pub fn commit(&mut self, ast: &mut Ast) {
        self.commit_children_of(0, ast);
        ast.store_root(self.nodes[0]);
    }

    /// Pushes a new node into this buffer
    pub fn push(&mut self, symbol: TableElemRef, action: TreeAction) -> usize {
        let result = self.nodes.len();
        self.nodes.push(AstCell {
            label: symbol,
            count: 0,
            first: 0
        });
        self.actions.push(action);
        result
    }

    /// Moves an item within the buffer
    pub fn move_node(&mut self, from: usize, to: usize) {
        self.nodes[to] = self.nodes[from];
    }

    /// Moves a range of items within the buffer
    pub fn move_range(&mut self, from: usize, to: usize, length: usize) {
        for i in 0..length {
            self.nodes[to + i] = self.nodes[from + i];
            self.actions[to + i] = self.actions[from + i];
        }
    }
}