valgrind errors

[RobinHankin]

automated error message from Brian Ripley:

==1887801== Memcheck, a memory error detector
==1887801== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==1887801== Using Valgrind-3.16.1 and LibVEX; rerun with -h for copyright info
==1887801== Command: /data/blackswan/ripley/R/R-devel-vg/bin/exec/R -f testthat.R --restore --save --no-readline --vanilla
==1887801== 

R Under development (unstable) (2021-02-10 r79983) -- "Unsuffered Consequences"
Copyright (C) 2021 The R Foundation for Statistical Computing
Platform: x86_64-pc-linux-gnu (64-bit)

R is free software and comes with ABSOLUTELY NO WARRANTY.
You are welcome to redistribute it under certain conditions.
Type 'license()' or 'licence()' for distribution details.

R is a collaborative project with many contributors.
Type 'contributors()' for more information and
'citation()' on how to cite R or R packages in publications.

Type 'demo()' for some demos, 'help()' for on-line help, or
'help.start()' for an HTML browser interface to help.
Type 'q()' to quit R.

> library("testthat")
> test_check("partitions")
Loading required package: partitions
==1887801== Invalid read of size 4
==1887801==    at 0x1A78A617: E_num(Rcpp::Vector<14, Rcpp::PreserveStorage>&) (/tmp/RtmpfL63wv/R.INSTALL4bda76cebf71/eddington/src/eddington.cpp:56)
==1887801==    by 0x1A786A35: _eddington_E_num_try(SEXPREC*) (/tmp/RtmpfL63wv/R.INSTALL4bda76cebf71/eddington/src/RcppExports.cpp:17)
==1887801==    by 0x1A786C35: _eddington_E_num (/tmp/RtmpfL63wv/R.INSTALL4bda76cebf71/eddington/src/RcppExports.cpp:25)
==1887801==    by 0x49D1AF: R_doDotCall (svn/R-devel/src/main/dotcode.c:598)
==1887801==    by 0x49D663: do_dotcall (svn/R-devel/src/main/dotcode.c:1281)
==1887801==    by 0x4D3566: bcEval (svn/R-devel/src/main/eval.c:7115)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801==    by 0x4F1A8D: R_execClosure (svn/R-devel/src/main/eval.c:1897)
==1887801==    by 0x4F2783: Rf_applyClosure (svn/R-devel/src/main/eval.c:1823)
==1887801==    by 0x4F478F: R_forceAndCall (svn/R-devel/src/main/eval.c:1964)
==1887801==    by 0x4F4AE1: do_forceAndCall (svn/R-devel/src/main/eval.c:1986)
==1887801==    by 0x4D336F: bcEval (svn/R-devel/src/main/eval.c:7135)
==1887801==  Address 0x13ae7200 is 6,800 bytes inside a block of size 7,960 alloc'd
==1887801==    at 0x483A809: malloc (/builddir/build/BUILD/valgrind-3.16.1/coregrind/m_replacemalloc/vg_replace_malloc.c:307)
==1887801==    by 0x52BA30: GetNewPage (svn/R-devel/src/main/memory.c:946)
==1887801==    by 0x52D6CB: Rf_allocVector3 (svn/R-devel/src/main/memory.c:2784)
==1887801==    by 0x44723D: Rf_allocVector (svn/R-devel/src/include/Rinlinedfuns.h:595)
==1887801==    by 0x44723D: getAttrib0 (svn/R-devel/src/main/attrib.c:124)
==1887801==    by 0x5AA382: do_subset_dflt (svn/R-devel/src/main/subset.c:812)
==1887801==    by 0x4CB1AE: VECSUBSET_PTR (svn/R-devel/src/main/eval.c:5649)
==1887801==    by 0x4DAB20: bcEval (svn/R-devel/src/main/eval.c:7340)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801==    by 0x4F09AF: forcePromise (svn/R-devel/src/main/eval.c:555)
==1887801==    by 0x4F0537: Rf_eval (svn/R-devel/src/main/eval.c:763)
==1887801==    by 0x5334A6: do_usemethod (svn/R-devel/src/main/objects.c:563)
==1887801==    by 0x4D336F: bcEval (svn/R-devel/src/main/eval.c:7135)
==1887801== 
==1887801== Invalid read of size 4
==1887801==    at 0x16F7DFB5: durfee_vector (packages/tests-vg/partitions/src/partitions.c:311)
==1887801==    by 0x16F7E003: c_durfee (packages/tests-vg/partitions/src/partitions.c:320)
==1887801==    by 0x49F495: do_dotCode (svn/R-devel/src/main/dotcode.c:1811)
==1887801==    by 0x4D3566: bcEval (svn/R-devel/src/main/eval.c:7115)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801==    by 0x4F1A8D: R_execClosure (svn/R-devel/src/main/eval.c:1897)
==1887801==    by 0x4F2783: Rf_applyClosure (svn/R-devel/src/main/eval.c:1823)
==1887801==    by 0x4F0243: Rf_eval (svn/R-devel/src/main/eval.c:850)
==1887801==    by 0x49B68F: do_External (svn/R-devel/src/main/dotcode.c:573)
==1887801==    by 0x4D3566: bcEval (svn/R-devel/src/main/eval.c:7115)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801==    by 0x4F1A8D: R_execClosure (svn/R-devel/src/main/eval.c:1897)
==1887801==  Address 0x15055b5c is 4,236 bytes inside a block of size 7,960 alloc'd
==1887801==    at 0x483A809: malloc (/builddir/build/BUILD/valgrind-3.16.1/coregrind/m_replacemalloc/vg_replace_malloc.c:307)
==1887801==    by 0x52BA30: GetNewPage (svn/R-devel/src/main/memory.c:946)
==1887801==    by 0x52D6CB: Rf_allocVector3 (svn/R-devel/src/main/memory.c:2784)
==1887801==    by 0x5A8E90: Rf_allocVector (svn/R-devel/src/include/Rinlinedfuns.h:595)
==1887801==    by 0x5A8E90: MatrixSubset (svn/R-devel/src/main/subset.c:290)
==1887801==    by 0x5AA845: do_subset_dflt (svn/R-devel/src/main/subset.c:856)
==1887801==    by 0x5AC4C2: do_subset (svn/R-devel/src/main/subset.c:662)
==1887801==    by 0x4F04C4: Rf_eval (svn/R-devel/src/main/eval.c:802)
==1887801==    by 0x4F43F0: Rf_evalList (svn/R-devel/src/main/eval.c:3067)
==1887801==    by 0x4F490D: R_forceAndCall (svn/R-devel/src/main/eval.c:1932)
==1887801==    by 0x4F4AE1: do_forceAndCall (svn/R-devel/src/main/eval.c:1986)
==1887801==    by 0x4D336F: bcEval (svn/R-devel/src/main/eval.c:7135)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801== 
==1887801== Invalid read of size 4
==1887801==    at 0x16F7DFB7: durfee_vector (packages/tests-vg/partitions/src/partitions.c:311)
==1887801==    by 0x16F7E003: c_durfee (packages/tests-vg/partitions/src/partitions.c:320)
==1887801==    by 0x49F495: do_dotCode (svn/R-devel/src/main/dotcode.c:1811)
==1887801==    by 0x4D3566: bcEval (svn/R-devel/src/main/eval.c:7115)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801==    by 0x4F1A8D: R_execClosure (svn/R-devel/src/main/eval.c:1897)
==1887801==    by 0x4F2783: Rf_applyClosure (svn/R-devel/src/main/eval.c:1823)
==1887801==    by 0x4F0243: Rf_eval (svn/R-devel/src/main/eval.c:850)
==1887801==    by 0x49B68F: do_External (svn/R-devel/src/main/dotcode.c:573)
==1887801==    by 0x4D3566: bcEval (svn/R-devel/src/main/eval.c:7115)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801==    by 0x4F1A8D: R_execClosure (svn/R-devel/src/main/eval.c:1897)
==1887801==  Address 0x15055b5c is 4,236 bytes inside a block of size 7,960 alloc'd
==1887801==    at 0x483A809: malloc (/builddir/build/BUILD/valgrind-3.16.1/coregrind/m_replacemalloc/vg_replace_malloc.c:307)
==1887801==    by 0x52BA30: GetNewPage (svn/R-devel/src/main/memory.c:946)
==1887801==    by 0x52D6CB: Rf_allocVector3 (svn/R-devel/src/main/memory.c:2784)
==1887801==    by 0x5A8E90: Rf_allocVector (svn/R-devel/src/include/Rinlinedfuns.h:595)
==1887801==    by 0x5A8E90: MatrixSubset (svn/R-devel/src/main/subset.c:290)
==1887801==    by 0x5AA845: do_subset_dflt (svn/R-devel/src/main/subset.c:856)
==1887801==    by 0x5AC4C2: do_subset (svn/R-devel/src/main/subset.c:662)
==1887801==    by 0x4F04C4: Rf_eval (svn/R-devel/src/main/eval.c:802)
==1887801==    by 0x4F43F0: Rf_evalList (svn/R-devel/src/main/eval.c:3067)
==1887801==    by 0x4F490D: R_forceAndCall (svn/R-devel/src/main/eval.c:1932)
==1887801==    by 0x4F4AE1: do_forceAndCall (svn/R-devel/src/main/eval.c:1986)
==1887801==    by 0x4D336F: bcEval (svn/R-devel/src/main/eval.c:7135)
==1887801==    by 0x4F0077: Rf_eval (svn/R-devel/src/main/eval.c:727)
==1887801== 
[ FAIL 0 | WARN 0 | SKIP 0 | PASS 49 ]
> 
> proc.time()
   user  system elapsed 
 64.840   0.382  64.249 
==1887801== 
==1887801== HEAP SUMMARY:
==1887801==     in use at exit: 98,653,726 bytes in 19,595 blocks
==1887801==   total heap usage: 98,244 allocs, 78,649 frees, 204,739,640 bytes allocated
==1887801== 
==1887801== LEAK SUMMARY:
==1887801==    definitely lost: 0 bytes in 0 blocks
==1887801==    indirectly lost: 0 bytes in 0 blocks
==1887801==      possibly lost: 0 bytes in 0 blocks
==1887801==    still reachable: 98,653,726 bytes in 19,595 blocks
==1887801==         suppressed: 0 bytes in 0 blocks
==1887801== Reachable blocks (those to which a pointer was found) are not shown.
==1887801== To see them, rerun with: --leak-check=full --show-leak-kinds=all
==1887801== 
==1887801== For lists of detected and suppressed errors, rerun with: -s
==1887801== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)

[RobinHankin]

not 100% sure I am reading the valgrind output correctly but it seems that there are two distinct errors: one from eddington and one from the partitions package. The line in question is:

      for(i=0 ; x[i] > i && i < nrow; i++)

and I think what is happening is that the second argument x[]>i && i<nrow is buggy. If i==nrow-1 and x[i]>i then i will be incremented. Then control will execute x[]>i && i<nrow (but with i==nrow). So it will try to read x[i] which is x[nrow] which is out of bounds. We can correct this by swapping the order of the tests so it reads

      for(i=0 ; i<nrow && x[i]>i ; i++)

I spoke with Steffan Hooper about it and he suggests rewriting to use a while() loop instead.

[RobinHankin]

The while() code would be

int durfee_vector(const int *x, const int nrow)
{
      int i=0;
      while(i<nrow){
    if(x[i] <= i){break;}
    i++;
      }
      return i;
}