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

//! Constraint graph.

#![allow(dead_code)]

use graph::{Graph, NodeIndex};
use std::collections::VecDeque;
use std::u32;

#[cfg(test)]
mod test;

pub trait Lattice {
    type Element: Clone + Eq;

    fn lub(&self, elem1: &Self::Element, elem2: &Self::Element) -> Option<Self::Element>;
}

pub struct ConstraintGraph<L: Lattice> {
    graph: Graph<(), ()>,
    values: Vec<L::Element>,
    lattice: L,
}

#[derive(Copy, Clone)]
pub struct Var {
    index: u32,
}

impl Var {
    pub fn index(&self) -> usize {
        self.index as usize
    }

    fn to_node_index(self) -> NodeIndex {
        NodeIndex(self.index as usize)
    }

    fn from_node_index(ni: NodeIndex) -> Var {
        assert!(ni.0 < (u32::MAX as usize));
        Var { index: ni.0 as u32 }
    }
}

impl<L> ConstraintGraph<L>
    where L: Lattice
{
    fn new(lattice: L) -> ConstraintGraph<L> {
        ConstraintGraph {
            graph: Graph::new(),
            values: Vec::new(),
            lattice: lattice,
        }
    }

    fn new_var(&mut self, initial_value: L::Element) -> Var {
        assert_eq!(self.graph.all_nodes().len(), self.values.len());
        let node_index = self.graph.add_node(());
        self.values.push(initial_value);
        Var::from_node_index(node_index)
    }

    pub fn constrain_var(&mut self, var: Var, value: L::Element) -> Vec<PropagationError<L>> {
        let propagation = Propagation::new(&self.lattice, &self.graph, &mut self.values);
        propagation.propagate(value, var)
    }

    pub fn add_edge(&mut self, source: Var, target: Var) -> Vec<PropagationError<L>> {
        let source_node = source.to_node_index();
        let target_node = target.to_node_index();

        if self.graph
               .successor_nodes(source_node)
               .any(|n| n == target_node) {
            return vec![];
        }

        self.graph.add_edge(source_node, target_node, ());
        let value = self.current_value(source);
        self.constrain_var(target, value)
    }

    pub fn current_value(&self, node: Var) -> L::Element {
        self.values[node.index()].clone()
    }
}

/// ////////////////////////////////////////////////////////////////////////

struct Propagation<'p, L>
    where L: Lattice + 'p,
          L::Element: 'p
{
    lattice: &'p L,
    graph: &'p Graph<(), ()>,
    values: &'p mut Vec<L::Element>,
    queue: VecDeque<Var>,
    errors: Vec<PropagationError<L>>,
}

pub struct PropagationError<L>
    where L: Lattice
{
    var: Var,
    old_value: L::Element,
    new_value: L::Element,
}

impl<'p, L> Propagation<'p, L>
    where L: Lattice,
          L::Element: 'p
{
    fn new(lattice: &'p L,
           graph: &'p Graph<(), ()>,
           values: &'p mut Vec<L::Element>)
           -> Propagation<'p, L> {
        Propagation {
            lattice: lattice,
            graph: graph,
            values: values,
            queue: VecDeque::new(),
            errors: Vec::new(),
        }
    }

    fn propagate(mut self, value: L::Element, var: Var) -> Vec<PropagationError<L>> {
        self.update_node(value, var);

        while let Some(dirty) = self.queue.pop_front() {
            let value = self.values[dirty.index()].clone();

            for succ_node_index in self.graph.successor_nodes(dirty.to_node_index()) {
                let succ_var = Var::from_node_index(succ_node_index);
                self.update_node(value.clone(), succ_var);
            }
        }

        self.errors
    }

    fn update_node(&mut self, value: L::Element, var: Var) {
        let cur_value = self.values[var.index()].clone();
        match self.lattice.lub(&cur_value, &value) {
            Some(new_value) => {
                if cur_value != new_value {
                    self.values[var.index()] = value;
                    self.queue.push_back(var);
                }
            }

            None => {
                // Error. Record for later.
                self.errors.push(PropagationError::<L> {
                    var: var,
                    old_value: cur_value,
                    new_value: value,
                });
            }
        }
    }
}