#653 - Update the loclist binary search to work with buffer numbers, to filter out items for other buffers

5 files changed, 82 insertions, 40 deletions

diff --git a/autoload/ale/balloon.vim b/autoload/ale/balloon.vim
index 3d179a0d..41fa95fa 100644
--- a/autoload/ale/balloon.vim
+++ b/autoload/ale/balloon.vim
@@ -3,7 +3,7 @@
 
 function! ale#balloon#MessageForPos(bufnr, lnum, col) abort
     let l:loclist = get(g:ale_buffer_info, a:bufnr, {'loclist': []}).loclist
-    let l:index = ale#util#BinarySearch(l:loclist, a:lnum, a:col)
+    let l:index = ale#util#BinarySearch(l:loclist, a:bufnr, a:lnum, a:col)
 
     return l:index >= 0 ? l:loclist[l:index].text : ''
 endfunction
diff --git a/autoload/ale/cursor.vim b/autoload/ale/cursor.vim
index 72351c5f..340432f7 100644
--- a/autoload/ale/cursor.vim
+++ b/autoload/ale/cursor.vim
@@ -62,10 +62,11 @@ function! ale#cursor#TruncatedEcho(message) abort
 endfunction
 
 function! s:FindItemAtCursor() abort
-    let l:info = get(g:ale_buffer_info, bufnr(''), {})
+    let l:buf = bufnr('')
+    let l:info = get(g:ale_buffer_info, l:buf, {})
     let l:loclist = get(l:info, 'loclist', [])
     let l:pos = getcurpos()
-    let l:index = ale#util#BinarySearch(l:loclist, l:pos[1], l:pos[2])
+    let l:index = ale#util#BinarySearch(l:loclist, l:buf, l:pos[1], l:pos[2])
     let l:loc = l:index >= 0 ? l:loclist[l:index] : {}
 
     return [l:info, l:loc]
diff --git a/autoload/ale/util.vim b/autoload/ale/util.vim
index adfcd476..98fe53e8 100644
--- a/autoload/ale/util.vim
+++ b/autoload/ale/util.vim
@@ -41,37 +41,52 @@ function! ale#util#LocItemCompare(left, right) abort
     return 0
 endfunction
 
-" This function will perform a binary search to find a message from the
-" loclist to echo when the cursor moves.
-function! ale#util#BinarySearch(loclist, line, column) abort
+" This function will perform a binary search and a small sequential search
+" on the list to find the last problem in the buffer and line which is
+" on or before the column. The index of the problem will be returned.
+"
+" -1 will be returned if nothing can be found.
+function! ale#util#BinarySearch(loclist, buffer, line, column) abort
     let l:min = 0
     let l:max = len(a:loclist) - 1
-    let l:last_column_match = -1
 
     while 1
         if l:max < l:min
-            return l:last_column_match
+            return -1
         endif
 
         let l:mid = (l:min + l:max) / 2
-        let l:obj = a:loclist[l:mid]
+        let l:item = a:loclist[l:mid]
 
-        " Binary search to get on the same line
-        if a:loclist[l:mid]['lnum'] < a:line
+        " Binary search for equal buffers, equal lines, then near columns.
+        if l:item.bufnr < a:buffer
+            let l:min = l:mid + 1
+        elseif l:item.bufnr > a:buffer
+            let l:max = l:mid - 1
+        elseif l:item.lnum < a:line
             let l:min = l:mid + 1
-        elseif a:loclist[l:mid]['lnum'] > a:line
+        elseif l:item.lnum > a:line
             let l:max = l:mid - 1
         else
-            let l:last_column_match = l:mid
-
-            " Binary search to get the same column, or near it
-            if a:loclist[l:mid]['col'] < a:column
-                let l:min = l:mid + 1
-            elseif a:loclist[l:mid]['col'] > a:column
-                let l:max = l:mid - 1
-            else
-                return l:mid
-            endif
+            " This part is a small sequential search.
+            let l:index = l:mid
+
+            " Search backwards to find the first problem on the line.
+            while l:index > 0
+            \&& a:loclist[l:index - 1].bufnr == a:buffer
+            \&& a:loclist[l:index - 1].lnum == a:line
+                let l:index -= 1
+            endwhile
+
+            " Find the last problem on or before this column.
+            while l:index < l:max
+            \&& a:loclist[l:index + 1].bufnr == a:buffer
+            \&& a:loclist[l:index + 1].lnum == a:line
+            \&& a:loclist[l:index + 1].col <= a:column
+                let l:index += 1
+            endwhile
+
+            return l:index
         endif
     endwhile
 endfunction
diff --git a/test/test_balloon_messages.vader b/test/test_balloon_messages.vader
index 50dc6af4..ec09fe29 100644
--- a/test/test_balloon_messages.vader
+++ b/test/test_balloon_messages.vader
@@ -3,16 +3,19 @@ Before:
 
   let g:ale_buffer_info[347] = {'loclist': [
   \ {
+  \   'bufnr': 347,
   \   'lnum': 1,
   \   'col': 10,
   \   'text': 'Missing semicolon. (semi)',
   \ },
   \ {
+  \   'bufnr': 347,
   \   'lnum': 2,
   \   'col': 10,
   \   'text': 'Infix operators must be spaced. (space-infix-ops)'
   \ },
   \ {
+  \   'bufnr': 347,
   \   'lnum': 2,
   \   'col': 15,
   \   'text': 'Missing radix parameter (radix)'
diff --git a/test/test_loclist_binary_search.vader b/test/test_loclist_binary_search.vader
index e0b2c651..5558191c 100644
--- a/test/test_loclist_binary_search.vader
+++ b/test/test_loclist_binary_search.vader
@@ -1,26 +1,49 @@
 Before:
   let g:loclist = [
-  \ {'lnum': 2, 'col': 10},
-  \ {'lnum': 3, 'col': 2},
-  \ {'lnum': 3, 'col': 10},
-  \ {'lnum': 3, 'col': 12},
-  \ {'lnum': 3, 'col': 25},
-  \ {'lnum': 5, 'col': 4},
-  \ {'lnum': 5, 'col': 5},
+  \ {'bufnr': 1, 'lnum': 2, 'col': 10},
+  \ {'bufnr': 1, 'lnum': 3, 'col': 2},
+  \ {'bufnr': 1, 'lnum': 3, 'col': 10},
+  \ {'bufnr': 1, 'lnum': 3, 'col': 12},
+  \ {'bufnr': 1, 'lnum': 3, 'col': 25},
+  \ {'bufnr': 1, 'lnum': 5, 'col': 4},
+  \ {'bufnr': 1, 'lnum': 5, 'col': 5},
+  \ {'bufnr': 1, 'lnum': 9, 'col': 5},
+  \ {'bufnr': 1, 'lnum': 10, 'col': 1},
+  \ {'bufnr': 2, 'lnum': 7, 'col': 10},
+  \ {'bufnr': 2, 'lnum': 9, 'col': 2},
+  \ {'bufnr': 2, 'lnum': 10, 'col': 2},
+  \ {'bufnr': 2, 'lnum': 11, 'col': 2},
   \]
 
-Execute (Exact column matches should be correct):
-   AssertEqual 1, ale#util#BinarySearch(g:loclist, 3, 2)
+After:
+  unlet g:loclist
 
-Execute (Off lines, there should be no match):
-   AssertEqual -1, ale#util#BinarySearch(g:loclist, 4, 2)
+Execute(Exact column matches should be correct):
+  AssertEqual 1, ale#util#BinarySearch(g:loclist, 1, 3, 2)
 
-Execute (Near column matches should be taken):
-   AssertEqual 2, ale#util#BinarySearch(g:loclist, 3, 11)
-   AssertEqual 4, ale#util#BinarySearch(g:loclist, 3, 13)
+Execute(Off lines, there should be no match):
+  AssertEqual -1, ale#util#BinarySearch(g:loclist, 1, 4, 2)
 
-Execute (Columns before should be taken when the cursor is far ahead):
-   AssertEqual 4, ale#util#BinarySearch(g:loclist, 3, 300)
+Execute(Near column matches should be taken):
+  AssertEqual 2, ale#util#BinarySearch(g:loclist, 1, 3, 11)
+  AssertEqual 3, ale#util#BinarySearch(g:loclist, 1, 3, 13)
 
-After:
-  unlet g:loclist
+Execute(Columns before should be taken when the cursor is far ahead):
+  AssertEqual 4, ale#util#BinarySearch(g:loclist, 1, 3, 300)
+
+Execute(The only problems on lines in later columns should be matched):
+  AssertEqual 7, ale#util#BinarySearch(g:loclist, 1, 9, 1)
+
+Execute(The only problems on lines in earlier columns should be matched):
+  AssertEqual 8, ale#util#BinarySearch(g:loclist, 1, 10, 30)
+
+Execute(Lines for other buffers should not be matched):
+  AssertEqual -1, ale#util#BinarySearch(g:loclist, 1, 7, 10)
+
+Execute(Searches for buffers later in the list should work):
+  AssertEqual 10, ale#util#BinarySearch(g:loclist, 2, 9, 10)
+
+Execute(Searches should work with just one item):
+  let g:loclist = [{'bufnr': 1, 'lnum': 3, 'col': 10}]
+
+  AssertEqual 0, ale#util#BinarySearch(g:loclist, 1, 3, 2)