Problem with adist function in text comparison

Question

I have a problem with adist function. Basically I am using the example of the RDocumentation.

attr(adist(c("kitten", "sitting"), counts = TRUE), "trafos") here

However, when I am trying to run added one more word

attr(adist(c("kitten", "sitting", "hi"), counts = TRUE), "trafos") 

I am taking these results:

     [,1]      [,2]      [,3]     
[1,] "MMMMMM"  "SMMMSMI" "SMDDDDI"

[2,] "SMMMSMD" "MMMMMMM" "SDDDMDD"

[3,] "SMIIIID" "SIIIMII" "MMI" 

In the third column, third row, I am taking MMI, but I can not understand why as it is the same word "hi". So it has to be MM. (match, match and no insertion)

Reference: https://www.rdocumentation.org/packages/utils/versions/3.6.0/topics/adist

I am using another example:

test <- c('x','hi', 'y','x')

attr(adist(test, y=NULL , counts = TRUE), "trafos")

I am taking these results. But at least the diagonal needs to be M as is the same word.

     [,1] [,2] [,3] [,4]
[1,] "M"  "SI" "SI" "MI"

[2,] "SD" "MM" "SD" "SD"

[3,] "SD" "SI" "MI" "SI"

[4,] "MI" "SI" "SI" "MI"

I can not understand what it is going wrong.

Answer 1

As others have already pointed out it looks like a bug. Using the source from https://cran.r-project.org/src/base/R-3/R-3.5.3.tar.gz and looking at lines 429-432 in file src/main/agrep.c, there is code that is reversing a buffer:

/* Now reverse the transcript. */
for(k = 0, l = --m; l >= nz; k++, l--)
  buf[k] = buf[l];
buf[++k] = '\0';

Walking through what happens in gdb:

$ R -d gdb
GNU gdb (Debian 7.12-6) 7.12.0.20161007-git
...
(gdb) b agrep.c:430
Breakpoint 1 at 0x7222e: file agrep.c, line 430.
(gdb) r
Starting program: /usr/local/lib64/R/bin/exec/R
...
R version 3.5.3 (2019-03-11) -- "Great Truth"
...

Then executing the following R code:

> attr(adist(c("kitten", "sitting", "hi"), counts = TRUE), "trafos")

Breakpoint 1, adist_full (x=0x555557995a48, y=0x555557995a48, costs=0x5555561567a8, opt_counts=TRUE) at agrep.c:430
430                                 for(k = 0, l = --m; l >= nz; k++, l--)

Continue 8 at the break to reach the last diagonal entry:

(gdb) c 8
Will ignore next 7 crossings of breakpoint 1.  Continuing.

Breakpoint 1, adist_full (x=0x555557995a48, y=0x555557995a48, costs=0x5555561567a8, opt_counts=TRUE) at agrep.c:430
430                                 for(k = 0, l = --m; l >= nz; k++, l--)

Examine the buffer before reversal:

(gdb) x/6c buf
0x5555566a8da0: 83 'S'  73 'I'  73 'I'  73 'I'  77 'M'  77 'M'

Stepping through the code shows that buf[0] and buf[1] are copied from the end of the buffer:

(gdb) n
431                                     buf[k] = buf[l];
(gdb) n
430                                 for(k = 0, l = --m; l >= nz; k++, l--)
(gdb) p k
$1 = 0
(gdb) n
431                                     buf[k] = buf[l];
(gdb) n
430                                 for(k = 0, l = --m; l >= nz; k++, l--)
(gdb) p k
$2 = 1

Exiting the loop k=2:

(gdb) n
432                                 buf[++k] = '\0';
(gdb) p k
$3 = 2

And ++k is 3:

(gdb) n
433                                 COUNTS(i, j, 0) = nins;
(gdb) p k
$4 = 3

Examining the reversed buffer shows that buf[2] was not set to NUL:

(gdb) x/6c buf
0x5555566a8da0: 77 'M'  77 'M'  73 'I'  0 '\000'        77 'M'  77 'M'

This results in:

     [,1]      [,2]      [,3]
[1,] "MMMMMM"  "SMMMSMI" "SMDDDDI"
[2,] "SMMMSMD" "MMMMMMM" "SDDDMDD"
[3,] "SMIIIID" "SIIIMII" "MMI"

Replacing buf[++k] = '\0' with buf[k] = '\0' appears to put the NUL in the correct location:

> attr(adist(c("kitten", "sitting", "hi"), counts = TRUE), "trafos")

Breakpoint 1, adist_full (x=0x555557995cb8, y=0x555557995cb8, costs=0x5555561567a8, opt_counts=TRUE) at agrep.c:430
430                                 for(k = 0, l = --m; l >= nz; k++, l--)
(gdb) c 8
Will ignore next 7 crossings of breakpoint 1.  Continuing.

Breakpoint 1, adist_full (x=0x555557995cb8, y=0x555557995cb8, costs=0x5555561567a8, opt_counts=TRUE) at agrep.c:430
430                                 for(k = 0, l = --m; l >= nz; k++, l--)
(gdb) x/6c buf
0x5555566a8da0: 83 'S'  73 'I'  73 'I'  73 'I'  77 'M'  77 'M'
(gdb) n
431                                     buf[k] = buf[l];
(gdb) n
430                                 for(k = 0, l = --m; l >= nz; k++, l--)
(gdb) p k
$1 = 0
(gdb) n
431                                     buf[k] = buf[l];
(gdb) n
430                                 for(k = 0, l = --m; l >= nz; k++, l--)
(gdb) p k
$2 = 1
(gdb) n
432                                 buf[k] = '\0';
(gdb) p k
$3 = 2
(gdb) n
433                                 COUNTS(i, j, 0) = nins;
(gdb) p k
$4 = 2
(gdb) x/6c buf
0x5555566a8da0: 77 'M'  77 'M'  0 '\000'        73 'I'  77 'M'  77 'M'

Resulting in the expected output:

     [,1]      [,2]      [,3]     
[1,] "MMMMMM"  "SMMMSMI" "SMDDDD" 
[2,] "SMMMSMD" "MMMMMMM" "SDDDMDD"
[3,] "SMIIII"  "SIIIMII" "MM" 

After the fix your second example results in:

> test <- c('x','hi', 'y','x')
> attr(adist(test, y=NULL , counts = TRUE), "trafos")
     [,1] [,2] [,3] [,4]
[1,] "M"  "SI" "S"  "M"
[2,] "SD" "MM" "SD" "SD"
[3,] "S"  "SI" "M"  "S"
[4,] "M"  "SI" "S"  "M"

The result appears to be consistent with the other attributes for ins, sub and del.

> adist(c('x', 'hi', 'y', 'x'), counts=TRUE)
     [,1] [,2] [,3] [,4]
[1,]    0    2    1    0
[2,]    2    0    2    2
[3,]    1    2    0    1
[4,]    0    2    1    0
attr(,"counts")
, , ins

     [,1] [,2] [,3] [,4]
[1,]    0    1    0    0
[2,]    0    0    0    0
[3,]    0    1    0    0
[4,]    0    1    0    0

, , del

     [,1] [,2] [,3] [,4]
[1,]    0    0    0    0
[2,]    1    0    1    1
[3,]    0    0    0    0
[4,]    0    0    0    0

, , sub

     [,1] [,2] [,3] [,4]
[1,]    0    1    1    0
[2,]    1    0    1    1
[3,]    1    1    0    1
[4,]    0    1    1    0

attr(,"trafos")
     [,1] [,2] [,3] [,4]
[1,] "M"  "SI" "S"  "M"
[2,] "SD" "MM" "SD" "SD"
[3,] "S"  "SI" "M"  "S"
[4,] "M"  "SI" "S"  "M"