fix(quickfix): avoid O(N^2) when filling from string typval (#16663)

github-actions[bot] · web-flow · commit aa0ddc6690a5 · 2021-12-15T08:08:53.000-07:00
When filling a quickfix/loclist from a string-typed VimL variable, the complexity is O(N^2) in the number of lines in the variable. The problem is caused by using `xstrlcpy(3)` to copy the characters from the current position up to the next newline into the quickfix/loclist buffer in a loop. strlcpy(3) returns the length of `src`, so by necessity it has to compute `strlen(src)`. This means scanning the full rest of the typval on every iteration while only copying a small fraction (up to the next '\n'). This is not a problem whenever the srclen-to-copylen ratio is close to 1, which it usually is. But not in this case. Since we already calculated exactly how many bytes we want to copy, we should be using memcpy(3). This problem is not present in Vim, as it uses `vim_strncpy`, a `strncpy(3)`-alike, which stops at either `\0` or `n`, whichever comes first. The quickfix/loclist window can be filled using a: 1. File (used by commands like :grep/:make/... to source directly from their errorfile) 2. Buffer (used by :cbuffer and its variants) 3. Typval a. String (used by :cexpr and its variants) b. List of strings (used by setqflist(), setloclist(), :cepxr and its variants) This commit optimizes case (3a), especially when the typval is a long string. The pathological path is triggered by (e.g.) :grep enhancements as found in https://gist.github.com/romainl/56f0c28ef953ffc157f36cc495947ab3: function! Grep(...) return system(join([&grepprg] + a:000), ' ')) endfunction :cgetexpr Grep('foo') It would've been better for Neovim to use `systemlist` here, before this commit.
diff --git a/src/nvim/quickfix.c b/src/nvim/quickfix.c
@@ -658,7 +658,8 @@ static int qf_get_next_str_line(qfstate_T *state)
     state->linebuf = IObuff;
     state->linelen = len;
   }
-  STRLCPY(state->linebuf, p_str, state->linelen + 1);
+  memcpy(state->linebuf, p_str, state->linelen);
+  state->linebuf[state->linelen] = '\0';
 
   // Increment using len in order to discard the rest of the line if it
   // exceeds LINE_MAXLEN.

Original file line number	Diff line number	Diff line change
`@@ -658,7 +658,8 @@ static int qf_get_next_str_line(qfstate_T *state)`
`658`	`658`	`state->linebuf = IObuff;`
`659`	`659`	`state->linelen = len;`
`660`	`660`	`}`
`661`		`- STRLCPY(state->linebuf, p_str, state->linelen + 1);`
	`661`	`+ memcpy(state->linebuf, p_str, state->linelen);`
	`662`	`+ state->linebuf[state->linelen] = '\0';`
`662`	`663`
`663`	`664`	`// Increment using len in order to discard the rest of the line if it`
`664`	`665`	`// exceeds LINE_MAXLEN.`