[ruby-core:71536] [Ruby trunk - Feature #10984] Hash#contain? to check whether hash contains other hash

[prijutme4ty@gmail.com]

Issue #10984 has been updated by Ilya Vorontsov.


I've missed absence of `<=>` first. Yes, you are right. And it can slightly reduce damage.

But anyway it doesn't resolve issues with misinterpretation of comparison negation. My qsort function is just the one problem which lie on surface. There are lots `if (a < b) ...; else ...` constructions in lots of codebases.
I'm sure that such behaviour will lead to tons of subtle bugs. 

Also It's highly probable that some libraries will be subjected to malicious inputs which will cause infinite recursion bombs or other threats. Here I've slightly changed qsort code using `#reject` instead of `#select`. Not a very natural code but it's still correct:

```ruby
def qsort(arr)
  return arr  if arr.size <= 1
  pivot = arr[arr.length / 2]
  left = arr.reject{|el| el >= pivot }
  right = arr.reject{|el| el <= pivot }
  central = arr.select{|el| el == pivot }
  qsort(left) + central + qsort(right)
end
```

This code will not reduce size as in my previous example but contrariwise will expand array size and break asymptotical estimations of CPU time.

```ruby
qsort( [{}, {a:1,b:2}, {c:3}, {a:1}, {b:2}] )
# => [{}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}, {:c=>3}, {:b=>2}, {:a=>1}, {:b=>2}, {:a=>1, :b=>2}]
```

Look at expansion rate.

```ruby
qsort( 10.times.map{|i| {i => i} } ).size # => 1023
qsort( 20.times.map{|i| {i => i} } ).size # => 1048575
qsort( 25.times.map{|i| {i => i} } ).size # => 33554431
```

The last array of 25 single-element hashes is sorted in a minute or so. It can easily hang server.

Ok, I specially wrote code subjected to this attack. But in a large codebase of ruby community there would be places which have similar problems (which are not problems for totally ordered sets like numbers). It can be hard to find and exploit it, but if you did - you have broken the server. Just imagine that some code which earlies just raised an exception due to bad input now ruins your application.

----------------------------------------
Feature #10984: Hash#contain? to check whether hash contains other hash
https://bugs.ruby-lang.org/issues/10984#change-54916

* Author: Olivier Lacan
* Status: Closed
* Priority: Normal
* Assignee: Akira Tanaka
----------------------------------------
Comparing hashes seems like a common practice but there currently isn't a method to ask a 
hash instance whether it includes another hash instance.

The most intuitive method to reach for would be `Hash#include?` but it is in fact an alias to `Hash#has_key?`

What I'm looking for can be achieved with:

~~~
class Hash
  def contain?(other)
    self.merge(other) == self
  end
end
~~~

Here's a simple demo of `#contain?` in use:

~~~
{ a: true, b: false }.contain?({ a: true})
# => true

{ a: true, b: false }.contain?({ b: false})
# => true

{ a: true, b: false }.contain?({ a: false})
# => false

{ a: true, b: false }.contain?({ c: true})
# => false
~~~

One important note is that this method is *not checking for nested hash matches*.
This may need to be addressed when the parameters include a nested hash perhaps.

Thanks to Terence Lee's help, nobu created a patch for this feature last year. 
I've only modified the name of the method from [his original patch](https://gist.github.com/nobu/dfe8ba14a48fc949f2ed) and attached it to this issue.

---Files--------------------------------
Hash#contain_.patch (2.22 KB)


-- 
https://bugs.ruby-lang.org/