Skip to content
Merged
Show file tree
Hide file tree
Changes from all commits
Commits
File filter

Filter by extension

Filter by extension


Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 1 addition & 1 deletion Cargo.lock

Some generated files are not rendered by default. Learn more about how customized files appear on GitHub.

2 changes: 1 addition & 1 deletion Cargo.toml
Original file line number Diff line number Diff line change
Expand Up @@ -283,7 +283,7 @@ pem-rfc7468 = "1.0"
pkcs8 = "0.11"
proc-macro2 = "1.0.105"
psm = "0.1"
pymath = { git = "https://github.com/RustPython/pymath.git", rev = "dd1e9a4cf26d68caf3b549c09476f52e356e16a3", features = ["mul_add", "malachite-bigint", "complex"] }
pymath = { git = "https://github.com/RustPython/pymath.git", rev = "6992bbfc853707545d0fb4b91931a2f36df89abe", features = ["mul_add", "malachite-bigint", "complex"] }
pyo3 = "0.30"
quote = "1.0.45"
radium = "1.1.1"
Expand Down
1 change: 0 additions & 1 deletion Lib/test/test_math.py
Original file line number Diff line number Diff line change
Expand Up @@ -1759,7 +1759,6 @@ def testRadians(self):
self.ftest('radians(-45)', math.radians(-45), -math.pi/4)
self.ftest('radians(0)', math.radians(0), 0)

@unittest.expectedFailureIfWindows("TODO: RUSTPYTHON; Error message too long")
@requires_IEEE_754
def testRemainder(self):
from fractions import Fraction
Expand Down
41 changes: 18 additions & 23 deletions crates/common/src/hash.rs
Original file line number Diff line number Diff line change
Expand Up @@ -214,29 +214,12 @@ pub fn keyed_hash(key: u64, buf: &[u8]) -> u64 {
pub fn hash_tuple<E>(
element_hashes: impl IntoIterator<Item = Result<PyHash, E>>,
) -> Result<PyHash, E> {
const PRIME1: PyUHash = cfg_select! {
target_pointer_width = "64" => 11400714785074694791,
target_pointer_width = "32" => 2654435761,
_ => unreachable!(),
};

const PRIME2: PyUHash = cfg_select! {
target_pointer_width = "64" => 14029467366897019727,
target_pointer_width = "32" => 2246822519,
_ => unreachable!(),
};

const PRIME5: PyUHash = cfg_select! {
target_pointer_width = "64" => 2870177450012600261,
target_pointer_width = "32" => 374761393,
_ => unreachable!(),
};

const ROTATE: u32 = cfg_select! {
target_pointer_width = "64" => 31,
target_pointer_width = "32" => 13,
_ => unreachable!(),
};
// PyHash is 64-bit even on 32-bit targets, so the xxHash parameters
// must follow the hash width rather than the pointer width.
const PRIME1: PyUHash = 11400714785074694791;
const PRIME2: PyUHash = 14029467366897019727;
const PRIME5: PyUHash = 2870177450012600261;
const ROTATE: u32 = 31;

let mut acc = PRIME5;
let mut len: PyUHash = 0;
Expand Down Expand Up @@ -309,6 +292,18 @@ impl FrozenSetHash {
mod tests {
use super::*;

#[test]
fn tuple_hash_uses_the_declared_hash_width() {
for (elements, expected) in [
(&[][..], 5740354900026072187),
(&[0][..], -8753497827991233192),
(&[0, 0][..], -8458139203682520985),
] {
let actual = hash_tuple(elements.iter().copied().map(Ok::<_, ()>)).unwrap();
assert_eq!(actual, expected);
}
}

#[test]
fn from_keys_is_stable_and_seed_independent() {
const K0: u64 = 0x0706_0504_0302_0100;
Expand Down
132 changes: 85 additions & 47 deletions crates/vm/src/builtins/range.rs
Original file line number Diff line number Diff line change
Expand Up @@ -2,7 +2,7 @@ use super::{
PyGenericAlias, PyInt, PyIntRef, PySlice, PyTupleRef, PyType, PyTypeRef, builtins_iter,
tuple::tuple_hash,
};
use crate::common::lock::LazyLock;
use crate::common::lock::{LazyLock, PyMutex};
use crate::{
AsObject, Context, Py, PyObject, PyObjectRef, PyPayload, PyRef, PyResult, TryFromObject,
VirtualMachine, atomic_func,
Expand All @@ -16,7 +16,6 @@ use crate::{
},
};
use core::cell::Cell;
use core::cmp::max;
use core::ptr::NonNull;
use crossbeam_utils::atomic::AtomicCell;
use malachite_bigint::{BigInt, Sign};
Expand Down Expand Up @@ -376,7 +375,7 @@ impl Py<PyRange> {
.into_pyobject(vm)
} else {
PyLongRangeIterator {
index: AtomicCell::new(0),
index: PyMutex::new(BigInt::zero()),
start,
step,
length,
Expand Down Expand Up @@ -544,7 +543,7 @@ impl Iterable for PyRange {
.into_pyobject(vm))
} else {
Ok(PyLongRangeIterator {
index: AtomicCell::new(0),
index: PyMutex::new(BigInt::zero()),
start: start.clone(),
step: step.clone(),
length,
Expand All @@ -566,18 +565,11 @@ impl Representable for PyRange {
}
}

// Semantically, this is the same as the previous representation.
//
// Unfortunately, since AtomicCell requires a Copy type, no BigInt implementations can
// generally be used. As such, usize::MAX is the upper bound on number of elements (length)
// the range can contain in RustPython.
//
// This doesn't preclude the range from containing large values, since start and step
// can be BigInts, we can store any arbitrary range of values.
// Long ranges need arbitrary-precision positions as well as values.
#[pyclass(module = false, name = "longrange_iterator")]
#[derive(Debug)]
pub(crate) struct PyLongRangeIterator {
index: AtomicCell<usize>,
index: PyMutex<BigInt>,
start: BigInt,
step: BigInt,
length: BigInt,
Expand All @@ -594,7 +586,7 @@ impl PyPayload for PyLongRangeIterator {
impl Py<PyLongRangeIterator> {
#[pymethod]
fn __length_hint__(&self) -> BigInt {
let index = BigInt::from(self.index.load());
let index = self.index.lock().clone();
if index < self.length {
self.length.clone() - index
} else {
Expand All @@ -604,17 +596,19 @@ impl Py<PyLongRangeIterator> {

#[pymethod]
fn __setstate__(&self, state: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
self.index.store(range_state(&self.length, &state, vm)?);
let index = range_state(&self.length, &state, vm)?;
*self.index.lock() = index;
Ok(())
}

#[pymethod]
fn __reduce__(&self, vm: &VirtualMachine) -> PyResult<PyTupleRef> {
let index = self.index.lock().clone();
range_iter_reduce(
self.start.clone(),
self.length.clone(),
self.step.clone(),
self.index.load(),
index,
vm,
)
}
Expand All @@ -623,17 +617,17 @@ impl Py<PyLongRangeIterator> {
impl SelfIter for PyLongRangeIterator {}
impl IterNext for PyLongRangeIterator {
fn next(zelf: &Py<Self>, vm: &VirtualMachine) -> PyResult<PyIterReturn> {
// TODO: In pathological case (index == usize::MAX) this can wrap around
// (since fetch_add wraps). This would result in the iterator spinning again
// from the beginning.
let index = BigInt::from(zelf.index.fetch_add(1));
let r = if index < zelf.length {
let value = zelf.start.clone() + index * zelf.step.clone();
PyIterReturn::Return(vm.ctx.new_int(value).into())
} else {
PyIterReturn::StopIteration(None)
let index = {
let mut index = zelf.index.lock();
if *index >= zelf.length {
return Ok(PyIterReturn::StopIteration(None));
}
let current = index.clone();
*index += 1;
current
};
Ok(r)
let value = zelf.start.clone() + index * zelf.step.clone();
Ok(PyIterReturn::Return(vm.ctx.new_int(value).into()))
}
}

Expand Down Expand Up @@ -665,8 +659,11 @@ impl Py<PyRangeIterator> {

#[pymethod]
fn __setstate__(&self, object: PyObjectRef, vm: &VirtualMachine) -> PyResult<()> {
self.index
.store(range_state(&BigInt::from(self.length), &object, vm)?);
self.index.store(
range_state(&BigInt::from(self.length), &object, vm)?
.to_usize()
.unwrap(),
);
Ok(())
}

Expand All @@ -676,7 +673,7 @@ impl Py<PyRangeIterator> {
BigInt::from(self.start),
BigInt::from(self.length),
BigInt::from(self.step),
self.index.load(),
BigInt::from(self.index.load()),
vm,
)
}
Expand All @@ -686,12 +683,14 @@ impl PyRangeIterator {
/// Fast path for FOR_ITER specialization. Returns the next isize value
/// without allocating PyInt or PyIterReturn.
pub(crate) fn fast_next(&self) -> Option<isize> {
let index = self.index.fetch_add(1);
if index < self.length {
Some(self.start + (index as isize) * self.step)
} else {
None
}
let index = self
.index
.fetch_update(|index| (index < self.length).then(|| index + 1))
.ok()?;
Some(
self.start
.wrapping_add((index as isize).wrapping_mul(self.step)),
)
}
}

Expand All @@ -710,13 +709,12 @@ fn range_iter_reduce(
start: BigInt,
length: BigInt,
step: BigInt,
index: usize,
index: BigInt,
vm: &VirtualMachine,
) -> PyResult<PyTupleRef> {
let iter = builtins_iter(vm)?;
// CPython pickles the remaining range with a None state. next() increments
// the index unconditionally, so clamp it to length before rebasing start.
let index = BigInt::from(index).min(length.clone());
// CPython pickles the remaining range with a None state.
let index = index.min(length.clone());
let stop = start.clone() + length * step.clone();
let start = start + index * step.clone();
let range = PyRange {
Expand All @@ -727,15 +725,10 @@ fn range_iter_reduce(
Ok(vm.new_tuple((iter, (range,), vm.ctx.none())))
}

// Silently clips state (i.e index) in range [0, usize::MAX].
fn range_state(length: &BigInt, state: &PyObject, vm: &VirtualMachine) -> PyResult<usize> {
// Silently clips state (i.e index) in range [0, length].
fn range_state(length: &BigInt, state: &PyObject, vm: &VirtualMachine) -> PyResult<BigInt> {
if let Some(i) = state.downcast_ref::<PyInt>() {
let mut index = i.as_bigint();
let max_usize = BigInt::from(usize::MAX);
if index > length {
index = max(length, &max_usize);
}
Ok(index.to_usize().unwrap_or(0))
Ok(i.as_bigint().clone().clamp(BigInt::zero(), length.clone()))
} else {
Err(vm.new_type_error("an integer is required."))
}
Expand All @@ -761,3 +754,48 @@ impl TryFromObject for RangeIndex {
})
}
}

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

#[test]
fn long_iterator_preserves_arbitrary_precision_state() {
crate::Interpreter::without_stdlib(Default::default()).enter(|vm| {
let length: BigInt = BigInt::one() << 100;
let iter = PyLongRangeIterator {
index: PyMutex::new(BigInt::zero()),
start: BigInt::zero(),
step: BigInt::one(),
length: length.clone(),
}
.into_ref(&vm.ctx);
let state: BigInt = &length - 1;
iter.__setstate__(vm.ctx.new_bigint(&state).into(), vm)
.unwrap();
assert_eq!(iter.__length_hint__(), BigInt::one());
let PyIterReturn::Return(value) = PyLongRangeIterator::next(&iter, vm).unwrap() else {
panic!("wide iterator state was lost");
};
assert_eq!(value.downcast_ref::<PyInt>().unwrap().as_bigint(), &state);
for _ in 0..2 {
assert!(matches!(
PyLongRangeIterator::next(&iter, vm).unwrap(),
PyIterReturn::StopIteration(None)
));
}
});
}

#[test]
fn exhausted_fast_iterator_does_not_wrap_its_index() {
let iter = PyRangeIterator {
index: AtomicCell::new(usize::MAX),
start: 0,
step: 1,
length: usize::MAX,
};
assert_eq!(iter.fast_next(), None);
assert_eq!(iter.fast_next(), None);
}
}
32 changes: 32 additions & 0 deletions crates/vm/src/object/core.rs
Original file line number Diff line number Diff line change
Expand Up @@ -144,13 +144,45 @@ mod trashcan {
item
};
if let Some((obj, dealloc)) = next {
// A queued deallocator may defer more objects, but its
// end() must not start another drain.
t.depth.set(1);
let _draining = scopeguard::guard((), |()| t.depth.set(0));
unsafe { dealloc(obj) };
} else {
break;
}
}
})
}

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

unsafe fn assert_guarded_dealloc(_: *mut super::super::PyObject) {
assert!(TRASHCAN.with(|t| t.depth.get() > 0));
}

#[test]
fn deferred_deallocations_remain_guarded() {
// This callback never dereferences its opaque object pointer.
let obj = core::ptr::null_mut();
unsafe {
for _ in 0..TRASHCAN_LIMIT {
assert!(begin(obj, assert_guarded_dealloc));
}
assert!(!begin(obj, assert_guarded_dealloc));
for _ in 0..TRASHCAN_LIMIT {
end();
}
}
TRASHCAN.with(|t| {
assert_eq!(t.depth.get(), 0);
assert!(t.queue.take().is_empty());
});
}
}
}

/// Default dealloc: handles __del__, weakref clearing, tp_clear, and memory free.
Expand Down
Loading
Loading