• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

kaidokert / picojson-rs / 15977103664

30 Jun 2025 03:26PM UTC coverage: 94.482% (+0.5%) from 94.027%
15977103664

Pull #16

github

kaidokert
Rename things
Pull Request #16: Rename things

13 of 13 new or added lines in 3 files covered. (100.0%)

25 existing lines in 3 files now uncovered.

2089 of 2211 relevant lines covered (94.48%)

134.33 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

95.56
/picojson/src/ujson/bitstack/mod.rs
1
// SPDX-License-Identifier: Apache-2.0
2

3
use core::cmp::PartialEq;
4
use core::ops::{BitAnd, BitOr, Shl, Shr};
5

6
/// Trait for bit buckets - provides bit storage for JSON parser state.
7
/// This trait is implemented for both integer and [T; N] types.
8
///
9
/// NOTE: BitBucket implementations do NOT implement depth tracking.
10
/// This is the responsibility of the caller.
11
pub trait BitBucket: Default {
12
    /// Pushes a bit (true for 1, false for 0) onto the stack.
13
    fn push(&mut self, bit: bool);
14
    /// Pops the top bit off the stack, returning it if the stack isn’t empty.
15
    fn pop(&mut self) -> bool;
16
    /// Returns the top bit without removing it.
17
    fn top(&self) -> bool;
18
}
19

20
/// Automatic implementation for builtin-types ( u8, u32 etc ).
21
/// Any type that implements the required traits is automatically implemented for BitBucket.
22
impl<T> BitBucket for T
23
where
24
    T: Shl<u8, Output = T>
25
        + Shr<u8, Output = T>
26
        + BitAnd<T, Output = T>
27
        + BitOr<Output = T>
28
        + PartialEq
29
        + Clone
30
        + Default,
31
    T: From<u8>, // To create 0 and 1 constants
32
{
33
    fn push(&mut self, bit: bool) {
423✔
34
        *self = (self.clone() << 1u8) | T::from(bit as u8);
423✔
35
    }
423✔
36

37
    fn pop(&mut self) -> bool {
122✔
38
        let bit = (self.clone() & T::from(1)) != T::from(0);
122✔
39
        *self = self.clone() >> 1u8;
122✔
40
        bit
122✔
41
    }
122✔
42

43
    fn top(&self) -> bool {
237✔
44
        (self.clone() & T::from(1)) != T::from(0)
237✔
45
    }
237✔
46
}
47

48
// TODO: Can this be implemented for slices as well ?
49

50
/// Trait for depth counters - tracks nesting depth
51
/// This is automatically implemented for any type that satisfies the individual bounds.
52
pub trait DepthCounter:
53
    From<u8>
54
    + core::cmp::PartialEq<Self>
55
    + core::ops::AddAssign<Self>
56
    + core::ops::SubAssign<Self>
57
    + core::ops::Not<Output = Self>
58
    + core::fmt::Debug
59
{
60
}
61

62
impl<T> DepthCounter for T where
63
    T: From<u8>
64
        + core::cmp::PartialEq<T>
65
        + core::ops::AddAssign<T>
66
        + core::ops::SubAssign<T>
67
        + core::ops::Not<Output = T>
68
        + core::fmt::Debug
69
{
70
}
71

72
/// Configuration trait for BitStack systems - defines bucket and counter types.
73
pub trait BitStackConfig {
74
    type Bucket: BitBucket + Default;
75
    type Counter: DepthCounter + Default;
76
}
77

78
/// Default configuration using u32 bucket and u8 counter
79
pub struct DefaultConfig;
80

81
impl BitStackConfig for DefaultConfig {
82
    type Bucket = u32;
83
    type Counter = u8;
84
}
85

86
/// User-facing BitStack configuration struct - the main API users interact with
87
/// Usage: `BitStack<u64, u16>` for custom bucket and counter types
88
pub struct BitStackStruct<B, C> {
89
    _phantom: core::marker::PhantomData<(B, C)>,
90
}
91

92
impl<B, C> BitStackConfig for BitStackStruct<B, C>
93
where
94
    B: BitBucket + Default,
95
    C: DepthCounter + Default,
96
{
97
    type Bucket = B;
98
    type Counter = C;
99
}
100

101
/// Array-based BitStack implementation for large storage capacity.
102
pub type ArrayBitStack<const N: usize, T, D> = BitStackStruct<ArrayBitBucket<N, T>, D>;
103

104
/// Array-based BitBucket implementation for large storage capacity.
105
/// Provides large BitBucket storage using multiple elements.
106
/// This can be used to parse very deeply nested JSON.
107
#[derive(Debug)]
108
pub struct ArrayBitBucket<const N: usize, T>(pub [T; N]);
109

110
impl<const N: usize, T: Default + Copy> Default for ArrayBitBucket<N, T> {
111
    fn default() -> Self {
11✔
112
        ArrayBitBucket([T::default(); N])
11✔
113
    }
11✔
114
}
115

116
impl<const N: usize, T> BitBucket for ArrayBitBucket<N, T>
117
where
118
    T: Shl<u8, Output = T>
119
        + Shr<u8, Output = T>
120
        + BitAnd<T, Output = T>
121
        + core::ops::BitOr<Output = T>
122
        + PartialEq
123
        + Clone
124
        + From<u8>
125
        + Copy
126
        + Default,
127
{
128
    fn push(&mut self, bit: bool) {
78✔
129
        // Strategy: Use array as big-endian storage, with leftmost element as most significant
130
        // Shift all elements left, carrying overflow from right to left
131
        let bit_val = T::from(bit as u8);
78✔
132
        let mut carry = bit_val;
78✔
133
        let element_bits = (core::mem::size_of::<T>() * 8) as u8;
78✔
134
        let msb_shift = element_bits - 1;
78✔
135

136
        // Start from the rightmost (least significant) element and work left
137
        for i in (0..N).rev() {
276✔
138
            let old_msb = (self.0[i] >> msb_shift) & T::from(1); // Extract MSB that will be lost
276✔
139
            self.0[i] = (self.0[i] << 1u8) | carry;
276✔
140
            carry = old_msb;
276✔
141
        }
276✔
142
        // Note: carry from leftmost element is discarded (overflow)
143
    }
78✔
144

145
    fn pop(&mut self) -> bool {
86✔
146
        // Extract rightmost bit from least significant element
147
        let bit = (self.0[N - 1] & T::from(1)) != T::from(0);
86✔
148

149
        // Shift all elements right, carrying underflow from left to right
150
        let mut carry = T::from(0);
86✔
151
        let element_bits = (core::mem::size_of::<T>() * 8) as u8;
86✔
152
        let msb_shift = element_bits - 1;
86✔
153

154
        // Start from the leftmost (most significant) element and work right
155
        for i in 0..N {
373✔
156
            let old_lsb = self.0[i] & T::from(1); // Extract LSB that will be lost
287✔
157
            self.0[i] = (self.0[i] >> 1u8) | (carry << msb_shift);
287✔
158
            carry = old_lsb;
287✔
159
        }
287✔
160

161
        bit
86✔
162
    }
86✔
163

164
    fn top(&self) -> bool {
19✔
165
        // Return rightmost bit from least significant element without modifying
166
        (self.0[N - 1] & T::from(1)) != T::from(0)
19✔
167
    }
19✔
168
}
169

170
#[cfg(test)]
171
mod tests {
172
    use super::*;
173

174
    #[test]
175
    fn test_bitstack() {
1✔
176
        let mut bitstack = 0;
1✔
177
        bitstack.push(true);
1✔
178
        bitstack.push(false);
1✔
179
        assert_eq!(bitstack.pop(), false);
1✔
180
        assert_eq!(bitstack.pop(), true);
1✔
181
    }
1✔
182

183
    #[test]
184
    fn test_array_bitstack() {
1✔
185
        // Test ArrayBitStack with 2 u8 elements (16-bit total capacity)
186
        let mut bitstack: ArrayBitBucket<2, u8> = ArrayBitBucket::default();
1✔
187

188
        // Test basic push/pop operations
189
        bitstack.push(true);
1✔
190
        bitstack.push(false);
1✔
191
        bitstack.push(true);
1✔
192

193
        // Verify top() doesn't modify stack
194
        assert_eq!(bitstack.top(), true);
1✔
195
        assert_eq!(bitstack.top(), true);
1✔
196

197
        // Verify LIFO order
198
        assert_eq!(bitstack.pop(), true);
1✔
199
        assert_eq!(bitstack.pop(), false);
1✔
200
        assert_eq!(bitstack.pop(), true);
1✔
201
    }
1✔
202

203
    #[test]
204
    fn test_array_bitstack_large_capacity() {
1✔
205
        // Test larger ArrayBitStack (320-bit capacity with 10 u32 elements)
206
        let mut bitstack: ArrayBitBucket<10, u32> = ArrayBitBucket::default();
1✔
207

208
        // Push many bits to test multi-element handling
209
        let pattern = [true, false, true, true, false, false, true, false];
1✔
210
        for &bit in &pattern {
9✔
211
            bitstack.push(bit);
8✔
212
        }
8✔
213

214
        // Pop and verify reverse order (LIFO)
215
        for &expected in pattern.iter().rev() {
8✔
216
            assert_eq!(bitstack.pop(), expected);
8✔
217
        }
218
    }
1✔
219

220
    #[test]
221
    fn test_element_size_handling() {
1✔
222
        // Test that bitstack correctly handles different element sizes
223

224
        // Test u8 elements (8-bit each)
225
        let mut bitstack_u8: ArrayBitBucket<1, u8> = ArrayBitBucket::default();
1✔
226

227
        // Fill all 8 bits of a u8 element
228
        for i in 0..8 {
9✔
229
            bitstack_u8.push(i % 2 == 0); // alternating pattern: true, false, true, false...
8✔
230
        }
8✔
231

232
        // Verify we can retrieve all 8 bits in LIFO order
233
        for i in (0..8).rev() {
8✔
234
            assert_eq!(bitstack_u8.pop(), i % 2 == 0);
8✔
235
        }
236

237
        // Test u32 elements (32-bit each)
238
        let mut bitstack_u32: ArrayBitBucket<1, u32> = ArrayBitBucket::default();
1✔
239

240
        // Fill all 32 bits of a u32 element
241
        for i in 0..32 {
33✔
242
            bitstack_u32.push(i % 3 == 0); // pattern: true, false, false, true, false, false...
32✔
243
        }
32✔
244

245
        // Verify we can retrieve all 32 bits in LIFO order
246
        for i in (0..32).rev() {
32✔
247
            assert_eq!(bitstack_u32.pop(), i % 3 == 0);
32✔
248
        }
249
    }
1✔
250

251
    #[test]
252
    fn test_array_bitstack_basic_moved() {
1✔
253
        // Test ArrayBitStack with 2 u8 elements (16-bit total capacity)
254
        let mut bitstack: ArrayBitBucket<2, u8> = ArrayBitBucket::default();
1✔
255

256
        // Test basic push/pop operations
257
        bitstack.push(true);
1✔
258
        bitstack.push(false);
1✔
259
        bitstack.push(true);
1✔
260

261
        // Verify top() doesn't modify stack
262
        assert_eq!(bitstack.top(), true);
1✔
263
        assert_eq!(bitstack.top(), true);
1✔
264

265
        // Verify LIFO order
266
        assert_eq!(bitstack.pop(), true);
1✔
267
        assert_eq!(bitstack.pop(), false);
1✔
268
        assert_eq!(bitstack.pop(), true);
1✔
269
    }
1✔
270

271
    #[test]
272
    fn test_array_bitstack_large_capacity_moved() {
1✔
273
        // Test larger ArrayBitStack (320-bit capacity with 10 u32 elements)
274
        let mut bitstack: ArrayBitBucket<10, u32> = ArrayBitBucket::default();
1✔
275

276
        // Push many bits to test multi-element handling
277
        let pattern = [true, false, true, true, false, false, true, false];
1✔
278
        for &bit in &pattern {
9✔
279
            bitstack.push(bit);
8✔
280
        }
8✔
281

282
        // Pop and verify reverse order (LIFO)
283
        for &expected in pattern.iter().rev() {
8✔
284
            assert_eq!(bitstack.pop(), expected);
8✔
285
        }
286
    }
1✔
287

288
    #[test]
289
    fn test_array_bitstack_element_overflow_moved() {
1✔
290
        // Test ArrayBitStack with 2 u8 elements to verify cross-element operations
291
        let mut bitstack: ArrayBitBucket<2, u8> = ArrayBitBucket::default();
1✔
292

293
        // Push more than 8 bits to force usage of multiple elements
294
        let bits = [
1✔
295
            true, false, true, false, true, false, true, false, true, true,
1✔
296
        ];
1✔
297
        for &bit in &bits {
11✔
298
            bitstack.push(bit);
10✔
299
        }
10✔
300

301
        // Pop all bits and verify order
302
        for &expected in bits.iter().rev() {
10✔
303
            assert_eq!(bitstack.pop(), expected);
10✔
304
        }
305
    }
1✔
306

307
    #[test]
308
    fn test_array_bitstack_empty_behavior_moved() {
1✔
309
        // Test behavior when popping from an empty ArrayBitStack
310
        // With the new API, empty stacks return false (no depth tracking needed)
311
        let mut bitstack: ArrayBitBucket<2, u8> = ArrayBitBucket::default();
1✔
312

313
        // CURRENT BEHAVIOR: Empty stack returns false (was Some(false) before API change)
314
        // This behavior is now the intended design - no depth tracking needed
315
        assert!(!bitstack.pop(), "Empty stack returns false");
1✔
316
        assert!(!bitstack.top(), "Empty stack top() returns false");
1✔
317

318
        // Test that underflow doesn't panic (at least it's safe)
319
        assert_eq!(
1✔
320
            bitstack.pop(),
1✔
321
            false,
UNCOV
322
            "Multiple underflow calls don't panic"
×
323
        );
324
        assert_eq!(
1✔
325
            bitstack.pop(),
1✔
326
            false,
UNCOV
327
            "Multiple underflow calls don't panic"
×
328
        );
329
    }
1✔
330

331
    #[test]
332
    fn test_array_bitstack_underflow_does_not_panic_moved() {
1✔
333
        // Test that multiple underflow attempts are safe (don't panic)
334
        // This is important for robustness even with the current incorrect API
335
        let mut bitstack: ArrayBitBucket<1, u8> = ArrayBitBucket::default();
1✔
336

337
        // Multiple calls to pop() on empty stack should not panic
338
        for i in 0..5 {
6✔
339
            let result = bitstack.pop();
5✔
340
            // With new API, just ensure it doesn't panic and returns a bool
341
            assert_eq!(
5✔
342
                result,
343
                false,
UNCOV
344
                "Empty ArrayBitStack pop() attempt {} should return false",
×
345
                i + 1
×
346
            );
347

348
            let top_result = bitstack.top();
5✔
349
            assert_eq!(
5✔
350
                top_result,
351
                false,
UNCOV
352
                "Empty ArrayBitStack top() attempt {} should return false",
×
UNCOV
353
                i + 1
×
354
            );
355
        }
356
    }
1✔
357
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc