Issue #17354 has been updated by mame (Yusuke Endoh).
Why do you want to know the location of the autoload call after it is actually loaded? I guess that information is already gone from the runtime as well.
----------------------------------------
Bug #17354: Module#const_source_location is misleading for constants awaiting autoload
https://bugs.ruby-lang.org/issues/17354#change-104563
* Author: tomstuart (Tom Stuart)
* Status: Open
* Priority: Normal
* ruby -v: ruby 2.7.2p137 (2020-10-01 revision 5445e04352) [x86_64-darwin20]
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN
----------------------------------------
Feature #10771 added `Module#const_source_location` as a way to find the source location of a constant’s definition. Bug #16764 reported that it didn’t work correctly for autoloaded constants, instead giving the source location of the `autoload` call site. This was fixed in `v3_0_0_preview1` in commit:92730810 and backported to `v2_7_2` in commit:c65aae11.
However, `#const_source_location` still returns the `autoload` call site for constants which have not yet been loaded:
```
% echo 'class Foo; end' > foo.rb
% irb
>> Module.const_defined?(:Foo)
=> false
>> Module.const_source_location(:Foo)
=> nil
>> autoload :Foo, './foo'
=> nil
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["(irb)", 3]
>> Module.const_get(:Foo)
=> Foo
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["./foo.rb", 1]
```
This edge case is undocumented and surprising. It looks like a bug to the programmer who receives the `autoload` location instead of one of the documented return values of `#const_source_location` (`nil`, `[]`, or the definition’s source location).
We could either:
* change the behaviour of `#const_source_location` to return `[]` for constants awaiting autoload, which is consistent with the [return value of `Module#const_defined?`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_defined-3F) in this case (“if the constant is not present but there is an autoload for it, `true` is returned directly”), as well as the [return value of `#const_source_location`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_source_location) for other constants whose source location is unknown (“if the constant is found, but its source location can not be extracted (constant is defined in C code), empty array is returned”); or
* document the current behaviour of `#const_source_location` to make it less surprising.
I recommend the first option — although the current behaviour was recently specified in source:spec/ruby/core/module/const_source_location_spec.rb@6d059674#L209, it doesn’t seem intentional — but if that’s not feasible, simply documenting this edge case would also be an improvement.
--
https://bugs.ruby-lang.org/
Issue #9115 has been updated by Eregon (Benoit Daloze).
"defensive" code like that is just broken, no one should `rescue Exception`.
Let's remove that outer `rescue`?
If `synchronize` raises there is a serious bug worth fixing and not ignoring.
Similarly I think the inner `rescue`s should either be removed or only rescue IOError if really needed.
----------------------------------------
Bug #9115: Logger traps all exceptions; breaks Timeout
https://bugs.ruby-lang.org/issues/9115#change-104556
* Author: cphoenix (Chris Phoenix)
* Status: Assigned
* Priority: Normal
* Assignee: sonots (Naotoshi Seo)
* ruby -v: ruby 2.0.0p247 (2013-06-27) [i386-mingw32]
----------------------------------------
Line 577-579 of logger.rb
rescue Exception => ignored
warn("log writing failed. #{ignored}")
end
Thus, when the system times out in the middle of writing a log message, it warns "log writing failed. execution expired" and just keeps right on running.
This is true in 1.9.3 as well. I haven't looked at older versions.
Pardon me while I go grep "rescue Exception" in the entire Ruby codebase, and see whether I can reliably use Timeout at all...
OK, you might check out C:\Ruby200\lib\ruby\gems\2.0.0\gems\activerecord-3.2.13\lib\active_record\railties\databases.rake
All the other "rescue Exception" seem to re-raise it, except maybe C:\Ruby200\lib\ruby\2.0.0\xmlrpc\server.rb and C:\Ruby200\lib\ruby\gems\2.0.0\gems\activesupport-3.2.13\lib\active_support\callbacks.rb
--
https://bugs.ruby-lang.org/
Issue #19872 has been reported by vo.x (Vit Ondruch).
----------------------------------------
Bug #19872: TestRequireLib#test_thread_size test case is unstable
https://bugs.ruby-lang.org/issues/19872
* Author: vo.x (Vit Ondruch)
* Status: Open
* Priority: Normal
* ruby -v: ruby 3.3.0dev (2023-09-05 master 7c8932365f) [x86_64-linux]
* Backport: 3.0: UNKNOWN, 3.1: UNKNOWN, 3.2: UNKNOWN
----------------------------------------
Just exploring the difference in skipped test cases, it seems to be due to `TestRequireLib#test_thread_size`. One test run might look like:
~~~
84) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/reline/history.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant Reline
85) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/reline/line_editor.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant Reline
86) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/net/http/generic_request.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant Net
87) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/rdoc/markup/formatter.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant RDoc
88) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/rdoc/generator/pot/message_extractor.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant RDoc
89) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/rdoc/markup/block_quote.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant RDoc
90) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/irb/context.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant IRB
91) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/rdoc/markup/indented_paragraph.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant RDoc
92) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/rdoc/parser/text.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant RDoc
93) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/rdoc/markup/to_label.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant RDoc
~~~
While in the other run, there is e.g. just one test skipped:
~~~
40) Skipped:
TestRequireLib#test_thread_size:/builddir/build/BUILD/ruby-3.3.0-7c8932365f/lib/rdoc/markdown/entities.rb [/builddir/build/BUILD/ruby-3.3.0-7c8932365f/test/ruby/test_require_lib.rb:21]:
uninitialized constant RDoc
~~~
I can't help myself, but this test case contains too much randomness to my taste.
--
https://bugs.ruby-lang.org/
Issue #19075 has been updated by kyanagi (Kouhei Yanagita).
FYI: Julia has `searchsortedfirst` and `searchsortedlast`
https://docs.julialang.org/en/v1/base/sort/#Base.Sort.searchsortedfirst
----------------------------------------
Feature #19075: Binary searching for the last element
https://bugs.ruby-lang.org/issues/19075#change-104553
* Author: kyanagi (Kouhei Yanagita)
* Status: Open
* Priority: Normal
----------------------------------------
My latest proposal is https://bugs.ruby-lang.org/issues/19075#note-6.
I will leave the initial proposal below.
---
PR: https://github.com/ruby/ruby/pull/6611
(I'm going to talk about `Array` here, but the same argument can be made for `Range`. If `Array#bsearch_last` is acceptable, I will work also for `Range`.)
Ruby's bsearch returns the first element which satisfies the given block.
```ruby
# Search the first element greater than 18
array = [10, 15, 20, 25]
array.bsearch { |x| x > 18 } # => 20
```
If we want the last element, we need to invert the condition and step backward.
```ruby
# Search the last element less than 18
array = [10, 15, 20, 25]
index = array.bsearch_index { |x| !(x < 18) }
array[index-1] # => 15
```
Of course, we need to consider `nil` and the boundary.
```ruby
# Search the last element less than 100
index = array.bsearch_index { |x| !(x < 100) } # => nil
if index.nil?
array.last # => 25
else
array[index-1]
end
```
```ruby
# Search the last element less than 0
index = array.bsearch_index { |x| !(x < 0) } # => 0
if index.nil?
array.last
elsif index == 0
nil
else
array[index-1]
end
```
This is where mistakes can easily be made, so I propose `Array#bsearch_last` and `Array#bsearch_last_index`.
`Array#bsearch_last` returns the last element which satisfies the given block.
`Array#bsearch` requires that all false-evaluating elements precede all true-evaluating elements. As is clear from the meaning of the method, conversely to `bsearch`, `bsearch_last` requires that all true-evaluating elements precede all false-evaluating elements. (If `bsearch_last` is acceptable, the name "find-minimum mode" should be changed.)
```ruby
array = [10, 15, 20, 25]
array.bsearch_last { |x| x < 18 } # => 15
array.bsearch_last { |x| x < 100 } # => 25
array.bsearch_last { |x| x < 0 } # => nil
```
There are several possible options for find-any mode.
(1) `bsearch_last` does not support find-any mode.
A block for `bsearch_last` must return `true`, `false` or `nil`.
```
[1, 2, 3].bsearch_last { 0 } # => TypeError
```
My pull request tentatively includes this implementation.
(2) `bsearch_last` supports find-any mode and it behaves like `bsearch`.
`bsearch` with find-any mode returns an element, for which the block returns zero.
If multiple elements satisfy the condition, it is not determined which of them will be returned.
It is conceivable that `bsearch_last` behaves in the same way as `bsearch`.
```
# current behavior
# It is not specified whether `:b`, `:c`, or `:d` is returned.
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch { |a, b| 2 <=> a } # => [2, :c]
```
(3) `bsearch_last` supports find-any mode and returns the last element. Make `bsearch` return the first element.
Change the behavior of `bsearch` to return the first element for which the block returns zero.
`bsearch_last` returns the last element for which the block returns zero.
```
# Change it like this:
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch { |a, b| 2 <=> a } # => [2, :b]
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch_last { |a, b| 2 <=> a } # => [2, :d]
```
(If this option is adopted, the name "find-any mode" should be renamed.)
--
https://bugs.ruby-lang.org/
Issue #17354 has been updated by sawa (Tsuyoshi Sawada).
mame (Yusuke Endoh) wrote in #note-14:
> As I said, you can use it safely in conjunction with `Module.autoload?`.
>
> ```ruby
> autoload "A", File.expand_path("./a.rb")
> p Module.autoload?(:A) #=> "/path/to/a.rb"
> p Module.const_source_location(:A) #=> autoload call site
> p A
> p Module.autoload?(:A) #=> nil
> p Module.const_source_location(:A) #=> def site
> ```
What I meant is that, once you are in a location beyond where `A` was called, you cannot reference the call site any more.
```rb
# b.rb
autoload "A", File.expand_path("./a.rb")
# short code
load "c.rb"
```
```rb
# c.rb
p A
# long code, or in a different file after a chain of file loading
load "d.rb"
```
```rb
# d.rb
# You can tell that you cannot achieve the call site from here:
p Module.autoload?(:A) #=> nil
# And in fact, what is returned is not the call site:
p Module.const_source_location(:A) #=> def site
```
Provided you are currently working on d.rb, in order to use `const_source_location` to find the call site, you have to find a location where the constant is not yet called (all the way back to before the line in c.rb where `A` is called), and then use `const_source_location` there. If you are able to do that, you can probably find the call site directly without much more effort.
----------------------------------------
Bug #17354: Module#const_source_location is misleading for constants awaiting autoload
https://bugs.ruby-lang.org/issues/17354#change-104551
* Author: tomstuart (Tom Stuart)
* Status: Open
* Priority: Normal
* ruby -v: ruby 2.7.2p137 (2020-10-01 revision 5445e04352) [x86_64-darwin20]
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN
----------------------------------------
Feature #10771 added `Module#const_source_location` as a way to find the source location of a constant’s definition. Bug #16764 reported that it didn’t work correctly for autoloaded constants, instead giving the source location of the `autoload` call site. This was fixed in `v3_0_0_preview1` in commit:92730810 and backported to `v2_7_2` in commit:c65aae11.
However, `#const_source_location` still returns the `autoload` call site for constants which have not yet been loaded:
```
% echo 'class Foo; end' > foo.rb
% irb
>> Module.const_defined?(:Foo)
=> false
>> Module.const_source_location(:Foo)
=> nil
>> autoload :Foo, './foo'
=> nil
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["(irb)", 3]
>> Module.const_get(:Foo)
=> Foo
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["./foo.rb", 1]
```
This edge case is undocumented and surprising. It looks like a bug to the programmer who receives the `autoload` location instead of one of the documented return values of `#const_source_location` (`nil`, `[]`, or the definition’s source location).
We could either:
* change the behaviour of `#const_source_location` to return `[]` for constants awaiting autoload, which is consistent with the [return value of `Module#const_defined?`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_defined-3F) in this case (“if the constant is not present but there is an autoload for it, `true` is returned directly”), as well as the [return value of `#const_source_location`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_source_location) for other constants whose source location is unknown (“if the constant is found, but its source location can not be extracted (constant is defined in C code), empty array is returned”); or
* document the current behaviour of `#const_source_location` to make it less surprising.
I recommend the first option — although the current behaviour was recently specified in source:spec/ruby/core/module/const_source_location_spec.rb@6d059674#L209, it doesn’t seem intentional — but if that’s not feasible, simply documenting this edge case would also be an improvement.
--
https://bugs.ruby-lang.org/
Issue #17354 has been updated by mame (Yusuke Endoh).
sawa (Tsuyoshi Sawada) wrote in #note-13:
> You cannot safely use `const_source_location` to extract the autoload call site since the return value depends on whether the constant is called or not:
As I said, you can use it safely in conjunction with `Module.autoload?`.
```ruby
autoload "A", File.expand_path("./a.rb")
p Module.autoload?(:A) #=> "/path/to/a.rb"
p Module.const_source_location(:A) #=> autoload call site
p A
p Module.autoload?(:A) #=> nil
p Module.const_source_location(:A) #=> def site
```
As Aaron says, I think it is one reasonable design to load it immediately when calling `Module.const_source_location`.
But I think the current behavior is also reasonable enough. I don't know if we need to risk compatibility to change it.
----------------------------------------
Bug #17354: Module#const_source_location is misleading for constants awaiting autoload
https://bugs.ruby-lang.org/issues/17354#change-104549
* Author: tomstuart (Tom Stuart)
* Status: Open
* Priority: Normal
* ruby -v: ruby 2.7.2p137 (2020-10-01 revision 5445e04352) [x86_64-darwin20]
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN
----------------------------------------
Feature #10771 added `Module#const_source_location` as a way to find the source location of a constant’s definition. Bug #16764 reported that it didn’t work correctly for autoloaded constants, instead giving the source location of the `autoload` call site. This was fixed in `v3_0_0_preview1` in commit:92730810 and backported to `v2_7_2` in commit:c65aae11.
However, `#const_source_location` still returns the `autoload` call site for constants which have not yet been loaded:
```
% echo 'class Foo; end' > foo.rb
% irb
>> Module.const_defined?(:Foo)
=> false
>> Module.const_source_location(:Foo)
=> nil
>> autoload :Foo, './foo'
=> nil
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["(irb)", 3]
>> Module.const_get(:Foo)
=> Foo
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["./foo.rb", 1]
```
This edge case is undocumented and surprising. It looks like a bug to the programmer who receives the `autoload` location instead of one of the documented return values of `#const_source_location` (`nil`, `[]`, or the definition’s source location).
We could either:
* change the behaviour of `#const_source_location` to return `[]` for constants awaiting autoload, which is consistent with the [return value of `Module#const_defined?`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_defined-3F) in this case (“if the constant is not present but there is an autoload for it, `true` is returned directly”), as well as the [return value of `#const_source_location`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_source_location) for other constants whose source location is unknown (“if the constant is found, but its source location can not be extracted (constant is defined in C code), empty array is returned”); or
* document the current behaviour of `#const_source_location` to make it less surprising.
I recommend the first option — although the current behaviour was recently specified in source:spec/ruby/core/module/const_source_location_spec.rb@6d059674#L209, it doesn’t seem intentional — but if that’s not feasible, simply documenting this edge case would also be an improvement.
--
https://bugs.ruby-lang.org/
Issue #17354 has been updated by sawa (Tsuyoshi Sawada).
mame (Yusuke Endoh) wrote in #note-11:
> 2. If we want to identify where a constant is set as autoload, we can use the current `Module#const_source_location`.
>
> If `Module#const_source_location` returns `[]` or `nil` when a constant is not actually loaded, it breaks the scenario 2. In fact I have used the method to identify the callsite of autoload for debugging.
You cannot safely use `const_source_location` (by itself) to extract the autoload call site since the return value depends on whether the constant is called or not:
```rb
autoload "A", "path_to_def_of_A"
autoload "B", "path_to_def_of_B"
p A
p Module.const_source_location("A") # => def site
p Module.const_source_location("B") # => autoload call site
```
Using `const_source_location`, you can know the call site of `B`, but not the call site of `A`. If you wanted to safely know the autoload call site for a constant name, you would need a different mechanism anyway.
Even worse, the return value for the same constant name may change:
```rb
autoload "A", File.expand_path("~/tmp/bin/a.rb")
p Module.const_source_location("A") # => autoload call site
p A
p Module.const_source_location("A") # => def site
```
Also, mame suggests to retain the current behavior of `const_source_location` and use it in combination with `autoload?` or `const_get`. That makes `const_source_location` useless by itself, and would have to always be used together with `autoload?` or `const_get` if there is a possibility of autoload.
Hence, if there is a use case of extracting the autoload call site as mame discusses, (which I am neither for nor against), there should be a different method for doing that, and `const_source_location` should not return autoload call site at all.
----------------------------------------
Bug #17354: Module#const_source_location is misleading for constants awaiting autoload
https://bugs.ruby-lang.org/issues/17354#change-104548
* Author: tomstuart (Tom Stuart)
* Status: Open
* Priority: Normal
* ruby -v: ruby 2.7.2p137 (2020-10-01 revision 5445e04352) [x86_64-darwin20]
* Backport: 2.5: UNKNOWN, 2.6: UNKNOWN, 2.7: UNKNOWN
----------------------------------------
Feature #10771 added `Module#const_source_location` as a way to find the source location of a constant’s definition. Bug #16764 reported that it didn’t work correctly for autoloaded constants, instead giving the source location of the `autoload` call site. This was fixed in `v3_0_0_preview1` in commit:92730810 and backported to `v2_7_2` in commit:c65aae11.
However, `#const_source_location` still returns the `autoload` call site for constants which have not yet been loaded:
```
% echo 'class Foo; end' > foo.rb
% irb
>> Module.const_defined?(:Foo)
=> false
>> Module.const_source_location(:Foo)
=> nil
>> autoload :Foo, './foo'
=> nil
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["(irb)", 3]
>> Module.const_get(:Foo)
=> Foo
>> Module.const_defined?(:Foo)
=> true
>> Module.const_source_location(:Foo)
=> ["./foo.rb", 1]
```
This edge case is undocumented and surprising. It looks like a bug to the programmer who receives the `autoload` location instead of one of the documented return values of `#const_source_location` (`nil`, `[]`, or the definition’s source location).
We could either:
* change the behaviour of `#const_source_location` to return `[]` for constants awaiting autoload, which is consistent with the [return value of `Module#const_defined?`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_defined-3F) in this case (“if the constant is not present but there is an autoload for it, `true` is returned directly”), as well as the [return value of `#const_source_location`](https://docs.ruby-lang.org/en/2.7.0/Module.html#method-i-const_source_location) for other constants whose source location is unknown (“if the constant is found, but its source location can not be extracted (constant is defined in C code), empty array is returned”); or
* document the current behaviour of `#const_source_location` to make it less surprising.
I recommend the first option — although the current behaviour was recently specified in source:spec/ruby/core/module/const_source_location_spec.rb@6d059674#L209, it doesn’t seem intentional — but if that’s not feasible, simply documenting this edge case would also be an improvement.
--
https://bugs.ruby-lang.org/
Issue #19858 has been reported by mame (Yusuke Endoh).
----------------------------------------
Misc #19858: DevMeeting-2023-09-14
https://bugs.ruby-lang.org/issues/19858
* Author: mame (Yusuke Endoh)
* Status: Open
* Priority: Normal
----------------------------------------
# The next dev meeting
**Date: 2023/09/14 13:00-17:00** (JST)
Log: *TBD*
- Dev meeting *IS NOT* a decision-making place. All decisions should be done at the bug tracker.
- Dev meeting is a place we can ask Matz, nobu, nurse and other developers directly.
- Matz is a very busy person. Take this opportunity to ask him. If you can not attend, other attendees can ask instead of you (if attendees can understand your issue).
- We will write a record of the discussion in the file or to each ticket in English.
- All activities are best-effort (keep in mind that most of us are volunteer developers).
- The date, time and place of the meeting are scheduled according to when/where we can reserve Matz's time.
- *DO NOT* discuss then on this ticket, please.
# Call for agenda items
If you have a ticket that you want matz and committers to discuss, please post it into this ticket in the following format:
```
* [Ticket ref] Ticket title (your name)
* Comment (A summary of the ticket, why you put this ticket here, what point should be discussed, etc.)
```
Example:
```
* [Feature #14609] `Kernel#p` without args shows the receiver (ko1)
* I feel this feature is very useful and some people say :+1: so let discuss this feature.
```
- It is recommended to add a comment by 2023/09/11. We hold a preparatory meeting to create an agenda a few days before the dev-meeting.
- The format is strict. We'll use [this script to automatically create an markdown-style agenda](https://gist.github.com/mame/b0390509ce1491b43610b9ebb665eb86). We may ignore a comment that does not follow the format.
- Your comment is mandatory. We cannot read all discussion of the ticket in a limited time. We appreciate it if you could write a short summary and update from a previous discussion.
--
https://bugs.ruby-lang.org/
Issue #19075 has been updated by kyanagi (Kouhei Yanagita).
(In the following, searching for the last element will be referred to as "LAST".)
There are often cases where searching for the last element would be useful.
A typical example that immediately comes to mind is as follows:
* When we have a list of events with timestamps, find the last event that occurred up to a specific time
```
events.bsearch(target: :last) { |event| event.timestamp <= time }
```
Of course, this can be written without LAST, but I believe using LAST makes it more natural
and less prone to errors.
```
index = events.bsearch { |event| event.timestamp > time }
last_event = if index.nil?
events.last
elsif index == 0
nil
else
events[index-1]
end
```
A similar example is the case of finding the most expensive item available in a shop.
```
highest = item_prices.bsearch(target: :last) { |price| price <= your_money }
```
Let's see another example.
Given a sorted list of words, find the last word with a particular prefix in lexicographic order.
```
words = %w(pen pi pin pine ping png)
prefix = 'pin'
# => want to get 'ping'
```
With LAST and determistic find-any mode (what I call find-by-number mode in my pull request),
the solution to this problem can be written as follows.
```
words.bsearch(target: :last) { |w| prefix <=> w[0, prefix.size] }
```
Using the current `bsearch_index`, it would be like this.
```
index = words.bsearch_index { |w| w[0, prefix.size] > prefix }
w = if index.nil?
words.last
elsif index == 0
nil
else
words[index-1]
end
ans = w if w[0, prefix.size] == prefix
```
The difference is obvious.
When it comes to names, I thought `target: :last` was easy to understand.
However, the fact that several people have said that it is confusing means that this may not be an appropriate name.
I hope we can find a good name.
As mame-san says, `bsearch` is a confusing method in the first place.
The condition that false must precede true in the value returned by the block, or that positive must precede zero and zero must precede negative, is difficult to imagine from the appearance of the method.
Rather than trying to interpret the meaning of behavior, a formal name which represents "the reverse of `bsearch`" might be easier to understand.
----------------------------------------
Feature #19075: Binary searching for the last element
https://bugs.ruby-lang.org/issues/19075#change-104544
* Author: kyanagi (Kouhei Yanagita)
* Status: Open
* Priority: Normal
----------------------------------------
My latest proposal is https://bugs.ruby-lang.org/issues/19075#note-6.
I will leave the initial proposal below.
---
PR: https://github.com/ruby/ruby/pull/6611
(I'm going to talk about `Array` here, but the same argument can be made for `Range`. If `Array#bsearch_last` is acceptable, I will work also for `Range`.)
Ruby's bsearch returns the first element which satisfies the given block.
```ruby
# Search the first element greater than 18
array = [10, 15, 20, 25]
array.bsearch { |x| x > 18 } # => 20
```
If we want the last element, we need to invert the condition and step backward.
```ruby
# Search the last element less than 18
array = [10, 15, 20, 25]
index = array.bsearch_index { |x| !(x < 18) }
array[index-1] # => 15
```
Of course, we need to consider `nil` and the boundary.
```ruby
# Search the last element less than 100
index = array.bsearch_index { |x| !(x < 100) } # => nil
if index.nil?
array.last # => 25
else
array[index-1]
end
```
```ruby
# Search the last element less than 0
index = array.bsearch_index { |x| !(x < 0) } # => 0
if index.nil?
array.last
elsif index == 0
nil
else
array[index-1]
end
```
This is where mistakes can easily be made, so I propose `Array#bsearch_last` and `Array#bsearch_last_index`.
`Array#bsearch_last` returns the last element which satisfies the given block.
`Array#bsearch` requires that all false-evaluating elements precede all true-evaluating elements. As is clear from the meaning of the method, conversely to `bsearch`, `bsearch_last` requires that all true-evaluating elements precede all false-evaluating elements. (If `bsearch_last` is acceptable, the name "find-minimum mode" should be changed.)
```ruby
array = [10, 15, 20, 25]
array.bsearch_last { |x| x < 18 } # => 15
array.bsearch_last { |x| x < 100 } # => 25
array.bsearch_last { |x| x < 0 } # => nil
```
There are several possible options for find-any mode.
(1) `bsearch_last` does not support find-any mode.
A block for `bsearch_last` must return `true`, `false` or `nil`.
```
[1, 2, 3].bsearch_last { 0 } # => TypeError
```
My pull request tentatively includes this implementation.
(2) `bsearch_last` supports find-any mode and it behaves like `bsearch`.
`bsearch` with find-any mode returns an element, for which the block returns zero.
If multiple elements satisfy the condition, it is not determined which of them will be returned.
It is conceivable that `bsearch_last` behaves in the same way as `bsearch`.
```
# current behavior
# It is not specified whether `:b`, `:c`, or `:d` is returned.
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch { |a, b| 2 <=> a } # => [2, :c]
```
(3) `bsearch_last` supports find-any mode and returns the last element. Make `bsearch` return the first element.
Change the behavior of `bsearch` to return the first element for which the block returns zero.
`bsearch_last` returns the last element for which the block returns zero.
```
# Change it like this:
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch { |a, b| 2 <=> a } # => [2, :b]
[[1,:a], [2, :b], [2, :c], [2, :d], [3, :e]].bsearch_last { |a, b| 2 <=> a } # => [2, :d]
```
(If this option is adopted, the name "find-any mode" should be renamed.)
--
https://bugs.ruby-lang.org/