Class: Dommy::Internal::SelectorIndex

Inherits:
Object
  • Object
show all
Defined in:
lib/dommy/internal/selector_index.rb

Overview

A by-id / by-class / by-tag index over a document's backend element tree, in document order. It turns a fast_query pre-filter from an O(tree) walk ("visit every node, test it") into an O(matches) lookup ("here are the nodes with class X"). Built once and memoized per DOM generation (Document#style_generation) — a mutation invalidates it, and the NEXT query rebuilds it, so on a page that fires many queries between mutations (jQuery $.find storms) it is a big win, while a build costs the same single tree walk it replaces, so it never loses to the plain walk.

Works for ELEMENT-scoped queries too (jQuery's .find is el.querySelectorAll): each element gets a pre-order interval [enter, exit] during the build, so a candidate is inside a scope element's subtree iff its enter falls in the scope's (enter, exit] — an O(candidates) range test, no per-node ancestor walk. Candidates are stored as [enter, node] in document order.

Holds backend nodes (never wrapped); the caller wraps only candidates and still runs the authoritative #matches?, so the index need only be a SUPERSET (tag matching is case-insensitive here; exact case / namespace stays #matches?'s job).

Constant Summary collapse

EMPTY = 
[].freeze

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SelectorIndex

Returns a new instance of SelectorIndex.



31
32
33
34
35
36
37
 
# File 'lib/dommy/internal/selector_index.rb', line 31

def initialize
  @by_id = {}
  @by_class = {}
  @by_tag = {}
  @extent = {} # node pointer_id => [enter, exit] pre-order interval
  @counter = 0
end

Class Method Details

.build(backend_doc) ⇒ Object 



27
28
29
 
# File 'lib/dommy/internal/selector_index.rb', line 27

def self.build(backend_doc)
  new.tap { |index| index.populate(backend_doc) }
end

Instance Method Details

#any_ancestor?(prefilter, enter_l) ⇒ Boolean

Is there an indexed element matching prefilter whose subtree contains the element at pre-order position enter_l — i.e. does that element have an ANCESTOR matching the prefilter? Answered in O(log) via a prefix-max of the matching elements' exit over their (sorted) enters: an interval [enter, exit] contains enter_l iff enter < enter_l <= exit, and by the pre-order property that element is then an ancestor. Used to settle a descendant combinator's leftmost compound without walking ancestors.

Returns:

  • (Boolean) 


86
87
88
89
90
91
92
93
94
 
# File 'lib/dommy/internal/selector_index.rb', line 86

def any_ancestor?(prefilter, enter_l)
  enters, max_exits = prefix_max_exit(prefilter)
  return false unless enters

  # last index with enters[i] < enter_l
  gte = enters.bsearch_index { |enter| enter >= enter_l } || enters.length
  i = gte - 1
  i >= 0 && max_exits[i] >= enter_l
end

#candidates(prefilter, scope_node = nil) ⇒ Object

Backend nodes for an indexable pre-filter ([:id|:class|:type, value]), optionally restricted to scope_node's subtree; nil when the index can't serve it (a non-indexable :attr, or a scope it doesn't know) so the caller falls back to the walk.



57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
# File 'lib/dommy/internal/selector_index.rb', line 57

def candidates(prefilter, scope_node = nil)
  entries = entries_for(prefilter)
  return nil unless entries

  if scope_node.nil?
    entries.map { |_enter, node| node }
  else
    ext = @extent[scope_node.pointer_id]
    return nil unless ext # detached / unknown scope -> let the caller walk

    lo, hi = ext
    entries.each_with_object([]) { |(enter, node), out| out << node if enter > lo && enter <= hi }
  end
end

#enter_of(node) ⇒ Object

The pre-order enter number of a backend node (its position), or nil if the node isn't in this index (detached / unknown).



74
75
76
77
 
# File 'lib/dommy/internal/selector_index.rb', line 74

def enter_of(node)
  ext = @extent[node.pointer_id]
  ext && ext[0]
end

#populate(node) ⇒ Object

Walk the backend element tree in document order, numbering each element and recording it under its id / classes / tag.



41
42
43
44
45
46
47
48
49
50
51
 
# File 'lib/dommy/internal/selector_index.rb', line 41

def populate(node)
  child = node.first_element_child
  while child
    enter = (@counter += 1)
    record(child, enter)
    populate(child)
    @extent[child.pointer_id] = [enter, @counter]
    child = child.next_element
  end
  self
end