diff options
| -rw-r--r-- | src/libcollections/btree/map.rs | 35 | ||||
| -rw-r--r-- | src/libcollections/btree/node.rs | 21 | ||||
| -rw-r--r-- | src/libcollectionstest/btree/map.rs | 16 | ||||
| -rw-r--r-- | src/test/compile-fail/variance-btree-invariant-types.rs | 63 |
4 files changed, 118 insertions, 17 deletions
diff --git a/src/libcollections/btree/map.rs b/src/libcollections/btree/map.rs index 2375a63fbd7..492263da2bc 100644 --- a/src/libcollections/btree/map.rs +++ b/src/libcollections/btree/map.rs @@ -12,6 +12,7 @@ use core::cmp::Ordering; use core::fmt::Debug; use core::hash::{Hash, Hasher}; use core::iter::FromIterator; +use core::marker::PhantomData; use core::ops::Index; use core::{fmt, intrinsics, mem, ptr}; @@ -158,7 +159,8 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()> Found(handle) => { Some(OccupiedEntry { handle: handle, - length: &mut self.length + length: &mut self.length, + _marker: PhantomData, }.remove_kv().0) }, GoDown(_) => None @@ -172,7 +174,8 @@ impl<K, Q: ?Sized> super::Recover<Q> for BTreeMap<K, ()> VacantEntry { key: key, handle: handle, - length: &mut self.length + length: &mut self.length, + _marker: PhantomData, }.insert(()); None } @@ -223,7 +226,10 @@ pub struct Range<'a, K: 'a, V: 'a> { /// A mutable iterator over a sub-range of BTreeMap's entries. pub struct RangeMut<'a, K: 'a, V: 'a> { front: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, - back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge> + back: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, + + // Be invariant in `K` and `V` + _marker: PhantomData<&'a mut (K, V)>, } /// A view into a single entry in a map, which may either be vacant or occupied. @@ -247,7 +253,10 @@ pub enum Entry<'a, K: 'a, V: 'a> { pub struct VacantEntry<'a, K: 'a, V: 'a> { key: K, handle: Handle<NodeRef<marker::Mut<'a>, K, V, marker::Leaf>, marker::Edge>, - length: &'a mut usize + length: &'a mut usize, + + // Be invariant in `K` and `V` + _marker: PhantomData<&'a mut (K, V)>, } /// An occupied Entry. @@ -259,7 +268,10 @@ pub struct OccupiedEntry<'a, K: 'a, V: 'a> { marker::LeafOrInternal >, marker::KV>, - length: &'a mut usize + length: &'a mut usize, + + // Be invariant in `K` and `V` + _marker: PhantomData<&'a mut (K, V)>, } impl<K: Ord, V> BTreeMap<K, V> { @@ -415,7 +427,8 @@ impl<K: Ord, V> BTreeMap<K, V> { Found(handle) => { Some(OccupiedEntry { handle: handle, - length: &mut self.length + length: &mut self.length, + _marker: PhantomData, }.remove()) }, GoDown(_) => None @@ -568,7 +581,8 @@ impl<K: Ord, V> BTreeMap<K, V> { RangeMut { front: front, - back: back + back: back, + _marker: PhantomData } } @@ -593,12 +607,14 @@ impl<K: Ord, V> BTreeMap<K, V> { match search::search_tree(self.root.as_mut(), &key) { Found(handle) => Occupied(OccupiedEntry { handle: handle, - length: &mut self.length + length: &mut self.length, + _marker: PhantomData, }), GoDown(handle) => Vacant(VacantEntry { key: key, handle: handle, - length: &mut self.length + length: &mut self.length, + _marker: PhantomData, }) } } @@ -1235,6 +1251,7 @@ impl<K, V> BTreeMap<K, V> { range: RangeMut { front: first_leaf_edge(root1), back: last_leaf_edge(root2), + _marker: PhantomData, }, length: self.length } diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs index 2e2a39df347..c8a0f60587e 100644 --- a/src/libcollections/btree/node.rs +++ b/src/libcollections/btree/node.rs @@ -97,13 +97,13 @@ impl<K, V> BoxedNode<K, V> { } } - unsafe fn from_ptr(ptr: NonZero<*mut LeafNode<K, V>>) -> Self { - BoxedNode { ptr: Unique::new(*ptr) } + unsafe fn from_ptr(ptr: NonZero<*const LeafNode<K, V>>) -> Self { + BoxedNode { ptr: Unique::new(*ptr as *mut LeafNode<K, V>) } } - fn as_ptr(&self) -> NonZero<*mut LeafNode<K, V>> { + fn as_ptr(&self) -> NonZero<*const LeafNode<K, V>> { unsafe { - NonZero::new(*self.ptr) + NonZero::new(*self.ptr as *const LeafNode<K, V>) } } } @@ -209,6 +209,11 @@ impl<K, V> Root<K, V> { } } +// N.B. `NodeRef` is always covariant in `K` and `V`, even when the `BorrowType` +// is `Mut`. This is technically wrong, but cannot result in any unsafety due to +// internal use of `NodeRef` because we stay completely generic over `K` and `V`. +// However, whenever a public type wraps `NodeRef`, make sure that it has the +// correct variance. /// A reference to a node. /// /// This type has a number of paramaters that controls how it acts: @@ -223,8 +228,8 @@ impl<K, V> Root<K, V> { /// `NodeRef` could be pointing to either type of node. pub struct NodeRef<BorrowType, K, V, Type> { height: usize, - node: NonZero<*mut LeafNode<K, V>>, - root: *mut Root<K, V>, + node: NonZero<*const LeafNode<K, V>>, + root: *const Root<K, V>, _marker: PhantomData<(BorrowType, Type)> } @@ -401,7 +406,7 @@ impl<'a, K, V, Type> NodeRef<marker::Mut<'a>, K, V, Type> { fn as_leaf_mut(&mut self) -> &mut LeafNode<K, V> { unsafe { - &mut **self.node + &mut *(*self.node as *mut LeafNode<K, V>) } } @@ -434,7 +439,7 @@ impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Immut<'a>, K, V, Type> { impl<'a, K: 'a, V: 'a, Type> NodeRef<marker::Mut<'a>, K, V, Type> { pub fn into_root_mut(self) -> &'a mut Root<K, V> { unsafe { - &mut *self.root + &mut *(self.root as *mut Root<K, V>) } } diff --git a/src/libcollectionstest/btree/map.rs b/src/libcollectionstest/btree/map.rs index c4473b64066..05d4aff108a 100644 --- a/src/libcollectionstest/btree/map.rs +++ b/src/libcollectionstest/btree/map.rs @@ -378,6 +378,22 @@ fn test_clone() { } } +#[test] +fn test_variance() { + use std::collections::btree_map::{Iter, IntoIter, Range, Keys, Values}; + + fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> { v } + fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> { v } + fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> { v } + fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> { v } + fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> { v } + fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> { v } + fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> { v } + fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> { v } + fn keys<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> { v } + fn vals<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> { v } +} + mod bench { use std::collections::BTreeMap; use std::__rand::{Rng, thread_rng}; diff --git a/src/test/compile-fail/variance-btree-invariant-types.rs b/src/test/compile-fail/variance-btree-invariant-types.rs new file mode 100644 index 00000000000..e9607de00a3 --- /dev/null +++ b/src/test/compile-fail/variance-btree-invariant-types.rs @@ -0,0 +1,63 @@ +// Copyright 2016 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +#![feature(rustc_attrs)] + +use std::collections::btree_map::{IterMut, OccupiedEntry, VacantEntry}; + +fn iter_cov_key<'a, 'new>(v: IterMut<'a, &'static (), ()>) -> IterMut<'a, &'new (), ()> { + v //~ ERROR mismatched types +} +fn iter_cov_val<'a, 'new>(v: IterMut<'a, (), &'static ()>) -> IterMut<'a, (), &'new ()> { + v //~ ERROR mismatched types +} +fn iter_contra_key<'a, 'new>(v: IterMut<'a, &'new (), ()>) -> IterMut<'a, &'static (), ()> { + v //~ ERROR mismatched types +} +fn iter_contra_val<'a, 'new>(v: IterMut<'a, (), &'new ()>) -> IterMut<'a, (), &'static ()> { + v //~ ERROR mismatched types +} + +fn occ_cov_key<'a, 'new>(v: OccupiedEntry<'a, &'static (), ()>) + -> OccupiedEntry<'a, &'new (), ()> { + v //~ ERROR mismatched types +} +fn occ_cov_val<'a, 'new>(v: OccupiedEntry<'a, (), &'static ()>) + -> OccupiedEntry<'a, (), &'new ()> { + v //~ ERROR mismatched types +} +fn occ_contra_key<'a, 'new>(v: OccupiedEntry<'a, &'new (), ()>) + -> OccupiedEntry<'a, &'static (), ()> { + v //~ ERROR mismatched types +} +fn occ_contra_val<'a, 'new>(v: OccupiedEntry<'a, (), &'new ()>) + -> OccupiedEntry<'a, (), &'static ()> { + v //~ ERROR mismatched types +} + +fn vac_cov_key<'a, 'new>(v: VacantEntry<'a, &'static (), ()>) + -> VacantEntry<'a, &'new (), ()> { + v //~ ERROR mismatched types +} +fn vac_cov_val<'a, 'new>(v: VacantEntry<'a, (), &'static ()>) + -> VacantEntry<'a, (), &'new ()> { + v //~ ERROR mismatched types +} +fn vac_contra_key<'a, 'new>(v: VacantEntry<'a, &'new (), ()>) + -> VacantEntry<'a, &'static (), ()> { + v //~ ERROR mismatched types +} +fn vac_contra_val<'a, 'new>(v: VacantEntry<'a, (), &'new ()>) + -> VacantEntry<'a, (), &'static ()> { + v //~ ERROR mismatched types +} + +#[rustc_error] +fn main() { } |