1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
//! 切片原始类型的实用工具。
//!
//! *[See also the slice primitive type](slice).*
//!
//! 该模块中的大部分结构体都是迭代器类型,只能使用某个函数创建。
//! 例如,`slice.iter()` 产生一个 [`Iter`]。
//!
//! 提供了一些函数来从值引用或裸指针创建切片。
//!
#![stable(feature = "rust1", since = "1.0.0")]
// 该模块中的许多用法仅在测试配置中使用。
// 仅关闭 unused_imports 警告比解决它们更干净。
#![cfg_attr(test, allow(unused_imports, dead_code))]

use core::borrow::{Borrow, BorrowMut};
#[cfg(not(no_global_oom_handling))]
use core::cmp::Ordering::{self, Less};
#[cfg(not(no_global_oom_handling))]
use core::mem::{self, SizedTypeProperties};
#[cfg(not(no_global_oom_handling))]
use core::ptr;
#[cfg(not(no_global_oom_handling))]
use core::slice::sort;

use crate::alloc::Allocator;
#[cfg(not(no_global_oom_handling))]
use crate::alloc::{self, Global};
#[cfg(not(no_global_oom_handling))]
use crate::borrow::ToOwned;
use crate::boxed::Box;
use crate::vec::Vec;

#[cfg(test)]
mod tests;

#[unstable(feature = "slice_range", issue = "76393")]
pub use core::slice::range;
#[unstable(feature = "array_chunks", issue = "74985")]
pub use core::slice::ArrayChunks;
#[unstable(feature = "array_chunks", issue = "74985")]
pub use core::slice::ArrayChunksMut;
#[unstable(feature = "array_windows", issue = "75027")]
pub use core::slice::ArrayWindows;
#[stable(feature = "inherent_ascii_escape", since = "1.60.0")]
pub use core::slice::EscapeAscii;
#[stable(feature = "slice_get_slice", since = "1.28.0")]
pub use core::slice::SliceIndex;
#[stable(feature = "from_ref", since = "1.28.0")]
pub use core::slice::{from_mut, from_ref};
#[unstable(feature = "slice_from_ptr_range", issue = "89792")]
pub use core::slice::{from_mut_ptr_range, from_ptr_range};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{from_raw_parts, from_raw_parts_mut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{Chunks, Windows};
#[stable(feature = "chunks_exact", since = "1.31.0")]
pub use core::slice::{ChunksExact, ChunksExactMut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{ChunksMut, Split, SplitMut};
#[unstable(feature = "slice_group_by", issue = "80552")]
pub use core::slice::{GroupBy, GroupByMut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{Iter, IterMut};
#[stable(feature = "rchunks", since = "1.31.0")]
pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
#[stable(feature = "slice_rsplit", since = "1.27.0")]
pub use core::slice::{RSplit, RSplitMut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut};
#[stable(feature = "split_inclusive", since = "1.51.0")]
pub use core::slice::{SplitInclusive, SplitInclusiveMut};

////////////////////////////////////////////////////////////////////////////////
// 基本切片扩展方法
////////////////////////////////////////////////////////////////////////////////

// HACK(japaric) 在测试 NB 期间需要实现 `vec!` 宏,请参阅此文件中的 `hack` 模块以获取更多详细信息。
//
#[cfg(test)]
pub use hack::into_vec;

// HACK(japaric) 在测试 NB 期间需要实现 `Vec::clone`,请参阅此文件中的 `hack` 模块以获取更多详细信息。
//
#[cfg(test)]
pub use hack::to_vec;

// HACK(japaric): cfg(test) `impl [T]` 不可用,这三个函数实际上是 `impl [T]` 中的方法,`core::slice::SliceExt` 中没有 - 我们需要为 `test_permutations` 测试提供这些函数
//
//
//
pub(crate) mod hack {
    use core::alloc::Allocator;

    use crate::boxed::Box;
    use crate::vec::Vec;

    // 我们不应该向此属性添加内联属性,因为该属性主要在 `vec!` 宏中使用,并且会导致性能下降。
    // 有关讨论和性能结果,请参见 #71204。
    //
    pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> {
        unsafe {
            let len = b.len();
            let (b, alloc) = Box::into_raw_with_allocator(b);
            Vec::from_raw_parts_in(b as *mut T, len, len, alloc)
        }
    }

    #[cfg(not(no_global_oom_handling))]
    #[inline]
    pub fn to_vec<T: ConvertVec, A: Allocator>(s: &[T], alloc: A) -> Vec<T, A> {
        T::to_vec(s, alloc)
    }

    #[cfg(not(no_global_oom_handling))]
    pub trait ConvertVec {
        fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A>
        where
            Self: Sized;
    }

    #[cfg(not(no_global_oom_handling))]
    impl<T: Clone> ConvertVec for T {
        #[inline]
        default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
            struct DropGuard<'a, T, A: Allocator> {
                vec: &'a mut Vec<T, A>,
                num_init: usize,
            }
            impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
                #[inline]
                fn drop(&mut self) {
                    // SAFETY:
                    // 项在下面的循环中被标记为已初始化
                    unsafe {
                        self.vec.set_len(self.num_init);
                    }
                }
            }
            let mut vec = Vec::with_capacity_in(s.len(), alloc);
            let mut guard = DropGuard { vec: &mut vec, num_init: 0 };
            let slots = guard.vec.spare_capacity_mut();
            // .take(slots.len()) 是 LLVM 删除边界检查所必需的,并且具有比 zip 更好的 codegen。
            //
            for (i, b) in s.iter().enumerate().take(slots.len()) {
                guard.num_init = i;
                slots[i].write(b.clone());
            }
            core::mem::forget(guard);
            // SAFETY:
            // vec 的分配和初始化至少要达到此长度。
            unsafe {
                vec.set_len(s.len());
            }
            vec
        }
    }

    #[cfg(not(no_global_oom_handling))]
    impl<T: Copy> ConvertVec for T {
        #[inline]
        fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
            let mut v = Vec::with_capacity_in(s.len(), alloc);
            // SAFETY:
            // 在上面分配了 `s` 的容量,并在下面的 ptr::copy_to_non_overlapping 中初始化为 `s.len()`。
            //
            unsafe {
                s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len());
                v.set_len(s.len());
            }
            v
        }
    }
}

#[cfg(not(test))]
impl<T> [T] {
    /// 对切片进行排序。
    ///
    /// 这种排序是稳定的 (即,不对相等的元素重新排序),并且 *O*(*n*\*log(* n*)) 最坏的情况)。
    ///
    /// 在适用时,首选不稳定排序,因为它通常比稳定排序快,并且不分配辅助内存。
    /// 请参见 [`sort_unstable`](slice::sort_unstable)。
    ///
    /// # 当前实现
    ///
    /// 当前的算法是一种受 [timsort](https://en.wikipedia.org/wiki/Timsort) 启发的自适应迭代合并排序。
    /// 在切片几乎被排序或由两个或多个依次连接的排序序列组成的情况下,它设计得非常快。
    ///
    ///
    /// 同样,它分配临时存储空间的大小是 `self` 的一半,但是对于短片,则使用非分配插入排序。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [-5, 4, 1, -3, 2];
    ///
    /// v.sort();
    /// assert!(v == [-5, -3, 1, 2, 4]);
    /// ```
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn sort(&mut self)
    where
        T: Ord,
    {
        stable_sort(self, T::lt);
    }

    /// 用比较器函数对切片进行排序。
    ///
    /// 这种排序是稳定的 (即,不对相等的元素重新排序),并且 *O*(*n*\*log(* n*)) 最坏的情况)。
    ///
    /// 比较器函数必须为切片中的元素定义总顺序。如果排序不全,则元素的顺序是未指定的。
    /// 如果一个顺序是 (对于所有的`a`, `b` 和 `c`),那么它就是一个总体顺序
    ///
    /// * 完全和反对称的: `a < b`,`a == b` 或 `a > b` 之一正确,并且
    /// * 可传递的,`a < b` 和 `b < c` 表示 `a < c`。`==` 和 `>` 必须保持相同。
    ///
    /// 例如,虽然 [`f64`] 由于 `NaN != NaN` 而不实现 [`Ord`],但是当我们知道切片不包含 `NaN` 时,可以将 `partial_cmp` 用作我们的排序函数。
    ///
    ///
    /// ```
    /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
    /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
    /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
    /// ```
    ///
    /// 在适用时,首选不稳定排序,因为它通常比稳定排序快,并且不分配辅助内存。
    /// 请参见 [`sort_unstable_by`](slice::sort_unstable_by)。
    ///
    /// # 当前实现
    ///
    /// 当前的算法是一种受 [timsort](https://en.wikipedia.org/wiki/Timsort) 启发的自适应迭代合并排序。
    /// 在切片几乎被排序或由两个或多个依次连接的排序序列组成的情况下,它设计得非常快。
    ///
    /// 同样,它分配临时存储空间的大小是 `self` 的一半,但是对于短片,则使用非分配插入排序。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [5, 4, 1, 3, 2];
    /// v.sort_by(|a, b| a.cmp(b));
    /// assert!(v == [1, 2, 3, 4, 5]);
    ///
    /// // 反向排序
    /// v.sort_by(|a, b| b.cmp(a));
    /// assert!(v == [5, 4, 3, 2, 1]);
    /// ```
    ///
    ///
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn sort_by<F>(&mut self, mut compare: F)
    where
        F: FnMut(&T, &T) -> Ordering,
    {
        stable_sort(self, |a, b| compare(a, b) == Less);
    }

    /// 用键提取函数对切片进行排序。
    ///
    /// 这种排序是稳定的 (即,不对相等的元素重新排序),并且是 *O*(*m*\* * n *\* log(*n*)) 最坏的情况,其中键函数为 *O*(*m*)。
    ///
    /// 对于昂贵的键函数 (例如
    /// 不是简单的属性访问或基本操作的函数),[`sort_by_cached_key`](slice::sort_by_cached_key) 可能会显着提高速度,因为它不会重新计算元素键。
    ///
    ///
    /// 在适用时,首选不稳定排序,因为它通常比稳定排序快,并且不分配辅助内存。
    /// 请参见 [`sort_unstable_by_key`](slice::sort_unstable_by_key)。
    ///
    /// # 当前实现
    ///
    /// 当前的算法是一种受 [timsort](https://en.wikipedia.org/wiki/Timsort) 启发的自适应迭代合并排序。
    /// 在切片几乎被排序或由两个或多个依次连接的排序序列组成的情况下,它设计得非常快。
    ///
    /// 同样,它分配临时存储空间的大小是 `self` 的一半,但是对于短片,则使用非分配插入排序。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [-5i32, 4, 1, -3, 2];
    ///
    /// v.sort_by_key(|k| k.abs());
    /// assert!(v == [1, 2, -3, 4, -5]);
    /// ```
    ///
    ///
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
    #[inline]
    pub fn sort_by_key<K, F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
        stable_sort(self, |a, b| f(a).lt(&f(b)));
    }

    /// 用键提取函数对切片进行排序。
    ///
    /// 在排序过程中,每个元素最多调用一次 key 函数,通过使用临时存储来记住 key 评估的结果。
    /// 对 key 函数的调用顺序是未指定的,并且在标准库的未来版本中可能会发生变化。
    ///
    /// 这种排序是稳定的 (即,不对相等的元素重新排序),并且 *O*(*m*\* * n *+* n *\* log(*n*)) 最坏的情况是,其中键函数为 *O*(*m*)。
    ///
    /// 对于简单的键函数 (例如,作为属性访问或基本操作的函数),[`sort_by_key`](slice::sort_by_key) 可能会更快。
    ///
    /// # 当前实现
    ///
    /// 当前算法基于 Orson Peters 的 [pattern-defeating 的快速排序][pdqsort],该算法将随机快速排序的快速平均情况与堆排序的快速最坏情况相结合,同时在具有特定模式的切片上实现了线性时间。
    /// 它使用一些随机化来避免退化的情况,但是使用固定的 seed 来始终提供确定性的行为。
    ///
    /// 在最坏的情况下,该算法在 `Vec<(K, usize)>` 中分配切片长度的临时存储。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [-5i32, 4, 32, -3, 2];
    ///
    /// v.sort_by_cached_key(|k| k.to_string());
    /// assert!(v == [-3, -5, 2, 32, 4]);
    /// ```
    ///
    /// [pdqsort]: https://github.com/orlp/pdqsort
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")]
    #[inline]
    pub fn sort_by_cached_key<K, F>(&mut self, f: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
        // 辅助宏,用于通过最小的类型索引 vector,以减少分配。
        macro_rules! sort_by_key {
            ($t:ty, $slice:ident, $f:ident) => {{
                let mut indices: Vec<_> =
                    $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
                // `indices` 的元素是唯一的,因为它们已被索引,因此任何种类相对于原始切片都是稳定的。
                // 我们在这里使用 `sort_unstable` 是因为它需要较少的内存分配。
                //
                indices.sort_unstable();
                for i in 0..$slice.len() {
                    let mut index = indices[i].1;
                    while (index as usize) < i {
                        index = indices[index as usize].1;
                    }
                    indices[i].1 = index;
                    $slice.swap(i, index as usize);
                }
            }};
        }

        let sz_u8 = mem::size_of::<(K, u8)>();
        let sz_u16 = mem::size_of::<(K, u16)>();
        let sz_u32 = mem::size_of::<(K, u32)>();
        let sz_usize = mem::size_of::<(K, usize)>();

        let len = self.len();
        if len < 2 {
            return;
        }
        if sz_u8 < sz_u16 && len <= (u8::MAX as usize) {
            return sort_by_key!(u8, self, f);
        }
        if sz_u16 < sz_u32 && len <= (u16::MAX as usize) {
            return sort_by_key!(u16, self, f);
        }
        if sz_u32 < sz_usize && len <= (u32::MAX as usize) {
            return sort_by_key!(u32, self, f);
        }
        sort_by_key!(usize, self, f)
    }

    /// 将 `self` 复制到新的 `Vec` 中。
    ///
    /// # Examples
    ///
    /// ```
    /// let s = [10, 40, 30];
    /// let x = s.to_vec();
    /// // 在此,`s` 和 `x` 可以独立修改。
    /// ```
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[rustc_conversion_suggestion]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn to_vec(&self) -> Vec<T>
    where
        T: Clone,
    {
        self.to_vec_in(Global)
    }

    /// 使用分配器将 `self` 复制到新的 `Vec` 中。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(allocator_api)]
    ///
    /// use std::alloc::System;
    ///
    /// let s = [10, 40, 30];
    /// let x = s.to_vec_in(System);
    /// // 在此,`s` 和 `x` 可以独立修改。
    /// ```
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[inline]
    #[unstable(feature = "allocator_api", issue = "32838")]
    pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
    where
        T: Clone,
    {
        // 注意,有关更多详细信息,请参见此文件中的 `hack` 模块。
        hack::to_vec(self, alloc)
    }

    /// 将 `self` 转换为 vector,而无需克隆或分配。
    ///
    /// 产生的 vector 可以通过 `Vec 转换回 box<T>` 的 `into_boxed_slice` 方法。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// let s: Box<[i32]> = Box::new([10, 40, 30]);
    /// let x = s.into_vec();
    /// // `s` 不能再使用了,因为它已经转换成 `x`。
    ///
    /// assert_eq!(x, vec![10, 40, 30]);
    /// ```
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> {
        // 注意,有关更多详细信息,请参见此文件中的 `hack` 模块。
        hack::into_vec(self)
    }

    /// 通过复制切片 `n` 次创建 vector。
    ///
    /// # Panics
    ///
    /// 如果容量溢出,此函数将为 panic。
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
    /// ```
    ///
    /// 溢出时为 panic:
    ///
    /// ```should_panic
    /// // 这将在运行时 panic
    /// b"0123456789abcdef".repeat(usize::MAX);
    /// ```
    #[rustc_allow_incoherent_impl]
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "repeat_generic_slice", since = "1.40.0")]
    pub fn repeat(&self, n: usize) -> Vec<T>
    where
        T: Copy,
    {
        if n == 0 {
            return Vec::new();
        }

        // 如果 `n` 大于零,则可以将其拆分为 `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`。
        // `2^expn` 是 `n` 最左边的 '1' 位所代表的数字,`rem` 是 `n` 的剩余部分。
        //
        //

        // 使用 `Vec` 访问 `set_len()`。
        let capacity = self.len().checked_mul(n).expect("capacity overflow");
        let mut buf = Vec::with_capacity(capacity);

        // `2^expn` 重复是通过将 `buf` `expn` 次加倍来完成的。
        buf.extend(self);
        {
            let mut m = n >> 1;
            // 如果是 `m > 0`,则剩余的位将保留到最左边的 '1'。
            while m > 0 {
                // `buf.extend(buf)`:
                unsafe {
                    ptr::copy_nonoverlapping(
                        buf.as_ptr(),
                        (buf.as_mut_ptr() as *mut T).add(buf.len()),
                        buf.len(),
                    );
                    // `buf` 的容量为 `self.len() * n`。
                    let buf_len = buf.len();
                    buf.set_len(buf_len * 2);
                }

                m >>= 1;
            }
        }

        // `rem` (`= n - 2^expn`) 重复是通过从 `buf` 本身复制第一个 `rem` 重复来完成的。
        //
        let rem_len = capacity - buf.len(); // `self.len() * rem`
        if rem_len > 0 {
            // `buf.extend(buf[0 .. rem_len])`:
            unsafe {
                // 自 `2^expn > rem` 起,这是不重叠的。
                ptr::copy_nonoverlapping(
                    buf.as_ptr(),
                    (buf.as_mut_ptr() as *mut T).add(buf.len()),
                    rem_len,
                );
                // `buf.len() + rem_len` 等于 `buf.capacity()` (`= self.len() * n`)。
                buf.set_len(capacity);
            }
        }
        buf
    }

    /// 将 `T` 的切片展平为单个值 `Self::Output`。
    ///
    /// # Examples
    ///
    /// ```
    /// assert_eq!(["hello", "world"].concat(), "helloworld");
    /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
    /// ```
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
    where
        Self: Concat<Item>,
    {
        Concat::concat(self)
    }

    /// 将 `T` 的切片展平为单个值 `Self::Output`,并在每个值之间放置一个给定的分隔符。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// assert_eq!(["hello", "world"].join(" "), "hello world");
    /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
    /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
    /// ```
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
    pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
    where
        Self: Join<Separator>,
    {
        Join::join(self, sep)
    }

    /// 将 `T` 的切片展平为单个值 `Self::Output`,并在每个值之间放置一个给定的分隔符。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// # #![allow(deprecated)]
    /// assert_eq!(["hello", "world"].connect(" "), "hello world");
    /// assert_eq!([[1, 2], [3, 4]].connect(&0), [1, 2, 0, 3, 4]);
    /// ```
    #[rustc_allow_incoherent_impl]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[deprecated(since = "1.3.0", note = "renamed to join")]
    pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
    where
        Self: Join<Separator>,
    {
        Join::join(self, sep)
    }
}

#[cfg(not(test))]
impl [u8] {
    /// 返回一个 vector,其中包含此切片的副本,其中每个字节都映射到其等效的 ASCII 大写字母。
    ///
    ///
    /// ASCII 字母 'a' 到 'z' 映射到 'A' 到 'Z',但是非 ASCII 字母不变。
    ///
    /// 要就地将值大写,请使用 [`make_ascii_uppercase`]。
    ///
    /// [`make_ascii_uppercase`]: slice::make_ascii_uppercase
    ///
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[must_use = "this returns the uppercase bytes as a new Vec, \
                  without modifying the original"]
    #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
    #[inline]
    pub fn to_ascii_uppercase(&self) -> Vec<u8> {
        let mut me = self.to_vec();
        me.make_ascii_uppercase();
        me
    }

    /// 返回一个 vector,其中包含该切片的副本,其中每个字节均映射为其等效的 ASCII 小写字母。
    ///
    ///
    /// ASCII 字母 'A' 到 'Z' 映射到 'a' 到 'z',但是非 ASCII 字母不变。
    ///
    /// 要就地小写该值,请使用 [`make_ascii_lowercase`]。
    ///
    /// [`make_ascii_lowercase`]: slice::make_ascii_lowercase
    ///
    #[cfg(not(no_global_oom_handling))]
    #[rustc_allow_incoherent_impl]
    #[must_use = "this returns the lowercase bytes as a new Vec, \
                  without modifying the original"]
    #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
    #[inline]
    pub fn to_ascii_lowercase(&self) -> Vec<u8> {
        let mut me = self.to_vec();
        me.make_ascii_lowercase();
        me
    }
}

////////////////////////////////////////////////////////////////////////////////
// 扩展 traits 用于切片特定类型的数据
////////////////////////////////////////////////////////////////////////////////

/// [`[T]::concat`](slice::concat) 的辅助程序 trait。
///
/// Note: `Item` 类型参数未在此 trait 中使用,但它使 impls 更具泛型性。
/// 没有它,我们将收到此错误:
///
/// ```error
/// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica
///    --> library/alloc/src/slice.rs:608:6
///     |
/// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
///     |      ^ unconstrained type parameter
/// ```
///
/// 这是因为可能存在具有多个 `Borrow<[_]>` 表示的 `V` 类型,因此将应用多个 `T` 类型:
///
///
/// ```
/// # #[allow(dead_code)]
/// pub struct Foo(Vec<u32>, Vec<String>);
///
/// impl std::borrow::Borrow<[u32]> for Foo {
///     fn borrow(&self) -> &[u32] { &self.0 }
/// }
///
/// impl std::borrow::Borrow<[String]> for Foo {
///     fn borrow(&self) -> &[String] { &self.1 }
/// }
/// ```
///
#[unstable(feature = "slice_concat_trait", issue = "27747")]
pub trait Concat<Item: ?Sized> {
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    /// 串联后的结果类型
    type Output;

    /// [`[T]::concat`](slice::concat) 的实现
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    fn concat(slice: &Self) -> Self::Output;
}

/// [`[T]::join`](slice::join) 的辅助 trait
#[unstable(feature = "slice_concat_trait", issue = "27747")]
pub trait Join<Separator> {
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    /// 串联后的结果类型
    type Output;

    /// [`[T]::join`](slice::join) 的实现
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    fn join(slice: &Self, sep: Separator) -> Self::Output;
}

#[cfg(not(no_global_oom_handling))]
#[unstable(feature = "slice_concat_ext", issue = "27747")]
impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] {
    type Output = Vec<T>;

    fn concat(slice: &Self) -> Vec<T> {
        let size = slice.iter().map(|slice| slice.borrow().len()).sum();
        let mut result = Vec::with_capacity(size);
        for v in slice {
            result.extend_from_slice(v.borrow())
        }
        result
    }
}

#[cfg(not(no_global_oom_handling))]
#[unstable(feature = "slice_concat_ext", issue = "27747")]
impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
    type Output = Vec<T>;

    fn join(slice: &Self, sep: &T) -> Vec<T> {
        let mut iter = slice.iter();
        let first = match iter.next() {
            Some(first) => first,
            None => return vec![],
        };
        let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
        let mut result = Vec::with_capacity(size);
        result.extend_from_slice(first.borrow());

        for v in iter {
            result.push(sep.clone());
            result.extend_from_slice(v.borrow())
        }
        result
    }
}

#[cfg(not(no_global_oom_handling))]
#[unstable(feature = "slice_concat_ext", issue = "27747")]
impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
    type Output = Vec<T>;

    fn join(slice: &Self, sep: &[T]) -> Vec<T> {
        let mut iter = slice.iter();
        let first = match iter.next() {
            Some(first) => first,
            None => return vec![],
        };
        let size =
            slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
        let mut result = Vec::with_capacity(size);
        result.extend_from_slice(first.borrow());

        for v in iter {
            result.extend_from_slice(sep);
            result.extend_from_slice(v.borrow())
        }
        result
    }
}

////////////////////////////////////////////////////////////////////////////////
// 切片的标准 trait 实现
////////////////////////////////////////////////////////////////////////////////

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> Borrow<[T]> for Vec<T, A> {
    fn borrow(&self) -> &[T] {
        &self[..]
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> BorrowMut<[T]> for Vec<T, A> {
    fn borrow_mut(&mut self) -> &mut [T] {
        &mut self[..]
    }
}

// 专门用于实现 ToOwned::clone_into 的 trait。
// 这在 crate 中是公共的,并且具有 Allocator 参数,因此 vec::clone_from 也可以使用它。
//
#[cfg(not(no_global_oom_handling))]
pub(crate) trait SpecCloneIntoVec<T, A: Allocator> {
    fn clone_into(&self, target: &mut Vec<T, A>);
}

#[cfg(not(no_global_oom_handling))]
impl<T: Clone, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
    default fn clone_into(&self, target: &mut Vec<T, A>) {
        // 丢弃目标中不会被覆盖的任何内容
        target.truncate(self.len());

        // target.len <= self.len 由于上面的截断,所以这里的切片总是在边界内。
        //
        let (init, tail) = self.split_at(target.len());

        // 重用包含的值的 allocations/resources。
        target.clone_from_slice(init);
        target.extend_from_slice(tail);
    }
}

#[cfg(not(no_global_oom_handling))]
impl<T: Copy, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
    fn clone_into(&self, target: &mut Vec<T, A>) {
        target.clear();
        target.extend_from_slice(self);
    }
}

#[cfg(not(no_global_oom_handling))]
#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Clone> ToOwned for [T] {
    type Owned = Vec<T>;
    #[cfg(not(test))]
    fn to_owned(&self) -> Vec<T> {
        self.to_vec()
    }

    #[cfg(test)]
    fn to_owned(&self) -> Vec<T> {
        hack::to_vec(self, Global)
    }

    fn clone_into(&self, target: &mut Vec<T>) {
        SpecCloneIntoVec::clone_into(self, target);
    }
}

////////////////////////////////////////////////////////////////////////////////
// Sorting
////////////////////////////////////////////////////////////////////////////////

#[inline]
#[cfg(not(no_global_oom_handling))]
fn stable_sort<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    if T::IS_ZST {
        // 零大小类型的排序没有有意义的行为。什么也不做。
        return;
    }

    let elem_alloc_fn = |len: usize| -> *mut T {
        // SAFETY: 只要 merge_sort 从不使用 len > v.len() 调用它,创建布局就是安全的。
        // Alloc 一般只会作为 'shadow-region' 来存放临时交换元素。
        //
        unsafe { alloc::alloc(alloc::Layout::array::<T>(len).unwrap_unchecked()) as *mut T }
    };

    let elem_dealloc_fn = |buf_ptr: *mut T, len: usize| {
        // SAFETY: 只要 merge_sort 从不使用 len > v.len() 调用它,创建布局就是安全的。
        // 调用者必须确保 buf_ptr 是由具有相同 len 的 elem_alloc_fn 创建的。
        //
        unsafe {
            alloc::dealloc(buf_ptr as *mut u8, alloc::Layout::array::<T>(len).unwrap_unchecked());
        }
    };

    let run_alloc_fn = |len: usize| -> *mut sort::TimSortRun {
        // SAFETY: 创建布局是安全的,只要 merge_sort 从不使用淫秽长度调用它或 0.
        //
        unsafe {
            alloc::alloc(alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked())
                as *mut sort::TimSortRun
        }
    };

    let run_dealloc_fn = |buf_ptr: *mut sort::TimSortRun, len: usize| {
        // SAFETY: 调用者必须确保 buf_ptr 是由具有相同 len 的 elem_alloc_fn 创建的。
        //
        unsafe {
            alloc::dealloc(
                buf_ptr as *mut u8,
                alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked(),
            );
        }
    };

    sort::merge_sort(v, &mut is_less, elem_alloc_fn, elem_dealloc_fn, run_alloc_fn, run_dealloc_fn);
}