p8n_types/
table.rs

1// Panopticon - A libre program analysis library for machine code
2// Copyright (C) 2014-2018  The Panopticon Developers
3//
4// This library is free software; you can redistribute it and/or
5// modify it under the terms of the GNU Lesser General Public
6// License as published by the Free Software Foundation; either
7// version 2.1 of the License, or (at your option) any later version.
8//
9// This library is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12// Lesser General Public License for more details.
13//
14// You should have received a copy of the GNU Lesser General Public
15// License along with this library; if not, write to the Free Software
16// Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
17
18//! Generic table for mapping complex types to integers.
19//!
20//! This module implements `Table<K, V>`. It is used in `Function` for performace optimization.
21
22use std::collections::HashMap;
23use std::hash::Hash;
24use std::clone::Clone;
25use std::fmt::Debug;
26
27use quickcheck::{Arbitrary,Gen};
28
29use {Result,Str,Variable};
30
31#[macro_export]
32macro_rules! define_table_ref {
33    ( $name:ident ) => {
34        /// Table index
35        #[derive(Hash,Clone,Copy,Debug,PartialEq,Eq,PartialOrd,Ord)]
36        pub struct $name (usize);
37
38        impl $name {
39            /// Returns the numberic index.
40            pub fn index(&self) -> usize { self.0 }
41
42            /// Creates a new index.
43            pub fn new(i: usize) -> $name { $name(i) }
44        }
45
46        impl From<usize> for $name {
47            fn from(i: usize) -> $name { $name::new(i) }
48        }
49
50        impl Into<usize> for $name {
51            fn into(self) -> usize { self.index() }
52        }
53    };
54}
55
56define_table_ref!(NameRef);
57define_table_ref!(SegmentRef);
58define_table_ref!(StrRef);
59
60/// A SSA variable name.
61#[derive(Hash,Clone,Debug,PartialEq,Eq,PartialOrd,Ord)]
62pub struct Name {
63    base: Str,
64    subscript: Option<usize>,
65}
66
67impl Name {
68    /// Create a new SSA variable name.
69    pub fn new<S: Into<Option<usize>> + Sized>(s: Str, o: S) -> Name {
70        Name{
71            base: s,
72            subscript: o.into(),
73        }
74    }
75
76    /// Returns the SSA variable name without subscript.
77    pub fn base<'a>(&'a self) -> &'a Str { &self.base }
78
79    /// Returns the numeric subscript of this SSA name.
80    pub fn subscript(&self) -> Option<usize> { self.subscript }
81}
82
83/// Table mapping hashable values to and from numeric indices.
84#[derive(Debug,Clone)]
85pub struct Table<V: Hash + Debug + Clone + Eq,R: Clone + Copy + From<usize> + Into<usize>> {
86    refs: HashMap<V,R>,
87    values: Vec<V>,
88    facade: bool
89}
90
91impl<V: Hash + Debug + Clone + Eq,R: Clone + Copy + From<usize> + Into<usize>> Table<V,R> {
92    /// Creates a new table with initial capacity `cap`.
93    pub fn with_capacity(cap: usize) -> Table<V,R> {
94        Table{
95            refs: HashMap::with_capacity(cap),
96            values: Vec::with_capacity(cap),
97            facade: false,
98        }
99    }
100
101    /// Inserts `v` into the table, returing its index. If `v` already exists in the table its not inserted again.
102    pub fn insert(&mut self, v: &V) -> R {
103        if let Some(i) = self.refs.get(v).cloned() {
104            i
105        } else {
106            let i = self.values.len();
107            self.refs.insert(v.clone(),i.into());
108            self.values.push(v.clone());
109            i.into()
110        }
111    }
112
113    /// Returns the index of `s` in the table.
114    pub fn index(&self, s: &V) -> Result<R> {
115        match self.refs.get(s).map(|&x| x) {
116            Some(s) => Ok(s),
117            None if self.facade => Ok(0.into()),
118            None => Err("name not part of this set".into()),
119        }
120    }
121
122    /// Returns the value of the entry with index `i`.
123    pub fn value<'a>(&'a self, i: R) -> Result<&'a V> {
124        if self.facade {
125            Ok(&self.values[0])
126        } else {
127            Ok(&self.values[i.into()])
128        }
129    }
130
131    /// Number of entries in the table.
132    pub fn len(&self) -> usize {
133        self.values.len()
134    }
135
136    /// Creates a dummy tables that maps every index to `v`.
137    #[cfg(test)]
138    pub fn facade(v: &V) -> Table<V,R> {
139        let mut ret = Table{
140            refs: HashMap::default(),
141            values: Vec::default(),
142            facade: true,
143        };
144
145        ret.insert(v);
146        ret
147    }
148}
149
150impl Table<Name,NameRef> {
151    /// Shortcut for getting the index of the `Name` with the same base as `idx` but subscript
152    /// `None`.
153    pub fn base_name(&self, idx: NameRef) -> Result<NameRef> {
154        let name = self.value(idx)?;
155        match name {
156            &Name{ ref base, subscript: Some(_) } => {
157                self.index(&Name{ base: base.clone(), subscript: None })
158            }
159            &Name{ subscript: None,.. } => {
160                Ok(idx)
161            }
162        }
163    }
164
165    /// Create a new variable with `name` and `subscript`, inserting the name if it's not present
166    /// in the table.
167    pub fn var<S: Into<Str>>(&mut self, name: S, subscript: Option<usize>, bits: usize) -> Result<Variable> {
168        let i = self.insert(&Name::new(name.into(),subscript));
169        Variable::new(i,bits)
170    }
171}
172
173impl Table<Name,SegmentRef> {
174    /// Shortcut for getting the index of the `Segment` with the same base as `idx` but subscript
175    /// `None`.
176    pub fn base_name(&self, idx: SegmentRef) -> Result<SegmentRef> {
177        let seg = self.value(idx)?;
178        match seg {
179            &Name{ ref base, subscript: Some(_) } => {
180                self.index(&Name{ base: base.clone(), subscript: None })
181            }
182            &Name{ subscript: None,.. } => {
183                Ok(idx)
184            }
185        }
186    }
187}
188
189impl<V: Hash + Debug + Clone + Eq,R: Clone + Copy + From<usize> + Into<usize>> Default for Table<V,R> {
190    fn default() -> Table<V,R> {
191        Table{
192            refs: HashMap::default(),
193            values: Vec::default(),
194            facade: false,
195        }
196    }
197}
198
199impl Arbitrary for NameRef {
200    fn arbitrary<G: Gen>(g: &mut G) -> Self {
201        NameRef::new(g.gen_range(0,100))
202    }
203}
204
205impl Arbitrary for StrRef {
206    fn arbitrary<G: Gen>(g: &mut G) -> Self {
207        StrRef::new(g.gen_range(0,100))
208    }
209}
210
211/// String table.
212pub type Strings = Table<Str,StrRef>;
213
214/// Name table for RREIL code.
215pub type Names = Table<Name,NameRef>;
216
217/// Segment table RREIL code.
218pub type Segments = Table<Name,SegmentRef>;
p8n_types/table.rs

p8n_types/
table.rs
