diff --git a/.hgignore b/.hgignore --- a/.hgignore +++ b/.hgignore @@ -35,6 +35,7 @@ contrib/chg/chg contrib/hgsh/hgsh contrib/vagrant/.vagrant +contrib/merge-lists/target/ dist packages doc/common.txt diff --git a/contrib/merge-lists/Cargo.lock b/contrib/merge-lists/Cargo.lock new file mode 100644 --- /dev/null +++ b/contrib/merge-lists/Cargo.lock @@ -0,0 +1,560 @@ +# This file is automatically @generated by Cargo. +# It is not intended for manual editing. +version = 3 + +[[package]] +name = "aho-corasick" +version = "0.7.18" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e37cfd5e7657ada45f742d6e99ca5788580b5c529dc78faf11ece6dc702656f" +dependencies = [ + "memchr", +] + +[[package]] +name = "assert_cmd" +version = "2.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "93ae1ddd39efd67689deb1979d80bad3bf7f2b09c6e6117c8d1f2443b5e2f83e" +dependencies = [ + "bstr", + "doc-comment", + "predicates", + "predicates-core", + "predicates-tree", + "wait-timeout", +] + +[[package]] +name = "atty" +version = "0.2.14" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d9b39be18770d11421cdb1b9947a45dd3f37e93092cbf377614828a319d5fee8" +dependencies = [ + "hermit-abi", + "libc", + "winapi", +] + +[[package]] +name = "autocfg" +version = "1.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d468802bab17cbc0cc575e9b053f41e72aa36bfa6b7f55e3529ffa43161b97fa" + +[[package]] +name = "bitflags" +version = "1.3.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bef38d45163c2f1dde094a7dfd33ccf595c92905c8f8f4fdc18d06fb1037718a" + +[[package]] +name = "bstr" +version = "0.2.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ba3569f383e8f1598449f1a423e72e99569137b47740b1da11ef19af3d5c3223" +dependencies = [ + "lazy_static", + "memchr", + "regex-automata", +] + +[[package]] +name = "clap" +version = "3.1.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "d8c93436c21e4698bacadf42917db28b23017027a4deccb35dbe47a7e7840123" +dependencies = [ + "atty", + "bitflags", + "clap_derive", + "indexmap", + "lazy_static", + "os_str_bytes", + "strsim", + "termcolor", + "textwrap", +] + +[[package]] +name = "clap_derive" +version = "3.1.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "da95d038ede1a964ce99f49cbe27a7fb538d1da595e4b4f70b8c8f338d17bf16" +dependencies = [ + "heck", + "proc-macro-error", + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "console" +version = "0.15.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a28b32d32ca44b70c3e4acd7db1babf555fa026e385fb95f18028f88848b3c31" +dependencies = [ + "encode_unicode", + "libc", + "once_cell", + "terminal_size", + "winapi", +] + +[[package]] +name = "difflib" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6184e33543162437515c2e2b48714794e37845ec9851711914eec9d308f6ebe8" + +[[package]] +name = "doc-comment" +version = "0.3.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "fea41bba32d969b513997752735605054bc0dfa92b4c56bf1189f2e174be7a10" + +[[package]] +name = "either" +version = "1.6.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e78d4f1cc4ae33bbfc157ed5d5a5ef3bc29227303d595861deb238fcec4e9457" + +[[package]] +name = "encode_unicode" +version = "0.3.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a357d28ed41a50f9c765dbfe56cbc04a64e53e5fc58ba79fbc34c10ef3df831f" + +[[package]] +name = "fuchsia-cprng" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a06f77d526c1a601b7c4cdd98f54b5eaabffc14d5f2f0296febdc7f357c6d3ba" + +[[package]] +name = "hashbrown" +version = "0.11.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ab5ef0d4909ef3724cc8cce6ccc8572c5c817592e9285f5464f8e86f8bd3726e" + +[[package]] +name = "heck" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2540771e65fc8cb83cd6e8a237f70c319bd5c29f78ed1084ba5d50eeac86f7f9" + +[[package]] +name = "hermit-abi" +version = "0.1.19" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "62b467343b94ba476dcb2500d242dadbb39557df889310ac77c5d99100aaac33" +dependencies = [ + "libc", +] + +[[package]] +name = "indexmap" +version = "1.8.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "282a6247722caba404c065016bbfa522806e51714c34f5dfc3e4a3a46fcb4223" +dependencies = [ + "autocfg", + "hashbrown", +] + +[[package]] +name = "insta" +version = "1.13.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "30a7e1911532a662f6b08b68f884080850f2fd9544963c3ab23a5af42bda1eac" +dependencies = [ + "console", + "once_cell", + "serde", + "serde_json", + "serde_yaml", + "similar", +] + +[[package]] +name = "itertools" +version = "0.10.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a9a9d19fa1e79b6215ff29b9d6880b706147f16e9b1dbb1e4e5947b5b02bc5e3" +dependencies = [ + "either", +] + +[[package]] +name = "itoa" +version = "1.0.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1aab8fc367588b89dcee83ab0fd66b72b50b72fa1904d7095045ace2b0c81c35" + +[[package]] +name = "lazy_static" +version = "1.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e2abad23fbc42b3700f2f279844dc832adb2b2eb069b2df918f455c4e18cc646" + +[[package]] +name = "libc" +version = "0.2.119" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1bf2e165bb3457c8e098ea76f3e3bc9db55f87aa90d52d0e6be741470916aaa4" + +[[package]] +name = "linked-hash-map" +version = "0.5.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7fb9b38af92608140b86b693604b9ffcc5824240a484d1ecd4795bacb2fe88f3" + +[[package]] +name = "memchr" +version = "2.4.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "308cc39be01b73d0d18f82a0e7b2a3df85245f84af96fdddc5d202d27e47b86a" + +[[package]] +name = "merge-lists" +version = "0.1.0" +dependencies = [ + "assert_cmd", + "clap", + "insta", + "itertools", + "regex", + "similar", + "tempdir", +] + +[[package]] +name = "once_cell" +version = "1.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "87f3e037eac156d1775da914196f0f37741a274155e34a0b7e427c35d2a2ecb9" + +[[package]] +name = "os_str_bytes" +version = "6.0.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8e22443d1643a904602595ba1cd8f7d896afe56d26712531c5ff73a15b2fbf64" +dependencies = [ + "memchr", +] + +[[package]] +name = "predicates" +version = "2.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a5aab5be6e4732b473071984b3164dbbfb7a3674d30ea5ff44410b6bcd960c3c" +dependencies = [ + "difflib", + "itertools", + "predicates-core", +] + +[[package]] +name = "predicates-core" +version = "1.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "da1c2388b1513e1b605fcec39a95e0a9e8ef088f71443ef37099fa9ae6673fcb" + +[[package]] +name = "predicates-tree" +version = "1.0.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "4d86de6de25020a36c6d3643a86d9a6a9f552107c0559c60ea03551b5e16c032" +dependencies = [ + "predicates-core", + "termtree", +] + +[[package]] +name = "proc-macro-error" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "da25490ff9892aab3fcf7c36f08cfb902dd3e71ca0f9f9517bea02a73a5ce38c" +dependencies = [ + "proc-macro-error-attr", + "proc-macro2", + "quote", + "syn", + "version_check", +] + +[[package]] +name = "proc-macro-error-attr" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a1be40180e52ecc98ad80b184934baf3d0d29f979574e439af5a55274b35f869" +dependencies = [ + "proc-macro2", + "quote", + "version_check", +] + +[[package]] +name = "proc-macro2" +version = "1.0.36" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c7342d5883fbccae1cc37a2353b09c87c9b0f3afd73f5fb9bba687a1f733b029" +dependencies = [ + "unicode-xid", +] + +[[package]] +name = "quote" +version = "1.0.15" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "864d3e96a899863136fc6e99f3d7cae289dafe43bf2c5ac19b70df7210c0a145" +dependencies = [ + "proc-macro2", +] + +[[package]] +name = "rand" +version = "0.4.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "552840b97013b1a26992c11eac34bdd778e464601a4c2054b5f0bff7c6761293" +dependencies = [ + "fuchsia-cprng", + "libc", + "rand_core 0.3.1", + "rdrand", + "winapi", +] + +[[package]] +name = "rand_core" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b" +dependencies = [ + "rand_core 0.4.2", +] + +[[package]] +name = "rand_core" +version = "0.4.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9c33a3c44ca05fa6f1807d8e6743f3824e8509beca625669633be0acbdf509dc" + +[[package]] +name = "rdrand" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "678054eb77286b51581ba43620cc911abf02758c91f93f479767aed0f90458b2" +dependencies = [ + "rand_core 0.3.1", +] + +[[package]] +name = "regex" +version = "1.5.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1a11647b6b25ff05a515cb92c365cec08801e83423a235b51e231e1808747286" +dependencies = [ + "aho-corasick", + "memchr", + "regex-syntax", +] + +[[package]] +name = "regex-automata" +version = "0.1.10" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "6c230d73fb8d8c1b9c0b3135c5142a8acee3a0558fb8db5cf1cb65f8d7862132" + +[[package]] +name = "regex-syntax" +version = "0.6.25" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f497285884f3fcff424ffc933e56d7cbca511def0c9831a7f9b5f6153e3cc89b" + +[[package]] +name = "remove_dir_all" +version = "0.5.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "3acd125665422973a33ac9d3dd2df85edad0f4ae9b00dafb1a05e43a9f5ef8e7" +dependencies = [ + "winapi", +] + +[[package]] +name = "ryu" +version = "1.0.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "73b4b750c782965c211b42f022f59af1fbceabdd026623714f104152f1ec149f" + +[[package]] +name = "serde" +version = "1.0.136" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ce31e24b01e1e524df96f1c2fdd054405f8d7376249a5110886fb4b658484789" +dependencies = [ + "serde_derive", +] + +[[package]] +name = "serde_derive" +version = "1.0.136" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "08597e7152fcd306f41838ed3e37be9eaeed2b61c42e2117266a554fab4662f9" +dependencies = [ + "proc-macro2", + "quote", + "syn", +] + +[[package]] +name = "serde_json" +version = "1.0.79" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8e8d9fa5c3b304765ce1fd9c4c8a3de2c8db365a5b91be52f186efc675681d95" +dependencies = [ + "itoa", + "ryu", + "serde", +] + +[[package]] +name = "serde_yaml" +version = "0.8.23" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "a4a521f2940385c165a24ee286aa8599633d162077a54bdcae2a6fd5a7bfa7a0" +dependencies = [ + "indexmap", + "ryu", + "serde", + "yaml-rust", +] + +[[package]] +name = "similar" +version = "2.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2e24979f63a11545f5f2c60141afe249d4f19f84581ea2138065e400941d83d3" +dependencies = [ + "bstr", +] + +[[package]] +name = "strsim" +version = "0.10.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "73473c0e59e6d5812c5dfe2a064a6444949f089e20eec9a2e5506596494e4623" + +[[package]] +name = "syn" +version = "1.0.87" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "1e59d925cf59d8151f25a3bedf97c9c157597c9df7324d32d68991cc399ed08b" +dependencies = [ + "proc-macro2", + "quote", + "unicode-xid", +] + +[[package]] +name = "tempdir" +version = "0.3.7" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "15f2b5fb00ccdf689e0149d1b1b3c03fead81c2b37735d812fa8bddbbf41b6d8" +dependencies = [ + "rand", + "remove_dir_all", +] + +[[package]] +name = "termcolor" +version = "1.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "bab24d30b911b2376f3a13cc2cd443142f0c81dda04c118693e35b3835757755" +dependencies = [ + "winapi-util", +] + +[[package]] +name = "terminal_size" +version = "0.1.17" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "633c1a546cee861a1a6d0dc69ebeca693bf4296661ba7852b9d21d159e0506df" +dependencies = [ + "libc", + "winapi", +] + +[[package]] +name = "termtree" +version = "0.2.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "507e9898683b6c43a9aa55b64259b721b52ba226e0f3779137e50ad114a4c90b" + +[[package]] +name = "textwrap" +version = "0.15.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b1141d4d61095b28419e22cb0bbf02755f5e54e0526f97f1e3d1d160e60885fb" + +[[package]] +name = "unicode-xid" +version = "0.2.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "8ccb82d61f80a663efe1f787a51b16b5a51e3314d6ac365b08639f52387b33f3" + +[[package]] +name = "version_check" +version = "0.9.4" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "49874b5167b65d7193b8aba1567f5c7d93d001cafc34600cee003eda787e483f" + +[[package]] +name = "wait-timeout" +version = "0.2.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "9f200f5b12eb75f8c1ed65abd4b2db8a6e1b138a20de009dacee265a2498f3f6" +dependencies = [ + "libc", +] + +[[package]] +name = "winapi" +version = "0.3.9" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "5c839a674fcd7a98952e593242ea400abe93992746761e38641405d28b00f419" +dependencies = [ + "winapi-i686-pc-windows-gnu", + "winapi-x86_64-pc-windows-gnu", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" + +[[package]] +name = "winapi-util" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "70ec6ce85bb158151cae5e5c87f95a8e97d2c0c4b001223f33a334e3ce5de178" +dependencies = [ + "winapi", +] + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f" + +[[package]] +name = "yaml-rust" +version = "0.4.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "56c1936c4cc7a1c9ab21a1ebb602eb942ba868cbd44a99cb7cdc5892335e1c85" +dependencies = [ + "linked-hash-map", +] diff --git a/contrib/merge-lists/Cargo.toml b/contrib/merge-lists/Cargo.toml new file mode 100644 --- /dev/null +++ b/contrib/merge-lists/Cargo.toml @@ -0,0 +1,21 @@ +# A tool that performs a 3-way merge, resolving conflicts in sorted lists and +# leaving other conflicts unchanged. This is useful with Mercurial's support +# for partial merge tools (configured in `[partial-merge-tools]`). + +[package] +name = "merge-lists" +version = "0.1.0" +edition = "2021" +# We need https://github.com/rust-lang/rust/pull/89825 +rust-version = "1.59" + +[dependencies] +clap = { version = "3.1.6", features = ["derive"] } +itertools = "0.10.3" +regex = "1.5.5" +similar = { version="2.1.0", features = ["bytes"] } + +[dev-dependencies] +assert_cmd = "2.0.4" +insta = "1.13.0" +tempdir = "0.3.7" diff --git a/contrib/merge-lists/src/main.rs b/contrib/merge-lists/src/main.rs new file mode 100644 --- /dev/null +++ b/contrib/merge-lists/src/main.rs @@ -0,0 +1,280 @@ +use clap::Parser; +use itertools::Itertools; +use regex::bytes::Regex; +use similar::ChangeTag; +use std::cmp::{max, min, Ordering}; +use std::collections::HashSet; +use std::ffi::OsString; +use std::ops::Range; +use std::path::PathBuf; + +fn find_unchanged_ranges( + old_bytes: &[u8], + new_bytes: &[u8], +) -> Vec<(Range, Range)> { + let diff = similar::TextDiff::configure() + .algorithm(similar::Algorithm::Patience) + .diff_lines(old_bytes, new_bytes); + let mut new_unchanged_ranges = vec![]; + let mut old_index = 0; + let mut new_index = 0; + for diff in diff.iter_all_changes() { + match diff.tag() { + ChangeTag::Equal => { + new_unchanged_ranges.push(( + old_index..old_index + diff.value().len(), + new_index..new_index + diff.value().len(), + )); + old_index += diff.value().len(); + new_index += diff.value().len(); + } + ChangeTag::Delete => { + old_index += diff.value().len(); + } + ChangeTag::Insert => { + new_index += diff.value().len(); + } + } + } + new_unchanged_ranges +} + +/// Returns a list of all the lines in the input (including trailing newlines), +/// but only if they all match the regex and they are sorted. +fn get_lines<'input>( + input: &'input [u8], + regex: &Regex, +) -> Option> { + let lines = input.split_inclusive(|x| *x == b'\n').collect_vec(); + let mut previous_line = "".as_bytes(); + for line in &lines { + if *line < previous_line { + return None; + } + if !regex.is_match(line) { + return None; + } + previous_line = line; + } + Some(lines) +} + +fn resolve_conflict( + base_slice: &[u8], + local_slice: &[u8], + other_slice: &[u8], + regex: &Regex, +) -> Option> { + let base_lines = get_lines(base_slice, regex)?; + let local_lines = get_lines(local_slice, regex)?; + let other_lines = get_lines(other_slice, regex)?; + let base_lines_set: HashSet<_> = base_lines.iter().copied().collect(); + let local_lines_set: HashSet<_> = local_lines.iter().copied().collect(); + let other_lines_set: HashSet<_> = other_lines.iter().copied().collect(); + let mut result = local_lines_set; + for to_add in other_lines_set.difference(&base_lines_set) { + result.insert(to_add); + } + for to_remove in base_lines_set.difference(&other_lines_set) { + result.remove(to_remove); + } + Some(result.into_iter().sorted().collect_vec().concat()) +} + +fn resolve( + base_bytes: &[u8], + local_bytes: &[u8], + other_bytes: &[u8], + regex: &Regex, +) -> (Vec, Vec, Vec) { + // Find unchanged ranges between the base and the two sides. We do that by + // initially considering the whole base unchanged. Then we compare each + // side with the base and intersect the unchanged ranges we find with + // what we had before. + let unchanged_ranges = vec![UnchangedRange { + base_range: 0..base_bytes.len(), + offsets: vec![], + }]; + let unchanged_ranges = intersect_regions( + unchanged_ranges, + &find_unchanged_ranges(base_bytes, local_bytes), + ); + let mut unchanged_ranges = intersect_regions( + unchanged_ranges, + &find_unchanged_ranges(base_bytes, other_bytes), + ); + // Add an empty UnchangedRange at the end to make it easier to find change + // ranges. That way there's a changed range before each UnchangedRange. + unchanged_ranges.push(UnchangedRange { + base_range: base_bytes.len()..base_bytes.len(), + offsets: vec![ + local_bytes.len().wrapping_sub(base_bytes.len()) as isize, + other_bytes.len().wrapping_sub(base_bytes.len()) as isize, + ], + }); + + let mut new_base_bytes: Vec = vec![]; + let mut new_local_bytes: Vec = vec![]; + let mut new_other_bytes: Vec = vec![]; + let mut previous = UnchangedRange { + base_range: 0..0, + offsets: vec![0, 0], + }; + for current in unchanged_ranges { + let base_slice = + &base_bytes[previous.base_range.end..current.base_range.start]; + let local_slice = &local_bytes[previous.end(0)..current.start(0)]; + let other_slice = &other_bytes[previous.end(1)..current.start(1)]; + if let Some(resolution) = + resolve_conflict(base_slice, local_slice, other_slice, regex) + { + new_base_bytes.extend(&resolution); + new_local_bytes.extend(&resolution); + new_other_bytes.extend(&resolution); + } else { + new_base_bytes.extend(base_slice); + new_local_bytes.extend(local_slice); + new_other_bytes.extend(other_slice); + } + new_base_bytes.extend(&base_bytes[current.base_range.clone()]); + new_local_bytes.extend(&local_bytes[current.start(0)..current.end(0)]); + new_other_bytes.extend(&other_bytes[current.start(1)..current.end(1)]); + previous = current; + } + + (new_base_bytes, new_local_bytes, new_other_bytes) +} + +/// A tool that performs a 3-way merge, resolving conflicts in sorted lists and +/// leaving other conflicts unchanged. This is useful with Mercurial's support +/// for partial merge tools (configured in `[partial-merge-tools]`). +#[derive(Parser, Debug)] +#[clap(version, about, long_about = None)] +struct Args { + /// Path to the file's content in the "local" side + local: OsString, + + /// Path to the file's content in the base + base: OsString, + + /// Path to the file's content in the "other" side + other: OsString, +} + +fn main() { + let args: Args = Args::parse(); + + let base_path = PathBuf::from(&args.base); + let local_path = PathBuf::from(&args.local); + let other_path = PathBuf::from(&args.other); + + let base_bytes = std::fs::read(&base_path).unwrap(); + let local_bytes = std::fs::read(&local_path).unwrap(); + let other_bytes = std::fs::read(&other_path).unwrap(); + + let regex = + regex::bytes::Regex::new(r"import \w+(\.\w+)*( +#.*)?\n|from (\w+(\.\w+)* import \w+( as \w+)?(, \w+( as \w+)?)*( +#.*)?)\r?\n?").unwrap(); + let (new_base_bytes, new_local_bytes, new_other_bytes) = + resolve(&base_bytes, &local_bytes, &other_bytes, ®ex); + + // Write out the result if anything changed + if new_base_bytes != base_bytes { + std::fs::write(&base_path, new_base_bytes).unwrap(); + } + if new_local_bytes != local_bytes { + std::fs::write(&local_path, new_local_bytes).unwrap(); + } + if new_other_bytes != other_bytes { + std::fs::write(&other_path, new_other_bytes).unwrap(); + } +} + +fn checked_add(base: usize, offset: isize) -> usize { + if offset < 0 { + base.checked_sub(offset.checked_abs().unwrap() as usize) + .unwrap() + } else { + base.checked_add(offset as usize).unwrap() + } +} + +// The remainder of the file is copied from +// https://github.com/martinvonz/jj/blob/main/lib/src/diff.rs + +#[derive(Clone, PartialEq, Eq, Debug)] +struct UnchangedRange { + base_range: Range, + offsets: Vec, +} + +impl UnchangedRange { + fn start(&self, side: usize) -> usize { + checked_add(self.base_range.start, self.offsets[side]) + } + + fn end(&self, side: usize) -> usize { + checked_add(self.base_range.end, self.offsets[side]) + } +} + +impl PartialOrd for UnchangedRange { + fn partial_cmp(&self, other: &Self) -> Option { + Some(self.cmp(other)) + } +} + +impl Ord for UnchangedRange { + fn cmp(&self, other: &Self) -> Ordering { + self.base_range + .start + .cmp(&other.base_range.start) + .then_with(|| self.base_range.end.cmp(&other.base_range.end)) + } +} + +/// Takes the current regions and intersects it with the new unchanged ranges +/// from a 2-way diff. The result is a map of unchanged regions with one more +/// offset in the map's values. +fn intersect_regions( + current_ranges: Vec, + new_unchanged_ranges: &[(Range, Range)], +) -> Vec { + let mut result = vec![]; + let mut current_ranges_iter = current_ranges.into_iter().peekable(); + for (new_base_range, other_range) in new_unchanged_ranges.iter() { + assert_eq!(new_base_range.len(), other_range.len()); + while let Some(UnchangedRange { + base_range, + offsets, + }) = current_ranges_iter.peek() + { + // No need to look further if we're past the new range. + if base_range.start >= new_base_range.end { + break; + } + // Discard any current unchanged regions that don't match between + // the base and the new input. + if base_range.end <= new_base_range.start { + current_ranges_iter.next(); + continue; + } + let new_start = max(base_range.start, new_base_range.start); + let new_end = min(base_range.end, new_base_range.end); + let mut new_offsets = offsets.clone(); + new_offsets + .push(other_range.start.wrapping_sub(new_base_range.start) + as isize); + result.push(UnchangedRange { + base_range: new_start..new_end, + offsets: new_offsets, + }); + if base_range.end >= new_base_range.end { + // Break without consuming the item; there may be other new + // ranges that overlap with it. + break; + } + current_ranges_iter.next(); + } + } + result +} diff --git a/contrib/merge-lists/tests/test-merge-lists.rs b/contrib/merge-lists/tests/test-merge-lists.rs new file mode 100644 --- /dev/null +++ b/contrib/merge-lists/tests/test-merge-lists.rs @@ -0,0 +1,156 @@ +use similar::DiffableStr; +use tempdir::TempDir; + +fn run_test(input: &str) -> String { + let mut cmd = assert_cmd::Command::cargo_bin("merge-lists").unwrap(); + let temp_dir = TempDir::new("test").unwrap(); + let base_path = temp_dir.path().join("base"); + let local_path = temp_dir.path().join("local"); + let other_path = temp_dir.path().join("other"); + + let rest = input.strip_prefix("\nbase:\n").unwrap(); + let mut split = rest.split("\nlocal:\n"); + std::fs::write(&base_path, split.next().unwrap()).unwrap(); + let rest = split.next().unwrap(); + let mut split = rest.split("\nother:\n"); + std::fs::write(&local_path, split.next().unwrap()).unwrap(); + std::fs::write(&other_path, split.next().unwrap()).unwrap(); + cmd.args(&[ + local_path.as_os_str(), + base_path.as_os_str(), + other_path.as_os_str(), + ]) + .assert() + .success(); + + let new_base_bytes = std::fs::read(&base_path).unwrap(); + let new_local_bytes = std::fs::read(&local_path).unwrap(); + let new_other_bytes = std::fs::read(&other_path).unwrap(); + // No newline before "base:" because of https://github.com/mitsuhiko/insta/issues/117 + format!( + "base:\n{}\nlocal:\n{}\nother:\n{}", + new_base_bytes.as_str().unwrap(), + new_local_bytes.as_str().unwrap(), + new_other_bytes.as_str().unwrap() + ) +} + +#[test] +fn test_merge_lists_basic() { + let output = run_test( + r" +base: +import lib1 +import lib2 + +local: +import lib2 +import lib3 + +other: +import lib3 +import lib4 +", + ); + insta::assert_snapshot!(output, @r###" + base: + import lib3 + import lib4 + + local: + import lib3 + import lib4 + + other: + import lib3 + import lib4 + "###); +} + +#[test] +fn test_merge_lists_from() { + // Test some "from x import y" statements and some non-import conflicts + // (unresolvable) + let output = run_test( + r" +base: +from . import x + +1+1 + +local: +from . import x +from a import b + +2+2 + +other: +from a import c + +3+3 +", + ); + insta::assert_snapshot!(output, @r###" + base: + from a import b + from a import c + + 1+1 + + local: + from a import b + from a import c + + 2+2 + + other: + from a import b + from a import c + + 3+3 + "###); +} + +#[test] +fn test_merge_lists_not_sorted() { + // Test that nothing is done if the elements in the conflicting hunks are + // not sorted + let output = run_test( + r" +base: +import x + +1+1 + +local: +import a +import x + +2+2 + +other: +import z +import y + +3+3 +", + ); + insta::assert_snapshot!(output, @r###" + base: + import x + + 1+1 + + local: + import a + import x + + 2+2 + + other: + import z + import y + + 3+3 + "###); +}