src/vendor/string_cache/src/atom.rs

   1 // Copyright 2014 The Servo Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution.
   3 //
   4 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   5 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   7 // option. This file may not be copied, modified, or distributed
   8 // except according to those terms.
   9
  10 #![allow(non_upper_case_globals)]
  11
  12 #[cfg(feature = "heapsize")]
  13 use heapsize::HeapSizeOf;
  14
  15 use phf_shared;
  16 use serde::{Deserialize, Deserializer, Serialize, Serializer};
  17
  18 use std::ascii::AsciiExt;
  19 use std::borrow::Cow;
  20 use std::cmp::Ordering::{self, Equal};
  21 use std::fmt;
  22 use std::hash::{Hash, Hasher};
  23 use std::marker::PhantomData;
  24 use std::mem;
  25 use std::ops;
  26 use std::slice;
  27 use std::str;
  28 use std::sync::Mutex;
  29 use std::sync::atomic::AtomicIsize;
  30 use std::sync::atomic::Ordering::SeqCst;
  31
  32 use shared::{STATIC_TAG, INLINE_TAG, DYNAMIC_TAG, TAG_MASK, MAX_INLINE_LEN, STATIC_SHIFT_BITS,
  33              ENTRY_ALIGNMENT, pack_static};
  34 use self::UnpackedAtom::{Dynamic, Inline, Static};
  35
  36 #[cfg(feature = "log-events")]
  37 use event::Event;
  38
  39 #[cfg(not(feature = "log-events"))]
  40 macro_rules! log (($e:expr) => (()));
  41
  42 const NB_BUCKETS: usize = 1 << 12;  // 4096
  43 const BUCKET_MASK: u64 = (1 << 12) - 1;
  44
  45 struct StringCache {
  46     buckets: [Option<Box<StringCacheEntry>>; NB_BUCKETS],
  47 }
  48
  49 #[cfg(feature = "heapsize")]
  50 impl HeapSizeOf for StringCache {
  51     fn heap_size_of_children(&self) -> usize {
  52         self.buckets.iter().fold(0, |size, bucket| size + bucket.heap_size_of_children())
  53     }
  54 }
  55
  56 lazy_static! {
  57     static ref STRING_CACHE: Mutex<StringCache> = Mutex::new(StringCache::new());
  58 }
  59
  60 /// A token that represents the heap used by the dynamic string cache.
  61 #[cfg(feature = "heapsize")]
  62 pub struct StringCacheHeap;
  63
  64 #[cfg(feature = "heapsize")]
  65 impl HeapSizeOf for StringCacheHeap {
  66     fn heap_size_of_children(&self) -> usize {
  67         STRING_CACHE.lock().unwrap().heap_size_of_children()
  68     }
  69 }
  70
  71 struct StringCacheEntry {
  72     next_in_bucket: Option<Box<StringCacheEntry>>,
  73     hash: u64,
  74     ref_count: AtomicIsize,
  75     string: Box<str>,
  76 }
  77
  78 #[cfg(feature = "heapsize")]
  79 impl HeapSizeOf for StringCacheEntry {
  80     fn heap_size_of_children(&self) -> usize {
  81         self.next_in_bucket.heap_size_of_children() +
  82         self.string.heap_size_of_children()
  83     }
  84 }
  85
  86 impl StringCacheEntry {
  87     fn new(next: Option<Box<StringCacheEntry>>, hash: u64, string: String)
  88            -> StringCacheEntry {
  89         StringCacheEntry {
  90             next_in_bucket: next,
  91             hash: hash,
  92             ref_count: AtomicIsize::new(1),
  93             string: string.into_boxed_str(),
  94         }
  95     }
  96 }
  97
  98 impl StringCache {
  99     fn new() -> StringCache {
 100         StringCache {
 101             buckets: unsafe { mem::zeroed() },
 102         }
 103     }
 104
 105     fn add(&mut self, string: Cow<str>, hash: u64) -> *mut StringCacheEntry {
 106         let bucket_index = (hash & BUCKET_MASK) as usize;
 107         {
 108             let mut ptr: Option<&mut Box<StringCacheEntry>> =
 109                 self.buckets[bucket_index].as_mut();
 110
 111             while let Some(entry) = ptr.take() {
 112                 if entry.hash == hash && &*entry.string == &*string {
 113                     if entry.ref_count.fetch_add(1, SeqCst) > 0 {
 114                         return &mut **entry;
 115                     }
 116                     // Uh-oh. The pointer's reference count was zero, which means someone may try
 117                     // to free it. (Naive attempts to defend against this, for example having the
 118                     // destructor check to see whether the reference count is indeed zero, don't
 119                     // work due to ABA.) Thus we need to temporarily add a duplicate string to the
 120                     // list.
 121                     entry.ref_count.fetch_sub(1, SeqCst);
 122                     break;
 123                 }
 124                 ptr = entry.next_in_bucket.as_mut();
 125             }
 126         }
 127         debug_assert!(mem::align_of::<StringCacheEntry>() >= ENTRY_ALIGNMENT);
 128         let string = string.into_owned();
 129         let _string_clone = if cfg!(feature = "log-events") {
 130             string.clone()
 131         } else {
 132             "".to_owned()
 133         };
 134         let mut entry = Box::new(StringCacheEntry::new(
 135             self.buckets[bucket_index].take(), hash, string));
 136         let ptr: *mut StringCacheEntry = &mut *entry;
 137         self.buckets[bucket_index] = Some(entry);
 138         log!(Event::Insert(ptr as u64, _string_clone));
 139
 140         ptr
 141     }
 142
 143     fn remove(&mut self, key: u64) {
 144         let ptr = key as *mut StringCacheEntry;
 145         let bucket_index = {
 146             let value: &StringCacheEntry = unsafe { &*ptr };
 147             debug_assert!(value.ref_count.load(SeqCst) == 0);
 148             (value.hash & BUCKET_MASK) as usize
 149         };
 150
 151
 152         let mut current: &mut Option<Box<StringCacheEntry>> = &mut self.buckets[bucket_index];
 153
 154         loop {
 155             let entry_ptr: *mut StringCacheEntry = match current.as_mut() {
 156                 Some(entry) => &mut **entry,
 157                 None => break,
 158             };
 159             if entry_ptr == ptr {
 160                 mem::drop(mem::replace(current, unsafe { (*entry_ptr).next_in_bucket.take() }));
 161                 break;
 162             }
 163             current = unsafe { &mut (*entry_ptr).next_in_bucket };
 164         }
 165
 166         log!(Event::Remove(key));
 167     }
 168 }
 169
 170 pub trait StaticAtomSet {
 171     fn get() -> &'static PhfStrSet;
 172     fn empty_string_index() -> u32;
 173 }
 174
 175 pub struct PhfStrSet {
 176     pub key: u64,
 177     pub disps: &'static [(u32, u32)],
 178     pub atoms: &'static [&'static str],
 179     pub hashes: &'static [u32],
 180 }
 181
 182 pub struct EmptyStaticAtomSet;
 183
 184 impl StaticAtomSet for EmptyStaticAtomSet {
 185     fn get() -> &'static PhfStrSet {
 186         // The name is a lie: this set is not empty (it contains the empty string)
 187         // but that’s only to avoid divisions by zero in rust-phf.
 188         static SET: PhfStrSet = PhfStrSet {
 189             key: 0,
 190             disps: &[(0, 0)],
 191             atoms: &[""],
 192             // "" SipHash'd, and xored with u64_hash_to_u32.
 193             hashes: &[0x3ddddef3],
 194         };
 195         &SET
 196     }
 197
 198     fn empty_string_index() -> u32 {
 199         0
 200     }
 201 }
 202
 203 /// Use this if you don’t care about static atoms.
 204 pub type DefaultAtom = Atom<EmptyStaticAtomSet>;
 205
 206 pub struct Atom<Static: StaticAtomSet> {
 207     /// This field is public so that the `atom!()` macros can use it.
 208     /// You should not otherwise access this field.
 209     #[doc(hidden)]
 210     pub unsafe_data: u64,
 211
 212     #[doc(hidden)]
 213     pub phantom: PhantomData<Static>,
 214 }
 215
 216 #[cfg(feature = "heapsize")]
 217 impl<Static: StaticAtomSet> HeapSizeOf for Atom<Static> {
 218     #[inline(always)]
 219     fn heap_size_of_children(&self) -> usize {
 220         0
 221     }
 222 }
 223
 224 impl<Static: StaticAtomSet> ::precomputed_hash::PrecomputedHash for Atom<Static> {
 225     fn precomputed_hash(&self) -> u32 {
 226         self.get_hash()
 227     }
 228 }
 229
 230 fn u64_hash_as_u32(h: u64) -> u32 {
 231     // This may or may not be great...
 232     ((h >> 32) ^ h) as u32
 233 }
 234
 235 impl<Static: StaticAtomSet> Atom<Static> {
 236     #[inline(always)]
 237     unsafe fn unpack(&self) -> UnpackedAtom {
 238         UnpackedAtom::from_packed(self.unsafe_data)
 239     }
 240
 241     pub fn get_hash(&self) -> u32 {
 242         match unsafe { self.unpack() } {
 243             Static(index) => {
 244                 let static_set = Static::get();
 245                 static_set.hashes[index as usize]
 246             }
 247             Dynamic(entry) => {
 248                 let entry = entry as *mut StringCacheEntry;
 249                 u64_hash_as_u32(unsafe { (*entry).hash })
 250             }
 251             Inline(..) => {
 252                 u64_hash_as_u32(self.unsafe_data)
 253             }
 254         }
 255     }
 256 }
 257
 258 impl<Static: StaticAtomSet> Default for Atom<Static> {
 259     #[inline]
 260     fn default() -> Self {
 261         Atom {
 262             unsafe_data: pack_static(Static::empty_string_index()),
 263             phantom: PhantomData
 264         }
 265     }
 266 }
 267
 268 impl<Static: StaticAtomSet> Hash for Atom<Static> {
 269     #[inline]
 270     fn hash<H>(&self, state: &mut H) where H: Hasher {
 271         state.write_u32(self.get_hash())
 272     }
 273 }
 274
 275 impl<Static: StaticAtomSet> Eq for Atom<Static> {}
 276
 277 // NOTE: This impl requires that a given string must always be interned the same way.
 278 impl<Static: StaticAtomSet> PartialEq for Atom<Static> {
 279     #[inline]
 280     fn eq(&self, other: &Self) -> bool {
 281         self.unsafe_data == other.unsafe_data
 282     }
 283 }
 284
 285 impl<Static: StaticAtomSet> PartialEq<str> for Atom<Static> {
 286     fn eq(&self, other: &str) -> bool {
 287         &self[..] == other
 288     }
 289 }
 290
 291 impl<Static: StaticAtomSet> PartialEq<Atom<Static>> for str {
 292     fn eq(&self, other: &Atom<Static>) -> bool {
 293         self == &other[..]
 294     }
 295 }
 296
 297 impl<Static: StaticAtomSet> PartialEq<String> for Atom<Static> {
 298     fn eq(&self, other: &String) -> bool {
 299         &self[..] == &other[..]
 300     }
 301 }
 302
 303 impl<'a, Static: StaticAtomSet> From<Cow<'a, str>> for Atom<Static> {
 304     #[inline]
 305     fn from(string_to_add: Cow<'a, str>) -> Self {
 306         let static_set = Static::get();
 307         let hash = phf_shared::hash(&*string_to_add, static_set.key);
 308         let index = phf_shared::get_index(hash, static_set.disps, static_set.atoms.len());
 309
 310         let unpacked = if static_set.atoms[index as usize] == string_to_add {
 311             Static(index)
 312         } else {
 313             let len = string_to_add.len();
 314             if len <= MAX_INLINE_LEN {
 315                 let mut buf: [u8; 7] = [0; 7];
 316                 buf[..len].copy_from_slice(string_to_add.as_bytes());
 317                 Inline(len as u8, buf)
 318             } else {
 319                 Dynamic(STRING_CACHE.lock().unwrap().add(string_to_add, hash) as *mut ())
 320             }
 321         };
 322
 323         let data = unsafe { unpacked.pack() };
 324         log!(Event::Intern(data));
 325         Atom { unsafe_data: data, phantom: PhantomData }
 326     }
 327 }
 328
 329 impl<'a, Static: StaticAtomSet> From<&'a str> for Atom<Static> {
 330     #[inline]
 331     fn from(string_to_add: &str) -> Self {
 332         Atom::from(Cow::Borrowed(string_to_add))
 333     }
 334 }
 335
 336 impl<Static: StaticAtomSet> From<String> for Atom<Static> {
 337     #[inline]
 338     fn from(string_to_add: String) -> Self {
 339         Atom::from(Cow::Owned(string_to_add))
 340     }
 341 }
 342
 343 impl<Static: StaticAtomSet> Clone for Atom<Static> {
 344     #[inline(always)]
 345     fn clone(&self) -> Self {
 346         unsafe {
 347             match from_packed_dynamic(self.unsafe_data) {
 348                 Some(entry) => {
 349                     let entry = entry as *mut StringCacheEntry;
 350                     (*entry).ref_count.fetch_add(1, SeqCst);
 351                 },
 352                 None => (),
 353             }
 354         }
 355         Atom {
 356             unsafe_data: self.unsafe_data,
 357             phantom: PhantomData,
 358         }
 359     }
 360 }
 361
 362 impl<Static: StaticAtomSet> Drop for Atom<Static> {
 363     #[inline]
 364     fn drop(&mut self) {
 365         // Out of line to guide inlining.
 366         fn drop_slow<Static: StaticAtomSet>(this: &mut Atom<Static>) {
 367             STRING_CACHE.lock().unwrap().remove(this.unsafe_data);
 368         }
 369
 370         unsafe {
 371             match from_packed_dynamic(self.unsafe_data) {
 372                 Some(entry) => {
 373                     let entry = entry as *mut StringCacheEntry;
 374                     if (*entry).ref_count.fetch_sub(1, SeqCst) == 1 {
 375                         drop_slow(self);
 376                     }
 377                 }
 378                 _ => (),
 379             }
 380         }
 381     }
 382 }
 383
 384 impl<Static: StaticAtomSet> ops::Deref for Atom<Static> {
 385     type Target = str;
 386
 387     #[inline]
 388     fn deref(&self) -> &str {
 389         unsafe {
 390             match self.unpack() {
 391                 Inline(..) => {
 392                     let buf = inline_orig_bytes(&self.unsafe_data);
 393                     str::from_utf8_unchecked(buf)
 394                 },
 395                 Static(idx) => Static::get().atoms.get(idx as usize).expect("bad static atom"),
 396                 Dynamic(entry) => {
 397                     let entry = entry as *mut StringCacheEntry;
 398                     &(*entry).string
 399                 }
 400             }
 401         }
 402     }
 403 }
 404
 405 impl<Static: StaticAtomSet> fmt::Display for Atom<Static> {
 406     #[inline]
 407     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 408         <str as fmt::Display>::fmt(self, f)
 409     }
 410 }
 411
 412 impl<Static: StaticAtomSet> fmt::Debug for Atom<Static> {
 413     #[inline]
 414     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 415         let ty_str = unsafe {
 416             match self.unpack() {
 417                 Dynamic(..) => "dynamic",
 418                 Inline(..) => "inline",
 419                 Static(..) => "static",
 420             }
 421         };
 422
 423         write!(f, "Atom('{}' type={})", &*self, ty_str)
 424     }
 425 }
 426
 427 impl<Static: StaticAtomSet> PartialOrd for Atom<Static> {
 428     #[inline]
 429     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 430         if self.unsafe_data == other.unsafe_data {
 431             return Some(Equal);
 432         }
 433         self.as_ref().partial_cmp(other.as_ref())
 434     }
 435 }
 436
 437 impl<Static: StaticAtomSet> Ord for Atom<Static> {
 438     #[inline]
 439     fn cmp(&self, other: &Self) -> Ordering {
 440         if self.unsafe_data == other.unsafe_data {
 441             return Equal;
 442         }
 443         self.as_ref().cmp(other.as_ref())
 444     }
 445 }
 446
 447 impl<Static: StaticAtomSet> AsRef<str> for Atom<Static> {
 448     fn as_ref(&self) -> &str {
 449         &self
 450     }
 451 }
 452
 453 impl<Static: StaticAtomSet> Serialize for Atom<Static> {
 454     fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error> where S: Serializer {
 455         let string: &str = self.as_ref();
 456         string.serialize(serializer)
 457     }
 458 }
 459
 460 impl<'a, Static: StaticAtomSet> Deserialize<'a> for Atom<Static> {
 461     fn deserialize<D>(deserializer: D) -> Result<Self, D::Error> where D: Deserializer<'a> {
 462         let string: String = try!(Deserialize::deserialize(deserializer));
 463         Ok(Atom::from(string))
 464     }
 465 }
 466
 467 // AsciiExt requires mutating methods, so we just implement the non-mutating ones.
 468 // We don't need to implement is_ascii because there's no performance improvement
 469 // over the one from &str.
 470 impl<Static: StaticAtomSet> Atom<Static> {
 471     fn from_mutated_str<F: FnOnce(&mut str)>(s: &str, f: F) -> Self {
 472         let mut buffer: [u8; 64] = unsafe { mem::uninitialized() };
 473         if let Some(buffer_prefix) = buffer.get_mut(..s.len()) {
 474             buffer_prefix.copy_from_slice(s.as_bytes());
 475             // FIXME: use from std::str when stable https://github.com/rust-lang/rust/issues/41119
 476             pub unsafe fn from_utf8_unchecked_mut(v: &mut [u8]) -> &mut str {
 477                 mem::transmute(v)
 478             }
 479             let as_str = unsafe { from_utf8_unchecked_mut(buffer_prefix) };
 480             f(as_str);
 481             Atom::from(&*as_str)
 482         } else {
 483             let mut string = s.to_owned();
 484             f(&mut string);
 485             Atom::from(string)
 486         }
 487     }
 488
 489     pub fn to_ascii_uppercase(&self) -> Self {
 490         for (i, b) in self.bytes().enumerate() {
 491             if let b'a' ... b'z' = b {
 492                 return Atom::from_mutated_str(self, |s| s[i..].make_ascii_uppercase())
 493             }
 494         }
 495         self.clone()
 496     }
 497
 498     pub fn to_ascii_lowercase(&self) -> Self {
 499         for (i, b) in self.bytes().enumerate() {
 500             if let b'A' ... b'Z' = b {
 501                 return Atom::from_mutated_str(self, |s| s[i..].make_ascii_lowercase())
 502             }
 503         }
 504         self.clone()
 505     }
 506
 507     pub fn eq_ignore_ascii_case(&self, other: &Self) -> bool {
 508         (self == other) || self.eq_str_ignore_ascii_case(&**other)
 509     }
 510
 511     pub fn eq_str_ignore_ascii_case(&self, other: &str) -> bool {
 512         (&**self).eq_ignore_ascii_case(other)
 513     }
 514 }
 515
 516 // Atoms use a compact representation which fits this enum in a single u64.
 517 // Inlining avoids actually constructing the unpacked representation in memory.
 518 #[allow(missing_copy_implementations)]
 519 enum UnpackedAtom {
 520     /// Pointer to a dynamic table entry.  Must be 16-byte aligned!
 521     Dynamic(*mut ()),
 522
 523     /// Length + bytes of string.
 524     Inline(u8, [u8; 7]),
 525
 526     /// Index in static interning table.
 527     Static(u32),
 528 }
 529
 530 #[inline(always)]
 531 fn inline_atom_slice(x: &u64) -> &[u8] {
 532     unsafe {
 533         let x: *const u64 = x;
 534         let mut data = x as *const u8;
 535         // All except the lowest byte, which is first in little-endian, last in big-endian.
 536         if cfg!(target_endian = "little") {
 537             data = data.offset(1);
 538         }
 539         let len = 7;
 540         slice::from_raw_parts(data, len)
 541     }
 542 }
 543
 544 #[inline(always)]
 545 fn inline_atom_slice_mut(x: &mut u64) -> &mut [u8] {
 546     unsafe {
 547         let x: *mut u64 = x;
 548         let mut data = x as *mut u8;
 549         // All except the lowest byte, which is first in little-endian, last in big-endian.
 550         if cfg!(target_endian = "little") {
 551             data = data.offset(1);
 552         }
 553         let len = 7;
 554         slice::from_raw_parts_mut(data, len)
 555     }
 556 }
 557
 558 impl UnpackedAtom {
 559     #[inline(always)]
 560     unsafe fn pack(self) -> u64 {
 561         match self {
 562             Static(n) => pack_static(n),
 563             Dynamic(p) => {
 564                 let n = p as u64;
 565                 debug_assert!(0 == n & TAG_MASK);
 566                 n
 567             }
 568             Inline(len, buf) => {
 569                 debug_assert!((len as usize) <= MAX_INLINE_LEN);
 570                 let mut data: u64 = (INLINE_TAG as u64) | ((len as u64) << 4);
 571                 {
 572                     let dest = inline_atom_slice_mut(&mut data);
 573                     dest.copy_from_slice(&buf)
 574                 }
 575                 data
 576             }
 577         }
 578     }
 579
 580     #[inline(always)]
 581     unsafe fn from_packed(data: u64) -> UnpackedAtom {
 582         debug_assert!(DYNAMIC_TAG == 0); // Dynamic is untagged
 583
 584         match (data & TAG_MASK) as u8 {
 585             DYNAMIC_TAG => Dynamic(data as *mut ()),
 586             STATIC_TAG => Static((data >> STATIC_SHIFT_BITS) as u32),
 587             INLINE_TAG => {
 588                 let len = ((data & 0xf0) >> 4) as usize;
 589                 debug_assert!(len <= MAX_INLINE_LEN);
 590                 let mut buf: [u8; 7] = [0; 7];
 591                 let src = inline_atom_slice(&data);
 592                 buf.copy_from_slice(src);
 593                 Inline(len as u8, buf)
 594             },
 595             _ => debug_unreachable!(),
 596         }
 597     }
 598 }
 599
 600 /// Used for a fast path in Clone and Drop.
 601 #[inline(always)]
 602 unsafe fn from_packed_dynamic(data: u64) -> Option<*mut ()> {
 603     if (DYNAMIC_TAG as u64) == (data & TAG_MASK) {
 604         Some(data as *mut ())
 605     } else {
 606         None
 607     }
 608 }
 609
 610 /// For as_slice on inline atoms, we need a pointer into the original
 611 /// string contents.
 612 ///
 613 /// It's undefined behavior to call this on a non-inline atom!!
 614 #[inline(always)]
 615 unsafe fn inline_orig_bytes<'a>(data: &'a u64) -> &'a [u8] {
 616     match UnpackedAtom::from_packed(*data) {
 617         Inline(len, _) => {
 618             let src = inline_atom_slice(&data);
 619             &src[..(len as usize)]
 620         }
 621         _ => debug_unreachable!(),
 622     }
 623 }
 624
 625 #[cfg(test)]
 626 #[macro_use]
 627 mod tests {
 628     use std::mem;
 629     use std::thread;
 630     use super::{StaticAtomSet, StringCacheEntry};
 631     use super::UnpackedAtom::{Dynamic, Inline, Static};
 632     use shared::ENTRY_ALIGNMENT;
 633
 634     include!(concat!(env!("OUT_DIR"), "/test_atom.rs"));
 635     pub type Atom = TestAtom;
 636
 637     #[test]
 638     fn test_as_slice() {
 639         let s0 = Atom::from("");
 640         assert!(s0.as_ref() == "");
 641
 642         let s1 = Atom::from("class");
 643         assert!(s1.as_ref() == "class");
 644
 645         let i0 = Atom::from("blah");
 646         assert!(i0.as_ref() == "blah");
 647
 648         let s0 = Atom::from("BLAH");
 649         assert!(s0.as_ref() == "BLAH");
 650
 651         let d0 = Atom::from("zzzzzzzzzz");
 652         assert!(d0.as_ref() == "zzzzzzzzzz");
 653
 654         let d1 = Atom::from("ZZZZZZZZZZ");
 655         assert!(d1.as_ref() == "ZZZZZZZZZZ");
 656     }
 657
 658     macro_rules! unpacks_to (($e:expr, $t:pat) => (
 659         match unsafe { Atom::from($e).unpack() } {
 660             $t => (),
 661             _ => panic!("atom has wrong type"),
 662         }
 663     ));
 664
 665     #[test]
 666     fn test_types() {
 667         unpacks_to!("", Static(..));
 668         unpacks_to!("id", Static(..));
 669         unpacks_to!("body", Static(..));
 670         unpacks_to!("c", Inline(..)); // "z" is a static atom
 671         unpacks_to!("zz", Inline(..));
 672         unpacks_to!("zzz", Inline(..));
 673         unpacks_to!("zzzz", Inline(..));
 674         unpacks_to!("zzzzz", Inline(..));
 675         unpacks_to!("zzzzzz", Inline(..));
 676         unpacks_to!("zzzzzzz", Inline(..));
 677         unpacks_to!("zzzzzzzz", Dynamic(..));
 678         unpacks_to!("zzzzzzzzzzzzz", Dynamic(..));
 679     }
 680
 681     #[test]
 682     fn test_equality() {
 683         let s0 = Atom::from("fn");
 684         let s1 = Atom::from("fn");
 685         let s2 = Atom::from("loop");
 686
 687         let i0 = Atom::from("blah");
 688         let i1 = Atom::from("blah");
 689         let i2 = Atom::from("blah2");
 690
 691         let d0 = Atom::from("zzzzzzzz");
 692         let d1 = Atom::from("zzzzzzzz");
 693         let d2 = Atom::from("zzzzzzzzz");
 694
 695         assert!(s0 == s1);
 696         assert!(s0 != s2);
 697
 698         assert!(i0 == i1);
 699         assert!(i0 != i2);
 700
 701         assert!(d0 == d1);
 702         assert!(d0 != d2);
 703
 704         assert!(s0 != i0);
 705         assert!(s0 != d0);
 706         assert!(i0 != d0);
 707     }
 708
 709     #[test]
 710     fn default() {
 711         assert_eq!(TestAtom::default(), test_atom!(""));
 712         assert_eq!(&*TestAtom::default(), "");
 713     }
 714
 715     #[test]
 716     fn ord() {
 717         fn check(x: &str, y: &str) {
 718             assert_eq!(x < y, Atom::from(x) < Atom::from(y));
 719             assert_eq!(x.cmp(y), Atom::from(x).cmp(&Atom::from(y)));
 720             assert_eq!(x.partial_cmp(y), Atom::from(x).partial_cmp(&Atom::from(y)));
 721         }
 722
 723         check("a", "body");
 724         check("asdf", "body");
 725         check("zasdf", "body");
 726         check("z", "body");
 727
 728         check("a", "bbbbb");
 729         check("asdf", "bbbbb");
 730         check("zasdf", "bbbbb");
 731         check("z", "bbbbb");
 732     }
 733
 734     #[test]
 735     fn clone() {
 736         let s0 = Atom::from("fn");
 737         let s1 = s0.clone();
 738         let s2 = Atom::from("loop");
 739
 740         let i0 = Atom::from("blah");
 741         let i1 = i0.clone();
 742         let i2 = Atom::from("blah2");
 743
 744         let d0 = Atom::from("zzzzzzzz");
 745         let d1 = d0.clone();
 746         let d2 = Atom::from("zzzzzzzzz");
 747
 748         assert!(s0 == s1);
 749         assert!(s0 != s2);
 750
 751         assert!(i0 == i1);
 752         assert!(i0 != i2);
 753
 754         assert!(d0 == d1);
 755         assert!(d0 != d2);
 756
 757         assert!(s0 != i0);
 758         assert!(s0 != d0);
 759         assert!(i0 != d0);
 760     }
 761
 762     macro_rules! assert_eq_fmt (($fmt:expr, $x:expr, $y:expr) => ({
 763         let x = $x;
 764         let y = $y;
 765         if x != y {
 766             panic!("assertion failed: {} != {}",
 767                 format_args!($fmt, x),
 768                 format_args!($fmt, y));
 769         }
 770     }));
 771
 772     #[test]
 773     fn repr() {
 774         fn check(s: &str, data: u64) {
 775             assert_eq_fmt!("0x{:016X}", Atom::from(s).unsafe_data, data);
 776         }
 777
 778         fn check_static(s: &str, x: Atom) {
 779             assert_eq_fmt!("0x{:016X}", x.unsafe_data, Atom::from(s).unsafe_data);
 780             assert_eq!(0x2, x.unsafe_data & 0xFFFF_FFFF);
 781             // The index is unspecified by phf.
 782             assert!((x.unsafe_data >> 32) <= TestAtomStaticSet::get().atoms.len() as u64);
 783         }
 784
 785         // This test is here to make sure we don't change atom representation
 786         // by accident.  It may need adjusting if there are changes to the
 787         // static atom table, the tag values, etc.
 788
 789         // Static atoms
 790         check_static("a",       test_atom!("a"));
 791         check_static("address", test_atom!("address"));
 792         check_static("area",    test_atom!("area"));
 793
 794         // Inline atoms
 795         check("e",       0x0000_0000_0000_6511);
 796         check("xyzzy",   0x0000_797A_7A79_7851);
 797         check("xyzzy01", 0x3130_797A_7A79_7871);
 798
 799         // Dynamic atoms. This is a pointer so we can't verify every bit.
 800         assert_eq!(0x00, Atom::from("a dynamic string").unsafe_data & 0xf);
 801     }
 802
 803     #[test]
 804     fn assert_sizes() {
 805         use std::mem;
 806         struct EmptyWithDrop;
 807         impl Drop for EmptyWithDrop {
 808             fn drop(&mut self) {}
 809         }
 810         let compiler_uses_inline_drop_flags = mem::size_of::<EmptyWithDrop>() > 0;
 811
 812         // Guard against accidental changes to the sizes of things.
 813         assert_eq!(mem::size_of::<Atom>(),
 814                    if compiler_uses_inline_drop_flags { 16 } else { 8 });
 815         assert_eq!(mem::size_of::<super::StringCacheEntry>(),
 816                    8 + 4 * mem::size_of::<usize>());
 817     }
 818
 819     #[test]
 820     fn test_threads() {
 821         for _ in 0_u32..100 {
 822             thread::spawn(move || {
 823                 let _ = Atom::from("a dynamic string");
 824                 let _ = Atom::from("another string");
 825             });
 826         }
 827     }
 828
 829     #[test]
 830     fn atom_macro() {
 831         assert_eq!(test_atom!("body"), Atom::from("body"));
 832         assert_eq!(test_atom!("font-weight"), Atom::from("font-weight"));
 833     }
 834
 835     #[test]
 836     fn match_atom() {
 837         assert_eq!(2, match Atom::from("head") {
 838             test_atom!("br") => 1,
 839             test_atom!("html") | test_atom!("head") => 2,
 840             _ => 3,
 841         });
 842
 843         assert_eq!(3, match Atom::from("body") {
 844             test_atom!("br") => 1,
 845             test_atom!("html") | test_atom!("head") => 2,
 846             _ => 3,
 847         });
 848
 849         assert_eq!(3, match Atom::from("zzzzzz") {
 850             test_atom!("br") => 1,
 851             test_atom!("html") | test_atom!("head") => 2,
 852             _ => 3,
 853         });
 854     }
 855
 856     #[test]
 857     fn ensure_deref() {
 858         // Ensure we can Deref to a &str
 859         let atom = Atom::from("foobar");
 860         let _: &str = &atom;
 861     }
 862
 863     #[test]
 864     fn ensure_as_ref() {
 865         // Ensure we can as_ref to a &str
 866         let atom = Atom::from("foobar");
 867         let _: &str = atom.as_ref();
 868     }
 869
 870     #[test]
 871     fn string_cache_entry_alignment_is_sufficient() {
 872         assert!(mem::align_of::<StringCacheEntry>() >= ENTRY_ALIGNMENT);
 873     }
 874
 875     #[test]
 876     fn test_ascii_lowercase() {
 877         assert_eq!(Atom::from("").to_ascii_lowercase(), Atom::from(""));
 878         assert_eq!(Atom::from("aZ9").to_ascii_lowercase(), Atom::from("az9"));
 879         assert_eq!(Atom::from("The Quick Brown Fox!").to_ascii_lowercase(), Atom::from("the quick brown fox!"));
 880         assert_eq!(Atom::from("JE VAIS À PARIS").to_ascii_lowercase(), Atom::from("je vais À paris"));
 881     }
 882
 883     #[test]
 884     fn test_ascii_uppercase() {
 885         assert_eq!(Atom::from("").to_ascii_uppercase(), Atom::from(""));
 886         assert_eq!(Atom::from("aZ9").to_ascii_uppercase(), Atom::from("AZ9"));
 887         assert_eq!(Atom::from("The Quick Brown Fox!").to_ascii_uppercase(), Atom::from("THE QUICK BROWN FOX!"));
 888         assert_eq!(Atom::from("Je vais à Paris").to_ascii_uppercase(), Atom::from("JE VAIS à PARIS"));
 889     }
 890
 891     #[test]
 892     fn test_eq_ignore_ascii_case() {
 893         assert!(Atom::from("").eq_ignore_ascii_case(&Atom::from("")));
 894         assert!(Atom::from("aZ9").eq_ignore_ascii_case(&Atom::from("aZ9")));
 895         assert!(Atom::from("aZ9").eq_ignore_ascii_case(&Atom::from("Az9")));
 896         assert!(Atom::from("The Quick Brown Fox!").eq_ignore_ascii_case(&Atom::from("THE quick BROWN fox!")));
 897         assert!(Atom::from("Je vais à Paris").eq_ignore_ascii_case(&Atom::from("je VAIS à PARIS")));
 898         assert!(!Atom::from("").eq_ignore_ascii_case(&Atom::from("az9")));
 899         assert!(!Atom::from("aZ9").eq_ignore_ascii_case(&Atom::from("")));
 900         assert!(!Atom::from("aZ9").eq_ignore_ascii_case(&Atom::from("9Za")));
 901         assert!(!Atom::from("The Quick Brown Fox!").eq_ignore_ascii_case(&Atom::from("THE quick BROWN fox!!")));
 902         assert!(!Atom::from("Je vais à Paris").eq_ignore_ascii_case(&Atom::from("JE vais À paris")));
 903     }
 904
 905     #[test]
 906     fn test_from_string() {
 907         assert!(Atom::from("camembert".to_owned()) == Atom::from("camembert"));
 908     }
 909 }
 910
 911 #[cfg(all(test, feature = "unstable"))]
 912 #[path = "bench.rs"]
 913 mod bench;