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
|
# Memory Region Description
This module bridges the abstract [`BitSlice`] region to real memory by
segmenting any bit-slice along its maybe-aliased and known-unaliased boundaries.
This segmentation applies to both bit-slice and ordinary-element views of
memory, and can be used to selectively remove alias restrictions or to enable
access to the underlying memory with ordinary types.
The four enums in this module all intentionally have the same variants by name
and shape, in order to maintain textual consistency.
## Memory Layout Model
Any bit-slice resident in memory has one of two major kinds, which the enums in
this module refer to as `Enclave` and `Region`
### Enclave
An `Enclave` layout occurs when a bit-slice is contained entirely within a
single memory element, and does not include either the initial or final semantic
index in its span.
```text
[ 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 ]
[ ^^^^^^^^^^^^^^^^^^^^^ ]
```
In an 8-bit element, a bit-slice is considered to be an `Enclave` if it is
contained entirely in the marked interior bits, and touches *neither* bit 7 nor
bit 0. Wider elements may touch interior byte boundaries, and only restrict bits
0 and `width - 1`.
### Region
A `Region` layout occurs when a bit-slice consists of:
- zero or one half-spanned head element (excludes bit 0, includes `width - 1`)
- zero or more fully-spanned elements body (includes both 0 and `width - 1`)
- zero or one half-spanned tail element (includes bit 0, excludes `width - 1`)
Each of these three sections is optionally present independently of the other
two. That is, in the following three bytes, all of the following bit-slices have
the `Region` layout:
```text
[ 7 6 5 4 3 2 1 0 ] [ 7 6 5 4 3 2 1 0 ] [ 7 6 5 4 3 2 1 0 ]
[ ]
[ h h h h ]
[ b b b b b b b b ]
[ t t t t ]
[ h h h h t t t t ]
[ h h h h b b b b b b b b ]
[ b b b b b b b b t t t t ]
[ h h h h b b b b b b b b t t t t ]
```
1. The empty bit-slice is a region with all of its segments blank.
1. A bit-slice with one element that touches `width - 1` but not 0 has a head,
but no body or tail.
1. A bit-slice that touches both `0` and `width - 1` of any number of elements
has a body, but no head or tail.
1. A bit-slice with one element that touches 0 but not `width - 1` has a tail,
but no head or body.
1. A bit-slice with two elements, that touches neither 0 of the first nor
`width - 1` of the second (but by definition `width - 1` of the first and 0
of the second; bit-slices are contiguous) has a head and tail, but no body.
The final three rows show how the individual segments can be composed to
describe all possible bit-slices.
## Aliasing Awareness
The contiguity property of `BitSlice` combines with the `&`/`&mut` exclusion
rules of the Rust language to provide additional information about the state of
the program that allows a given bit-slice to exist.
Specifically, any well-formed Rust program knows that *if* a bit-slice is able
to produce a `Region.body` segment, *then* that body is not aliased by `bitvec`,
and can safely transition to the `T::Unalias` state. Alias-permitting types like
`Cell` and the atomics will never change their types (because `bitvec` cannot
know that there are no views to a region other than what it has been given), but
a tainted `BitSlice<O, u8::Alias>` bit-slice can revert its interior body back
to `u8` and no longer require the alias tainting.
The head and tail segments do not retain their history, and cannot tell whether
they have been created by splitting or by shrinking, so they do not change their
types at all.
## Raw Memory Access
The [`BitDomain`] enum only splits a bit-slice along these boundaries, and
allows a bit-slice view to safely shed aliasing protection added to it by
[`.split_at_mut()`].
The [`Domain`] enum completely sheds its bit-precision views, and reverts to
ordinary element accesses. The body segment is an ordinary Rust slice with no
additional information or restriction; it can be freely used without regard for
any of `bitvec`’s constraints.
In order to preserve the rules that any given bit-slice can never be used to
affect bits outside of its own view of memory, the underlying memory of the head
and tail segments is only made accessible through a [`PartialElement`] reference
guard. This guard is an opaque proxy to the memory location, and holds both a
reference and the bit-mask required to prevent reading from or writing to the
bits outside the scope of the originating bit-slice.
## Generics
This module, and the contents of [`ptr`], make extensive use of a trait-level
mutability and reference tracking system in order to reduce code duplication and
provide a more powerful development environment than would be achieved with
macros.
As such, the trait bounds on types in this module are more intense than the
standard `<T, O>` fare in the crate’s main data structures. However, they are
only ever instantiated with shared or exclusive references, and all of the
bounds are a much more verbose way of saying “a reference, that is maybe-mut and
maybe-slice, of `T`”.
User code does not need to be aware of any of this: the `BitSlice` APIs that
call into this module always result in structures where the complex bounds are
reduced to ordinary slice references.
[`BitDomain`]: BitDomain
[`BitSlice`]: crate::slice::BitSlice
[`Domain`]: Domain
[`PartialElement`]: PartialElement
[`ptr`]: crate::ptr
[`.split_at_mut()`]: crate::slice::BitSlice::split_at_mut
|
