gcollections/ops/
lattice.rs

1// Copyright 2018 Pierre Talbot (IRCAM)
2
3// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
4// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
5// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
6// option. This file may not be copied, modified, or distributed
7// except according to those terms.
8
9/// A [lattice](https://en.wikipedia.org/wiki/Lattice_(order)) is an ordered set where every pair of elements can be combined with a `join` and `meet` operations.
10/// The following traits operate on an element of the lattice, and do not represent a set of elements (which would be the whole lattice).
11/// This is the reason why we do not require `Lattice` to inherit from `Collection`.
12
13use trilean::SKleene;
14
15pub trait Join
16{
17  fn join(self, other: Self) -> Self;
18}
19
20pub trait Meet
21{
22  fn meet(self, other: Self) -> Self;
23}
24
25pub trait Entailment
26{
27  fn entail(&self, other: &Self) -> SKleene;
28}
29
30pub trait StrictEntailment
31{
32  /// Must be similar to `a.entail(&b) && a != b`.
33  fn strict_entail(&self, other: &Self) -> SKleene;
34}
35
36macro_rules! strict_entailment_impl
37{
38  ( $( $keyword:tt ),*) =>
39  {
40    impl<R> StrictEntailment for R where
41      R: Entailment + Eq
42    {
43      $($keyword)* fn strict_entail(&self, other: &R) -> SKleene {
44        self.entail(other).and(SKleene::from_bool(self != other))
45      }
46    }
47  }
48}
49
50#[cfg(feature = "nightly")]
51strict_entailment_impl!(default);
52#[cfg(not(feature = "nightly"))]
53strict_entailment_impl!();
54
55pub trait Top {
56  fn top() -> Self;
57}
58
59pub trait Bot {
60  fn bot() -> Self;
61}
62
63pub trait Lattice:
64   Join
65 + Meet
66 + Entailment
67{}
68
69impl<R> Lattice for R where
70 R: Join,
71 R: Meet,
72 R: Entailment,
73{}
74
75pub trait BoundedLattice:
76   Lattice
77 + Top
78 + Bot
79{}
80
81impl<R> BoundedLattice for R where
82 R: Lattice,
83 R: Top,
84 R: Bot,
85{}
86
87pub mod test
88{
89  use super::*;
90  use trilean::SKleene;
91  use trilean::SKleene::*;
92  use std::fmt::{Display, Debug};
93
94  pub struct LatticeTester<T>
95  {
96    test_id: usize,
97    current_test: String,
98    data_a: Vec<T>,
99    data_b: Vec<T>,
100    expected_entailment: Vec<SKleene>,
101    expected_join: Vec<T>,
102    expected_meet: Vec<T>
103  }
104
105  impl<T> LatticeTester<T> where
106    T: BoundedLattice + Clone + Debug + Display + Eq
107  {
108    pub fn new(test_id: usize, data_a: Vec<T>, data_b: Vec<T>,
109      expected_entailment: Vec<SKleene>,
110      expected_join: Vec<T>,
111      expected_meet: Vec<T>) -> Self
112    {
113      let tester = LatticeTester {
114        test_id: test_id,
115        current_test: String::new(),
116        data_a: data_a,
117        data_b: data_b,
118        expected_entailment: expected_entailment,
119        expected_join: expected_join,
120        expected_meet: expected_meet
121      };
122      tester.verify_input_data();
123      tester
124    }
125
126    fn verify_input_data(&self) {
127      assert_eq!(self.data_a.len(), self.data_b.len());
128      assert_eq!(self.data_a.len(), self.expected_entailment.len());
129      assert_eq!(self.data_a.len(), self.expected_join.len());
130      assert_eq!(self.data_a.len(), self.expected_meet.len());
131    }
132
133    pub fn test_all(mut self) {
134      let n = self.data_a.len();
135      for i in 0..n {
136        self.current_test = self.make_test_name(i, "entail");
137        self.test_entailment(self.data_a[i].clone(), self.data_b[i].clone(), self.expected_entailment[i]);
138      }
139      for i in 0..n {
140        self.current_test = self.make_test_name(i, "join");
141        self.test_join(self.data_a[i].clone(), self.data_b[i].clone(), self.expected_join[i].clone());
142      }
143      for i in 0..n {
144        self.current_test = self.make_test_name(i, "meet");
145        self.test_meet(self.data_a[i].clone(), self.data_b[i].clone(), self.expected_meet[i].clone());
146      }
147    }
148
149    fn make_test_name(&self, idx: usize, op: &str) -> String {
150      format!("[{}] `{}`-test on the data with the index {} has failed.\n\
151                 a = {}\n\
152                 b = {}\n\
153                 reason: ", self.test_id, op, idx, self.data_a[idx], self.data_b[idx])
154    }
155
156    pub fn test_entailment(&self, a: T, b: T, expected: SKleene)
157    {
158      let ab = a.entail(&b);
159      self.assert_expected("a.entail(b)", ab.clone(), expected, "");
160      let ba = b.entail(&a);
161      match ab {
162        True => {
163          assert!(ba != Unknown,
164            "{}`a.entail(b) == True` and `b.entail(a) == Unknown` \n\
165             problem: if `a |= b` holds, then `b |= a` is either true (a = b) or false.\n\
166             note: `a` and `b` form a chain and can not be unordered.",
167            self.current_test);
168          match ba {
169            True => self.test_equality(a, b, true,
170              "\n problem: if `b |= a` is `true` then we must have `a == b`."),
171            False => self.test_strict_entail(a, b, True),
172            Unknown => self.test_strict_entail(a, b, Unknown)
173          }
174        },
175        False | Unknown => {
176          self.assert_expected("b |= a", ba, !ab,
177            format!("\n  problem: if `a |= b` is `{}` then we must have `b |= a` equal to `{}`.",
178              ab, !ab).as_str());
179          self.test_equality(a, b, false,
180            format!("\n problem: if `a |= b` is `{}` then we must have `a != b`", ab).as_str());
181        }
182      }
183    }
184
185    fn test_equality(&self, a: T, b: T, expected: bool, msg: &str) {
186      self.assert_expected("a == b", a == b, expected, msg);
187      self.assert_expected("b == a", b == a, expected, msg);
188    }
189
190    fn assert_expected<U: Eq + Debug + Display>(&self, op: &str, obtained: U, expected: U, msg: &str) {
191      assert_eq!(obtained, expected,
192        "{}`{}` is equal to `{}` instead of the expected value `{}`.{}",
193          self.current_test, op, obtained, expected, msg);
194    }
195
196    fn test_strict_entail(&self, a: T, b: T, expected: SKleene) {
197      let ab = a.strict_entail(&b);
198      let ba = b.strict_entail(&a);
199      self.assert_expected("a.strict_entail(b)", ab, expected, "");
200      self.assert_expected("b.strict_entail(a)", ba, !expected, "");
201      match expected {
202        True | Unknown => self.test_equality(a, b, false,
203          format!("\n problem: if `a.strict_entail(b)` is `{}` then we must have `a != b`.", expected).as_str()),
204        False => (),
205      }
206    }
207
208    pub fn test_join(&self, a: T, b: T, expected: T) {
209      self.test_top_bot_join(a.clone());
210      let c = a.clone().join(b.clone());
211      self.test_equality(c.clone(), expected.clone(), true,
212        format!("\n problem: `a.join(b)` != {}.", expected).as_str());
213
214      // Test commutativity
215      let d = b.clone().join(a.clone());
216      self.test_equality(d.clone(), c.clone(), true,
217        "\n problem (commutativity): `a.join(b)` != b.join(a).");
218
219      // Test idempotence
220      let e = a.clone().join(b.clone()).join(c.clone());
221      self.test_equality(c.clone(), e.clone(), true,
222        "\n problem (idempotency): `a.join(b)` != `a.join(b).join(a.join(b))`.");
223      let f = d.clone().join(c.clone());
224      self.test_equality(c.clone(), f.clone(), true,
225        "\n problem (idempotency): `a.join(b)` != `b.join(a).join(a.join(b))`.");
226      let g = a.clone().join(a.clone());
227      let h = b.clone().join(b.clone());
228      self.test_equality(a.clone(), g.clone(), true,
229        "\n problem (idempotency): `a` != `a.join(a)`.");
230      self.test_equality(b.clone(), h.clone(), true,
231        "\n problem (idempotency): `b` != `b.join(b)`.");
232
233      // Test relation with entailment.
234      self.test_entailment(c.clone(), a.clone(), True);
235      self.test_entailment(c.clone(), b.clone(), True);
236      if a == c {
237        self.test_entailment(a.clone(), b.clone(), True);
238      }
239      if b == c {
240        self.test_entailment(b.clone(), a.clone(), True);
241      }
242    }
243
244    pub fn test_meet(&self, a: T, b: T, expected: T) {
245      self.test_top_bot_meet(a.clone());
246      let c = a.clone().meet(b.clone());
247      self.test_equality(c.clone(), expected.clone(), true,
248        format!("\n problem: `a.meet(b)` != {}.", expected).as_str());
249
250      // Test commutativity
251      let d = b.clone().meet(a.clone());
252      self.test_equality(d.clone(), c.clone(), true,
253        "\n problem (commutativity): `a.meet(b)` != b.meet(a).");
254
255      // Test idempotence
256      let e = a.clone().meet(b.clone()).meet(c.clone());
257      self.test_equality(c.clone(), e.clone(), true,
258        "\n problem (idempotency): `a.meet(b)` != `a.meet(b).meet(a.meet(b))`.");
259      let f = d.clone().meet(c.clone());
260      self.test_equality(c.clone(), f.clone(), true,
261        "\n problem (idempotency): `a.meet(b)` != `b.meet(a).meet(a.meet(b))`.");
262      let g = a.clone().meet(a.clone());
263      let h = b.clone().meet(b.clone());
264      self.test_equality(a.clone(), g.clone(), true,
265        "\n problem (idempotency): `a` != `a.meet(a)`.");
266      self.test_equality(b.clone(), h.clone(), true,
267        "\n problem (idempotency): `b` != `b.meet(b)`.");
268
269      // Test relation with entailment.
270      self.test_entailment(a.clone(), c.clone(), True);
271      self.test_entailment(b.clone(), c.clone(), True);
272      if a == c {
273        self.test_entailment(b.clone(), a.clone(), True);
274      }
275      if b == c {
276        self.test_entailment(a.clone(), b.clone(), True);
277      }
278    }
279
280    fn test_top_bot_join(&self, a: T) {
281      let top = T::top();
282      let bot = T::bot();
283      self.assert_expected("a.join(top)", a.clone().join(top.clone()), top.clone(),
284        "\n problem: `a.join(top)` must be equal to `top`.");
285      self.assert_expected("top.join(a)", top.clone().join(a.clone()), top.clone(),
286        "\n problem: `top.join(a)` must be equal to `top`.");
287     self.assert_expected("a.join(bot)", a.clone().join(bot.clone()), a.clone(),
288        "\n problem: `a.join(bot)` must be equal to `a`.");
289      self.assert_expected("bot.join(a)", bot.clone().join(a.clone()), a.clone(),
290        "\n problem: `bot.join(a)` must be equal to `a`.");
291    }
292
293    fn test_top_bot_meet(&self, a: T) {
294      let top = T::top();
295      let bot = T::bot();
296      self.assert_expected("a.meet(top)", a.clone().meet(top.clone()), a.clone(),
297        "\n problem: `a.meet(top)` must be equal to `a`.");
298      self.assert_expected("top.meet(a)", top.clone().meet(a.clone()), a.clone(),
299        "\n problem: `top.meet(a)` must be equal to `a`.");
300     self.assert_expected("a.meet(bot)", a.clone().meet(bot.clone()), bot.clone(),
301        "\n problem: `a.meet(bot)` must be equal to `bot`.");
302      self.assert_expected("bot.meet(a)", bot.clone().meet(a.clone()), bot.clone(),
303        "\n problem: `bot.meet(a)` must be equal to `bot`.");
304    }
305  }
306}
gcollections/ops/lattice.rs

gcollections/ops/
lattice.rs
