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
(alo, ahi, blo, bhi int)
| 222 | // |
| 223 | // If no blocks match, return (alo, blo, 0). |
| 224 | func (m *SequenceMatcher) findLongestMatch(alo, ahi, blo, bhi int) Match { |
| 225 | // CAUTION: stripping common prefix or suffix would be incorrect. |
| 226 | // E.g., |
| 227 | // ab |
| 228 | // acab |
| 229 | // Longest matching block is "ab", but if common prefix is |
| 230 | // stripped, it's "a" (tied with "b"). UNIX(tm) diff does so |
| 231 | // strip, so ends up claiming that ab is changed to acab by |
| 232 | // inserting "ca" in the middle. That's minimal but unintuitive: |
| 233 | // "it's obvious" that someone inserted "ac" at the front. |
| 234 | // Windiff ends up at the same place as diff, but by pairing up |
| 235 | // the unique 'b's and then matching the first two 'a's. |
| 236 | besti, bestj, bestsize := alo, blo, 0 |
| 237 | |
| 238 | // find longest junk-free match |
| 239 | // during an iteration of the loop, j2len[j] = length of longest |
| 240 | // junk-free match ending with a[i-1] and b[j] |
| 241 | j2len := map[int]int{} |
| 242 | for i := alo; i != ahi; i++ { |
| 243 | // look at all instances of a[i] in b; note that because |
| 244 | // b2j has no junk keys, the loop is skipped if a[i] is junk |
| 245 | newj2len := map[int]int{} |
| 246 | for _, j := range m.b2j[m.a[i]] { |
| 247 | // a[i] matches b[j] |
| 248 | if j < blo { |
| 249 | continue |
| 250 | } |
| 251 | if j >= bhi { |
| 252 | break |
| 253 | } |
| 254 | k := j2len[j-1] + 1 |
| 255 | newj2len[j] = k |
| 256 | if k > bestsize { |
| 257 | besti, bestj, bestsize = i-k+1, j-k+1, k |
| 258 | } |
| 259 | } |
| 260 | j2len = newj2len |
| 261 | } |
| 262 | |
| 263 | // Extend the best by non-junk elements on each end. In particular, |
| 264 | // "popular" non-junk elements aren't in b2j, which greatly speeds |
| 265 | // the inner loop above, but also means "the best" match so far |
| 266 | // doesn't contain any junk *or* popular non-junk elements. |
| 267 | for besti > alo && bestj > blo && !m.isBJunk(m.b[bestj-1]) && |
| 268 | m.a[besti-1] == m.b[bestj-1] { |
| 269 | besti, bestj, bestsize = besti-1, bestj-1, bestsize+1 |
| 270 | } |
| 271 | for besti+bestsize < ahi && bestj+bestsize < bhi && |
| 272 | !m.isBJunk(m.b[bestj+bestsize]) && |
| 273 | m.a[besti+bestsize] == m.b[bestj+bestsize] { |
| 274 | bestsize += 1 |
| 275 | } |
| 276 | |
| 277 | // Now that we have a wholly interesting match (albeit possibly |
| 278 | // empty!), we may as well suck up the matching junk on each |
| 279 | // side of it too. Can't think of a good reason not to, and it |
| 280 | // saves post-processing the (possibly considerable) expense of |
| 281 | // figuring out what to do with it. In the case of an empty |
no test coverage detected