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

use std::{
    collections::hash_map,
    path::{self, Path, PathBuf},
    collections::{HashMap, HashSet},
};

use serde_derive::Serialize;
use log::warn;

#[derive(Debug, Serialize)]
struct PathMapNode<T> {
    value: T,
    children: HashSet<PathBuf>,
}

/// A map from paths to another type, like instance IDs, with a bit of
/// additional data that enables removing a path and all of its child paths from
/// the tree more quickly.
#[derive(Debug, Serialize)]
pub struct PathMap<T> {
    nodes: HashMap<PathBuf, PathMapNode<T>>,
}

impl<T> PathMap<T> {
    pub fn new() -> PathMap<T> {
        PathMap {
            nodes: HashMap::new(),
        }
    }

    pub fn get(&self, path: &Path) -> Option<&T> {
        self.nodes.get(path).map(|v| &v.value)
    }

    pub fn get_mut(&mut self, path: &Path) -> Option<&mut T> {
        self.nodes.get_mut(path).map(|v| &mut v.value)
    }

    pub fn entry<'a>(&'a mut self, path: PathBuf) -> Entry<'a, T> {
        Entry {
            internal: self.nodes.entry(path),
        }
    }

    pub fn insert(&mut self, path: PathBuf, value: T) {
        if let Some(parent_path) = path.parent() {
            if let Some(parent) = self.nodes.get_mut(parent_path) {
                parent.children.insert(path.to_path_buf());
            }
        }

        self.nodes.insert(path, PathMapNode {
            value,
            children: HashSet::new(),
        });
    }

    pub fn remove(&mut self, root_path: &Path) -> Option<T> {
        if let Some(parent_path) = root_path.parent() {
            if let Some(parent) = self.nodes.get_mut(parent_path) {
                parent.children.remove(root_path);
            }
        }

        let mut root_node = match self.nodes.remove(root_path) {
            Some(node) => node,
            None => return None,
        };

        let root_value = root_node.value;
        let mut to_visit: Vec<PathBuf> = root_node.children.drain().collect();

        while let Some(path) = to_visit.pop() {
            match self.nodes.remove(&path) {
                Some(mut node) => {
                    for child in node.children.drain() {
                        to_visit.push(child);
                    }
                },
                None => {
                    warn!("Consistency issue; tried to remove {} but it was already removed", path.display());
                },
            }
        }

        Some(root_value)
    }

    /// Traverses the route between `start_path` and `target_path` and returns
    /// the path closest to `target_path` in the tree.
    ///
    /// This is useful when trying to determine what paths need to be marked as
    /// altered when a change to a path is registered. Depending on the order of
    /// FS events, a file remove event could be followed by that file's
    /// directory being removed, in which case we should process that
    /// directory's parent.
    pub fn descend(&self, start_path: &Path, target_path: &Path) -> PathBuf {
        let relative_path = target_path.strip_prefix(start_path)
            .expect("target_path did not begin with start_path");
        let mut current_path = start_path.to_path_buf();

        for component in relative_path.components() {
            match component {
                path::Component::Normal(name) => {
                    let next_path = current_path.join(name);

                    if self.nodes.contains_key(&next_path) {
                        current_path = next_path;
                    } else {
                        return current_path;
                    }
                },
                _ => unreachable!(),
            }
        }

        current_path
    }
}

pub struct Entry<'a, T> {
    internal: hash_map::Entry<'a, PathBuf, PathMapNode<T>>,
}

impl<'a, T> Entry<'a, T> {
    pub fn or_insert(self, value: T) -> &'a mut T {
        &mut self.internal.or_insert(PathMapNode {
            value,
            children: HashSet::new(),
        }).value
    }
}

impl<'a, T> Entry<'a, T>
    where T: Default
{
    pub fn or_default(self) -> &'a mut T {
        &mut self.internal.or_insert(PathMapNode {
            value: Default::default(),
            children: HashSet::new(),
        }).value
    }
}