Project

General

Profile

Actions

Feature #16828

closed

Introduce find patterns

Added by ktsj (Kazuki Tsujimoto) almost 4 years ago. Updated about 1 month ago.

Status:
Closed
Target version:
-
[ruby-core:98131]

Description

I propose to add find pattern to pattern matching.

Specification

find_pattern: Constant(*var, pat, ..., *var)
            | Constant[*var, pat, ..., *var]
            | [*var, pat, ..., *var]

This pattern is similar to array pattern, except that it finds the first match values from the given object.

case ["a", 1, "b", "c", 2, "d", "e", "f", 3]
in [*pre, String => x, String => y, *post]
  p pre  #=> ["a", 1]
  p x    #=> "b"
  p y    #=> "c"
  p post #=> [2, "d", "e", "f", 3]
end

Note that, to avoid complexity, the proposed feature doesn't support backtracking. Thus, the following code raises a NoMatchingPatternError.

case [0, 1, 2]
in [*, a, *] if a == 1
end

Implementation

Updated by shyouhei (Shyouhei Urabe) almost 4 years ago

I am a noob in this area who don't understand what is good about it. Can you show us a bit more realistic example? The proposal kind of seems illustrative to me.

Updated by shevegen (Robert A. Heiler) almost 4 years ago

Is this a bit like .scan(), but applied to the pattern matching style? (Not
sure if I understood this completely but it reminds me a bit of using .scan()
and MatchData on the result possibly.)

Updated by matz (Yukihiro Matsumoto) almost 4 years ago

Suppose we have the following code:

json = {name: "Alice", children: [{name: "Bob", age: 6}, {name: "Chad", age: 4}]}
case json
in {name: "Alice", children: [{name: "Bob", age: age}]}
  p age
end

It doesn't match because array pattern does not search for the element. It only matches for an array with single element named "Bob". So to find an element in an array with multiple elements, you have to use find pattern like:

json = {name: "Alice", children: [{name: "Bob", age: 6}, {name: "Chad", age: 4}]}
case json
in {name: "Alice", children: [*, {name: "Bob", age: age}, *]}
  p age
end

Matz

Updated by matz (Yukihiro Matsumoto) almost 4 years ago

Accepted. But we have to clarify the term "backtracking" here. It does backtrack but not with a guard, right?

Matz.

Updated by Dan0042 (Daniel DeLorme) almost 4 years ago

From the implementation linked above:

case [0, 1, 2]
in [*, a, *] 
  p a #=> 0; non-greedy match
end

case [0, 1, 2]
in [*, b, 2, *]
  p b #=> 1; backtracking
end

So yes, it supports "backtracking" in a certain fashion otherwise the second case wouldn't match.

Note that it only supports splat expressions at the beginning and end of the array:

case [0, 1, 2, 3, 4, 5, 6]
in [*, a, *, b, 5, *] 
  p a, b
end
# syntax error, unexpected ',', expecting ']'
# in [*, a, *, b, 5, *]

Updated by ktsj (Kazuki Tsujimoto) almost 4 years ago

  • Status changed from Open to Assigned
  • Assignee set to ktsj (Kazuki Tsujimoto)

Accepted.

Thank you. I'll commit it.

But we have to clarify the term "backtracking" here. It does backtrack but not with a guard, right?

Yes. This is exactly what I intend.

Actions #7

Updated by sawa (Tsuyoshi Sawada) almost 4 years ago

  • Description updated (diff)
Actions #8

Updated by ktsj (Kazuki Tsujimoto) almost 4 years ago

  • Status changed from Assigned to Closed

Applied in changeset git|ddded1157a90d21cb54b9f07de35ab9b4cc472e1.


Introduce find pattern [Feature #16828]

Updated by Eregon (Benoit Daloze) about 1 month ago

An easy way to understand the "backtracking" of find pattern is it works like each_slice(n) and doesn't actually backtrack.
So its performance is linear to the number of elements of the array being matched.
https://github.com/ruby/ruby/commit/ddded1157a90d21cb54b9f07de35ab9b4cc472e1#diff-a5ba41b51e3655f9f244362a616282b5119d3e15dd6c52ee999bbdfcc5b86a77 has nice Ruby pseudo-code describing how it works.

Actions

Also available in: Atom PDF

Like0
Like0Like0Like0Like0Like0Like0Like0Like0Like0