use ::std::collections::HashSet;
use ::prettytable::Table;
use ::petgraph::graph::NodeIndex;
use ::either::Either;
use super::pattern::PatternProvider;
#[derive(Debug, Derivative)]
#[derivative(Clone(bound=""))]
pub struct MatchMatrix<P> where P: PatternProvider {
pub data: Vec<MatchMatrixElement<P>>,
pub variables: Vec<P::CfgVariable>,
pub clause_leaves: Vec<super::cfg::CfgNodeIndex>,
}
#[derive(Debug, Derivative)]
#[derivative(Clone(bound=""))]
pub struct MatchMatrixElement<P> where P: PatternProvider {
pub node: P::PatternNodeKey,
pub variable_num: usize,
pub clause_num: usize,
}
fn chunks_len<'a, T>(entities: &'a [T], chunk_len: usize, num_chunks: usize)
-> Box<Iterator<Item = &'a [T]> + 'a> {
assert!(entities.len() == (chunk_len * num_chunks));
let ret = if chunk_len == 0 {
Either::Left((0..num_chunks).map(|_| [].as_ref()))
} else {
Either::Right(entities.chunks(chunk_len))
};
Box::new(ret)
}
impl<P> MatchMatrix<P> where P: PatternProvider {
pub fn new(nodes: &[P::PatternNodeKey],
leaves: Vec<super::cfg::CfgNodeIndex>,
vars: Vec<P::CfgVariable>) -> Self {
assert!(vars.len() * leaves.len() == nodes.len());
let data = if vars.len() == 0 {
vec![]
} else {
nodes.chunks(vars.len()).enumerate()
.flat_map(|(clause_idx, clause)| {
clause.iter().enumerate().map(move |(variable_idx, pat)| {
MatchMatrixElement {
variable_num: variable_idx,
clause_num: clause_idx,
node: *pat,
}
})
}).collect()
};
MatchMatrix {
data: data,
variables: vars,
clause_leaves: leaves,
}
}
pub fn select_specialize_variable(&self, pattern: &P) -> usize
{
let mut sums = vec![(0, true); self.variables.len()];
let clauses = self.data.chunks(self.variables.len());
for clause in clauses {
for variable_pattern in clause.iter() {
if pattern.is_wildcard(pattern.get_kind(variable_pattern.node)) {
sums[variable_pattern.variable_num].1 = false;
} else {
if sums[variable_pattern.variable_num].1 {
sums[variable_pattern.variable_num].0 += 1;
}
}
}
}
sums.iter().enumerate()
.max_by_key(|&(_, s)| s.0)
.map(|(i, _)| i).unwrap()
}
pub fn get_var(&self, var: usize) -> P::CfgVariable {
self.variables[var]
}
pub fn collect_specialization_types<'a>(&self, pattern: &'a P,
variable: usize)
-> HashSet<P::PatternNodeKind>
{
let mut types = HashSet::new();
let clauses = self.data.chunks(self.variables.len());
for clause in clauses {
let variable_pattern = &clause[variable];
types.insert(pattern.get_kind(variable_pattern.node));
}
types.remove(&pattern.get_wildcard());
types
}
pub fn specialize(&self, ctx: &mut super::MatchCompileContext<P>,
variable: usize,
on: P::PatternNodeKind)
-> (Vec<P::CfgVariable>, MatchMatrix<P>)
{
let to_specialize_rows: Vec<(usize, &[MatchMatrixElement<_>])> = self.data
.chunks(self.variables.len())
.enumerate()
.filter(|&(_, node)| ctx.pattern.kind_includes(on, node[variable].node))
.collect();
let specialize_nodes: Vec<&MatchMatrixElement<_>> = to_specialize_rows.iter()
.map(|&(_, nodes)| &nodes[variable])
.collect();
let rest_nodes: Vec<Vec<&MatchMatrixElement<_>>> = to_specialize_rows.iter()
.map(|&(_, nodes)| {
nodes.iter()
.filter(|node| node.variable_num != variable)
.collect::<Vec<_>>()
})
.collect();
let specialized = {
let nodes: Vec<_> = specialize_nodes.iter()
.map(|node| node.node)
.collect();
ctx.pattern.expand_clause_nodes(nodes)
};
let specialized_chunked = chunks_len(&specialized.nodes, specialized.variables.len(),
specialized.clauses);
let new_nodes: Vec<_> = specialized_chunked
.zip(rest_nodes.iter())
.flat_map(|(specialized, rest)| {
let specialized_m = specialized.iter().map(|node| *node);
let rest_m = rest.iter().map(|node| node.node);
specialized_m.chain(rest_m)
})
.collect();
let new_clause_leaves: Vec<_> = to_specialize_rows.iter()
.map(|&(clause_num, _)| self.clause_leaves[clause_num])
.collect();
let new_variables: Vec<_> = {
let rest_variables = self.variables.iter()
.enumerate()
.filter(|&(var_num, _)| var_num != variable)
.map(|(_, var)| *var);
specialized.variables.iter()
.map(|var| *var)
.chain(rest_variables)
.collect()
};
let new_mat = Self::new(new_nodes.as_slice(),
new_clause_leaves, new_variables);
(specialized.variables, new_mat)
}
pub fn iterate_clauses<'a>(&'a self) -> Box<Iterator<Item = (NodeIndex, &'a [MatchMatrixElement<P>])> + 'a> {
let iter = self.clause_leaves.iter().map(|l| *l)
.zip(chunks_len(&self.data, self.variables.len(), self.clause_leaves.len()));
Box::new(iter)
}
pub fn default(&self, ctx: &mut super::MatchCompileContext<P>,
variable: usize)
-> (Vec<P::CfgVariable>, MatchMatrix<P>)
{
let wildcard = ctx.pattern.get_wildcard();
self.specialize(ctx, variable, wildcard)
}
pub fn is_empty(&self) -> bool {
self.clause_leaves.len() == 0
}
pub fn has_wildcard_head(&self, pattern: &P)
-> Option<super::cfg::CfgNodeIndex>
{
assert!(self.clause_leaves.len() > 0);
if self.variables.len() == 0 {
Some(self.clause_leaves[0])
} else {
let has_wildcard_head = self.data
.chunks(self.variables.len())
.next().unwrap()
.iter().all(|p| {
pattern.is_wildcard(pattern.get_kind(p.node))
});
if has_wildcard_head {
Some(self.clause_leaves[0])
} else {
None
}
}
}
pub fn to_table(&self, pat: &P) -> Table {
use ::prettytable::Cell;
let mut table = Table::new();
{
let head_row = table.add_empty_row();
head_row.add_cell(Cell::new(&format!(
"{}*{}=={}",
self.variables.len(),
self.clause_leaves.len(),
self.data.len())));
for variable in self.variables.iter() {
let var_str = format!("{:?}", variable);
head_row.add_cell(Cell::new(&var_str));
}
}
for row_idx in 0..self.clause_leaves.len() {
let t_row = table.add_empty_row();
let leaf_id = format!("{:?}", self.clause_leaves[row_idx]);
t_row.add_cell(Cell::new(&leaf_id));
let row_start = row_idx * self.variables.len();
for col in &self.data[row_start..(row_start+self.variables.len())] {
let node = pat.get_kind(col.node);
let cell_fmt = format!("{:?}", node);
let cell = Cell::new(&cell_fmt);
t_row.add_cell(cell);
}
}
table
}
}