Class: Mustermann::Set

Inherits:
Object
  • Object
show all
Defined in:
lib/mustermann/set.rb,
lib/mustermann/set/trie.rb,
lib/mustermann/set/cache.rb,
lib/mustermann/set/match.rb,
lib/mustermann/set/linear.rb,
lib/mustermann/set/strict_order.rb

Overview

Note:

Adding patterns via #add, #update, or #[]= is not thread-safe, but matching and expanding is.

A collection of patterns that can be matched against strings efficiently.

Each pattern in the set may be associated with one or more arbitrary values, such as handler objects or route actions. A single #match call returns a Match that provides both the captured parameters and the associated value for the matched pattern. When the set contains many patterns, an internal trie (prefix tree) is used to dispatch requests in sub-linear time.

Examples:

Building a routing table

require 'mustermann/set'

set = Mustermann::Set.new
set.add('/users/:id',  :users_show)
set.add('/posts/:id',  :posts_show)

m = set.match('/users/42')
m.value          # => :users_show
m.params['id']   # => '42'

Constructor shorthand with a hash

set = Mustermann::Set.new('/users/:id' => :users_show, '/posts/:id' => :posts_show)

Block syntax

set = Mustermann::Set.new do |s|
  s.add('/users/:id', :users_show)
  s.add('/posts/:id', :posts_show)
end

Defined Under Namespace

Classes: Match

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(*mapping, additional_values: :raise, use_trie: 50, use_cache: true, strict_order: false, **options, &block) ⇒ Set

Creates a new set, optionally pre-populated with patterns.

Patterns can be supplied as a Hash (pattern → value), a plain String or Pattern, an Array of any of these, or an existing Mustermann::Set. The same forms are accepted by #update and #add.

Examples:

Empty set

Mustermann::Set.new

Pre-populated from a hash

Mustermann::Set.new('/users/:id' => :users, '/posts/:id' => :posts)

Imperative block

Mustermann::Set.new do |s|
  s.add('/users/:id', :users)
end

Zero-argument block returning a mapping hash

Mustermann::Set.new { { '/users/:id' => :users } }

Parameters:

  • mapping (Array) —

    initial patterns or mappings to add

  • additional_values (:raise, :ignore, :append) (defaults to: :raise) —

    behavior when extra keys are passed to #expand. Defaults to :raise

  • use_trie (Boolean, Integer) (defaults to: 50) —

    whether to use a trie for matching If an Integer is given, it is the number of patterns at which to switch from linear to trie matching. Defaults to 50

  • use_cache (Boolean) (defaults to: true) —

    whether to cache matches not yet garbage collected. Defaults to true

  • strict_order (Boolean) (defaults to: false) —

    whether to match patterns in strict insertion order rather than trie order. Defaults to false. See #use_strict_order? for details

  • options (Hash) —

    pattern options forwarded to Mustermann.new (e.g. type: :rails)

Raises:

  • (ArgumentError) —

    if additional_values is not a recognized behavior symbol



85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
# File 'lib/mustermann/set.rb', line 85

def initialize(*mapping, additional_values: :raise, use_trie: 50, use_cache: true, strict_order: false, **options, &block)
  raise ArgumentError, "Illegal value %p for additional_values" % additional_values unless Expander::ADDITIONAL_VALUES.include? additional_values
  raise ArgumentError, "Illegal value %p for use_trie" % use_trie unless [true, false].include?(use_trie) or use_trie.is_a? Integer

  @use_trie          = use_trie
  @use_cache         = use_cache
  @matcher           = nil
  @mapping           = {}
  @reverse_mapping   = {}
  @options           = {}
  @expanders         = {}
  @additional_values = additional_values
  @strict_order      = strict_order

  options.each do |key, value|
    if key.is_a? Symbol
      @options[key] = value
    else
      mapping << { key => value }
    end
  end

  update(mapping)

  block.arity == 0 ? update(yield) : yield(self) if block

  optimize!
end

Instance Attribute Details

#options ⇒ Hash (readonly)

Pattern options forwarded to Mustermann.new when patterns are created from strings.

Returns:

  • (Hash) 


42
43
44
 
# File 'lib/mustermann/set.rb', line 42

def options
  @options
end

Instance Method Details

#[](pattern_or_string) ⇒ Object?

Looks up a value by string or retrieves the first value for a known pattern object.

When given a String, it is matched against the set and the associated value of the first matching pattern is returned. When given a Pattern, the first value registered for that exact pattern is returned without matching.

Examples:

String lookup

set['/users/42']  # => :users_show (or nil)

Pattern lookup

pattern = Mustermann.new('/users/:id')
set[pattern] # => :users_show (or nil)

Parameters:

  • pattern_or_string (String, Pattern)

Returns:

  • (Object, nil) —

    the associated value, or nil if not found

Raises:

  • (ArgumentError) —

    for unsupported argument types



234
235
236
237
238
239
240
 
# File 'lib/mustermann/set.rb', line 234

def [](pattern_or_string)
  case pattern_or_string
  when String  then match(pattern_or_string)&.value
  when Pattern then values_for_pattern(pattern_or_string)&.first
  else raise ArgumentError, "unsupported pattern type #{pattern_or_string.class}"
  end
end

#add(pattern, *values) ⇒ self Also known as: []=

Adds a pattern to the set, optionally associated with one or more values.

If the pattern is given as a String it will be compiled via Mustermann.new using the set’s own options. The pattern must be AST-based (Sinatra, Rails, and similar types). Plain regexp patterns are not supported.

Calling add more than once for the same pattern appends additional values without creating duplicates.

Examples:

set.add('/users/:id', :users)
set.add('/users/:id', :admin)   # same pattern, second value

Parameters:

  • pattern (String, Pattern) —

    the pattern to add

  • values (Array) —

    zero or more values to associate with the pattern

Returns:

  • (self)

Raises:

  • (ArgumentError) —

    if the pattern is not AST-based, or if a reserved symbol is used as a value



187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
 
# File 'lib/mustermann/set.rb', line 187

def add(pattern, *values)
  pattern = Mustermann.new(pattern, **options)
  raise ArgumentError, "Non-AST patterns are not supported" unless pattern.respond_to? :to_ast

  if @mapping.key? pattern
    current = @mapping[pattern]
  else
    add_pattern(pattern)
    current = @mapping[pattern] = []
  end

  values = [nil] if values.empty?

  values.each do |value|
    raise ArgumentError, "%p may not be used as a value" % value if Expander::ADDITIONAL_VALUES.include? value
    raise ArgumentError, "the set itself may not be used as value" if value == self
    next if current.include? value
    current << value
    @reverse_mapping[value] ||= []
    @reverse_mapping[value] << pattern unless @reverse_mapping[value].include? pattern
    @expanders[value]&.add(pattern)
    @matcher.track(pattern, value) if strict_order?
  end

  self
end

#expand(value = self, behavior = nil, values = nil) ⇒ String

Generates a string from a parameter hash using the patterns in the set.

When called with just a parameter hash, the first pattern that can be fully expanded with those keys is used. Pass a value as the first argument to restrict expansion to the patterns associated with that value. You may also pass an additional_values behavior symbol (:raise, :ignore, or :append) as the first argument to override the set’s default behavior for that call.

Examples:

Expand using any pattern

set.expand(id: '5')

Expand patterns for a specific value

set.expand(:users, id: '5')

Override additional_values behavior for one call

set.expand(:ignore, id: '5', extra: 'ignored')

Parameters:

  • value (Object, :raise, :ignore, :append) (defaults to: self) —

    the value whose patterns should be used, or an additional_values behavior symbol; defaults to all patterns

  • behavior (:raise, :ignore, :append, nil) (defaults to: nil) —

    how to handle extra keys; defaults to the set’s additional_values setting

  • values (Hash, nil) (defaults to: nil) —

    the parameters to expand

Returns:

  • (String)

Raises:



357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
 
# File 'lib/mustermann/set.rb', line 357

def expand(value = self, behavior = nil, values = nil)
  if Expander::ADDITIONAL_VALUES.include? value
    if behavior.is_a? Hash
      values   = values ? values.merge(behavior) : behavior
      behavior = nil
    elsif behavior and behavior != value
      raise ArgumentError, "behavior specified multiple times" if behavior
    end
    behavior = value
    value    = self
  elsif value.is_a? Hash and behavior.nil? and values.nil?
    values = value
    value  = self unless @reverse_mapping.key? values
  end
  expander(value).expand(behavior || @additional_values, values || {})
end

#expander(value = self) ⇒ Mustermann::Expander

Returns an Expander that can generate strings from parameter hashes.

When called without arguments (or with the set itself as the value) the expander covers all patterns in the set. Pass a specific value to get an expander limited to the patterns associated with that value.

Parameters:

  • value (Object) (defaults to: self) —

    restricts the expander to patterns associated with this value; defaults to the set itself (all patterns)

Returns:



324
325
326
327
328
329
 
# File 'lib/mustermann/set.rb', line 324

def expander(value = self)
  @expanders[value] ||= begin
    patterns = value == self ? @mapping.keys : @reverse_mapping[value] || []
    Mustermann::Expander.new(patterns, additional_values: @additional_values, **options)
  end
end

#has_value?(value) ⇒ Boolean

Returns whether the set contains any pattern associated with the given value.

Returns:

  • (Boolean) —

    whether the set contains any pattern associated with the given value



375
 
# File 'lib/mustermann/set.rb', line 375

def has_value?(value) = @reverse_mapping[value]&.any?

#match(string) ⇒ Set::Match?

Matches the string against all patterns in the set and returns the first match.

Parameters:

  • string (String) —

    the string to match

Returns:

  • (Set::Match, nil) —

    the first match, or nil if none of the patterns match



246
 
# File 'lib/mustermann/set.rb', line 246

def match(string) = @matcher&.match(string)

#match_all(string) ⇒ Array<Set::Match>

Matches the string against all patterns and returns every match, one per (pattern, value) pair, in insertion order.

Parameters:

  • string (String)

Returns:

  • (Array<Set::Match>) —

    all matches, or an empty array if none



261
 
# File 'lib/mustermann/set.rb', line 261

def match_all(string) = @matcher&.match(string, all: true)

#merge(mapping) ⇒ Set

Returns a new set that includes all patterns from the receiver plus those from mapping. The receiver is not modified.

Parameters:

  • mapping (Hash, String, Pattern, Array, Set) —

    patterns to merge in

Returns:

  • (Set) —

    a new set



276
 
# File 'lib/mustermann/set.rb', line 276

def merge(mapping) = dup.update(mapping)

#optimize! ⇒ Object

Runs trie optimizations pro-actively and explicitly rather than at match time.



381
 
# File 'lib/mustermann/set.rb', line 381

def optimize! = @matcher&.optimize!

#patterns ⇒ Array<Pattern>

Returns all patterns that have been added to the set, in insertion order.

Returns:



313
 
# File 'lib/mustermann/set.rb', line 313

def patterns = @mapping.keys

#peek_match(string) ⇒ Set::Match?

Matches the beginning of the string against all patterns and returns the first prefix match. The unmatched remainder of the string is available via Match#post_match.

Parameters:

  • string (String)

Returns:

  • (Set::Match, nil) —

    the first prefix match, or nil



254
 
# File 'lib/mustermann/set.rb', line 254

def peek_match(string) = @matcher&.match(string, peek: true)

#peek_match_all(string) ⇒ Array<Set::Match>

Matches the beginning of the string against all patterns and returns every prefix match, one per (pattern, value) pair. The unmatched remainder is available as Match#post_match on each result.

Parameters:

  • string (String)

Returns:

  • (Array<Set::Match>) —

    all prefix matches, or an empty array if none



269
 
# File 'lib/mustermann/set.rb', line 269

def peek_match_all(string) = @matcher&.match(string, all: true, peek: true)

#strict_order? ⇒ Boolean

A set can match patterns and values in loose or strict insertion order.

You have the following guarantees without strict ordering:

  • Patterns with dynamic segments in the same position and equal static parts will always match in the order they were added.

  • Multiple values for the same pattern will retain their insertion order in regards to that pattern.

Trade-offs without strict ordering:

  • Static segments may be favored over dynamic segments. If you want to guarantee this behavior, enable trie-mode proactively.

  • When a pattern has multiple values, these will follow each other directly when using #match_all or #peek_match_all.

Strict ordering comes with both a performance overhead and marginally increased memory usage. How big the performance overhead is depends on the number of patterns that overlap in the strings they successfully match against. It does use Ruby’s built-in sorting, which on MRI is based on quicksort. The memory overhead grows linear with the number of pattern and value combinations, but is generally small compared to the memory used by the patterns and values themselves.

With strict ordering enabled, patterns and values are guaranteed to occur in insertion order.

Examples:

Without strict ordering, not using a trie

set = Mustermann::Set.new(use_trie: false)

set.add("/:path",  :first)
set.add("/static", :second)
set.add("/:path",  :third)

set.match("/static").value             # => :first
set.match_all("/static").map(&:value)  # => [:first, :third, :second]

Without strict ordering, using a trie

set = Mustermann::Set.new(use_trie: true)

set.add("/:path",  :first)
set.add("/static", :second)
set.add("/:path",  :third)

set.match("/static").value             # => :second
set.match_all("/static").map(&:value)  # => [:second, :first, :third]

With strict ordering

set = Mustermann::Set.new(strict_order: true)

set.add("/:path",  :first)
set.add("/static", :second)
set.add("/:path",  :third)

set.match("/static").value             # => :first
set.match_all("/static").map(&:value)  # => [:first, :second, :third]

Returns:

  • (Boolean) —

    whether matching happens in strict pattern/value insertion order



162
 
# File 'lib/mustermann/set.rb', line 162

def strict_order? = @strict_order

#update(mapping) ⇒ self Also known as: merge!

Adds all patterns from mapping to the set in place and returns self. Aliased as merge!.

Accepts the same argument forms as #initialize: a Hash, a String, a Pattern, an Array, or another Mustermann::Set.

Parameters:

Returns:

  • (self)

Raises:

  • (ArgumentError) —

    for unsupported mapping types



298
299
300
301
302
303
304
305
306
307
 
# File 'lib/mustermann/set.rb', line 298

def update(mapping)
  case mapping
  when Set             then mapping.mapping.each { |pattern, values| add(pattern, *values) }
  when Hash            then mapping.each { |k, v| add(k, v) }
  when String, Pattern then add(mapping)
  when Array           then mapping.each { |item| update(item) }
  else raise ArgumentError, "unsupported mapping type #{mapping.class}"
  end
  self
end

#use_cache? ⇒ Boolean

Returns whether caching is enabled.

Returns:

  • (Boolean) —

    whether caching is enabled



165
 
# File 'lib/mustermann/set.rb', line 165

def use_cache? = @use_cache

#use_trie? ⇒ Boolean

Returns whether trie optimization is enabled.

Returns:

  • (Boolean) —

    whether trie optimization is enabled



168
 
# File 'lib/mustermann/set.rb', line 168

def use_trie? = @use_trie == true