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
//! The JOIN's mechanism: [`Join`], and the two memberships a fused face chooses between.
use HashMap;
/// Where each root already sits in the fold's accumulator — the join's one moving part.
///
/// # Why the mechanism is a parameter, and not a `HashMap` written into the fold
///
/// It is a BOUNDS choice on the ROOT type, which is the same choice [`Seen`](crate::Seen) already
/// carries for the key type one stage up. The dedup ruling settled it there — `dedup(hash)` wants
/// `Hash + Eq` and `dedup(eq)` asks only `PartialEq`, so *a key that cannot hash is retrievable* —
/// and a root key is a PREFIX of such a key, built out of the same segments, so it inherits the
/// property rather than escaping it. A fold that hardcoded a hash map would make a graph whose roots
/// do not hash unfusable while every one of its members retrieves.
///
/// | mechanism | what the root must satisfy |
/// |---|---|
/// | [`HashJoin`] | [`Hash`](core::hash::Hash) + [`Eq`] |
/// | [`EqJoin`] | [`PartialEq`] |
///
/// # The contract, which the fold depends on and cannot check
///
/// An implementor assigns indices DENSELY FROM ZERO in admission order: the first root it admits is
/// `0`, the next `1`, and a root it has already admitted answers with the index it was given. So
/// when [`place`](Self::place) answers `None`, the accumulator's current length IS the index that
/// root just took, and the fold pushes there.
///
/// Both shipped implementors get that for free by deriving the index from their own length, which
/// is why the contract is stated rather than defended: a mechanism that assigned indices some other
/// way would have to go out of its way to.
/// The join through a [`HashMap`] — one hash and one bucket probe per contribution.
///
/// What every emitted root key satisfies today, and the mechanism a fused face takes unless its root
/// cannot hash.
;
/// The join through a list walked by field-wise equality — quadratic in the number of DISTINCT
/// ROOTS, and that is stated rather than hidden.
///
/// The bound it asks is [`PartialEq`] alone, which is the whole point: a root carrying a float
/// coordinate or a foreign type with no `Hash` impl fuses through here and through nothing else. The
/// distinct-root count is bounded by the members' intake ceilings rather than by the corpus, so the
/// walk is bounded too — but it is the escape rather than the default, exactly as
/// [`EqSeen`](crate::EqSeen) is.
;