Reverse match()

matchr.vim

" File:		matchr.vim
" Created:	2020 Jul 30
" Last Change:	2020 Aug 02
" Version:	0.3
" Author:	Andy Wokula <[email protected]>
" License:	Vim License, see :h license

" NvMatchReverse({str}, {pat})
"
"   like match({str}, {pat}), but return the position of the right-most
"   match.
"
"   Uses exponential search to make this suitable for large strings.  Once
"   the interval becomes small enough (s:MATCHLIMIT or less), the search is
"   turned into
"	match(StringPart, '^.*\zs\%('. {pat}. '\)')
"   like how one would do it normally.
"
"   Look-behind patterns should work: as long as there is no match, the
"   interval is increased to the left.
"
"   Works best when the match is near the end of the string.
"

" Dev Notes:
" - starting with a small interval, the interval size is exponentially
"   increased by powers of two, until something interesting is inside the
"   interval; then a binary search is applied to find the exact position

" History:
" 2020 Aug 02	s:BinSearch(), avoid recursion
" 2020 Jul 31
" + once a matching interval is known, switch to binary search (with
"   `endoff' steps from large to small)!
" + if the interval (with a known match) lstart..rstart is small enough (eg
"   less than 1000) switch to '^.*\zs{pat}' matching, starting at {lstart}.
"   Maybe then start with a higher endoff

let s:MATCHLIMIT = 256	" longer intervals are split
let s:MATCHLEN = 50	" longer matches are maybe not found!

func! NvMatchReverse(str, pat) "{{{
    let strend = strlen(a:str)
    let endoff = s:MATCHLIMIT
    if strend < endoff
	return match(a:str, '^.*\zs\%('. a:pat. '\)')
    endif
    let pos = match(a:str, a:pat, strend - endoff)
    if pos >= 0
	return s:BinSearch(a:str, a:pat, strend - endoff, strend)
    endif
    while strend >= endoff * 2
	let endoff = endoff * 2
	let pos = match(a:str, a:pat, strend - endoff)
	if pos >= 0
	    return s:BinSearch(a:str, a:pat, strend - endoff, strend - endoff/2)
	endif
    endwhile
    if strend > endoff
	let pos = match(a:str, a:pat, 0)
	if pos >= 0
	    return s:BinSearch(a:str, a:pat, 0, strend - endoff)
	endif
    endif
    return -1
endfunc "}}}

" a match starts somewhere between {lstart} and {rstart} (exclusive)
func! s:BinSearch(str, pat, lstart, rstart) "{{{
    let lstart = a:lstart
    let rstart = a:rstart
    while rstart - lstart > s:MATCHLIMIT
	let mid = lstart + (rstart - lstart) / 2
	let pos = match(a:str, a:pat, mid)
	if pos >= 0
	    let lstart = mid
	else
	    let rstart = mid
	endif
    endwhile
    return lstart + match(strpart(a:str, lstart, rstart - lstart + s:MATCHLEN), '^.*\zs\%('. a:pat. '\)')
endfunc "}}}