nanvm_lib/vm/bigint/
shl.rs

1use core::ops::Shl;
2
3use crate::{
4    common::sized_index::SizedIndex,
5    sign::Sign,
6    vm::{Any, BigInt, IVm, error},
7};
8
9use super::{MAX_WORDS, ShiftAmount, assert_slice_normalized};
10
11/// `<<`. <https://tc39.es/ecma262/#sec-numeric-types-bigint-leftShift>
12impl<A: IVm> Shl for BigInt<A> {
13    type Output = Result<Self, Any<A>>;
14
15    fn shl(self, rhs: Self) -> Self::Output {
16        // A negative shift amount is a right shift by its magnitude.
17        if rhs.sign() == Sign::Negative {
18            return self >> -rhs;
19        }
20
21        let (word_shift, bit_shift) = match self.shift_amount(&rhs) {
22            ShiftAmount::Noop => return Ok(self),
23            ShiftAmount::TooWide => return Err(error::bigint_too_large()),
24            ShiftAmount::Words(word_shift, bit_shift) => (word_shift, bit_shift),
25        };
26        let n_len = self.length();
27
28        // A carry word is only produced when `bit_shift` actually pushes a
29        // set bit out of the current top word — not on every shift, so this
30        // is computed exactly rather than conservatively reserved for every
31        // call: `1n << 1048575n` needs exactly `MAX_WORDS` words (no carry)
32        // and must succeed. That boundary is `nanvm-lib`'s own `MAX_WORDS`
33        // policy limit (see its doc comment), not V8's own — V8 alone would
34        // still accept a shift far past it.
35        let top_word = self[n_len - 1];
36        let carries_new_word = bit_shift > 0 && top_word >> (64 - bit_shift) != 0;
37        let result_len = word_shift + n_len as u64 + if carries_new_word { 1 } else { 0 };
38        if result_len > MAX_WORDS {
39            return Err(error::bigint_too_large());
40        }
41        let word_shift = word_shift as usize;
42
43        // `result_len` is already policy-bounded to `MAX_WORDS` (128 KiB) by
44        // the check above, but the allocator can still fail below that —
45        // the real memory available to an embedder can be smaller — so this
46        // reserves fallibly rather than through `Vec`'s ordinary growth,
47        // whose failure aborts the process instead of returning an `Err`.
48        let mut value: Vec<u64> = Vec::new();
49        if value.try_reserve_exact(result_len as usize).is_err() {
50            return Err(error::bigint_too_large());
51        }
52        value.extend(core::iter::repeat_n(0u64, word_shift));
53        value.extend((0..n_len).map(|i| self[i]));
54
55        if bit_shift > 0 {
56            let mut carry = 0u64;
57            for digit in value.iter_mut().skip(word_shift) {
58                let new_carry = *digit >> (64 - bit_shift);
59                *digit = (*digit << bit_shift) | carry;
60                carry = new_carry;
61            }
62            if carry != 0 {
63                value.push(carry);
64            }
65        }
66
67        assert!(!value.is_empty(), "shl: result must be non-empty");
68        assert_slice_normalized(value.as_slice());
69
70        // TODO: `value`'s own allocation above is fallible, but
71        // `unchecked_new` -> `IContainer::new_ok` -> (for `Naive`)
72        // `Container::new` collects it into an `Rc<[u64]>`, a second
73        // allocation that is not: an allocator that fails only that step
74        // still aborts the process instead of returning `RangeError` here.
75        // Making container construction reuse this buffer, or exposing a
76        // fallible construction path, needs a change to `IContainer`/the
77        // `Naive` backend rather than to this function.
78        Ok(Self::unchecked_new(self.sign(), value))
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use crate::vm::{
85        bigint::test_util::{T, neg, pos},
86        error,
87    };
88
89    #[test]
90    fn zero_shl_zero() {
91        let a: T = 0u64.into();
92        let b: T = 0u64.into();
93        assert_eq!((a << b).unwrap(), T::default());
94    }
95
96    #[test]
97    fn value_shl_zero() {
98        let a: T = 42u64.into();
99        let b: T = 0u64.into();
100        assert_eq!((a << b).unwrap(), 42u64.into());
101    }
102
103    #[test]
104    fn zero_shl_value() {
105        let a: T = 0u64.into();
106        let b: T = 5u64.into();
107        assert_eq!((a << b).unwrap(), T::default());
108    }
109
110    #[test]
111    fn shl_by_one() {
112        let a: T = 50u64.into();
113        let b: T = 1u64.into();
114        assert_eq!((a << b).unwrap(), 100u64.into());
115    }
116
117    #[test]
118    fn shl_full_word() {
119        // 1 << 64 = [0, 1]
120        let a: T = 1u64.into();
121        let b: T = 64u64.into();
122        assert_eq!((a << b).unwrap(), pos(vec![0, 1]));
123    }
124
125    #[test]
126    fn shl_more_than_word() {
127        // 2 << 65 = 4 * 2^64 = [0, 4]
128        let a: T = 2u64.into();
129        let b: T = 65u64.into();
130        assert_eq!((a << b).unwrap(), pos(vec![0, 4]));
131    }
132
133    #[test]
134    fn shl_preserves_positive_sign() {
135        let a = pos(vec![100]);
136        let b: T = 1u64.into();
137        assert_eq!((a << b).unwrap(), 200u64.into());
138    }
139
140    #[test]
141    fn shl_preserves_negative_sign() {
142        let a = neg(vec![100]);
143        let b: T = 1u64.into();
144        assert_eq!((a << b).unwrap(), neg(vec![200]));
145    }
146
147    #[test]
148    fn shl_63_bits() {
149        let a: T = 1u64.into();
150        let b: T = 63u64.into();
151        assert_eq!((a << b).unwrap(), (1u64 << 63).into());
152    }
153
154    #[test]
155    fn shl_overflow_into_new_word() {
156        // 0x8000_0000_0000_0000 << 1 = 2^64 = [0, 1]
157        let a: T = (1u64 << 63).into();
158        let b: T = 1u64.into();
159        assert_eq!((a << b).unwrap(), pos(vec![0, 1]));
160    }
161
162    #[test]
163    fn shl_large_bit_shift() {
164        // 0xF << 4 = 0xF0
165        let a: T = 0xFu64.into();
166        let b: T = 4u64.into();
167        assert_eq!((a << b).unwrap(), 0xF0u64.into());
168    }
169
170    #[test]
171    fn shl_three_words_by_word() {
172        // [1, 2, 3] << 64 = [0, 1, 2, 3]
173        let a = pos(vec![1, 2, 3]);
174        let b: T = 64u64.into();
175        assert_eq!((a << b).unwrap(), pos(vec![0, 1, 2, 3]));
176    }
177
178    #[test]
179    fn shl_three_words_by_128() {
180        // [1, 2, 3] << 128 = [0, 0, 1, 2, 3]
181        let a = pos(vec![1, 2, 3]);
182        let b: T = 128u64.into();
183        assert_eq!((a << b).unwrap(), pos(vec![0, 0, 1, 2, 3]));
184    }
185
186    #[test]
187    fn shl_word_plus_bits() {
188        // [0x80] << 65 = shift by 64 words + 1 bit
189        // = [0, 0x100]
190        let a = pos(vec![0x80]);
191        let b: T = 65u64.into();
192        assert_eq!((a << b).unwrap(), pos(vec![0, 0x100]));
193    }
194
195    #[test]
196    fn shl_multi_word_carry_propagation() {
197        // [u64::MAX, u64::MAX] << 1
198        // word 0: (MAX << 1) | 0 = MAX - 1 + carry 1
199        // word 1: (MAX << 1) | 1 = MAX, carry 1
200        // overflow carry: 1
201        let a = pos(vec![u64::MAX, u64::MAX]);
202        let b: T = 1u64.into();
203        let expected = pos(vec![u64::MAX - 1, u64::MAX, 1]);
204        assert_eq!((a << b).unwrap(), expected);
205    }
206
207    #[test]
208    fn shl_roundtrip_with_shr() {
209        // (42 << 10) >> 10 = 42
210        let a: T = 42u64.into();
211        let shift: T = 10u64.into();
212        let shifted = (a.clone() << shift.clone()).unwrap();
213        assert_eq!((shifted >> shift).unwrap(), 42u64.into());
214    }
215
216    #[test]
217    fn shl_negative_to_multi_word() {
218        let a = neg(vec![1]);
219        let b: T = 64u64.into();
220        assert_eq!((a << b).unwrap(), neg(vec![0, 1]));
221    }
222
223    #[test]
224    fn shl_by_192() {
225        // 5 << 192 = [0, 0, 0, 5]
226        let a: T = 5u64.into();
227        let b: T = 192u64.into();
228        assert_eq!((a << b).unwrap(), pos(vec![0, 0, 0, 5]));
229    }
230
231    #[test]
232    fn shl_by_63_multi_word() {
233        // [1, 1] << 63: maximum bit_shift on multi-word input
234        // word 0: (1 << 63) | 0 = 0x8000_0000_0000_0000, carry = 0
235        // word 1: (1 << 63) | 0 = 0x8000_0000_0000_0000, carry = 0
236        let a = pos(vec![1, 1]);
237        let b: T = 63u64.into();
238        assert_eq!(
239            (a << b).unwrap(),
240            pos(vec![0x8000_0000_0000_0000, 0x8000_0000_0000_0000])
241        );
242    }
243
244    #[test]
245    fn shl_all_ones_by_63() {
246        // [u64::MAX] << 63: all bits carry over
247        // digit: (MAX << 63) = 0x8000_0000_0000_0000, carry = MAX >> 1 = 0x7FFF_FFFF_FFFF_FFFF
248        let a: T = u64::MAX.into();
249        let b: T = 63u64.into();
250        assert_eq!(
251            (a << b).unwrap(),
252            pos(vec![0x8000_0000_0000_0000, 0x7FFF_FFFF_FFFF_FFFF])
253        );
254    }
255
256    #[test]
257    fn shl_pure_word_shift_multi_word() {
258        // [7, 11, 13] << 128: only word shift, no bit shift
259        let a = pos(vec![7, 11, 13]);
260        let b: T = 128u64.into();
261        assert_eq!((a << b).unwrap(), pos(vec![0, 0, 7, 11, 13]));
262    }
263
264    #[test]
265    fn shl_u64_max_by_one() {
266        // u64::MAX << 1 = [u64::MAX - 1, 1]
267        let a: T = u64::MAX.into();
268        let b: T = 1u64.into();
269        assert_eq!((a << b).unwrap(), pos(vec![u64::MAX - 1, 1]));
270    }
271
272    #[test]
273    fn shr_then_shl_roundtrip() {
274        // ([0, 42] >> 10) << 10 should equal [0, 42] (no bits lost in low word)
275        let a = pos(vec![0, 42]);
276        let shift: T = 10u64.into();
277        let shifted = (a.clone() >> shift.clone()).unwrap();
278        assert_eq!((shifted << shift).unwrap(), pos(vec![0, 42]));
279    }
280
281    #[test]
282    fn shl_negative_multi_word_with_carry() {
283        // neg([u64::MAX, u64::MAX]) << 1: carry propagates and overflows
284        let a = neg(vec![u64::MAX, u64::MAX]);
285        let b: T = 1u64.into();
286        assert_eq!((a << b).unwrap(), neg(vec![u64::MAX - 1, u64::MAX, 1]));
287    }
288
289    #[test]
290    fn shl_negative_multi_word_word_plus_bits() {
291        // neg([1, 2]) << 65: word_shift=1, bit_shift=1
292        // after word shift: [0, 1, 2]
293        // bit shift: word1: (1<<1)|0 = 2, carry=0; word2: (2<<1)|0 = 4, carry=0
294        let a = neg(vec![1, 2]);
295        let b: T = 65u64.into();
296        assert_eq!((a << b).unwrap(), neg(vec![0, 2, 4]));
297    }
298
299    #[test]
300    fn shl_multi_word_word_plus_bits() {
301        // [3, 5] << 65: word_shift=1, bit_shift=1
302        // after word shift: [0, 3, 5]
303        // bit shift: word1: (3<<1)|0 = 6, carry=0; word2: (5<<1)|0 = 10, carry=0
304        let a = pos(vec![3, 5]);
305        let b: T = 65u64.into();
306        assert_eq!((a << b).unwrap(), pos(vec![0, 6, 10]));
307    }
308
309    #[test]
310    fn shl_word_plus_bits_with_carry_overflow() {
311        // [0x8000_0000_0000_0000] << 65: word_shift=1, bit_shift=1
312        // after word shift: [0, 0x8000_0000_0000_0000]
313        // bit shift: (0x8000.. << 1) | 0 = 0, carry = 1 → pushed as new word
314        let a = pos(vec![0x8000_0000_0000_0000]);
315        let b: T = 65u64.into();
316        assert_eq!((a << b).unwrap(), pos(vec![0, 0, 1]));
317    }
318
319    #[test]
320    fn shl_all_ones_multi_word_by_63() {
321        // [u64::MAX, u64::MAX] << 63: max carry propagation across words
322        // word 0: (MAX << 63) | 0 = 0x8000.., carry = MAX >> 1 = 0x7FFF..
323        // word 1: (MAX << 63) | 0x7FFF.. = 0xFFFF.., carry = MAX >> 1 = 0x7FFF..
324        // overflow carry: 0x7FFF.. pushed
325        let a = pos(vec![u64::MAX, u64::MAX]);
326        let b: T = 63u64.into();
327        assert_eq!(
328            (a << b).unwrap(),
329            pos(vec![0x8000_0000_0000_0000, u64::MAX, 0x7FFF_FFFF_FFFF_FFFF])
330        );
331    }
332
333    #[test]
334    fn shl_multi_word_rhs_returns_err() {
335        let a: T = 1u64.into();
336        let b = pos(vec![0, 1]); // shift = 2^64
337        assert_eq!(a << b, Err(error::bigint_too_large()));
338    }
339
340    #[test]
341    fn shl_large_single_word_shift_returns_err() {
342        // u64::MAX would require ~2^58 words; exceeds the MAX_WORDS limit
343        let a: T = 1u64.into();
344        let b: T = u64::MAX.into();
345        assert_eq!(a << b, Err(error::bigint_too_large()));
346    }
347
348    #[test]
349    fn shl_just_over_max_words_returns_err_without_allocating() {
350        // Shifting by exactly `MAX_WORDS * 64` bits (2^20, matching
351        // `fjs/types/bigint/module.f.mjs`'s `maxLength`) needs MAX_WORDS + 1
352        // words (word_shift = MAX_WORDS, plus the existing word of `1`, no
353        // carry since bit_shift is 0) — one word past `nanvm-lib`'s own
354        // policy limit. That is not a boundary V8 itself enforces (V8 alone
355        // would still accept this shift); it is the tighter, cross-engine
356        // limit `MAX_WORDS`'s doc comment (in `bigint/mod.rs`) explains.
357        // Rejected by the guard before any allocation is attempted, so this
358        // stays cheap even though the *value* it describes would not.
359        let a: T = 1u64.into();
360        let b: T = (super::MAX_WORDS * 64).into();
361        assert_eq!(a << b, Err(error::bigint_too_large()));
362    }
363
364    #[test]
365    fn shl_at_max_words_boundary_succeeds() {
366        // One bit under the just-over-the-limit case above: shifting by
367        // `MAX_WORDS * 64 - 1` bits needs exactly `MAX_WORDS` words
368        // (word_shift = MAX_WORDS - 1, bit_shift = 63, no carry since the
369        // shifted bit lands on the top word's own MSB rather than past it)
370        // and must succeed — the doc comment on `MAX_WORDS`'s own use above
371        // asserts this ("must succeed"), but nothing tested it: the only
372        // existing boundary test exercises the throwing side, one word past
373        // this one. Tightening the guard to reject this shift too would
374        // leave that test green.
375        let a: T = 1u64.into();
376        let b: T = (super::MAX_WORDS * 64 - 1).into();
377        let mut expected = vec![0u64; super::MAX_WORDS as usize - 1];
378        expected.push(1u64 << 63);
379        assert_eq!((a << b).unwrap(), pos(expected));
380    }
381
382    #[test]
383    fn shl_carry_word_only_counted_when_actually_needed() {
384        // A shift landing the single set bit on the top word's own MSB
385        // (bit_shift = 63, and that bit was 0 before the shift) produces no
386        // carry — word_shift + n_len alone is the exact result length, so
387        // the guard must not conservatively add one for every call. Here
388        // the shift is chosen so the guard's word-count arithmetic is
389        // exercised directly (word_shift = 2, matching a hypothetically
390        // tiny `MAX_WORDS`), without needing an allocation anywhere near
391        // the real 128 KiB limit to prove it.
392        let a: T = 1u64.into();
393        let b: T = 191u64.into(); // word_shift = 2, bit_shift = 63
394        assert_eq!((a << b).unwrap(), pos(vec![0, 0, 1u64 << 63]));
395    }
396
397    #[test]
398    fn shl_by_negative_is_right_shift() {
399        // x << -y is x >> y.
400        let a: T = 40u64.into();
401        let b: T = (-3i64).into();
402        assert_eq!((a << b).unwrap(), 5u64.into());
403    }
404
405    #[test]
406    fn shl_negative_by_negative_is_right_shift() {
407        let a = neg(vec![40]);
408        let b: T = (-3i64).into();
409        assert_eq!((a << b).unwrap(), neg(vec![5]));
410    }
411}
nanvm_lib/vm/bigint/shl.rs

nanvm_lib/vm/bigint/
shl.rs
