dugong 0.8.0

Dagre-compatible graph layout algorithms (port of dagrejs/dagre).
Documentation 
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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172

//! Owner-local work control for the Dagre layout kernel.

/// Neutral failure returned by the layout kernel or a caller-provided work control.
///
/// Dugong deliberately does not depend on renderer resource-policy types. Callers can map an
/// interruption to their own cancellation or resource error, while arithmetic overflow remains a
/// deterministic resource failure even without a configured ceiling.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
#[non_exhaustive]
pub enum WorkError {
    Interrupted,
    ArithmeticOverflow,
}

impl std::fmt::Display for WorkError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.write_str(match self {
            Self::Interrupted => "layout work was interrupted by the caller",
            Self::ArithmeticOverflow => "layout work arithmetic overflowed",
        })
    }
}

impl std::error::Error for WorkError {}

/// Caller-owned work control for one Dugong layout invocation.
///
/// Implementations must accept a complete tranche or reject it without advancing their budget.
pub trait WorkControl {
    fn charge(&mut self, units: usize) -> Result<(), WorkError>;
}

/// Checked no-op control used by the compatibility [`crate::layout`] entry point.
#[derive(Debug, Default, Clone, Copy)]
pub struct NoopWorkControl;

impl WorkControl for NoopWorkControl {
    fn charge(&mut self, _units: usize) -> Result<(), WorkError> {
        Ok(())
    }
}

pub(crate) fn checked_add(left: usize, right: usize) -> Result<usize, WorkError> {
    left.checked_add(right).ok_or(WorkError::ArithmeticOverflow)
}

pub(crate) fn checked_mul(left: usize, right: usize) -> Result<usize, WorkError> {
    left.checked_mul(right).ok_or(WorkError::ArithmeticOverflow)
}

pub(crate) fn ceil_log2(value: usize) -> usize {
    if value <= 1 {
        0
    } else {
        usize::BITS as usize - (value - 1).leading_zeros() as usize
    }
}

pub(crate) fn checked_n_log_n(value: usize) -> Result<usize, WorkError> {
    checked_mul(value, ceil_log2(value).max(1))
}

/// Conservative comparison-height work for ordered object-key map mutations.
///
/// Graphlib uses ordered maps for JavaScript array-index keys. Each insertion or removal is
/// logarithmic in the maximum live numeric-key population; the extra level covers the root/leaf
/// visit for singleton and empty maps instead of treating those mutations as free.
pub(crate) fn checked_ordered_key_updates(
    entry_bound: usize,
    update_count: usize,
) -> Result<usize, WorkError> {
    let height = checked_add(ceil_log2(entry_bound), 1)?;
    checked_mul(update_count, height)
}

/// Conservative work for Graphlib's construction-only unparented assignment batch.
///
/// The batch builds and validates a union-by-rank forest from `existing_parent_count` live links,
/// then replays every first assignment. Ordinary child buckets are covered by the linear tranche
/// and amortized compaction; array-index children additionally remove from one ordered root map and
/// insert into one ordered parent map. Keeping the existing-link count separate from allocated node
/// slots avoids charging an empty freshly copied forest as though every slot already had a parent.
pub(crate) fn checked_unparented_parent_batch_work(
    node_slots: usize,
    existing_parent_count: usize,
    assignment_count: usize,
    numeric_assignment_count: usize,
) -> Result<usize, WorkError> {
    if assignment_count == 0 {
        return Ok(0);
    }
    let find_work = checked_mul(checked_add(ceil_log2(node_slots), 1)?, 4)?;
    let forest_items = checked_add(existing_parent_count, assignment_count)?;
    let union_work = checked_mul(forest_items, find_work)?;
    let linear_work = checked_add(
        checked_mul(node_slots, 6)?,
        checked_mul(assignment_count, 2)?,
    )?;
    let ordered_updates = checked_mul(numeric_assignment_count, 2)?;
    let ordered_work = checked_ordered_key_updates(node_slots, ordered_updates)?;
    checked_add(checked_add(union_work, linear_work)?, ordered_work)
}

/// Conservative work for Graphlib's independent-leaf parent batch.
///
/// Each assignment pays sixteen linear units for live-slot checks, leaf/parent-role validation,
/// two hash-set updates, snapshot growth, and the later root removal, parent write, and child-bucket
/// insertion. Numeric child IDs additionally pay the ordered-map comparison bound for the root and
/// parent updates.
pub(crate) fn checked_unparented_leaf_parent_batch_work(
    node_slots: usize,
    assignment_count: usize,
    numeric_assignment_count: usize,
) -> Result<usize, WorkError> {
    if assignment_count == 0 {
        return Ok(0);
    }
    let linear_work = checked_mul(assignment_count, 16)?;
    let ordered_updates = checked_mul(numeric_assignment_count, 2)?;
    let ordered_work = checked_ordered_key_updates(node_slots, ordered_updates)?;
    checked_add(linear_work, ordered_work)
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn checked_work_arithmetic_fails_closed() {
        assert_eq!(
            checked_add(usize::MAX, 1),
            Err(WorkError::ArithmeticOverflow)
        );
        assert_eq!(
            checked_mul(usize::MAX, 2),
            Err(WorkError::ArithmeticOverflow)
        );
    }

    #[test]
    fn logarithmic_work_is_monotonic_and_checked() {
        assert_eq!(ceil_log2(0), 0);
        assert_eq!(ceil_log2(1), 0);
        assert_eq!(ceil_log2(2), 1);
        assert_eq!(ceil_log2(3), 2);
        assert_eq!(ceil_log2(4), 2);
        assert_eq!(checked_n_log_n(4), Ok(8));
        assert_eq!(checked_ordered_key_updates(0, 3), Ok(3));
        assert_eq!(checked_ordered_key_updates(1, 3), Ok(3));
        assert_eq!(checked_ordered_key_updates(4, 3), Ok(9));
        assert_eq!(checked_unparented_parent_batch_work(0, 0, 0, 0), Ok(0));
        assert_eq!(checked_unparented_parent_batch_work(4, 3, 0, 0), Ok(0));
        assert_eq!(checked_unparented_parent_batch_work(4, 0, 3, 0), Ok(66));
        assert_eq!(checked_unparented_parent_batch_work(4, 0, 3, 2), Ok(78));
        assert_eq!(checked_unparented_parent_batch_work(4, 3, 3, 0), Ok(102));
        assert_eq!(checked_unparented_leaf_parent_batch_work(4, 0, 0), Ok(0));
        assert_eq!(checked_unparented_leaf_parent_batch_work(4, 3, 0), Ok(48));
        assert_eq!(checked_unparented_leaf_parent_batch_work(4, 3, 2), Ok(60));
        assert_eq!(
            checked_ordered_key_updates(usize::MAX, usize::MAX),
            Err(WorkError::ArithmeticOverflow)
        );
        assert_eq!(
            checked_unparented_parent_batch_work(usize::MAX, usize::MAX, usize::MAX, usize::MAX,),
            Err(WorkError::ArithmeticOverflow)
        );
        assert_eq!(
            checked_unparented_leaf_parent_batch_work(usize::MAX, usize::MAX, usize::MAX),
            Err(WorkError::ArithmeticOverflow)
        );
    }
}