SQLite: Check-in [fab2c2b0]

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview

Comment:	Improve the performance of the built-in REPLACE() function in cases where it does many substitutions that make the string larger. OSSFuzz is reporting intermittant timeouts when running a test where it does a REPLACE() on a 930KB random blob. Perhaps this enhancement will fix that.
Downloads:	Tarball \| ZIP archive \| SQL archive
Timelines:	family \| ancestors \| descendants \| both \| trunk
Files:	files \| file ages \| folders
SHA3-256:	fab2c2b07b5d3cd851db3e6f5c8a44155e32b0df22905ea33412b153b825a928
User & Date:	drh 2018-02-09 23:25:14

Context

2018-02-10
02:31		Fix misplaced testcase() macros from the previous check-in. check-in: 3aed949a user: drh tags: trunk
2018-02-09
23:25		Improve the performance of the built-in REPLACE() function in cases where it does many substitutions that make the string larger. OSSFuzz is reporting intermittant timeouts when running a test where it does a REPLACE() on a 930KB random blob. Perhaps this enhancement will fix that. check-in: fab2c2b0 user: drh tags: trunk
20:49		Add the zorder.c extension implementing zorder() and unzorder() SQL functions. check-in: a57a77dc user: drh tags: trunk

Changes

Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/func.c.

  unsigned char *zOut;              /* The output */
  int nStr;                /* Size of zStr */
  int nPattern;            /* Size of zPattern */
  int nRep;                /* Size of zRep */
  i64 nOut;                /* Maximum size of zOut */
  int loopLimit;           /* Last zStr[] that might match zPattern[] */
  int i, j;                /* Loop counters */



  assert( argc==3 );
  UNUSED_PARAMETER(argc);
  zStr = sqlite3_value_text(argv[0]);
  if( zStr==0 ) return;
  nStr = sqlite3_value_bytes(argv[0]);
  assert( zStr==sqlite3_value_text(argv[0]) );  /* No encoding change */
................................................................................
  nOut = nStr + 1;
  assert( nOut<SQLITE_MAX_LENGTH );
  zOut = contextMalloc(context, (i64)nOut);
  if( zOut==0 ){
    return;
  }
  loopLimit = nStr - nPattern;  

  for(i=j=0; i<=loopLimit; i++){
    if( zStr[i]!=zPattern[0] || memcmp(&zStr[i], zPattern, nPattern) ){
      zOut[j++] = zStr[i];
    }else{
      u8 *zOld;
      sqlite3 *db = sqlite3_context_db_handle(context);
      nOut += nRep - nPattern;
      testcase( nOut-1==db->aLimit[SQLITE_LIMIT_LENGTH] );
      testcase( nOut-2==db->aLimit[SQLITE_LIMIT_LENGTH] );
      if( nOut-1>db->aLimit[SQLITE_LIMIT_LENGTH] ){
        sqlite3_result_error_toobig(context);
        sqlite3_free(zOut);
        return;
      }







      zOld = zOut;
      zOut = sqlite3_realloc64(zOut, (int)nOut);
      if( zOut==0 ){
        sqlite3_result_error_nomem(context);
        sqlite3_free(zOld);
        return;


      }
      memcpy(&zOut[j], zRep, nRep);
      j += nRep;
      i += nPattern-1;
    }
  }
  assert( j+nStr-i+1==nOut );
  memcpy(&zOut[j], &zStr[i], nStr-i);
  j += nStr - i;
  assert( j<=nOut );
  zOut[j] = 0;
  sqlite3_result_text(context, (char*)zOut, j, sqlite3_free);
}








>
>







 







>




<
|
|
<
<
|
|
|
|
|
>
>
>
>
>
>
>
|
|
|
|
|
|
>
>






|

  unsigned char *zOut;              /* The output */
  int nStr;                /* Size of zStr */
  int nPattern;            /* Size of zPattern */
  int nRep;                /* Size of zRep */
  i64 nOut;                /* Maximum size of zOut */
  int loopLimit;           /* Last zStr[] that might match zPattern[] */
  int i, j;                /* Loop counters */
  unsigned cntExpand;      /* Number zOut expansions */
  sqlite3 *db = sqlite3_context_db_handle(context);

  assert( argc==3 );
  UNUSED_PARAMETER(argc);
  zStr = sqlite3_value_text(argv[0]);
  if( zStr==0 ) return;
  nStr = sqlite3_value_bytes(argv[0]);
  assert( zStr==sqlite3_value_text(argv[0]) );  /* No encoding change */
................................................................................
  nOut = nStr + 1;
  assert( nOut<SQLITE_MAX_LENGTH );
  zOut = contextMalloc(context, (i64)nOut);
  if( zOut==0 ){
    return;
  }
  loopLimit = nStr - nPattern;  
  cntExpand = 0;
  for(i=j=0; i<=loopLimit; i++){
    if( zStr[i]!=zPattern[0] || memcmp(&zStr[i], zPattern, nPattern) ){
      zOut[j++] = zStr[i];
    }else{

      if( nRep>nPattern ){
        nOut += nRep - nPattern;


        if( nOut-1>db->aLimit[SQLITE_LIMIT_LENGTH] ){
          sqlite3_result_error_toobig(context);
          sqlite3_free(zOut);
          return;
        }
        testcase( nOut-1==db->aLimit[SQLITE_LIMIT_LENGTH] );
        testcase( nOut-2==db->aLimit[SQLITE_LIMIT_LENGTH] );
        cntExpand++;
        if( (cntExpand&(cntExpand-1))==0 ){
          /* Grow the size of the output buffer only on substitutions
          ** whose index is a power of two: 1, 2, 4, 8, 16, 32, ... */
          u8 *zOld;
          zOld = zOut;
          zOut = sqlite3_realloc64(zOut, (int)nOut + (nOut - nStr - 1));
          if( zOut==0 ){
            sqlite3_result_error_nomem(context);
            sqlite3_free(zOld);
            return;
          }
        }
      }
      memcpy(&zOut[j], zRep, nRep);
      j += nRep;
      i += nPattern-1;
    }
  }
  assert( j+nStr-i+1<=nOut );
  memcpy(&zOut[j], &zStr[i], nStr-i);
  j += nStr - i;
  assert( j<=nOut );
  zOut[j] = 0;
  sqlite3_result_text(context, (char*)zOut, j, sqlite3_free);
}

Changes to test/func.test.

  do_test func-9.12-utf8 {
    execsql {SELECT hex(replace('abcdefg','','12'))}
  } {61626364656667}
  do_test func-9.13-utf8 {
    execsql {SELECT hex(replace('aabcdefg','a','aaa'))}
  } {616161616161626364656667}
}











  
# Use the "sqlite_register_test_function" TCL command which is part of
# the text fixture in order to verify correct operation of some of
# the user-defined SQL function APIs that are not used by the built-in
# functions.
#
set ::DB [sqlite3_connection_pointer db]








>
>
>
>
>
>
>
>
>
>
>

  do_test func-9.12-utf8 {
    execsql {SELECT hex(replace('abcdefg','','12'))}
  } {61626364656667}
  do_test func-9.13-utf8 {
    execsql {SELECT hex(replace('aabcdefg','a','aaa'))}
  } {616161616161626364656667}
}
do_execsql_test func-9.14 {
  WITH RECURSIVE c(x) AS (
     VALUES(1)
     UNION ALL
     SELECT x+1 FROM c WHERE x<1040
  )
  SELECT 
    count(*),
    sum(length(replace(printf('abc%.*cxyz',x,'m'),'m','nnnn'))-(6+x*4))
  FROM c;
} {1040 0}
  
# Use the "sqlite_register_test_function" TCL command which is part of
# the text fixture in order to verify correct operation of some of
# the user-defined SQL function APIs that are not used by the built-in
# functions.
#
set ::DB [sqlite3_connection_pointer db]