D issues are now tracked on GitHub. This Bugzilla instance remains as a read-only archive.
Issue 21702 - avoid quadratic template expansion in constraints of multiple search term versions of std.algorithm.searching.startsWith & endsWith
Summary: avoid quadratic template expansion in constraints of multiple search term ver...
Status: RESOLVED FIXED
Alias: None
Product: D
Classification: Unclassified
Component: phobos (show other issues)
Version: D2
Hardware: All All
: P1 normal
Assignee: No Owner
URL:
Keywords: pull
Depends on:
Blocks: 21473
  Show dependency tree / graph
 
Reported: 2021-03-12 16:53 UTC by Nathan S.
Modified: 2021-04-27 09:42 UTC (History)
0 users

See Also:

Attachments
Add an attachment (proposed patch, testcase, etc.)

Note You need to log in before you can comment on or make changes to this issue.
Description Nathan S. 2021-03-12 16:53:50 UTC 
See DMD issue #21473 for an example of reasonable library usage that takes more than 22 gigabytes of memory to compile (the process got killed before finishing). There is other stuff going on too but fixing this problem is enough to make the example compile.

The culprit is:

---
 uint endsWith(alias pred = "a == b", Range, Needles...)(Range doesThisEnd, Needles withOneOfThese)
 if (isBidirectionalRange!Range && Needles.length > 1 &&
    is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[0])) : bool) &&
    is(typeof(.endsWith!pred(doesThisEnd, withOneOfThese[1 .. $])) : uint))
---

Because in certain situations this is causing the compiler to hang I think it is reasonable to consider this a bug fix rather than an enhancement.
Comment 1 Dlang Bot 2021-03-12 17:03:57 UTC 
@n8sh created dlang/phobos pull request #7847 "Avoid quadratic template expansion in constraints of multiple search term versions of std.algorithm.searching.startsWith & endsWith" fixing this issue:

- Fix issue #21702 - avoid quadratic template expansion in constraints of multiple search term versions of std.algorithm.searching.startsWith & endsWith

https://github.com/dlang/phobos/pull/7847
Comment 2 Dlang Bot 2021-03-13 01:25:53 UTC 
dlang/phobos pull request #7847 "Avoid quadratic template expansion in constraints of multiple search term versions of std.algorithm.searching.startsWith & endsWith" was merged into stable:

- 9c7a7750ff7816c7d74f620dc4989b4b92bf904f by Nathan Sashihara:
  Fix issue #21702 - avoid quadratic template expansion in constraints of multiple search term versions of std.algorithm.searching.startsWith & endsWith

https://github.com/dlang/phobos/pull/7847
Comment 3 Dlang Bot 2021-04-25 13:45:59 UTC 
dlang/phobos pull request #7964 "merge stable" was merged into master:

- a23fa4ed06fe188582631bacd6f3405d99855fa6 by Nathan Sashihara:
  Fix issue #21702 - avoid quadratic template expansion in constraints of multiple search term versions of std.algorithm.searching.startsWith & endsWith

https://github.com/dlang/phobos/pull/7964
Comment 4 Dlang Bot 2021-04-27 09:42:39 UTC 
dlang/phobos pull request #8012 "merge stable" was merged into master:

- 6d9a508baf2689d7dcca54f677f8ec9ebdef421b by Nathan Sashihara:
  Fix issue #21702 - avoid quadratic template expansion in constraints of multiple search term versions of std.algorithm.searching.startsWith & endsWith

https://github.com/dlang/phobos/pull/8012