lib.rs

#![feature(question_mark)]

use std::{cmp, ops};
use std::cell::Cell;

/// The condition graph.
///
/// Each edge represents an outlives relation between two regions.
pub struct Graph {
    /// The nodes.
    nodes: Vec<Node>,
}

impl Graph {
    /// Assert an outlives relation.
    pub fn outlives(&mut self, a: usize, b: usize) {
        self.nodes[a].outlives.push(Cell::new(b));
    }

    /// Add a new lifetime to the graph nodes.
    pub fn add(&mut self, lifetime: Option<Lifetime>) -> usize {
        self.nodes.push(Node {
            outlives: Vec::new(),
            lifetime: Cell::new(lifetime),
        });

        self.nodes.len() - 1
    }

    /// Finish the graph building.
    pub fn finish(self) -> RegionCtx {
        RegionCtx {
            graph: self,
        }
    }
}

/// The region context.
///
/// This is used for inferring the region data.
pub struct RegionCtx {
    graph: Graph,
}

impl RegionCtx {
    /// Infer a lifetime.
    pub fn get_lifetime(&self, n: usize) -> Option<Lifetime> {
        // To avoid cycles.
        if let Some(x) = self.graph.nodes[n].lifetime.get() {
            return Some(x);
        }

        let mut extend = None;
        for i in &self.graph.nodes[n].outlives {
            let lt = if let Some(x) = self.get_lifetime(i.get()) {
                x
            } else {
                break;
            };

            if let Some(x) = extend {
                // Extend the region.
                extend = Some(lt + x);
            } else {
                extend = Some(lt);
            }
        }

        // Cache the result.
        self.graph.nodes[n].lifetime.set(extend);
        extend
    }
}

/// A region.
struct Node {
    /// The regions it outlives.
    outlives: Vec<Cell<usize>>,
    /// The lifetime.
    lifetime: Cell<Option<Lifetime>>,
}

/// A lifetime (token span).
#[derive(PartialEq, Clone, Copy)]
pub struct Lifetime {
    pub start: u64,
    pub end: u64,
}

impl cmp::PartialOrd for Lifetime {
    fn partial_cmp(&self, other: &Lifetime) -> Option<cmp::Ordering> {
        // The outlives relation.
        if other.end < self.end && other.start > self.start {
            Some(cmp::Ordering::Less)
        } else if self == other {
            Some(cmp::Ordering::Equal)
        } else if other.end > self.end && other.start < self.start {
            Some(cmp::Ordering::Greater)
        } else {
            None
        }
    }
}

impl ops::Add for Lifetime {
    type Output = Lifetime;

    fn add(self, rhs: Lifetime) -> Lifetime {
        // Addition, as explained in the blog post.
        Lifetime {
            start: cmp::min(self.start, rhs.start),
            end: cmp::max(self.end, rhs.end),
        }
    }
}