dblsaiko/pijul - Change RSFUX6MLPHII3DRELHN62DOJCHFCDNKSRMWJDSFGTWN5S4RJVSSQC

Correct find_alive cache system

Created by pmeunier on January 14, 2022

RSFUX6MLPHII3DRELHN62DOJCHFCDNKSRMWJDSFGTWN5S4RJVSSQC

Dependencies

In channels

main

Change contents

Deletion in libpijul/src/missing_context.rs at line 6 [8.696460]
B:BD[6.83368] → [7.0:24]
```
use std::cell::RefCell;
```
Deletion in libpijul/src/missing_context.rs at line 7 [8.696460]
B:BD[8.696664] → [7.25:42]
```
use std::rc::Rc;
```

Replacement in libpijul/src/missing_context.rs at line 83 [8.696460]

B:BD[7.197] → [5.0:44]

∅:D[5.44] → [7.237:275]

B:BD[7.237] → [7.237:275]

∅:D[7.275] → [8.698423:698527]

∅:D[9.9555] → [8.698423:698527]

B:BD[8.698423] → [8.698423:698527]

    let mut alive = alive.borrow().clone();
    debug!("files = {:?}", ws.files);
    crate::TIMERS.lock().unwrap().find_alive += now.elapsed();
    ws.load_graph(txn, channel, inode)?;

[7.197]

[8.698527]

    if let Some(alive) = alive {
        let mut alive = alive.clone();
        debug!("files = {:?}", ws.files);
        crate::TIMERS.lock().unwrap().find_alive += now.elapsed();
        ws.load_graph(txn, channel, inode)?;

Replacement in libpijul/src/missing_context.rs at line 89 [8.696460]

B:BD[8.698528] → [8.698528:698590]

B:BD[8.698652] → [8.698652:698670]

B:BD[8.698670] → [9.9556:9619]

∅:D[9.9619] → [8.698731:698828]

B:BD[8.698731] → [8.698731:698828]

B:BD[8.698828] → [5.45:73]

∅:D[5.73] → [8.698856:698931]

∅:D[7.305] → [8.698856:698931]

B:BD[8.698856] → [8.698856:698931]

    debug!("repair_missing_up_context, alive = {:?}", alive);
    for &d in d {
        if let Some((graph, vids)) = ws.graphs.0.get(&inode) {
            crate::alive::remove_redundant_parents(
                graph,
                vids,
                &mut alive,
                &mut ws.covered_parents,
                d,
            );

[8.698528]

[8.698931]

        debug!("repair_missing_up_context, alive = {:?}", alive);
        for &d in d {
            if let Some((graph, vids)) = ws.graphs.0.get(&inode) {
                crate::alive::remove_redundant_parents(
                    graph,
                    vids,
                    &mut alive,
                    &mut ws.covered_parents,
                    d,
                );
            }
            repair_regular_up(txn, channel, &alive, d, EdgeFlags::PSEUDO)?;

Replacement in libpijul/src/missing_context.rs at line 102 [8.696460]

B:BD[8.698941] → [5.74:146]

        repair_regular_up(txn, channel, &alive, d, EdgeFlags::PSEUDO)?;

[8.698941]

[8.699912]

    } else {
        debug!("repair_missing_up_context: {:?} is alive", c);

Replacement in libpijul/src/missing_context.rs at line 144 [8.696460]

B:BD[7.574] → [5.147:191]

∅:D[5.191] → [7.614:649]

B:BD[7.614] → [7.614:649]

∅:D[7.649] → [8.701033:701137]

B:BD[8.701033] → [8.701033:701137]

B:BD[8.701137] → [9.10294:10353]

B:BD[9.10353] → [5.192:269]

∅:D[5.269] → [8.701271:701277]

∅:D[7.728] → [8.701271:701277]

B:BD[8.701271] → [8.701271:701277]

    let mut alive = alive.borrow().clone();
    debug!("alive = {:?}", alive);
    crate::TIMERS.lock().unwrap().find_alive += now.elapsed();
    ws.load_graph(txn, channel, inode)?;
    if let Some((graph, vids)) = ws.graphs.0.get(&inode) {
        crate::alive::remove_redundant_children(graph, vids, &mut alive, c);
    }

[7.574]

[8.701277]

    if let Some(alive) = alive {
        let mut alive = alive.clone();
        debug!("alive = {:?}", alive);
        crate::TIMERS.lock().unwrap().find_alive += now.elapsed();
        ws.load_graph(txn, channel, inode)?;
        if let Some((graph, vids)) = ws.graphs.0.get(&inode) {
            crate::alive::remove_redundant_children(graph, vids, &mut alive, c);
        }

Replacement in libpijul/src/missing_context.rs at line 153 [8.696460]

B:BD[8.701278] → [8.701278:701379]

    if !alive.is_empty() {
        debug!("repair_missing_down_context alive = {:#?}", alive);
    }

[8.701278]

[8.701379]

        if !alive.is_empty() {
            debug!("repair_missing_down_context alive = {:#?}", alive);
        }

Replacement in libpijul/src/missing_context.rs at line 157 [8.696460]

B:BD[8.701380] → [8.701380:701398]

B:BD[8.701398] → [9.10354:10501]

∅:D[9.10501] → [8.701621:701647]

B:BD[8.701621] → [8.701621:701647]

    for &d in d {
        for &desc in alive.iter() {
            if d == desc {
                info!("repair_missing_down_context, alive: {:?} == {:?}", d, desc);
                continue;

[8.701380]

[8.701647]

        for &d in d {
            for &desc in alive.iter() {
                if d == desc {
                    info!("repair_missing_down_context, alive: {:?} == {:?}", d, desc);
                    continue;
                }
                debug!("repair_missing_down {:?} {:?}", d, desc);
                put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, d, desc, ChangeId::ROOT)?;

Deletion in libpijul/src/missing_context.rs at line 166 [8.696460]

B:BD[8.701661] → [9.10502:10564]

B:BD[9.10564] → [10.89461:89552]

            debug!("repair_missing_down {:?} {:?}", d, desc);
            put_graph_with_rev(txn, channel, EdgeFlags::PSEUDO, d, desc, ChangeId::ROOT)?;

Insertion in libpijul/src/missing_context.rs at line 167 [8.696460]
[8.701835]
[8.701835]
```
    } else {
        debug!("repair_missing_down: {:?} is alive", c);
```

Replacement in libpijul/src/missing_context.rs at line 377 [8.696460]

B:BD[9.13269] → [7.729:1005]

    alive_down_cache: HashMap<Vertex<ChangeId>, Rc<RefCell<HashSet<Vertex<ChangeId>>>>>,
    alive_up_cache: HashMap<
        Vertex<ChangeId>,
        (
            Rc<RefCell<HashSet<Vertex<ChangeId>>>>,
            Rc<RefCell<HashSet<Vertex<ChangeId>>>>,
        ),
    >,

[9.13269]

[8.707180]

    alive_down_cache: HashMap<Vertex<ChangeId>, Option<HashSet<Vertex<ChangeId>>>>,
    alive_up_cache:
        HashMap<Vertex<ChangeId>, (Option<HashSet<Vertex<ChangeId>>>, HashSet<Vertex<ChangeId>>)>,

Replacement in libpijul/src/missing_context.rs at line 523 [8.696460]

B:BD[8.711431] → [7.1006:1091]

            let alive = find_alive_down(txn, channel, p, &mut ws.alive_down_cache)?;

[8.711431]

[7.1091]

            let alive = find_alive_down(txn, channel, p, &mut ws.alive_down_cache)?.clone();

Replacement in libpijul/src/missing_context.rs at line 531 [8.696460]

B:BD[7.1275] → [7.1275:1309]

                &*alive.borrow(),

[7.1275]

[7.1309]

                alive.iter().flat_map(|t| t.iter()),

Insertion in libpijul/src/fs.rs at line 881 [8.737429]

[4.554]

                debug!("name_dest = {:?}", name_dest);

Insertion in libpijul/src/fs.rs at line 960 [8.737429]
[11.2747]
[2.0]
```
        debug!("inode_vertex = {:?}", inode_vertex);
```
Insertion in libpijul/src/fs.rs at line 993 [8.737429]
[10.114634]
[10.114634]
```
            debug!("next = {:?}", next);
```
Insertion in libpijul/src/fs.rs at line 1005 [8.737429]
[8.762693]
[8.762693]
```
                        debug!("youngest");
```

Deletion in libpijul/src/find_alive.rs at line 3 [8.763306]

B:BD[7.1357] → [7.1357:1452]

use std::cell::RefCell;
use std::rc::Rc;
type Alive = Rc<RefCell<HashSet<Vertex<ChangeId>>>>;

Replacement in libpijul/src/find_alive.rs at line 4 [8.763306]

B:BD[12.32358] → [10.114846:114891]

pub(crate) fn find_alive_down<T: GraphTxnT>(

[12.32358]

[8.763561]

/// The following is an unrolled DFS, where each alive vertex is
/// inserted into each "alive set" along the current path (which is
/// recognised by looking at the visited vertices on the stack).
pub(crate) fn find_alive_down<'a, T: GraphTxnT>(

Replacement in libpijul/src/find_alive.rs at line 11 [8.763306]

B:BD[8.763631] → [7.1453:1637]

    cache: &mut HashMap<Vertex<ChangeId>, Alive>,
) -> Result<Alive, BlockError<T::GraphError>> {
    let mut stack = vec![SerializedEdge::empty(vertex0.start_pos(), ChangeId::ROOT)];

[8.763631]

[6.85243]

    cache: &'a mut HashMap<Vertex<ChangeId>, Option<HashSet<Vertex<ChangeId>>>>,
) -> Result<&'a Option<HashSet<Vertex<ChangeId>>>, BlockError<T::GraphError>> {
    let mut stack: Vec<(_, Option<HashSet<Vertex<ChangeId>>>)> = vec![(
        SerializedEdge::empty(vertex0.start_pos(), ChangeId::ROOT),
        None,
    )];

Replacement in libpijul/src/find_alive.rs at line 18 [8.763306]

B:BD[6.85285] → [7.1638:1733]

∅:D[13.139] → [14.134265:134306]

∅:D[7.1733] → [14.134265:134306]

B:BD[8.764007] → [14.134265:134306]

    let alive = Rc::new(RefCell::new(HashSet::new()));
    while let Some(elt) = stack.pop() {
        if !visited.insert(elt.dest()) {

[6.85285]

[8.764046]

    while let Some((elt, alive)) = stack.pop() {
        if let Some(alive) = alive {
            // We've gone through all the descendants, put this in the
            // cache.
            let vertex = txn.find_block(&channel, elt.dest())?;
            cache.insert(*vertex, Some(alive.clone()));
            if stack.is_empty() {
                // Done!
                return Ok(cache.get(&vertex0).unwrap());
            }

Insertion in libpijul/src/find_alive.rs at line 29 [8.763306]

[8.764068]

        } else {
            if !visited.insert(elt.dest()) {
                continue;
            }
            stack.push((elt, Some(HashSet::new())));

Replacement in libpijul/src/find_alive.rs at line 37 [8.763306]

B:BD[7.1779] → [7.1779:1846]

            alive.borrow_mut().extend(c.borrow().iter().cloned());

[7.1779]

[7.1846]

            for st in stack.iter_mut() {
                if let Some(ref mut st) = st.1 {
                    if let Some(c) = c {
                        st.extend(c.iter().cloned());
                    } else {
                        st.insert(*vertex);
                    }
                }
            }

Deletion in libpijul/src/find_alive.rs at line 47 [8.763306]
B:BD[7.1868] → [7.1868:1935]
```
        } else {
            cache.insert(*vertex, alive.clone());
```

Replacement in libpijul/src/find_alive.rs at line 62 [8.763306]

B:BD[13.184] → [7.1946:2006]

∅:D[7.2006] → [15.3716:3758]

B:BD[13.235] → [15.3716:3758]

                        assert!(alive.borrow().is_empty());
                        return Ok(alive);

[13.184]

[13.276]

                        // vertex0 is alive.
                        stack.truncate(elt_index);
                        let (_, alive) = stack.pop().unwrap();
                        let alive = alive.unwrap();
                        assert!(alive.is_empty());
                        cache.insert(vertex0, None);
                        return Ok(cache.get(&vertex0).unwrap());

Replacement in libpijul/src/find_alive.rs at line 70 [8.763306]

B:BD[13.305] → [7.2007:2067]

                        alive.borrow_mut().insert(*vertex);

[13.305]

[13.352]

                        // vertex is alive, insert it into all the
                        // alive sets on the current DFS path
                        // (including `vertex`).
                        for st in stack.iter_mut() {
                            if let Some(ref mut st) = st.1 {
                                st.insert(*vertex);
                            }
                        }

Replacement in libpijul/src/find_alive.rs at line 83 [8.763306]
B:BD[5.469] → [5.469:500]
```
                stack.push(*v)
```
[5.469]
[8.764996]
```
                stack.push((*v, None))
```
Replacement in libpijul/src/find_alive.rs at line 87 [8.763306]
B:BD[8.765119] → [8.765119:765133]
```
    Ok(alive)
```
[8.765119]
[8.765133]
```
    unreachable!()
```
Replacement in libpijul/src/find_alive.rs at line 90 [8.763306]
B:BD[12.32414] → [3.4703:4739]
```
pub fn find_alive_up<T: GraphTxnT>(
```
[12.32414]
[8.765228]
```
pub fn find_alive_up<'a, T: GraphTxnT>(
```

Replacement in libpijul/src/find_alive.rs at line 96 [8.763306]

B:BD[9.15653] → [7.2096:2203]

    cache: &mut HashMap<Vertex<ChangeId>, (Alive, Alive)>,
) -> Result<Alive, BlockError<T::GraphError>> {

[9.15653]

[7.2203]

    cache: &'a mut HashMap<
        Vertex<ChangeId>,
        (Option<HashSet<Vertex<ChangeId>>>, HashSet<Vertex<ChangeId>>),
    >,
) -> Result<&'a Option<HashSet<Vertex<ChangeId>>>, BlockError<T::GraphError>> {

Replacement in libpijul/src/find_alive.rs at line 102 [8.763306]

B:BD[7.2247] → [7.2247:2366]

∅:D[7.2366] → [13.496:580]

B:BD[6.85366] → [13.496:580]

    let alive = Rc::new(RefCell::new(HashSet::default()));
    let files_ = Rc::new(RefCell::new(HashSet::default()));
    let mut stack = vec![SerializedEdge::empty(vertex0.end_pos(), ChangeId::ROOT)];

[7.2247]

[6.85367]

    let mut stack: Vec<(
        _,
        Option<(HashSet<Vertex<ChangeId>>, HashSet<Vertex<ChangeId>>)>,
    )> = vec![(
        SerializedEdge::empty(vertex0.end_pos(), ChangeId::ROOT),
        None,
    )];

Replacement in libpijul/src/find_alive.rs at line 111 [8.763306]
B:BD[16.95] → [13.581:621]
```
    while let Some(elt) = stack.pop() {
```
[16.95]
[14.134913]
```
    while let Some((elt, alive)) = stack.pop() {
```

Replacement in libpijul/src/find_alive.rs at line 115 [8.763306]

B:BD[8.765801] → [14.134948:134989]

        if !visited.insert(elt.dest()) {

[8.765801]

[8.765840]

        if let Some((alive, files_)) = alive {
            let vertex = *txn.find_block_end(&channel, elt.dest())?;
            cache.insert(vertex, (Some(alive), files_));
            if stack.is_empty() {
                // Done!
                return Ok(&cache.get(&vertex0).unwrap().0);
            }

Replacement in libpijul/src/find_alive.rs at line 123 [8.763306]

B:BD[8.765862] → [8.765862:765872]

[8.765862]

[14.134990]

        } else {
            if !visited.insert(elt.dest()) {
                continue;
            }
            stack.push((elt, Some((HashSet::new(), HashSet::new()))));
        };

Replacement in libpijul/src/find_alive.rs at line 131 [8.763306]

B:BD[7.2408] → [7.2408:2927]

        let is_cached = if let Some((c, f)) = cache.get(&vertex) {
            alive.borrow_mut().extend(c.borrow().iter().cloned());
            files_.borrow_mut().extend(f.borrow().iter().cloned());
            files.extend(f.borrow().iter().cloned());
            // We're not continuing here, since the while loop below
            // needs to insert stuff into `files` and `files_`.
            true
        } else {
            cache.insert(vertex, (alive.clone(), files_.clone()));
            false
        };

[7.2408]

[8.765934]

        if let Some((c, d)) = cache.get(&vertex) {
            debug!("Cached: {:?} {:?}", c, d);
            for st in stack.iter_mut() {
                if let Some((ref mut al, ref mut f)) = st.1 {
                    if let Some(c) = c {
                        al.extend(c.iter().cloned());
                    } else {
                        al.insert(vertex);
                    }
                    f.extend(d.iter().cloned());
                    files.extend(d.iter().cloned());
                }
            }
            continue;
        }

Replacement in libpijul/src/find_alive.rs at line 149 [8.763306]

B:BD[8.766044] → [9.15707:15740]

        let mut is_file = false;

[8.766044]

[10.115205]

        let mut is_file = false; // Is this the "inode" vertex of a file?

Insertion in libpijul/src/find_alive.rs at line 162 [8.763306]

[14.135257]

                if vertex == vertex0 {
                    // vertex0 is alive.
                    stack.truncate(elt_index);
                    let (_, alive) = stack.pop().unwrap();
                    let (alive, _) = alive.unwrap();
                    assert!(alive.is_empty());
                    cache.insert(vertex0, (None, HashSet::new()));
                    return Ok(&cache.get(&vertex0).unwrap().0);
                }

Replacement in libpijul/src/find_alive.rs at line 176 [8.763306]

B:BD[10.115464] → [13.735:789]

                    if is_file && vertex != vertex0 {

[10.115464]

[7.2928]

                    if is_file {

Replacement in libpijul/src/find_alive.rs at line 178 [8.763306]

B:BD[7.2995] → [7.2995:3114]

                        alive.borrow_mut().insert(vertex);
                        files_.borrow_mut().insert(vertex);

[7.2995]

[9.16236]

                        for st in stack.iter_mut() {
                            if let Some((ref mut al, ref mut fi)) = st.1 {
                                al.insert(vertex);
                                fi.insert(vertex);
                            }
                        }

Replacement in libpijul/src/find_alive.rs at line 188 [8.763306]

B:BD[17.69] → [13.790:833]

B:BD[13.833] → [7.3115:3231]

                    if vertex != vertex0 {
                        debug!("is alive {:?}", vertex);
                        alive.borrow_mut().insert(vertex);

[17.69]

[9.16444]

                    debug!("is alive {:?}", vertex);
                    for st in stack.iter_mut() {
                        if let Some((ref mut st, _)) = st.1 {
                            st.insert(vertex);
                        }

Replacement in libpijul/src/find_alive.rs at line 199 [8.763306]

B:BD[14.135477] → [13.956:1006]

B:BD[13.1006] → [7.3232:3396]

                if is_file && vertex != vertex0 {
                    debug!("is alive {:?}", vertex);
                    alive.borrow_mut().insert(vertex);
                    files_.borrow_mut().insert(vertex);

[14.135477]

[9.16574]

                if is_file {
                    debug!("is pseudo-alive folder {:?}", vertex);
                    for st in stack.iter_mut() {
                        if let Some((ref mut al, ref mut fi)) = st.1 {
                            al.insert(vertex);
                            fi.insert(vertex);
                        }
                    }

Replacement in libpijul/src/find_alive.rs at line 210 [8.763306]

B:BD[9.16640] → [7.3397:3432]

∅:D[7.3432] → [13.1007:1038]

B:BD[8.768674] → [13.1007:1038]

            } else if !is_cached {
                stack.push(*v)

[9.16640]

[8.768704]

            } else {
                stack.push((*v, None))

Replacement in libpijul/src/find_alive.rs at line 216 [8.763306]
B:BD[8.768850] → [9.16685:16699]
```
    Ok(alive)
```
[8.768850]
[8.768873]
```
    unreachable!()
```