rain_lang/graph/
region.rs

1/*!
2A region, containing scoped nodes, parameters and outputs.
3*/
4use parking_lot::{RwLock, RwLockReadGuard, RwLockWriteGuard};
5use std::ops::Deref;
6use std::cmp::{PartialOrd, Ordering};
7use std::sync::{Arc, Weak};
8use std::convert::Infallible;
9use std::hash::{Hash, Hasher};
10use crate::value::{
11    ValId, ValueEnum, ValueData, ValueDesc, Value,
12    error::RegionAlreadyFused
13};
14
15/// A region into which nodes are scoped
16#[derive(Debug, Clone)]
17pub struct Region(Arc<RegionData>);
18
19impl Region {
20    /// Create a new region
21    pub fn new() -> Region { Region::new_in(WeakRegion::default()) }
22    /// Create a new region with a given parent
23    pub fn new_in(parent: WeakRegion) -> Region {
24        let depth = parent.upgrade().map(|parent| parent.depth).unwrap_or(0) + 1;
25        let result = Region(Arc::new(RegionData {
26            parent,
27            depth,
28            params: RwLock::new(Parameters::new()),
29            _private: ()
30        }));
31        let weak = result.downgrade();
32        result.params.write().this = weak;
33        result
34    }
35    /// Downgrade a region to a weak reference
36    #[inline] pub fn downgrade(&self) -> WeakRegion { WeakRegion(Arc::downgrade(&self.0)) }
37}
38
39impl PartialEq for Region {
40    fn eq(&self, other: &Region) -> bool { Arc::ptr_eq(&self.0, &other.0) }
41}
42
43impl Eq for Region {}
44
45impl Hash for Region {
46    #[inline] fn hash<H: Hasher>(&self, hasher: &mut H) {
47        Arc::as_ptr(&self.0).hash(hasher)
48    }
49}
50
51impl PartialOrd for Region {
52    fn partial_cmp(&self, other: &Region) -> Option<Ordering> {
53        if self == other { return Some(Ordering::Equal) }
54        let ordering = self.depth.cmp(&other.depth);
55        let (deeper, shallower) = match ordering {
56            Ordering::Equal => { return None },
57            Ordering::Greater => (self, other),
58            Ordering::Less => (other, self)
59        };
60        let mut parent = deeper.parent.upgrade()?;
61        while parent.depth > shallower.depth {
62            parent = parent.parent.upgrade()?;
63        }
64        if &parent == shallower {
65            Some(ordering.reverse())
66        } else {
67            None
68        }
69    }
70}
71
72impl PartialEq<WeakRegion> for Region {
73    fn eq(&self, other: &WeakRegion) -> bool {
74        if let Some(other) = other.upgrade() { other.eq(self) } else { false }
75    }
76}
77
78impl PartialOrd<WeakRegion> for Region {
79    fn partial_cmp(&self, other: &WeakRegion) -> Option<Ordering> {
80        if other.is_null() { Some(Ordering::Less) }
81        else { self.partial_cmp(&other.upgrade()?) }
82    }
83}
84
85impl PartialEq<Region> for WeakRegion {
86    fn eq(&self, other: &Region) -> bool { other.eq(self) }
87}
88
89impl PartialOrd<Region> for WeakRegion {
90    fn partial_cmp(&self, other: &Region) -> Option<Ordering> {
91        other.partial_cmp(self).map(Ordering::reverse)
92    }
93}
94
95impl Deref for Region {
96    type Target = RegionData;
97    #[inline] fn deref(&self) -> &RegionData { self.0.deref() }
98}
99
100/// A weak handle on a region
101#[derive(Debug, Clone, Default)]
102pub struct WeakRegion(pub Weak<RegionData>);
103
104impl WeakRegion {
105    /// Attempt to upgrade a region to a strong reference
106    #[inline] pub fn upgrade(&self) -> Option<Region> { self.0.upgrade().map(Region) }
107    /// Check whether a weak region is null
108    #[inline] pub fn is_null(&self) -> bool { self == &WeakRegion::default() }
109    /// Get the outer region of nested regions, if either is
110    #[inline] pub fn outer<'a>(&'a self, other: &'a WeakRegion) -> Option<&'a WeakRegion> {
111        self.partial_cmp(other).map(|ord| match ord { Ordering::Greater => self, _ => other })
112    }
113    /// Get the inner region of nested regions, if either is
114    #[inline] pub fn inner<'a>(&'a self, other: &'a WeakRegion) -> Option<&'a WeakRegion> {
115        self.partial_cmp(other).map(|ord| match ord { Ordering::Less => self, _ => other })
116    }
117    /// Get the innermost region of a list of nested regions, assuming all are comparable.
118    /// Return an error if not.
119    #[inline] pub fn innermost<'a, I>(&'a self, mut regions: I)
120    -> Result<&'a WeakRegion, (&'a WeakRegion, &'a WeakRegion)>
121    where I: Iterator<Item=&'a WeakRegion> {
122        let mut res = self;
123        while let Some(region) = regions.next() {
124            match res.partial_cmp(region) {
125                None => return Err((res, region)),
126                Some(Ordering::Less) => res = region,
127                _ => {}
128            }
129        }
130        Ok(res)
131    }
132}
133
134impl PartialEq for WeakRegion {
135    fn eq(&self, other: &WeakRegion) -> bool { Weak::ptr_eq(&self.0, &other.0) }
136}
137
138impl Eq for WeakRegion {}
139
140impl Hash for WeakRegion {
141    #[inline] fn hash<H: Hasher>(&self, hasher: &mut H) {
142        self.0.as_ptr().hash(hasher)
143    }
144}
145
146impl PartialOrd for WeakRegion {
147    fn partial_cmp(&self, other: &WeakRegion) -> Option<Ordering> {
148        if self == other {
149            Some(Ordering::Equal)
150        } else if self.is_null() {
151            Some(Ordering::Greater)
152        } else if other.is_null() {
153            Some(Ordering::Less)
154        } else {
155            let left = self.upgrade()?;
156            let right = other.upgrade()?;
157            let ordering = left.partial_cmp(&right);
158            debug_assert_ne!(ordering, Some(Ordering::Equal));
159            ordering
160        }
161    }
162}
163
164/// The data defining a region
165#[derive(Debug)]
166pub struct RegionData {
167    /// The parent scope of this region
168    pub parent: WeakRegion,
169    /// The depth of this region
170    pub depth: usize,
171    /// The parameters of a region
172    pub params: RwLock<Parameters>,
173    /// Disallow directly creating `RegionData`
174    _private: ()
175}
176
177impl RegionData {
178    /// Get the parameters of a region
179    pub fn params(&self) -> RwLockReadGuard<Parameters> { self.params.read() }
180    /// Mutably get the parameters of a region
181    pub fn params_mut(&self) -> RwLockWriteGuard<Parameters> { self.params.write() }
182    /// Add a parameter to this region, get the parameter back along with its index
183    pub fn add_param(&self, desc: ParameterDesc) -> (usize, ValId) {
184        let mut params = self.params_mut();
185        let ix = params.add_param(desc).expect("Unfused region");
186        let param = params.arr()[ix].clone();
187        (ix, param)
188    }
189    /// Add a parameter to this region with a given type, get the parameter back
190    pub fn add_with_ty(&self, ty: ValId) -> (usize, ValId) {
191        let mut params = self.params_mut();
192        let ix = params.add_with_ty(ty).expect("Unfused region");
193        let param = params.arr()[ix].clone();
194        (ix, param)
195    }
196    /// Get the this pointer of this region
197    pub fn this(&self) -> WeakRegion { self.params().this() }
198}
199
200/// The roots of a region
201#[derive(Debug)]
202pub struct Parameters {
203    /// The actual parameters
204    arr: Vec<ValId>,
205    /// A self-pointer to the region
206    this: WeakRegion,
207    /// Whether this node is fused
208    fused: bool
209}
210
211impl Parameters {
212    /// Create a new, empty set of region roots
213    fn new() -> Parameters {
214        Parameters { arr: Vec::new(), this: WeakRegion::default(), fused: false }
215    }
216    /// Add a new parameter to the region. Get the associated index
217    pub fn add_param(&mut self, desc: ParameterDesc) -> Result<usize, RegionAlreadyFused> {
218        if self.fused { return Err(RegionAlreadyFused) } //TODO
219        let ix = self.arr.len();
220        let param = Parameter {
221            ty: desc.ty,
222            region: self.this.clone(),
223            ix
224        };
225        let node = ValId::from(param);
226        self.arr.push(node);
227        Ok(ix)
228    }
229    /// Add a new parameter with a given type
230    pub fn add_with_ty(&mut self, ty: ValId) -> Result<usize, RegionAlreadyFused> {
231        self.add_param(ParameterDesc { ty })
232    }
233    /// Get the parameter array
234    pub fn arr(&self) -> &[ValId] { &self.arr }
235    /// Get the this pointer of this region
236    pub fn this(&self) -> WeakRegion { self.this.clone() }
237    /// Check whether this region is fused
238    pub fn fused(&self) -> bool { self.fused }
239    /// Fuse this region.
240    pub fn fuse(&mut self) { self.fused = true }
241}
242
243/// A descriptor for a region parameter
244#[derive(Debug, Clone, PartialEq)]
245pub struct ParameterDesc {
246    /// The type of this parameter
247    pub ty: ValId
248}
249
250/// A parameter for a region
251#[derive(Debug, Clone, Hash)]
252pub struct Parameter {
253    /// The type of this parameter
254    pub ty: ValId,
255    /// The region this parameter is associated to
256    region: WeakRegion,
257    /// The parameter index of this parameter
258    ix: usize
259}
260
261impl From<Parameter> for ValueEnum {
262    fn from(param: Parameter) -> ValueEnum { ValueEnum::Parameter(param) }
263}
264impl From<Parameter> for ValueData {
265    fn from(param: Parameter) -> ValueData {
266        let region = param.region.clone();
267        ValueData::with_region(ValueEnum::Parameter(param), region)
268    }
269}
270impl From<Parameter> for ValId {
271    fn from(param: Parameter) -> ValId {
272        ValId::try_new(ValueData::from(param)).expect("Impossible")
273    }
274}
275
276impl ValueDesc for Parameter {
277    type Err = Infallible;
278}
279
280impl Value for Parameter {}
281
282impl Parameter {
283    /// Get the parameter index of this parameter
284    pub fn ix(&self) -> usize { self.ix }
285    /// Get the region of this parameter
286    pub fn region(&self) -> &WeakRegion { &self.region }
287}
288
289impl PartialEq for Parameter {
290    fn eq(&self, other: &Parameter) -> bool {
291        self.region == other.region && self.ix == other.ix
292    }
293}
294
295impl Eq for Parameter {}
296
297#[cfg(test)]
298pub mod tests {
299    use super::*;
300    use crate::value::primitive::{Unit, logical::{Unary, Bool}};
301    use crate::value::expr::SexprArgs;
302    use smallvec::smallvec;
303    use std::convert::TryInto;
304
305    #[test]
306    fn nested_region_construction() {
307        let region = Region::new();
308        let nested_region = Region::new_in(region.downgrade());
309        let other_region = Region::new();
310        let null = WeakRegion::default();
311        assert_eq!(nested_region.parent, region.downgrade());
312        assert_eq!(nested_region.this(), nested_region.downgrade());
313        assert_eq!(region.this(), region.downgrade());
314        assert_eq!(region.parent, WeakRegion::default());
315        assert_eq!(region.depth, 1);
316        assert_eq!(other_region.parent, WeakRegion::default());
317        assert_eq!(other_region.depth, 1);
318        assert_eq!(nested_region.depth, 2);
319        assert_eq!(region, region);
320        assert_eq!(nested_region, nested_region);
321        assert_eq!(other_region, other_region);
322        assert_ne!(region, other_region);
323        assert_ne!(region, nested_region);
324        assert_ne!(other_region, nested_region);
325        assert_eq!(region.partial_cmp(&nested_region), Some(Ordering::Greater));
326        assert_eq!(region.partial_cmp(&null), Some(Ordering::Less));
327        assert_eq!(region.partial_cmp(&other_region), None);
328        assert_eq!(nested_region.partial_cmp(&region), Some(Ordering::Less));
329        assert_eq!(nested_region.partial_cmp(&other_region), None);
330    }
331
332    #[test]
333    fn parameters_are_added_to_region() {
334        let region = Region::new();
335        let unit_ty = ValId::from(Unit);
336        let bool_ty = ValId::from(Bool);
337        let mut params = region.params_mut();
338        assert_eq!(params.arr().len(), 0);
339        let tys = [unit_ty.clone(), bool_ty.clone(), unit_ty.clone()];
340        for (i, ty) in tys.iter().enumerate() {
341            assert_eq!(i, params.add_with_ty(ty.clone()).expect("Unfused region"))
342        }
343        assert_eq!(params.arr().len(), tys.len());
344        let weak = region.downgrade();
345        for (i, a) in params.arr().iter().enumerate() {
346            let data = a.data();
347            match &data.value {
348                ValueEnum::Parameter(p) => {
349                    assert_eq!(p.ix, i);
350                    assert_eq!(p.region, weak);
351                    assert_eq!(p.ty, tys[i])
352                },
353                v => panic!("Bad parameter value {} @ params[{}]", v, i)
354            }
355        }
356
357        let not_args = SexprArgs(
358            smallvec![params.arr()[1].clone(), Unary::Not.into()]
359        );
360        let not: ValId = not_args.try_into().expect("This is a valid expression");
361        {
362            let not = not.data();
363            assert_eq!(
364                not.region, weak,
365                "Wrong region for (not #parameter): is null = {}",
366                not.region == WeakRegion::default()
367            );
368        }
369    }
370}
rain_lang/graph/region.rs

rain_lang/graph/
region.rs
