Chasesomero/pijul - Change FSJBK6CUVMSKZVLD7SWC4L53GMPUKIQESWDBFMV5GLX43WBUZDPQC

Fixing the stitching in cyclic conflict

Stitching is when we use pseudo-edges to reconnect alive parts which may have been separated by a deletion. One of our test cases showed that this wasn't working well in the case of cyclic conflicts.

That particular test case is probably the worst thing imaginable, since it manages to create a cyclic + zombie conflict between the empty vertices used to solve regular order conflicts.

Created by pmeunier on January 18, 2026

FSJBK6CUVMSKZVLD7SWC4L53GMPUKIQESWDBFMV5GLX43WBUZDPQC

Dependencies

In channels

main

Change contents

Insertion in libpijul/src/tests/conflict.rs at line 2538 [2.357372]

[2.433351]

[7.78092]


    {
        let txn = txn.read();
        let graph = channel_bob.read();
        let mut f = std::fs::File::create("bob0").unwrap();
        crate::pristine::debug(&*txn, &txn.graph(&*graph), &mut f).unwrap();
    }

Insertion in libpijul/src/tests/conflict.rs at line 2546 [2.357372]

[7.78172]

[8.10475]


    {
        let txn = txn.read();
        let graph = channel_bob.read();
        let mut f = std::fs::File::create("bob1").unwrap();
        crate::pristine::debug(&*txn, &txn.graph(&*graph), &mut f).unwrap();
    }

Replacement in libpijul/src/lib.rs at line 84 [2.717381]

B:BD[2.720384] → [2.720384:720536]

impl MutTxnTExt for pristine::sanakirja::MutTxn<()> {}
impl TxnTExt for pristine::sanakirja::MutTxn<()> {}
impl TxnTExt for pristine::sanakirja::Txn {}

[2.720384]

[2.720536]

impl<
        T: ::sanakirja::LoadPage<Error = ::sanakirja::Error>
            + ::sanakirja::RootPageMut
            + ::sanakirja::Commit
            + ::sanakirja::AllocPage<Error = ::sanakirja::Error>,
    > MutTxnTExt for pristine::sanakirja::GenericTxn<T>
{
}
impl<T: ::sanakirja::LoadPage<Error = ::sanakirja::Error> + ::sanakirja::RootPage> TxnTExt
    for pristine::sanakirja::GenericTxn<T>
{
}

Replacement in libpijul/src/diff/delete.rs at line 133 [2.805350]
B:BD[2.809674] → [5.116879:116894]
```
            )?
```
[2.809674]
[3.1308]
```
            )?;
```

Replacement in libpijul/src/apply.rs at line 602 [2.944089]

B:BD[12.821] → [13.7152:7199]

∅:D[13.7199] → [12.821:1066]

B:BD[12.821] → [12.821:1066]

                debug!("descendant {:#?}", r);
                put_graph_with_rev(
                    txn,
                    channel,
                    EdgeFlags::PSEUDO,
                    elt.last_alive,
                    *r,
                    ChangeId::ROOT,
                )?;

[12.821]

[12.1066]

                debug!("put_pseudo, descendant {:?} {:?}", elt.last_alive, r);
                // If we aren't in a direct cycle, reconnect.
                if elt.last_alive != *r {
                    put_graph_with_rev(
                        txn,
                        channel,
                        EdgeFlags::PSEUDO,
                        elt.last_alive,
                        *r,
                        ChangeId::ROOT,
                    )?;
                }
            }
            if !elt.is_alive() {
                continue;

Replacement in libpijul/src/apply.rs at line 626 [2.944089]

B:BD[13.7529] → [13.7529:8249]

                        // We need to reconnect, and we can do it now
                        // since we won't have a chance to visit that
                        // edge (because non-PARENT edge we are
                        // inserting now starts from a vertex that is
                        // on the path, which means we've already
                        // pushed all its children onto the stack.).
                        put_graph_with_rev(
                            txn,
                            channel,
                            EdgeFlags::PSEUDO,
                            v.vertex,
                            elt.vertex,
                            ChangeId::ROOT,
                        )?;

[13.7529]

[13.8249]

                        if v.vertex != elt.vertex {
                            // We need to reconnect, and we can do it now
                            // since we won't have a chance to visit that
                            // edge (because non-PARENT edge we are
                            // inserting now starts from a vertex that is
                            // on the path, which means we've already
                            // pushed all its children onto the stack.).
                            debug!("alive, put_pseudo {:?} {:?}", v.vertex, elt.vertex);
                            put_graph_with_rev(
                                txn,
                                channel,
                                EdgeFlags::PSEUDO,
                                v.vertex,
                                elt.vertex,
                                ChangeId::ROOT,
                            )?;
                        }

Replacement in libpijul/src/apply.rs at line 712 [2.944089]

B:BD[12.2810] → [12.2810:2971]

                        put_graph_with_rev(
                            txn,
                            channel,
                            EdgeFlags::PSEUDO,

[12.2810]

[13.8605]

                        debug!(
                            "put_pseudo, alive 2, {:?} {:?}",

Replacement in libpijul/src/apply.rs at line 715 [2.944089]

∅:D[13.8647] → [12.3015:3138]

B:BD[12.3015] → [12.3015:3138]

                            stack[len - 1].vertex,
                            ChangeId::ROOT,
                        )?;

[13.8647]

[12.3138]

                            stack[len - 1].vertex
                        );
                        debug!("{:?}", stack);
                        let edge = Edge {
                            dest: stack[len - 1].vertex.start_pos(),
                            flag: EdgeFlags::empty(),
                            introduced_by: ChangeId::ROOT,
                        };
                        match txn.get_graph(channel, &v.last_alive, Some(&edge.into()))? {
                            Some(e) if e.dest() == edge.dest && e.flag() == EdgeFlags::BLOCK => {}
                            _ => {
                                put_graph_with_rev(
                                    txn,
                                    channel,
                                    EdgeFlags::PSEUDO,
                                    v.last_alive,
                                    stack[len - 1].vertex,
                                    ChangeId::ROOT,
                                )?;
                            }
                        }

Replacement in libpijul/src/apply.rs at line 776 [2.944089]
B:BD[11.7127] → [11.7127:7137]
```
        {
```
[11.7127]
[11.7137]
```
        if log_enabled!(log::Level::Debug) {
```

Insertion in libpijul/src/apply.rs at line 1125 [2.944089]

[4.27459]

                debug!("put_pseudo {:?} {:?}", next, current);

Replacement in libpijul/src/apply.rs at line 1250 [2.944089]

B:BD[9.583] → [9.583:639]

            .sample_iter(rand::distributions::Standard)

[9.583]

[9.639]

            .sample_iter(rand::distr::StandardUniform)

Insertion in libpijul/src/apply/vertex.rs at line 37 [6.90459]

[6.91421]

[10.2117]

        // Collect the vertices in the up context (we only have their
        // end positions at this point), also collecting the deleted
        // ones (they're part of a conflict if they're unknown to the
        // patch we're applying).

Insertion in libpijul/src/apply/vertex.rs at line 50 [6.90459]
[6.91778]
[6.91778]
```
        // Not the same here, we're only collecting down contexts.
```
Insertion in libpijul/src/apply/vertex.rs at line 61 [6.90459]
[6.92181]
[6.92181]
```
            // Mark the delete/insert conflict, if any.
```
Insertion in libpijul/src/apply/vertex.rs at line 66 [6.90459]
[6.92333]
[6.92333]
```
        // And put the edge into the graph.
```