diff options
| -rw-r--r-- | Gopkg.lock | 129 | ||||
| -rw-r--r-- | pkg/utils/utils_test.go | 83 | ||||
| -rw-r--r-- | vendor/github.com/pmezard/go-difflib/LICENSE | 27 | ||||
| -rw-r--r-- | vendor/github.com/pmezard/go-difflib/difflib/difflib.go | 772 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/LICENSE | 22 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/assert/assertion_format.go | 484 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/assert/assertion_forward.go | 956 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/assert/assertions.go | 1394 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/assert/doc.go | 45 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/assert/errors.go | 10 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/assert/forward_assertions.go | 16 | ||||
| -rw-r--r-- | vendor/github.com/stretchr/testify/assert/http_assertions.go | 143 |
12 files changed, 3975 insertions, 106 deletions
diff --git a/Gopkg.lock b/Gopkg.lock index 662a9c28d..8afe97d30 100644 --- a/Gopkg.lock +++ b/Gopkg.lock @@ -2,31 +2,24 @@ [[projects]] - digest = "1:b2339e83ce9b5c4f79405f949429a7f68a9a904fed903c672aac1e7ceb7f5f02" name = "github.com/Sirupsen/logrus" packages = ["."] - pruneopts = "NUT" revision = "3e01752db0189b9157070a0e1668a620f9a85da2" version = "v1.0.6" [[projects]] branch = "master" - digest = "1:cd7ba2b29e93e2a8384e813dfc80ebb0f85d9214762e6ca89bb55a58092eab87" name = "github.com/cloudfoundry/jibber_jabber" packages = ["."] - pruneopts = "NUT" revision = "bcc4c8345a21301bf47c032ff42dd1aae2fe3027" [[projects]] - digest = "1:a2c1d0e43bd3baaa071d1b9ed72c27d78169b2b269f71c105ac4ba34b1be4a39" name = "github.com/davecgh/go-spew" packages = ["spew"] - pruneopts = "NUT" revision = "346938d642f2ec3594ed81d874461961cd0faa76" version = "v1.1.0" [[projects]] - digest = "1:de4a74b504df31145ffa8ca0c4edbffa2f3eb7f466753962184611b618fa5981" name = "github.com/emirpasic/gods" packages = [ "containers", @@ -34,39 +27,31 @@ "lists/arraylist", "trees", "trees/binaryheap", - "utils", + "utils" ] - pruneopts = "NUT" revision = "f6c17b524822278a87e3b3bd809fec33b51f5b46" version = "v1.9.0" [[projects]] - digest = "1:ade392a843b2035effb4b4a2efa2c3bab3eb29b992e98bacf9c898b0ecb54e45" name = "github.com/fatih/color" packages = ["."] - pruneopts = "NUT" revision = "5b77d2a35fb0ede96d138fc9a99f5c9b6aef11b4" version = "v1.7.0" [[projects]] - digest = "1:1b91ae0dc69a41d4c2ed23ea5cffb721ea63f5037ca4b81e6d6771fbb8f45129" name = "github.com/fsnotify/fsnotify" packages = ["."] - pruneopts = "NUT" revision = "c2828203cd70a50dcccfb2761f8b1f8ceef9a8e9" version = "v1.4.7" [[projects]] branch = "master" - digest = "1:4a8ed9b8cf22bd03bee5d74179fa06a282e4a73b6de949f7a865ff56cd2537e0" name = "github.com/golang-collections/collections" packages = ["stack"] - pruneopts = "NUT" revision = "604e922904d35e97f98a774db7881f049cd8d970" [[projects]] branch = "master" - digest = "1:11c6c696067d3127ecf332b10f89394d386d9083f82baf71f40f2da31841a009" name = "github.com/hashicorp/hcl" packages = [ ".", @@ -78,218 +63,180 @@ "hcl/token", "json/parser", "json/scanner", - "json/token", + "json/token" ] - pruneopts = "NUT" revision = "ef8a98b0bbce4a65b5aa4c368430a80ddc533168" [[projects]] branch = "master" - digest = "1:62fe3a7ea2050ecbd753a71889026f83d73329337ada66325cbafd5dea5f713d" name = "github.com/jbenet/go-context" packages = ["io"] - pruneopts = "NUT" revision = "d14ea06fba99483203c19d92cfcd13ebe73135f4" [[projects]] branch = "master" - digest = "1:c9a848b0484a72da2dae28957b4f67501fe27fa38bc73f4713e454353c0a4a60" name = "github.com/jesseduffield/gocui" packages = ["."] - pruneopts = "NUT" revision = "432b7f6215f81ef1aaa1b2d9b69887822923cf79" [[projects]] - digest = "1:8021af4dcbd531ae89433c8c3a6520e51064114aaf8eb1724c3cf911c497c9ba" name = "github.com/kevinburke/ssh_config" packages = ["."] - pruneopts = "NUT" revision = "9fc7bb800b555d63157c65a904c86a2cc7b4e795" version = "0.4" [[projects]] - digest = "1:d244f8666a838fe6ad70ec8fe77f50ebc29fdc3331a2729ba5886bef8435d10d" name = "github.com/magiconair/properties" packages = ["."] - pruneopts = "NUT" revision = "c2353362d570a7bfa228149c62842019201cfb71" version = "v1.8.0" [[projects]] - digest = "1:08c231ec84231a7e23d67e4b58f975e1423695a32467a362ee55a803f9de8061" name = "github.com/mattn/go-colorable" packages = ["."] - pruneopts = "NUT" revision = "167de6bfdfba052fa6b2d3664c8f5272e23c9072" version = "v0.0.9" [[projects]] - digest = "1:bc4f7eec3b7be8c6cb1f0af6c1e3333d5bb71072951aaaae2f05067b0803f287" name = "github.com/mattn/go-isatty" packages = ["."] - pruneopts = "NUT" revision = "0360b2af4f38e8d38c7fce2a9f4e702702d73a39" version = "v0.0.3" [[projects]] - digest = "1:cb591533458f6eb6e2c1065ff3eac6b50263d7847deb23fc9f79b25bc608970e" name = "github.com/mattn/go-runewidth" packages = ["."] - pruneopts = "NUT" revision = "9e777a8366cce605130a531d2cd6363d07ad7317" version = "v0.0.2" [[projects]] - digest = "1:a25c9a6b41e100f4ce164db80260f2b687095ba9d8b46a1d6072d3686cc020db" name = "github.com/mgutz/str" packages = ["."] - pruneopts = "NUT" revision = "968bf66e3da857419e4f6e71b2d5c9ae95682dc4" version = "v1.2.0" [[projects]] branch = "master" - digest = "1:a4df73029d2c42fabcb6b41e327d2f87e685284ec03edf76921c267d9cfc9c23" name = "github.com/mitchellh/go-homedir" packages = ["."] - pruneopts = "NUT" revision = "58046073cbffe2f25d425fe1331102f55cf719de" [[projects]] branch = "master" - digest = "1:5fe20cfe4ef484c237cec9f947b2a6fa90bad4b8610fd014f0e4211e13d82d5d" name = "github.com/mitchellh/mapstructure" packages = ["."] - pruneopts = "NUT" revision = "f15292f7a699fcc1a38a80977f80a046874ba8ac" [[projects]] - digest = "1:2c34c77bf3ec848da26e48af58fc511ed52750961fa848399d122882b8890928" name = "github.com/nicksnyder/go-i18n" packages = [ "v2/i18n", "v2/internal", - "v2/internal/plural", + "v2/internal/plural" ] - pruneopts = "NUT" revision = "a16b91a3ba80db3a2301c70d1d302d42251c9079" version = "v2.0.0-beta.5" [[projects]] branch = "master" - digest = "1:34d9354c2c5d916c05864327553047df59fc10e86ff1f408e4136eba0a25a5ec" name = "github.com/nsf/termbox-go" packages = ["."] - pruneopts = "NUT" revision = "5c94acc5e6eb520f1bcd183974e01171cc4c23b3" [[projects]] - digest = "1:cf254277d898b713195cc6b4a3fac8bf738b9f1121625df27843b52b267eec6c" name = "github.com/pelletier/go-buffruneio" packages = ["."] - pruneopts = "NUT" revision = "c37440a7cf42ac63b919c752ca73a85067e05992" version = "v0.2.0" [[projects]] - digest = "1:51ea800cff51752ff68e12e04106f5887b4daec6f9356721238c28019f0b42db" name = "github.com/pelletier/go-toml" packages = ["."] - pruneopts = "NUT" revision = "c01d1270ff3e442a8a57cddc1c92dc1138598194" version = "v1.2.0" [[projects]] - digest = "1:d917313f309bda80d27274d53985bc65651f81a5b66b820749ac7f8ef061fd04" + name = "github.com/pmezard/go-difflib" + packages = ["difflib"] + revision = "792786c7400a136282c1664665ae0a8db921c6c2" + version = "v1.0.0" + +[[projects]] name = "github.com/sergi/go-diff" packages = ["diffmatchpatch"] - pruneopts = "NUT" revision = "1744e2970ca51c86172c8190fadad617561ed6e7" version = "v1.0.0" [[projects]] branch = "master" - digest = "1:41618aee8828e62dfe62d44f579c06892d0e98907d1c6d5bcd83bfe8536ec5a3" name = "github.com/shibukawa/configdir" packages = ["."] - pruneopts = "NUT" revision = "e180dbdc8da04c4fa04272e875ce64949f38bd3e" [[projects]] - digest = "1:330e9062b308ac597e28485699c02223bd052437a6eed32a173c9227dcb9d95a" name = "github.com/spf13/afero" packages = [ ".", - "mem", + "mem" ] - pruneopts = "NUT" revision = "787d034dfe70e44075ccc060d346146ef53270ad" version = "v1.1.1" [[projects]] - digest = "1:3fa7947ca83b98ae553590d993886e845a4bff19b7b007e869c6e0dd3b9da9cd" name = "github.com/spf13/cast" packages = ["."] - pruneopts = "NUT" revision = "8965335b8c7107321228e3e3702cab9832751bac" version = "v1.2.0" [[projects]] branch = "master" - digest = "1:f29f83301ed096daed24a90f4af591b7560cb14b9cc3e1827abbf04db7269ab5" name = "github.com/spf13/jwalterweatherman" packages = ["."] - pruneopts = "NUT" revision = "14d3d4c518341bea657dd8a226f5121c0ff8c9f2" [[projects]] - digest = "1:e3707aeaccd2adc89eba6c062fec72116fe1fc1ba71097da85b4d8ae1668a675" name = "github.com/spf13/pflag" packages = ["."] - pruneopts = "NUT" revision = "9a97c102cda95a86cec2345a6f09f55a939babf5" version = "v1.0.2" [[projects]] - digest = "1:454979540e2a1582f375a17c106cf4e11e3bcac4baffb4af23e515c87f87de13" name = "github.com/spf13/viper" packages = ["."] - pruneopts = "NUT" revision = "907c19d40d9a6c9bb55f040ff4ae45271a4754b9" version = "v1.1.0" [[projects]] - digest = "1:ccca1dcd18bc54e23b517a3c5babeff2e3924a7d8fc1932162225876cfe4bfb0" name = "github.com/src-d/gcfg" packages = [ ".", "scanner", "token", - "types", + "types" ] - pruneopts = "NUT" revision = "f187355171c936ac84a82793659ebb4936bc1c23" version = "v1.3.0" [[projects]] - digest = "1:cd5ffc5bda4e0296ab3e4de90dbb415259c78e45e7fab13694b14cde8ab74541" + name = "github.com/stretchr/testify" + packages = ["assert"] + revision = "f35b8ab0b5a2cef36673838d662e249dd9c94686" + version = "v1.2.2" + +[[projects]] name = "github.com/tcnksm/go-gitconfig" packages = ["."] - pruneopts = "NUT" revision = "d154598bacbf4501c095a309753c5d4af66caa81" version = "v0.1.2" [[projects]] - digest = "1:3148cb3478c26a92b4c1a18abb9428234b281e278af6267840721a24b6cbc6a3" name = "github.com/xanzy/ssh-agent" packages = ["."] - pruneopts = "NUT" revision = "640f0ab560aeb89d523bb6ac322b1244d5c3796c" version = "v0.2.0" [[projects]] branch = "master" - digest = "1:dfcb1b2db354cafa48fc3cdafe4905a08bec4a9757919ab07155db0ca23855b4" name = "golang.org/x/crypto" packages = [ "cast5", @@ -308,32 +255,26 @@ "ssh", "ssh/agent", "ssh/knownhosts", - "ssh/terminal", + "ssh/terminal" ] - pruneopts = "NUT" revision = "de0752318171da717af4ce24d0a2e8626afaeb11" [[projects]] branch = "master" - digest = "1:76ee51c3f468493aff39dbacc401e8831fbb765104cbf613b89bef01cf4bad70" name = "golang.org/x/net" packages = ["context"] - pruneopts = "NUT" revision = "c39426892332e1bb5ec0a434a079bf82f5d30c54" [[projects]] branch = "master" - digest = "1:ec76a40fbfda0c329ee58f4e3b14b4279a939efce89eca020e934e2e5234eddd" name = "golang.org/x/sys" packages = [ "unix", - "windows", + "windows" ] - pruneopts = "NUT" revision = "98c5dad5d1a0e8a73845ecc8897d0bd56586511d" [[projects]] - digest = "1:a95288ef1ef4dfad6cba7fe30843e1683f71bc28c912ca1ba3f6a539d44db739" name = "golang.org/x/text" packages = [ "internal/gen", @@ -343,28 +284,24 @@ "language", "transform", "unicode/cldr", - "unicode/norm", + "unicode/norm" ] - pruneopts = "NUT" revision = "f21a4dfb5e38f5895301dc265a8def02365cc3d0" version = "v0.3.0" [[projects]] - digest = "1:47a697b155f5214ff14e68e39ce9c2e8d93e1fb035ae5ba7e247d044e0ce64e3" name = "gopkg.in/src-d/go-billy.v4" packages = [ ".", "helper/chroot", "helper/polyfill", "osfs", - "util", + "util" ] - pruneopts = "NUT" revision = "83cf655d40b15b427014d7875d10850f96edba14" version = "v4.2.0" [[projects]] - digest = "1:e66078da2bd6e53c72518d7f6ae0c3c8c7f34c0df12c39435ce34a6bce165525" name = "gopkg.in/src-d/go-git.v4" packages = [ ".", @@ -406,45 +343,25 @@ "utils/merkletrie/filesystem", "utils/merkletrie/index", "utils/merkletrie/internal/frame", - "utils/merkletrie/noder", + "utils/merkletrie/noder" ] - pruneopts = "NUT" revision = "43d17e14b714665ab5bc2ecc220b6740779d733f" [[projects]] - digest = "1:b233ad4ec87ac916e7bf5e678e98a2cb9e8b52f6de6ad3e11834fc7a71b8e3bf" name = "gopkg.in/warnings.v0" packages = ["."] - pruneopts = "NUT" revision = "ec4a0fea49c7b46c2aeb0b51aac55779c607e52b" version = "v0.1.2" [[projects]] - digest = "1:7c95b35057a0ff2e19f707173cc1a947fa43a6eb5c4d300d196ece0334046082" name = "gopkg.in/yaml.v2" packages = ["."] - pruneopts = "NUT" revision = "5420a8b6744d3b0345ab293f6fcba19c978f1183" version = "v2.2.1" [solve-meta] analyzer-name = "dep" analyzer-version = 1 - input-imports = [ - "github.com/Sirupsen/logrus", - "github.com/cloudfoundry/jibber_jabber", - "github.com/davecgh/go-spew/spew", - "github.com/fatih/color", - "github.com/golang-collections/collections/stack", - "github.com/jesseduffield/gocui", - "github.com/mgutz/str", - "github.com/nicksnyder/go-i18n/v2/i18n", - "github.com/shibukawa/configdir", - "github.com/spf13/viper", - "github.com/tcnksm/go-gitconfig", - "golang.org/x/text/language", - "gopkg.in/src-d/go-git.v4", - "gopkg.in/src-d/go-git.v4/plumbing", - ] + inputs-digest = "ad8efec24df196d55f26988aca5a065ba7c7e15614eeca2bb433f37a28cfb1b1" solver-name = "gps-cdcl" solver-version = 1 diff --git a/pkg/utils/utils_test.go b/pkg/utils/utils_test.go new file mode 100644 index 000000000..58e78cce9 --- /dev/null +++ b/pkg/utils/utils_test.go @@ -0,0 +1,83 @@ +package utils + +import ( + "testing" + + "github.com/stretchr/testify/assert" +) + +func TestSplitLines(t *testing.T) { + type scenario struct { + multilineString string + expected []string + } + + scenarios := []scenario{ + { + "", + []string{}, + }, + { + "\n", + []string{}, + }, + { + "hello world !\nhello universe !\n", + []string{ + "hello world !", + "hello universe !", + }, + }, + } + + for _, s := range scenarios { + assert.EqualValues(t, s.expected, SplitLines(s.multilineString)) + } +} + +func TestWithPadding(t *testing.T) { + type scenario struct { + str string + padding int + expected string + } + + scenarios := []scenario{ + { + "hello world !", + 1, + "hello world !", + }, + { + "hello world !", + 14, + "hello world ! ", + }, + } + + for _, s := range scenarios { + assert.EqualValues(t, s.expected, WithPadding(s.str, s.padding)) + } +} + +func TestTrimTrailingNewline(t *testing.T) { + type scenario struct { + str string + expected string + } + + scenarios := []scenario{ + { + "hello world !\n", + "hello world !", + }, + { + "hello world !", + "hello world !", + }, + } + + for _, s := range scenarios { + assert.EqualValues(t, s.expected, TrimTrailingNewline(s.str)) + } +} diff --git a/vendor/github.com/pmezard/go-difflib/LICENSE b/vendor/github.com/pmezard/go-difflib/LICENSE new file mode 100644 index 000000000..c67dad612 --- /dev/null +++ b/vendor/github.com/pmezard/go-difflib/LICENSE @@ -0,0 +1,27 @@ +Copyright (c) 2013, Patrick Mezard +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are +met: + + Redistributions of source code must retain the above copyright +notice, this list of conditions and the following disclaimer. + Redistributions in binary form must reproduce the above copyright +notice, this list of conditions and the following disclaimer in the +documentation and/or other materials provided with the distribution. + The names of its contributors may not be used to endorse or promote +products derived from this software without specific prior written +permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS +IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED +TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A +PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED +TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR +PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING +NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS +SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. diff --git a/vendor/github.com/pmezard/go-difflib/difflib/difflib.go b/vendor/github.com/pmezard/go-difflib/difflib/difflib.go new file mode 100644 index 000000000..003e99fad --- /dev/null +++ b/vendor/github.com/pmezard/go-difflib/difflib/difflib.go @@ -0,0 +1,772 @@ +// Package difflib is a partial port of Python difflib module. +// +// It provides tools to compare sequences of strings and generate textual diffs. +// +// The following class and functions have been ported: +// +// - SequenceMatcher +// +// - unified_diff +// +// - context_diff +// +// Getting unified diffs was the main goal of the port. Keep in mind this code +// is mostly suitable to output text differences in a human friendly way, there +// are no guarantees generated diffs are consumable by patch(1). +package difflib + +import ( + "bufio" + "bytes" + "fmt" + "io" + "strings" +) + +func min(a, b int) int { + if a < b { + return a + } + return b +} + +func max(a, b int) int { + if a > b { + return a + } + return b +} + +func calculateRatio(matches, length int) float64 { + if length > 0 { + return 2.0 * float64(matches) / float64(length) + } + return 1.0 +} + +type Match struct { + A int + B int + Size int +} + +type OpCode struct { + Tag byte + I1 int + I2 int + J1 int + J2 int +} + +// SequenceMatcher compares sequence of strings. The basic +// algorithm predates, and is a little fancier than, an algorithm +// published in the late 1980's by Ratcliff and Obershelp under the +// hyperbolic name "gestalt pattern matching". The basic idea is to find +// the longest contiguous matching subsequence that contains no "junk" +// elements (R-O doesn't address junk). The same idea is then applied +// recursively to the pieces of the sequences to the left and to the right +// of the matching subsequence. This does not yield minimal edit +// sequences, but does tend to yield matches that "look right" to people. +// +// SequenceMatcher tries to compute a "human-friendly diff" between two +// sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the +// longest *contiguous* & junk-free matching subsequence. That's what +// catches peoples' eyes. The Windows(tm) windiff has another interesting +// notion, pairing up elements that appear uniquely in each sequence. +// That, and the method here, appear to yield more intuitive difference +// reports than does diff. This method appears to be the least vulnerable +// to synching up on blocks of "junk lines", though (like blank lines in +// ordinary text files, or maybe "<P>" lines in HTML files). That may be +// because this is the only method of the 3 that has a *concept* of +// "junk" <wink>. +// +// Timing: Basic R-O is cubic time worst case and quadratic time expected +// case. SequenceMatcher is quadratic time for the worst case and has +// expected-case behavior dependent in a complicated way on how many +// elements the sequences have in common; best case time is linear. +type SequenceMatcher struct { + a []string + b []string + b2j map[string][]int + IsJunk func(string) bool + autoJunk bool + bJunk map[string]struct{} + matchingBlocks []Match + fullBCount map[string]int + bPopular map[string]struct{} + opCodes []OpCode +} + +func NewMatcher(a, b []string) *SequenceMatcher { + m := SequenceMatcher{autoJunk: true} + m.SetSeqs(a, b) + return &m +} + +func NewMatcherWithJunk(a, b []string, autoJunk bool, + isJunk func(string) bool) *SequenceMatcher { + + m := SequenceMatcher{IsJunk: isJunk, autoJunk: autoJunk} + m.SetSeqs(a, b) + return &m +} + +// Set two sequences to be compared. +func (m *SequenceMatcher) SetSeqs(a, b []string) { + m.SetSeq1(a) + m.SetSeq2(b) +} + +// Set the first sequence to be compared. The second sequence to be compared is +// not changed. +// +// SequenceMatcher computes and caches detailed information about the second +// sequence, so if you want to compare one sequence S against many sequences, +// use .SetSeq2(s) once and call .SetSeq1(x) repeatedly for each of the other +// sequences. +// +// See also SetSeqs() and SetSeq2(). +func (m *SequenceMatcher) SetSeq1(a []string) { + if &a == &m.a { + return + } + m.a = a + m.matchingBlocks = nil + m.opCodes = nil +} + +// Set the second sequence to be compared. The first sequence to be compared is +// not changed. +func (m *SequenceMatcher) SetSeq2(b []string) { + if &b == &m.b { + return + } + m.b = b + m.matchingBlocks = nil + m.opCodes = nil + m.fullBCount = nil + m.chainB() +} + +func (m *SequenceMatcher) chainB() { + // Populate line -> index mapping + b2j := map[string][]int{} + for i, s := range m.b { + indices := b2j[s] + indices = append(indices, i) + b2j[s] = indices + } + + // Purge junk elements + m.bJunk = map[string]struct{}{} + if m.IsJunk != nil { + junk := m.bJunk + for s, _ := range b2j { + if m.IsJunk(s) { + junk[s] = struct{}{} + } + } + for s, _ := range junk { + delete(b2j, s) + } + } + + // Purge remaining popular elements + popular := map[string]struct{}{} + n := len(m.b) + if m.autoJunk && n >= 200 { + ntest := n/100 + 1 + for s, indices := range b2j { + if len(indices) > ntest { + popular[s] = struct{}{} + } + } + for s, _ := range popular { + delete(b2j, s) + } + } + m.bPopular = popular + m.b2j = b2j +} + +func (m *SequenceMatcher) isBJunk(s string) bool { + _, ok := m.bJunk[s] + return ok +} + +// Find longest matching block in a[alo:ahi] and b[blo:bhi]. +// +// If IsJunk is not defined: +// +// Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where +// alo <= i <= i+k <= ahi +// blo <= j <= j+k <= bhi +// and for all (i',j',k') meeting those conditions, +// k >= k' +// i <= i' +// and if i == i', j <= j' +// +// In other words, of all maximal matching blocks, return one that +// starts earliest in a, and of all those maximal matching blocks that +// start earliest in a, return the one that starts earliest in b. +// +// If IsJunk is defined, first the longest matching block is +// determined as above, but with the additional restriction that no +// junk element appears in the block. Then that block is extended as +// far as possible by matching (only) junk elements on both sides. So +// the resulting block never matches on junk except as identical junk +// happens to be adjacent to an "interesting" match. +// +// If no blocks match, return (alo, blo, 0). +func (m *SequenceMatcher) findLongestMatch(alo, ahi, blo, bhi int) Match { + // CAUTION: stripping common prefix or suffix would be incorrect. + // E.g., + // ab + // acab + // Longest matching block is "ab", but if common prefix is + // stripped, it's "a" (tied with "b"). UNIX(tm) diff does so + // strip, so ends up claiming that ab is changed to acab by + // inserting "ca" in the middle. That's minimal but unintuitive: + // "it's obvious" that someone inserted "ac" at the front. + // Windiff ends up at the same place as diff, but by pairing up + // the unique 'b's and then matching the first two 'a's. + besti, bestj, bestsize := alo, blo, 0 + + // find longest junk-free match + // during an iteration of the loop, j2len[j] = length of longest + // junk-free match ending with a[i-1] and b[j] + j2len := map[int]int{} + for i := alo; i != ahi; i++ { + // look at all instances of a[i] in b; note that because + // b2j has no junk keys, the loop is skipped if a[i] is junk + newj2len := map[int]int{} + for _, j := range m.b2j[m.a[i]] { + // a[i] matches b[j] + if j < blo { + continue + } + if j >= bhi { + break + } + k := j2len[j-1] + 1 + newj2len[j] = k + if k > bestsize { + besti, bestj, bestsize = i-k+1, j-k+1, k + } + } + j2len = newj2len + } + + // Extend the best by non-junk elements on each end. In particular, + // "popular" non-junk elements aren't in b2j, which greatly speeds + // the inner loop above, but also means "the best" match so far + // doesn't contain any junk *or* popular non-junk elements. + for besti > alo && bestj > blo && !m.isBJunk(m.b[bestj-1]) && + m.a[besti-1] == m.b[bestj-1] { + besti, bestj, bestsize = besti-1, bestj-1, bestsize+1 + } + for besti+bestsize < ahi && bestj+bestsize < bhi && + !m.isBJunk(m.b[bestj+bestsize]) && + m.a[besti+bestsize] == m.b[bestj+bestsize] { + bestsize += 1 + } + + // Now that we have a wholly interesting match (albeit possibly + // empty!), we may as well suck up the matching junk on each + // side of it too. Can't think of a good reason not to, and it + // saves post-processing the (possibly considerable) expense of + // figuring out what to do with it. In the case of an empty + // interesting match, this is clearly the right thing to do, + // because no other kind of match is possible in the regions. + for besti > alo && bestj > blo && m.isBJunk(m.b[bestj-1]) && + m.a[besti-1] == m.b[bestj-1] { + besti, bestj, bestsize = besti-1, bestj-1, bestsize+1 + } + for besti+bestsize < ahi && bestj+bestsize < bhi && + m.isBJunk(m.b[bestj+bestsize]) && + m.a[besti+bestsize] == m.b[bestj+bestsize] { + bestsize += 1 + } + + return Match{A: besti, B: bestj, Size: bestsize} +} + +// Return list of triples describing matching subsequences. +// +// Each triple is of the form (i, j, n), and means that +// a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in +// i and in j. It's also guaranteed that if (i, j, n) and (i', j', n') are +// adjacent triples in the list, and the second is not the last triple in the +// list, then i+n != i' or j+n != j'. IOW, adjacent triples never describe +// adjacent equal blocks. +// +// The last triple is a dummy, (len(a), len(b), 0), and is the only +// triple with n==0. +func (m *SequenceMatcher) GetMatchingBlocks() []Match { + if m.matchingBlocks != nil { + return m.matchingBlocks + } + + var matchBlocks func(alo, ahi, blo, bhi int, matched []Match) []Match + matchBlocks = func(alo, ahi, blo, bhi int, matched []Match) []Match { + match := m.findLongestMatch(alo, ahi, blo, bhi) + i, j, k := match.A, match.B, match.Size + if match.Size > 0 { + if alo < i && blo < j { + matched = matchBlocks(alo, i, blo, j, matched) + } + matched = append(matched, match) + if i+k < ahi && j+k < bhi { + matched = matchBlocks(i+k, ahi, j+k, bhi, matched) + } + } + return matched + } + matched := matchBlocks(0, len(m.a), 0, len(m.b), nil) + + // It's possible that we have adjacent equal blocks in the + // matching_blocks list now. + nonAdjacent := []Match{} + i1, j1, k1 := 0, 0, 0 + for _, b := range matched { + // Is this block adjacent to i1, j1, k1? + i2, j2, k2 := b.A, b.B, b.Size + if i1+k1 == i2 && j1+k1 == j2 { + // Yes, so collapse them -- this just increases the length of + // the first block by the length of the second, and the first + // block so lengthened remains the block to compare against. + k1 += k2 + } else { + // Not adjacent. Remember the first block (k1==0 means it's + // the dummy we started with), and make the second block the + // new block to compare against. + if k1 > 0 { + nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) + } + i1, j1, k1 = i2, j2, k2 + } + } + if k1 > 0 { + nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) + } + + nonAdjacent = append(nonAdjacent, Match{len(m.a), len(m.b), 0}) + m.matchingBlocks = nonAdjacent + return m.matchingBlocks +} + +// Return list of 5-tuples describing how to turn a into b. +// +// Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple +// has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the +// tuple preceding it, and likewise for j1 == the previous j2. +// +// The tags are characters, with these meanings: +// +// 'r' (replace): a[i1:i2] should be replaced by b[j1:j2] +// +// 'd' (delete): a[i1:i2] should be deleted, j1==j2 in this case. +// +// 'i' (insert): b[j1:j2] should be inserted at a[i1:i1], i1==i2 in this case. +// +// 'e' (equal): a[i1:i2] == b[j1:j2] +func (m *SequenceMatcher) GetOpCodes() []OpCode { + if m.opCodes != nil { + return m.opCodes + } + i, j := 0, 0 + matching := m.GetMatchingBlocks() + opCodes := make([]OpCode, 0, len(matching)) + for _, m := range matching { + // invariant: we've pumped out correct diffs to change + // a[:i] into b[:j], and the next matching block is + // a[ai:ai+size] == b[bj:bj+size]. So we need to pump + // out a diff to change a[i:ai] into b[j:bj], pump out + // the matching block, and move (i,j) beyond the match + ai, bj, size := m.A, m.B, m.Size + tag := byte(0) + if i < ai && j < bj { + tag = 'r' + } else if i < ai { + tag = 'd' + } else if j < bj { + tag = 'i' + } + if tag > 0 { + opCodes = append(opCodes, OpCode{tag, i, ai, j, bj}) + } + i, j = ai+size, bj+size + // the list of matching blocks is terminated by a + // sentinel with size 0 + if size > 0 { + opCodes = append(opCodes, OpCode{'e', ai, i, bj, j}) + } + } + m.opCodes = opCodes + return m.opCodes +} + +// Isolate change clusters by eliminating ranges with no changes. +// +// Return a generator of groups with up to n lines of context. +// Each group is in the same format as returned by GetOpCodes(). +func (m *SequenceMatcher) GetGroupedOpCodes(n int) [][]OpCode { + if n < 0 { + n = 3 + } + codes := m.GetOpCodes() + if len(codes) == 0 { + codes = []OpCode{OpCode{'e', 0, 1, 0, 1}} + } + // Fixup leading and trailing groups if they show no changes. + if codes[0].Tag == 'e' { + c := codes[0] + i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2 + codes[0] = OpCode{c.Tag, max(i1, i2-n), i2, max(j1, j2-n), j2} + } + if codes[len(codes)-1].Tag == 'e' { + c := codes[len(codes)-1] |