diff options
23 files changed, 4037 insertions, 52 deletions
diff --git a/.goreleaser.yml b/.goreleaser.yml index 6ae81e27d..8f8da01ee 100644 --- a/.goreleaser.yml +++ b/.goreleaser.yml @@ -13,8 +13,6 @@ builds: - arm - arm64 - 386 - ldflags: - - -s -w -X main.version={{.Version}} -X main.tag={{.Tag}} -X main.date={{.Date}} -X main.commit={{.Commit}} -X main.goos={{.Os}} -X main.arch={{.Arch}} -X main.arm={{.Arm}} archive: replacements: diff --git a/Gopkg.lock b/Gopkg.lock index 662a9c28d..dc92d8e90 100644 --- a/Gopkg.lock +++ b/Gopkg.lock @@ -200,6 +200,14 @@ version = "v1.2.0" [[projects]] + digest = "1:0028cb19b2e4c3112225cd871870f2d9cf49b9b4276531f03438a88e94be86fe" + name = "github.com/pmezard/go-difflib" + packages = ["difflib"] + pruneopts = "NUT" + revision = "792786c7400a136282c1664665ae0a8db921c6c2" + version = "v1.0.0" + +[[projects]] digest = "1:d917313f309bda80d27274d53985bc65651f81a5b66b820749ac7f8ef061fd04" name = "github.com/sergi/go-diff" packages = ["diffmatchpatch"] @@ -272,6 +280,14 @@ version = "v1.3.0" [[projects]] + digest = "1:bacb8b590716ab7c33f2277240972c9582d389593ee8d66fc10074e0508b8126" + name = "github.com/stretchr/testify" + packages = ["assert"] + pruneopts = "NUT" + revision = "f35b8ab0b5a2cef36673838d662e249dd9c94686" + version = "v1.2.2" + +[[projects]] digest = "1:cd5ffc5bda4e0296ab3e4de90dbb415259c78e45e7fab13694b14cde8ab74541" name = "github.com/tcnksm/go-gitconfig" packages = ["."] @@ -441,6 +457,7 @@ "github.com/nicksnyder/go-i18n/v2/i18n", "github.com/shibukawa/configdir", "github.com/spf13/viper", + "github.com/stretchr/testify/assert", "github.com/tcnksm/go-gitconfig", "golang.org/x/text/language", "gopkg.in/src-d/go-git.v4", diff --git a/VERSION b/VERSION deleted file mode 100644 index 71b47abc8..000000000 --- a/VERSION +++ /dev/null @@ -1 +0,0 @@ -v0.1.70
\ No newline at end of file @@ -3,7 +3,6 @@ package main import ( "flag" "fmt" - "io/ioutil" "os" "path/filepath" "runtime" @@ -26,23 +25,8 @@ func projectPath(path string) string { return filepath.FromSlash(gopath + "/src/github.com/jesseduffield/lazygit/" + path) } -// when building the binary, `version` is set as a compile-time variable, along -// with `date` and `commit`. If this program has been opened directly via go, -// we will populate the `version` with VERSION in the lazygit root directory -func fallbackVersion() string { - path := projectPath("VERSION") - byteVersion, err := ioutil.ReadFile(path) - if err != nil { - return "unversioned" - } - return string(byteVersion) -} - func main() { flag.Parse() - if version == "unversioned" { - version = fallbackVersion() - } if *versionFlag { fmt.Printf("commit=%s, build date=%s, version=%s, os=%s, arch=%s\n", commit, date, version, runtime.GOOS, runtime.GOARCH) os.Exit(0) diff --git a/pkg/commands/git.go b/pkg/commands/git.go index 95a60e8a6..bf9aa6646 100644 --- a/pkg/commands/git.go +++ b/pkg/commands/git.go @@ -83,7 +83,7 @@ func (c *GitCommand) GetStatusFiles() []File { filename := statusString[3:] tracked := !includes([]string{"??", "A ", "AM"}, change) file := File{ - Name: filename, + Name: c.OSCommand.Unquote(filename), DisplayString: statusString, HasStagedChanges: !includes([]string{" ", "U", "?"}, stagedChange), HasUnstagedChanges: unstagedChange != " ", @@ -270,8 +270,12 @@ func (c *GitCommand) Pull() error { } // Push push to a branch -func (c *GitCommand) Push(branchName string) error { - return c.OSCommand.RunCommand("git push -u origin " + branchName) +func (c *GitCommand) Push(branchName string, force bool) error { + forceFlag := "" + if force { + forceFlag = "--force-with-lease " + } + return c.OSCommand.RunCommand("git push " + forceFlag + "-u origin " + branchName) } // SquashPreviousTwoCommits squashes a commit down to the one below it @@ -321,24 +325,24 @@ func (c *GitCommand) SquashFixupCommit(branchName string, shaValue string) error } // CatFile obtain the contents of a file -func (c *GitCommand) CatFile(file string) (string, error) { - return c.OSCommand.RunCommandWithOutput("cat " + file) +func (c *GitCommand) CatFile(fileName string) (string, error) { + return c.OSCommand.RunCommandWithOutput("cat " + c.OSCommand.Quote(fileName)) } // StageFile stages a file -func (c *GitCommand) StageFile(file string) error { - return c.OSCommand.RunCommand("git add " + c.OSCommand.Quote(file)) +func (c *GitCommand) StageFile(fileName string) error { + return c.OSCommand.RunCommand("git add " + c.OSCommand.Quote(fileName)) } // UnStageFile unstages a file -func (c *GitCommand) UnStageFile(file string, tracked bool) error { +func (c *GitCommand) UnStageFile(fileName string, tracked bool) error { var command string if tracked { command = "git reset HEAD " } else { command = "git rm --cached " } - return c.OSCommand.RunCommand(command + file) + return c.OSCommand.RunCommand(command + c.OSCommand.Quote(fileName)) } // GitStatus returns the plaintext short status of the repo @@ -364,7 +368,7 @@ func (c *GitCommand) RemoveFile(file File) error { } } if !file.Tracked { - return os.RemoveAll(c.OSCommand.Unquote(file.Name)) + return os.RemoveAll(file.Name) } // if the file is tracked, we assume you want to just check it out return c.OSCommand.RunCommand("git checkout -- " + file.Name) @@ -461,10 +465,8 @@ func (c *GitCommand) GetLog() string { } // Ignore adds a file to the gitignore for the repo -func (c *GitCommand) Ignore(filename string) { - if _, err := c.OSCommand.RunDirectCommand("echo '" + filename + "' >> .gitignore"); err != nil { - panic(err) - } +func (c *GitCommand) Ignore(filename string) error { + return c.OSCommand.AppendLineToFile(".gitignore", filename) } // Show shows the diff of a commit @@ -479,12 +481,9 @@ func (c *GitCommand) Show(sha string) string { // Diff returns the diff of a file func (c *GitCommand) Diff(file File) string { cachedArg := "" - fileName := file.Name + fileName := c.OSCommand.Quote(file.Name) if file.HasStagedChanges && !file.HasUnstagedChanges { cachedArg = "--cached" - } else { - // if the file is staged and has spaces in it, it comes pre-quoted - fileName = c.OSCommand.Quote(fileName) } trackedArg := "--" if !file.Tracked && !file.HasStagedChanges { diff --git a/pkg/commands/git_test.go b/pkg/commands/git_test.go index 1cd9901b3..9c2a64330 100644 --- a/pkg/commands/git_test.go +++ b/pkg/commands/git_test.go @@ -45,7 +45,7 @@ func TestDiff(t *testing.T) { DisplayString: " D deleted_staged", }, { - Name: "\"file with space staged\"", + Name: "file with space staged", HasStagedChanges: true, HasUnstagedChanges: false, Tracked: false, diff --git a/pkg/commands/os.go b/pkg/commands/os.go index b72585e44..9756d619d 100644 --- a/pkg/commands/os.go +++ b/pkg/commands/os.go @@ -174,3 +174,14 @@ func (c *OSCommand) Unquote(message string) string { message = strings.Replace(message, `"`, "", -1) return message } + +func (C *OSCommand) AppendLineToFile(filename, line string) error { + f, err := os.OpenFile(filename, os.O_APPEND|os.O_WRONLY|os.O_CREATE, 0600) + if err != nil { + return err + } + defer f.Close() + + _, err = f.WriteString("\n" + line) + return err +} diff --git a/pkg/gui/commits_panel.go b/pkg/gui/commits_panel.go index 417b947a2..c428e3b99 100644 --- a/pkg/gui/commits_panel.go +++ b/pkg/gui/commits_panel.go @@ -74,7 +74,7 @@ func (gui *Gui) handleCommitSelect(g *gocui.Gui, v *gocui.View) error { } commit, err := gui.getSelectedCommit(g) if err != nil { - if err != errors.New(gui.Tr.SLocalize("NoCommitsThisBranch")) { + if err.Error() != gui.Tr.SLocalize("NoCommitsThisBranch") { return err } return gui.renderString(g, "main", gui.Tr.SLocalize("NoCommitsThisBranch")) diff --git a/pkg/gui/files_panel.go b/pkg/gui/files_panel.go index 596eb80cc..5791a9d15 100644 --- a/pkg/gui/files_panel.go +++ b/pkg/gui/files_panel.go @@ -142,7 +142,9 @@ func (gui *Gui) handleIgnoreFile(g *gocui.Gui, v *gocui.View) error { if file.Tracked { return gui.createErrorPanel(g, gui.Tr.SLocalize("CantIgnoreTrackFiles")) } - gui.GitCommand.Ignore(file.Name) + if err := gui.GitCommand.Ignore(file.Name); err != nil { + return gui.createErrorPanel(g, err.Error()) + } return gui.refreshFiles(g) } @@ -358,21 +360,35 @@ func (gui *Gui) pullFiles(g *gocui.Gui, v *gocui.View) error { return nil } -func (gui *Gui) pushFiles(g *gocui.Gui, v *gocui.View) error { - gui.createMessagePanel(g, v, "", gui.Tr.SLocalize("PushWait")) +func (gui *Gui) pushWithForceFlag(currentView *gocui.View, force bool) error { + if err := gui.createMessagePanel(gui.g, currentView, "", gui.Tr.SLocalize("PushWait")); err != nil { + return err + } go func() { branchName := gui.State.Branches[0].Name - if err := gui.GitCommand.Push(branchName); err != nil { - gui.createErrorPanel(g, err.Error()) + if err := gui.GitCommand.Push(branchName, force); err != nil { + _ = gui.createErrorPanel(gui.g, err.Error()) } else { - gui.closeConfirmationPrompt(g) - gui.refreshCommits(g) - gui.refreshStatus(g) + _ = gui.closeConfirmationPrompt(gui.g) + _ = gui.refreshCommits(gui.g) + _ = gui.refreshStatus(gui.g) } }() return nil } +func (gui *Gui) pushFiles(g *gocui.Gui, v *gocui.View) error { + // if we have pullables we'll ask if the user wants to force push + _, pullables := gui.GitCommand.UpstreamDifferenceCount() + if pullables == "?" || pullables == "0" { + return gui.pushWithForceFlag(v, false) + } + err := gui.createConfirmationPanel(g, nil, gui.Tr.SLocalize("ForcePush"), gui.Tr.SLocalize("ForcePushPrompt"), func(g *gocui.Gui, v *gocui.View) error { + return gui.pushWithForceFlag(v, true) + }, nil) + return err +} + func (gui *Gui) handleSwitchToMerge(g *gocui.Gui, v *gocui.View) error { mergeView, err := g.View("main") if err != nil { diff --git a/pkg/gui/gui.go b/pkg/gui/gui.go index 1e7b6156b..66777b3a6 100644 --- a/pkg/gui/gui.go +++ b/pkg/gui/gui.go @@ -141,14 +141,15 @@ func max(a, b int) int { func (gui *Gui) layout(g *gocui.Gui) error { g.Highlight = true width, height := g.Size() + version := gui.Config.GetVersion() leftSideWidth := width / 3 statusFilesBoundary := 2 filesBranchesBoundary := 2 * height / 5 // height - 20 commitsBranchesBoundary := 3 * height / 5 // height - 10 commitsStashBoundary := height - 5 // height - 5 + optionsVersionBoundary := width - max(len(version), 1) minimumHeight := 16 minimumWidth := 10 - version := gui.Config.GetVersion() panelSpacing := 1 if OverlappingEdges { @@ -227,7 +228,7 @@ func (gui *Gui) layout(g *gocui.Gui) error { v.FgColor = gocui.ColorWhite } - if v, err := g.SetView("options", -1, optionsTop, width-len(version)-2, optionsTop+2, 0); err != nil { + if v, err := g.SetView("options", -1, optionsTop, optionsVersionBoundary-1, optionsTop+2, 0); err != nil { if err != gocui.ErrUnknownView { return err } @@ -249,8 +250,7 @@ func (gui *Gui) layout(g *gocui.Gui) error { commitMessageView.Editable = true } } - - if v, err := g.SetView("version", width-len(version)-1, optionsTop, width, optionsTop+2, 0); err != nil { + if v, err := g.SetView("version", optionsVersionBoundary-1, optionsTop, width, optionsTop+2, 0); err != nil { if err != gocui.ErrUnknownView { return err } diff --git a/pkg/i18n/english.go b/pkg/i18n/english.go index bebe9b282..c0384136b 100644 --- a/pkg/i18n/english.go +++ b/pkg/i18n/english.go @@ -300,6 +300,12 @@ func addEnglish(i18nObject *i18n.Bundle) error { }, &i18n.Message{ ID: "EditConfig", Other: "edit config file", + }, &i18n.Message{ + ID: "ForcePush", + Other: "Force push", + }, &i18n.Message{ + ID: "ForcePushPrompt", + Other: "Your branch has diverged from the remote branch. Press 'esc' to cancel, or 'enter' to force push.", }, ) } diff --git a/pkg/i18n/i18n.go b/pkg/i18n/i18n.go index f2bd2839e..e209d55c5 100644 --- a/pkg/i18n/i18n.go +++ b/pkg/i18n/i18n.go @@ -23,7 +23,10 @@ func NewLocalizer(log *logrus.Logger) (*Localizer, error) { // detect the user's language userLang, err := jibber_jabber.DetectLanguage() if err != nil { - return nil, err + if err.Error() != "Could not detect Language" { + return nil, err + } + userLang = "C" } log.Info("language: " + userLang) 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{} |