From c52a4910bf281f5e7851db455adf8939412308c1 Mon Sep 17 00:00:00 2001 From: w0rp Date: Sat, 12 Aug 2017 14:27:47 +0100 Subject: #653 - Update the loclist binary search to work with buffer numbers, to filter out items for other buffers --- autoload/ale/balloon.vim | 2 +- autoload/ale/cursor.vim | 5 +-- autoload/ale/util.vim | 53 ++++++++++++++++++++----------- test/test_balloon_messages.vader | 3 ++ test/test_loclist_binary_search.vader | 59 ++++++++++++++++++++++++----------- 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) -- cgit v1.2.3