New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

counting the empty substring in a string results in infinite loop #8919

Closed
skilchen opened this Issue Sep 8, 2018 · 4 comments

Comments

Projects
None yet
3 participants
@skilchen
Copy link
Contributor

skilchen commented Sep 8, 2018

This example will never terminate:

import strutils

proc test(s, sub: string): int =
  count(s, sub)

echo test("hello world", "")

Since Nim allows the replacement of the empty substring, it would be probably reasonable to return the number of replacements that would be performed by replace(s, ""), ie. len(s) + 1 in the case of counting the empty substring (or the empty set[char]).

@dom96 dom96 added the Stdlib label Sep 8, 2018

@dom96

This comment has been minimized.

Copy link
Member

dom96 commented Sep 8, 2018

I agree. I recall a similar discussion to this which might be useful to look up.

eqperes added a commit to eqperes/Nim that referenced this issue Oct 10, 2018

Araq added a commit that referenced this issue Oct 12, 2018

Proposed solution for issue #8919 (#9280)
* Proposed solution for issue #8919

* count sub/subs must be non-empty

@Araq Araq closed this Oct 12, 2018

@skilchen

This comment has been minimized.

Copy link
Contributor

skilchen commented Oct 13, 2018

Counting the empty string is not an API misuse as someone else claims. But raising an exception is better than looping infinitely.

In some circles the empty string is considered as the identity operator of string concatenation. From this point of view it makes sense to allow the replacement of the empty string and therefore to count the occurrences of such replacements.

But currently it would be more important to fix the handling of the empty string (aka zero-length match) in re.nim where in some cases it also ends in infinite loops.

@Araq

This comment has been minimized.

Copy link
Member

Araq commented Oct 13, 2018

It is an API misuse and the fact that it needs special code logic everywhere suggests that the view "the empty string is the identity operator of string concatenation" is just misguided. This is multiplication written with +:

proc mul(a, b: Natural): Natural =
  result = 0
  for i in 1..b: result += a

Notice how the code naturally handles the b == 0 case.

@skilchen

This comment has been minimized.

Copy link
Contributor

skilchen commented Oct 13, 2018

The messages produced about the API misuse could be better:

echo count("", "")

produces

.../lib/pure/strutils.nim(1474, 12) `
0 < len(sub)`  [AssertionError]

and the similar echo count("", {}) produces

.../lib/pure/strutils.nim(1492, 12) `
0 < card(subs)`  [AssertionError]

A line-break before the first "`" instead of after it, would be better.

An explicit message such as "counting the empty string is an API misuse" or something similar would be helpful for logically impaired people like me.

Two other observations about the empty string:

  • strutils.find("somestring", "", n) returns n for any non-negative n.
  • strutils.rfind("somestring", "", n) returns 0 for any non-negative n.

I was expecting to get -1 when searching outside of the bounds of "somestring" (like for every other substring).
Are these bugs or legitimate consequences of my adversarial API misuse?

krux02 added a commit to krux02/Nim that referenced this issue Oct 15, 2018

Proposed solution for issue nim-lang#8919 (nim-lang#9280)
* Proposed solution for issue nim-lang#8919

* count sub/subs must be non-empty

narimiran added a commit to narimiran/Nim that referenced this issue Oct 31, 2018

Proposed solution for issue nim-lang#8919 (nim-lang#9280)
* Proposed solution for issue nim-lang#8919

* count sub/subs must be non-empty

narimiran added a commit to narimiran/Nim that referenced this issue Nov 1, 2018

Proposed solution for issue nim-lang#8919 (nim-lang#9280)
* Proposed solution for issue nim-lang#8919

* count sub/subs must be non-empty

narimiran added a commit that referenced this issue Nov 1, 2018

Proposed solution for issue #8919 (#9280)
* Proposed solution for issue #8919

* count sub/subs must be non-empty

narimiran added a commit that referenced this issue Nov 1, 2018

Proposed solution for issue #8919 (#9280)
* Proposed solution for issue #8919

* count sub/subs must be non-empty

(cherry picked from commit 14925ee)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment