diff options
Diffstat (limited to 'third_party/rust/line-wrap')
| -rw-r--r-- | third_party/rust/line-wrap/.cargo-checksum.json | 1 | ||||
| -rw-r--r-- | third_party/rust/line-wrap/Cargo.toml | 29 | ||||
| -rw-r--r-- | third_party/rust/line-wrap/LICENSE.txt | 202 | ||||
| -rw-r--r-- | third_party/rust/line-wrap/README.md | 5 | ||||
| -rw-r--r-- | third_party/rust/line-wrap/benches/benchmarks.rs | 97 | ||||
| -rw-r--r-- | third_party/rust/line-wrap/src/lib.rs | 351 | ||||
| -rw-r--r-- | third_party/rust/line-wrap/src/tests.rs | 281 |
7 files changed, 966 insertions, 0 deletions
diff --git a/third_party/rust/line-wrap/.cargo-checksum.json b/third_party/rust/line-wrap/.cargo-checksum.json new file mode 100644 index 0000000000..af4dbc888f --- /dev/null +++ b/third_party/rust/line-wrap/.cargo-checksum.json @@ -0,0 +1 @@ +{"files":{"Cargo.toml":"bef86f5e51a493503e4a116261bb605c1145edccfbfcf66df445d11a8ae22220","LICENSE.txt":"cfc7749b96f63bd31c3c42b5c471bf756814053e847c10f3eb003417bc523d30","README.md":"40fe512990ac37f5317f9a533fbf88adef8e6923afb88cdba12391eb7780c59f","benches/benchmarks.rs":"eccf00d726b148685ecd1743094f3b5f4be962e6246748e5beb2b8211e926863","src/lib.rs":"d06cb455a9a01da4c806350e62c92075387aeeeaa4de8ac294c45ec861ea964e","src/tests.rs":"9aec71ba44079da3141b9ff24576ef1c5c33433038ae51fb9296f5492b886a25"},"package":"f30344350a2a51da54c1d53be93fade8a237e545dbcc4bdbe635413f2117cab9"}
\ No newline at end of file diff --git a/third_party/rust/line-wrap/Cargo.toml b/third_party/rust/line-wrap/Cargo.toml new file mode 100644 index 0000000000..d27efdd654 --- /dev/null +++ b/third_party/rust/line-wrap/Cargo.toml @@ -0,0 +1,29 @@ +# THIS FILE IS AUTOMATICALLY GENERATED BY CARGO +# +# When uploading crates to the registry Cargo will automatically +# "normalize" Cargo.toml files for maximal compatibility +# with all versions of Cargo and also rewrite `path` dependencies +# to registry (e.g. crates.io) dependencies +# +# If you believe there's an error in this file please file an +# issue against the rust-lang/cargo repository. If you're +# editing this file be aware that the upstream Cargo.toml +# will likely look very different (and much more reasonable) + +[package] +name = "line-wrap" +version = "0.1.1" +authors = ["Marshall Pierce <marshall@mpierce.org>"] +description = "Efficiently insert line separators" +documentation = "https://docs.rs/line-wrap/" +readme = "README.md" +keywords = ["line-wrap", "line", "wrap"] +categories = ["encoding"] +license = "Apache-2.0" +repository = "https://bitbucket.org/marshallpierce/line-wrap-rs/src" +[profile.bench] +debug = true +[dependencies.safemem] +version = "0.3" +[dev-dependencies.rand] +version = "0.5.5" diff --git a/third_party/rust/line-wrap/LICENSE.txt b/third_party/rust/line-wrap/LICENSE.txt new file mode 100644 index 0000000000..d645695673 --- /dev/null +++ b/third_party/rust/line-wrap/LICENSE.txt @@ -0,0 +1,202 @@ + + Apache License + Version 2.0, January 2004 + http://www.apache.org/licenses/ + + TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION + + 1. Definitions. + + "License" shall mean the terms and conditions for use, reproduction, + and distribution as defined by Sections 1 through 9 of this document. + + "Licensor" shall mean the copyright owner or entity authorized by + the copyright owner that is granting the License. + + "Legal Entity" shall mean the union of the acting entity and all + other entities that control, are controlled by, or are under common + control with that entity. For the purposes of this definition, + "control" means (i) the power, direct or indirect, to cause the + direction or management of such entity, whether by contract or + otherwise, or (ii) ownership of fifty percent (50%) or more of the + outstanding shares, or (iii) beneficial ownership of such entity. + + "You" (or "Your") shall mean an individual or Legal Entity + exercising permissions granted by this License. + + "Source" form shall mean the preferred form for making modifications, + including but not limited to software source code, documentation + source, and configuration files. + + "Object" form shall mean any form resulting from mechanical + transformation or translation of a Source form, including but + not limited to compiled object code, generated documentation, + and conversions to other media types. + + "Work" shall mean the work of authorship, whether in Source or + Object form, made available under the License, as indicated by a + copyright notice that is included in or attached to the work + (an example is provided in the Appendix below). + + "Derivative Works" shall mean any work, whether in Source or Object + form, that is based on (or derived from) the Work and for which the + editorial revisions, annotations, elaborations, or other modifications + represent, as a whole, an original work of authorship. For the purposes + of this License, Derivative Works shall not include works that remain + separable from, or merely link (or bind by name) to the interfaces of, + the Work and Derivative Works thereof. + + "Contribution" shall mean any work of authorship, including + the original version of the Work and any modifications or additions + to that Work or Derivative Works thereof, that is intentionally + submitted to Licensor for inclusion in the Work by the copyright owner + or by an individual or Legal Entity authorized to submit on behalf of + the copyright owner. For the purposes of this definition, "submitted" + means any form of electronic, verbal, or written communication sent + to the Licensor or its representatives, including but not limited to + communication on electronic mailing lists, source code control systems, + and issue tracking systems that are managed by, or on behalf of, the + Licensor for the purpose of discussing and improving the Work, but + excluding communication that is conspicuously marked or otherwise + designated in writing by the copyright owner as "Not a Contribution." + + "Contributor" shall mean Licensor and any individual or Legal Entity + on behalf of whom a Contribution has been received by Licensor and + subsequently incorporated within the Work. + + 2. Grant of Copyright License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + copyright license to reproduce, prepare Derivative Works of, + publicly display, publicly perform, sublicense, and distribute the + Work and such Derivative Works in Source or Object form. + + 3. Grant of Patent License. Subject to the terms and conditions of + this License, each Contributor hereby grants to You a perpetual, + worldwide, non-exclusive, no-charge, royalty-free, irrevocable + (except as stated in this section) patent license to make, have made, + use, offer to sell, sell, import, and otherwise transfer the Work, + where such license applies only to those patent claims licensable + by such Contributor that are necessarily infringed by their + Contribution(s) alone or by combination of their Contribution(s) + with the Work to which such Contribution(s) was submitted. If You + institute patent litigation against any entity (including a + cross-claim or counterclaim in a lawsuit) alleging that the Work + or a Contribution incorporated within the Work constitutes direct + or contributory patent infringement, then any patent licenses + granted to You under this License for that Work shall terminate + as of the date such litigation is filed. + + 4. Redistribution. You may reproduce and distribute copies of the + Work or Derivative Works thereof in any medium, with or without + modifications, and in Source or Object form, provided that You + meet the following conditions: + + (a) You must give any other recipients of the Work or + Derivative Works a copy of this License; and + + (b) You must cause any modified files to carry prominent notices + stating that You changed the files; and + + (c) You must retain, in the Source form of any Derivative Works + that You distribute, all copyright, patent, trademark, and + attribution notices from the Source form of the Work, + excluding those notices that do not pertain to any part of + the Derivative Works; and + + (d) If the Work includes a "NOTICE" text file as part of its + distribution, then any Derivative Works that You distribute must + include a readable copy of the attribution notices contained + within such NOTICE file, excluding those notices that do not + pertain to any part of the Derivative Works, in at least one + of the following places: within a NOTICE text file distributed + as part of the Derivative Works; within the Source form or + documentation, if provided along with the Derivative Works; or, + within a display generated by the Derivative Works, if and + wherever such third-party notices normally appear. The contents + of the NOTICE file are for informational purposes only and + do not modify the License. You may add Your own attribution + notices within Derivative Works that You distribute, alongside + or as an addendum to the NOTICE text from the Work, provided + that such additional attribution notices cannot be construed + as modifying the License. + + You may add Your own copyright statement to Your modifications and + may provide additional or different license terms and conditions + for use, reproduction, or distribution of Your modifications, or + for any such Derivative Works as a whole, provided Your use, + reproduction, and distribution of the Work otherwise complies with + the conditions stated in this License. + + 5. Submission of Contributions. Unless You explicitly state otherwise, + any Contribution intentionally submitted for inclusion in the Work + by You to the Licensor shall be under the terms and conditions of + this License, without any additional terms or conditions. + Notwithstanding the above, nothing herein shall supersede or modify + the terms of any separate license agreement you may have executed + with Licensor regarding such Contributions. + + 6. Trademarks. This License does not grant permission to use the trade + names, trademarks, service marks, or product names of the Licensor, + except as required for reasonable and customary use in describing the + origin of the Work and reproducing the content of the NOTICE file. + + 7. Disclaimer of Warranty. Unless required by applicable law or + agreed to in writing, Licensor provides the Work (and each + Contributor provides its Contributions) on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or + implied, including, without limitation, any warranties or conditions + of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A + PARTICULAR PURPOSE. You are solely responsible for determining the + appropriateness of using or redistributing the Work and assume any + risks associated with Your exercise of permissions under this License. + + 8. Limitation of Liability. In no event and under no legal theory, + whether in tort (including negligence), contract, or otherwise, + unless required by applicable law (such as deliberate and grossly + negligent acts) or agreed to in writing, shall any Contributor be + liable to You for damages, including any direct, indirect, special, + incidental, or consequential damages of any character arising as a + result of this License or out of the use or inability to use the + Work (including but not limited to damages for loss of goodwill, + work stoppage, computer failure or malfunction, or any and all + other commercial damages or losses), even if such Contributor + has been advised of the possibility of such damages. + + 9. Accepting Warranty or Additional Liability. While redistributing + the Work or Derivative Works thereof, You may choose to offer, + and charge a fee for, acceptance of support, warranty, indemnity, + or other liability obligations and/or rights consistent with this + License. However, in accepting such obligations, You may act only + on Your own behalf and on Your sole responsibility, not on behalf + of any other Contributor, and only if You agree to indemnify, + defend, and hold each Contributor harmless for any liability + incurred by, or claims asserted against, such Contributor by reason + of your accepting any such warranty or additional liability. + + END OF TERMS AND CONDITIONS + + APPENDIX: How to apply the Apache License to your work. + + To apply the Apache License to your work, attach the following + boilerplate notice, with the fields enclosed by brackets "[]" + replaced with your own identifying information. (Don't include + the brackets!) The text should be enclosed in the appropriate + comment syntax for the file format. We also recommend that a + file or class name and description of purpose be included on the + same "printed page" as the copyright notice for easier + identification within third-party archives. + + Copyright [yyyy] [name of copyright owner] + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License at + + http://www.apache.org/licenses/LICENSE-2.0 + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. diff --git a/third_party/rust/line-wrap/README.md b/third_party/rust/line-wrap/README.md new file mode 100644 index 0000000000..56af5e9ba7 --- /dev/null +++ b/third_party/rust/line-wrap/README.md @@ -0,0 +1,5 @@ +[](https://crates.io/crates/line_wrap) [](https://docs.rs/line-wrap/) [](https://semaphoreci.com/marshallpierce/line-wrap-rs) + +See the [docs](https://docs.rs/line-wrap/) for usage info. + +This line-wrapping logic originally was part of [rust-base64](https://github.com/alicemaz/rust-base64). diff --git a/third_party/rust/line-wrap/benches/benchmarks.rs b/third_party/rust/line-wrap/benches/benchmarks.rs new file mode 100644 index 0000000000..a8d84948dc --- /dev/null +++ b/third_party/rust/line-wrap/benches/benchmarks.rs @@ -0,0 +1,97 @@ +#![feature(test)] + +extern crate line_wrap; +extern crate test; + +use test::Bencher; + +#[bench] +fn wrap_10_10_lf(b: &mut Bencher) { + do_wrap_bench(b, 10, 10, &line_wrap::lf()); +} + +#[bench] +fn wrap_10_10_crlf(b: &mut Bencher) { + do_wrap_bench(b, 10, 10, &line_wrap::crlf()); +} + +#[bench] +fn wrap_10_1_lf(b: &mut Bencher) { + do_wrap_bench(b, 10, 1, &line_wrap::lf()); +} + +#[bench] +fn wrap_10_1_crlf(b: &mut Bencher) { + do_wrap_bench(b, 10, 1, &line_wrap::crlf()); +} + +#[bench] +fn wrap_100_10_lf(b: &mut Bencher) { + do_wrap_bench(b, 100, 10, &line_wrap::lf()); +} + +#[bench] +fn wrap_100_10_crlf(b: &mut Bencher) { + do_wrap_bench(b, 100, 10, &line_wrap::crlf()); +} + +#[bench] +fn wrap_100_10_slice_10(b: &mut Bencher) { + let bytes = vec![b'\n', 10]; + let line_ending = line_wrap::SliceLineEnding::new(&bytes); + do_wrap_bench(b, 100, 10, &line_ending); +} + +#[bench] +fn wrap_100_1_lf(b: &mut Bencher) { + do_wrap_bench(b, 100, 1, &line_wrap::lf()); +} + +#[bench] +fn wrap_100_1_crlf(b: &mut Bencher) { + do_wrap_bench(b, 100, 1, &line_wrap::crlf()); +} + +#[bench] +fn wrap_1000_100_lf(b: &mut Bencher) { + do_wrap_bench(b, 1000, 100, &line_wrap::lf()); +} + +#[bench] +fn wrap_1000_100_crlf(b: &mut Bencher) { + do_wrap_bench(b, 1000, 100, &line_wrap::crlf()); +} + +#[bench] +fn wrap_10000_100_lf(b: &mut Bencher) { + do_wrap_bench(b, 10000, 100, &line_wrap::lf()); +} + +#[bench] +fn wrap_10000_100_crlf(b: &mut Bencher) { + do_wrap_bench(b, 10000, 100, &line_wrap::crlf()); +} + +#[bench] +fn wrap_10000_100_slice_1(b: &mut Bencher) { + let line_ending = line_wrap::SliceLineEnding::new(b"\n"); + + do_wrap_bench(b, 10000, 100, &line_ending); +} + +#[bench] +fn wrap_10000_100_slice_10(b: &mut Bencher) { + let bytes = vec![b'\n', 10]; + let line_ending = line_wrap::SliceLineEnding::new(&bytes); + + do_wrap_bench(b, 10000, 100, &line_ending); +} + +fn do_wrap_bench<L: line_wrap::LineEnding>(b: &mut Bencher, input_len: usize, line_len: usize, line_ending: &L) { + let mut v = vec![0_u8; input_len + input_len / line_len * line_ending.len()]; + + b.bytes = input_len as u64; + b.iter(|| { + line_wrap::line_wrap(&mut v, input_len, line_len, line_ending); + }) +}
\ No newline at end of file diff --git a/third_party/rust/line-wrap/src/lib.rs b/third_party/rust/line-wrap/src/lib.rs new file mode 100644 index 0000000000..3760d10175 --- /dev/null +++ b/third_party/rust/line-wrap/src/lib.rs @@ -0,0 +1,351 @@ +//! Efficiently insert line endings. +//! +//! If you have a buffer full of data and want to insert any sort of regularly-spaced separator, +//! this will do it with a minimum of data copying. Commonly, this is to insert `\n` (see `lf()`) or `\r\n` (`crlf()`), but +//! any byte sequence can be used. +//! +//! 1. Pick a line ending. For single byte separators, see `ByteLineEnding`, or for two bytes, `TwoByteLineEnding`. For +//! arbitrary byte slices, use `SliceLineEnding`. +//! 2. Call `line_wrap`. +//! 3. Your data has been rearranged in place with the specified line ending inserted. +//! +//! # Examples +//! +//! ``` +//! use line_wrap::*; +//! // suppose we have 80 bytes of data in a buffer and we want to wrap as per MIME. +//! // Buffer is large enough to hold line endings. +//! let mut data = vec![0; 82]; +//! +//! assert_eq!(2, line_wrap(&mut data, 80, 76, &crlf())); +//! +//! // first line of zeroes +//! let mut expected_data = vec![0; 76]; +//! // line ending +//! expected_data.extend_from_slice(b"\r\n"); +//! // next line +//! expected_data.extend_from_slice(&[0, 0, 0, 0]); +//! assert_eq!(expected_data, data); +//! ``` +//! +//! # Performance +//! +//! On an i7 6850k: +//! +//! - 10 byte input, 1 byte line length takes ~60ns (~160MiB/s) +//! - 100 byte input, 10 byte lines takes ~60ns (~1.6GiB/s) +//! - Startup costs dominate at these small lengths +//! - 1,000 byte input, 100 byte lines takes ~65ns (~15GiB/s) +//! - 10,000 byte input, 100 byte lines takes ~550ns (~17GiB/s) +//! - In general, `SliceLineEncoding` is about 75% the speed of the fixed-length impls. +//! +//! Naturally, try `cargo +nightly bench` on your hardware to get more representative data. +extern crate safemem; + +/// Unix-style line ending. +pub fn lf() -> ByteLineEnding { ByteLineEnding::new(b'\n') } + +/// Windows-style line ending. +pub fn crlf() -> TwoByteLineEnding { TwoByteLineEnding::new(b'\r', b'\n') } + +/// Writes line endings. +/// +/// The trait allows specialization for the common single and double byte cases, netting nice +/// throughput improvements over simply using a slice for everything. +pub trait LineEnding { + /// Write the line ending into the slice, which starts at the point where the ending should be written and is len() in length + fn write_ending(&self, slice: &mut [u8]); + /// The length of this particular line ending (must be constant and > 0) + fn len(&self) -> usize; +} + +/// A single byte line ending. +/// +/// See `lf()`. +/// +/// # Examples +/// +/// ``` +/// use line_wrap::*; +/// +/// let ending = ByteLineEnding::new(b'\n'); +/// +/// let mut data = vec![1, 2, 3, 4, 5, 6, 255, 255]; +/// +/// assert_eq!(2, line_wrap(&mut data[..], 6, 2, &ending)); +/// +/// assert_eq!(vec![1, 2, b'\n', 3, 4, b'\n', 5, 6], data); +/// ``` +pub struct ByteLineEnding { + byte: u8 +} + +impl ByteLineEnding { + pub fn new(byte: u8) -> ByteLineEnding { + ByteLineEnding { + byte + } + } +} + +impl LineEnding for ByteLineEnding { + #[inline] + fn write_ending(&self, slice: &mut [u8]) { + slice[0] = self.byte; + } + + #[inline] + fn len(&self) -> usize { + 1 + } +} + +/// A double byte line ending. +/// +/// See `crlf()`. +/// +/// # Examples +/// +/// ``` +/// use line_wrap::*; +/// +/// let ending = TwoByteLineEnding::new(b'\r', b'\n'); +/// +/// let mut data = vec![1, 2, 3, 4, 5, 6, 255, 255, 255, 255]; +/// +/// assert_eq!(4, line_wrap(&mut data[..], 6, 2, &ending)); +/// +/// assert_eq!(vec![1, 2, b'\r', b'\n', 3, 4, b'\r', b'\n', 5, 6], data); +/// ``` +pub struct TwoByteLineEnding { + byte0: u8, + byte1: u8, +} + +impl TwoByteLineEnding { + pub fn new(byte0: u8, byte1: u8) -> TwoByteLineEnding { + TwoByteLineEnding { + byte0, + byte1, + } + } +} + +impl LineEnding for TwoByteLineEnding { + #[inline] + fn write_ending(&self, slice: &mut [u8]) { + slice[0] = self.byte0; + slice[1] = self.byte1; + } + + #[inline] + fn len(&self) -> usize { + 2 + } +} + +/// A byte slice line ending. +/// +/// Gives up some throughput compared to the specialized single/double byte impls, but works with +/// any length. +/// +/// # Examples +/// +/// ``` +/// use line_wrap::*; +/// +/// let ending = SliceLineEnding::new(b"xyz"); +/// +/// let mut data = vec![1, 2, 3, 4, 5, 6, 255, 255, 255, 255, 255, 255]; +/// +/// assert_eq!(6, line_wrap(&mut data[..], 6, 2, &ending)); +/// +/// assert_eq!(vec![1, 2, b'x', b'y', b'z', 3, 4, b'x', b'y', b'z', 5, 6], data); +/// ``` +pub struct SliceLineEnding<'a> { + slice: &'a [u8] +} + +impl<'a> SliceLineEnding<'a> { + pub fn new(slice: &[u8]) -> SliceLineEnding { + SliceLineEnding { + slice + } + } +} + +impl<'a> LineEnding for SliceLineEnding<'a> { + #[inline] + fn write_ending(&self, slice: &mut [u8]) { + slice.copy_from_slice(self.slice); + } + + #[inline] + fn len(&self) -> usize { + self.slice.len() + } +} + +/// Insert line endings into the input. +/// +/// Endings are inserted after each complete line, except the last line, even if the last line takes +/// up the full line width. +/// +/// - `buf` must be large enough to handle the increased size after endings are inserted. In other +/// words, `buf.len() >= input_len / line_len * line_ending.len()`. +/// - `input_len` is the length of the unwrapped in `buf`. +/// - `line_len` is the desired line width without line ending characters. +/// +/// Returns the number of line ending bytes added. +/// +/// # Panics +/// +/// - When `line_ending.len() == 0` +/// - When `buf` is too small to contain the original input and its new line endings +pub fn line_wrap<L: LineEnding>( + buf: &mut [u8], + input_len: usize, + line_len: usize, + line_ending: &L, +) -> usize { + assert!(line_ending.len() > 0); + + if input_len <= line_len { + return 0; + } + + let line_ending_len = line_ending.len(); + let line_wrap_params = line_wrap_parameters(input_len, line_len, line_ending_len); + + // ptr.offset() is undefined if it wraps, and there is no checked_offset(). However, because + // we perform this check up front to make sure we have enough capacity, we know that none of + // the subsequent pointer operations (assuming they implement the desired behavior of course!) + // will overflow. + assert!( + buf.len() >= line_wrap_params.total_len, + "Buffer must be able to hold encoded data after line wrapping" + ); + + // Move the last line, either partial or full, by itself as it does not have a line ending + // afterwards + let last_line_start = input_len.checked_sub(line_wrap_params.last_line_len) + .expect("Last line start index underflow"); + // last line starts immediately after all the wrapped full lines + let new_line_start = line_wrap_params.total_full_wrapped_lines_len; + + safemem::copy_over( + buf, + last_line_start, + new_line_start, + line_wrap_params.last_line_len, + ); + + let mut total_line_ending_bytes = 0; + + // initialize so that the initial decrement will set them correctly + let mut old_line_start = last_line_start; + let mut new_line_start = line_wrap_params.total_full_wrapped_lines_len; + + // handle the full lines + for _ in 0..line_wrap_params.lines_with_endings { + // the index after the end of the line ending we're about to write is the start of the next + // line + let end_of_line_ending = new_line_start; + let start_of_line_ending = end_of_line_ending + .checked_sub(line_ending_len) + .expect("Line ending start index underflow"); + + // doesn't underflow because it's decremented `line_wrap_params.lines_with_endings` times + old_line_start = old_line_start.checked_sub(line_len) + .expect("Old line start index underflow"); + new_line_start = new_line_start.checked_sub(line_wrap_params.line_with_ending_len) + .expect("New line start index underflow"); + + safemem::copy_over(buf, old_line_start, new_line_start, line_len); + + line_ending.write_ending(&mut buf[start_of_line_ending..(end_of_line_ending)]); + total_line_ending_bytes += line_ending_len; + } + + assert_eq!(line_wrap_params.total_line_endings_len, total_line_ending_bytes); + + total_line_ending_bytes +} + +#[derive(Debug, PartialEq)] +struct LineWrapParameters { + line_with_ending_len: usize, + // number of lines that need an ending + lines_with_endings: usize, + // length of last line (which never needs an ending) + last_line_len: usize, + // length of lines that need an ending (which are always full lines), with their endings + total_full_wrapped_lines_len: usize, + // length of all lines, including endings for the ones that need them + total_len: usize, + // length of the line endings only + total_line_endings_len: usize, +} + +/// Calculations about how many lines we'll get for a given line length, line ending, etc. +/// This assumes that the last line will not get an ending, even if it is the full line length. +// Inlining improves short input single-byte by 25%. +#[inline] +fn line_wrap_parameters( + input_len: usize, + line_len: usize, + line_ending_len: usize, +) -> LineWrapParameters { + let line_with_ending_len = line_len + .checked_add(line_ending_len) + .expect("Line length with ending exceeds usize"); + + if input_len <= line_len { + // no wrapping needed + return LineWrapParameters { + line_with_ending_len, + lines_with_endings: 0, + last_line_len: input_len, + total_full_wrapped_lines_len: 0, + total_len: input_len, + total_line_endings_len: 0, + }; + }; + + // lines_with_endings > 0, last_line_len > 0 + let (lines_with_endings, last_line_len) = if input_len % line_len > 0 { + // Every full line has an ending since there is a partial line at the end + (input_len / line_len, input_len % line_len) + } else { + // Every line is a full line, but no trailing ending. + // Subtraction will not underflow since we know input_len > line_len. + (input_len / line_len - 1, line_len) + }; + + // Should we expose exceeding usize via Result to be kind to 16-bit users? Or is that + // always going to be a panic anyway in practice? + + // length of just the full lines with line endings + let total_full_wrapped_lines_len = lines_with_endings + .checked_mul(line_with_ending_len) + .expect("Full lines with endings length exceeds usize"); + // all lines with appropriate endings, including the last line + let total_len = total_full_wrapped_lines_len + .checked_add(last_line_len) + .expect("All lines with endings length exceeds usize"); + let total_line_endings_len = lines_with_endings + .checked_mul(line_ending_len) + .expect("Total line endings length exceeds usize"); + + LineWrapParameters { + line_with_ending_len, + lines_with_endings, + last_line_len, + total_full_wrapped_lines_len, + total_len, + total_line_endings_len, + } +} + +#[cfg(test)] +mod tests;
\ No newline at end of file diff --git a/third_party/rust/line-wrap/src/tests.rs b/third_party/rust/line-wrap/src/tests.rs new file mode 100644 index 0000000000..6793e10968 --- /dev/null +++ b/third_party/rust/line-wrap/src/tests.rs @@ -0,0 +1,281 @@ +extern crate rand; + + +use super::*; +use self::rand::distributions::{Distribution, Range}; +use self::rand::{Rng, FromEntropy}; + +#[test] +fn line_params_perfect_multiple_of_line_length_lf() { + let params = line_wrap_parameters(100, 20, lf().len()); + + assert_eq!( + LineWrapParameters { + line_with_ending_len: 21, + lines_with_endings: 4, + last_line_len: 20, + total_full_wrapped_lines_len: 84, + total_len: 104, + total_line_endings_len: 4, + }, + params + ); +} + +#[test] +fn line_params_partial_last_line_crlf() { + let params = line_wrap_parameters(103, 20, crlf().len()); + + assert_eq!( + LineWrapParameters { + line_with_ending_len: 22, + lines_with_endings: 5, + last_line_len: 3, + total_full_wrapped_lines_len: 110, + total_len: 113, + total_line_endings_len: 10, + }, + params + ); +} + +#[test] +fn line_params_line_len_1_crlf() { + let params = line_wrap_parameters(100, 1, crlf().len()); + + assert_eq!( + LineWrapParameters { + line_with_ending_len: 3, + lines_with_endings: 99, + last_line_len: 1, + total_full_wrapped_lines_len: 99 * 3, + total_len: 99 * 3 + 1, + total_line_endings_len: 99 * 2, + }, + params + ); +} + +#[test] +fn line_params_line_len_longer_than_input_crlf() { + let params = line_wrap_parameters(100, 200, crlf().len()); + + assert_eq!( + LineWrapParameters { + line_with_ending_len: 202, + lines_with_endings: 0, + last_line_len: 100, + total_full_wrapped_lines_len: 0, + total_len: 100, + total_line_endings_len: 0, + }, + params + ); +} + +#[test] +fn line_params_line_len_same_as_input_crlf() { + let params = line_wrap_parameters(100, 100, crlf().len()); + + assert_eq!( + LineWrapParameters { + line_with_ending_len: 102, + lines_with_endings: 0, + last_line_len: 100, + total_full_wrapped_lines_len: 0, + total_len: 100, + total_line_endings_len: 0, + }, + params + ); +} + + +#[test] +fn line_wrap_length_1_lf() { + let mut buf = vec![0x1, 0x2, 0x3, 0x4]; + + assert_eq!(3, do_line_wrap(&mut buf, 1, &lf())); + + assert_eq!(vec![0x1, 0xA, 0x2, 0xA, 0x3, 0xA, 0x4], buf); +} + +#[test] +fn line_wrap_length_1_crlf() { + let mut buf = vec![0x1, 0x2, 0x3, 0x4]; + + assert_eq!(6, do_line_wrap(&mut buf, 1, &crlf())); + + assert_eq!(vec![0x1, 0xD, 0xA, 0x2, 0xD, 0xA, 0x3, 0xD, 0xA, 0x4], buf); +} + +#[test] +fn line_wrap_length_2_lf_full_lines() { + let mut buf = vec![0x1, 0x2, 0x3, 0x4]; + + assert_eq!(1, do_line_wrap(&mut buf, 2, &lf())); + + assert_eq!(vec![0x1, 0x2, 0xA, 0x3, 0x4], buf); +} + +#[test] +fn line_wrap_length_2_crlf_full_lines() { + let mut buf = vec![0x1, 0x2, 0x3, 0x4]; + + assert_eq!(2, do_line_wrap(&mut buf, 2, &crlf())); + + assert_eq!(vec![0x1, 0x2, 0xD, 0xA, 0x3, 0x4], buf); +} + +#[test] +fn line_wrap_length_2_lf_partial_line() { + let mut buf = vec![0x1, 0x2, 0x3, 0x4, 0x5]; + + assert_eq!(2, do_line_wrap(&mut buf, 2, &lf())); + + assert_eq!(vec![0x1, 0x2, 0xA, 0x3, 0x4, 0xA, 0x5], buf); +} + +#[test] +fn line_wrap_length_2_crlf_partial_line() { + let mut buf = vec![0x1, 0x2, 0x3, 0x4, 0x5]; + + assert_eq!(4, do_line_wrap(&mut buf, 2, &crlf())); + + assert_eq!(vec![0x1, 0x2, 0xD, 0xA, 0x3, 0x4, 0xD, 0xA, 0x5], buf); +} + +#[test] +fn line_wrap_random_slice() { + let mut buf: Vec<u8> = Vec::new(); + let buf_range = Range::new(10, 1000); + let line_range = Range::new(10, 100); + let mut rng = rand::rngs::SmallRng::from_entropy(); + let mut line_ending_bytes: Vec<u8> = Vec::new(); + + for _ in 0..10_000 { + buf.clear(); + line_ending_bytes.clear(); + + let buf_len = buf_range.sample(&mut rng); + let line_len = line_range.sample(&mut rng); + + for _ in 0..buf_len { + buf.push(rng.gen()); + } + + line_ending_bytes.clear(); + for _ in 0..rng.gen_range(1, 11) { + line_ending_bytes.push(rng.gen()); + } + let line_ending = SliceLineEnding::new(&line_ending_bytes); + + let _ = do_line_wrap(&mut buf, line_len, &line_ending); + } +} + +#[test] +fn line_wrap_random_single_byte() { + let mut buf: Vec<u8> = Vec::new(); + let buf_range = Range::new(10, 1000); + let line_range = Range::new(10, 100); + let mut rng = rand::rngs::SmallRng::from_entropy(); + + for _ in 0..10_000 { + buf.clear(); + + let buf_len = buf_range.sample(&mut rng); + let line_len = line_range.sample(&mut rng); + + for _ in 0..buf_len { + buf.push(rng.gen()); + } + + let line_ending = ByteLineEnding::new(rng.gen()); + + let _ = do_line_wrap(&mut buf, line_len, &line_ending); + } +} + +#[test] +fn line_wrap_random_two_bytes() { + let mut buf: Vec<u8> = Vec::new(); + let buf_range = Range::new(10, 1000); + let line_range = Range::new(10, 100); + let mut rng = rand::rngs::SmallRng::from_entropy(); + + for _ in 0..10_000 { + buf.clear(); + + let buf_len = buf_range.sample(&mut rng); + let line_len = line_range.sample(&mut rng); + + for _ in 0..buf_len { + buf.push(rng.gen()); + } + + let line_ending = TwoByteLineEnding::new(rng.gen(), rng.gen()); + + let _ = do_line_wrap(&mut buf, line_len, &line_ending); + } +} + +fn do_line_wrap<L: LineEnding>(buf: &mut Vec<u8>, line_len: usize, line_ending: &L) -> usize { + let mut rng = rand::rngs::SmallRng::from_entropy(); + + let orig_len = buf.len(); + let orig_buf = buf.to_vec(); + + // Add on extra bytes so we'll have sentinel bytes at the end that shouldn't get changed. + for _ in 0..(1000 + line_ending.len() * orig_len) { + buf.push(rng.gen()); + } + + let before_line_wrap = buf.to_vec(); + + let params = line_wrap_parameters(orig_len, line_len, line_ending.len()); + + let bytes_written = line_wrap::<L>(&mut buf[..], orig_len, line_len, line_ending); + + assert_eq!(params.total_line_endings_len, bytes_written); + assert_eq!(params.lines_with_endings * line_ending.len(), bytes_written); + assert_eq!(params.total_len, orig_len + bytes_written); + + // make sure line_wrap didn't touch anything beyond what it should + assert_eq!(before_line_wrap[params.total_len..], buf[params.total_len..]); + + { + // also make sure that line wrapping will fit into a slice no bigger than what it should + // need + let mut buf_strict = before_line_wrap.to_vec(); + buf_strict.truncate(orig_len); + // fill in some fresh random garbage + while buf_strict.len() < params.total_len { + buf_strict.push(rng.gen()); + } + let bytes_written_precise_fit = line_wrap::<L>( + &mut buf_strict, + orig_len, + line_len, + line_ending, + ); + assert_eq!(params.total_len, buf_strict.len()); + assert_eq!(bytes_written, bytes_written_precise_fit); + assert_eq!(&buf[0..(params.total_len)], &buf_strict[..]); + + // since we have a copy of the wrapped bytes lying around, remove the endings and see + // if we get the original + for line_ending_num in 0..params.lines_with_endings { + let line_ending_offset = (line_ending_num + 1) * line_len; + + for _ in 0..line_ending.len() { + let _ = buf_strict.remove(line_ending_offset); + } + } + assert_eq!(orig_buf, buf_strict); + } + + buf.truncate(params.total_len); + + bytes_written +}
\ No newline at end of file |